Ordered Linked List Project

Overview

You are to write the code for an ordered linked list module. You will be supplied with three files: main.c, orderedList.h, orderedList.c and Makefile. You are not to modify the file orderedList.h. In the file orderedList.c, you are to supply the code for the three functions whose prototypes are in orderedList.h. The file main.c is used to test your implementation of these functions. It is not necessarily a complete test, so you may modify it to check other possible places where your functions might fail.

Submission

The only file that will be submitted is orderedList.h.

Using the Makefile

Select Makefile from the file list and hit Compile/Validate. This will compile ordereList.c and main.c, producing an executable named main. If you double click main, the program will execute and should produce the output shown in the example below.

Contents of orderedList.h

typedef struct node {

int data;

struct node *next;

} Node;

Node *orderedInsert(Node *p, int newval);

/* Allocates a new Node with data value newval and inserts into the ordered list with first node pointer p in such a way that the data values in the modified list are in nondecreasing order as the list is traversed.

*/

void printList(Node *p);

/* Prints the data values in the list with first node pointer p from first to last, with a space between successive values.

Prints a newline at the end of the list.

*/

void clearList(Node **p);

/* Deletes all the nodes in the list with first node pointer *p, resulting in *p having value NULL. Note that we are passing

a pointer by address so we can modify that pointer.*/

Design of orderedInsert function

Here is a step by step description of what you should do to insert a integer newval into an ordered linked list with first node pointer p:

1. Declare a Node pointer variable q, dynamically allocate a Node as the target of q and set the data value of the new node to newval.

2. If the list is empty or newval is less than or equal to the data value in the first node of the list, make the target node of q the first node of the list and return q.

3. Use a Node pointer tmp to traverse the list until it either reaches the last node or reaches a Node whose following node has data value greater than or equal to newval.

4. Insert the target of q after the target of tmp and return p (the original first node pointer).

Example

Suppose the following code (from main.c) is executed :

Node * p = NULL;

p = orderedInsert(p,2);

printList(p);

p = orderedInsert(p,0);

printList(p);

p = orderedInsert(p,3);

printList(p);

p = orderedInsert(p,3);

printList(p);

p = orderedInsert(p,5);

printList(p);

clearList(&p);

p = orderedInsert(p,6);

printList(p)

Then the output would be:

2

0 2

0 2 3

0 2 3 3

0 2