Data Structure & Algorithms
Muzammil Khan
Department of
Computer & Software Technology
University of Swat
1
Chapter 2
Data Structure
“Array”
Data Structure & Algorithms
2
Array
Array is
A container which can hold a fix number of items
These items should be of the same type
Most of the data structures make use of arrays to implement
their algorithms
Following are the important terms to understand the
concept of Array.
Element
Each item stored in an array is called an element.
Index
Each location of an element in an array has a numerical
index, which is used to identify the element.
Data Structure & Algorithms
3
Array Representation
Arrays can be declared in various ways in different
languages
For illustration, let's take C array declaration.
Memory representation
Each element can be accessed via its index i.e. array[0]
Each element has it binary memory address
Data Structure & Algorithms
4
Basic Operations on Array
Following are the basic operations supported by an array
Traverse
Prints all the array elements one by one
Insertion
Adds an element at the given index
Deletion
Deletes an element at the given index
Search
Searches an element using the given index or by the value
Update
Updates an element at the given index
Data Structure & Algorithms
5
Traverse a “Linear Array”
Algorithm’s Description
Here LA is a Linear array with lower boundary LB and
upper boundary UB. This algorithm traverses LA applying
an operation Process to each element of LA.
Algorithm’s Statements
Step 1. Set K=LB [Initialize counter]
Repeat Steps 2 to 4
Step 2. while K≤UB. then
Step 3. Apply PROCESS to LA[K] [Visit element]
Step 4. Set k=K+1 [Increase counter]
[End of Step 2 loop.]
Step 5. Exit
Data Structure & Algorithms
6
Traverse a “Linear Array” (Cont…)
An alternative algorithm of the previous one
Algorithm’s Description
Here LA is a Linear array with lower boundary LB and
upper boundary UB. This algorithm traverses LA applying
an operation Process to each element of LA.
Algorithm’s Statements
Step 1. Repeat for K=LB to UB.
Apply PROCESS to LA[K]
[End of loop].
Step 2. Exit
Data Structure & Algorithms
7
Search in Array
Algorithm’s Description
Here LA is a Linear Array with N elements and KEY is a
given item of information to search. This algorithm finds the
location of KEY in LA if successful, otherwise it returns
unsuccessful
Algorithm’s Statements
LINEAR_SEARCH (LA, KEY)
Step 1. Repeat for i = 0 to N-1
Step 2. if( LA[i] = KEY)
return i [Successful Search]
Exit
Step 3. Return [Un-Successful search]
Step 4. Exit
Data Structure & Algorithms
8
Insertion in Array
Based on the requirement
A new element can be added at the beginning, end, or any
given index of array
Algorithm’s Description
Here LA is a Linear Array (unordered) with N elements and
K is a counter variable such that K<=N. Following is the
algorithm where ITEM is to be inserted at the Kth position
of LA. Let J is temp variable.
Algorithm’s Statements
Step 1. Set J := N
Step 2. Set N := N + 1
Data Structure & Algorithms
9
Insertion in Array (Cont…)
Repeat steps 3 to 5
Step 3. while J >= K
Step 4. Set LA[J+1] = LA[J]
Step 5. Set J = J-1
Step 6. Set LA[K] = ITEM
Step 7. Exit
Class Task
Design algorithms for the following
Insertion of item at the beginning of the Linear Array
Insertion of item at the end of Linear Array
Data Structure & Algorithms
10
End of Chapter
Homework
Design algorithms for Delete and Update
You can design many algorithms with Array
For example,
Sorting algorithms etc.
Simple algorithms with different requirements or conditions
Etc...
You may have quiz next week
Data Structure & Algorithms
11
