Assignment 6

---

[ Submission site  |  Show solution  |  Hide solution ]

---

In this exercise you work with linked lists. First define a node in a linked list as follows.

   typedef struct _node {
      int key;
      struct _node *next;
   } node;

Write a function that creates a list of n integers randomly chosen between 0 and 999 (both inclusive). Also write a function that prints the items stored in a linked list sequentially from beginning to end. These two functions are already covered in the tutorial.

Part 1 [Credit: 60%]

Write a function that takes as argument a pointer p to the first node of a linked list. Assume that the list is non-empty. The first element in the list is called the pivot. The function splits the list in two parts: the first part consists of the nodes with key values smaller than or equal to the pivot, and the second part consists of the nodes with key values larger than the pivot. The first part contains the pivot and so is non-empty. The second part may be empty. In any case, a pointer to the first node of the second part is returned by the function. The first part continues to be headed by the old header pointer.

Do not create new linked lists to store the two parts. Adjust the pointers of the original list so that the split is done. There must not be any memory allocation call in the splitting function.

   node *splitList ( node *p );

Part 2 [Credit: 40%]

Write a function that takes the headers of two linked lists as inputs, and returns the linked list obtained by concatenating the two input lists. Note that one or both of the input lists must be allowed to be empty.

There must not be any memory allocation calls inside the function. Only adjust the pointers so that joining is performed.

   node *joinList ( node *p, node *q );

Here is a sample main() function that checks the above functions.

   int main ()
   {
      node *p, *q, *t;
      unsigned int n;

      srand((unsigned int)time(NULL));
      printf("Enter the size of list    : "); scanf("%u", &n); printf("%d\n", n);
      p = buildList(n);
      printf("The list before splitting : "); printList(p);
      q = splitList(p);
      printf("Sublist with smaller keys : "); printList(p);
      printf("Sublist with larger keys  : "); printList(q);
      t = joinList(p,q);
      printf("The list after joining    : "); printList(t);
   }

Dowload the skeleton of the program.

Report the output of your program on the following values of n (the length of the list).

   0
   1
   10
   100
   1000

Sample run

   Enter the size of the list: 50
   The list before splitting :  514 190 112 742 903  70 200 155 881 694 215
    246  78 393 958 348 178  53 153 662 645 245 950  96 780 727 707 973 255
    946 864 769 488 329 511 392 751  63 547 985 757 114 231 835 859 189 536
     37 595  41
   Total count = 50
   Sublist with smaller keys :  514 190 112  70 200 155 215 246  78 393 348
    178  53 153 245  96 255 488 329 511 392  63 114 231 189  37  41
   Total count = 27
   Sublist with larger keys  :  742 903 881 694 958 662 645 950 780 727 707
    973 946 864 769 751 547 985 757 835 859 536 595
   Total count = 23
   The list after joining    :  514 190 112  70 200 155 215 246  78 393 348
    178  53 153 245  96 255 488 329 511 392  63 114 231 189  37  41 742 903
    881 694 958 662 645 950 780 727 707 973 946 864 769 751 547 985 757 835
    859 536 595
   Total count = 50

---

Solution

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX 1000

typedef struct _node {
   int key;
   struct _node *next;
} node;

node *buildList ( int n )
{
   node *p, *head;
   int i;

   if (n <= 0) return NULL;
   head = p = (node *)malloc(sizeof(node));
   p -> key = rand() % MAX;
   for (i=1; i<n; ++i) {
      p -> next = (node *)malloc(sizeof(node));
      p -> next -> key = rand() % MAX;
      p = p -> next;
   }
   p -> next = NULL;
   return head;
}

void printList ( node *p )
{
   int cnt = 0, nelp = 7;

   while (p != NULL) {
      printf("%4d", p -> key);
      p = p -> next;
      ++cnt;
      if (++nelp == 18) { printf("\n"); nelp = 0; }
   }
   if (nelp != 0) printf("\n");
   printf("Total count = %d\n", cnt);
}

node *splitList ( node *p )
{
   node *q = NULL, *qhead = NULL;
   int pivot;

   if (p == NULL) return NULL;
   pivot = p -> key;
   while (p -> next != NULL) {
      if (p -> next -> key <= pivot) {
         p = p -> next;
      } else {
         if (q == NULL) {
            q = p -> next;
            qhead = q;
         } else {
            q -> next = p -> next;
            q = q -> next;
         }
         p -> next = p -> next -> next;
      }
   }
   if (q != NULL) q -> next = NULL;
   return qhead;
}

node *joinList ( node *p, node *q )
{
   node *t;

   if (p == NULL) return q;
   t = p;
   while (t -> next != NULL) t = t -> next;
   t -> next = q;
   return p;
}

int main ()
{
   node *p, *q, *t;
   unsigned int n;

   srand((unsigned int)time(NULL));
   printf("Enter the size of the list: "); scanf("%u", &n); printf("%d\n", n);
   p = buildList(n);
   printf("The list before splitting : "); printList(p);
   q = splitList(p);
   printf("Sublist with smaller keys : "); printList(p);
   printf("Sublist with larger keys  : "); printList(q);
   t = joinList(p,q);
   printf("The list after joining    : "); printList(t);
   printf("\n");
}

Output

---

[ Submission site  |  Show solution  |  Hide solution ]

---

Back  |  Home