PROGRAM MUST BE IN C PROGRAMMING AND PLEASE COMPLETE ALL AS WELL AS SEND SCREENSHOT OF OUTPUT FOR THE THUMBS UP! SRC files are given below! 

Examine the files list.h and llist.c in the src directory where you found this handout.

You will discover that it is a partially implemented linked list module.

The lists store numeric values (the type of which can be changed by altering the typedef for ElemType in list.h).

As in previous projects, the .h file gives the interface for an ADT while the actual implementation is given in the .c file. The members of list_struct are also hidden in the .c file. The ADT defines many natural operations on lists -- some of these have already been implemented and will be used as motivating examples during lecture; others have not been implemented: It is your job to do the implementation! Look for TODO labels throughout the files.

A subtle detail: why did I decide to name the header file list.h (one l), but the implementation file llist.c (two ls)???

So part I is completion of all of the TODO items specified.

Rules: you cannot change list.h (except maybe to experiment with different ElemTypes). All of your work is in llist.c (except testing code).

list.h

// 

/** TODO (part of previous lab, but no solution provided!) * function: lst_is_sorted * * description: returns 1 if the list is sorted in * non-decreasing order; 0 otherwise * * DIFFICULTY LEVEL: 1 */ extern int lst_is_sorted(LIST *l); /** TODO * function: lst_insert_sorted * * description: assumes given list is already in sorted order * and inserts x into the appropriate position * retaining sorted-ness. * Note 1: duplicates are allowed. * * Note 2: if given list not sorted, behavior is undefined/implementation * dependent. We blame the caller. * So... you don't need to check ahead of time if it is sorted. * * DIFFICULTY LEVEL: 2.5 */ extern void lst_insert_sorted(LIST *l, ElemType x); 

 ll_tst.c #include #include "list.h" // very incomplete small demo/test program... // You may use this as a template/framework for developing tests int main() { LIST *lst1; int i; lst1 = lst_create(); for(i=0; i<5; i++) { lst_push_front(lst1, i); } for(i=0; i<5; i++) { lst_push_back(lst1, i); } printf("lst_len(lst1) : %i ", lst_len(lst1)); printf("lst1 contents: "); lst_print(lst1); lst_pop_front(lst1); lst_pop_front(lst1); printf("lst1 contents after two pops: "); lst_print(lst1); // an example of a "real" test int a[5] = {3, 4, 5, 6, 2}; int b[5] = {3, 4, 5, 6, 8}; LIST *lstA = lst_from_array(a, 5); LIST *lstB = lst_from_array(b, 5); if(lst_is_sorted(lstA) ) printf("is_sorted TEST 1 FAILED! "); else printf("is_sorted TEST 1 PASSED! "); if(lst_is_sorted(lstB) ) printf("is_sorted TEST 2 PASSED! "); else printf("is_sorted TEST 2 FAILED! "); /** test code for lst_count **/ // TESTS THAT REQUIRE VISUAL INSPECTION printf("number of 3's = %i ", lst_count(lst1, 3)); printf("number of 0's = %i ", lst_count(lst1, 0)); /** test code for lst_print_rev **/ /** test code for lst_push_back **/ lst_free(lst1); lst_free(lstA); lst_free(lstB); } 

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

llist.c

#include #include #include "list.h" /************* structs and typedefs *************/ typedef struct node { ElemType val; struct node *next; } NODE; struct list_struct { NODE *front; NODE *back; 

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------MakeFile

llist.o: list.h llist.c

gcc -c llist.c

ll_tst: ll_tst.c llist.o

gcc -o ll_tst ll_tst.c llist.o

quad: quad.c

gcc -o quad quad.c

clean:

rm quad ll_tst llist.o