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

// /** ElemType may be changed for application * specific needs. * * However, it should be a numeric type. */ typedef int ElemType; #define FORMAT " %i " #define DEFAULT 0 // hidden implementation of list_struct typedef struct list_struct LIST; /** * function: lst_create() * desc: allocates and initializes an empty list and returns it. */ extern LIST *lst_create(); /** * function: lst_from_array * desc: creates a new list populated with the elements of * the given array, in the same order as given. * * [the front of the list is a[0] and so on] */ extern LIST *lst_from_array(ElemType a[], int n); /** * TODO * function: lst_to_array * desc: Dynamically allocates an array of appropriate * length and populates it with the elements of * the given list (in the same order). * * Array is returned as a pointer to ElemType * The length of the array (equal to the list length) * is stored in *out_n * * Sample invocation code: LIST *lst; ElemType *a; int n; lst = lst_create(); // bunch of operations on lst a = lst_to_array(lst, &n); * * DIFFICULTY LEVEL: 2 * */ extern ElemType * lst_to_array(LIST *l, int *out_n); /** * TODO * function: lst_clone * desc: creates a clone of the given list and returns it. * * This is a "deep copy": the clone and original are completely * independent of each other; they just happen to have the same * contents (in the same sequence). * * DIFFICULTY LEVEL: 2 * */ extern LIST *lst_clone(LIST *l); /** 

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

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