Assignment 9

A nested ordered list of integers is recursively defined as follows:

   Rule 1: The empty tuple () is a nested list.
   Rule 2: If L0,L1,...,Ln-1 are nested lists or integers for some n >= 1,
           then (L0,L1,...,Ln-1) is again a nested list.

Here are some examples:

   ()
   (3 4 5)
   (() 3 () (4) 5)
   (3 (4) ((5) () (6 7 (8))) ((9) ()))

A nested list should support the following functions:

   L = init();             /* Initialize the nested list L to the empty list () */
   isEmpty(L);             /* Returns true if and only if L is an empty nested list */
   L = insertInt(L,a,k);   /* If L = (L0 L1 ... Lm-1) is a list and a is an integer, then assign to L the
                              nested list (L0 L1 ... Lk-1 a Lk ... Lm-1). Report error if k > m. */
   L = insertList(L,M,k);  /* If L = (L0 L1 ... Lm-1) is a list and M is a list, then assign to L the
                              nested list (L0 L1 ... Lk-1 M Lk ... Lm-1). Report error if k > m. */
   L = join(L,M);          /* If L = (L0 L1 ... Lm-1) and M = (M0 M1 ... Mn-1) are nested lists,
                              assign to L the nested list (L0 L1 ... Lm-1 M0 M1 ... Mn-1). */
   L = delete(L,k);        /* If L = (L0 L1 ... Lm-1) is a nested list, assign to L the nested list
                              (L0 L1 ... Lk-1 Lk+1 ... Lm-1). Report error if k >= m. */
   print(L);               /* Print the nested list L as a fully parenthesized expression. */

For the insertList and join operations the argument list M must be mutually disjoint from L.

Implement the nested list ADT using dynamic linked lists. A node in such a list should be ready to hold either an integer or another list. The following structure may be used.

   typedef struct _node {
      int element;
      struct _node *sublist;
      struct _node *next;
   } node;

   typedef node *nlist;

The sublist pointer heads a sub-list. If it is NULL, then the integer element is to be treated as the content of that node.

Output

Use a sequence of the above calls to prepare the following nested lists. Also print the sequence of calls that you have used to prepare these lists. Finally, print the prepared lists using the print function.

   (1 (2) (3) (4 5))
   (1 (2 () 3) 4 ((5) 6))
   (1 (2 3) 4 6)
   (((((((0) 1) 2) 3) 4) 5) 6)
   (0 (1 (2 (3 (4 (5 (6)))))))

For each of the above examples you mat start from an empty list and grow it gradually to reach the end result.

Sample output

Suppose we want to prepare the lists: (5 (6 7) 8) and (5 (6 7)). The following sequence may be used:

   L = init();
   Now the list L is ().
   L = insertInt(L,5,0);
   Now the list L is (5).
   L = insertInt(L,8,1);
   Now the list L is (5 8).
   L1 = init();
   Now the list L1 is ().
   L1 = insert(L1,7,0);
   Now the list L1 is (7).
   L1 = insert(L1,6,0);
   Now the list L1 is (6 7).
   L = insertList(L,L1,1);
   Now the list L is (5 (6 7) 8).
   L = delete(L,2);
   Now the list L is (5 (6 7)).

---

[Submission site] [Lab home] [Course home]