CS19002 Programming and Data Structures Laboratory |
Spring 2010, Section 5 |

In this assignment, you are asked to implement a list ADT to support the following operations.

L = init()- Initialize
Lto an empty list.L = insert(L,n)- Insert the integer
ninL.L = delete(L)- Delete the median(s) from the list
L. IfLcontains an odd number of items, the central one is deleted. IfLcontains an even number of items, then the two central elements are deleted.empty(L)- Returns true if and only if
Lis empty.print(L)- Print the items stored in the list
L.

Make a linked-list-based implementation of this ADT. It is useful to
keep the list sorted. While inserting `n`, the exact location of
`n` is first determined so as to keep the list sorted after the
insertion. During deletion, the center of the list is first located. In
order to locate the center, it may be useful to store the size (number of
elements) in the list. In view of this, define the list data type as
follows.

typedef struct _node { int data; struct _node *next; } node; typedef struct { int size; node *head; } list;

Write the ADT functions as described above. Maintaining a dummy node at the beginning of the list is expected to simplify your implementation.

Your functions should be compatible with the following `main()`
function.

#include <stdio.h> #include <stdlib.h> #include <time.h> #define N 25 int main () { list L; int i; srand((unsigned int)time(NULL)); L = init(); for (i=0; i<N; ++i) { L = insert(L, 100 + rand() % 900); print(L); } while (!empty(L)) { L = delete(L); print(L); } exit(0); }

Lab Home | Submission Site | My Home |