CS13002 Programming and Data Structures

Spring semester

Abstract data types

You are now a master C programmer. You know most of the essential features of C. So, given a problem, you plan to jump to write the code. Yes, I see that you have mentally written the #include line.

Please wait. Solving a problem is a completely different game. Writing the final code is only a tiny part of it. I admit that even when all the algorithms are fully specified, writing a good program is not always a joke, in particular, when the program is pretty huge and involves cooperation of many programmers. Think of the Linux operating system which was developed by thousands of free-lance programmers all over the globe. The system works pretty harmoniously and reportedly with much less bugs than software from commercial giants like Microsoft.

First notice that your code may be understood and augmented by third parties in your absence. Even if you flood your code with documentation, its readability is not ensured. An important thing you require is a design document. That is not at the programming level, but at a more abstract level.

Data abstraction is the first step. A problem is a problem of its own nature. It deals with input and output in specified formats not related to any computer program. For example, a weather forecast system reads gigantic databases and outputs some prediction. Where is C coming in the picture in this behavioral description? One can use any other computer language, perhaps assembly languages, or even hand calculations, to arrive at the solution.

Assume that you are taught the natural language English pretty well. You are also given a plot. Your problem is to write an attractive detective story in English. Is it a trivial matter? I think it is not quite so, at least for most of us. You have to carefully plan about your characters, the location, the sequence, the suspense, and what not. Each such planning step involves many things that have nothing to do with English. The murderer is to be modeled as a human being, an abstract data, together with a set of behaviors, a set of abstract procedures. There is no English till this point. A language is necessary only when you want to give a specific concrete form to these abstract things.

Still, you cannot perhaps be a Conan Doyle or Christie, neither in plot design nor in expressions. Well, they are geniuses. However, if you plan carefully and master English reasonably well to arrive at a decent and sleek production, who knows, you may be the script-writer for the next Bollywood blockbuster?

What is an abstract data type?

An abstract data type (ADT) is an object with a generic description independent of implementation details. This description includes a specification of the components from which the object is made and also the behavioral details of the object. Instances of abstract objects include mathematical objects (like numbers, polynomials, integrals, vectors), physical objects (like pulleys, floating bodies, missiles), animate objects (dogs, Pterodactyls, Indians) and objects (like poverty, honesty, inflation) that are abstract even in the natural language sense. You do not see C in Pterodactyls. Only when you want to simulate a flying Pterodactyl, you would think of using a graphics package in tandem with a computer language. Similarly, inflation is an abstract concept. When you want to model it and want to predict it for the next 10 years, you would think of writing an extrapolation program in C.

Specifying only the components of an object does not suffice. Depending on the problem you are going to solve, you should also identify the properties and behaviors of the object and perhaps additionally the pattern of interaction of the object with other objects of same and/or different types. Thus in order to define an ADT we need to specify:

There may be thousands of ways in which a given ADT can be implemented, even when the coding language remains constant. Any such implementation must comply with the content-wise and behavioral description of the ADT.

Examples

How to implement an abstract data type?

It is now and only now when you think about writing C codes. Carefully investigate the specification of the ADT and possible target applications where this ADT is going to be used. Plan for suitable C constructs to provide the appropriate functionality with good performance. Try to exploit your experience with C. But fully understand what you are going to implement, the limitations, the expected performance figures, the ease of code maintenance, and a lot of related issues. After all, you have to market your product.

Examples

A complete example : the ordered list ADT

Let us now define a new ADT which has not been encountered earlier in your math courses. We call this ADT the ordered list. It is a list of elements, say characters, in which elements are ordered, i.e., there is a zeroth element, a first element, a second element, and so on, and in which repetitions of elements are allowed. For an ordered list L, let us plan to have the following functionality:

L = init();
Initialize L to an empty list.

L = insert(L,ch,pos);
Insert the character ch at position pos in the list L and return the modified list. Report error if pos is not a valid position in L.

delete(L,pos);
Delete the character at position pos in the list L. Report error if pos is not a valid position in L.

isPresent(L,ch);
Check if the character ch is present in the list L. If no match is found, return -1, else return the index of the leftmost match.

getElement(L,pos);
Return the character at position pos in the list L. Report error if pos is not a valid position in L.

print(L);
Print the list elements from start to end.

We will provide two complete implementations of this ADT. We assume that the element positions are indexed starting from 0.

Implementation using static arrays

Let us restrict the number of elements in the ordered list to be <= 100. One can then use an array of characters of this size. Moreover, one needs to maintain the current size of the list. Thus the list data type can be defined as: 

   #define MAXLEN 100

   typedef struct {
      int len;
      char element[MAXLEN];
   } olist;
Let us now implement all the associated functions one by one. 
   olist init ()
   {
      olist L;

      L.len = 0;
      return L;
   }

   olist insert ( olist L , char ch , int pos )
   {
      int i;

      if ((pos < 0) || (pos > L.len)) {
         fprintf(stderr, "insert: Invalid index %d\n", pos);
         return L;
      }
      if (L.len == MAXLEN) {
         fprintf(stderr, "insert: List already full\n");
         return L;
      }
      for (i = L.len; i > pos; --i) L.element[i] = L.element[i-1];
      L.element[pos] = ch;
      ++L.len;
      return L;
   }

   olist delete ( olist L , int pos )
   {
      int i;

      if ((pos < 0) || (pos >= L.len)) {
         fprintf(stderr, "delete: Invalid index %d\n", pos);
         return L;
      }
      for (i = pos; i <= L.len - 2; ++i) L.element[i] = L.element[i+1];
      --L.len;
      return L;
   }

   int isPresent ( olist L , char ch )
   {
      int i;

      for (i = 0; i < L.len; ++i) if (L.element[i] == ch) return i;
      return -1;
   }

   char getElement ( olist L , int pos )
   {
      if ((pos < 0) || (pos >= L.len)) {
         fprintf(stderr, "getElement: Invalid index %d\n", pos);
         return '\0';
      }
      return L.element[pos];
   }

   void print ( olist L )
   {
      int i;

      for (i = 0; i < L.len; ++i) printf("%c", L.element[i]);
   }

Here is a possible main() function with these calls. 

   int main ()
   {
      olist L;

      L = init();
      L = insert(L,'a',0);
      printf("Current list is : "); print(L); printf("\n");
      L = insert(L,'b',0);
      printf("Current list is : "); print(L); printf("\n");
      L = delete(L,5);
      printf("Current list is : "); print(L); printf("\n");
      L = insert(L,'c',1);
      printf("Current list is : "); print(L); printf("\n");
      L = insert(L,'b',3);
      printf("Current list is : "); print(L); printf("\n");
      L = delete(L,2);
      printf("Current list is : "); print(L); printf("\n");
      L = insert(L,'z',8);
      printf("Current list is : "); print(L); printf("\n");
      L = delete(L,2);
      printf("Current list is : "); print(L); printf("\n");
      printf("Element at position 1 is %c\n", getElement(L,1));
   }

Here is the complete program.

Animation example : Implementation of the ordered list ADT with static memory

Implementation using linked lists

Let us now see an implementation based on dynamic linked lists. We use the same prototypes for function calls. But we define the basic data type olist in a separate manner. For the sake of ease of writing the functions, we maintain a dummy node at the beginning of the linked list. 

   typedef struct _node {
      char element;
      struct _node *next;
   } node;

   typedef node *olist;

   olist init ()
   {
      olist L;

      /* Create the dummy node */
      L = (node *)malloc(sizeof(node));
      L -> element = '\0';
      L -> next = NULL;
      return L;
   }

   olist insert ( olist L , char ch , int pos )
   {
      int i;
      node *p, *n;

      if (pos < 0) {
         fprintf(stderr, "insert: Invalid index %d\n", pos);
         return L;
      }
      p = L;
      i = 0;
      while (i < pos) {
         p = p -> next;
         if (p == NULL) {
            fprintf(stderr, "insert: Invalid index %d\n", pos);
            return L;
         }
         ++i;
      }
      n = (node *)malloc(sizeof(node));
      n -> element = ch; 
      n -> next = p -> next;
      p -> next = n;
      return L;
   }

   olist delete ( olist L , int pos )
   {
      int i;
      node *p;

      if (pos < 0) {
         fprintf(stderr, "delete: Invalid index %d\n", pos);
         return L;
      }
      p = L;
      i = 0;
      while ((i < pos) && (p -> next != NULL)) {
         p = p -> next;
         ++i;
      }
      if (p -> next == NULL) {
         fprintf(stderr, "delete: Invalid index %d\n", pos);
         return L;
      }
      p -> next = p -> next -> next;
      return L;
   }

   int isPresent ( olist L , char ch )
   {
      int i;
      node *p;

      i = 0;
      p = L -> next;
      while (p != NULL) {
         if (p -> element == ch) return i;
         p = p -> next;
         ++i;
      }
      return -1;
   }

   char getElement ( olist L , int pos )
   {
      int i;
      node *p;

      i = 0;
      p = L -> next;
      while ((i < pos) && (p != NULL)) {
         p = p -> next;
         ++i;
      }
      if (p == NULL) {
         fprintf(stderr, "getElement: Invalid index %d\n", pos);
         return '\0';
      }
      return p -> element;
   }

   void print ( olist L )
   {
      node *p;

      p = L -> next;
      while (p != NULL) {
         printf("%c", p -> element);
         p = p -> next;
      }
   }

The main() function of the static array implementation can be used without any change under this implementation. Here is the complete program.

Animation example : Implementation of the ordered list ADT with dynamic memory

This exemplifies that the abstract properties and functional behaviors are independent of the actual implementation, or stated in another way, our two implementations of the ordered list ADT correctly and consistently tally with the abstract specification.

And why should we stop here? There could be thousand other ways in which the same ADT can be implemented, and in all these cases the function prototypes may be so chosen that the same main() function will work. This is the precise difference between an abstract specification and particular implementations.

Course home