Objective: Write a C program that takes as input a list of integers (in random o
ID: 3621580 • Letter: O
Question
Objective:
Write a C program that takes as input a list of integers (in random order),
stores the integers in a linked list, and orders the list using the MergeSort
Specifications:
1. The program will read data from an input file and store the data in a
doubly-linked list.
2. The program will order the data using the MergeSort algorithm.
3. The program will display the sorted data to the user.
4. The program will have an abstract data type (ADT) for the doublylinked
list and will protect the struct by placing it in a List.c file, and
having just a typedef for the struct in the List.h file.
5. All code associated with the ADT will be placed in separate files and
included in the driver program. (Note: only include the .h file.)
6. The file that the program uses will have the following name: “Data.txt”.
7. The program will have appropriate programmer-defined functions
so that the main function provides a highlight of the program.
Turn in: (I'm not sure which part of my code goes into each of the .h and .c files)
You will submit a zipped (compressed) file to the course dropbox. It will contain five
files:
• List.h
• List.c
• MergeSort.h
• MergeSort.c
• Proj5.c
This is the help that she offered:
MergeSort is a recursive algorithm that divides an array into smaller and smaller subarrays (until they are sorted by defautl), and then combines the sorted subarrays into an ordered array. The algorithm presented and discussed in class uses the assumption that the elements are stored in an array. What if the data were stored in a doubly-lineked list rather than an array? What would be done differently?
One of the critical issues is how you would divide the list of numbers into two lists. With arrays, we simply manipulated the index numbers to have a start location, a stop location, and a middle location. This will be trickier with a linked list. First, how would we know the number of elements in the list?
Second, how would we get to the middle element? These are issues that you will need to think about for this project. Also, one of the ideas behind an Abstract Data Type (ADT) is that we want to protect data from being corrupted by various parts of the program. To fully protect our data, we can put the struct in our .c file and a typedef to it in our .h file. This would prevent any function other than those associated with the struct to have access to the elements of the struct.
Explanation / Answer
Dear, Giving you just List.h and list.c files for doubly linked list #include #include #include "Node.h" typedef struct list List; typedef struct list * ListPtr; struct list { int size; NodePtr head; NodePtr tail; }; /* prototypes of public methods */ ListPtr createList(); /* constructor */ int getSize(ListPtr L); Boolean isEmpty(ListPtr L); void addAtFront(ListPtr list, NodePtr node); void addAtRear(ListPtr list, NodePtr node); NodePtr removeFront(ListPtr list); NodePtr removeRear(ListPtr list); void reverseList(ListPtr L); void printList(ListPtr L); #endif /* __LIST_H */ #include #include #include "List.h" /*list.c Contains functions to manipulate a doubly-linked list.*/ /* private methods */ static NodePtr reverse(NodePtr L); static void print(NodePtr node); ListPtr createList() { ListPtr list = (ListPtr) malloc(sizeof(ListPtr)); list->size = 0; list->head = NULL; list->tail = NULL; return list; } int getSize(ListPtr L) { return L->size; } Boolean isEmpty(ListPtr L) { if (L->size == 0) return TRUE; else return FALSE; } void addAtFront(ListPtr list, NodePtr node) { if (list == NULL) return; if (node == NULL) return; & $ % list->size++; node->next = list->head; node->prev = NULL; if (list->head == NULL) { list->head = node; list->tail = node; } else { list->head->prev = node; list->head = node; } } void addAtRear(ListPtr list, NodePtr node) { } NodePtr removeFront(ListPtr list) { return NULL; } NodePtr removeRear(ListPtr list) { return NULL; } void reverseList(ListPtr L) { L->tail = L->head; L->head = reverse (L->head); } static NodePtr reverse(NodePtr L) { NodePtr list = NULL; while (L != NULL) { NodePtr tmp = L; L = L->next; if (L != NULL) L->prev = tmp; tmp->next = list; tmp->prev = L; list = tmp; } return list; } void printList(ListPtr L) { print(L->head); } static void print(NodePtr node) { while (node) { printf(" %s -->",toString(node->data)); node = node->next; } printf(" NULL "); } Hope this will help you..Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.