Array operations

this is adata structure lecture.

1. Lecture 01: DS & Algorithms:2013
Iftikhar 1
DATA STRUCTURES &
ALGORITHMS
Iftikhar Muhammad
1

2. Lecture 01: DS & Algorithms:2013
Iftikhar
Arrays Operations
•Traversal
•Inserting
•Deletion
•Search
•Sorting
2

3. Lecture 01: DS & Algorithms:2013
Iftikhar
Traversal
•Traversing:
•In traversing operation, each element of an array is accessed
exactly once for processing. This is called visiting of the array.
•To compute the sum of values of each element of an array.
•Display values of each element of an array.
•Algorithm:
•1. Set k=LB
•2. Repeat Step 3 and Step 4 while k<=UB
•3. Apply PROCESS to LA[K]
•4. Set K=K+1
•5. [End of Step 2 loop]
•6. Exit
3

4. Lecture 01: DS & Algorithms:2013
Iftikhar
Traversal Algo
•Find the Number NUM of years during which
more than 300 automobiles were sold.
•1. Set NUM=0
•2. Repeat for K=1932 to 1984
•3. If AUTO[K]>300, then: Set NUM=NUM +1.
•4. [End of Loop]
•5. Return
4

5. Lecture 01: DS & Algorithms:2013
Iftikhar
Inserting
•In inserting operation , new data items are added or inserted into
any location of an empty or filled array.
•In case of empty array, new values are stored in empty locations.
•In case of filled array , old values are either replaced by new values
or pushed backward to make room for new values.
•It is very easy to insert data at the end of array(Why?).
•Without disturbing the data of other elements of the array.
5

6. Lecture 01: DS & Algorithms:2013
Iftikhar
Inserting
•Algorithm- Inserting value at specified location
1.Set J=N
2.Repeat Step 3 and Step 4 while J>=K
3.Set LA[J+1]=LA[J]
4.Set J=J-1
5.[End of Step 2 loop]
6.Set LA[K]=ITEM
7.Set N=N+1
8.Exit
6

7. Lecture 01: DS & Algorithms:2013
Iftikhar
Deletion
•Deleting item from a specified Location
•When the data item is removed from a specified location within an
array, the items from that location up to the end of array are moved
one location towards the beginning of the array.
•Algorithm:
1.Set ITEM=LA[K]
2.Repeat for J=K to N-1
3.Set LA[J]=LA[J+1]
4.[End of loop]
5.Set N=N-1
6.Exit
7

8. Lecture 01: DS & Algorithms:2013
Iftikhar
Search
•The Process of finding a specific data item and its location in an
array is called searching.
•Successful- If found
•Terminated- If data item found
•Unsuccessful
•Searching Operation in data structures is used for data modification
together with inserting, deleting and updating.
•For example , when a data item is to be deleted , it is first searched
and then deleted, if found.
•The most commonly used search algorithms are as follows.
•i. Sequential Search
•Ii. Binary Search
8

9. Lecture 01: DS & Algorithms:2013
Iftikhar
Search
•The sequential search is a slow process and is used for only small lists of data.
•The Method is not recommended for large amount of data because some more
efficient methods are available for large and complex searches.
•Algorithm: Linear Search
1.SET LOC=-1
2.INPUT N values into array XYZ
3.INPUT VAL
4.Repeat Step 5 For I= 1 TO N
5.IF VAL = XYZ[I] THEN
6.LOC=1
7.Print “value found at location”, LOC
8.Exit
9.END IF
10.If LOC=-1 THEN
11.PRINT ”Value is not Found”
12.END IF
13.EXIT
9

10. Lecture 01: DS & Algorithms:2013
Iftikhar
Search(Binary Search)
1.Set BEG=LB, END=UB and MID=INT((BEG+ENG)/2
2.Repeat Steps 3 and 9 while BEB<=ENG and DATA[MID]!=ITEM
3.If ITEM<DATA[MID],then
4.Set END=MID-1
5.Else
6.Set BEG=MID+1
7.END IF
8.Set MID=INT((BEG+END))/2
9.END OF LOOP
10.If DATA[MID]=ITEM, then
11.Set LOC=MID
12.Else
13.Set LOC=NULL
14.END IF
15.EXIT
10