1. Engineering
  2. Computer Science
  3. in this assignment you will create a doublylinked list adt...

Question: in this assignment you will create a doublylinked list adt...

Question details

In this assignment you will create a Doubly-Linked List ADT module, and use it to perform an Insertion Sort. Another goal of this project is to make sure everyone is up to speed with C, especially pointers and structures, and to build an ADT that can be reused in future assignments. Be sure to read the two files ADT.pdf (which discussed ADTs in Java and C) and ADTRemarks.pdf (which has more information about ADTs in C) before proceeding, paying special attention to the second handout. Both files are on Piazza, under Resources →General Resources. The executable file for this project will be called InsertSortLinked, and will be operated by doing % ins erts or tLinked <input file> <output file> at the command prompt %. The program File 10.c, which is also posted on Resources→ General Resources, shows one way that file input and output can be accomp lished in C. Your List ADT module will be contained in a file called Liste, whose operations will be used by InsertSortLinked. Your List ADT will be a doubly-linked list of Node objects. The underlying data structure for the list will be a doubly linked list of Node objects. You may use the examples Queue.c and Stack.c (provided on Piazza under Resources→QueueExample and Resources→ StackExample) as starting points for your design. Your List module will export a List type along with the follow ing operations. (Some of these operators are not needed for PAl, but you should implement all of them.) Constructors-Destructors- List newList (void)i/7 returns a List which points to a new empty list object void freeList<List pL》; // frees all heap memory associated with its list argument, // and sets pL to NULL Access functions int length(List L)// Returns the number of nodes in this List. int frontValue (List L)// Returns the integer in the front Node. // Precondition: L has at least one Node on it. int backValue (List L) // Returns the integer in the back Node Precondition: L has at least one Node on it. int getValue (Node N) // Returns the integer in Node N / Precondition: N is not NULL int equals (List A, List B: 1/ Returnsl if if List A and List B are the same integer //sequence, otherwise returns .// Manipulation procedures void clear (List L) Node get Front(List L); // Resets this List to the empty state / If List is non-empty, returns the front Node, without /I changing the List. Otherwise, does nothing /1 If List is non-empty, returns the back Node, without /I changing the List. Otherwise, does nothing Node getBack (List L)i Without changing the List that Nis on, returns the Node that is previous to Node N on its List. If Node get PrevNode(Node N); // there is no previous Node, returns NULL Without changing the List that Nis on, returns the Node that is next after Node N on its List If Node getNextNode (Node N) / there is no next Node, returns NULL void prepend (List L, int data)Inserts a new Node into ListLbefore the front Node that has data as its value. If List is empty, // makes that new Node the only Node on the list. void append (List L, int data) Inserts a new Node into List L after the back Node that has data as its value. If List is empty // makes that new Node the only Node on the list. void insertBefore (List L, Node N, int data / Insert a new Node into Node Ns list before Node N that has data as its value Assume that Node N is on List L. If Node N is / the front of List L, then the new Node becomes the new / front Precondition: Node N is not NULL void insertAfter(List L, Node N, înt data); // Insert a new Node into Node Ns list after Node N that has data as its value /Assume that Node N is on List L. If Node N is / the back of List L, then the new Node becomes the new back / Precondition Node N is not NULL / Precondition: L has at least one Node on it / Deletes the back Node in List I void deleteFront (List L) Deletes the front Node in List L void deleteBack(List L); Precondition: L has at least one Node on it // Other operations void printList(FILE Out, List L: 17 Prints the values in List L from front to back // to the file pointed to by out, formatted as a /space-separated string For those familiar with Java, this is similar /1 to tostr ing)in JavaOptional Manipulation procedures void detachNode (List L, Node N):11 This operation is optional. / Removes N from List L by making the Node before Node N link to the Node thats after Node N as its the Node thats before Node N as its previous Node. After detachNode, Node N should have NULL as both its // next Node, and making the Node after Node N link to //next and previous Nodes Special cases: If Node N is the front the List L, then the Node after Node N becomes the front of List L, which should have a NULL previous Node If Node N is the back of List L, then the Node before / Node N becomes the back of List L, which should have /a NULL next Node Precondition: N is not NULL and N is a Node on List L void deleteNode (List L, Node N):11 This operation is optional. Deletes Node N from List L Removes N from List L by making the Node before Node N link to the Node thats after Node N as its //next Node, and making the Node after Node N link to // the Node thats before Node N as its previous Node Special cases: If Node N is the front the List L, then the Node after Node N becomes the front of List L, which should have /a NULL previous Node If Node N is the back of List L, then the Node before Node N becomes the back of List L, which should have a NULL next Node // Precondition: N is not NULL and N is a Node on List L void attachNode Between 《List L, Node N, Node N1 , Node N2); /This operation is optional Attaches Node N between Nodes Nl and N2. Makes NIs //next Node be N, and Ns previous Node be Makes // N2s previous Node be N, and Ns next Node be N2. Special cases: If Nl is NULL and N2 is the front of List L, makes N / the front of List L, which should have a NULL // previous Node, and whose next Node should be N2 If Nl is the back of List L and N2 is NULL, makes N / the back of List L, which should have a NULL next Node, and whose previous Node should be N1 / Preconditions: Nl and N2 are adjacent nodes on List L, with N2 being Nls next node and N1s being N2s // previous node. If Ni is NULL,then N2 is the front of / list L. If N2 is NULL, then Nl is the back of List LThe above methods allow the client of this ADT to iterate over lists. A typical loop in C iterating from the front to the back of List L would be aNodegetFront (L) while (aNode != NULL) { xgetValue (aNode) /I do something with x aNode = ge tNextNode(anode) ; and a similar loop would be used to iterate from back to front.

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution