Abstract data types..

Why We Need Abstract Data Types?

We’re well acquainted with data types by now, like integers, arrays, and so on. To access the data, you’ve used operations defined in the programming language for the data type, for instance by accessing array elements by using the square bracket notation, or by accessing scalar values merely by using the name of the corresponding variables.

This approach doesn’t always work on large programs in the real world, because these programs evolve as a result of new requirements or constraints. A modification in program requires one or more changes in data structures. We have to change many fields and operations related to that data structure. For example if we change a program that keeps records of a personal to add some more details then we may have to change the array or other structure. This may lead to change in operation also. Thus, it is useful to separate the use of a data structure from the details of its implementation. This is the principle underlying the use of abstract data types.

Definition of Abstract Data Types:

Abstract data structures are just mathematical entities consisting of a set of values (the carrier set) and a collection of operations that manipulate them. For example Integer abstract data type is a collection of all positive and negative numbers including zero and a collection of operation such as addition, subtraction, multiplication, division, equality comparison and and order comparison.

In general, following are called abstract data types:

  1. Stack: Operations are “push an item onto the stack”, “pop an item from the stack”, “ask if the stack is empty”; implementation may be as array or linked list or whatever.
  2. Queue: Operations are “add to the end of the queue”, “delete from the beginning of the queue”, “ask if the queue is empty”; implementation may be as array or linked list or heap.
  3. Search Structure: Operations are “insert an item”, “ask if an item is in the structure”, and “delete an item”; implementation may be as array, linked list, tree, hash table, …

Implementation of Abstract Data Types in C:

In C, a complex data type is typically represented by a pointer to the information stored in the data type. A C function can pass the pointer to other functions without knowing the details of what the pointer points to. One may also use parts of a program that have been separately compiled. All that a part of a program need know about functions it calls is their names and the types they return.

Thus, the convention in C is to prepare two files to implement an abstract data type. One (whose name ends in “.c”) provides the implementation view; it contains the complete declaration for the data type, along with the code that implements its associated operations. The other (whose name ends in “.h”) provides the abstract view; it contains short declarations for functions, pointer types, and globally accessible data.

The abstract data type “stack” might then be represented as follows:

Stack.h

typedef struct StackStructType *StackType;

	/* Return a pointer to an empty stack. */
	extern StackType InitStack ( );
	/* Push value onto the stack, returning success flag. */
	extern boolean Push (int k);
	/* Pop value from the stack, returning success flag. */
	extern boolean Pop ( );
	/* Print the elements of the stack. */
	extern PrintStack (StackType stack);

Stack.c

#include "stack.h"
	#define STACKSIZE 5
	struct StackStructType {		/* stack is implemented as */
		int stackItems [STACKSIZE];	/*  an array of items */
		int nItems;	/*  plus how many there are */
	};
	typedef struct StackStructType *StackType;

	/*
	**	Return a pointer to an empty stack.
	*/
	StackType InitStack ( ) {
		char *calloc( );
		StackType stack;
		stack = (StackType) calloc (1, sizeof (struct StackStructType));
		stack->nItems = 0;
		return (stack);
	}

Parts of the program that need to use stacks would then contain a line

#include “stack.h”

(Often the “.c” file also includes the corresponding “.h” file, as shown above, to insure consistency of function and type declarations.) The program would call InitStack to set up a stack, receiving in return a pointer of type StackType; it would access the stack by passing this pointer to Push, Pop, etc. Such a program would work no matter what the contents of stack.c, provided only that the implemented functions performed as specified in stack.h.

Advertisements

About bijolianabhi

Graduate from Engineering College Bikaner, India in 2010 and working as Open Source activist. I love programming and implementing interesting ideas. I have interest in Mozilla Firefox extension development. I am currently learning basics of python to develop some interesting applications.
This entry was posted in C, Programming, Programming Concepts and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s