Data Structures

Data Structures 


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};

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];

}