Various Data structures operations
Table of Content:
Data may be organized in many different ways. The logical or mathematical model of a particular organization of data is called a data structure. The choice of a particular data model depends on two considerations. First. it must be rich enough in structure to mirror the actual relationships of the data in the real world.
On the other hands, the structure should be simple enough that one can effectively process the data when necessary.
The data structure also describes the relationship among the elements in addition to memory storage. The data appearing in the data structure are processed by means of certain operations. The four operations that play a major role are :
- Inserting
- Deleting
- Traversing
- Searching
- Sorting
- Merging
Inserting: Adding a new record to the structure.
Deleting: Removing a record from the structure.
Traversing: Accessing each record exactly once so that certain items in the record may be processed.
Searching: Finding the location of a particular record.
Sorting and merging are two operations used in special situations.
Sorting: Arrange the records in same logical order.
Merging: Combining the records of the different sorted file into one sorted file.
Notion of Abstract Data Type
The ADT's are generalizations of primitive data type (integer, char etc) and they encapsulate a data type in the sense that the definition of the type and all operations on that type localized to one section of the program. They are treated as a primitive data type outside the section in which the ADT and its, operations are defined.
An, implementation of an ADT is the translation into statements of a programming language of the declaration that defines a variable to be of that ADT, plus a procedure in that language for each operation of the ADT. The implementation of the ADT chooses a data structure to represent the ADT.
A useful tool for specifying the logical properties of data type is the abstract data type. Fundamentally, a data type is a collection of values and a set of operations on those values. That collection and those operations form a mathetmatical construct that may be implemented using a particular hardware or software data structure. The term abstract data type refers to the basic mathematical concept that defines the data type.
In defining an abstract data type as mathematical concept, we are not concerned with space or time efficiency. Those are implementation issue. Infact, the definition of ADT is not concerned with implementation detail at all. It may not even be possible to implement a particular ADT on a particular piece of hardware or using a particular software system. For example, we have already seen that an ADT integer is not universally implementable.
To illustrate the concept of an ADT and our specification method, consider the ADT RATIONAL which corresponds to the mathematical concept of a rational number. A rational number is a number that can be expressed as the quotient of two integers. The operations on rational numbers that, we define are the creation of a rational number from two integers, addition, multiplication and testing for equality. The following is an initial specification of this ADT.
/* Value definition */ abstract typedef < integer, integer > RATIONAL; condition RATIONAL [1]! = 0; /*Operator definition*/ abstract RATIONAL makerational (a, b) int a, b; precondition b! = 0; postcondition makerational [0] = a; makerational [1] = b; abstract RATIONAL add [a, b] RATIONAL a, b; postcondition address[1] == a[1] * b[1] address[0] == a[0] * b[1] + b[0] * a[1] abstract RATIONAL mult [a, b] RATIONAL a, b; postcondition mult[0] = = a[0] * b[a] mult[1] = = a[0] * b[1] abstract equal (a, b) RATIONAL a, b;
postcondition equal = = a[0] * b[1] = = b[0] *apt An ADT consists of two parts : a value definition and an operation definition. The value definition defines the collection of values for the ADT and consists of two parts : a definition clause and a condition clause, For example, the value definition for the ADT RATIONAL states that a RATIONAL value consists of two integers, the second of which does not equal to O. The keyword abstract typedef introduces a value definitions and the keyword condition is used to specify any conditions on the newly defined data type. In this definition the condition specifies that the denominator may not be 0. The definition clause is required, but the condition may not be necessary for every ADT. Immediately following the value definition comes the opeator definition. Each operator is defined as an abstract junction with three parts : a header, the optional preconditions and the post-conditions. For example the operator definition of the ADT RATIONAL includes the operations of creation (makerational) , addition (add) and multiplication (mult) as well as a test for equality (equal). Let us consider the specification for multiplication first, since, it is the simplest. It contains a header and post-conditions, but no pre-conditions.
abstract RATIONAL mult [a, b] RATIONAL a, b; postcondition mult [0] = a[0] * b[0] mult [1] = a[1] * b[1]
The header of this definition is the first two lines, which lines, are just like a C function header. The keyword abstract indicates that it is not a C function but an ADT operation definition.
The post-condition specifies, what the operation does. In a post-condition, the name of the function (in this case, mult) is used to denote the result of an operation. Thus mult[0] represents numarator of result nd mult[1] specifies, what conditions become true after the operation is the executed. In this example the post-condition specifies the numerator of the result of a rational multiplication equals integer product of numerators of the two inputs and that the denominator equals the integer product of two denominators.