Types of data structure

Data Structure Data structure is collection of data elements which are characterised by accessing functions. The accessing functions are used to store  and  retrieve data elements. For example if the data is organised  as an array A of 100 elements then it's  elements  are represented  as A(1),A(2),.....A(100). In this example accessing function is A(K), which refers to Kth element of the array A. Types of data structures Data structures can be classified as: 1. Primitive data structures Basic data types such as integer,real ,character and boolean  are Known as primitive data structures or simple data types. They are known to be simple data types as they consists of those characters that can not be divided. 2. Non-Primitive data structures The simplest example of the non-primitive data structure is the processing of complex numbers. Very few computers are capable of doing arithmetic on complex numbers. The other examples are linked-lists,stacks,queues,trees and graphs. Logical versus physical implementation Logical implementation At the logical level, the user treats the given data whether it Is primitive or structured from programming point of  view.  The user may not have any knowledge about the storage of data in  the memory or how the operations are performed on this data.  For a user,  logically 2*3=6. He knows that 2*3 gives the result 6 But he  is  not aware where and how the  operations,  namely  2,3,and multiplication are stored in the memory or how the  computer  is performing this operation. Physical implementation By the physical implementation of data structure, it is meant the mode of storage of data. This physical implementation of data structure is discussed below : There  are many modes of stroage of data in computer memory. For example integers are stored in : 1. Signed bit magnitued form 2. One's complement form 3. Two's complement form 4. Binary coded decimal(BCD). This  knowledge of physical storage of data along with the  valid opertaions  permitted,  permits the user to create ,  access  and Change the data. Classification of data structures Data structures can be classified as: 1. Linear data structures 2. Non-linear data structures. 1. Linear data structures A data structure is said to be linear if it's elememnts form a sequence  or a linear list. The following are the two basic ways in  which  this type of linear structure is  represented  in  the memory. A. In the first way, the linear relationship between the elements is  represented by means of sequential memory  locations.  Arrays ,stacks and queues are the examples of such a data structure. B.  In the second way , the linear relationship between  elements is established by means of pointers or links. Such a data structure is known as linked data structure. 2. Non-linear data structures The elements of a non-linear data structure don't form a sequence but it represents hierarchial relationship between it's elements. Such  data  structures  are represented by  menas  of  tress  and graphs. Operations on data structures The following operations can be performed on data structures: 1. Traversing When each element of a data structure is accessed and processed Exactly once, it is called as traversing. 2. Searching Searching operations refers to finding the locations of an elment with a given value from the data structure. 3. Insertion The operation of adding a new element into the given data structure is known as insertion. 4. Deletion The operation of removing an element from the given data structure is known as deletion. 5. Sorting Sorting operation refers to rearranging the elements of a data structure in logical sequences. It can be used to arrange the List of numbers in ascending or descending order or to arrange the list of names in the alphabetic order. 6. Merging The operation of merging refers to combining the elements of two similar data structures into one. 7. Inverting Inverting refers to the operation of arranging the elemnts of a data structure in the reverse order. 8. Copying The operation of copying is used to copy the contents of one data Structure into another similar structure. Linear arrays The linear or one dimensional array is called a vector. It is a simple data structure. A one dimensional array consists of cer tain no.  of elements arranged in sequence. Each element has a right  neighbour  and a left neighbour except the  first  element Which has no left neighbour & the last element which has no right neighbour.  Once  the  address  of first  element  in  memory  is known,the address of any element of the array can be computed. It is convenient to store the address of first element in a register in order to allow the free relocation of the array in memory. Creating Arrays To create arrays,different programming languages have  different methods.But in all the languages : 1. The name of the array 2. It's type 3. The index set have to declared. Accesssing an array The basic operation that can be performed on arrays is the direct access of each element.A computer requires only the name and the subscript of the array to access any element from the array.  As the mode  of an element of an array is direct or random  so  the time to access every element of the array is same. If any element of array A can be accessed and processed in a time independent of its location this implies that the array can be indexed. This is an important property of the linear arrays in contrast to  linked lists. Lower and upper bounds The smallest element of the array's index is called the lower bound and will be represented as LB. Similarly the index of the highest element of the array is called it's upper bound and  will be represented as UB. In general, N the number of elements also known as it's range is given by N=UB-LB+1. Implementation of linear arrays in memory The array declaration instructs the computer to reserve and assign a block of consecutive memory locations to the elements of the  given  array . This memory is sufficient to store  all  the components  of the given array. The address of the first element is  called BASE ADDRESS of the array and is commonly  denoted  by BA.The address or location of any element A(K) can be  calculated by operating  system in terms of the base address by  using  the relation: Location of A(K)=BA+K-LB Consider an array of 10 integer elements. Where LB=5 and UB=10 and let it's BA=500 then this array will  be represented in the memory as : ______________________________________________________ | Array | A(5) | A(6) | A(7) | A(8) | A(9) | A(10) | | Element |------|------|------|------|------|-------| |-----------| | | | | | | | Memory | 500 | 501 | 502 | 503 | 504 | 505 | | Address | | | | | | | |___________|______|______|______|______|______|_______| Upto now, we has assumed that each element of the array occupies only one memory location. It is quite possible that each element of the array occupies more then one word. If each element occupies W words then address or location of A(K), the Kth element of the array is given as : Location of A(K) = BA + W (K-LB) Example An array HEIGHT consists of 5 real elements. Each element requires three memory  words for storage. Calculate the location of the fourth element of the array if the base address is 1000. Solution It is given that BA=1000, LB=1, W=3 We know that location of A(k) = BA + W(K-LB) Therefore, location of HEIGHT (4) = 1000 + 3(4-1) = 1000 + 3*3 = 1000 + 9 = 1009 Rules for writing arrays 1.  The name of the array is written according to the rules for writing the name of variables or identifiers. 2. A subscript used as array element may be one of the following types: a. An Integer Constant. b. An Integer Variable. c. An Integer Expression. 3.  The upper limit must be greater than the lower limit.  These limits must be seprated by delimiter. Over Dimensioning of arrays Using lesser number of memory locations than specified in the array declaration statement is called over dimensioning of array. Over dimensioning of arrays may be done by a programmer when he first runs a test program with small amount of data. Under dimensioning of arrays It is not permissible to use subscripted variables with sub scripts greater than those declared in the array declaration Statement. Packed Arrays The efficient use of computer memory can be achieved by packing data values  close to each other.Pascal  provides  facility  for packed arrays  in  which data items are  packed  close  to  each Other.The use of packed arrays permits a large quantity of data to be stored in a given memory space. Disadvantages of packed arrays The use of packed arrays may not be beneficial in all situations. The gain in storage may result in loss of computing speed. However, the use of packed arrays has an advantage over the use of unpacked arrays in the following situations. 1.  A program involving a large number of array assignments by Which elements of one array are assigned to the other. 2. A program which includes procedures calls in which arrays are Passed as value parameters. 3. A program in including function calls in which arrays are used as parameters.