Data Structures
Arrays
Arrays
Arrays are linear and the simplest form of data structures.
They contain finite number of elements of similar data types. Each data
element/ value of an array is referenced by its subscript/ index value. An
index value is a number n which
denotes the respective position in the list from the beginning.
The first element has an index value 0. Index value indicates
thathow many elements do we need to shift
Linear Data structures:
In linear data structures,
the elements of are arranged in
the form of a sequence.
Data can be presented in two ways :
Using linear structures like arrays.
Using elements stored at various locations but referenced in
a linear/ sequential fashion.
Linear arrays:
Linear arrays generally have a finite number of elements of
same data type (homogeneous ).
The elements are stored in a
succession
Elements are referenced by their
respective position from the beginning of the list.
The fixed number of elements that an array can store is called the length of the array.
Conceptually, every array has its own index set. This index
set defines the least and maximum integer value that an index can have. The
lowermost value is called the lowerbound(L) whereas the highest value is called
the upper bound(U) of the array index. The length of the array can be found
using :
U-L+1
In C++ the lowerbound is 0. The elements of an array AR of size n are referred to as :
AR[0}, AR[1], AR[2],
……AR[N-1]
The highest index value of array of size n is n-1 whereas the
lowest value is zero.
Representation of a linear array in the memory:-
As studied in class XI also, we will discuss how array
elements are stored in the memory. All the elements of an array are store in a
continuous succession one after another in thememory.
An array AR of length 5 having size of each element as 1 byte is store in a succession in the memory. The computer does not store address of all the elements in the array. Rather, it stores the address of the first element called as the Base Address whilethe rest of the elements are identified as per their index value. The index value tells the number of elements preceded by the element whose address we wish to refer to.
Address of element with index value m can be calculated as :
Address of AR[i]= Base Address + size of individual element X m
Try out the following code :
#include<iostream.h>
void main()
{ intar[10]={2,3,4,5};
for(int i=0;i<10;i++)
cout<< i+1<<” element : “<<ar{i];
}
Following are some very common operations with arrays :
1. Insertion
2. Deletion
3. Searching
4. Sorting
5. Merging
Insertion in an array
Consider the following example :
#include<iostream.h>
void main()
{
intar[10]={ 12,13,14,15};
cout<<ar[0];
cout<<a[1];
}
Output :
1213
In the example shown above only first four index positions of array are assigned VALUES WHILE REMAINING six places are initialized with junk values .some more values can be added either at the beginning , end or any other place in between the array.
Inserting an element at the end of the array is simply done by adding a new at the next index value while inserting an element in the between or in the beginning requires shifting of trailing array elements carefully provided the array has enough memory allocated to it.
Let us assume an array of size 10 having 8 values in it
[0]
|
[1]
|
[2]
|
[3]
|
[4]
|
[5]
|
[6]
|
[7]
|
[8]
|
[9]
|
2
|
4
|
8
|
9
|
10
|
12
|
15
|
20
|
,
|
In case a value 6 is
to be inserted at index value 2 then it is required to shift all the values
from index value 2 to one position higher.
[0]
|
[1]
|
[2]
|
[3]
|
[4]
|
[5]
|
[6]
|
[7]
|
[8]
|
[9]
|
2
|
4
|
8
|
8
|
9
|
10
|
12
|
15
|
20
|
Value 6 will
overwrite the previous value
|
[0]
|
[1]
|
[2]
|
[3]
|
[4]
|
[5]
|
[6]
|
[7]
|
[8]
|
[9]
|
2
|
4
|
6
|
8
|
9
|
10
|
12
|
15
|
20
|
Value at index 2 is overwritten by the new value to be
inserted.
Algorithm for inserting an element in an array :
K is the position at which element M is to be inserted in
array A having N number of elements.
1. Start
2. Initialize
the variable ctr to the n.
3. A[N+1]=A[N];
4. N=N-1;
5. If N>=K
go to step 3 else goto step 6.
6. A[K]=M;
7. Reset the
number of elements as N+1;
8. Stop
Deleting a value from array.
Element at position K in array A having N number of elements
is to be deleted
Algorithm
1. START
2. Declare a
variable M to store the value of element to be deleted.
3. M=A[K];
4. Declare
counter variable CTR.
5. CTR=K;
6. A[CTR]=A[CTR+1];
7. CTR=CTR+1;
8. If CTR<N
go to step 5 else goto step 8
9. Reset the
number of elements as N=N-1;
10. STOP
ARRAY TRAVERSAL
Traversing an array is reading every element of the array one
by one till all the elements are read in a sequential manner.
Algorithm to traverse an array AR having Nelements .
1. START
2. Declare a
counter variable CTR.
3. Declare a
variable NUM to display the value array.
4. CTR=0.
5. NUM=AR[CTR]
6. Display
NUM.
7. CTR=CTR+1
8. If CTR<N
goto step 4
9. STOP
Searching :
Basically there are two types of searching algorithms :
Linear search
Binary search
Linear search involves comparing each element one by one from
the beginning of the arrayi.e from index value zero till the end of the array
every element is compared with the value to be searched till either the end or
we get the value.
Following is the algorithm for searching an element in an
array of size n.
Algorithm for linear search :
1. START
2. Declare an
counter variable CTR.
3. Declare a
variable NUM to be searched.
4. CTR=0
5. If( NUM=AR[CTR])
6. Display the
position at which element is found and goto step 9.
7. CTR=CTR+1
8. If CTR<N
goto step 4
9. STOP
Program to search for a number in a list of integers
#include<iostream.h>
intlsearch ( intar[10], int size, intnum)
{
for(int i=0;i<size;i++)
{ if(ar[i]==num)
return i;
else
return -1;
}
}
void main()
{int list[20], s,n, number,i;
cout<<” \n enter the number of elements
in the list(from 1 to 20) : “;
cin>>n;
if((n>0)&&n<20))
{for(i=0;i<n;i++)
cin>>list[i};
cin>>list[i};
cout<< “enter the number to be searched
in the list : ” ;
cin>>number;
if(lsearch(list, n, number)==-1)
cout<<endl<< number <<” not
found in the list” ;
else
cout<<endl<<number << “
found at ”<<lsearch(list, s, number)+1 <<“ position”;
}
else
cout<<”\n enter a valid list size “;
}
Sorting techniques
Sorting is arranging the data elements in a particular order.
The values in an array or list can either be arranged in ascending or
descending order.
Consider following list of integers as the marks obtained by
7 students in a test:
3, 12, 6, 8, 5, 9,
15
After sorting the list elements appear as :
3, 5, 6, 8, 9, 12, 15
we may easily find the highest marks and the range of marks
in the above list. There are a number of ways to sort a given list of elements.
Various algorithms have been devised to sort list of elements .each sorting
technique has its own effective approach depending on situation.
We will be studying following sorting algorithms:
1. Bubble sort
2. Selection
sort
3. Insertion
sort.
Bubble sort
Bubble sort involves comparing every two consecutive elements
and the values are swapped if they are not in proper order.
FOR EXAMPLE: Consider the following unsorted array elements:
The comparison begins from the first position of the list and
the elements are interchanged if theyare not in sorted order. This is carried
on for every two adjacent values till the end of the list.
PASS
|
23, 12,
34, 5, 6,
20
|
|
PASS1
|
Before :23, 12, 34, 5,
6, 20
After :12, 23, 34, 5, 6,
20
|
Element at
index 0 is compared with element at index 1. 23 AND 12 ARE COMPARED. Since 12
is less than 23 therefore both of them are swapped
|
Before :12,23, 34, 5, 6,
20
After : 12,23, 34, 5, 6,
20
|
Now, element
at index 1 is compared with element at index 2.
Since 23 is
less than 34 therefore no swapping takes place.
|
|
Before :12, 23,34, 5, 6,
20
After :12,23,5,34, 6, 20
|
Element at
next index value i.e. 2 is compared with element at index 3.
It may be
observed that 5 is less than 34 therefore
both these values are swapped
|
|
Before :12, 23, 5, 34, 6, 20
After : 12, 23, 5,
6,34, 20
|
Element at
index 3 is compared with element at index 4.
As 34 is
larger than 6 so again swapping takes place and 6 is placed before 34.
|
|
Before :12, 23, 5, 6,34, 20
After : 12, 23, 5, 6,20,
34
|
At last
element at index 4 is compared with element at index 5.
In this case
20 is less than 34 therefore swapping of 20 and 34 takes place.
|
|
After first pass, last element of the list is in sorted
order. For example if we have to arrange the list in ascending order then the
largest element gets shifted to the last. Now the above procedure is repeated
and in second pass second last position is having the second largest value.
Successive comparisons are carried out for n-1 times for a list having n
elements.
It is clear that largest element is placed at the end
therefore in second pass the comparisons are done till second last element, in
third pass the elements are compared till third last element as last two
elements are already sorted. So after every pass the size of list reduces by 1.
So, the list would appear as follows after 5 passes:
After pass 2: 12,
5,6,20,23,34
After pass 3 :5,6,12,20,23,34
After pass 4:5,6,12 , 20,23,34
After pass 5 :5,6,12,20,23,34
After every pass the heaviest element moves to the end.
Algorithm to sort a given array AR of n elements.
1. DECLARE TWO
VARIABLES P AND Q
2. INITIALIZE P=0
3. INTIALIZE Q=0
4. If AR[Q]>AR[Q+1]
THEN INTERCHANGE VALUE OF AR[Q] WITH AR[Q+1]
5. SET Q=Q+1
6. IF (Q<N-1)
GOTO STEP 4
7. SET P = P
+1
8. IF P<N
GOTO STEP 3
9. STOP
Selection Sort
As per this type of sorting algorithm the smallest element is
searched and then placed at the first position. After this next smallest
element is searched in the list and then exchanged with the element at the
second position and so on.
Let us consider an array with following values:
23, 12,
34, 5, 6,
20
Smallest element is selected
23
|
12
|
34
|
5
|
6
|
20
|
and is exchanged with the element at first position.
5
|
12
|
34
|
23
|
6
|
20
|
Again second smallest
element is selected
5
|
12
|
34
|
23
|
6
|
20
|
and is exchanged with element at second position
5
|
6
|
34
|
23
|
12
|
20
|
Next element at third smallest element is selected
5
|
6
|
34
|
23
|
12
|
20
|
And isreplaced with
third smallest element
5
|
6
|
12
|
23
|
34
|
20
|
Next fourth smallest element is selected
5
|
6
|
12
|
23
|
34
|
20
|
This fourth smallest element is replaces the
element at fourth position
5
|
6
|
12
|
20
|
34
|
23
|
At last the fifth element is
selected
5
|
6
|
12
|
20
|
34
|
23
|
And is replaced with element at
fifth position
5
|
6
|
12
|
20
|
23
|
34
|
After five passes this array of six elements
is sorted
An array of N elements is sorted
with N-1 passes and the last unsorted element is automatically in sorted order.
Algorithm of Selection Sort
1. Declare a
variable MIN to store minimum value.
2. Declare
variable POS to store the p
3. Declare a
temporary variable TEMP.
4. Declare
counter variables S and P .
5. Set S=0
6. MIN=AR[S]
7. Set P=S+1
8. If
AR[P]<MIN
SET MIN=AR[P]
9. P=P+1
10. IF
(P<N-1) GOTO STEP 8
11. IF
MIN=AR[S] GOTO STEP
12. TEMP=AR[S]
13. AR[S]=MIN
14. AR[POS]=TEMP
15. S=S+1
16. IF S<N
GOTO STEP 6
17. STOP
INSERTION SORT
It uses the logic of reading value one by one from the array,
comparing it with all the elements from the beginning of the array and inserting
it at the place wherever it finds a value greater than the value being
compared.
For example consider the same array list discussed for bubble
sort and selection sort
23, 12,
34, 5, 6,
20
Firstelement is considered to be sorted.
23
|
12
|
34
|
5
|
6
|
20
|
Now, element at second positionis compared with the first
element. If value at first position is greater than the value at second
position then the element at first element position is shifted and value of
second element is place at first position. In this case 12 is less than 23 so,
23 is shifted one position to the right and value 12 is placed at first
position
23
|
12
|
34
|
5
|
6
|
20
|
12
|
23
|
34
|
5
|
6
|
20
|
Similarly now the value at third position is first compared
with value at first position , if value of third position element is less than
value at first position then elements are shiftedone position to the right
until third position otherwise third element is compared with element at second
place and if required it is inserted at second position. In this case, 34 is
first compared with 12 .Since 12 isless than 34 therefore no shifting takes
place.
12
|
23
|
34
|
5
|
6
|
20
|
12
|
23
|
34
|
5
|
6
|
20
|
Now, the value of fourth element is compared with the first
element. As ‘12’ is greater than ‘5’ so5 is inserted at first position and
element at first and second position are shift one place to the right i.e. down
in the list.
12
|
23
|
34
|
5
|
6
|
20
|
5
|
12
|
23
|
34
|
6
|
20
|
Program of sorting a
listof n numbers :
#include<iostream.h>
voidinsertsort( intar[]))
{ intj,k,tmp,min;
for(j=1; j<n-1;j++)
{ min=ar[j];
for( k=0;k<j;k++)
{ if(ar[k]>ar[j])
{ tmp=ar[j];
for(pos=j;pos>k;pos++) //
loop for shifting the elements
ar[pos]=ar[pos-1];
}
}
}
}
void main()
{intnum[20];
cout<<”\n enter the number of elements in the
array (max 20) : ” ;
cin>>n;
if(n<=20)
{ cout<<”\n enter the elements of the
array ”;
for(i=0;i<n;i++)
cin>>num[i];
insert(num);
cout<<”\n the sorted list is : “;
for(i=0;i<n; i++)
cout<<”\n”<<num[i];
}
No comments:
Post a Comment