/* knapsack.h

* implements simple knapsack data structure as a linked list

*/

/* pointer to linked list node data structure */

typedef struct listitem* listitemptr;

/* data structure to use as linked list nodes */

struct listitem {

int item; // actual int item

unsigned int count; // number of the same item in the knapsack; should be >= 1

listitemptr next; // pointer to next item

};

/*

* adds an item to a knapsack; must only update the "count" if the item already exist in the knapsack; "count" must be set to 1 for previously-nonexisting items

* @param knapsack: points to the first listitem in a knapsack; NULL if knapsack has not been created yet

* @param item: integer item to add

* @return pointer to the listitem added/updated; NULL if unsuccessful

*/

listitemptr KnapsackAdd(listitemptr knapsack, int item);

/*

* removes a value from a knapsack; must update the "count" and delete the associated listitem when count becomes 0

* @param knapsack: points to the first listitem in a knapsack

* @param item: integer item to remove

* @return pointer to the first listitem in knapsack; NULL if knapsack becomes empty

*/

listitemptr KnapsackRemove(listitemptr knapsack, int item);

/*

* prints elements and their counts in a knapsack

* @param knapsack: points to the first listitem in a knapsack

* @stdout: for example, "" (nothing) when knpsack==NULL, or "125 (4), -10 (1), 26 (2)" when items include four of 125, one of -10, and two of 26

* @return void

*/

void KnapsackPrint(listitemptr knapsack);

/*

* count the number of specific item in the knapsack

* @param knapsack: points to the first listitem in a knapsack

* @param item: integer item to search for

* @return item count, or 0 if it does not exist

*/

unsigned int KnapsackItemCount(listitemptr knapsack, int item);

/*

* total count of items in the knapsack

* @param knapsack: points to the first listitem in a knapsack

* @return total item count. for example, 7 in case of above example "125 (4), -10 (1), 26 (2)"

*/

unsigned int KnapsackSize(listitemptr knapsack);

pointer to the first listitem in the knapsack; NULL if empty." Note that function prototype stays the same. Our knapsack data structure simply stores a set of items (integer values) and their counts. The header file task2/knapsack.h provides the definitions and the prototypes of the functions for our knapsack. Your task is to implement the functions specified in the header file in a new source file called knapsack.c. I have provided detailed comments about the job of each function, its parameters, and its expected output. You are free to implement more helper functions in your source if needed. But any program should be able to use your knapsack functions by just including the existing header file and accessing the compiled version of your knapsack code. Note that your knapsack.c should not contain a main() function. In order to test your knapsack code, you should create a main() function in a separate file (say test_knapsack.c) which tests the functionality of your knapsack code by calling its functions. As discussed above, test_knapsack.c can only include knapsack.h (not knapsack.c). You can then use gcc to compile and link your source codes to create an executable. In your main() , you should call knapsack functions with various inputs to ensure each function works correctly. You can also use a sequence of different calls such as the below pseudo-code: consider knapsack k1 o add the following items sequentially: 10, -20, 10, 15, -20, 10 o check count of item 10 o check count of 8 o check knapsack size consider a second knapsack k2 (note that you can maintain multiple knapsacks concurrently) o add the following items sequentially: 5, 10, 15, 20, -5 o remove item 15 o remove item 10 add a new 10 to k1 check size of k2 check size of k1 You need to inspect the output after each call by comparing it against the expected output. You can use assert for testing the return value of a function against the expected value