/* Linklist.c */ /* Chris Kern * * This is the low-level linked list file, which deals with nodes. */ #include #include #include #include "linklist.h" /* Creates a new linked list given a string, which is used for the contents of * the first node. Returns a pointer to the new node created, * which is the first element of the new list. Returns NULL if the memory * was not allocated correctly. */ struct node *new_list(char *contents) { /* Create the new list. */ struct node *new; /* Allocate memory. */ new = malloc(sizeof(struct node)); new->item = malloc(1 + strlen(contents)); /* Make sure the memory was allocated correctly. */ if (!new || !new->item) return NULL; /* Put the contents into the node. */ strncpy(new->item, contents, 1 + strlen(contents)); /* Both the next and previous pointers should point to NULL. */ new->next = NULL; new->previous = NULL; /* Return the pointer to the new list. */ return new; } /* new_list */ /* Create a new node at the end of a list. It takes a string as a * parameter, which becomes the contents for the first node of the new list, * and it also takes a pointer to the first element of the list. * Returns a pointer to the new node, or NULL if the memory was not * allocated correctly. */ struct node *add_to_end(char *contents, struct node *first) { /* Create the new node. */ struct node *new; /* Create a temporary node. */ struct node *temp = first; /* Allocate memory for the node and the "item" field. */ new = malloc(sizeof(struct node)); new->item = malloc(1 + strlen(contents)); /* Return NULL if the memory allocation failed. */ if (!new || !new->item) return NULL; /* Put the contents into the node. */ strncpy(new->item, contents, 1 + strlen(contents)); /* Since this is the last node, the "next" field should point to NULL. */ new->next = NULL; /* Step through the list until the final element is reached. */ while (temp->next) temp = temp->next; /* Fix the pointers. */ temp->next = new; new->previous = temp; /* Return the pointer to the new node. */ return new; } /* addToEnd */ /* Find a node in a list given the first element and the string to search for. * Returns the pointer to the node, or NULL if the item is not in the list. */ struct node *find_node(char *thing, struct node *first) { /* Make a temporary pointer as a cursor. */ struct node *cursor; cursor = first; /* We want to advance through the list until one of two things happens: * 1. The item is found, i.e. (strcmp(cursor->item, thing)) returns NULL. * 2. The end of the list is reached, i.e. (cursor) returns NULL. */ while ((cursor) && (strcmp(cursor->item, thing))) { cursor = cursor->next; } /* while */ /* In either case we can return the cursor. If the end of the list was reached, * the cursor will point to NULL, which is our failure condition described above. */ return cursor; }/* find_node */ /* Delete an element from the list. Frees the memory used by that element, and * returns 1 if the delete was succesful and 0 if it was not. */ int delete_node(char *toBeDeleted, struct node *first) { /* Find the element given. */ struct node *node= find_node(toBeDeleted, first); /* If the element was not found, return 0. */ if (!node) return 0; /* Case 1 -- we are deleting the only element of the list. */ if (!node->next && !node->previous) { free(node->item); free(node); } /* Case 2 -- we are deleting the last element in the list. */ else if (!node->next) { node->previous->next = NULL; free(node->item); free(node); } /* Case 3 -- we are deleting the first element in the list. */ else if (!node->previous) { node->next->previous = NULL; free(node->item); free(node); } /* Case 4 -- the element to be deleted is in the middle. */ else { node->previous->next = node->next; node->next->previous = node->previous; free(node->item); free(node); } return 1; }/* int delete_node */ /* The following procedure starts from the first element of a linked list and prints all * of the elements. The function returns the number of elements printed. */ int write_list(struct node *first) { /* Set up a temporary pointer and a counter. */ struct node *temp = first; int number = 0; /* If there is no list, don't print anything */ if (!first) return 0; /* Print the first element of the list. */ printf("%s\n", temp->item); number = 1; /* Step through the remaining elements until the end of the list is reached. */ while (temp->next) { /* We advance the temporary pointer first because we've already printed the first list element. */ temp = temp->next; printf("%s\n", temp->item); number++; } /* while (temp->next) */ /* Return the number of elements printed. */ return number; }/* int write_list */ /* Save the linked list to a file. */ int f_write_list(char *filename, struct node *first) { /* Set up a temporary pointer and counter. */ struct node *temp = first; int number = 0; /* Open a file for writing. */ FILE *fp; fp = fopen(filename, "w"); /* Mark the file as a linked list file. Theoretically the loading segment would * check to make sure the file was a valid link list file. This is not implemented. */ fprintf(fp, "%s\n", "LINKED LIST"); /* If there is no list, don't write anything */ if (!first) return 0; /* Print the first element of the list. */ fprintf(fp, "%s\n", temp->item); number = 1; /* Step through the remaining elements until the end of the list is reached. */ while (temp->next) { /* We advance the temporary pointer first because we've already printed the first list element. */ temp = temp->next; fprintf(fp, "%s\n", temp->item); number++; } /* while (temp->next) */ /* Close the file. */ fclose(fp); /* Return the number of elements printed. */ return number; } /* f_write_list */ /* Read a linked list from a file. Returns 0 if the file does not exist or is not a linked list file. * Otherwise a pointer to the first element of the list is returned. */ struct node *f_read_list(char *filename) { /* Declare a file and a buffer */ FILE *fp; char test[200], *p; /* Make 2 temporary cursors. */ struct node *cursor; struct node *cursor2; /* Attempt memory allocation. */ struct node *first = malloc(sizeof(struct node)); if (!first) return 0; /* Allocate memory for string*/ if (!(first->item = malloc(200))) return 0; /* Open the file */ fp = fopen(filename, "r"); /* Read the first line. */ fgets(test, sizeof(test), fp); /* The following converts the newline into a terminating character. */ if ((p = strchr(test, '\n'))) *p = '\0'; /* Read the first item. */ bzero(test, sizeof(test)); fgets(test, sizeof(test), fp); if ((p = strchr(test, '\n'))) *p = '\0'; strcpy(first->item, test); /* Set the pointers. */ first->previous = NULL; first->next = malloc(sizeof(struct node)); /* Get the cursors ready. */ cursor = first->next; cursor->previous = first; cursor2 = first; bzero(test, sizeof(test)); /* Go until the end of the file is reached. */ while(fgets(test, sizeof(test), fp)) { /* Convert newline into \0 */ if ((p = strchr(test, '\n'))) *p = '\0'; /* Copy the string. */ if (!(cursor->item = malloc(1 + strlen(test)))) return 0; strcpy(cursor->item, test); /* Attempt memory allocation for the next node. */ if (!(cursor->next = malloc(sizeof(struct node)))); /* Set the previous link. */ cursor->previous = cursor2; /* Move the cursors. */ cursor = cursor->next; cursor2 = cursor2->next; bzero(test, sizeof(test)); } /* while */ /* Set the final link to null. */ cursor2->next = NULL; /* Return the first element of the list. */ return first; } /* f_read_list */