Abstract Data Type (ADT) is a conceptual model.ppt

An Abstract Data Type (ADT) is a conceptual model that defines a set of operations and behaviors for a data structure, without specifying ...

1. Data Structures & Algorithms
Arrays ADT

2. Data Structures & Algorithms
Introduction
•Linear Vs Non-Liner DS
•Need Liner Relationship
–How
•Arrays, linked lists
•Operation on Liner DS
–Traversal
–Search
–Insertion
–Deletion
–Sorting
–Merging
•Now which liner structure to use?

3. Data Structures & Algorithms
Linear Arrays
•A liner array is a finite number N homogeneous data elements
–Elements are referenced respectively by an index set of N consecutive numbers
–Elements are stored respectively in successive memory locations
–Fixed number of elements
•Index always integer
•Length=UB-LB+1
•Notation A1 or A(1) or A[1]

4. Data Structures & Algorithms
Representation of Liner Array in Memory
•Computer need to keep track of only first element of array
–Base address
•Address for rest of the elements is calculated using formula
–LOC(array[K])=base(LA)+w(K-LB)
•W is number of words per memory cell of array
•Time to calculate LOC(array[K]) is same for all values of K
•Given a value of K we can access the contents without
scanning any other element of the array
•200+4(1965-1932)
2003 D
2004 D
2005 D
2006 D
2007 A
2008 A
2009 A
2010 A
2011 A
2012 D
2013 S
2014 S

5. Data Structures & Algorithms
Traversing Liner Arrays
Repeat for K=LB to UB
Apply PROCESS to Array[K]
[End of Loop]
Exit

6. Data Structures & Algorithms
Inserting Into Liner Array
Pakistan
India
Iran
China
Russia
Insert At End
Pakistan
India
Iran
China
Russia
Afghanistan
Insert At Middle
Pakistan
India
Iran
USA
China
Russia
Afghanistan
Same for Deletion

7. Data Structures & Algorithms
Sorting
BUBBLE(DATA,N)
1. Repeat Steps 2 and 3 for K=1 to N-1
2. Set PTR:=1
3. Repeat while PTR<=N-K
a) if DATA[PTR]>DATA[PTR+1] then:
Swap DATA[PTR] and DATA [PTR+1]
b) Set PTR:=PTR+1
4. Exit
Complexity of Bubble Sort?
Can you see any problem?
How to make bubble sort efficient?

8. Data Structures & Algorithms
Searching in Linear Arrays
•Linear Search
•Complexity of Search

9. Data Structures & Algorithms
Two Dimensional Arrays
•A two dimensional array m X n is a collection of m.n data elements such that each
element is specified by a pair of integers (j,k) called subscripts
–0<=j<=m and 0<=k<=n
Also called matrix or table

10. Data Structures & Algorithms
Two Dimensional Arrays in Memory
•Two ways to be represented in
memory
–Column by column  column
majored
–Row by row  row majored
(1,1)
(2,1) Column 1
(3,1)
(1,2)
(2,2) Column 2
(3,2)
(1,3)
(2,3) Column 3
(3,3)
(1,4)
(2,4) Column 4
(3,4)
(1,1)
(1,2) Row 1
(1,3)
(1,4)
(2,1)
(2,2) Row 2
(2,3)
(2,4)
(3,1)
(3,2) Row 3
(3,3)
(3,4)
Representation
depends upon the
Programming
language used

11. Data Structures & Algorithms
Address Calculation in 2D Array
•For column majored
–LOC(Array[j,k])=base(A)+W[M(K-1)+(j-1)]
•For row majored
–LOC(Array[j,k])=base(A)+W[N(j-1)+(k-1)]
A 2D Array of 25X4
W=4
Base(Array)=200
M=25,N=4
LOC(Array[12,3])=?
200+4[4(12-1)+(3-1)]=384

12. Data Structures & Algorithms
Problems with arrays
•Capacity can not be changed during program execution
–Memory wastage
–Out of range errors
•Arrays are not self contained objects
–No way to find last value stored