Question
The code below (knapsack.h) provides the definitions and the prototypes of the functions for our knapsack. Your task is to implement the functions specified in
The code below (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. Written in C Language.
--------------------------------------------------------------------------------------------------------------------------------------------------------------
/* 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);
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started