/* knapsack.h * implements simple knapsack data structure as a linked list * NOTE: a function may update the value of input argument *knapsack if it changes the first node of the knapsack to another node. Such a change include the case when an item is added to an empty knapsack */

/* 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. Nodes should be in ascending order. You must simply increase the "count" if the item already exist in the knapsack; "count" must be set to 1 for previously-nonexisting items * @param knapsack: pointer to a listitemptr, itself pointing to the first item 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: [see KnapsackAdd() params]; updated to NULL if knapsack becomes empty * @param item: integer item to remove * @return 0 if successful, -1 otherwise (when item not found or knapsack is empty) */ int KnapsackRemove(listitemptr *knapsack, int item);

/* * prints integer items (in ascending order) and their counts in a knapsack * @param knapsack: [see KnapsackAdd() params] * @stdout: for example, "" (nothing) when knapsack==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(const listitemptr *knapsack);

/* * returns count of a specific item in a knapsack * @param knapsack: [see KnapsackAdd() params] * @param item: integer item to search for * @return item count, or 0 if it does not exist */ unsigned int KnapsackItemCount(const listitemptr *knapsack, int item);

You probably remember the knapsack problem from your previous courses. We will implement a very simple knapsack data structure in this task. Since we do not know the number of items to be stored in the knapsack beforehand, your implementation must rely on dynamic allocation of memory for managing knapsack storage. Our knapsack data structure simply stores a set of items (integer values) and their counts. The items are sorted in ascending order (from smaller to larger.) The header file 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.We 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. In other words, only the function prototypes currently in knapsack.h specify the interface of your knapsack unit. Note that your knapsack.c must not contain a main) function. In order to test your knapsack code, you should create a main() function in a separate file (knapsack-test.c) which tests the functionality of your knapsack code by calling its functions. knapsack-test.c may 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 that 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 item 8 o check knapsack size consider a second knapsack k2 (note that your main() can maintain multiple knapsacks concurrently) o add the following items sequentially: 5, 10, 15, 20, 10 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 Note that we will not grade your knapsack-test.c code. This is only for your own testing. We will use a similar approach to test and grade your knapsack code by compiling our own main() and linking it with your knapsack.c code Submission: files knapsack.c, knapsack-test.c You probably remember the knapsack problem from your previous courses. We will implement a very simple knapsack data structure in this task. Since we do not know the number of items to be stored in the knapsack beforehand, your implementation must rely on dynamic allocation of memory for managing knapsack storage. Our knapsack data structure simply stores a set of items (integer values) and their counts. The items are sorted in ascending order (from smaller to larger.) The header file 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.We 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. In other words, only the function prototypes currently in knapsack.h specify the interface of your knapsack unit. Note that your knapsack.c must not contain a main) function. In order to test your knapsack code, you should create a main() function in a separate file (knapsack-test.c) which tests the functionality of your knapsack code by calling its functions. knapsack-test.c may 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 that 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 item 8 o check knapsack size consider a second knapsack k2 (note that your main() can maintain multiple knapsacks concurrently) o add the following items sequentially: 5, 10, 15, 20, 10 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 Note that we will not grade your knapsack-test.c code. This is only for your own testing. We will use a similar approach to test and grade your knapsack code by compiling our own main() and linking it with your knapsack.c code Submission: files knapsack.c, knapsack-test.c