Tutorial Exercises: Set 8

---

Click on the links above

Exercise 1

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

Solution 1

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

   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 2

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

Solution 2

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

   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 -> next = (p == NULL) ? q : p;
      return head;
   }

Exercise 3

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

Solution 3

   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;
   }

Exercise 4

Define a polynomial with integer coefficients as follows:

   typedef {
      unsigned int deg;
      int *coeff;
   } poly;

Write a function that takes as input two polynomials and returns the product of the two input polynomials.

Solution 4

   poly prod ( poly f, poly g )
   {
      poly h;
      int i, j;

      h.deg = f.deg + g.deg;
      h.coeff = (int *)malloc(h.deg * sizeof(int));
      for (i=0; i<=h.deg; ++i) h.coeff[i] = 0;
      for (i=0; i<=f.deg; ++i)
         for (j=0; j<=g.deg; ++j)
            h.coeff[i+j] += f.coeff[i] * g.coeff[j];
      return h;
   }

Exercise 5

Define a matrix as the following structure:

   typedef {
      unsigned int nrow;
      unsigned int ncol;
      int **element;
   } matrix;

Write a function that accepts, as input, a non-negative integer n, and returns the Vandermonde matrix whose (i,j)-th entry is (i+1)^j for 0<=i,j<=n-1.

Solution 5

   matrix Vandermonde ( unsigned int n )
   {
      matrix V;
      int i, j;

      V.nrow = V.ncol = n;
      if (n == 0) V.element = NULL;
      else {
         V.element = (int **)malloc(n * sizeof(int *));
         for (i=0; i<n; ++n) {
            V.element[i] = (int *)malloc(n * sizeof(int));
            V.element[i][0] = 1;
            for (j=1; j<n; ++j)
               V.element[i][j] = V.element[i][j-1] * (i+1);
         }
      }
      return V;
   }

---

Back  |  Home