0% found this document useful (0 votes)

37 views36 pages

Data Structures: Hapter

Uploaded by

munshijubair7

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

37 views36 pages

Data Structures: Hapter

Uploaded by

munshijubair7

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

You are on page 1/ 36

Data Structures

Chapter 04
9/9/2024 Md. Golam Moazzam, Dept. of CSE, JU 1
Data Structures- Chapter 4
❑ Linear Array

– A linear array is a list of finite number N of homogeneous data

elements such that:
• The elements of the array are referenced respectively by an index
set consisting of N consecutive numbers.
• The elements of the array are stored respectively in successive
memory locations.

– The number N of elements is called the length or size of the array.

9/9/2024 Md. Golam Moazzam, Dept. of CSE, JU 2

Data Structures- Chapter 4
❑ Linear Array
– Three numbers define an array: Lower Bound, Upper Bound, and
Size.
• The lower bound is the smallest subscript you can use in the array
(usually 0).
• The upper bound is the largest subscript you can use in the array.
• The size / length of the array refers to the number of elements in the
array. It can be computed as
• Length= Upper bound - Lower bound + 1

– Let the array name be A. Then the elements of A are: a1, a2, ….., an.
– Or by the bracket notation: A[1], A[2], A[3],…………., A[n]
– The number k in A[k] is called a subscript and A[k] is called a
subscripted variable.
9/9/2024 Md. Golam Moazzam, Dept. of CSE, JU 3
Data Structures- Chapter 4
❑ Linear Array
Example:
– A linear array DATA consisting of six elements:

DATA
1 247 DATA [1] = 247
2 56 DATA [2] = 56
3 429 DATA [3] = 429
4 135 DATA [4] = 135
5 87 DATA [5] = 87
6 156 DATA [6] = 156

9/9/2024 Md. Golam Moazzam, Dept. of CSE, JU 4

Data Structures- Chapter 4
❑ Linear Array
Example:
– An automobile company uses an array AUTO to record the number of
auto mobile sold each year from 1932 through 1984.

– LB = 1932, UB = 1984

– AUTO[k] = Number of auto mobiles sold in the year k.

– Length = UB – LB+1 = 1984 – 1930+1 =55

9/9/2024 Md. Golam Moazzam, Dept. of CSE, JU 5

Data Structures- Chapter 4
❑ Operations on Linear Array

– Traversing: means to visit all the elements of the array in an

operation is called traversing.
– Insertion: means to put values into an array.
– Deletion / Remove: to delete a value from an array.
– Sorting: Re-arrangement of values in an array in a specific order
(Ascending / Descending) is called sorting.
– Searching: The process of finding the location of a particular
element in an array is called searching.
– There are two popular searching techniques/mechanisms: Linear
search and binary search.

9/9/2024 Md. Golam Moazzam, Dept. of CSE, JU 6

Data Structures- Chapter 4
❑ Representation of Linear Array in Memory
– Let LA be a linear array in the memory of the computer. The memory
of the computer is a sequence of addressed locations.
– The computer does not need to keep track of the address of every
element of LA, but needs to keep track only of the first element of LA,
denoted by
Base (LA) 1000 247
called the base address of LA. 1001 56
1002 429
– Using this address Base (LA), 1003 135
the computer calculates the address of 1004 87
1005 156
any element of LA by the following formula:

LOC(LA[k]) = Base(LA) + w(K – lower bound)

– Where w is the number of words per memory cell for the array LA
9/9/2024 Md. Golam Moazzam, Dept. of CSE, JU 7
Data Structures- Chapter 4
❑ Representation of Linear Array in Memory
Example: AUTO
An automobile company uses an array AUTO to record
200
the number of auto mobiles sold each year from 1932
through 1984. Suppose AUTO appears in memory as 201
pictured in Fig. That is, 202
Base(AUTO) = 200, and w = 4 words per memory cell, 203
LB=1932, UB=1984. Then, 204

LOC(AUTO[1932]) = 200, LOC(AUTO[1933]) =204 205

LOC(AUTO[1934]) = 208

The address of the array element for the year K = 1965

can be obtained by using:

LOC(AUTO[1965]) = Base(AUTO) + w(1965 – LB)

=200+4(1965-1932) =332

9/9/2024 Md. Golam Moazzam, Dept. of CSE, JU 8

Data Structures- Chapter 4
❑ Solved Problems 4.1: Consider the linear arrays AAA(5:50), BBB(-5:10)
and CCC(18).
(a) Find the number of elements in each array.
(b) Suppose Base(AAA)=300 and w=4 words per memory cell for
AAA. Find the address of AAA[15], AAA[35] and AAA[55].

Solution:
(a) The number of elements is equal to the length; hence use the formula
Length = UB –LB+1
Accordingly, Length(AAA) = 50-5+1=46
Length(BBB) =10-(-5)+1=16
Length(CCC) = 18-1+1=18

9/9/2024 Md. Golam Moazzam, Dept. of CSE, JU 9

Solution:
(b) Use the formula, LOC(AAA[K]) = Base(AAA) + w(K –LB)
Hence, LOC (AAA[15])=300+4(15-5)=340
LOC(AAA[35])=300+4(35-5)=420
AAA[55] is not an element of AAA, since 55 exceeds UB=50

9/9/2024 Md. Golam Moazzam, Dept. of CSE, JU 10

Data Structures- Chapter 4
❑ Algorithm 4.1: (Traversing a Linear Array)
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.

1. [Initialize counter.] Set K=LB.

2. Repeat Steps 3 and 4 while K≤UB.
3. [Visit element.] Apply PROCESS to LA[K].
4. [Increase counter.] Set k=K+1.
[End of Step 2 loop.]
5. Exit.

9/9/2024 Md. Golam Moazzam, Dept. of CSE, JU 11

1. Repeat for K=LB to UB

Apply PROCESS to LA[K].
[End of loop].
2. Exit.

9/9/2024 Md. Golam Moazzam, Dept. of CSE, JU 12

Data Structures- Chapter 4
❑ Insertion into Arrays
Inserting an element somewhere in the middle of the array require that each
subsequent element be moved downward to new locations to accommodate the new
element and keep the order of the other elements.
Algorithm 4.2: (Inserting into a linear array)
Here LA is linear array with N elements and K is a positive integer such
that K<=N. This algorithm inserts an element ITEM into the K-th position
in LA.
Step 1. Set J:=N
Step 2. Repeat Steps 3 and 4 while J>=K
Step 3. Set LA [J+1]: =LA [J]
Step 4. Set J:=J-1
[End of step 2 loop]
Step 5. Set LA [K]: =ITEM
Step 6. Set N:=N+1
Step 7. Exit
9/9/2024 Md. Golam Moazzam, Dept. of CSE, JU 13
Data Structures- Chapter 4
❑ Deletion of elements from linear arrays
Deleting an element somewhere in the middle of the array requires that
each subsequent element be moved one location upward in order to “fill
up” the array.

Algorithm 4.3: (Deleting from a linear array)

Here LA is a linear array with N elements and K is a positive integer such
that K≤N. This algorithm deletes the K-th element from LA.
Step 1. Set ITEM: = LA [K]
Step 2. Repeat for J=K to N-1
Set LA [J]: =LA [J+1]
[End of loop]
Step 3. Set N:=N-1
Step 4. Exit
9/9/2024 Md. Golam Moazzam, Dept. of CSE, JU 14
Data Structures- Chapter 4
❑ Bubble Sort
Suppose the following numbers are stored in an array A:
A: 32, 51, 27, 85, 66, 23, 13, 57
Apply the bubble sort to the array A. Show each pass separately.

Pass 1: (a) Compare A1 and A2. Since 32< 51, the list is not altered.
A: 32, 51, 27, 85, 66, 23, 13, 57
(b) Compare A2 and A3. Since 51>27, interchange 51 and 27.
A: 32, 27, 51, 85, 66, 23, 13, 57
(c) Compare A3 and A4. Since 51<85, the list is not altered.
A: 32, 27, 51, 85, 66, 23, 13, 57
(d) Compare A4 and A5. Since 85>66, interchange 85 and 66.
A: 32, 27, 51, 66, 85, 23, 13, 57