## CS13002 Programming and Data Structures | ## Section: 4/D, Spring 2005 |

## 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 L_{0},L_{1},...,L_{n-1}are nested lists or integers for some n >= 1, then (L_{0},L_{1},...,L_{n-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 = (L_{0}L_{1}... L_{m-1}) is a list and a is an integer, then assign to L the nested list (L_{0}L_{1}... L_{k-1}a L_{k}... L_{m-1}). Report error if k > m. */ L = insertList(L,M,k); /* If L = (L_{0}L_{1}... L_{m-1}) is a list and M is a list, then assign to L the nested list (L_{0}L_{1}... L_{k-1}M L_{k}... L_{m-1}). Report error if k > m. */ L = join(L,M); /* If L = (L_{0}L_{1}... L_{m-1}) and M = (M_{0}M_{1}... M_{n-1}) are nested lists, assign to L the nested list (L_{0}L_{1}... L_{m-1}M_{0}M_{1}... M_{n-1}). */ L = delete(L,k); /* If L = (L_{0}L_{1}... L_{m-1}) is a nested list, assign to L the nested list (L_{0}L_{1}... L_{k-1}L_{k+1}... L_{m-1}). Report error if k >= m. */ print(L); /* Print the nested list L as a fully parenthesized expression. */For the

insertListandjoinoperations the argument listMmust be mutually disjoint fromL.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

sublistpointer heads a sub-list. If it isNULL, then the integerelementis to be treated as the content of that node.

OutputUse 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

(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 outputSuppose 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)).