/* Goal: An implementation of doubly linked lists using pointers. * * List are implemented using two structures: a node and a list. * A node contains pointers to two other nodes, nextNode and previousNode * A list contains the length of the list and three pointers to nodes: startNode, endNode, and CursorNode * * Functions provided for list manipulation: * list *createList() * node *createNode(char *value, node *nextNode, node *previousNode) * int advanceCursor(int forward, list *dataList) * int regressCursor(int backward, list *dataList) * int deleteList(list *dataList) * int deleteCursorNode(list *dataList) * int addToStart(node *newNode, list *dataList) * int addToEnd(node *newNode, list *dataList) * int addAfterCursor(node *newNode, list *dataList) * int addBeforeCursor(node *newNode, list *dataList) * int clearList(list *dataList) * int *concatenateLists(list *dataList1, list *dataList2) * int compareNode(node *node1, node *node2) * int quicksort(list *dataList) * int readList(char *inputFileName, list *dataList) * int displayList(list *dataList) * int fdisplayList(FILE *outputFile, list *dataList) * Full descriptions of these functions are given below * * Author: Nathan Corvino * * Created 2/9/00 * First fully working version 2/22/99 * Code cleaned up and additional comments added 2/23/99 * */ /* Include libraries */ #include #include /* Define Constants */ #define MAXLINE 256 /* Define types */ typedef struct node_st node; struct node_st { char *data; /* The Node's data */ node *next; /* Pointer to the next node in the list */ node *previous; /* Pointer to the previous node in the list */ }; typedef struct list_st list; struct list_st { node *startNode; /* The first node in the list */ node *endNode; /* The last node in the list */ node *cursorNode; /* The current node being used */ int length; /* The number of nodes in the list */ }; /* pre-declarations of functions */ /************************************************************** * Purpose: instantiates a linked list * * Postconditions: memory is allocated for a list new list * * Problems: memory may not be able to be allocated * * Returns: a pointer to a list * **************************************************************/ list *createList(); /************************************************************** * Purpose: instantiates a node * * Postconditions: memory is allocated for a list new list * * Problems: memory may not be able to be allocated * * Returns: a pointer to a node if successful * * the null pointer if unsuccessful * **************************************************************/ node *createNode(char *value, node *nextNode, node *previousNode); /************************************************************************************************ * Purpose: moves a lists cursor forward a given number of nodes * * Parameters: int forward: the number of nodes to move forward * * list *dataList: the pointer to the list in which to move the cursor * * Preconditions: forward must be a positive integer; otherwise, cursor will not be moved * * Postconditions: the cursor is advanced the appropriate number of nodes * * if forward indicates the cursor should move past the last node in dataList, * * the cursor will point to the last node * * Returns: returns 0 after successful execution * ************************************************************************************************/ int advanceCursor(int forward, list *dataList); /************************************************************************************************* * Purpose: moves a lists cursor backward a given number of nodes * * Parameters: int backward: the number of nodes to move backword * * list *dataList: the pointer to the list in which to move the cursor * * Preconditions: backward must be a positive integer; otherwise, cursor will not be moved * * Postconditions: the cursor is regressed the appropriate number of nodes * * if backward indicates the cursor should move past the first node in dataList, * * the cursor will point to the starting node * * Returns: returns 0 after successful execution * *************************************************************************************************/ int regressCursor(int backward, list *dataList); /******************************************************************** * Purpose: too free the memory used by a list and all of its nodes * * Parameters: list *dataList: the list to be deleted * * returns: 0 after successful execution * ********************************************************************/ int deleteList(list *dataList); /******************************************************************************************************************* * Purpose: to remove the cursorNode from the current list and free the memory associated with this node * * Parameters: list *dataList: the list from which the cursor node should be removed * * Preconditions: the list is non-empty * * Postconditions: The cursorNode of *dataList i deleted and the memory associated with it is freed * * The cursor node is left pointing to the next element in the list, which is the same distance * * from the startNode that the original cursorNode was. The exception is when the cursorNode is * * at the end of the list, in which case the cursorNode still points to the end of the list. * * Returns: 0 if successful * * 1 if list was all ready empty * * -1 if anything else, unforseen, happens (should not) * *******************************************************************************************************************/ int deleteCursorNode(list *dataList); /**************************************************************** * Purose: to add a new node at the beginning of a list * * Parameters: node *newNode: node to be added * list *dataList: list to which to add node * * Preconditions: newNode and dataList are properly initialized * * Postconditions: newNode is added to beginning of dataList * * Returns: 0 for successful operation * ****************************************************************/ int addToStart(node *newNode, list *dataList); /**************************************************************** * Purose: to add a new node at the end of a list * * Parameters: node *newNode: node to be added * list *dataList: list to which to add node * * Preconditions: newNode and dataList are properly initialized * * Postconditions: newNode is added to end of dataList * * Returns: 0 for successful operation * ****************************************************************/ int addToEnd(node *newNode, list *dataList); /******************************************************************** * Purose: to add a new node after the cursor of a list * * Parameters: node *newNode: node to be added * list *dataList: list to which to add node * * Preconditions: newNode and dataList are properly initialized * * Postconditions: newNode is added after the cursor of dataList * * Returns: 0 for successful operation * ********************************************************************/ int addAfterCursor(node *newNode, list *dataList); /******************************************************************** * Purose: to add a new node before the cursor of a list * * Parameters: node *newNode: node to be added * list *dataList: list to which to add node * * Preconditions: newNode and dataList are properly initialized * * Postconditions: newNode is added before the cursor of dataList * * Returns: 0 for successful operation * ********************************************************************/ int addBeforeCursor(node *newNode, list *dataList); /***************************************************************************** * Purpose: to delete all the nodes in a list * * Parameters: list *dataList: the list to be cleared * * Postconditions: dataList is empty * * Returns: 0 for successful operation * * -1 if all nodes have been deleted and there list length is not 0 * * (should not happen * *****************************************************************************/ int clearList(list *dataList); /******************************************************************************** * Purpose: to combine two lists * * Parameters: list *dataList1: the list to appear at the start of the new list * * list *dataList2: the list to follow dataList1 * * Postconditions: *dataList1 points to dataList1 followed by dataList2 * * datatList2 is empty * * Returns: 0 after successful operation * ********************************************************************************/ int *concatenateLists(list *dataList1, list *dataList2); /****************************************************** * Purpose: to compare the data in two nodes * * Parameters: node *node1: a node to be compared * * node *node2: a node to be compared * * Preconditions: node1 and node2 are not NULL * * Postconditions: nothing changed * * Returns: <0 if node1's data < node2's data * * 0 if node1's data == node2's data * * >0 if node1's data > node2's data. * ******************************************************/ int compareNode(node *node1, node *node2); /*************************************************************************************************** * Purpose: To sort the list given based on string comparisons using the quicksort algorithm. * * Parameters: list *dataList: list to be sorted * * Preconditions: dataList is not NULL * * Postconditions: dataList is sorted * * Returns: 0 for successful operation * ***************************************************************************************************/ int quicksort(list *dataList); /************************************************************************************** * Purpose: to read a list from a file * * Parameters: char * inputFileName: the name of the file from which to read the list * * dataList: the list to be read * * Preconditions: dataList is not empty * * the file indicated exists and is in the proper formate to be read * * as a list * * Postconditions: dataList contains the list contained in the indicated file * * Problems: if input file is not in the proper format, problems may be encountered * * first line of file should be an integer with the number of nodes in * * the list being read * * each successive line of the file should contain a string representing * * the data on a node in the list. There should be at least as many * * such lines as the integer on the first line indicates * * Returns: 0 for successful operation * * -1 if dataList is non-empty * * -2 if inputFileName does not exist * **************************************************************************************/ int readList(char *inputFileName, list *dataList); /******************************************************** * Purpose: to display a list to the screen * * Parameters: list *dataList: the list to be displayed * * Returns: 0 for successful operation * ********************************************************/ int displayList(list *dataList); /*********************************************************** * Purpose: to write a list to a file * * Parameters: File *outputFile: the file to be written to * * list *dataList: the list to be written * * Returns: 0 for successful operation * ***********************************************************/ int fdisplayList(FILE *outputFile, list *dataList);