Tutorial Exercises: Set 9

---

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 lists

   typedef 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;
   }

---

Back  |  Home