共计 7928 个字符，预计需要花费 20 分钟才能阅读完成。
CSCI 2100B Data Structures
Assignment 2
Due Date: 16 March 2021
Written Exercises
- 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. - 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. - 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. - 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 - 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 - 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 - 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 - 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). - CHAN TAI MAN
B - CHEUNG MAN MING
A - MAN TAI SUN
B - YEUNG WING KEUNG
A
Note 1
You must use the following implementation: - 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. - 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 - – 100 A 90 – 100 A
- – 86 B 75 – 89 B
- – 71 C 65 – 74 C
- – 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.
正文完
