Friday, 1 November 2013

linear structure : Array

Linear  Arrays

A linear array is a list of a finite number of n homogeneous data elements ( that is data elements of the same type) such that
The elements are of the arrays are referenced respectively by an index set consisting of n consecutive numbers
The elements of the arrays are stored respectively in successive memory locations .
The number n of elements is called the length or size of the array. 
The index set consists of the integer 1, 2, … n
Length or the number of data elements of the array can be obtained from the index set by
  Length = UB – LB + 1 where UB is the largest index called the upper bound and LB is the smallest index called the lower bound of the arrays .

Element of an array A may be denoted by
Subscript notation A1, A2, , …. , An
Parenthesis notation A(1), A(2), …. , A(n)
Bracket notation A[1], A[2], ….. , A[n]
The number K in A[K] is called subscript or an index and A[K] is called a subscripted variable 

Related post :Data Structure vs Storage Structure

Representation of Linear Array in Memory

Representation of Linear Array in Memory
Let LA be a linear array in the memory of the computer
LOC(LA[K]) = address of the element LA[K] of the array LA
The element of LA are stored in the successive memory cells

Computer does not need to keep  track of the address of every element of LA, but need to track only the address of the first element of the array denoted by Base(LA) called the base address of LA 
LOC(LA[K]) = Base(LA) + w(K – lower bound) where w is the number of words per memory cell of the array LA [w is aka size of the data type] .

Example 1  :

Find the address for LA[6]
Each element of the array occupy 1 byte  
example of array

LOC(LA[K]) = Base(LA) + w(K – lower bound)
LOC(LA[6]) = 200 + 1(6 – 1)  = 205 

Example 2:

Find the address for LA[16]
Each element of the array occupy 2 byte  
linear structure : Array
LOC(LA[K]) = Base(LA) + w(K – lower bound)

LOC(LA[16]) = 200 + 2(16 – 1) =230

Representation of Linear Array in Memory

Given any value of K, time to calculate LOC(LA[K]) is same
Given any subscript K one can access and locate  the content of  LA[K] without scanning any other element of LA 
A collection A of data element is said to be index if any element of A called Ak can be located and processed in time that  is independent of K

Traversing Linear Arrays

Traversing is accessing and processing (aka visiting ) each element of the data structure exactly ones

linear array

1.Repeat for K = Lower Bound to Upper Bound
  Apply PROCESS to LA[K]
  [End of Loop]
2.  Exit 

             Insertion  in array

Insertion: Adding an element
Insert  Ford at the  End  of Array 
insertion in array

Insert  Ford as the  3rd Element  of Array 
Note :Insertion is not Possible without loss of data if the array is FULL

Deletion in array 

Deletion: Removing an element
Related post >>Double link list
Deletion of Wagner  at the  End  of Array

deletion in array

Deletion of  Davis  from the  Array 
deletion in array
No data item can be deleted from an empty  array 

Insertion Algorithm  

[LA is a linear array with N elements and K is a positive integers such that K ≤ N. This algorithm insert an element ITEM into the Kth position in LA ]
  1.   [Initialize Counter] Set J := N
  2.   Repeat Steps 3 and 4 while J ≥ K
  3.   [Move the Jth element downward ] Set LA[J + 1]   := LA[J]
  4.   [Decrease Counter] Set J := J -1
  5   [Insert Element] Set LA[K] := ITEM
  6.   [Reset N] Set N := N +1;
  7.   Exit 

Deletion  Algorithm  

[LA is a linear array with N elements and K is a positive integers such that K ≤ N. This algorithm deletes Kth element from  LA ]
  1.   Set ITEM := LA[K]
  2.   Repeat for J = K to N -1:
     [Move the J + 1st element upward] Set LA[J]   := LA[J + 1]
  3.   [Reset the number N of elements] Set N := N - 1;
  4.   Exit 

RElated post : >> Multidimensional Array

YOU may like these

No comments:

Post a Comment


Blogger Widgets