CSCI 2100B编程代写、C++程序语言代做、代写Data Structures

日期：2021-03-15 11:22

CSCI 2100B Data Structures

Assignment 2

Due Date: 16 March 2021

Written Exercises

1. Write the following function that makes use of the listADT of list of integers:

listADT moveMinToHead(listADT);

which moves the minimum element in the list to the head of the list if the argument

list is nonempty, or returns an empty list otherwise. For examples,

• moveMinToHead([]) = []

• moveMinToHead([3,4,8,2,4]) = [2,3,4,8,4]

• moveMinToHead([3,5]) = [3,5]

• moveMinToHead([7]) = [7]

a) Write this function as a recursive function. Hint: Call moveMinToHead with the tail

as the argument.

b) Write this function as a nonrecursive function.

2. Write the following function that sorts the argument list into ascending order by

selection sort:

listADT selectionSort(listADT);

Hint: Make use of the moveMinToHead function.

3. Use the selection sort algorithm to sort the following sequence of integers into

ascending order:

1, 8, 6, 6, 5, 7, 9

Show clearly each step in the process of sorting.

4. Write the following functions as recursive functions in C. You should use the list

operations defined in list ADT shown in the lecture notes. You can simply call

exit(EXIT_FAILURE) when error conditions are encountered. Note that your functions

should work well with any correct implementation of list ADT.

a) The function listIsSorted that accepts a listADT argument and returns an int value

1 if the argument list is sorted, or 0 otherwise. For examples:

§ listIsSorted([7,8,1,5,3]) = 0

§ listIsSorted([4,5,6,7]) = 1

§ listIsSorted([0]) = 1

§ listIsSorted([]) = 1

b) The function lastButOne that accepts a listADT argument and returns an int value

that is the last-but-one value in the list. For examples:

§ lastButOne([3,4,8,2,4]) = 2

§ lastButOne([0,1]) = 0

§ lastButOne([]) = ERROR

§ lastButOne([4]) = ERROR

c) The function member that accepts an int argument and a listADT argument, and

returns an int value true if the int argument is in the listADT argument, or 0

otherwise. For examples:

§ member(2, [3,4,8,2,4]) = 1

§ member(4, [3,5]) = 0

d) The function firstN that accepts a listADT argument and an int argument N, and

returns a listADT value that is the list of the first N elements of the argument, until

the end of the list. For examples:

§ firstN([3,4,8,2,4], 3) = [3,4,8]

§ firstN([2,4,6], 8) = [2,4,6]

§ firstN([], 0) = []

§ firstN([], 1) = []

§ firstN([8,7,6], 3) = [8,7,6]

e) The function evenOnly that accepts an int argument and a listADT argument, and

returns a listADT result that is the same as the List argument, except that all the

odd numbers are removed. For examples:

§ evenOnly([3,4,8,2,4]) = [4, 8, 2, 4]

§ evenOnly([3,5]) = []

§ evenOnly([2,8,4]) = [2, 8, 4]

§ evenOnly([]) = []

f) The function listsAreDifferent that accepts two listADT arguments, and returns an

int value 1 if the listADT arguments are different, or 0 otherwise. For examples:

§ listsAreDifferent([], [3,4,8,2,4]) = 1

§ listsAreDifferent([2], []) = 1

§ listsAreDifferent([], []) = 0

§ listsAreDifferent([39,3,8,12,3], [39,3,8,11,3]) = 1

§ listsAreDifferent([39,3,8,12,3], [39,3,8,12,3]) = 0

5. In the implementation version 2.0 of list ADT, we use a linked list-based

implementation of lists. On page 13 of lecture notes LN6-2a, we show list1 and list2

after a few statements are executed. For each of the code segments shown below,

show the linked list-based implementation of lists list1, list2 and list3 after all the

statements in the code segment are executed (you should assume that list1, list2 and

list3 are all properly declared as listADT variables). You should also indicate what will

be outputted from each of the code segments that contain printf statements.

a) list1 = Cons(4, Cons(5, Cons(6, EmptyList())));

list2 = Cons(Head(list1), list1);

b) list1 = Cons(3, Cons(7, Cons(6, EmptyList())));

list2 = Cons(Head(list1), Tail(list1));

list3 = Cons(0, list2);

c) listElementT firstElement, secondElement;

list1 = Cons(8, Cons(4, Cons(7, EmptyList())));

firstElement = Head(list1);

secondElement = Head(Tail(list1));

list3 = Cons(secondElement, Tail(Tail(list1)));

list2 = Cons(secondElement, Cons(firstElement, list3));

d) if (listEqual(EmptyList(), EmptyList()))

printf("listEqual(EmptyList(), EmptyList())\n");

else

printf("Not listEqual(EmptyList(), EmptyList())\n");

if (EmptyList() == EmptyList())

printf("EmptyList() == EmptyList()");

else

printf("EmptyList() != EmptyList()");

e) list1 = Cons(8, Cons(4, Cons(7, EmptyList())));

list3 = Tail(Tail(list1));

list2 = Cons(Head(Tail(list1)), Cons(Head(list1), list3));

Programming Exercises

6. There are two parts in this programming exercise.

a) (Part 1) In the lecture notes we have seen how to implement symbol tables using

Hash tables. In the version we present in the lecture notes, we use the technique

of separate chaining to resolve collisions. We shall call this version 1.0.

Implement version 2.0 of symtabADT, in which you use quadratic probing (instead

of separate chaining) for collision resolution. You should use F(i)=i

2 in your

implementation. Also you should set the table size at 51. You should use the

following hash function.

int Hash(char *s, int n) {

unsigned long hashcode = 0UL;

for (int i=0; s[i]!='\0'; i++) hashcode = (hashcode<<6) + (unsigned long) s[i];

return (int) (hashcode % n);

}

In your implementation, you should use the following definition for struct

symtabCDT:

typedef struct bucketT {

int inUse; // This is 1 if the bucket is in use, or 0 otherwise

char *key;

void *value; } bucketT;

struct symtabCDT { bucketT bucket[nBuckets]; };

where nBuckets is constant 51 defined using #define in symtab.c.

You shall need to implement at least four functions: EmptySymbolTable, Enter,

Lookup, and ForEachEntryDo.

Note: you only need to submit symtab.c that implements version 2.0 of

symtabADT.

b) (Part 2) Prof. Chan is teaching a course that is open to both postgraduate and

undergraduate students. Prof. Chan decides to use different scales for

postgraduate and undergraduate students to convert from numeric marks to

grades.

The class list with marks of individual students is stored in a student data file

studentData.txt. The format of the student data file is shown as follows:

218432

CHAN TAI MAN

78

200987

CHEUNG MAN MING

90

217748

MAN TAI SUN

75

216639

YEUNG WING KEUNG

98

A student’s information is stored in four separate lines in the student data file. The

first line is a 6-digit student number, the second line is the student’s name, and

the third line the student’s mark (which is an integer). Whether a student is a

postgraduate student or an undergraduate student is indicated by his or her

student number: if the second digit is 0, then the student is a postgraduate student;

otherwise, the student is an undergraduate student. The total number of students

is not known in advance, so you need to read the file until the end of file is reached.

There is another file called the data correction file dataCorrection.txt. If there is

any mistake in the studentData.txt file, then the correction information will

appear in the data correction file for correction purpose. A student’s information

is stored in two separate lines in the data correction file. The first line is a 6-digit

student number, and the second line the student’s correct mark (which is an

integer). We assume that there is only one data correction file for all teachers,

that is, it might contain information about a student whose student number does

not appear in the original student data file. This is because it is actually a correction

for the student data file of another teacher. If this happens, the you can simply

ignore it. The following is an example of the data correction file:

In this case the student whose student number is 200100 does not appear in the

data file, so it can be ignored.

Write a program that first reads the student data file and then the data correction

file, and outputs the grades of each of the students in a file. The following is a

sample output for the above input file (the order is not important).

218432 CHAN TAI MAN

B

200987 CHEUNG MAN MING

A

217748 MAN TAI SUN

B

216639 YEUNG WING KEUNG

A

Note 1

You must use the following implementation:

1. You must first use typedef to define a structure type StudentT for a structure

with 3 fields.

§ The first field sName is a string that stores the name of the student.

§ The second field level is a value of type studentLevelT

(studentLevelT level), where studentLevelT is an enum type defined

as

typedef enum {UG, PG} studentLevelT;

§ The last field mark is an int value (int mark) that stores the student’s

examination mark.

2. There is a function char getGrade(StudentT) to determine the grade for

each of the students.

The conversion schemes for undergraduates and postgraduates are as follows:

Undergraduate Postgraduate

87 – 100 A 90 – 100 A

72 – 86 B 75 – 89 B

59 – 71 C 65 – 74 C

50 – 58 D < 65 F

< 50 F

Note 2

You should use a symbol table to store the students’ information in your program.

The key is the student IDs. The data stored in the table should be pointers of type

StudentT*, which point to structures of type StudentT. For simplicity, you can

assume that the table will never be full.

Your program should work well using the symtab.h and symtab.c in the lecture

notes and in Part 1 of the question.

Note 3

To output the grades of all students, you must use a call back function

void displayStudentNameAndGrade(char*, StudentT*)

to display all entries in the table (the order is not important). You may use the

mapping function forEachEntryDo defined in the lecture notes.