COMP9024 Assignment One
Doubly Linked Lists and Sets
Objectives
· Give you experience with doubly linked lists and using doubly linked lists to solve set problems
· 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
Due Time 23:59:59pm Sunday March17, 2018.
Late Submissions Late submissions will not be accepted!
Aims
In this assignment, you will implement a set of functions based on the doubly linked list defined in MyDLList.c.
The functions you need to implement are shown as follows:
1. DLList *CreateDLListFromFileDlist(const char *filename). This function creates a doubly linked list of integers by reading all integers from a text file named filename, and returns a pointer to the doubly linked list created. Assume that adjacent integers in the file filename 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. Assume that each input line is an integer and an empty line denotes end of input.
2. void printDLList(DLList *u ). This function prints all the elements (integers) of a doubly linked list pointed by u on the standard output, one element per line.
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.
4. DLList *setUnion(DLList *u, DLList *v). This function computes the union of the two sets of integers that are stored in the doubly linked lists pointed by u and v, respectively, and returns a pointer to the doubly linked list that stores the union. Each 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.
5. DLList *setIntersection(DLList *u, DLList *v). This function computes the intersection of the two sets of integers that are stored in the doubly linked lists pointed by u and v, respectively, and returns a pointer to the doubly linked list that stores the intersection. Each element (int) of a set is stored in a node of the corresponding doubly linked list.
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}.
For simplicity, you may assume that all the elements of each set are distinct. Therefore, you do not need to check if a set contains duplicates.
6. void freeDLList(DLList *u). This function frees the space occupied by all the nodes of the doubly linked list pointed by u.
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 function, including malloc() and free(), takes O(1) time.
Major steps
1. Download the latest Eclipse C/C++ IDE.
2. Create a project.
3. Create a file MyDLList.c and copy the code of MyDLList.c given in this assignment to this file.
How to submit your code?
1. Go to the assignment one page
2. Click on Assignment Specfications
2. Click on Make Submission
3. Submit your MyDLList.c file that contains all the code.
Plagiarism
This is an individual assignment. Each student will have to develop their own solution without help from other people. In particular, it is not permitted to exchange code or pseudocode. You are not allowed to use code developed by persons other than yourself. All work submitted for assessment must be entirely your own work. We regard unacknowledged copying of material, in whole or part, as an extremely serious offence. For further information, see the Course Information.