INTRODUCTION TO DATA STRUCTURES
A data structure is a scheme designed for organizing a set of data that can be manipulated using a set of operations. It is a system which is implemented independent of the way in which the data are physically arrayed in secondary storage. A simple example for a data structure is a Stack.
A stack is a data structure, which operates on the principle of “Last In First Out” (LIFO). Stacks are widely and extensively used in modern computer systems, and are usually implemented through a combination of hardware and software.
Figure: Simple representation of a Stack
Examples for data structures already exist in C are: array and pointer. Simple data structures like array and pointer can be defined in a language like C using the simple data types - int, float and char. Whereas, complex data structures can be defined using the simple data structures such as array and pointer.
It is possible to present several implementations of the same data structure, each with its own strengths and weaknesses. But, sometimes no implementation, hardware or software, can model a mathematical concept completely. When several implementations are possible, one implementation may be better than another for a specific application.
One important consideration in any implementation is its efficiency. Efficiency is usually measured by two factors: time and space. Unfortunately, there is usually a trade-off between these two measures, because an implementation that is fast uses more storage than one that is slow. The choice of implementation in such a case involves a careful evaluation of the trade-offs among the various possibilities.
Abstract Data Type (ADT):
An Abstract Data Type is a data type which defines a data structure with a set of operations to be performed on it. Objects such as list, set and graph, along with their operations, can be viewed as Abstract Data Type (ADT).
A data type is defined with a collection of values and a set of operations to be performed on those values. Whereas, an Abstract Data Type (ADT) is a mathematical abstraction of a data structure; no where in an ADT's definition is there any mention of how the set of operations is implemented.
The class in C++ allows for the implementation of ADTs, with appropriate hiding of implementation details. Thus any other part of the program that needs to perform an operation on the ADT can do so by calling the appropriate method.
Pointers in C:
Pointer is a derived data type in C, whose possible values are memory locations. For instance, if x is declared as an integer, then &x refers to the location that has been set aside to contain x. Therefore &x is said to be a pointer.
Examples for pointer variable declarations are:
int *pi;
float *pf;
char *pc;
In these examples, pi is a pointer to an integer, pf is a pointer to a float number, and pc is a pointer to a character. The asterisk indicates that the values of these variables being declared are pointers to values of the type specified in the declaration rather than object of that type.
Pointer values can be assigned like any other values. For eg., the statement,
pi = &x;
assigns the address of variable x to the pointer pi.
The notation *pi in C refers to the integer at the location referenced by the pointer pi. Thus the statement
x = *pi;
assigns the integer available in the memory location pointed by pi to the variable x.
Arithmetic operations on Pointers:
While declaring a pointer variable, C insists that the pointer should be specified of a particular data type. For example,
int *pi;
declares a pointer pi as not simply “a pointer”, but “pointer to an integer”. This is required for doing the arithmetic operations on pointers such as incrementing or decrementing the address of the pointer to refer to the next or previous locations of the current memory location indicated by the pointer.
If we consider that pi is a pointer to an integer, then pi + 1 is the pointer to the integer immediately following the integer *pi in memory, pi - 1 is the pointer to the integer immediately proceeding *pi, pi + 2 is the pointer to the second integer following *pi, and so on.
