C Exercise 2

Linked list manipulations

Assume you have a structure like this:

     struct node {
         int dat;
         struct node *next;
     };

a) Complete the body of the following function "new_node":

     struct node* new_node(int d)
     {

     }

What should new_node do? Given an integer value as paramter, new_node should malloc a structure of type "node", fill its "dat" field with the value passed as parameter, and initialize the "next" field of the structure with 0. The function should return the address of the newly allocated structure.

b) Write a function:

   struct node* append(struct node *h, struct node *n)
   {

   }

What does append do?

Let's say you are calling it from main like this:

   main()
   {
        struct node *h = 0;
        h = append(h, new_node(10));
        h = append(h, new_node(20));
        h = append(h, new_node(30));
   }

The result of the three calls to append should be: you should get a linked list having 3 nodes - the first node containing 10, next one 20 and the last node 30. The pointer variable "h" should contain the address of the first node of the list.

c) Write a function "count" which will return total number of nodes in a list; "count" should be a recursive function (do not use a global variable for maintaining count).

     n = count(h); /* returns number of nodes in list pointed to by h */

d) Write a function "insert_before" which will insert a new node before an existing node.

       h = insert_before(h, b, n); /* Insert "n" before "b"; "h" is starting address */

Take care to handle all special cases. Test your code thoroughly. First write an iterative version of this function and then try to write a recursive version.

e) Write a "reverse" function which works like this:

Suppose your list contains 10, 20, 30.

      h = reverse(h); 
      print_nodes(h); /* This will print 30, 20, 10 */

"reverse" does not create a new list - it simply changes the pointers in the existing list.

Write iterative as well as recursive versions

f) Write a recursive "print_nodes" function which will print the data contained in all the nodes of the list.

h) Suppose we have a polynomial like this:

        5a^4 + 7a^2 + 2a - 3

We can represent each term by a structure:

    struct term {
          int coeft, exponent;
    }

The whole polynomial can be represented as a linked list of terms.

The above polynomial can be entered from the keyboard like this:

    5  4
    0  3
    7  2
    2  1 
    -3 0

Assume that we enter terms in descending order of exponent value (or ascending order, if you feel that is more convenient).

Modify the "new_node" function to create and return a term; call it "new_term"

Write a "create_polynomial" function which will read the number of terms from the keyboard, and then pairs of coeft/exponent values. "create_polynomial" will call "new_term" to create a new term after it reads every coeft/exponent value from the keyboard. It will then call "append" to append the newly created term to a list. Finally, this function will return address of the newly created list.

Write a "add_polynomials" function which works like this:

        c = add_polynomials(a, b);

where "a" and "b" are pointers to the first term of two polynomials.

Write a "multiply_polynomials" function which uses "add_polynomials".

Write a "print_polynomial" function which will display a polynomial on the screen.