Part 1: Implement a singly linked list --------------------------------------

(a)

Your job is to implement a generic singly linked list that can hold any data type. The interface has been specified and provided to you in a header file called mylist.h. So your job is to write mylist.c that implements each function whose prototype is included in mylist.h. Specifically, you are asked to write the following functions:

struct Node *addFront(struct List *list, void *data)

void traverseList(struct List *list, void (*f)(void *))

void flipSignDouble(void *data)

int compareDouble(const void *data1, const void *data2)

struct Node *findNode(struct List *list, const void *dataSought, int (*compar)(const void *, const void *))

void *popFront(struct List *list)

void removeAllNodes(struct List *list)

struct Node *addAfter(struct List *list, struct Node *prevNode, void *data)

void reverseList(struct List *list)

The header file contains detailed comments specifying the behavior of the functions. Your implementation should follow the specified behavior.

In addition, I provide you with a test driver program, mylist-test.c, which produces the following output for a correctly implemented linked list:

testing addFront(): 9.0 8.0 7.0 6.0 5.0 4.0 3.0 2.0 1.0 testing flipSignDouble(): -9.0 -8.0 -7.0 -6.0 -5.0 -4.0 -3.0 -2.0 -1.0 testing flipSignDouble() again: 9.0 8.0 7.0 6.0 5.0 4.0 3.0 2.0 1.0 testing findNode(): OK popped 9.0, the rest is: [ 8.0 7.0 6.0 5.0 4.0 3.0 2.0 1.0 ] popped 8.0, the rest is: [ 7.0 6.0 5.0 4.0 3.0 2.0 1.0 ] popped 7.0, the rest is: [ 6.0 5.0 4.0 3.0 2.0 1.0 ] popped 6.0, the rest is: [ 5.0 4.0 3.0 2.0 1.0 ] popped 5.0, the rest is: [ 4.0 3.0 2.0 1.0 ] popped 4.0, the rest is: [ 3.0 2.0 1.0 ] popped 3.0, the rest is: [ 2.0 1.0 ] popped 2.0, the rest is: [ 1.0 ] popped 1.0, the rest is: [ ] testing addAfter(): 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 popped 1.0, and reversed the rest: [ 9.0 8.0 7.0 6.0 5.0 4.0 3.0 2.0 ] popped 9.0, and reversed the rest: [ 2.0 3.0 4.0 5.0 6.0 7.0 8.0 ] popped 2.0, and reversed the rest: [ 8.0 7.0 6.0 5.0 4.0 3.0 ] popped 8.0, and reversed the rest: [ 3.0 4.0 5.0 6.0 7.0 ] popped 3.0, and reversed the rest: [ 7.0 6.0 5.0 4.0 ] popped 7.0, and reversed the rest: [ 4.0 5.0 6.0 ] popped 4.0, and reversed the rest: [ 6.0 5.0 ] popped 6.0, and reversed the rest: [ 5.0 ] popped 5.0, and reversed the rest: [ ]

This model output is also provided to you in mylist-test-output.txt.

I recommend you implement the functions in the order listed, and test each function as you go. You can start by commenting out the code in main() of mylist-test.c and uncomment the code one block at a time to test each list function you implemented, comparing your output with that of mylist-test-output.txt. The 'diff' UNIX command may come in handy.

Note that mylist-test.c may not test every single function. You are still responsible for correct implementations of all functions.

Don't forget to run valgrind at each step to make sure you don't have a memory bug, and don't forget to include the valgrind output in your README.txt when you're done.

(b)

Modify your Makefile to produce a static library named 'libmylist.a' that contains your linked list object files. Your test program, mylist-test, must link with the library file, not the mylist.o file.

You can learn how to make a library file here:

http://randu.org/tutorials/c/libraries.php

Note that we are making a static library, not a shared library.

mylist-test.c

#include #include #include #include "mylist.h"

static void printDouble(void *p) { printf("%.1f ", *(double *)p); }

static void die(const char *message) { perror(message); exit(1); }

int main() { double a[] = { 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0 }; int n = sizeof(a) / sizeof(a[0]);

int i; double x; void *data; struct Node *node;

// initialize list struct List list; initList(&list);

// test addFront() printf("testing addFront(): "); for (i = 0; i < n; i++) { if (addFront(&list, a+i) == NULL) die("addFront() failed"); } traverseList(&list, &printDouble); printf(" ");

// test flipSignDouble() printf("testing flipSignDouble(): "); traverseList(&list, &flipSignDouble); traverseList(&list, &printDouble); printf(" "); printf("testing flipSignDouble() again: "); traverseList(&list, &flipSignDouble); traverseList(&list, &printDouble); printf(" "); // test findNode() printf("testing findNode(): "); x = 3.5; node = findNode(&list, &x, &compareDouble); assert(node == NULL); x = 1.0; node = findNode(&list, &x, &compareDouble); assert(node != NULL && *(double *)node->data == x); printf("OK ");

// test popFront() while ((data = popFront(&list)) != NULL) { printf("popped %.1f, the rest is: [ ", *(double *)data); traverseList(&list, &printDouble); printf("] "); }

// test addAfter() printf("testing addAfter(): "); node = NULL; for (i = 0; i < n; i++) { // We keep adding after the previously added node, // so we are in effect 'appending' to the list. node = addAfter(&list, node, a+i); if (node == NULL) die("addAfter() failed"); } traverseList(&list, &printDouble); printf(" ");

// test reverseList() while ((data = popFront(&list)) != NULL) { printf("popped %.1f, and reversed the rest: [ ", *(double *)data); reverseList(&list); traverseList(&list, &printDouble); printf("] "); }

return 0; }

mylist.c

#include #include #include "mylist.h"

// adds node to front of list struct Node *addFront(struct List *list, void *data) { //creates new node struct Node *front = (struct Node *)malloc(sizeof(struct Node)); if (front == NULL) { perror("malloc returned NULL"); exit(1); } //adds to front front->data = data; front->next = list->head; list->head = front; return front; }

//calls f() on each element of the list void traverseList(struct List *list, void (*f)(void *)) { struct Node *linkedList = list->head; //traverses until list is null while (linkedList) { f(linkedList->data); linkedList = linkedList->next; } }

//takes given data point and makes it negative void flipSignDouble(void *data) { double *nodeData = (double *) data; *nodeData = *nodeData * -1;

}

// if given data are equal, returns 0 and 1 otherwise int compareDouble(const void *data1, const void *data2) { double *double1 = (double *) data1; double *double2 = (double *) data2; int result; if (*double1 == *double2) { result = 0; } else { result = 1; } return result; }

// uses compar function to find given data in list struct Node *findNode(struct List *list, const void *dataSought, int (*compar)(const void *, const void *)) { struct Node *linkedList = list->head; struct Node *nodeFound = NULL;

while (linkedList) { // sets nodeFound = 0 if data are equal if(compar(dataSought, linkedList->data) == 0) { nodeFound = linkedList; } linkedList = linkedList->next; } return nodeFound; }

// removes first node in list and returns pointer to data void *popFront(struct List *list) { if (isEmptyList(list)) { return NULL; } struct Node *firstnode = list->head; void *returndata = firstnode->data; //removes front node list->head = firstnode->next; free(firstnode); return returndata; }

// removes all nodes void removeAllNodes(struct List *list) { // only checks if list is not empty while(!isEmptyList(list)) { popFront(list); } }

//adds new node with data after given node struct Node *addAfter(struct List *list, struct Node *prevNode, void *data) { if (prevNode == NULL) { return addFront(list, data); } else { // creates new node to add to list struct Node *newNode = (struct Node *)malloc(sizeof(struct Node)); if (newNode == NULL) { perror("malloc returned null"); exit(1); } newNode->data = data; newNode->next = prevNode->next; prevNode->next = newNode; return newNode; } }

// reverses the list void reverseList(struct List *list) { struct Node *prev = NULL; struct Node *curr = list->head; struct Node *next;

// reverses list while (curr) { next = curr->next; curr->next = prev; prev = curr; curr = next; } // sets head to back of list list->head = prev; }

mylist.h

#ifndef _MYLIST_H_ #define _MYLIST_H_

/* * A node in a linked list. */ struct Node { void *data; struct Node *next; };

/* * A linked list. * 'head' points to the first node in the list. */ struct List { struct Node *head; };

/* * Initialize an empty list. */ static inline void initList(struct List *list) { list->head = 0; }

struct Node *addFront(struct List *list, void *data);

/* * Traverse the list, calling f() with each data item. */ void traverseList(struct List *list, void (*f)(void *));

struct Node *findNode(struct List *list, const void *dataSought, int (*compar)(const void *, const void *));

/* * Flip the sign of the double value pointed to by 'data' by * multiplying -1 to it and putting the result back into the memory * location. */ void flipSignDouble(void *data);

/* * Compare two double values pointed to by the two pointers. * Return 0 if they are the same value, 1 otherwise. */ int compareDouble(const void *data1, const void *data2);

/* * Returns 1 if the list is empty, 0 otherwise. */ static inline int isEmptyList(struct List *list) { return (list->head == 0); }

void *popFront(struct List *list);

/* * Remove all nodes from the list, deallocating the memory for the * nodes. You can implement this function using popFront(). */ void removeAllNodes(struct List *list);

struct Node *addAfter(struct List *list, struct Node *prevNode, void *data);

void reverseList(struct List *list);

#endif /* #ifndef _MYLIST_H_ */

Part 2: Using the linked list library for strings -------------------------------------------------

In this part, you will use the linked list library that you implemented in part1 to write a program called 'revecho' that simply prints out the command line arguments in reverse order. In addition, it will look for the word "dude" (case-sensitive) among the command line arguments you passed, and report whether it's there or not.

For example,

./revecho hello world dude dude world hello

dude found

Another example:

./revecho hello world friend friend world hello

dude not found

Here are the program requirements and hints:

- Your program should simply put all the argument strings into a list WITHOUT duplicating them. There should be no malloc in your code. Just call addFront() for all strings.

- To print out the strings, you can either use traverseList() or you can traverse the list by yourself by following the next pointers, printing out each string. - Don't forget to initialize the list and remove all nodes at the end to prevent memory errors or leaks. Make sure you include valgrind output in your README.txt.

- To find 'dude', you can either traverse the list yourself, or use findNode(). Either way, strcmp() function will come in handy. If you want to pass strcmp to findNode(), you will have to cast it to the correct function pointer type because the signature of strcmp() is slightly different from the signature of 'compar' argument of findNode(). K&R2 section 5.11 has an example of casting a function pointer.