Write a C program to create and manipulate a simple linked list. For each node i

Question

Write a C 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.

---------------------------------------

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()

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

Explanation / Answer

Solution:

C program for create and manipulate a simple linked list and Select a Random Node from a Singly Linked List.

Programme:

/* C program to randomly select a node from a singly
linked list */
#include<stdio.h>
#include<stdlib.h>
#include <time.h>

/* Link list node */
struct node
{
   int key;
   struct node* next;
};

// A reservoir sampling based function to print a
// random node from a linked list
void printRandom(struct node *head)
{
   // IF list is empty
   if (head == NULL)
   return;

   // Use a different seed value so that we don't get
   // same result each time we run this program
   srand(time(NULL));

   // Initialize result as first node
   int result = head->key;

   // Iterate from the (k+1)th element to nth element
   struct node *current = head;
   int n;
   for (n=2; current!=NULL; n++)
   {
       // change result with probability 1/n
       if (rand() % n == 0)
       result = current->key;

       // Move to next node
       current = current->next;
   }

   printf("Randomly selected key is %d ", result);
}

/* BELOW FUNCTIONS ARE JUST UTILITY TO TEST */

/* A utility function to create a new node */
struct node *newNode(int new_key)
{
   /* allocate node */
   struct node* new_node =
       (struct node*) malloc(sizeof(struct node));

   /* put in the key */
   new_node->key = new_key;
   new_node->next = NULL;

   return new_node;
}

/* A utility function to insert a node at the beginning
of linked list */
void push(struct node** head_ref, int new_key)
{
   /* allocate node */
   struct node* new_node = new node;

   /* put in the key */
   new_node->key = new_key;

   /* link the old list off the new node */
   new_node->next = (*head_ref);

   /* move the head to point to the new node */
   (*head_ref) = new_node;
}

// Driver program to test above functions
int main()
{
   struct node *head = NULL;
   push(&head, 5);
   push(&head, 20);
   push(&head, 4);
   push(&head, 3);
   push(&head, 30);

   printRandom(head);

   return 0;
}

Input: 1

Output: Randomly selected key is 30

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.