The code below (knapsack.h) provides the definitions and the prototypes of the f
ID: 3723070 • Letter: T
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 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);
Explanation / Answer
// all the function definition is written in C language.
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
};
listitemptr KnapsackAdd(listitemptr knapsack, int item)
{
listitemptr prev=NULL;
while(knapsack!=NULL)
{
prev=knapsack;
if(knapsack->item==item)
{
knapsack->count+=1;
return knapsack
}
knapsack=knapsack->next;
}
listitemptr new_item=listitemptr malloc(sizeof(struct listitem));
new_item->item=item;
new_item->count=1;
new_item->next=NULL;
if(prev!=NULL)
prev->next=new_item;
return new_item;
}
listitemptr KnapsackRemove(listitemptr knapsack, int item)
{
listitemptr prev;
listitemptr curr=knapsack;
if(knapsack==NULL)// knapsack is empty
return NULL;
while (curr != NULL && curr->item != item)
{
prev =curr;
curr = curr->next;
}
if(curr==NULL)// if item not found
return NULL;
if(curr->count==1)
{
if(knapsack->next==NULL)// If only one node is prestent in knapsack
{
free(knapsack);//free memory
return NULL;
}
prev->next=curr->next;
free(curr); //free memory
}
else
curr->count-=1;
return knapsack;
}
void KnapsackPrint(listitemptr knapsack)
{
if(knapsack==NULL)
printf("(nothing)");
else
{
while(knapsack->next!=NULL)
{
printf("%d(%d),",knapsack->item,knapsack->count);
knapsack=knapsack->next;
}
printf("%d(%d)",knapsack->item,knapsack->count);
}
}
unsigned int KnapsackItemCount(listitemptr knapsack, int item)
{
unsigned int no_of_specific_item=0;
while(knapsack!=NULL)
{
if(knapsack->item==item)
{
no_of_specific_item=knapsack->count;
break;
}
knapsack=knapsack->next;
}
return no_of_specific_item;
}
unsigned int KnapsackSize(listitemptr knapsack)
{
unsigned int total_count=0;
while(knapsack!=NULL)
{
total_count+=knapsack->count;
knapsack=knapsack->next;
}
return total_count;
}