Create a modular program in C that generates and modifies a number of circular double linked lists.
Each node in the circular double linked list should have two pointers which should “point” to the next and the previous node. And that the double linked list is in the form of a ring i.e. the first node’s back pointer should contain the address of the last node and the last node’s forward pointer should contain the address of the first node.
Each ringed double linked list should grow or reduce in size without the ring structure being broken. For each ring you will require a pointer, which should contain the address of the 1st node (start node).
Each node should contain the following fields, two pointers, one to hold address of the next node, the forward pointer and a second the back pointer, to hold the address of the previous node, and a character array of length 30 bytes.
Your program should provide a menu offering the following options
1. Generate a circular double linked list --- this option should prompt the user to name a text file; open the text file and then generate the circular linked list. For each string(word) in the file the program should generate a new node and insert this between the 1st and last node in the current ring, and so the new node once inserted becomes the last node. When complete i.e. the program encounters the end of the file character the file should be closed and the program should then provide the user with a label(this can be an integer) to identify the circular linked list, along with the labels of the existing circular double linked lists and then display the complete menu.
2. Print out the string fields of a double linked list – this option should prompt the user to type in the label of a given ringed double linked list and then the resultant strings should be displayed on screen.
3. Delete node/s – this option should prompt the user to type in the label of a given ringed double linked list and then display a sub menu which will offer the following
i. Search for a single string deleting the 1st instance – this will search through the linked list from the 1st node to the last and on the 1st instance of the string encountered it should delete the node and then the program should go back to the main menu.
ii. Search for a single string to delete all confirmed instances – this will search through the linked list and on finding a match should display the node number (1 for the 1st ,2 for the 2nd etc) and prompt the user if they wish to delete the given node if Y, or y is pressed then that node should be deleted. This process will run through all the nodes until the last node and then go back to the main menu
iii. Delete nodes – the program should offer the user a number range from 1 to the number of nodes in the ring and then ask the user to type in which nodes to be deleted. On completion the program should go back to the main menu
4. ADD node/s this option should prompt the user to type in the label of a given ringed double linked list and then display a sub menu which will offer the following
i. Insert node to the beginning of list – This will prompt the user to type in a string and then insert the node generated at the front of the linked list (This will become the new start node).
ii. Insert node to the end of the list – This will prompt the user to type in a string and then insert the node at the last node of the linked list
iii. Insert node between two nodes. The program will list the nodes from 1 to N with their corresponding string and then ask the user for two node numbers. On inserting the node the program should return back to main menu.
iv. Insert more than one node. The program will list the nodes from 1 to N with their corresponding string and then ask the user for two node numbers. It should then prompt the user for the string where for each word in the string a new node will created and then this should be inserted into the ring between the two identified nodes. On completion the program should then return back to main menu.
5. Merging a number of ringed double linked list – the program should display the available rings and then prompt the user to input which rings to be merged. The rings should be merged by interleaving the nodes.
e.g. if 2 rings exist and they are labeled A and B respectively and ring A has the following nodes A1, A2, A3 in order from the start node and subsequently ring B contains the following sequence of nodes B1, B2, B3 from the start node. Then Merging would result in a ring with the following order of nodes A1,B1,A2,B2,A3,B3.
Note – you must not generate any new nodes but just re-direct the pointer addresses to form the new structure.
When merging more than two rings then your program should merge the 1st two rings and then with the resultant ring merge with the 3rd ring and so on.
• Note menu options 2-5 should only be displayed to the user if there are “rings” in memory
• Your program should be modular, with appropriate header files.
• You should create a Makefile such that all the modules are compiled and linked to generate the final executable file.
• You should generate a user guide with screen shots highlighting your programs functionality and also a log to indicate what aspects of your program are complete and error free and which parts of the program are incomplete or have errors.
• All input should be appropriately validated, and your code should also be fully commented.
• You must provide a print out of your code, the user guide, and the log.
• You must provide your listings on a floppy disk or CD, which will be compiled and tested using a Linux machine.
• You must hand in your work by the 10th of December 2007 to the Undergraduate Office.