COMP9024 Assignment One Doubly Linked Lists and Sets
Objectives
• Give you further practice with C and data structures
Admin
Marks 10 marks Marking is based on the correctness and efficiency of your code. Your code must be well commented.
Group? This assignment is completed individually
Aims
Assume that adjacent integers in the file filename and the standard input are separated by one or more white space characters or a new line character.
If filename is “stdin”, CreateDLListFromFileDlist (“stdin”) creates a doubly linked list by reading all integers from the standard input and the word end denotes the end of input.
This function must check for invalid input. In case of invalid input, it prints an error message “Invalid input!” and returns NULL. (2 marks)
2. void printDLList(DLList *u ). This function prints all the elements (integers) of a doubly linked list pointed by u in the order from the first node to the last node in the list on the standard output, one element per line. (1.2 marks)
3. DLList *cloneList(DLList *u). This function creates an identical copy of a doubly linked list u and returns a pointer to the list cloned. (1.6 marks)
element (int) of a set is stored in a node of the corresponding doubly linked list.
Given two sets A and B, the union of A and B is a set that contains all the distinct element of A and B. For example, assuming that A = {2, 8, 5, 7} and B = {5, 9, 6, 7}, A ꓴ B = {2, 8, 5, 7, 9, 6}. Note that in a set, all the integers are not necessarily sorted. (2 marks)
intersection. Each element (int) of a set is stored in a node of the corresponding doubly linked list. (2 marks)
For simplicity, you may assume that all the elements of each input set are distinct for both set union and set intersection. Therefore, you do not need to check if a set contains duplicates.
Given two sets A and B, the intersection of A and B is a set that contains all the elements of A that are also in B. For example, assuming that A = {2, 8, 5, 7} and B = {5, 9, 6, 7}, A ꓵ B = {5, 7}.
6. void freeDLList(DLList *u). This function frees the space occupied by all the nodes of the doubly linked list pointed by u. (1.2 marks)
Time complexity analysis: For each function, you need to analyze its time complexity in terms of big-O notation and put your analysis as comments immediately before the code of the function. You may assume that a single execution of each built-in I/O function such as printf(), malloc() and free(), takes O(1) time.
How to submit your code?
Plagiarism
2020-03-05