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
Related post :Data Structure vs Storage Structure
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
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
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
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
–Beginning
–Middle
–End
DEMO 1
Insert Ford at the
End of Array
DEMO 2
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
–Beginning
–Middle
–End
Related post >>Double link list
DEMO 1
Deletion
of Wagner at the End of
Array
DEMO 2
Deletion
of Davis
from the Array
No data item can be deleted from an empty array
Insertion Algorithm
•INSERT
(LA, N , K , ITEM)
[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
•DELETE
(LA, N , K , ITEM)
[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
No comments:
Post a Comment
THANKS FOR UR GREAT COMMENT