Tutorial Exercises: Set 10

---

Click on the links above

Exercise 1

Define a data type for a node in a singly linked list of integers. Write a function that, upon the input of a pointer to the header of the list, prints the items stored in the list from beinning to end.

Solution 1

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

   void printList ( node *p )
   {
      while (p != NULL) {
         printf("%d ", p -> data);
         p = p -> next;
      }
   }

Exercise 2

Write a recursive function that, upon the input of a pointer to the header of a linked list, prints the items stored in the list in the reverse order, that is, from end to beginning. Also write a non-recursive function for the same task.

Solution 2

   void printListRev ( node *p )
   {
      if (p == NULL) return;
      printListRev(p -> next);
      printf("%d ", p -> data);
   }


   void printListRevIter ( node *p )
   {
      node *q, *r;

      if (p == NULL) return;

      /* First let r point to the last node in the list */
      r = p; while (r -> next != NULL) r = r -> next;

      /* Print the last item in the list */
      printf("%d ", r -> data);

      while (r != p) {
         /* Let q point to the node previous to the node pointed to by r */
         q = p; while (q -> next != r) q = q -> next;

         /* Print the content of this previous node */
         printf("%d ", q -> data);

         /* Move r backward by one node */
         r = q;
      }
   }

Exercise 3

Write a C function that reverses a linked list and returns a pointer to the new header.

Solution 3

   node *listRev ( node *head )
   {
      node *p, *q, *r;

      p = head;
      q = NULL;
      while (p != NULL) {
         r = p -> next;
         p -> next = q;
         q = p;
         p = r;
      }
      return q;
   }

Exercise 4

Write a C function that merges two sorted linked lists into a single sorted linked list by adjusting the pointers in the input lists (that is, without making any fresh memory allocation). The function should return a pointer to the header of the merged list.

Solution 4

   node *mergeLists ( node *p, node *q )
   {
      node *r, *head;

      if (p == NULL) return q;
      if (q == NULL) return p;
      if (p -> data < q -> data) {
         r = head = p;
         p = p -> next;
      } else {
         r = head = q;
         q = q -> next;
      }
      while ((p != NULL) && (q != NULL)) {
         if (p -> data < q -> data) {
            r -> next = p;
            p = p -> next;
         } else {
            r -> next = q;
            q = q -> next;
         }
         r = r -> next;
      }
      r -> next = (p == NULL) ? q : p;
      return head;
   }

Exercise 5

Write a function that returns a doubly linked list of complex numbers storing the numbers n²+sqrt(n) for n=1,2,...,100.

Solution 5

   typedef struct _node {
      double re;
      double im;
      struct _node *next;
      struct _node *prev;
   } node;

   node *createList ( )
   {
      node *p, *q, *head;
      int n;

      head = (node *)malloc(sizeof(node));
      head -> re = head -> im = 1;
      head -> prev = NULL;
      p = head;
      for (n=2; n<=100; ++n) {
         q = (node *)malloc(sizeof(node));
         q -> re = (double)(n * n);
         q -> im = sqrt((double)n);
         q -> prev = p;
         p -> next = q;
         p = q;
      }
      p -> next = NULL;
      return head;
   }

---

Back  |  Home