Implementing Linked List Utility Functions.

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

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).

Discussion: The given linked list structure has two levels:

At the lowest level are the linked-list nodes themselves specified as:

typedef struct node {

ElemType val;

struct node *next;

} NODE;

However, the type NODE isnt even visible to a client program. Only the type LIST is

visible to a client (just the type -- not the struct members). Through the header file, LIST is equivalent to a struct list_struct which is specified as follows:

struct list_struct {

NODE *front;

NODE *back;

};

Here is a diagram of a list with three entries: . The struct at the left (a LIST) gives access to the actual nodes.

The table on the next pages enumerates the functions to be implemented (identified with TODO in both list.h and llist.c) . Table includes a brief description and approximate difficulty level on a scale 1-3. See llist.h for detailed specifications.

FUNCTION NAME	SHORT DESCRIPTION
lst_to_array	Returns a dynamically allocated array populated with the elements of a given list
lst_clone	Builds and returns a clone of a given list (a deep copy)
lst_increment_vals	Increments all of the elements in a given list
lst_are_equal	Determines if two given lists are equal (same length and same values in same sequence)
lst_pop_back	Removes last element in list; returns value removed
lst_reverse	Reverses the order of a given list. Actually changes the list -- doesnt just print it in reverse order.
lst_sra_bad_case	Builds a list which makes the lst_remove_all_slow function run in quadratic time. (See .h file for details) This function has already been written and will be used for demo/discussion in class.
lst_remove_all_fast	Removes all occurrence of given value from given list. Does operation in one pass and takes linear time.	Concept not hard, but attention to detail will pay off!

FUNCTION NAME	SHORT DESCRIPTION
lst_is_sorted	Determines if a given list is in sorted order from smallest to largest.
lst_insert_sorted	Inserts a new element into a list assumed to be sorted. Resulting list sorted (i.e., new element inserted where it belongs)
lst_merge_sorted	Takes two lists assumed to be sorted and merges them into a single sorted list. After call, the first list (argument) is the merged list and the 2nd list (arg) becomes empty. Given lists are assumed to be sorted (this property does not need to be separately checked). No new nodes are allocated (existing nodes are relinked).

How To Get Started

You have been given a Makefile and a skeleton driver/tester program (ll_tst.c). Use them (and feel free to develop separate driver/tester programs) to help perform testing during development.

Overall, you know the drill for this kind of assignment:

Pick a function (start with easier ones)

Implement that function

Write test code for function in ll_tst.c or another driver program

Debug function

Re-test function

Repeat 4, 5 until satisfied

Think of test cases you may have missed

New test cases: Goto 3

No new tests/satisfied: Goto 1

ALL SOURCE CODE IS BELOW HERE SEPERATED BY DASHED LINES!

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

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); /** * function: lst_free * desc: deallocates all dynamically memory associated with the list */ extern void lst_free(LIST *l); /* * function: lst_print * desc: self explanatory */ extern void lst_print(LIST *l); /** DONE as part of previous lab * function: lst_print_rev * * description: prints the elements of the list * but in reverse order. */ extern void lst_print_rev(LIST *l); /** * TODO * func: lst_increment_vals * desc: increments all of the elements of the given list. * * Example: * * before call:  * after call:  * * DIFFICULTY LEVEL: 1 */ extern void lst_increment_vals(LIST *l); /** * TODO * func: lst_are_equal * desc: returns 1 if the two given lists are equal: * * they are the same length and * contain the same sequence of values * * returns 0 otherwise * * DIFFICULTY LEVEL: 1 */ extern int lst_are_equal(LIST *lst1, LIST *lst2); /* * function: lst_push_front * desc: self explanatory */ extern void lst_push_front(LIST *l, ElemType val); /* * function: lst_push_back * desc: self explanatory */ extern void lst_push_back(LIST *l, ElemType val); /* * function: lst_len * desc: returns length of list */ extern int lst_len(LIST *l); /* * function: lst_is_empty * desc: returns 1 if list is empty; 0 otherwise */ extern int lst_is_empty(LIST *l); /** [done as part of previous lab] * function: lst_count * description: Counts number of occurrences * of x in the list and returns * that value. */ extern int lst_count(LIST *l, ElemType x); // sanity checker functions - DONE extern int lst_sanity1(LIST *l); extern int lst_sanity2(LIST *l); extern int lst_sanity3(LIST *l); /* * function: lst_pop_front * desc: removes front element from list and returns * its value. * If list is empty, DEFAULT is returned (however, * this value has no real meaning -- caller should * not in general call lst_pop_front on an empty list). */ extern ElemType lst_pop_front(LIST *l); /** TODO (part of previous lab, but no solution provided!) * function: lst_pop_back * * description: removes last element from list * and returns that value. * * Note: if list is empty, the return value is * implementation specific -- i.e., caller's * fault. * * DIFFICULTY LEVEL: 3 */ extern ElemType lst_pop_back(LIST *l); /** TODO * function: lst_reverse * * description: reverses the given list. * this is different from printing it * in reverse order! * * The ordering of the actual list is * reversed. * * constraint: for full credit, NO MEMORY * ALLOCATION is allowed in this function; * it just re-links the already existing * nodes * * DIFFICULTY LEVEL: 3 */ extern void lst_reverse(LIST *l); /** DONE * function: lst_remove_first * * Description: The FIRST OCCURRENCE of x * in list (if any) is removed. * If x not in list, list is unchanged. * * NOT THE SAME AS lst_pop_front * * returns 1 if removal made; 0 otherwise */ extern ElemType lst_remove_first(LIST *l, ElemType x) ; /** DONE * function: lst_remove_all_slow * * description: removes all occurrences of x * from list and returns number of matches. * * implementation: simply repeatedly calls * lst_remogve_first on x until it fails. * * why is it slow? * * The number of operations this function performs * may depends on: * n: the length of the list * m: the number of matches of x * maybe the structure of the list * (e.g., where in the list the * matches occur). * * It seems like we should be able to perform * the operation in time proportional to n. * * However, I claim that there are cases for which * the approach of lst_remove_all_slow takes time * proportional to n^2 */ extern ElemType lst_remove_all_slow(LIST *l, ElemType x) ; /** TODO * function: lst_sra_bad_case (sra: slow_remove_all) * * description: this is not your typical function! To write this * function, you first need to determine what kind of * list structure will make the lst_remove_all_slow function * be "slow". * What do we mean by slow? * * Suppose the list has N elements (for some N). * * "Slow" for us means "proportional to N^2" * * * To get started thinking about this, imagine a list of * N elements all of which are zero. Now suppose * lst_remove_all_slow is called on this list (with x=0). * * This will turn out to NOT be a bad case, but figuring out * why is a good warmup exercise. * * Now recall that lst_remove_all_slow operates by * repeatedly calling lst_remove_first. * * What kind of scenario makes an _individual_ call * to lst_remove_first slow or fast? * * Consider when there is a match near the front. * How about when if the first match is near the end? * * Finally, what kind of configuration (list structure) results in * lst_slow_remove_all making many calls to lst_remove_first (where * "many" means "linear in N" such that each of those calls is * "slow" (also meaning "linear in N"). * * Once you have figured out a structure that makes lst_remove_all_slow take * quadratic time, you can complete the function! * * For the given n, lst_sra_bad_case will construct and return a list of * length n which if passed to lst_remove_all_slow with x=0, will result in * quadratic runtime. * * [By convention, the value to delete will be 0] * * * By the way, to test, you can try generating "bad" lists with large N * and passing them to lst_remove_all_slow. If your lists are really "bad" * then once N gets large enough, the slowdown will be evident just from * the terminal (once N gets above something like 20k, it should be obvious). * * [The trivial little program called quad.c gives you an idea of quadratic runtime] * * DIFFICULTY LEVEL: * Conceptual/pre-programming work: 3 * Implementation: 1.5 */ extern LIST *lst_sra_bad_case(int n); /** TODO * function: lst_remove_all_fast * * description: same behavior as lst_remove_all_slow but has * faster execution time even on "bad cases" as generated by * the function above. Number of operations proportional to the * length of the list regardless of number of matches and distribution * of matches. * * Approach: all occurrences of x removed in a single pass * * returns: number of elements removed * * DIFFICULTY LEVEL: 3+ */ extern int lst_remove_all_fast(LIST *l, ElemType x) ; /** 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); /** TODO * function: lst_merge_sorted * * description: assumes both list a and b are in * sorted (non-descending) order and merges them * into a single sorted list with the same * elements. * * This single sorted list is stored in a while * b becomes empty. * * if either of given lists are not sorted, * we blame the caller and the behavior is * implementation dependent -- i.e., don't worry * about it! * * Example: * * a: [2 3 4 9 10 30] * b: [5 8 8 11 20 40] * * after call on (a,b) * * a: [2 3 4 5 8 8 9 10 11 20 30 40] * b: [] * * implementation: should not allocate ANY new list * nodes -- it should just re-link existing * nodes. * * Must be linear time in the |a|+|b| -- i.e., * the total number of elements being processed. * * Suggestion: consider writing a recursive helper function * that does the merge at the "NODE level"; have the * non-recursive caller clean up the details (front, back * pointers, etc). * * DIFFICULTY LEVEL: 3 */ extern void lst_merge_sorted(LIST *a, LIST *b); 

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

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 
 ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
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; }; /************* structs and typedefs *************/ /* * returns pointer to newly created empty list */ LIST *lst_create() { LIST *l = malloc(sizeof(LIST)); l->front = NULL; l->back = NULL; return l; } LIST * lst_from_array(ElemType a[], int n) { int i; LIST *lst; lst = lst_create(); for(i=n-1; i>=0; i--) lst_push_front(lst, a[i]); return lst; } /** * TODO */ ElemType * lst_to_array(LIST *l, int *out_n) { return NULL; // placeholder } /** * TODO */ LIST *lst_clone(LIST *lst) { return NULL; // placholder } /* * frees entire list: * all associated nodes (if any) * and the LIST structure itself */ void lst_free(LIST *l) { NODE *p = l->front; NODE *pnext; while(p != NULL) { pnext = p->next; // keeps us from de-referencing a freed ptr free(p); p = pnext; } // now free the LIST free(l); } void lst_print(LIST *l) { NODE *p = l->front; printf("["); while(p != NULL) { printf(FORMAT, p->val); p = p->next; } printf("] "); } /** * (previous lab exercise - DONE/GIVEN) * function: lst_print_rev * prints list elements in reverse order * * [recursive helper function first p_rev which operates * at the "NODE level"] */ static void p_rev(NODE *p) { if(p==NULL) return; p_rev(p->next); printf(FORMAT, p->val); } void lst_print_rev(LIST *l) { printf(" [ "); p_rev(l->front); printf(" ] "); } /** * TODO * func: lst_increment_vals * desc: increments all of the elements of the given list. * * Example: * * before call:  * after call:  * * DIFFICULTY LEVEL: 1 */ void lst_increment_vals(LIST *l) { } /** * TODO * func: lst_are_equal * desc: returns 1 if the two given lists are equal: * * they are the same length and * contain the same sequence of values * * returns 0 otherwise * * DIFFICULTY LEVEL: 1 */ int lst_are_equal(LIST *lst1, LIST *lst2) { return 0; // placeholder } void lst_push_front(LIST *l, ElemType val) { NODE *p = malloc(sizeof(NODE)); p->val = val; p->next = l->front; l->front = p; if(l->back == NULL) // was empty, now one elem l->back = p; } void lst_push_back(LIST *l, ElemType val) { NODE *p; if(l->back == NULL) // list empty - same as push_front lst_push_front(l, val); else { // at least one element before push p = malloc(sizeof(NODE)); p->val = val; p->next = NULL; l->back->next = p; l->back = p; } } int lst_len(LIST *l) { NODE *p = l->front; int n=0; while(p != NULL) { n++; p = p->next; } return n; } int lst_is_empty(LIST *l) { return l->front == NULL; } /** * function: lst_count * description: Counts number of occurrences * of x in the list and returns * that value. */ int lst_count(LIST *l, ElemType x) { NODE *p=l->front; int n=0; while(p != NULL) { if(p->val == x) n++; p = p->next; } return n; } /* These are "sanity checker" functions that check to see * list invariants hold or not. */ int lst_sanity1(LIST *l) { if(l->front == NULL && l->back != NULL){ fprintf(stderr, "lst_sanity1 error: front NULL but back non-NULL "); return 0; } if(l->back == NULL && l->front != NULL){ fprintf(stderr, "lst_sanity1 error: back NULL but front non-NULL "); return 0; } return 1; } int lst_sanity2(LIST *l) { if(l->back != NULL && l->back->next != NULL) { fprintf(stderr, "lst_sanity2 error: back elem has a non-NULL next? "); return 0; } return 1; } /* * makes sure that the back pointer is also the last reachable * node when you start walking from front. * HINT: use pointer comparison */ int lst_sanity3(LIST *l) { printf("lst_sanity3 not implemented "); return 1; } ElemType lst_pop_front(LIST *l) { ElemType ret; NODE *p; if(lst_is_empty(l)) return DEFAULT; // no-op ret = l->front->val; if(l->front == l->back) { // one element free(l->front); l->front = NULL; l->back = NULL; } else { p = l->front; // don't lose node being deleted l->front = l->front->next; // hop over free(p); } return ret; } /* TODO * * if list is empty, we do nothing and return arbitrary value * otherwise, the last element in the list is removed and its * value is returned. * */ ElemType lst_pop_back(LIST *l) { return DEFAULT; } /* TODO * For full credit, you cannot allocate any new memory! * * description: see header file */ void lst_reverse(LIST *l) { } /* * removes first occurrence of x (if any). Returns * 0 or 1 depending on whether x was found */ int lst_remove_first(LIST *l, ElemType x) { NODE *p; NODE *tmp; if(l->front == NULL) return 0; if(l->front->val == x) { lst_pop_front(l); return 1; } // lst non-empty; no match on 1st elem p = l->front; while(p->next != NULL) { if(x == p->next->val) { tmp = p->next; p->next = tmp->next; if(tmp == l->back) l->back = p; free(tmp); return 1; } p = p->next; } return 0; } int lst_remove_all_slow(LIST *l, ElemType x) { int n=0; while(lst_remove_first(l, x)) n++; return n; } /** DONE * function: lst_sra_bad_case (sra: "slow_remove_all") * * description: constructs a list of length n such that * the above function takes quadratic time to remove * all occurrences of a specified value. * * By convention, the specified value will be 0 */ LIST *lst_sra_bad_case(int n) { // push n/2 0's on front of list followed // by n/2 1's // // thus 1st half of list is all 1's and 2nd // half is all 0's lst = lst_create(); while(n > n/2) { lst_push_front(lst, 0); n--; } while(n > 0) { lst_push_front(lst, 1); n--; } return NULL; } // TODO // desc: see header file int lst_remove_all_fast(LIST *l, ElemType x) { return 0; } // TODO int lst_is_sorted(LIST *l){ return 0; } /** 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. */ void lst_insert_sorted(LIST *l, ElemType x) { } /** TODO * function: lst_merge_sorted * * description: assumes both list a and b are in * sorted (non-descending) order and merges them * into a single sorted list with the same * elements. * * This single sorted list is stored in a while * b becomes empty. * * if either of given lists are not sorted, * we blame the caller and the behavior is * implementation dependent -- i.e., don't worry * about it! * * Example: * * a: [2 3 4 9 10 30] * b: [5 8 8 11 20 40] * * after call on (a,b) * * a: [2 3 4 5 8 8 9 10 11 20 30 40] * b: [] * * implementation: should not allocate ANY new list * nodes -- it should just re-link existing * nodes. * * Must be linear time in the |a|+|b| -- i.e., * the total number of elements being processed. */ void lst_merge_sorted(LIST *a, LIST *b){ } 
 
 ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
quad.c
 
// silly little program that runs a quadratic time function // for increasing values of n (n doubles each iteration). // // Purpose: person running the program will be able to observe // that once n gets large enough, the slowness of a quadratic // algorithm is readily apparent even in "wall clock" time // #include int quad(int n) { int i, j; int x=0; for(i=0; i 
 
 ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------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
  front val3 val 8 val |2 back