/* * Program that implements the functions defined in the LinkedList library. * * Jared Baszler, Joe Pipkins */ /* Include Libraries */ #include #include #include /* * Define the max number of characters that can be read in one line. * This is for reading characters from files. Will be implemented in * readFromFile. */ #define Max 70 /* Structure Definitions */ struct Node { char *contents; struct Node *left; struct Node *right; }; /* Node */ /* A pointer to the node. */ typedef struct Node *NODE; /* Global Variables. */ struct Node *first; /* Pointer to the first element. */ struct Node *last; /* Pointer to the last element. */ /* Program Prototype */ NODE newList(char *element); NODE addToFront(NODE current, char *element); NODE addToEnd(NODE current, char *element); void print(NODE current); NODE delete(NODE current); NODE getFirst(NODE current); NODE getLast(NODE current); NODE readFromFile(char *fileName); NODE writeToFile(char *target, NODE dlList); /* If we happen to get to it. */ NODE sort(NODE current); /* * This is a function that creates a new list with the first * node being the element passed in. */ NODE newList(char *element) { /* Allocate memory for the new node and make the new node. */ struct Node *new = (struct Node *) malloc(sizeof(struct Node)); char *newelement = (char *) malloc(1+strlen(element)); /* Initialize the left and right elements to null. */ new->left=NULL; new->right=NULL; new->contents=newelement; /* Return the node that we created. */ return new; } /* newList */ /* This function adds a new element to the front of the list. */ NODE addToFront(NODE current, char *element) { /* Allocate memory for the new first node. */ struct Node *firstnode = (struct Node *) malloc(sizeof(struct Node)); char *newfirst = (char *) malloc(1+strlen(element)); /* Get to the first element in the list using getFirst. */ getFirst(current); /* Initialize the new node and point it to the first node. */ firstnode->left=NULL; firstnode->contents=newfirst; firstnode->right=first; /* Changing the pointer to firstnode to make it a double link. */ first->left=firstnode; /* Return the node that we created. */ return firstnode; } /* addToFront */ /* This function adds a new element to the end of the list. */ NODE addToEnd(NODE current, char *element) { /* Allocate memory for the new last node. */ struct Node *lastnode = (struct Node *) malloc(sizeof(struct Node)); char *newlast = (char *) malloc(1+strlen(element)); /* Get to the last element in the list using getLast. */ getLast(current); /* Initialize the new node and point it to the last node. */ lastnode->right=NULL; lastnode->contents=newlast; lastnode->left=last; /* Changing the pointer to lastnode to make it a doulbe link. */ last->right=lastnode; /* Return the node we just created. */ return lastnode; } /* addToEnd */ /* This function returns the first node of the list. */ NODE getFirst(NODE current) { /* Create another pointer to the current node. */ NODE currentNode = current; /* * Recurse on the list until the left node is null. Then we * know that currentNode is at the beginning of the list. */ while(currentNode->left != NULL) { current->left = currentNode; } /* while */ return currentNode; } /* getFirst */ /* This function returns the last node of the list. */ NODE getLast(NODE current) { /* Create another pointer to the current node. */ NODE currentNode = current; /* * Recurse on the list until the left node is null. Then we * know that the currentNode is at the beginning of the list. */ while(currentNode->right != NULL) { current->right = currentNode; } /* while */ return currentNode; } /* getLast */ /* This function prints our current list. */ void print(NODE current) { /* Get the first element of the list and print it. */ current = getFirst(current); printf("( "); printf("%s", current->contents); /* Recurse on the rest of the list and print the elements. */ while(current->right != NULL) { current->right = current; printf(" "); printf("%s", current->contents); } /* while */ /* Print the close paren. */ printf(" )\n"); } /* print */ /* * This function deletes the current element that the pointer is * pointing to. * * Pre: List must be a non-empty list. * Post: Once element is deleted successfully, the current element * will be at the front of the list. */ NODE delete(NODE current) { /* * Change the pointer of the left node to the right of the current. * Hence skipping the node the current element is in. * * |---------------------------------->>>>| * | current->left=current->right; | * | | * *-----------* *----------* *-----------* * | left | | current | | right | * | | | | | | * *-----------* *----------* *-----------* * | | * | current->right=current->left; | * |<<<<----------------------------------| */ current->left=current->right; current->right=current->left; /* * Here, we are deleting the node "current" is in from memory. * We were given a clue about the free command here from our good * bud, Chris Kern. Thanks man. */ free(current); free(current->contents); /* * Move the pointer to the first element in the list to satisfy * the post-condition and return it. */ getFirst(current); return current; } /* delete */ /* * This function reads strings from a file and prints it * screen. */ NODE readFromFile(char *fileName) { /* Create a pointer to the file. */ FILE *fileptr; /* Create a pointer to a linked list. */ NODE dlList; /* * Create a buffer for the elements being read. Got this idea * from the client.c we used for Homework 1. */ char buffer[Max]; /* Check to see if the file passed in exists. */ if((fileptr = fopen(fileName, "r")) == NULL) { printf("The file doesn't exist. Try again please.\n"); } /* if */ /* Check to see if the file is empty. If so, tell user. */ else if((fgets(buffer, Max, fileptr)) == NULL) { printf("The file is empty. Sorry.\n"); } /* if */ /* Make the original list with the first line of the file. */ else if((fgets(buffer, Max, fileptr)) != NULL) { dlList = newList(buffer); } /* if */ /* Now make the rest of the list with the remainder of the file. */ else if((fgets(buffer, Max, fileptr)) != NULL) { dlList = addToEnd(dlList, buffer); } /* else if */ /* If the file contains no data, then state so. */ else { printf("File contains no usable data.\n"); } /* else */ return dlList; } /* readFromFile */ /* This function writes from the file we just read from. * THIS FUNCTION IS NOT FULLY IMPLEMENTED. DO NOT NO HOW * TO STEP THROUGH THE LIST AND THEN WRITE IT. */ NODE writeToFile(char *target, NODE dlList) { /* Set up a file pointer. */ FILE *fileptr; if((fileptr = fopen(target, "w")) == NULL) { printf("The file does not exsist.\n"); } /* if */ else { dlList = getFirst(dlList); if(fputs(dlList->contents, fileptr) == NULL) { printf("The file is empty.\n"); } return dlList; } /* else */ return dlList; } /* writeFromFile */