READING for Week 3



Sedgewick, 3.1, 3.2, 3.3

Kernighan and Ritchie, read over Chapters 1, 2, and 3.


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


        EXERCISES for Week 3 (for discussion in precept 10/6)



 1. What is wrong with the following declaration?

        struct element { float f; struct element link; }

 2. Suppose that a linked list is made up of nodes of type

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

    that you are given a pointer "list" of type link, which
    points to the first node of the list; that the last node
    has NULL as its link; and that there are at least two nodes on the
    list.  Write a code fragment to delete the second node of the list.

 3. Under the same conditions as the previous question, write a code
    fragment to add a new node just after the second node of the list.

 4. What does the following program print out?

     #include <stdio.h>
     #include <stdlib.h>
     typedef struct ex* ptr;
     struct ex { ptr ff; int k; };
     main()
      {
         ptr x, y, t;
         x = malloc(sizeof *x);
         y = malloc(sizeof *y);
         x->ff = y; y->ff = x; x->k = 1; y->k = 1;
         for (t = x; t->k < 100; t = t->ff)
           t->k = x->k + y->k;
         printf("%d\n", t->k);
       }

 5. What does the following Postscript program do?

       %!
       200 200 moveto 
       100 100 rlineto 
       200 300 moveto 
       100 -100 rlineto
       stroke showpage

 6. Write a Postscript program to draw a "T".








                    Answers to Exercises for Week 3

 1. Missing * before link.  This is a meaningless "recursive" declaration,
    defining what a structure is in terms of what a structure is.  With the
    * it makes sense because it says that link is a pointer to an
    element, whatever that is.

 2. 
        list->next = list->next->next;
    
    To free the node, too, put "t = list->next" before and "free(t)" after
    this statement.

 3. 
        link t = malloc(sizeof *t);
        t->next = list->next->next; list->next->next = t;

 4. 144


 5. Draws an "X".

 6. 
       %!
       200 200 moveto 
       0 100 rlineto 
       150 300 moveto 
       100 0 rlineto
       stroke showpage