For this homework, you will write a program to create and manipulate a simple li
ID: 3775372 • Letter: F
Question
For this homework, you will write a program to create and manipulate a simple linked list. For each node in the linked list you will generate a random number, create a node that holds that number, and insert that node into its sorted position in the linked list. Once the nodes are inserted, you will traverse the list, printing the value held in each node. Then you will clean up the list (deleting all the nodes) and exit the program. You will also learn about a tool that you can use to help you check for memory errors in your code.
Specifications:
Define a struct appropriate for holding a random integer. This struct will also contain a "next" pointer to reference a separate instance of the struct.
You may use the typedef keyword to give your struct a separate typename if you wish, but this is not a requirement.
The program will read command line arguments. The first argument is the program name (as it will always be) followed by a random number seed, the number of random numbers to generate and ending with the Maximum Possible Value of the Random numbers generated (i.e. argc should be 4).
Your program will use a "dummy node" for the linked list. In other words, the head of the list will be an actual node, but the data field in that node will not be used for sorting purposes.
Your program must contain the following functions:
main() (for obvious reasons)
insertNodeSorted() - You may implement this either of two ways.
One way is to use the head of the list as one parameter and the integer value as the second. The function will allocate memory for the node, initialize it and then insert it in the proper location in the list.
The other way is to pass the head of the list as one parameter and a previously allocated and initialized node as the other. The existing node is inserted in the proper location in the list.
printList() - Takes the head of the list as its only parameter, traverses the list, printing out the data in sorted order.
deleteList() - Takes the head of the list as its only parameter, traverses the list, deleting all nodes.
The basic algorithm of your program is
Use a loop (based upon command line input values) that:
Generates a random number
Prints the number to stdout
Creates a node that contains that random number
Inserts the new node in sorted order into the existing list
Print the sorted linked list
Delete the linked list
You will use a Makefile to compile your program
Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
struct test_struct
{
int val;
struct test_struct *next;
};
struct test_struct *head = NULL;
struct test_struct *curr = NULL;
struct test_struct* create_list(int val)
{
printf(" creating list with headnode as [%d] ",val);
struct test_struct *ptr = (struct test_struct*)malloc(sizeof(struct test_struct));
if(NULL == ptr)
{
printf(" Node creation failed ");
return NULL;
}
ptr->val = val;
ptr->next = NULL;
head = curr = ptr;
return ptr;
}
struct test_struct* add_to_list(int val, bool add_to_end)
{
if(NULL == head)
{
return (create_list(val));
}
if(add_to_end)
printf(" Adding node to end of list with value [%d] ",val);
else
printf(" Adding node to beginning of list with value [%d] ",val);
struct test_struct *ptr = (struct test_struct*)malloc(sizeof(struct test_struct));
if(NULL == ptr)
{
printf(" Node creation failed ");
return NULL;
}
ptr->val = val;
ptr->next = NULL;
if(add_to_end)
{
curr->next = ptr;
curr = ptr;
}
else
{
ptr->next = head;
head = ptr;
}
return ptr;
}
struct test_struct* search_in_list(int val, struct test_struct **prev)
{
struct test_struct *ptr = head;
struct test_struct *tmp = NULL;
bool found = false;
printf(" Searching the list for value [%d] ",val);
while(ptr != NULL)
{
if(ptr->val == val)
{
found = true;
break;
}
else
{
tmp = ptr;
ptr = ptr->next;
}
}
if(true == found)
{
if(prev)
*prev = tmp;
return ptr;
}
else
{
return NULL;
}
}
int delete_from_list(int val)
{
struct test_struct *prev = NULL;
struct test_struct *del = NULL;
printf(" Deleting value [%d] from list ",val);
del = search_in_list(val,&prev);
if(del == NULL)
{
return -1;
}
else
{
if(prev != NULL)
prev->next = del->next;
if(del == curr)
{
curr = prev;
}
else if(del == head)
{
head = del->next;
}
}
free(del);
del = NULL;
return 0;
}
void print_list(void)
{
struct test_struct *ptr = head;
printf(" Printing list Start ");
while(ptr != NULL)
{
printf(" [%d] ",ptr->val);
ptr = ptr->next;
}
printf(" Printing list End ");
return;
}
int main(void)
{
int i = 0, ret = 0;
struct test_struct *ptr = NULL;
print_list();
for(i = 5; i<10; i++)
add_to_list(i,true);
print_list();
for(i = 4; i>0; i--)
add_to_list(i,false);
print_list();
for(i = 1; i<10; i += 4)
{
ptr = search_in_list(i, NULL);
if(NULL == ptr)
{
printf(" Search [val = %d] failed, no such element found ",i);
}
else
{
printf(" Search passed [val = %d] ",ptr->val);
}
print_list();
ret = delete_from_list(i);
if(ret != 0)
{
printf(" delete [val = %d] failed, no such element found ",i);
}
else
{
printf(" delete [val = %d] passed ",i);
}
print_list();
}
return 0;
}
*********************
out put
Printing list Start
Printing list End
creating list with headnode as [5]
Adding node to end of list with value [6]
Adding node to end of list with value [7]
Adding node to end of list with value [8]
Adding node to end of list with value [9]
Printing list Start
[5]
[6]
[7]
[8]
[9]
Printing list End
Adding node to beginning of list with value [4]
Adding node to beginning of list with value [3]
Adding node to beginning of list with value [2]
Adding node to beginning of list with value [1]
Printing list Start
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
Printing list End
Searching the list for value [1]
Search passed [val = 1]
Printing list Start
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
Printing list End
Deleting value [1] from list
Searching the list for value [1]
delete [val = 1] passed
Printing list Start
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
Printing list End
Searching the list for value [5]
Search passed [val = 5]
Printing list Start
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
Printing list End
Deleting value [5] from list
Searching the list for value [5]
delete [val = 5] passed
Printing list Start
[2]
[3]
[4]
[6]
[7]
[8]
[9]
Printing list End
Searching the list for value [9]
Search passed [val = 9]
Printing list Start
[2]
[3]
[4]
[6]
[7]
[8]
[9]
Printing list End
Deleting value [9] from list
Searching the list for value [9]
delete [val = 9] passed
Printing list Start
[2]
[3]
[4]
[6]
[7]
[8]
Printing list End
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.