## CS19002 Programming and Data Structures Laboratory, Section 5 |
## Spring 2007 |

Exercise 1 | Exercise 2 | Exercise 3 | Exercise 4 | Exercise 5 | |

Solution 1 | Solution 2 | Solution 3 | Solution 4 | Solution 5 | |

Show all | Hide all |

## Click on the links above

## Exercise 1

We want to define a set ADT. It should support the following operations.

search(set,element) /* To return true/false */ insert(set,element) /* To return the modified set */ /* An element already present in the set is not re-inserted */ delete(set,element) /* To return the modified set */ /* If the element does not belong to the set, the original set is returned */Assume that the elements of a set cannot be naturally ordered. So you maintain an unsorted list as a set. For working with a specific situation, assume that we are working with sets of integers.

Define data types for representing a set: one using static arrays, and another using linked lists.

## Solution 1

Using arrays#define MAXSIZE 1000 typedef struct { unsigned int size; int element[MAXSIZE]; } set;

Using linked liststypedef struct _node { unsigned int key; struct _node *next; } node; typedef node *set;## Exercise 2

Implement the insert function on sets under the array representation.

## Solution 2

set insert ( set S, int x ) { unsigned int i; for (i=0; i<S.size; ++i) if (S.element[i] == x) return S; if (S.size == MAXSIZE) { fprintf(stderr, "Error: set is already full\n"); return S; } S.element[S.size++] = x; return S; }## Exercise 3

Implement the insert function on sets under the linked list representation.

## Solution 3

set insert ( set S, int x ) { node *p; /* Search x in S */ p = S; while (p != NULL) { if (p -> key == x) return S; /* element already present */ p = p -> next; } /* Insert at the beginning */ p = (node *)malloc(sizeof(node)); p -> key = x; p -> next = S; return p; }## Exercise 4

Implement the delete function on sets under the array representation.

## Solution 4

set delete ( set S, int x ) { unsigned int i; for (i=0; i<S.size; ++i) if (S.element[i] == x) break; if (i < S.size) /* if x is present in S */ S.element[i] = S.element[--S.size]; /* replace x by the last element */ return S; }## Exercise 5

Implement the delete function on sets under the linked list representation.

## Solution 5

set delete ( set S, int x ) { node *p; p = S; while (p != NULL) if (p -> key == x) break; else p = p -> next; if (p == NULL) return S; /* if x is not present in S */ p -> key = S -> key; /* replace x by the first element */ p = S -> next; free(S); return p; }