C PROGRAMMING: Searching a linked list in C

Now, write code to search the linked list. your task is to write the search() function itself.

This will be a linear search over the linked list, and looks somewhat similar to printall() in how it goes through the list with "p = p->next".

Since the list is in sorted order by the key, stop searching once either the key is found, or the end of the list is reached, OR the key value in the list item is greater than the search key. This early termination does not affect the big-O running time of your search algorithm, but it arguably decreases the running time by about half on average. It also simplifies your code a bit.

Starter code provided below:

#include

struct item {

int key;

int data;

struct item *next;

};

struct item *head = NULL;

int main()

{

extern void filllist();

extern int search(int key); /* returns -1 if not found */

filllist();

printf("%d ", search(20));

printf("%d ", search(38));

printf("%d ", search(138));

printf("%d ", search(8));

printf("%d ", search(5));

/* expected output: 2, 3, -1, -1, 0 */

return(0);

}

void filllist()

{

static struct item a, b, c, d;

head = &a;

a.key = 5;

a.data = 0;

a.next = &b;

b.key = 20;

b.data = 2;

b.next = &c;

c.next = &d;

c.key = 22;

c.data = 6;

d.key = 38;

d.data = 3;

d.next = NULL;

}

/*PLEASE EDIT SEARCH*/

int search(int key) /* returns -1 if not found */

{

}