Data structure

Data structure :-

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 relationship of the data in the real word. On the other hand, the structure should be simple enough that one can effectively process the data when necessary. This section will introduce us to some of the data structure which will be discussed in detail later in the text.

Arrays:-

The simplest type of data structure is a linear (or one dimensional) array. By a linear array, we mean a list of a finite number, n of similar data elements referenced respectively by a set if n consecutive number, usually 1,2,3,……..n. If we choose the name A for the array, then the elements of A are denoted by subscript notation.

A₁¸a₂ , a₃ ,………..,n₂

Or by the parenthesis notation

A(1),A(2),B(3)……….,A(N)

Or by the bracket notation

A[1], A[2], A[3]……….,A[N].

Regardless of the notation, the number K in a[k] is called subscript and a[k] is called subscript variable .

Remark: The parentheses notation and the bracket notation are frequently use when the array name consists of more than one letter or when the array name appears in an algorithm. When using this notation we will use ordinary uppercase letters for the name and subscripts as indicated above by the A and N . Otherwise, we may use the usual subscript notation of italics for the name and subscript and lowercase letter for the subscripts as indicated above by the a and n. the former

Notation follows the practice of computer-oriented texts whereas the latter notation follows the practice of mathematics in print.

Example:-

A linear array SUDENT consisting of the name of six students is pictured in fig. 1.1. Here STUDENT[1]

Denotes John Brown, STUDENT[2] denotes Sandra Gold, and so on.

STUDENT

John Brown

Sandra Gold

Tom Jones

Ram

Mohan

Ramavtar

6
Linear arrays are called one-dimensional arrays because each element in such an array is referenced by one subscript. A two-dimensional array is a collection of similar data elements where each element referenced by to subscript.(such arrays are called matrices in mathematics, and tables in business applications.) multidimensional arrays are defined analogously .

Linear array:-

A linear array is a list of a finite number n of homogeneous data element (i.e., data element of the same type) such that:

(a) The elements of the array are referenced respectively by an index set consisting of n consecutive numbers.

(b) The elements of the array are stored respectively in successive memory location .

The number n of elements is called the length or size of the array. If not explicitly stared, we will

Assume the index set consists of the integers 1,2……, n. In general the length or the number of data elements of the array can be obtained from the index set by the formula

Length=UB-LB+1

Where UB is the large index, called the upper bound and LB is the smallest index, called the lower bound of the array. Note that length=UB when LB=1.

The elements of an array A may be denoted by the subscript notation

A1, A2, A3, ……, An.

Or by parentheses notation (use in FORTAN, PL\1 and BASIC)

A(1), A(2), ……….., A(N).

Or by the bracket notation (use in Pascal )

A[1], A[2], …….., A[N].

We will usually use the subscript notation or the bracket notation. Regardless of the notation, the number K in A[K] is called a subscript or an index and A[K] is called a subscript variable. Note that subscripts allow any element of A to be referenced by its relative position in A.

Example:-

(a) Let DATA be a 6-element linear array of integer such that

DATA[1] = 247 , DATA[2] = 56 ,DATA[3] = 429 ,DATA[4] = 135 ,DATA[5] = 87 ,DATA[6] = 156

Sometimes we will denote such an array by simply writing

DATA: 247, 56, 429, 135, 87, 156.

REPRESENTATION OF LINEAR ARRAYS IN MEMORY

Let LA be a linear array in the memory of the computer. Recall that the memory of the computer is simply a sequence of addressed location as pictured in the fig. 4.2. let us use the notation

LOC(LA[K])= address of the element LA[K] of the array LA

101

102

103

104

105

106

Fig 4. 2.

TRAVERSING LINEAR ARRAY
Let A be a collection of data elements stored in the memory of the computer , suppose we want to print the contents of each element of A or suppose we want to count the number of elements of A with a given property. This can be accomplished by traversing A, that is, by accessing and

Processing (frequently called visiting)each element of A exactly once.

The following algorithm traverses a linear array LA. The simplicity of the algorithm comes from the fact that LA is a linear structure. Other linear structures, such as linked lists, can also be easily traversed. On the other hand, the traversal of nonlinear structures, such as tree and graph ,is considerably complicated.

Algorithm:- (Traversing a Linear Array) Here LA is a linear array with lower bound LB

And upper bound UB. This algorithm traverse LA appling an operating PROCESS to each element of LA.

1. [Initialize counter] set K= LB.

2. Repeat steps 3and 4 while K<=UB

3. [visit element] apply PROCESS to LA[K].

4. [increase counter] set K= k+1.

5. [End of step 2 loop.]

6. Exit.

INSERTING AND DELETING ARRAY

Let A be a collection of data elements in the memory of the computer. “Inserting” refers to the operation of adding another elements to the collection A and “deleting” refers to the operation of removing one of the elements from A. This section discusses inserting and deleting when A is a linear array.

Inserting an element at the “end” of a linear array can be easily done provided the memory space allocated for the array is large enough to accommodate the addition element. On the other hand, suppose we need to insert an element in the middle of the array. Then, on the average, half

Of the elements must be moved downward to new locations to accommodate the new element and keep the order of the other elements.

Similarly, deleting an element at the “end” of an array presents no difficulties, but deleting an

Element somewhere in the middle of the array would require that each subsequent element be moved one location upward in order to “fill up” the array.

Remark: since linear arrays are usually pictured extending downward, as in Fig. 4.1, the term “downward” refers to locations with larger subscripts, and the term “upward” refers to locations with smaller subscripts.

Example:-

Suppose TEXT has been declared to be a 5-element array by data have been recorded

Only for TEST [1], TEST[2]and TEST[3]. If X is the value of the next test, then one simply assigns

TEST [4] := X

to add X to the list. Similarly, if Y is the value of the subsequent test, then we simply assign

TEST [5] := y

to add Y to the list. Now, however, we cannot add any new test scores to the list.