Array operation
Representation of Linear Arrays in Memory
n The
process to determine the address in a memory:
a) First address – base address.
b) Relative address to base address through
index function.
Example:
char A[100];
Let char uses 1 location storage.
If the base address is 1200 then the next
element is in 1201.
Index Function is written as:
Loc (A[i]) = Loc(A[0]) + i , i is subscript
and LB = 0
1200 1201 1202 --------
A[0] A[1] A[2]-----
- In general, index
function:
Loc (A[i]) = Loc(A[LB]) +
w*(i-LB);
where w is length of memory location
required.
For real number: 4 byte, integer: 2 byte and
character: 1 byte.
- Example:
If LB = 5, Loc(A[LB]) = 1200, and w = 4, find
Loc(A[8]) ?
Loc(A[8])= Loc(A[5]) + 4*(8 – 5)= 1212.
Traversing
Algorithm
§ Traversing operation means visit
every element once.
e.g. to print, etc.
§ Example algorithm:
1.
[Assign counter]
|
K=LB
// LB = 0
|
2. Repeat step 2.1 and 2.2 while K <=
UB // If LB = 0
|
2.1 [visit
element]
|
do
PROCESS on LA[K]
|
2.2 [add
counter]
|
K=K+1
|
3. end repeat
step 2
|
4. exit
|
Insert operation
Insert item at the back is easy if there is a space. Insert item in the middle requires the movement of all elements to the right as in Figure 1
INSERT(LA, N,
K, ITEM)
|
//LA is a
linear array with N element
|
//K is integer
positive where K < N and LB = 0
|
//Insert an
element, ITEM in index K
|
1. [Assign counter]
|
J = N – 1; // LB = 0
|
2. Repeat step 2.1 and 2.2 while J
>= K
|
2.1 [shift to the right all elements from J]
|
LA[J+1] = LA[J]
|
2.2 [decrement counter] J = J
– 1
|
3. [Stop repeat step 2]
|
4. [Insert element] LA[K] = ITEM
|
5. [Reset N] N = N + 1
|
Deletion Operation
Deletion refers to removing an existing element from the array and re-organizing all elements of an array.
Algorithm
Consider LA is a linear array with N elements and Kis a positive integer such that K<=N. Following is the algorithm to delete an element available at the Kth position of LA.
1. Start.
2. Set J = K
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J+1
6. Set N = N-1
7. Stop
click below for next operation
