/* This is an implementation of doubly-linked lists. Written by: Jon Flaherty and Sarah Luebke Date: 18 February 2000 Methods provided: node * addAfterCurrent(node *current, char * newstr); (Returns a pointer to the element you pass in) node * addToEnd(node *first, char * new); (Add an element to the end of the list) int atEnd(node * anode); (Returns 1 if you are at the end of the list, 0 if not) node * deleteElt(node * first, char * str); (Delete an element) node * findElt(node *anode, char * str); (Find a string in the list and return it) char * getCurrent(node *anode); (Returns the data of that element, as a string) node * getFirst(node *anode); (Returns a pointer to the first element of the list) node * getLast(node *anode); (Returns a pointer to the last element of the list) node * getNext(node *anode); (Returns a pointer to the next element of the list) node * getPrev(node *anode); (Returns a pointer to the previous element of the list) node * getRandomElt(node *anode) (This takes a node and returns a random node in the list) int length(node *anode); (Returns the number of elements in the list) node * meld(node *firstlist, node *secondlist, node *thirdlist); (This takes 3 lists and puts them together into a single list) node * newList(char * new); (Returns a new list with a single element) */ #include "linkedlist.h" #include #include /* for rand */ #include /* for rand */ /* This function inserts an element in the list immediately after the current element. Returns: a pointer to the node you just added Parameters: current and the string */ node * addAfterCurrent(node *current, char * newstr) { /* Make a new node to add. */ struct node *newnode = (struct node *) malloc(sizeof(struct node)); /* the node that was after current */ node *nextnode = (*current).next; /* allocate space for string field of the new node */ char *newstring = (char *) malloc(1+strlen(newstr)); /* Copy the string we passed in to the place we just allocated space for */ strcpy(newstring, newstr); /* Set the value of the new node to be added. */ (*newnode).data = newstring; (*newnode).next = nextnode; (*newnode).prev = current; /* update the pointers of current and the node after the added node */ if (nextnode != NULL) { (*nextnode).prev = newnode; } (*current).next = newnode; return newnode; } /* addAfterCurrent (node *current, char *) */ /* This function adds the string to the end of the list. Returns: a pointer to the element you just added Parameters: a node and a string. */ node * addToEnd(node *first, char * thestring) { /* Make a new node with the value being "new". */ node *newnode = (struct node *) malloc(sizeof(struct node)); /* allocate memory for the string */ char *newstring = (char *) malloc(1+strlen(thestring)); /* Find the last element of the list.*/ node *last = getLast(first); /* Copy the string we pass in to the newly allocated */ strcpy(newstring, thestring); /* Set the fields of the newnode */ (*newnode).data = newstring; (*newnode).prev = last; (*newnode).next = NULL; (*last).next = newnode; return newnode; } /* add to end (node, char*) */ /* Check if we are at the tail end of the list. This returns 1 if we are at the end, 0 if we are not. Parameters: a pointer to the current node. */ int atEnd(node *anode) { if ((*anode).next == NULL) { return 1; } /* if */ else { return 0; } } /* atEnd(node) */ /* This function takes the first node of the list and a string and deletes the first occurance of that string from the list. It returns the first element of the list. Parameters: a list element and a string to delete */ node * deleteElt(node *first, char * str) { node *previousnode; node *nextnode; node *anode; anode = getFirst(first); /* Special case if the str is found in the first node. */ if (strcmp(str, (*anode).data) == 0) { /* the first element's next node (the new beginning of the list) */ nextnode = (*anode).next; /* set that elt to be the first elt */ (*nextnode).prev = NULL; return nextnode; } else { /* Find the node in question. */ while ((*anode).next != NULL) { /* We've found a match */ if (strcmp(str, (*anode).data) == 0) { /* The deleted node's previous node. */ previousnode = (*anode).prev; /* The deleted node's next node. */ nextnode = (*anode).next; /* Now set the previous node to point to the next node. */ (*previousnode).next = nextnode; /* deallocate the space of the deleted node */ free((*anode).data); free(anode); /* we're done deleting that node so get out of the while */ break; } /* if */ anode = (*anode).next; } /* while */ /* In case the str is the data of the last node */ if (strcmp(str, (*anode).data) == 0) { /* The deleted node's previous node. */ previousnode = (*anode).prev; /* The deleted node's next node. */ nextnode = (*anode).next; /* Now set the previous node to point to the next node. */ (*previousnode).next = nextnode; /* deallocate the space of the deleted node */ free(anode); } /* if */ } return first; } /* deleteElt (node, char*) */ /* This function searches the list for the string. Returns: the new node if it was found, the original node if it wasn't found Parameters: a node and a string */ node * findElt(node *anode, char * str) { /* We want to start with the first element of the list and traverse the list, looking for the string. */ node * found = getFirst(anode); /* Search for the element while the we're not at the last element of the list. */ while ((*found).next != NULL) { /* we've found a match */ if (strcmp(str, (*found).data) == 0) { return found; } found = (*found).next; } /* while */ if (strcmp(str, (*found).data) == 0) { return found; } /* otherwise return the original node*/ return anode; } /* Get the data of current. Returns: the string associated with that node Parameters: a node */ char * getCurrent(node *anode) { return (*anode).data; } /* getCurrent */ /* Return the first element. Parameters: a pointer to the current node */ node * getFirst(node *anode) { /* Create a node called current. */ node *current = anode; while ((*current).prev != NULL) { current = (*current).prev; } /*while*/ return current; } /* getFirst */ /* Return the last element. Parameters: a pointer to the current node */ node * getLast(node *anode) { /* Create a node called current. */ node *current = anode; while ((*current).next != NULL) { current = (*current).next; } /*while*/ return current; } /* getLast */ /* Get the next element. Returns: a pointer to the next element; right now if the next element is NULL I return the element you passed in. Parameters: a pointer to a node */ node * getNext(node *anode) { /* Check if the next list item exists. */ if ((*anode).next == NULL) { return anode; } else { return (*anode).next; } } /* getNext */ /* Return the previous element. Parameters: a pointer to a node */ node * getPrev(node *anode) { /* Check if the previous list item exists. */ if ((*anode).prev == NULL) { return anode; } else { return (*anode).prev; } } /* getPrev */ /* This takes a pointer to a node in the list and returns a random node in the list. Note: in order to use this, the client must set the seed, with a command like: "srand(time((time_t *) 0));" */ node * getRandomElt(node *anode) { int randomNumber; /* Since this function chooses a random position for a node, we don't want the random number larger than the length of the list. */ int maxRandInt = length(anode); int counter = 1; /* call rand to pick a random number */ randomNumber = rand(); /* take that number modulo the length of our list */ randomNumber = (randomNumber % maxRandInt); /* add 1 so it is 1 through n, not 0 through n-1 */ randomNumber++; /* traverse the list to get the element found at that position */ anode = getFirst(anode); while (((*anode).next != NULL) && (counter < randomNumber)) { /* printf("Random Number: %d, Counter: %d, anode: %s\n", randomNumber, counter, (*anode).data); */ counter++; anode = getNext(anode); } /* return the node */ return anode; } /* getRandomElt(node *anode) */ /* This returns the length of the list. Parameters: a pointer to the current node. */ int length(node *anode) { /* Find the length of the list */ int counter = 0; node *current = getFirst(anode); /* step through the list, incrementing the counter for each node */ while ((*current).next != NULL) { counter++; /* go to the next node in the list */ current = (*current).next; } /* increment counter because we haven't counted the last element, then return it */ return ++counter; } /* length */ /* This function takes three lists and puts them together into single list, in the order that they are received. Returns: the first node of the new list */ node * meldThree(node *firstlist, node *secondlist, node *thirdlist) { /* Find the last element of the first list*/ node * lastOfFirst = getLast(firstlist); /* Find the first element of the second list */ node * firstOfSecond = getFirst(secondlist); /* Find the last element of the second list */ node * lastOfSecond = getLast(secondlist); /* Find the first element of the third list */ node * firstOfThird = getFirst(thirdlist); /* Connect the last elt of first to the first elt of second */ (*lastOfFirst).next = firstOfSecond; (*firstOfSecond).prev = lastOfFirst; /* Connect the last elt of second to the first elt of third */ (*lastOfSecond).next = firstOfThird; (*firstOfThird).prev = lastOfSecond; /* Return a pointer to the first node of the entire list */ return getFirst(firstlist); } /* This function takes two lists and puts them together into single list, in the order that they are received. Returns: the first node of the new list */ node * meldTwo(node *firstlist, node *secondlist) { /* Find the last element of the first list*/ node * lastOfFirst = getLast(firstlist); /* Find the first element of the second list */ node * firstOfSecond = getFirst(secondlist); /* Connect the last elt of first to the first elt of second */ (*lastOfFirst).next = firstOfSecond; (*firstOfSecond).prev = lastOfFirst; /* Return a pointer to the first node of the entire list */ return getFirst(firstlist); } /* This function is the constructor. What it actually does is create one node with the next and previous nodes set to null. It returns that node. Returns: A pointer to the first node. Parameters: the string */ node * newList(char * newstr) { /* Create the new node. */ struct node *newnode = (struct node *) malloc(sizeof(struct node)); char *newstring = (char *) malloc(1+strlen(newstr)); /* Copy the string we passed in to the place we just allocated space for */ strcpy(newstring, newstr); /* Set the fields of this new node. */ (*newnode).next = NULL; (*newnode).prev = NULL; /* Copy the string we passed in to the data field of newnode. */ (*newnode).data = newstring; return newnode; } /* newList (char*) */