## Page 1

1Module I

Practical No: 1

Aim: Implement program for Bubble sort.

Objective: To understand working of bubble sort algorithm and sort

array elements if they are not in the right order.

Theory:

1. Bubble sort is a sorting technique that compares two adjacent array

elements and swaps them if they are not in the intended order.

2. It works on the principle of repeatedly swapping adjacent elements

in case they are not in the right order. If the element at the lower

index is greater than the element at the higher index, the two

elements are interchanged so that the element is placed before the

bigger one. This process will continue till the list of unsorted

elements exhausts.

3. In simpler terms, if the input is to be sorted in ascending order, the

bubble sort will first compare the first two elements in the array. In

case the second one is smaller than the first, it will swap the two,

and move on to the next element, and so on.

4. Note that at the end of the first pa ss, the largest element in the list

will be placed at its proper position.

Example:

Let us consider an array A[] that has the following elements:

A[] = {30, 52, 29, 87, 63, 27, 19, 54}

Pass 1 :-

(a) Compare 30 and 52. Since 30 < 52, no swapping is done.

(b) Compare 52 and 29. Since 52 > 29, swapping is done.

30, 29, 52, 87, 63, 27, 19, 54

(c) Compare 52 and 87. Since 52 < 87, no swapping is done.

(d) Compare 87 and 63. Since 87 > 63, swapping is done.

30, 29, 52, 63, 87, 27, 19, 54

(e) Compare 87 and 27. Since 87 > 27, swapping is done.

30, 29, 52, 63, 27, 87, 19, 54

(f) Compare 87 and 19. Since 87 > 19, swapping is done.

30, 29, 52, 63, 27, 19, 87, 54

(g) Compare 87 and 54. Since 87 > 54, swapping is done.

30, 29, 52, 63, 27, 19, 54, 87 munotes.in

## Page 2

2Observe that after the end of the first pass, the largest element is

placed at the highest index of the array. All the other elements are still

unsorted.

Pass 2 :-

(a) Compare 30 and 29. Since 30 > 29, swapping is done.

29, 30, 52, 63, 27, 19, 54, 87

(b) Compare 30 and 52. Since 30 < 52, no swapping is done.

(c) Compare 52 and 63. Since 52 < 63, no swapping is done.

(d) Compare 63 and 27. Since 63 > 27, swapping is done.

29, 30, 52, 27, 63, 19, 54, 87

(e) Compare 63 and 19. Since 63 > 19, swapping is done.

29, 30, 52, 27, 19, 63, 54, 87

(f) Compare 63 and 54. Since 63 > 54, swapping is done.

29, 30, 52, 27, 19, 54, 63, 87

Observe that after the end of the second pass, the second largest

element is placed at the second highest index of the array. All the other

elements are still unsorted.

Pass 3 :-

(a) Compare 29 and 30. Since 29 < 30, no swapping is done.

(b) Compare 30 and 52. Since 30 < 52, no swapping is done.

(c) Compare 52 and 27. Since 52 > 27, swapping is done.

29, 30, 27, 52, 19, 54, 63, 87

(d) Compare 52 and 19. Since 52 > 19, swapping is done.

29, 30, 27, 19, 52, 54, 63, 87

(e) Compare 52 and 54. Since 52 < 54, no swapping is done.

Observe that after the end of the third pass, the third largest element is

placed at the third highest index of the array. All the other elements are

still unsorted.

Pass 4 :-

(a) Compare 29 and 30. Since 29 < 30, no swapping is done.

(b) Compare 30 and 27. Since 30 > 27, swapping is done.

29, 27, 30, 19, 52, 54, 63, 87

(c) Compare 30 and 19. Since 30 > 19, swapping is done.

29, 27, 19, 30, 52, 54, 63, 87

(d) Compare 30 and 52. Since 30 < 52, no swapping is done.

Observe that after the end of the fourth pass, the fourth largest

element is placed at the fourth highest index of the array. All the other

elements are still unsorted.

munotes.in

## Page 3

3Pass 5 :-

(a) Compare 29 and 27. Since 29 > 27, swapping is done.

27, 29, 19, 30, 52, 54, 63, 87

(b) Compare 29 and 19. Since 29 > 19, swapping is done.

27, 19, 29, 30, 52, 54, 63, 87

(c) Compare 29 and 30. Since 29 < 30, no swapping is done.

Observe that after the end of the fifth pass, the fifth largest element

is placed at the fifth highest index of the array. All the other elements are

still unsorted.

Pass 6 :-

(a) Compare 27 and 19. Since 27 > 19, swapping is done.

19, 27, 29, 30, 52, 54, 63, 87

(b) Compare 27 and 29. Since 27 < 29, no swapping is done.

Observe that after the end of the sixth pass, the sixth largest

element is placed at the sixth largest index of the array.

All the array elements are present in sorted order.

Algorithm:

BUBBLE_SORT(A, N)

Step 1: Repeat Step 2 For I= 0 to N-1 // to keep track of the number of

iterations

Step 2: Repeat For J= 0 to N-I // to compare the elements within the

particular iteration

Step 3: IF A[J] > A[J+1] // swap if any element is greater than its

adjacent element

SWAP A[J] and A[J+1]

[END OF INNER LOOP]

[END OF OUTER LOOP]

Step 4: EXIT

Program:

#include

#include

int main()

{

int i, n, temp, j, arr[10];

printf("Enter the maximum elements you want to store : ");

scanf("%d", &n);

printf("Enter the elements \n");

for(i=0;i {

scanf("%d", & arr[i]);

} munotes.in

## Page 4

4 for(i=0;i {

for(j=0;j {

if(arr[j]>arr[j+1])

{

temp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = temp;

}

}

}

printf("The array sorted in ascending order is :\n");

for(i=0;i printf("%d\t", arr[i]);

getch();

return 0;

}

Questions:

1. Assume that we use Bubble Sort to sort n distinct elements in ascending

order. When does the best case of Bubble Sort occur?

A. When elements are sorted in descending order

B. When elements are sorted in ascending order

C. When elements are not sorted by any order

D. There is no best case for Bubble Sort. It always takes O(n*n) time

2.The number of swapping needed to sort the numbers 8, 22, 7, 9, 31, 5,

13 in ascending order, using bubble sort is

A. 11

B. 12

C. 13

D. 10

3. When will bubble sort take worst-case time complexity?

A. Only the first half of the array is sorted.

B. Only the second half of the array is sorted.

C. The array is sorted in descending order.

D. The array is sorted in ascending order.

4. Sort given array elements using Bubble Sort.

9 0 , 2 5 , 3 0 , 7 8 , 8 6 , 6 0 , 4 0 , 8 , 5 5

munotes.in

## Page 5

5Practical No: 2

Aim: Implement program for Insertion sort.

Objective: To understand steps for sorting data using insertion sort

algorithm. To implement program fo r sorting array elements using

insertion sort.

Theory:

Insertion sort is a sorting algorithm that places an unsorted

element at its suitable place in each iteration. The array is virtually split

into a sorted and an unsorted part. Elements from the unsorted part are

picked and placed at the correct position in the sorted part. For example,

the lower part of an array is maintained to be sort ed. An element which is

to be inserted in this sorted list, has to find its appropriate place and then it

has to be inserted there. He nce the name, insertion sort.

Example:

Another Example:

12, 11, 13, 5, 6

Let us loop for i = 1 (second element of the array) to 4 (last element of the

array)

Step 1: Since 11 is smaller than 12, move 12 and insert 11 before 12

11, 12, 13, 5, 6

Step 2: 13 will remain at its position as all elements in A[0..i-1] are

smaller than 13

11, 12, 13, 5, 6

Step 3: 5 will move to the beginning and all other elements from 11 to 13

will move one position ahead of their current position.

5, 11, 12, 13, 6 munotes.in

## Page 6

6Step 4: 6 will move to position after 5, and elements from 11 to 13 will

move one position ahead of their current position.

5, 6, 11, 12, 13

Algorithm:

INSERTION-SORT (ARR, N)

Step 1: Repeat Steps 2 to 5 for K = 1 to N-1

Step 2: SET TEMP = ARR[K]

Step 3: SET J = K - 1

Step 4: Repeat while TEMP <=ARR[J]

SET ARR[J + 1] = ARR[J]

SET J = J - 1

[END OF INNER LOOP]

Step 5: SET ARR[J + 1] = TEMP

[END OF LOOP]

Step 6: EXIT

Program:

#include

#include

void main ()

{

int i, j, k,temp;

int a[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};

printf("\nprinting sorted elements...\n");

for(k=1; k<10; k++)

{

temp = a[k];

j= k-1;

while(j>=0 && temp <= a[j])

{

a[j+1] = a[j];

j = j-1;

}

a[j+1] = temp;

}

for(i=0;i<10;i++)

{

printf("\n%d\n",a[i]);

}

getch();

}

munotes.in

## Page 7

7Questions:

1. What will be the number of passes to sort the elements using insertion

sort?

14, 12,16, 6, 3, 10

A. 6

B. 5

C. 7

D. 1

2. For the following question, how will the array elements look like after

second pass?

34, 8, 64, 51, 32, 21

A. 8, 21, 32, 34, 51, 64

B. 8, 32, 34, 51, 64, 21

C. 8, 34, 51, 64, 32, 21

D. 8, 34, 64, 51, 32, 21

3. In C, what are the basic loops required to perform an insertion sort?

A. do- while

B. if else

C. for and while

D. for and if

4.Consider an array of elements arr[5]= {5,4,3,2,1} , what are the steps of

insertions done while doing insertion sort in the array.

A. 5 4 3 1 2, 5 4 1 2 3, 5 1 2 3 4, 1 2 3 4 5

B. 4 5 3 2 1, 3 4 5 2 1, 2 3 4 5 1, 1 2 3 4 5

C. 4 3 2 1 5, 3 2 1 5 4, 2 1 5 4 3, 1 5 4 3 2

D. 4 5 3 2 1, 2 3 4 5 1, 3 4 5 2 1, 1 2 3 4 5

5. Which of the following real time examples is based on insertion sort?

A. Arranging a pack of playing cards

B. Database scenarios and distributes scenarios

C. Arranging books on a library shelf

D. Real-time systems

Practical No: 3

Aim: Implement program for Selection Sort.

Objective: Develop a program for sorting array elements using selection

sort.

Theory:

1. Selection sorting is conceptually the simplest sorting algorithm. This

algorithm first finds the smallest element in the array and exchanges it munotes.in

## Page 8

8with the element in the first position, then finds the second smallest

element and exchange it with the element in the second position, and

continues in this way until the entire array is sorted.

2. The idea behind this algorithm is that first divide the array into two

parts: sorted and unsorted. The left part is sorted subarray and the right

part is unsorted subarray. Initially, sorted subarray is empty and unsorted

array is the complete given array.Then perform the steps given below until

the unsorted subarray becomes empty:

i. Pick the minimum element from the unsorted subarray.

ii. Swap it with the leftmost element and that element becomes a part

of sorted subarray and will not be a part of unsorted subarray.

iii. This process continues moving unsorted array boundary by one

element to the right.

Example:

Consider the following array with 6 elements. Sort the elements of

the array by using selection sort.

A = {10, 2, 3, 90, 43, 56}

Pass A[0] A[1] A[2] A[3] A[4] A[5]

1 2 10 3 90 43 56

2 2 3 10 90 43 56

3 2 3 10 90 43 56

4 2 3 10 43 90 56

5 2 3 10 43 56 90

Algorithm:

SELECTION SORT(ARR, N)

Step 1: Repeat Steps 2 and 3 for K = 1 to N-1

Step 2: CALL SMALLEST(ARR, K, N, POS)

Step 3: SWAP A[K] with ARR[POS]

[END OF LOOP]

Step 4: EXIT

munotes.in

## Page 9

9SMALLEST (ARR, K, N, POS)

Step 1: [INITIALIZE] SET SMALL = ARR[K]

Step 2: [INITIALIZE] SET POS = K

Step 3: Repeat for J = K+1 to N -1

IF SMALL > ARR[J]

SET SMALL = ARR[J]

SET POS = J

[END OF IF]

[END OF LOOP]

Step 4: RETURN POS

Program:

#include

#include

int smallest(int[],int,int);

void main ()

{

int a[10] = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};

int i,j,k,pos,temp;

for(i=0;i<10;i++)

{

pos = smallest(a,10,i);

temp = a[i];

a[i]=a[pos];

a[pos] = temp;

}

printf("\nprinting sorted elements...\n");

for(i=0;i<10;i++)

{

printf("%d\n",a[i]);

}

}

int smallest(int a[], int n, int i)

{

int small,pos,j;

small = a[i];

pos = i;

for(j=i+1;j<10;j++)

{

if(a[j] {

small = a[j]; munotes.in

## Page 10

10 pos=j;

}

}

getch();

return pos;

}

Questions:

1. The given array is arr = {3,4,5,2,1}. The number of iterations in bubble

sort and selection sort respectively are __________.

A. 5 and 4

B. 4 and 5

C. 2 and 4

D. 2 and 5

2.How many comparisons are needed to sort an array of length 5 if a

straight selection sort is used and array is already in the opposite order?

A. 1

B. 10

C. 5

D. 20

3. Which operation does the Selection sort use to move numbers from the

unsorted section to the sorted section of the list?

A. Swap

B. Sort

C. Insert

D. Merge

4. For each i from 1 to n-1, there are ____________ exchanges for

selection sort.

A. 1

B. n

C. n-1

D. n-3

5. Selection sort the following array. Show the array after each swap that

takes place.

80, 65, 46, 32, 95, 30

munotes.in

## Page 11

11Practical No: 4

Aim: Implement program for Shell sort.

Objective: To understand working of Shell Sort algorithm for sorting

array elements and implement program for the same.

Theory:

Shell sort algorithm is invented by Donald shell. Shell sort is a

highly efficient sorting algorithm. It is a variation of Insertion Sort. In

insertion sort, we move elements only one position ahead. When an

element has to be moved far ahead, many movements are involved. This

algorithm avoids large shifts. The idea of ShellSort is to allow exchange

of far items. It first sorts elements that are far apart from each other and

successively reduces the interval between the elements to be sorted. We

keep reducing the value of interval until it becomes 1.

Example:

Suppose, we need to sort the following array.

9 8 3 7 5 6 4 1

Step 1: In the first step, if the array size is N = 8 then, the elements lying

at the interval of N/2 = 4 are compared and swapped if they are not in

order.

a. The 0th element is compared with the 4th element.

b. If the 0th element is greater than the 4th one then, the 4th element

is first stored in temp variable and the 0th element (ie. greater

element) is stored in the 4th position and the element stored in

temp is stored in the 0th position.

This process goes on for all the remaining elements at N/2 interval i.e., 4 5 8 3 7 9 6 4 1

5 6 3 7 9 8 4 1

5 6 3 7 9 8 4 1

5 6 3 1 9 8 4 7 munotes.in

## Page 12

12In the second step, an interval of N/4 = 8/4 = 2 is taken and again the

elements lying at these intervals are sorted.

Rearrange the elements at n/4 interval 5 6 3 1 9 8 4 7

3 6 5 1 9 8 4 7

All the elements in the array lying at the current interval are compared.

3 1 5 6 9 8 4 7

3 1 5 6 9 8 4 7

The elements at 4th and 2nd position are compared. The elements at 2nd

and 0th position is also compared. All the elements in the array lying at

the current interval are compared. The same process goes on for

remaining elements.

3 6 5 1 9 8 4 7

3 1 5 6 9 8 4 7

3 1 4 6 5 8 9 7

3 1 4 6 5 8 9 7

3 1 4 6 5 7 9 8

Finally, when the interval is N/8 = 8/8 =1 then the array elements lying at

the interval of 1 are sorted. The array is now completely sorted. 3 1 4 6 5 7 9 8 1 3 4 6 5 7 9 8 1 3 4 6 5 7 9 8 1 3 4 6 5 7 9 8 1 3 4 5 6 7 9 8 1 3 4 5 6 7 9 8 1 3 4 5 6 7 9 8 1 3 4 5 6 7 9 8 1 3 4 5 6 7 8 9

Algorithm:

Shell_Sort(Arr, n)

Step 1: SET FLAG = 1, GAP_SIZE = N

Step 2: Repeat Steps 3 to 6 while FLAG = 1 OR GAP_SIZE > 1

Step 3: SET FLAG = 0

Step 4: SET GAP_SIZE = (GAP_SIZE + 1) / 2

Step 5: Repeat Step 6 for I = 0 to I < (N -GAP_SIZE)

munotes.in

## Page 13

13Step 6: IF Arr[I + GAP_SIZE] > Arr[I]

SWAP Arr[I + GAP_SIZE], Arr[I]

SET FLAG = 0

Step 7: END

Program:

#include

#include

void shellsort(int arr[], int num)

{

int i, j, k, tmp;

for (i = num / 2; i > 0; i = i / 2)

{

for (j = i; j < num; j++)

{

for(k = j - i; k >= 0; k = k - i)

{

if (arr[k+i] >= arr[k])

break;

else

{

tmp = arr[k];

arr[k] = arr[k+i];

arr[k+i] = tmp;

}

}

}

}

}

int main()

{

int arr[30];

int k, num;

printf("Enter total no. of elements : ");

scanf("%d", &num);

printf("\nEnter %d numbers: ", num);

for (k = 0 ; k < num; k++)

{

scanf("%d", &arr[k]);

}

shellsort(arr, num);

printf("\n Sorted array is: ");

for (k = 0; k < num; k++) munotes.in

## Page 14

14printf("%d ", arr[k]);

return 0;

}

Questions:

1.Which of the following sorting algorithms is closely related to shell sort?

A. Selection sort

B. Merge sort

C. Insertion sort

D. Bucket sort

2. Why is Shell sort called as a generalization of Insertion sort?

A. Shell sort allows an exchange of far items whereas insertion sort

moves elements by one position

B. Improved lower bound analysis

C. Insertion is more efficient than any other algorithms

D. Shell sort performs internal sorting

3. Who invented the shell sort algorithm?

A. John Von Neumann

B. Donald Shell

C. Tony Hoare

D. Alan Shell

4. Shell sort is applied on the elements 27 59 49 37 15 90 81 39 and the

chosen decreasing sequence of increments is (5, 3, 1). The result after the

first iteration will be ___________.

A. 27 59 49 37 15 90 81 39

B. 27 59 37 49 15 90 81 39

C. 27 59 39 37 15 90 81 49

D. 15 59 49 37 27 90 81 39

5. What is the best-case complexity for shell sort?

A. O(1)

B. O(n)

C. O(logn)

D. O(nlogn)

6. Given an array of the following elements

81,94,11,96,12,35,17,95,28,58,41,75,15.

What will be the sorted order after shell sort?

munotes.in

## Page 15

15Practical No: 5

Aim: Implement program for Radix sort.

Objective: To understand steps for sorting elements using Radix

sort.Develop a program for sorting array elements using Radix sort.

Theory:

Radix sort is one of the sorting algorithms used to sort a list of

integer numbers in order. In radix sort algorithm, a list of integer numbers

will be sorted based on the digits of individual numbers. Sorting is

performed from least significant digit to the most significant digit.

Suppose, we have an array of 8 elements. First, we will sort elements

based on the value of the unit place. Then, we will sort elements based on

the value of the tenth place. This pro cess goes on until the last significant

place.

Radix sort algorithm requires the number of passes which are equal

to the number of digits present in the largest number among the list of

numbers. For example, if the largest number is a 3 digit number then that

list is sorted with 3 passes.

Step by Step Process:

The Radix sort algorithm is performed using the following steps.

Step 1 - Define 10 queues each representing a bucket for each digit from 0

to 9.

Step 2 - C o n s i d e r t h e l e a s t s i g n i f i c a n t d i g i t o f e a c h n u m b e r i n t h e l i s t

which is to be sorted.

Step 3 - Insert each number into their respective queue based on the least

significant digit.

Step 4 - Group all the numbers from queue 0 to queue 9 in the order they

have inserted into their respective queues.

Step 5 - Repeat from step 3 based on the next least significant digit.

Step 6 - Repeat from step 2 until all the numbers are grouped based on the

most significant digit.

Example:

Sort the numbers given below using radix sort.

345, 654, 924, 123, 567, 472, 555, 808, 911 munotes.in

## Page 16

16In the first pass, the numbers are sorted according to the digit at

ones place. The buckets are pictured upside down as shown below.

Number 0 1 2 3 4 5 6 7 8 9

345 345

654 654

123 123

567 567

472 472

555 555

808 808

911 911

After this pass, the numbers are collected bucket by bucket. The

new list thus formed is used as an input for the next pass. In the second

pass, the numbers are sorted according to the digit at the tens place. The

buckets are pictured upside down.

Number 0 1 2 3 4 5 6 7 8 9

911 911

472 472

123 123

654 654

345 345

555 555

567 567

808 808

munotes.in

## Page 17

17In the third pass, the numbers are sorted according to the digit at

the hundreds place. The buckets are pictured upside down.

Number 0 1 2 3 4 5 6 7 8 9

808 808

911 911

123 123

345 345

654 654

555 555

567 567

472 472

The numbers are collected bucket by bucket. The new list thus

formed is the final sorted result. After the third pass, the list can be given

as

123, 345, 472, 555, 567, 654, 808, 911

Algorithm:

Step 1: Find the largest number in ARR as LARGE

Step 2: [INITIALIZE] SET NOP = Number of digits in LARGE

Step 3: SET PASS =0

Step 4: Repeat Step 5 while PASS <= NOP-1

Step 5: SET I = 0 and INITIALIZE buckets

Step 6: Repeat Steps 7 to 9 while I

Step 7: SET DIGIT = digit at Passth place in A[I]

Step 8: Add A[I] to the bucket numbered DIGIT

Step 9: INCREMENT bucket count for bucket numbered DIGIT

[END OF LOOP]

Step 10: Collect the numbers in the bucket

[END OF LOOP]

Step 11: END

Program:

#include

#include

int largest(int a[]);

void radix_sort(int a[]);

void main()

{ munotes.in

## Page 18

18 int i;

int a[10]={90,23,101,45,65,23,67,89,34,23};

radix_sort(a);

printf("\n The sorted array is: \n");

for(i=0;i<10;i++)

printf(" %d\t", a[i]);

}

int largest(int a[])

{

int larger=a[0], i;

for(i=1;i<10;i++)

{

if(a[i]>larger)

larger = a[i];

}

return larger;

}

void radix_sort(int a[])

{

int bucket[10][10], bucket_count[10];

int i, j, k, remainder, NOP=0, divisor=1, larger, pass;

larger = largest(a);

while(larger>0)

{

NOP++;

larger/=10;

}

for(pass=0;pass {

for(i=0;i<10;i++)

bucket_count[i]=0;

for(i=0;i<10;i++)

{

// sort the numbers according to the digit at passth place

remainder = (a[i]/divisor)%10;

bucket[remainder][bucket_count[remainder]] = a[i];

bucket_count[remainder] += 1;

}

// collect the numbers after PASS pass

i=0;

for(k=0;k<10;k++)

{

for(j=0;j

## Page 19

19 {

a[i] = bucket[k][j];

i++;

}

}

divisor *= 10;

}

getch();

}

Questions:

1. Given a number of elements in the range [0….n^3]. which of the

following sorting algorithms can sort them in O(n) time?

A. Counting sort

B. Bucket sort

C. Radix sort

D. Quick sort

2. Suppose we need to sort 10 million 80-character strings representing

DNA information from a biological study. Which sorting algorithm should

we use?

A. Bucket Sort

B. Radix Sort

C. Quick Sort

D. Selection Sort

3. Given an array where numbers are in range from 1 to n6, which sorting

algorithm can be used to sort these number in linear time?

A. Not possible to sort in linear time

B. Radix Sort

C. Counting Sort

D. Quick Sort

4. Which of the following is the most suitable definition of radix sort?

A. It is a non-comparison based integer sort

B. It is a comparison based integer sort

C. It is a non-comparison based non integer sort

D. It is a comparison based non integer sort

5. Which of the following is the distribution sort?

A. Heap sort

B. Smooth sort

C. Quick sort

D. Radix sort munotes.in

## Page 20

206. Sort following elements using Radix Sort.

1 2 7 , 3 2 4 , 1 7 3 , 4 , 3 8 , 2 1 7 , 1 3 5

7. Perform Radix sort on following array elements

1 0 , 2 1 , 1 7 , 3 4 , 4 4 , 1 1 , 6 5 4 , 1 2 3

Self-Learning Topic:

Quick sort:

Quicksort is a sorting algorithm based on the divide and conquer approach

where an array is divided into subarrays by selecting a pivot element.The

left and right subarrays are also divided using the same approach. This

process continues until each subarray contains a single element.Finally,

elements are combined to form a sorted array.

munotes.in

## Page 21

21Module II

Practical No: 1

Aim: Implement program for Linear Search.

Objective: Develop a program for searching an element from array using

Linear search.

Theory:

Linear search is the simplest s earch algorithm and often called

sequential search. In this type of searching, we simply traverse the list

completely and match each element of the list with the item whose

location is to be found. If the match is found then locati on of the item is

returned otherwise the algorithm retu rns no element found. Linear search

is mostly used to search an unordered list in which the items are not

sorted. As Linear search compares each and every element one by one i.e.,

it requires more time as compared to other search algorithms.

Example:

If an array A[] is declared and initialized as,

int A[] = {10, 8, 1, 21, 7, 32, 5, 11, 0}

The value to be searched is VAL = 5, then searching means to find

whether the value ‘5’ is present in the array or not. If yes, then it returns

the position of its occurrence. Here, POS = 6 (index starting from 0).

Algorithm:

LINEAR_SEARCH(A, N, VAL)

Step 1: [Initialize] set pos = -1

Step 2: [Initialize] set i = 1

Step 3: Repeat Step 4 while I<=N

Step 4: If a[i] = val

Set pos = i munotes.in

## Page 22

22Print pos

Go to step 6

[End of if]

Set i = i + 1

[End of loop]

Step 5: If pos = -1

Print " value is not present in the array "

[End of if]

Step 6: Exit

Program:

#include

#include

void main ()

{

int a[10] = {10, 23, 40, 1, 2, 0, 14, 13, 50, 9};

int item, i, flag;

printf("\nEnter Item which is to be searched\n");

scanf("%d",&item);

for (i = 0; i< 10; i++)

{

if(a[i] == item)

{

flag = i+1;

break;

}

else

{

flag = 0;

}

}

if(flag != 0)

{

printf("\nItem found at location %d\n",flag);

}

else

{

printf("\nItem not found\n");

}

getch();

}

munotes.in

## Page 23

23Questions:

1. Which of the following is a disadvantage of linear search?

A. Requires more space

B. Requires more time for searching

C. Not easy to understand

D. Not easy to implement

2. The array is as follows: 11,2,30,65,80,100. Given that the number 23 is

to be searched. After how many iterations it tells that there is no such

element?

A. 7

B. 9

C. 20

D. 5

3. A linear search algorithm is also known as a __________.

A . B i n a r y s e a r c h a l g o r i t h m

B . B u b b l e s o r t a l g o r i t h m

C . S e q u e n t i a l s e a r c h a l g o r i t h m

D . R a d i x s e a r c h a l g o r i t h m

4. What will happen in a Linear sear ch algorithm if no match is found?

A . I t c o n t i n u e s t o s e a r c h i n a n e v e r - e n d i n g l o o p .

B . " I t e m n o t f o u n d " i s r e t u r n e d

C . C o m p i l e - t i m e e r r o r

D . R u n - t i m e e r r o r

5. What is an advantage of the Linear search algorithm?

A . I s c o m p l i c a t e d t o c o d e

B . C a n b e u s e d o n d a t a s e t s with more than a million elements

C. Performs well with small sized data sets

D . D i f f i c u l t t o u n d e r s t a n d

Practical No: 2

Aim: Implement program for Binary Search.

Objective: To understand working of Binary search algorithm and to

implement program for searching an element using binary search.

Theory:

Binary search is the search technique which works efficiently on

the sorted lists. Hence, in order to search an element into some list by

using binary search technique, we must ensure that the list is sorted. But it munotes.in

## Page 24

24cannot be applied to linked list. Binary search follows divide and conquer

approach in which, the list is divided into two halves and the item is

compared with the middle element of the list. If the match is found then,

the location of middle element is returned. If the middle item is greater

than the item, then the item is searched in the sub-array to the left of the

middle item. Otherwise, the item is searched in the sub-array to the right

of the middle item.

Example:

Let us consider an array a = {11, 15, 17, 18, 23, 29, 30, 33, 39}.

Find the location of the item 33 in the array.

Elements 11 15 17 18 23 29 30 33 39

Indexes 0 1 2 3 4 5 6 7 8

Step 1:

BEG = 0

END = 8

MID = (BEG+END)/2= (0+8)/2= 4

a[MID] = a[4] = 23 < 33

Step 2:

BEG = MID +1 = 4+1= 5

END = 8

MID = (BEG+END)/2= (5+8)/2= 13/2 = 6

a[MID] = a[6] = 30 < 33

Step 3:

BEG = MID + 1 = 6+1= 7

END = 8

MID = (BEG+END)/2= (7+8)/2= 15/2 = 7

a[MID] = a[7]

a[7] = 33 = item;

Therefore, the location of the item will be 7.

Algorithm:

Step 1 : Find the middle element in the sorted list.

Step 2 : Compare the search element with the middle element in the sorted

list.

Step 3 : If both are matched, then display "Given element is found!" and

terminate the function.

Step 4 : If both are not matched, then check whether the search element is

smaller or larger than the middle element. munotes.in

## Page 25

25Step 5 : If the search element is smaller than middle element, repeat steps

2, 3, 4 and 5 for the left sublist of the middle element.

Step 6 : If the search element is larger than middle element, repeat steps 2,

3, 4 and 5 for the right sublist of the middle element.

Step 7 : Repeat the same proce ss until we find the sear ch element in the list

or until sublist contains only one element.

Step 8 : If that element also doesn't match with the search element, then

display "Element is not found in the list" and terminate the function.

Program:

#include

#include

void main()

{

int first, last, middle, size, i, key, list[100];

clrscr();

printf("Enter the size of the list: ");

scanf("%d",& size);

printf("Enter %d integer values in Ascending order\n", size);

for (i = 0; i < size; i++)

{

scanf("%d",&list[i]);

}

printf("Enter value to be search: ");

scanf("%d", &key);

first = 0;

last = size - 1;

middle = (first+last)/2;

while (first <= last)

{

if (list[middle] {

first = middle + 1;

}

else if (list[middle] == key)

{

printf("Element found at index %d.\n",middle);

break;

}

else

{

last = middle - 1;} munotes.in

## Page 26

26middle = (first + last)/2;

}

if (first > last)

{

printf("Element Not found in the list.");

}

getch();

}

Questions:

1. Binary Search can be categorized into which of the following?

A. Brute Force technique

B. Divide and conquer

C. Greedy algorithm

D. Dynamic programming

2. Given an array S = {50,60,77,88,99} and key = 88; How many

iterations are done until the element is found?

A. 1

B. 3

C. 4

D. 2

3. Binary search algorithm cannot be applied to

A . S o r t e d l i n k e d l i s t

B . S o r t e d b i n a r y t r e e s

C . S o r t e d l i n e a r a r r a y

D . P o i n t e r a r r a y

4. Search element 500 from the given array using binary search algorithm.

5 0 , 6 0 , 1 5 0 , 2 8 0 , 3 2 0 , 4 0 0 , 5 0 0 , 6 0 0

Practical No: 3

Aim: Implement program for Modulo Division.

Objective: To understand modulo division method in hashing with the

help of example. To implement program for finding key location of

elements using Modulo division.

Theory:

Hashing is a technique or process of mapping keys, values into the

hash table by using a hash function. It is done for faster access to

elements. Modulo Division is the easiest method to create a hash function. munotes.in

## Page 27

27Also known as division remainder, the modulo-division method divides

the key by table size and uses the remainder for the address. The hash

function can be described as

h(k) = k mod m

Here, h(k) is the hash value obtained by dividing the key value k by size of

hash table m using the remainder.

A disadvantage of the division method is that consecutive keys

map to consecutive hash values in the hash table. This leads to a poor

performance. This algorithm works with a n y t a b l e s i z e , b u t a t a b l e s i z e

that is a prime number produces fewer collisions than other table sizes.

We should therefore try to make the array size a prime number.

Example:

Elements to be placed in a hash table are 42,78,89,64 and let’s take table

size as 10.

Hash (key) = Elements % table size;

h(k)= k mod m

h(42) = 42 % 10 = 2

h(78) = 78 % 10 = 8

h(89) = 89 % 10 = 9

h(64) = 64 % 10 = 4

The table representation can be seen as below:

Key Value

0

1

2 42

3

4 64

5

6

7

8 78

9 89

Algorithm:

Suppose array name is A and n is the size of array.

Step 1: Initialize all array values with -1.

Step 2: Specify the values which needs to be inserted.

Step 3: Calculate key address using modulo division method.

S e t k e y = v a l u e % s i z e

Step 4: If A[key] = = -1

S e t A [ k e y ] = v a l u e / / I n s e r t t h e v a l u e a t c a l c u l a t e d k e y o r a d d r e s s munotes.in

## Page 28

28 E l s e

P r i n t : U n a b l e t o i n s e r t

[ E n d I f ]

Step 5: If A[key] = = value

P r i n t : S e a r c h f o u n d

E l s e

P r i n t : S e a r c h n o t f o u n d

[ E n d I f ]

Step 6: Repeat while key< n

P r i n t : A [ k e y ]

[ E n d w h i l e ]

Step 7: End

Program:

#include

#include

#define size 7

int arr[size];

void init()

{

int i;

for(i = 0; i < size; i++)

{

arr[i] = -1;

}

}

void insert(int value)

{

int key = value % size; //use of modulo division

if(arr[key] == -1)

{

arr[key] = value;

printf("%d inserted at arr[%d]\n", value,key);

}

else

{

printf("Collision : arr[%d] has element %d already!\n",key,arr[key]);

printf("Unable to insert %d\n",value);

}

}

void search(int value)

{ munotes.in

## Page 29

29 int key = value % size;

if(arr[key] == value)

{

printf("Search Found\n");

}

else

{

printf("Search Not Found\n");

}

}

void display()

{

int i;

for(i = 0; i < size; i++)

{

printf("arr[%d] = %d\n",i,arr[i]);

}

}

int main()

{

init();

insert(10); //key = 10 % 7 ==> 3

insert(4); //key = 4 % 7 ==> 4

insert(2); //key = 2 % 7 ==> 2

insert(3); //key = 3 % 7 ==> 3 (collision)

printf("Hash table\n");

display();

printf("\n");

printf("Searching value 4..\n");

search(4);

getch();

return 0;

}

Questions:

1. What is the hash function used in the division method?

A. h(k) = k/m

B. h(k) = k mod m

C. h(k) = m/k

D. h(k) = m mod k

munotes.in

## Page 30

302. What can be the value of m in the division method?

A. Any prime number

B. Any even number

C. 2p – 1

D. 2p

3. Using division method, in a given hash table of size 157, the key of

value 172 be placed at position _________.

A. 19

B. 72

C. 15

D. 17

4. In which of the following hash functions, do consecutive keys map to

consecutive hash values?

A . D i v i s i o n M e t h o d

B . M u l t i p l i c a t i o n M e t h o d

C . F o l d i n g M e t h o d

D . M i d - S q u a r e M e t h o d

Practical No: 4

Aim: Implement program for Digit Extraction.

Objective: To develop program for hashing using digit extraction method.

Theory:

Using digit extraction method, selected digits are extracted from

the key and used as the address. It is also called a Truncation method.

Steps for truncation are as follows.

1. Choose the hash table size.

2. Then the respective right most or left most digits are truncated and used

as hash value.

If address is represented by n-bits, the use n digits from the key.

Address = selected digits from key

Using employee number to hash to a 3 digit address we could select first,

third & fourth element [from left].

Key Address

3 9 7 4 2 5 3 7 4

2 3 5 6 7 8 2 5 6

munotes.in

## Page 31

31Example:

Ex: 123,42,56 and Table size = 9

H(123) =1 //First digit i.e. 1 is selected

H(42) = 4 //First digit i.e. 4 is selected

H(56) = 5 //First digit i.e. 5 is selected

Address Key

0

1 123

2

3

4 42

5 56

6

7

8

Algorithm:

Step 1: Begin

Step 2: Pass key value ‘Key’ as an argument to digit_extraction().

Step 3: Initialize values

Set: first_digit=0 and fouth_digit=0 //for extracting digit at first &

fourth position

Step 4: For extracting first digit from given no

Calculate: first_digit= key%10000000;

first_digit=first_digit/1000000;

Step 5: For extracting fourth digit from given no

Calculate: fourth_digit= key%1000;

fourth_digit=fourth_digit/100;

Step 6: Display the hashed location where given number will be stored.

Print: (first_digit, fourth_digit);

Step 7: End

Program:

#include

int digit_extraction(int key)

{

int key_length=0;

int first_digit=0;

int fourth_digit=0;

first_digit= key%10000000;

first_digit=first_digit/1000000;

fourth_digit= key%1000; munotes.in

## Page 32

32fourth_digit=f ourth_digit/100;

printf("%d key would be hashed at location %d%d

\n",key,first_digit, fourth_digit);

}

int main()

{

digit_extraction(1347878); //18

digit_extraction(1234678); //16

return 0;

}

Questions:

1. In ________ method of hashing, selected digits are extracted from the

key and used as the address.

A . S u b t r a c t i o n

B. Digit extraction

C. Rotation

D. Folding

2. __________ is also known as Digit Extraction.

A . F o l d i n g

B . S u b t r a c t i o n

C . T r u n c a t i o n

D . C o l l i s i o n R e s o l u t i o n

3. If key is 987654 then using the odd-place digits, the index(hash value)

would be ________.

A . 4 8 6

B . 8 6 4

C . 9 7 5

D . 9 8 7

4. If key is 356487 then using the even-place digits, the index(hash value)

would be ________.

A . 3 6 8

B . 5 4 7

C . 6 4 8

D . 3 5 4

munotes.in

## Page 33

33Practical No: 5

Aim: Implement program for Fold Shift.

Objective: To understand fold shift method of hash function and to

implement program for hashing values using fold shift.

Theory:

In fold shift the key value is divi ded into parts whose size matches

the size of the required address. Then the left and right parts are shifted

and added with the middle part.The fo lding method works in the following

two steps:

Step 1: Divide the key value into a number of parts. That is, divide k into

parts k1, k2, …, kn, where each part has the same number of digits except

the last part which may have lesser digits than the other parts.

Step 2: Add the individual parts. That is, obtain the sum of k1 + k2 + … +

kn. The hash value is produced by ignoring the last carry, if any.

Example:

Suppose to calculate hash value for X = 5678 and hash table size 100, we

need to follow below steps:

Step 1: The X will be divided into tw o parts each having two digits i.e.

k1=56 and k2 = 78

Step 2: Adding all key parts

k1 + k2 i.e.

Key= 56 + 78 = 134

After ignoring the carry 1 (because here only two digits are

required as hash value) the resulting hash value for 5678 is 34.

Algorithm:

Step 1: The folding method is used for creating hash functions starts with

the item being divided into equal-sized pieces i.e., the last piece may not

be of equal size.

Step 2: The outcome of adding these bits together is the hash value, H(x) =

(a + b + c) mod M, where a, b, and c represent the preconditioned key

broken down into three parts and M is the table size, and mod stands for

modulo.

Step 3: In other words, the sum of three parts of the preconditioned key is

divided by the table size. The remainder is the hash key. munotes.in

## Page 34

34Program:

#include

#include

#include

#include

int count_digits(int key)

{

int count=0;

w h i l e ( k e y ! = 0 )

{

k e y / = 1 0 ;

+ + c o u n t ;

}

return count;

}

int fold_shift(int key, int size)

{

int key_roll=key;

int key_sum=0;

int key_frac=0;

int key_length=0;

int fraction = size;

key_length = count_digits(key_roll);

while (key_length > 0)

{

i f ( k e y _ l e n g t h > f r a c t i o n )

{

k e y _ f r a c = k e y _ r o l l / ( i n t ) p o w ( 1 0 , ( k e y _ l e n g t h - f r a c t i o n ) ) ;

k e y _ s u m + = k e y _ f r a c ;

k e y _ r o l l = k e y _ r o l l % ( i n t ) p o w ( 1 0 , ( k e y _ l e n g t h - f r a c t i o n ) ) ;

k e y _ l e n g t h = k e y _ l e n g t h - f r a c t i o n ;

}

e l s e

{

k e y _ s u m + = k e y _ r o l l ;

b r e a k ;

}

}

return key_sum % (int)pow(10, (fraction));

}

int main()

{ munotes.in

## Page 35

35clrscr();

printf("\n\n%d",fold_shift (12789, 3)); //216

printf("\n\n%d",fold_shift (12345678, 1)); //6

printf("\n\n%d",fold_shift(5678, 2)); //34

getch();

return 0;

}

Questions:

1. For key 345678123 what will be index in fold shift?

A . 1 4 6

B . 6 4 1

C . 5 4 2

D . 6 7 8

2. Folding is a method of generating _________.

A. A hash function

B. Index function for a triangular matrix

C. Linear probing

D. Chaining

3. Hashing method in which the give n key is partitioned into subparts

k1,k2,k3....kn is known as

A. Mid square method

B. Division method

C. Partition method

D. Folding method

4. If the number is 164257408 and table size is 100 then the location

where number will get stored by fold shift method is _________.

A. 6

B. 3

C. 56

D. 63

5. If the number is 123456789 and table size is 1000 then address where

number will get stored by fo ldshift method is __________.

A. 8

B. 138

C. 368

D. 20

munotes.in

## Page 36

36Practical No: 6

Aim: Implement program for Fold Boundary.

Objective: To understand fold boundary method of hash function and to

develop program for hashing values using fold boundary.

Theory:

In fold boundary the left and right numbers are folded on a fixed boundary

between them and the center number. The two outside values are thus

reversed.

The fold boundary method works in the following two steps:

Step 1: D i v i d e t h e k e y v a l u e i n t o a n u m b e r o f p a r t s i . e . , l e f t , r i g h t a n d

middle parts.

Step 2: Reverse left and right individual parts. Then, obtain the sum of

reversed parts and middle part if it exists. The hash value is produced by

ignoring the last carry, if any.

Example:

Suppose to calculate hash value for Key = 123456789 and size of required

address is 3 digits, we need to follow below steps:

Step 1: The Key will be divided into two parts

Key = 123 | 456 | 789

Step 2: Reverse left and right parts and add it with middle part.

321 (folding applied)+456+987 (folding applied) = 1764(discard 1

or 4)

After we ignore the carry 1 (because here only three digits are

required as hash value) the result ing hash value for 123456789 is 764.

Algorithm:

Step 1: Specify the number which is to be folded and boundary between

them.

f o l d _ b o u n d a r y ( i n t k e y , i n t s i z e )

Step 2: Initialize all the integer values.

S e t : k e y _ s u m = 0 , k e y _ f r a c = 0 , m i d d l e = 0 , l e f t = 0 , r i g h t = 0 , d i g i t s = 0 ,

key_length=0

S e t : k e y _ r o l l = k e y & f r a c t i o n = s i z e munotes.in

## Page 37

37Step 3: Calculate key_length

count_digits(key)

a. Initialize count with value zero

b. Repeat while (key!=0)

Key/=10;

++count

[End while]

c. Return count

d. Terminate function

Step 4: Divide the number in three parts around a fixed boundary on left

and right side.

Step 5: Compute first three digits of given number. Reverse it and store

the reversed value in left variable.

Step 6: Compute last three digits of the given number. Reverse it and store

the reversed value in right variable.

Step 7: Find middle value of the given number and store it in variable

middle.

Step 8: Calculate key_sum

k e y _ s u m = l e f t + m i d d l e + r i g h t

Step 9: If carry is generated then ignore carry

S e t : k e y _ s u m = k e y _ s u m % ( i n t ) p o w ( 1 0 , ( f r a c t i o n ) )

Step 10: Print: key_sum

Step 11: End

Program:

#include

#include

#include

int count_digits(int key)

{

int count=0;

w h i l e ( k e y ! = 0 )

{

k e y / = 1 0 ;

+ + c o u n t ;

}

return count;

}

int fold_boundary(int key, int size) munotes.in

## Page 38

38{

int key_roll=key;

int key_sum=0;

int key_frac=0;

int middle=0;

int left=0;

int right=0;

int digits=0;

int key_length=0;

int fraction = size;

key_length = count_digits(key_roll);

key_frac = key_roll / (int)pow(10, (key_length - fraction));// start digit

left=reversDigits(key_frac);

key_roll = key_roll % (int)pow(10,3);

right=reversDigits(key_roll);

digits = (int)log10(key) + 1;

middle= (int)(key / pow(10, digits/ 2)) % 10;

key_sum = left +middle+ right;

r e t u r n k e y _ s u m % ( i n t ) p o w ( 1 0 , (fraction)); //ignore carry

}

int reversDigits(int num)

{

int rev_num = 0;

w h i l e ( n u m > 0 )

{

r e v _ n u m = r e v _ n u m * 1 0 + n u m % 1 0 ;

n u m = n u m / 1 0 ;

}

r e t u r n r e v _ n u m ;

}

int main()

{

printf("\n\n%d",fold_boundary(3347878, 3)); //318

printf("\n\n%d",fold_boundary(1234678, 3)); //201

return 0;

}

munotes.in

## Page 39

39Questions:

1. In which of the following, the left and right numbers are reversed on

except the center number?

A. Division method

B. fold boundary

C. fold shift

D. folding method

2. For key 345678123 what will be index in fold boundary?

A . 5 4 2

B . 2 4 5

C . 1 4 6

D . 8 7 6

3. If number is 15547012 and table size is 100 then address of number by

fold boundary method is _________.

A. 1

B. 51

C. 96

D. 6

4. The types of folding method are:

A. fold shift

B. fold boundary

C. both

D. none of these

Practical No: 7

Aim: Implement program for Linear probe for Collision Resolution.

Objective: To understand linear probing with its example. To develop

program for collision resolution using linear probe.

Theory:

Linear probing is one of the co llision resolution techniques

classified under open addressing te chnique/Closed Hashing which is a

method for handling collisions. While hashing if two or more key points to

the same hash index under some modulo M it is called as collision. When

collision occurs, we linearly probe for the next slot. We keep probing until

an empty slot is found. The main problem with linear probing is

clustering. Many consecutive elements form groups.

munotes.in

## Page 40

40Steps for collision resolution using linear probing are as follows.

Step 1: Calculate the hash key.

address = key % size;

Step 2: If hashTable[key] is empty, store the value directly.

hashTable[key] = data.

If the hash index already has some value, check for next index.

Next address = (key+1) % size;

If the next index is available hashTable[key], store the value.

Otherwise try for next index.

h(k) = (key+i) % size; where i= 0,1,2,3,…

Step 3: Do the above process till we find the space.

Example:

Let us consider a simple hash function as “key mod 7” and a sequence of

keys as 50, 700, 76, 85, 92. Hash them and if collision occurs resolve it

with linear probing.

1) Initially empty table

Key

Location 0 1 2 3 4 5 6

2) Insert 50:

h(k)= key % 7, h(50) = 50 % 7 = 1

Key 50

Location 0 1 2 3 4 5 6

3) Insert 700:

h(k)= key % 7, h(700) = 700 % 7 = 0

Key 700 50

Location 0 1 2 3 4 5 6

4) Insert 76:

h(k)= key % 7, h(76) = 76 % 7 = 6

Key 700 50 76

Location 0 1 2 3 4 5 6

5) Insert 85:

h(k)= key % 7, h(85) = 85 % 7 = 1 //Collision occurs as 50 is already

present at location 1 i.e. Find next location i.e.

h(k ̍) =(key + 1) % 7, h(85 ̍)= (85+1)%7= 2 //insert 85 at location 2

Key 700 50 85 76

Location 0 1 2 3 4 5 6

munotes.in

## Page 41

416) Insert 92:

h(k)= key % 7 = 92 % 7 = 1 //Collision occurs as 50 is already present at

location 1, Find next location i.e.

h(k ̍) =(key + 1) % 7= (92+1)%7= 2 //Collision occurs as 85 is already

present at location 2, Find next location i.e.

h(k ̍) =(key + 2) % 7= (92+2)%7= 3 //insert 92 at location 3

Key 700 50 85 92 76

Location 0 1 2 3 4 5 6

Algorithm:

Consider x is original array of elements, n is total no of elements in x, and

ht is hash table array.

Step 1: Enter total no of elements to store and enter those elements.

A c c e p t : n a n d v a l u e s o f x [ i ]

Step 2: Initialize empty hash table, Repeat while i < size

S e t h t [ i ] = - 1 / / e m p t y h a s h t a b l e

Step 3: Repeat while i< n

S e t k e y = x [ i ] ;

S e t a d d r e s s = m o d u l o d i v i s i o n ( k e y )

I f a d d r e s s n o t e q u a l s t o - 1

S e t a d d r e s s = l i n e a r p r o b e ( a d d r e s s )

e l s e

S e t a d d r e s s = k e y

[ E n d I f ]

[ E n d w h i l e ]

Step 4: End

modulodivision(key)

Step 1: Calculate address as

a d d r e s s = k e y % s i z e + 1

Step 2: If address equal to size of hash table

S e t a d d r e s s = 0

E l s e

R e t u r n a d d r e s s

[ E n d I f ]

linearprobe(address)

Step 1: Repeat while address in hash table is not empty

F i n d n e x t a d d r e s s

I f a d d r e s s = = s i z e / / a d d r e s s e q u a l s t o l a s t a d d r e s s o f h a s h

table

Set address = 0 //point address to first address in

hash table munotes.in

## Page 42

42 [ E n d I f ]

[ E n d w h i l e ]

Step 2: Return Address

Program:

#include

#include

#define size 10

int ht[size];

void store(int x[ ], int n);

int modulodivision(int key);

int linearprobe(int address);

void main()

{

int i, n, x[10] ;

char ch ;

clrscr();

printf("Enter the number of elements: ") ;

scanf("%d",&n) ;

printf("Enter the elements:\n") ;

for(i=0 ; i {

scanf("%d",&x[i]) ;

}

store(x,n) ;

printf("Hashtable is as shown:\n") ;

for(i=0 ; i {

printf("%d ", ht[i]) ;

}

getch() ;

}

void store(int x[ ], int n)

{

int i, key, address;

/* Initializing hash table to empty */

for(i=0 ; i ht[i]=-1;

/* Copying elements from original array to hashtable */

for(i=0 ; i {

key=x[i]; munotes.in

## Page 43

43 address=modulodivision(key);

if(ht[address]!=-1)

address=linearprobe(address);

ht[address]=key;

}

}

/* Hash Function */

int modulodivision(int key)

{

int address;

address=key%size+1;

if(address==size)

{

return 0;

}

else

{

return address;

}

}

/* Collision Resolution */

int linearprobe(int address)

{

while(ht[address]!=-1)

{

address++;

if(address==size)

address=0;

}

return address;

}

Questions:

1. What is the hash function used in linear probing?

A. H(x)= key mod table size

B. H(x)= (key+ F(i2)) mod table size

C. H(x)= (key+ F(i)) mod table size

D. H(x)= X mod 17

munotes.in

## Page 44

442. ___________ is not a theoretical problem but actually occurs in real

implementations of probing.

A. Hashing

B. Clustering

C. Rehashing

D. Collision

3. Consider a 13-element hash table for which h(k)= key mod 13 is used

with integer keys. Assuming linear probing is used for collision resolution,

at which location would the key 103 be inserted, if the keys 661, 182, 24

and 103 are inserted in that order?

A . 0

B . 1

C . 1 1

D . 1 2

4. A hash function h defined as h(k) = k mod 7, with linear probing, insert

the keys 37, 38, 72, 48, 98, 11, 56 into a table. Key 11 will be stored at the

location ______.

A . 3

B . 7

C . 2

D . 5

Self-Learning Topics:

Direct and Subtraction hashing:

In direct hashing the key is the address without any algorithmic

manipulation.

Direct hashing is limited and not suitable for large key values, but

it can be very powerful because it guarantees that there are no collisions.

In Subtraction hashing a fixed number is subtracted from key. It is suitable

for small list.

munotes.in

## Page 45

45Module III

Practical No: 1

Aim: Implement program for Stack using Arrays.

Objective: To understand stack operations and to develop a program for

implementing stack using array.

Theory:

A Stack is a linear data structure that follows the Last-In-First-

Out(LIFO) principle. It can be defined as a container in which insertion

and deletion can be done from the one end known as the top of the stack.

A stack data structure can be implemented using a one-dimensional array.

But stack implemented using array stores only a fixed number of data

values. Just define a one-dimensional array of specific size and insert or

delete the values into that array by using LIFO principle with the help of a

variable called 'top'. Initially, the top is set to -1. Whenever we want to

insert a value into the stack, incr ement the top value by one and then

insert. Whenever we want to delete a value from the stack, then delete the

top value and decrement the top value by one.

Stack Operations using Array:

1. push(): In a stack, push() is used to insert an element into the stack. In a

stack, the new element is always inserted at top position. Following are the

steps to push an element on to the stack.

Step 1: Check whether stack is full. (top == n)

Step 2: If it is full, then display "Overflow” and terminate the function.

Step 3: If it is not full, then increment top value by one (top+1) and set

stack[top] to value (stack[top] = value).

2. pop(): In a stack, pop() is used to delete an element from the stack. In a

stack, the element is always delete d from top position. We can use the

following steps to pop an element from the stack.

Step 1: Check whether stack is empty. (top == -1)

Step 2: I f i t i s e m p t y , t h e n d i s p l a y " U n d e r f l o w " a n d t e r m i n a t e t h e

function.

Step 3: If it is not empty, then delete stack[top] and decrement top value

by one (top-1).

munotes.in

## Page 46

46Algorithm:

1. Algorithm for push operation:

begin

if top = n then stack full

top = top + 1

stack (top) : = item;

end

2. Algorithm for pop operation:

begin

if top = 0 then stack empty;

item := stack(top);

top = top - 1;

end;

Program:

#include

int stack[100],i,j,choice=0,n,top=-1;

void push();

void pop();

void show();

void main ()

{

printf("Enter the number of elements in the stack ");

scanf("%d",&n);

printf("***Stack operations using array***");

printf("\n---------------------------------\n");

while(choice != 4)

{

printf("Chose one from the below options...\n");

printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");

printf("\n Enter your choice \n");

scanf("%d",&choice);

switch(choice)

{

case 1:

{

push();

break;

}

case 2:

{

pop();

break;

} munotes.in

## Page 47

47 case 3:

{

show();

break;

}

case 4:

{

printf("Exiting....");

break;

}

default:

{

printf("Please Enter valid choice ");

}

}

}

}

void push ()

{

int val;

if (top == n )

printf("\n Overflow");

else

{

printf("Enter the value?");

scanf("%d",&val);

top = top +1;

stack[top] = val;

}

}

void pop ()

{

if(top == -1)

printf("Underflow");

else

top = top -1;

}

void show()

{

for (i=top;i>=0;i--)

{

printf("%d\n",stack[i]); munotes.in

## Page 48

48 }

if(top == -1)

{

printf("Stack is empty");

}

}

Questions:

1. What does ‘stack underflow’ refers to?

A. Accessing item from an undefined stack

B. Adding items to a full stack

C. Removing items from an empty stack

D. Index out of bounds exception

2. Array implementation of Stack is not dynamic, which of the following

statements supports this argument?

A . U s e r u n a b l e t o g i v e t h e i n p u t f o r s t a c k o p e r a t i o n s

B. Space allocation for array is fixed and cannot be changed during

run-time

C . A r u n t i m e e x c e p t i o n h a l t s e x e c u t i o n

D . I m p r o p e r p r o g r a m c o m p i l a t i o n

3. Which of the following array element will return the top of the stack

element for a stack of size n elements?

A. S[n-1]

B. S[n]

C. S[n-2]

D. S[n+1]

4. Which one of the following is the process of inserting an element in the

stack?

A. Insert

B. Add

C. Push

D. Pop

5. What is the meaning of Top == -1?

A . S t a c k i s e m p t y

B . O v e r f l o w c o n d i t i o n

C . U n d e r f l o w c o n d i t i o n

D . S t a c k i s f u l l

munotes.in

## Page 49

49Practical No: 2

Aim: Implement program for Stack using Linked List.

Objective: To develop a program for implementing stack using Linked

List.

Theory:

The major problem with the stack implemented using an array is, it

works only for a fixed number of data values. Stack implemented using an

array is not suitable, when we don't know the size of data which we are

going to use. The stack implemented using linked list can work for an

unlimited number of values. That means, stack implemented using linked

list works for the variable size of data . So, there is no need to fix the size

at the beginning of the implementation. In linked list implementation of a

stack, every newly inserted element is pointed by 'top'. Whenever we want

to remove an element from the stack, simply remove the node which is

pointed by 'top' by moving 'top' to its previous node in the list. The next

field of the first element must be always NULL.

Stack operations using linked list

1. push(): We can use the following steps to p u s h a n e l e m e n t i n t o t h e

stack.

Step 1: Create a newNode with the given data.

Step 2: Check whether the stack is empty (TOP == NULL).

Step 3: If it is empty, then set the pointer of the node to NULL.

Step 4: If it is not empty, then make the node point to TOP.

Step 5: Finally, make the newNode as TOP.

2. pop(): We can use the following steps to pop an element from the stack.

Step 1: Check whether stack is empty (top == NULL).

Step 2: If it is empty, th en display "EMPTY STACK"

Step 3: If it is not empty, then crea te a temporary node and set it to TOP.

Step 4: Print the data of TOP.

Step 5: Make TOP to point to the next node.

Step 6: Delete the temporary node.

Algorithm:

1. Algorithm for push() operation:

begin

if (TOP == NULL) //Check whether stack is Empty

newNode -> next = NULL //if stack is empty

else

newNode -> next = TOP //if stack is not empty munotes.in

## Page 50

50TOP= newNode

end

2. Algorithm for pop() operation:

begin

if (TOP == NULL) //Check whether stack is Empty

print "EMPTY STACK"

else

create a temporary node, temp = top //if stack is not empty

print TOP -> data

TOP = TOP -> next

free(temp)

end

Program:

#include

#include

/* Structure to create a node with data and pointer */

struct Node

{

int data;

struct Node *next;

}

*top = NULL; // Initially the list is empty

void push(int);

void pop();

void display();

int main()

{

int choice, value;

printf("\nIMPLEMENTING STACKS USING LINKED LISTS\n");

while(1)

{

printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");

printf("\nEnter your choice : ");

scanf("%d",&choice);

switch(choice)

{

case 1: printf("\nEnter the value to insert: ");

scanf("%d", &value);

push(value);

break;

munotes.in

## Page 51

51case 2: pop();

break;

case 3: display();

break;

case 4: exit(0);

break;

default: printf("\nInvalid Choice\n");

}

}

}

void push(int value)

{

struct Node *newNode;

newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = value; // get value for the node

if(top == NULL)

newNode->next = NULL;

else

newNode->next = top; // Make the node as TOP

top = newNode;

printf("Node is Inserted\n\n");

}

void pop()

{

if(top == NULL)

printf("\nEMPTY STACK\n");

else{

struct Node *temp = top;

printf("\nPopped Element : %d", temp->data);

printf("\n");

top = temp->next; // After poppin g, make the next node as TOP

free(temp);

}

}

void display()

{

if(top == NULL)

printf("\nEMPTY STACK\n");

else munotes.in

## Page 52

52{

printf("The stack is \n");

struct Node *temp = top;

while(temp->next != NULL){

printf("%d--->",temp->data);

temp = temp -> next;

}

printf("%d--->NULL\n\n",temp->data);

}

}

Questions:

1. If the size of the stack is 8 and we try to add the 9th element in the stack

then the condition is known as __________.

A. Underflow

B. Garbage collection

C. Overflow

D . E m p t y

2. If the elements '10', '20', '30' and '40' are added in a stack, so what

would be the order for the removal?

A. 10, 20, 30, 40

B. 20, 10, 30, 40

C. 40, 30, 20, 10

D. 30, 10, 20, 40

3. Stack can be implemented using _________ and _________?

A . A r r a y a n d B i n a r y T r e e

B . L i n k e d L i s t a n d G r a p h

C . A r r a y a n d L i n k e d L i s t

D . Q u e u e a n d L i n k e d L i s t

4. TOP == NULL represents:

A. Stack is full

B. Stack is empty

C. Overflow condition

D. Underflow condition

5. Statement top = temp->next does what in the Linked List?

A . M a k e t h e n e x t n o d e a s t o p

B . M a k e t h e c u r r e n t n o d e a s t o p

C . M a k e t h e p r e d e c e s s o r n o d e a s t o p

D . P o p o n e e l e m e n t f o r m t h e l i n k e d l i s t

munotes.in

## Page 53

53Practical No: 3

Aim: Implement program for Evaluation of Postfix Expression.

Objective: To develop program for Evaluation of Postfix Expression.

Theory:

The Postfix notation is used to represent algebraic

expressions.Reverse Polish notation, also known as Polish postfix notation

or simply postfix notation, is a math ematical notation in which operators

follow their operands. The expression s written in postfix form are

evaluated faster compared to infix nota tion as parenthesis are not required

in postfix.

Example:

Let us consider the given expression as 2 3 1 * + 9 -

We scan all elements one by one.

Step Character

Scanned Operation Stack

Status Calculation

1 2 Push 2

2 3 Push 2,3

3 1 Push 2,3,1 3*1=3

4 * Pop 2 elements &

evaluate 2,3

5 + Pop 2 elements &

evaluate 5 2+3=5

6 9 Push 5,9

7 - Pop 2 elements &

evaluate -4 5-9= -4

Explanation:

1) Scan ‘2’, it’s a number, so push it to stack. Stack contains ‘2’

2) Scan ‘3’, again a number, push it to stack, stack now contains ‘2 3’.

3) Scan ‘1’, again a number, push it to stack, stack now contains ‘2 3 1’

4) Scan ‘*’, it’s an operator, pop two operands from stack, apply the *

operator on operands, we get 3*1 which results in 3. We push the

result ‘3’ to stack. Stack now becomes ‘2 3’.

5) Scan ‘+’, it’s an operator, pop two operands from stack, apply the +

operator on operands, we get 3 + 2 which results in 5. We push the

result ‘5’ to stack. Stack now becomes ‘5’. munotes.in

## Page 54

546) Scan ‘9’, it’s a number, we push it to the stack. Stack now becomes

‘5 9’.

7) Scan ‘-‘, it’s an operator, pop two operands from stack, apply the –

operator on operands, we get 5 – 9 which results in -4. We push the

result ‘-4’ to stack. Stack now becomes ‘-4’.

8) There are no more elements to scan, we return the top element from

stack (which is the only element left in stack).

Algorithm:

Step 1: Create a stack to store operands (or values).

Step 2: Scan the given expression and do following for every scanned

element.

a) If the element is a number, push it into the stack.

b) If the element is an operator, pop operands for the operator from

stack. Evaluate the operator and push the result back to the stack.

Step 3: When the expression is ended, the number in the stack is the final

answer.

Program:

#include

#include

#include

#define MAX 50 //max size defined

int stack[MAX]; //a global stack

char post[MAX]; //a global postfix stack

int top=-1; //initializing top to -1

void pushstack(int tmp); //push function

void evaluate(char c); //calculate function

void main()

{

int i,l;

//clrscr();

printf("Insert a postfix notation :: ");

gets(post); //getting a postfix expression

l=strlen(post); //string length

for(i=0;i {

if(post[i]>='0' && post[i]<='9')

{

pushstack(i); //if the element is a number push it

}

if(post[i]=='+' || post[i]=='-' || post[i]=='*' ||

post[i]=='/' || post[i]=='^') //if element is an operator munotes.in

## Page 55

55 {

evaluate(post[i]); //pass it to the evaluate

}

} //print the result from the top

printf("\n\nResult :: %d",stack[top]);

getch();

}

void pushstack(int tmp) //definiton for push

{

top++; //incrementing top

stack[top]=(int)(post[tmp]-48); //type casting the string to its integer

value

}

void evaluate(char c) //evaluate function

{

int a,b,ans; //variables used

a=stack[top]; //a takes the value stored in the top

stack[top]='\0'; //make the stack top NULL as its a string

top--; //decrement top's value

b=stack[top]; //put the value at new top to b

stack[top]='\0'; //make it NULL

top--; //decrement top

switch(c) //check operator been passed to evaluate

{

case '+': //addition

ans=b+a;

break;

case '-': //subtraction

ans=b-a;

break;

case '*': //multiplication

ans=b*a;

break;

case '/': //division

ans=b/a;

break;

case '^': //power

ans=b^a;

break;

default:

ans=0; //else 0

} munotes.in

## Page 56

56 top++; //increment top

stack[top]=ans; //store the answer at top

}

Questions:

1. Which of the following is an example for a postfix expression?

A. a*b(c+d)

B. abc*+de-+

C. +ab

D. a+b-c

2. While evaluating a postfix expression, when an operator is encountered,

what is the correct operation to be performed?

A. Push it directly on to the stack

B. Pop 2 operands, evaluate them and push the result on to the

stack

C. Pop the entire stack

D. Ignore the operator

3. What is the result of the following postfix expression?

ab*cd*+ where a=2,b=2,c=3,d=4.

A. 16

B. 12

C. 14

D. 10

4. Evaluate and write the result for the following postfix expression

abc*+de*f+g*+ where a=1, b=2, c=3, d=4, e=5, f=6, g=2.

A. 61

B .59

C. 60

D. 55

5. What is the other name for a postfix expression?

A. Normal polish Notation

B. Reverse polish Notation

C. Warsaw notation

D. Infix notation

6. Data Structure required to evaluate postfix expression is __________.

A. Heap

B. Stack

C. Pointer

D. Queue munotes.in

## Page 57

57Practical No: 4

Aim: Implement program for balancing of parenthesis.

Objective: To understand applications of stack in balancing of parenthesis

and to implement program for same using stack.

Theory:

A stack can be used for syntax verification of the arithmetic

expression for ensuring that for each left parenthesis in the expression

there is a corresponding right parenthesis.

To accomplish this task the expression is scanned from left to right

character by character.

1. Whenever a left parenthesis is encountered, we push it onto the

stack. It could be of any type, square brace [, round brace (, or

curly brace {.

2. When we encounter a right parenthesis], or), or}, the status of the

stack is checked.

a. If the stack is empty and we have a right parenthesis in the

expression that does not have corresponding left parenthesis

then there is mistake in expression.

b. If the stack is not empty, we will pop the topmost element from

the stack and compare it with the scanned right parenthesis.

3. If both the parenthesis is not of t h e s a m e t y p e t h e n i t s h o w s a

mistake in expression. But if both parentheses are of same type,

then same procedure is repeated until the whole expression is

scanned and stack is empty

Let us check the order of brackets in an expression I:

I= [(5+6)*7-{7/4}+(3*2)-8]

Character scanned Status of stack

[ [

( [(

) [

{ [{

} [

( [(

) [

] Null munotes.in

## Page 58

58Expression is balanced as every left parenthesis is having corresponding

right parenthesis.

Algorithm:

Algorithm to check balanced parenthesis

Step 1: Initialize a character stack. Set top pointer of stack to -1.

Step 2: Find length of input string using strlen function and store it in an

integer variable "length".

Step 3: Using a for loop, traverse input string from index 0 to length-1.

Step 4: a.If current character is open parenthesis, then push it inside stack.

b. If current character is closing parenthesis, then pop a character

from stack.

c. If stack is empty, then input string is invalid, it means there is

no matching opening parenthesis corresponding to closing parenthesis.

Step 5: After complete traversal of input string, If stack is empty then

input expression is a Valid expression otherwise Invalid.

Program:

#include

#include

#define MAX 20

struct stack

{

char stk[MAX];

int top;

}s;

void push(char item)

{

if (s.top == (MAX - 1))

printf ("Stack is Full\n");

else

{

s.top = s.top + 1; // Push the char and increment top

s.stk[s.top] = item;

}

}

void pop()

{ munotes.in

## Page 59

59if (s.top == - 1)

{

printf ("Stack is Empty\n");

}

else

{

s.top = s.top - 1; // Pop the char and decrement top

}

}

int main()

{

char exp[MAX];

int i = 0;

s.top = -1;

printf("\nINPUT THE EXPRESSION : ");

scanf("%s", exp);

for(i = 0;i < strlen(exp);i++)

{

if(exp[i] == '(' || exp[i] == '[' || exp[i] == '{')

{

push(exp[i]); // Push the open bracket

continue;

}

else if(exp[i] == ')' || exp[i] == ']' || exp[i] == '}') // If a closed

bracket is encountered

{

if(exp[i] == ')')

{

if(s.stk[s.top] == '(')

{

pop(); // Pop the stack until closed bracket is

found

}

else

{

printf("\nUNBALANCED

EXPRESSION\n");

break;

}

}

if(exp[i] == ']')

{

if(s.stk[s.top] == '[') munotes.in

## Page 60

60{

pop(); // Pop the stack until closed bracket is found

}

else

{

printf("\nUNBALANCED

EXPRESSION\n");

break;

}

}

if(exp[i] == '}')

{

if(s.stk[s.top] == '{')

{

pop(); // Pop the stack until closed bracket is found

}

else

{

printf("\nUNBALANCED

EXPRESSION\n");

break;

}

}

}

}

if(s.top == -1)

{

printf("\nBALANCED EXPRESSION\n"); // Finally if the

stack is empty, display that the expression is balanced

}

getch();

}

Questions:

1. In balancing parentheses algor ithm, the string is read from?

A. Right to left

B. Left to right

C. Center to right

D. Center to left

munotes.in

## Page 61

612. Which is the most appropriate data structure for applying balancing of

parentheses algorithm?

A. Stack

B. Queue

C. Tree

D. Graph

3. Which of the following does the balancing symbols algorithm include?

A. Balancing double quotes

B. Balancing single quotes

C. Balancing operators and brackets

D. Balancing parentheses, brackets and braces

4. What should be done when an opening parenthesis is read in a

balancing symbols algorithm?

A. Push it on to the stack

B. Throw an error

C. Ignore the parentheses

D. Pop the stack

5. If the corresponding end bracket/braces/parentheses is encountered,

which of the following is done?

A. Push it on to the stack

B. Pop the stack

C. Throw an error

D. Treated as an exception

6. Consider the usual algorithm for determining whether a sequence of

parentheses is balanced. The maximum number of parentheses that appear

on the stack at any one time when the algorithm analyzes: (()(())(())) are:

A. 1

B. 2

C. 3

D. 4 or more

Self-Learning Topic:

Conversion of infix notation to postfix notation:

When the operator is written in between the operands, then it is

known as infix notation. The postfix expression is an expression in which

the operator is written after the operands. Postfix notation is very easily

implemented and does not have overhead of parentheses and there is no

complication of precedence of one operator over the other. To convert

infix expression to postfix expression stack data structure will be used.

munotes.in

## Page 62

62Module IV

Data structures

Form No .: 5

1. Point: To implement a singly linked list using C / C ++

Objective: Get familiar with the List interface. Understand how to write a

matrix based on.

Theory:

● The individually linked list can be defined as the collection of

ordered sets of elements. The number of items may vary according

to the needs of the program. A node in the individual linked list

consists of two parts: data part and link part. The data part of the

node stores the actual information that will be represented by the

node, while the link part of the node stores the address of its

immediate successor.

● One-way strings or individually linked lists can only be traversed

in one direction. In other words, we can say that each node

contains only the next pointer, so we cannot traverse the list in the

reverse direction.

● Consider an example where the student's grades in three subjects

are stored in a linked list as shown in the figure.

In the figure above, the arrow repres ents the links. The data part of

each node contains the marks obtained by the student in the various

subjects. The last node in the list is identified by the null pointer in the

address part of the last node. We can have all the elements we need, in the

data part of the list.

munotes.in

## Page 63

63Algorithm:

Operations on a single linked list

The following operations are performed on a single linked list

● Insertion

● deletion

● Show

Before implementing the actual operations, we must first set up an

empty list. First, perform the following steps before implementing the

actual operations.

● Step 1: Include all header files used in the program.

● Step 2: Declare all user-defined functions.

● Step 3: Define a node structure with two-membered data, then

● Step 4: Define a 'head' node pointer and set it to NULL.

● Step 5: Implement the main method by displaying the operations

menu and make appropriate function calls in the main method to

perform the operation selected by the user.

Insertion

In a single linked list, the insert operation can be performed in

three ways. Are the following...

1. Insert at the beginning of the list

2. Enter to the end of the list

3. Insert in a specific position in the list

Insert at the beginning of the list

We can use the following steps to insert a new node at the

beginning of the single linked list ...

● Step 1: Create a new node with a certain value.

● Step 2: Check if the list is empty (head == NULL)

● Step 3: If blank, configure newNode → next = NULL and head =

newNode.

● Step 4: If it's not empty, configure newNode → next = head and

head = new knot.

Enter to the end of the list

We can use the following steps to insert a new node at the end of

the unique linked list ...

● Step 1: Create a new node with a certain value e newNode → next

as NULL. munotes.in

## Page 64

64● Step 2: Check if the list is empty (head == NULL).

● Step 3: If empty, set head = newNode.

● Step 4: If it is not empty, define a node pointer temperature and

initialize with head.

● Step 5: Keep moving the temperature to the next node until it

reaches the last node in the list (until temperature → next equal

to NULL).

● Step 6 - Set up temperature → next = newNode.

Insert in a specific position in the list (after a node)

We can use the following steps to insert a new node after a node in

the single linked list ...

● Step 1: Create a new node with a certain value.

● Step 2: Check if the list is empty (head == NULL)

● Step 3: If blank, configure newNode → next = NULL and head =

newNode.

● Step 4: If it is not empty, define a node pointer temperature and

initialize with head.

● Step 5: Keep moving the temperature on its next node until it

reaches the node, after which we wa nt to insert the new node (until

temp1 → data is equal to location, here location is the value of the

node after which we want to insert the newNode).

● Step 6: Check each time the temperature has reached the last knot

or not. If the last node is reached, 'The specified node is not in the

list! Entry is not possible ! !! 'and terminate the function.

Otherwise, move the temperature to the next node.

● Step 7 - Finally, configure ' newNode → next = temperature →

next'S'temperature → next = newNode '

deletion

In a single linked list, the delete operation can be performed in

three ways. Are the following...

1. Delete from the top of the list

2. Remove from the end of the list

3. Delete a specific node

Delete from the top of the list

We can use the following steps to remove a node from the

beginning of the unique linked list ... munotes.in

## Page 65

65● Step 1: Check if the list is empty (head == NULL)

● Step 2: If blank, display 'List is empty! Deletion is not possible and

the function ends.

● Step 3: If it is not empty, define a pointer to the 'temp' node and

initialize with head.

● Step 4: Check if the list has only one node ( temperature → next

== NULL)

● Step 5: If TRUE, set head = NULL and remove the temperature

(setting the conditions of the empty list)

● Step 6: If FALSE, set head = temperature → next and eliminates

temp.

Remove from the end of the list

We can use the following steps to remove a node from the end of the

unique linked list ...

● Step 1: Check if the list is empty (head == NULL)

● Step 2: If blank, display 'List is empty! Deletion is not possible and

the function ends.

● Step 3: If it is not empty, define two pointers to the node "temp1"

and "temp2" and initialize "temp1" with head.

● Step 4: Check if the list has only one node ( temp1 → n e x t = =

NULL)

● Step 5: if it is TRUE. Then set head = NULL and remove temp1.

And finish the show. (Setting the empty list condition)

● Step 6: If it is FALSE. Then set 'temp2 = temp1' and move temp1

to your next node. Repeat the same until you reach the last node in

the list. (as far as temp1 → next == NULL)

● Step 7 - Finally, configure temp2 → n e x t = NULL and remove

temp1.

Remove a specific node from the list

We can use the following steps to remove a specific node from the unique

linked list ...

● Step 1: Check if the list is empty (head == NULL)

● Step 2: If blank, display 'List is empty! Deletion is not possible and

the function ends. munotes.in

## Page 66

66● Step 3: If it is not empty, define two pointers to the node "temp1"

and "temp2" and initialize "temp1" with head.

● Step 4: Continue moving temp1 until you reach the exact node to

be removed or the last node. And each time, set 'temp2 = temp1'

before moving 'temp1' to your next node.

● Step 5: If the last node is reached, display 'The specified node is

not in the list! Cancellation is not possible !!! '. And finish the

show.

● Step 6: If the exact node we want to remove is reached, check if

the list has only one node or not

● Step 7: If the list has only one node and this is the node to remove,

set head = NULL and remove temp1 (free (temp1)).

● Step 8: If the list contains multiple nodes, check if temp1 is the

first node in the list (temp1 == head).

● Step 9: If temp1 is the first node, move your head to the next node

(head = head → forward ) and remove temp1.

● Step 10: If temp1 is not the first n ode, check if it is the last node in

the list ( temp1 → next == NULL ).

● Step 11: If temp1 is the last node, configure temp2 → n e x t =

NULL and remove temp1 (free (temp1)).

● Step 12: If temp1 is not the first node and not the last node, set

temp2 → next = temp1 → next and remove temp1 (free (temp1)).

View a single linked list

We can use the following steps to view the elements of a single linked list

● Step 1: Check if the list is empty (head == NULL)

● Step 2: If blank, display "List is empty!" and terminate the

function.

● Step 3: If it is not empty, define a pointer to the 'temp' node and

initialize with head.

● Step 4: Keep showing temperature → data with an arrow (--->)

until the temperature reaches the last knot

● Step 5 - Finally it shows temperature → d a t a w i t h t h e a r r o w

pointing to NULL ( temp → data ---> NULL ).

munotes.in

## Page 67

67Program:

#include

#include

#include

void insertAtBeginning (int);

void insertAtEnd (int);

void insertBetween (int, int, int);

blank display ();

void removeBeginning ();

void removeEnd ();

void removeSpecific (int);

Structure node

{

int data;

struct Node * next;

} * head = NULL;

main vacuum ()

{

int choice, value, choice1, loc1, loc2;

clrscr ();

while (1) {

mainMenu: printf ("\ n \ n ****** MENU ****** \ n1. Insert \ n2. Show \

n3. Delete \ n4. Exit \ nEnter your choice:");

scanf ("% d", & option);

change (choice)

{

case 1: printf ("Insert the value to insert:");

s c a n f ( " % d " , & v a l u e ) ;

w h i l e ( 1 ) {

printf ("Where do you want to enter: \ n1. At the beginning \ n2. At the

end \ n3. Enter \ nPlease enter your choice:"); munotes.in

## Page 68

68 s c a n f ( " % d " , & c h o i c e 1 ) ;

s w i t c h ( o p t i o n 1 )

{

c a s e 1 : i n s e r t A t B e g i n n i n g ( v a l u e ) ;

b r e a k t i m e ;

c a s e 2 : i n s e r t A t E n d ( v a l u e ) ;

b r e a k t i m e ;

c a s e 3 : p r i n t f ( " I n s e r t t h e t w o v a l u e s w h e r e y o u w a n t t o i n s e r t : " ) ;

s c a n f ( " % d % d " , & l o c 1 , & l o c 2 ) ;

i n s e r t B e t w e e n ( v a l u e , l o c 1 , l o c 2 ) ;

b r e a k t i m e ;

d e f a u l t : p r i n t f ( " \ n I n c o r r e c t e n t r y ! T r y a g a i n ! \ n \ n " ) ;

g o t o t h e m a i n m e n u ;

}

g o t o s u b M e n u E n d ;

}

s u b m e n u E n d :

b r e a k t i m e ;

case 2: display ();

b r e a k t i m e ;

case 3: printf ("How do you want to remove: \ n1. From the beginning \

n2. From the end \ n3. Specific \ nPlease enter your choice:");

s c a n f ( " % d " , & c h o i c e 1 ) ;

s w i t c h ( o p t i o n 1 )

{

c a s e 1 : r e m o v e B e g i n n i n g ( ) ;

b r e a k t i m e ;

c a s e 2 : r e m o v e E n d ( ) ;

b r e a k t i m e ;

c a s e 3 : p r i n t f ( " E n t e r t h e value you want to remove:");

s c a n f ( " % d " , & l o c 2 ) ; munotes.in

## Page 69

69 r e m o v e S p e c i f i c ( l o c 2 ) ;

b r e a k t i m e ;

d e f a u l t : p r i n t f ( " \ n I n c o r r e c t e n t r y ! T r y a g a i n ! \ n \ n " ) ;

g o t o t h e m a i n m e n u ;

}

b r e a k t i m e ;

case 4: exit (0);

default: printf ("\ nIncorrect entry !!! Try again !! \ n \ n");

}}}

void insertAtBeginning (int value)

{

struct Node * newNode;

newNode = (struct Node *) ma lloc (sizeof (struct Node));

newNode-> data = value;

yes (head == NULL)

{

newNode-> next = NULL;

head = newNode;

}

the rest

{

newNode-> next = head;

head = newNode;

}

printf ("\ nA node entered !!! \ n");

}

void insertAtEnd (int value)

{

struct Node * newNode;

newNode = (struct Node *) ma lloc (sizeof (struct Node)); munotes.in

## Page 70

70 newNode-> data = value;

newNode-> next = NULL;

yes (head == NULL)

h e a d = n e w N o d e ;

the rest

{

struct Node * temp = head;

while (temp-> next! = NULL)

t e m p = t e m p - > n e x t ;

temp-> next = newNode;

}

printf ("\ nA node entered !!! \ n");

}

void insertBetween (int value, int loc1, int loc2)

{

struct Node * newNode;

newNode = (struct Node *) ma lloc (sizeof (struct Node));

newNode-> data = value;

yes (head == NULL)

{

newNode-> next = NULL;

head = newNode;

}

the rest

{

struct Node * temp = head;

while (temp-> data! = loc1 && temp-> data! = loc2)

t e m p = t e m p - > n e x t ;

newNode-> next = temp-> next;

temp-> next = newNode; munotes.in

## Page 71

71 }

printf ("\ nA node entered !!! \ n");

}

void removeBeginning ()

{

yes (head == NULL)

p r i n t f ( " \ n \ n T h e l i s t i s e m p t y ! " ) ;

the rest

{

struct Node * temp = head;

yes (header-> next == NULL)

{

h e a d = N U L L ;

f r e e ( t e m p e r a t u r e ) ;

}

the rest

{

h e a d = t e m p - > n e x t ;

f r e e ( t e m p e r a t u r e ) ;

p r i n t f ( " \ n A n o d e r e m o v e d ! ! ! \ n \ n " ) ;

}}}

void removeEnd ()

{

yes (head == NULL)

{

printf ("\ nThe list is empty! \ n");

}

the rest

{ munotes.in

## Page 72

72 struct Node * temp1 = head, * temp2;

yes (header-> next == NULL)

h e a d = N U L L ;

the rest

{

w h i l e ( t e m p 1 - > n e x t ! = N U L L )

{

t e m p 2 = t e m p 1 ;

t e m p 1 = t e m p 1 - > n e x t ;

}

t e m p 2 - > n e x t = N U L L ;

}

free (temp1);

printf ("\ nA node removed !!! \ n \ n");

}

}

void removeSpecific (int delValue)

{

struct Node * temp1 = head, * temp2;

while (temp1-> data! = delValue)

{

if (temp1 -> next == NULL) {

p r i n t f ( " \ n N o n o d e s f o u n d i n t h e l i s t ! ! ! " ) ;

g o t o f u n c t i o n E n d ;

}

temp2 = temp1;

temp1 = temp1 -> next;

}

temp2 -> next = temp1 -> next;

free (temp1); munotes.in

## Page 73

73 printf ("\ nA node removed !!! \ n \ n");

End function:

}

blank screen ()

{

yes (head == NULL)

{

printf ("\ nThe list is empty \ n");

}

the rest

{

struct Node * temp = head;

printf ("\ n \ nThe elements of the list are - \ n");

while (temp-> next! = NULL)

{

p r i n t f ( " % d - - - > " , t e m p - > d a t a ) ;

t e m p = t e m p - > n e x t ;

}

printf ("% d ---> NULL", temp-> data);

}}

Production:

munotes.in

## Page 74

741) Search in an individually linked list

The search is performed to find the position of a particular item in

the list. Searching for any item in the list requires you to scroll through the

list and compare each item in the list with the specified item. If the

element matches one of the elements in the list, the function returns the

position of the element.

Algorithm:

● Step 1: SET PTR = HEAD

● Step 2: Set I = 0

● STEP 3: IF PTR = NULL

● WRITE "EMPTY LIST" GOTO STEP 8 END OF YES STEP 4:

REPEAT STEPS 5 TO 7 UNTIL PTR! = NULL

● STEP 5: if ptr → data = item

● write i + 1 End of IFSTEP 6: I = I + 1

● STEP 7: PTR = PTR → NEXT

● [END OF LOOP] STEP 8: EXIT

Program:

#include

#include

empty create (int);

empty Research();

structure node

{

int data;

next structure node *;

};

knot structure * head;

empty principal ()

{

int choice, object, loc;

do

{

printf ("\ n1.Create \ n2.Search \ n3.Sexit \ n4.Enter your choice?"); munotes.in

## Page 75

75 scanf ("% d", & option);

change (choice)

{

Case 1:

printf ("\ nInsert element \ n");

scanf ("% d", & element);

create (element);

break time;

case 2:

Research();

case 3:

output (0);

break time;

default:

printf ("\ nPlease enter a valid option \ n");

}

} while (choice! = 3);

}

create empty (int element)

{

structure node * ptr = (structure node *) malloc (size of (structure node

*));

yes (ptr == NULL)

{

printf ("\ nOVERFLOW \ n");

}

the rest

{

ptr-> data = element;

ptr-> next = head;

head = ptr;

printf ("\ nNode inserted \ n"); munotes.in

## Page 76

76 }}

empty Research()

{

struct node * ptr;

int element, i = 0, flag;

ptr = head;

yes (ptr == NULL)

{

printf ("\ nEmpty list \ n");

}

the rest

{

printf ("\ nPlease enter the element you want to search for? \ n");

scanf ("% d", & element);

while (ptr! = NULL)

{

if (ptr-> data == element)

{

printf ("article found at location% d", i + 1);

flag = 0;

}

the rest

{

flag = 1;

}

i ++;

ptr = ptr -> next;

}

yes (flag == 1)

{

printf ("Item not found \ n");

}}} munotes.in

## Page 77

77Production:

2) Individually count the total number of nodes in the linked list

Algorithm:

%%Entrance : parent node of the linked list

Start:

count 0

If (test! = NULL) then

head temperature

While (temp! = NULL) do

count ← count + 1

temperature ← temperature. following

Finish in the meantime

It will end if

write ('Total nodes in list =' + count)

end munotes.in

## Page 78

78Program:

#include

#include

/ * Structure of a node * /

node structure {

int data; // Data

next structure node *; // Address

}*head;

void createList (int n);

int countNodes ();

void displayList ();

main integer ()

{

int n, total;

/ *

* Create a linked list of n nodes

* /

printf ("Enter the total number of nodes:");

scanf ("% d", & n);

createList (n);

printf ("\ nData in the list \ n");

displayList ();

/ * Counts the number of nodes in the list * /

total = countNodes ();

printf ("\ nTotal number of nodes =% d \ n", total);

returns 0;

}

/ *

* Create a list of n nodes

* / munotes.in

## Page 79

79empty createList (int n)

{

struct node * newNode, * temp;

int data, i;

head = (structure node *) ma lloc (size of (structure node));

/ *

* If you cannot allocate memory for the head root node

* /

yes (head == NULL)

{

printf ("Unable to allocate memory");

}

the rest

{

/ *

* Read data from user node

* /

printf ("Enter data for node 1:");

scanf ("% d", & data);

head-> data = data; // Link the data field with the data

head-> next = NULL; // Map the address field to NULL

temperature = head;

/ *

* Create n nodes and add to linked list

* /

for (i = 2; i <= n; i ++)

{

newNode = (structure node *) mall oc (size of (structure node));

/ * If no memory is allocated for newNode * /

yes (newNode == NULL)

{

printf ("Unable to allocate memory"); munotes.in

## Page 80

80 break time;

}

the rest

{

printf ("Insert data for node% d:", i);

scanf ("% d", & data);

newNode-> data = data; // Associate the data field of newNode with the

data

newNode-> next = NULL; // Associate the address field of newNode with

NULL

temp-> next = newNode; // Associate the previous node, ie temporarily

with the new node

temp = temp-> next;

}}

printf ("SIMPLE CONNECTED LIST CREATED SUCCESSFULLY \

n");

}}

/ *

* Counts the total number of nodes in the list

* /

int countNodes ()

{

int count = 0;

struct node * temp;

temperature = head;

while (temp! = NULL)

{

count ++;

temp = temp-> next;

}

counting of returns;

}

/ * munotes.in

## Page 81

81 * Show the complete list

* /

empty displayList ()

{

struct node * temp;

/ *

* If the list is empty, ie head = NULL

* /

yes (head == NULL)

{

printf ("The list is empty");

}

the rest

{

temperature = head;

while (temp! = NULL)

{

printf ("Data =% d \ n", temp-> data); // Print the data of the current node

temp = temp-> next; // Go to the next node

}}}

Production:

munotes.in

## Page 82

823) Reverse a linked list

Given a pointer to the parent node of a linked list, the task is to

reverse the linked list. We need to reverse the list by changing the links

between the nodes.

Examples of :

Entrance : Head of the next linked list

1-> 2-> 3-> 4-> NULL

Production : the linked list must be changed to,

4-> 3-> 2-> 1-> NULL

Entrance : Head of the next linked list

1-> 2-> 3-> 4-> 5-> NULL

Production : the linked list must be changed to,

5-> 4-> 3-> 2-> 1-> NULL

Entrance : NOTHING

Production : NOTHING

Entrance : 1-> NULL

Production : 1-> NULL

Iterative method

1. Initializes three pointers prev as NULL, curr as head and next as

NULL.

2. Iterate through the linked list. In a loop, do the following. // Before

changing the next one from the current one, // memorize the next node

next = curr-> next // Now change the next one from the current one //

This is where the actual inversion ta kes place curr-> next = previous //

Move previous and current one step forward previous = curr curr =

next

Program:

#include

using the std namespace;

/ * Link List Node * /

node structure {

int data;

struct Node * next;

Node (int data) munotes.in

## Page 83

83{

this-> data = data;

next = NULL;

}

};

struct LinkedList {

Knot * head;

LinkedList () {head = NULL; }

/ * Function to invert the linked list * /

reverse vacuum ()

{

// Initialize current, previous and

// next pointers

Current * node = head;

Node * previous = NULL, * next = NULL;

while (current! = NULL) {

// Memorize the next one

next = current-> next;

// Pointer to the current inverse node

current-> next = previous;

// Move pointers one position forward.

previous = current;

current = next;

}

head = front;

}

/ * Function to print the linked list * /

blank print ()

{ munotes.in

## Page 84

84 struct Node * temp = head;

while (temp! = NULL) {

cout << temp-> data << "";

temp = temp-> next;

}

}

empty push (int data)

{

Node * temp = new Node (data);

temp-> next = head;

head = temperature;

}

};

/ * Driver code * /

main integer ()

{

/ * Start with empty list * /

LinkedList ll;

ll.push (20);

ll. press (4);

ll.push (15);

ll.push (85);

cout << "Linked list given \ n";

ll.print ();

ll.reverse ();

cout << "\ nInverted linked list \ n";

ll.print (); munotes.in

## Page 85

85 returns 0;

}

Production:

Linked list given

85 15 4 20

Inverted linked list

20 4 15 85

Question:

1. What does the following function do for a given Linked List with

first node as head?

void fun1(struct node* head)

{

if(head == NULL)

return;

fun1(head->next);

printf("%d ", head->data);

}

1. A linear collection of data elements where the linear node is given

by means of a pointer is called?

A. linked list

B. node list

C. primitive list

D. None of these

munotes.in

## Page 86

862. What is the output of the following function for starting pointing to the

first node of the following linked list? 1->2->3->4->5->6

void fun(struct node* start)

{

if(start == NULL)

return;

printf("%d ", start->data);

if(start->next != NULL )

fun(start->next->next);

printf("%d ", start->data);

}

A. 1 4 6 6 4 1

B. 1 3 5 1 3 5

C. 1 2 3 5

D. 1 3 5 5 3 1

3. Linked lists are not suitable for the implementation of?

A. Insertion sort

B. Radix sort

C. Polynomial manipulation

D. Binary search

4. Which of these is an ap plication of linked lists?

A. To implement file systems

B. For separate chaining in hash-tables

C. To implement non-binary trees

D. All of the mentioned

2. Objective: To implement a circular linked list using C / C ++

Objective: To make it convenient for the operating system to use a circular

list so that when you reach the end of the list you can scroll to the top of

the list. munotes.in

## Page 87

87Theory:

What is a circular linked list?

● In a single linked list, each node points to the next node in the

sequence and the last node poin ts to NULL. But in a circular

linked list, each node points to the next node in the sequence, but

the last node points to the first node in the list.

● A circular linked list is a sequence of elements where each element

has a link to the next element in the sequence and the last element

has a link to the first element.

● This means that the circular link ed list is similar to the single

linked list, except that the last node points to the first node in the

list.

Example

Operations

In a circular linked list, we do the following ...

1. Insertion

2. deletion

3. Show

Before implementing the actual operations, we must first set up an

empty list. First, perform the following steps before implementing the

actual operations.

● Step 1: Include all header files used in the program.

● Step 2: Declare all user-defined functions.

● Step 3: Define a node structure with two-membered data, then

● Step 4: Define a 'head' node pointer and set it to NULL.

● Step 5: Implement the main method by displaying the operations

menu and make appropriate function calls in the main method to

perform the operation selected by the user.

munotes.in

## Page 88

88Insertion

In a circular linked list, the insert operation can be performed in three

ways. Are the following...

1. Insert at the beginning of the list

2. Enter to the end of the list

3. Insert in a specific position in the list

Insert at the beginning of the list

We can use the following steps to insert a new node at the beginning of

the linked circular list ...

● Step 1: Create a new node with a certain value.

● Step 2: Check if the list is empty (head == NULL)

● Step 3: If empty, set head = newNode and newNode → n e x t =

head.

● Step 4: If it is not empty, define a pointer to the 'temp' node and

initialize with 'head'.

● Step 5: Keep moving 'temp' to the next node until it reaches the last

node (up to ' temperature → next == head ').

● Step 6 - Set ' newNode → n e x t = h e a d ' , ' h e a d = n e w N o d e

'e'temperature → next = head '.

Enter to the end of the list

We can use the following steps to insert a new node at the end of the

linked circular list ...

● Step 1: Create a new node with a certain value.

● Step 2: Check if the list is empty (head == NULL).

● Step 3: If empty, set head = newNode and newNode → n e x t =

head.

● Step 4: If it is not empty, define a node pointer temperature and

initialize with head.

● Step 5: Keep moving the temperature to the next node until it

reaches the last node in the list (until temperature → n e x t = =

head).

● Step 6 - Set up temperature → next = newNode e newNode →

next = head.

Insert in a specific position in the list (after a node)

We can use the following steps to insert a new node after a node in the

circular linked list ...

● Step 1: Create a new node with a certain value. munotes.in

## Page 89

89● Step 2: Check if the list is empty (head == NULL)

● Step 3: If empty, set head = newNode and newNode → n e x t =

head.

● Step 4: If it is not empty, define a node pointer temperature and

initialize with head.

● Step 5: Keep moving the temperature on its next node until it

reaches the node after which we want to insert the new node (up to

temp1 → data is equal to location, here location is the value of the

node after which we want to insert the newNode).

● Step 6: Check each time if the temperature has been reached or not

until the last node. If the last node is reached, 'The specified node

is not in the list! Insertion no t possible !!! 'and terminate the

function. Otherwise, move the temperature to the next node.

● Step 7: If the temperature you reach the exact node after which you

want to insert the newNode and then check if it is the last node

(temp → next == head).

● Step 8: If the temperature is the last knot, set temperature → next

= newNode e newNode → next = head.

● Step 8: If the temperature is not the last knot, set newNode → next

= temperature → next Yup temperature → next = newNode.

deletion

In a circular linked list, the delete operation can be performed in three

ways, which are as follows ...

1. Delete from the top of the list

2. Remove from the end of the list

3. Delete a specific node

Delete from the top of the list

We can use the following steps to remove a node from the beginning of

the circular linked list ...

● Step 1: Check if the list is empty (head == NULL)

● Step 2: If blank, display 'List is empty! Deletion is not possible and

terminate the function.

● Step 3: If it is not empty, define two node pointers "temp1" and

"temp2" and initialize both "tem p1" and "temp2" with head.

● Step 4: Check if the list has only one node ( temp1 → n e x t = =

head) munotes.in

## Page 90

90● Step 5: If TRUE, set head = NULL and remove temp1 (setting

conditions of empty list)

● Step 6: If it is FALSE, move temp1 until it reaches the last node.

(as far as temp1 → next == head)

● Step 7: Then set the head = temp2 → next , temp1 → next = test

and clear temp2.

Remove from the end of the list

We can use the following steps to remove a node from the end of the

linked circular list ...

● Step 1: Check if the list is empty (head == NULL)

● Step 2: If blank, display 'List is empty! Deletion is not possible and

terminate the function.

● Step 3: If it is not empty, define two pointers to the node "temp1"

and "temp2" and initialize "temp1" with head.

● Step 4: Check if the list has only one node ( temp1 → n e x t = =

head)

● Step 5: if it is TRUE. Then set head = NULL and remove temp1.

And finish the show. (Setting the empty list condition)

● Step 6: If it is FALSE. Then set 'temp2 = temp1' and move temp1

to your next node. Repeat the same until temp1 reaches the last

node in the list. (as far as temp1 → next == head)

● Step 7 - Set up temp2 → next = test and delete temp1.

Remove a specific node from the list

We can use the following steps to remove a specific node from the linked

circular list ...

● Step 1: Check if the list is empty (head == NULL)

● Step 2: If blank, display 'List is empty! Deletion is not possible and

terminate the function.

● Step 3: If it is not empty, define two pointers to the node "temp1"

and "temp2" and initialize "temp1" with head.

● Step 4: Continue moving temp1 until you reach the exact node to

be removed or the last node. And each time, set 'temp2 = temp1'

before moving 'temp1' to your next node.

● Step 5: If the last node is reached, display 'The specified node is

not in the list! It cannot be can celed !!! '. And finish the show. munotes.in

## Page 91

91● Step 6: If the exact node we want to remove is reached, check if

the list has only one node ( temp1 → next == head)

● Step 7: If the list has only one node and this is the node to remove,

set head = NULL and remove temp1 (free (temp1)).

● Step 8: If the list contains multiple nodes, check if temp1 is the

first node in the list (temp1 == head).

● Step 9: If temp1 is the first node, set temp2 = head and keep

moving temp2 to the next node un til temp2 reaches the last node.

Then set head = head → f o r w a r d , temp2 → next t = head and

delete temp1.

● Step 10: If temp1 is not the first n ode, check if it is the last node in

the list ( temp1 → next == head ).

● Step 1 1- If temp1 is the last node, configure temp2 → n e x t =

head and remove temp1 (free (temp1)).

● Step 12: If temp1 is not the first node and not the last node, set

temp2 → next = temp1 → next and remove temp1 (free (temp1)).

View a circular linked list

We can use the following steps to view the elements of a circular linked

list ...

● Step 1: Check if the list is empty (head == NULL)

● Step 2: If blank, show 'List is empty !!!' and terminate the function.

● Step 3: If it is not empty, define a pointer to the 'temp' node and

initialize with head.

● Step 4: Keep showing temperature → data with an arrow (--->)

until the temperature reaches the last knot

● Step 5 - Finally it shows temperature → data with arrow pointing

to head → data .

Program:

#include

#include

void insertAtBeginning (int);

void insertAtEnd (int);

void insertAtAfter (int, int);

void deleteBeginning (); munotes.in

## Page 92

92void deleteEnd ();

void deleteSpecific (int);

blank display ();

Structure node

{

int data;

struct Node * next;

} * head = NULL;

main vacuum ()

{

int choice1, choice2, value, position;

clrscr ();

while (1)

{

printf ("\ n *********** MENU ************* \ n");

printf ("1. Enter \ n2. Delete \ n3. Screen \ n4. Exit \ nEnter your

choice:");

scanf ("% d", & choice1);

Change ()

{

case 1: printf ("Insert the value to insert:");

scanf ("% d", & value);

while (1)

{

printf ("\ nSelect from the following insert options \ n");

printf ("1. At the beginning \ n2. At the end \ n3. After a node \ n4. Cancel

\ nEnter your choice:");

scanf ("% d", & choice2);

switch (option 2)

{

case 1: insertAtBeginning (value); munotes.in

## Page 93

93 break time;

case 2: insertAtEnd (value);

break time;

case 3: printf ("Enter the position after which you want to insert:");

scanf ("% d", & location);

insertAfter (value, position);

break time;

case 4: go to EndSwitch;

default: printf ("\ nSelect the correct insert option! \ n");

}

}

case 2: while (1)

{

printf ("\ nSelect from the following delete options \ n");

printf ("1. At the beginning \ n2. At the end \ n3. Specific node \ n4.

Cancel \ nEnter your choice:");

scanf ("% d", & choice2);

switch (option 2)

{

case 1: deleteBeginning ();

break time;

case 2: deleteEnd ();

break time;

case 3: printf ("Enter the value of the node to be removed:");

scanf ("% d", & location);

deleteSpecic (location);

break time;

case 4: go to EndSwitch;

default: printf ("\ nSelect the correct delete option! \ n");

}

} munotes.in

## Page 94

94 Limit switch: pause;

case 3: display ();

break time;

case 4: exit (0);

default: printf ("\ nSelect the correct option!");

}}}

void insertAtBeginning (int value)

{

struct Node * newNode;

newNode = (struct Node *) malloc (sizeof (struct Node));

newNode -> data = value;

yes (head == NULL)

{

head = newNode;

newNode -> next = head;

}

the rest

{

struct Node * temp = head;

while (temp -> next! = head)

temp = temp -> next;

newNode -> next = head;

head = newNode;

temp -> next = head;

}

printf ("\ nThe entry was successful!");

}

void insertAtEnd (int value)

{

struct Node * newNode; munotes.in

## Page 95

95 newNode = (struct Node *) ma lloc (sizeof (struct Node));

newNode -> data = value;

yes (head == NULL)

{

head = newNode;

newNode -> next = head;

}

the rest

{

struct Node * temp = head;

while (temp -> next! = head)

temp = temp -> next;

temp -> next = newNode;

newNode -> next = head;

}

printf ("\ nThe entry was successful!");

}

void insertAfter (int value, int location)

{

struct Node * newNode;

newNode = (struct Node *) ma lloc (sizeof (struct Node));

newNode -> data = value;

yes (head == NULL)

{

head = newNode;

newNode -> next = head;

}

the rest

{

struct Node * temp = head; munotes.in

## Page 96

96 while (temp -> data! = location)

{

yes (temp -> next == head)

{

printf ("The indicated node is not in the list !!!");

go to EndFunction;

}

the rest

{

temp = temp -> next;

}

}

newNode -> next = temp -> next;

temp -> next = newNode;

printf ("\ nThe entry was successful!");

}

Final function:

}

void deleteBeginning ()

{

yes (head == NULL)

printf ("The list is empty! Could not delete it!");

the rest

{

struct Node * temp = head;

yes (temp -> next == head)

{

head = NULL;

free (temperature);

} munotes.in

## Page 97

97 the rest{

head = head -> forward;

free (temperature);

}

printf ("\ n Deletio n successful !!!");

}

}

void deleteEnd ()

{

yes (head == NULL)

printf ("The list is empty! Could not delete it!");

the rest

{

struct Node * temp1 = head, temp2;

yes (temp1 -> next == head)

{

head = NULL;

free (temp1);

}

the rest{

while (temp1 -> next! = head) {

temp2 = temp1;

temp1 = temp1 -> next;

}

temp2 -> next = head;

free (temp1);

}

printf ("\ n Deletio n successful !!!");

}

} munotes.in

## Page 98

98void deleteSpecific (int delValue)

{

yes (head == NULL)

printf ("The list is empty! Could not delete it!");

the rest

{

struct Node * temp1 = head, temp2;

while (temp1 -> data! = delValue)

{

yes (temp1 -> next == head)

{

printf ("\ nThe indicated node is not in the list !!!");

go to FineFunction;

}

the rest

{

temp2 = temp1;

temp1 = temp1 -> next;

}

}

if (temp1 -> next == head) {

head = NULL;

free (temp1);

}

the rest{

yes (temp1 == head)

{

temp2 = head;

while (temp2 -> next! = head)

temp2 = temp2 -> next; munotes.in

## Page 99

99 head = head -> forward;

temp2 -> next = head;

free (temp1);

}

the rest

{

yes (temp1 -> next == head)

{

temp2 -> next = head;

}

the rest

{

temp2 -> next = temp1 -> next;

}

free (temp1);

}

}

printf ("\ n Deletio n successful !!!");

}

End function:

}

blank screen ()

{

yes (head == NULL)

printf ("\ nList is empty !!!");

the rest

{

struct Node * temp = head;

printf ("\ nThe elements of the list are: \ n");

while (temp -> next! = head) munotes.in

## Page 100

100 {

printf ("% d --->", temp -> data);

}

printf ("% d --->% d", temp -> data, test -> data);

}}

Production

1) Search the individually linked circular list

Searching in an individually linked circular list must traverse the

list. The element to find in the list matches the data for each node in the

list once, and if a match is found, the position of that element is returned,

otherwise -1 is returned.

Algorithm:

● Step 1: SET PTR = HEAD

● Step 2: Set I = 0

● STEP 3: IF PTR = NULL

● WRITE "EMPTY LIST" GO TO STEP 8 END YES

PHASE 4: IF HEAD → DATA = ARTICLE

● WRITE i + 1 RETURN [END OF S] STEP 5: REPEAT STEPS 5

TO 7 UNTIL PTR-> next! = Head

● STEP 6: if ptr → date = article

● write i + 1 RETURN of IF STEP 7: I = I + 1

● STEP 8: PTR = PTR → NEXT

● [END OF LOOP] STEP 9: EXIT munotes.in

## Page 101

101Program:

#include

#include

create void (int);

empty search ();

structure node

{

int data;

next structure node *;

};

knot structure * head;

main vacuum ()

{

int choice, object, loc;

do

{

printf ("\ n1.Create \ n2.Search \ n3.Sexit \ n4.Enter your choice?");

scanf ("% d", & option);

change (choice)

{

Case 1:

printf ("\ nInsert element \ n");

scanf ("% d", & element);

create (element);

break time;

case 2:

Research();

case 3:

output (0);

break time;

default:

printf ("\ nPlease enter a valid option \ n"); munotes.in

## Page 102

102 }

} while (choice! = 3);

}

create empty (int element)

{

structure node * ptr = (structure node *) malloc (size of (structure node));

struct node * temp;

yes (ptr == NULL)

{

printf ("\ nOVERFLOW \ n");

}

the rest

{

ptr-> data = element;

yes (head == NULL)

{

head = ptr;

ptr -> next = head;

}

the rest

{

temperature = head;

while (temp -> next! = head)

{

temp = temp -> next;

}

temp -> next = ptr;

ptr -> next = head;

}

printf ("\ nNode inserted \ n");

}}

stop searching () munotes.in

## Page 103

103{

struct node * ptr;

int element, i = 0, flag = 1;

ptr = head;

yes (ptr == NULL)

{

printf ("\ nEmpty list \ n");

}

the rest

{

printf ("\ nPlease enter the element you want to search for? \ n");

scanf ("% d", & element);

if (head -> data == element)

{

printf ("article found at location% d", i + 1);

flag = 0;

come back;

}

the rest

{

while (ptr-> next! = head)

{

if (ptr-> data == element)

{

printf ("article found at location% d", i + 1);

flag = 0;

come back;

}

the rest

{

flag = 1;

} munotes.in

## Page 104

104 i ++;

ptr = ptr -> next;

}}

yes (flag! = 0)

{

printf ("Item not found \ n");

come back;

}}}

Production:

2) Count the nodes in a circular linked list

Given a circular linked list, count the number of nodes it contains.

For example, the output is 5 for the following list. munotes.in

## Page 105

105

Program:

#include

using the std namespace;

/ * structure for a node * /

node structure {

int data;

Next node *;

Node (int x)

{

data = x;

next = NULL;

}};

/ * Function to insert a node at the beginning

of a circular linked list * /

struct Node * push (struct Node * last, int data)

{

if (last == NULL) {

struct Node * temp

= (struct Node *) malloc (sizeof (struct Node));

// Assign the data.

temp-> data = data;

last = temperature;

munotes.in

## Page 106

106// Note: The list was empty. We connect a single node

// Furthermore.

temp-> next = last;

come back last;

}

// Dynamic creation of a node.

struct Node * temp

= (struct Node *) malloc (sizeof (struct Node));

// Assign the data.

temp-> data = data;

// Adjust the links.

temp-> next = last-> next;

last-> next = temp;

come back last;

}

/ * Function to count the nodes in a given Circular

linked list * /

int countNodes (node * head)

{

Node * temp = head;

int result = 0;

if (head! = NULL) {

do {

temp = temp-> next;

result ++;

} while (temp! = head);

}

return the result; munotes.in

## Page 107

107}

/ * Controller program to test the above functions * /

main integer ()

{

/ * Initialize lists as empty * /

Node * head = NULL;

head = thrust (head, 12);

head = thrust (head, 56);

head = thrust (head, 2);

head = thrust (head, 11);

cout << countNodes (head);

returns 0;

}

Production:

4

3) Reverse a circular linked list

Given a linked circular of size n. The problem is to reverse the given

circular linked list by changing the links between nodes.

Examples:

ENTRANCE:

PRODUCTION:

munotes.in

## Page 108

108Program:

#include

using the std namespace;

// Node of the linked list

node structure {

int data;

Next node *;

};

// function to get a new node

Node * getNode (int data)

{

// allocate memory for the node

Node * newNode = new Node;

// put the data

newNode-> data = data;

newNode-> next = NULL;

returns newNode;

}

// Function to invert the circular linked list

reverse void (node ** head_ref)

{

// if the list is empty

yes (* head_ref == NULL)

come back;

// inverse procedure equal to inverse a

// list linked individually munotes.in

## Page 109

109 Node * prev = NULL;

Current * node = * head_ref;

Next node *;

do {

next = current-> next;

current-> next = previous;

previous = current;

current = next;

} while (current! = (* head_ref));

// adjusting the bindings so that the

// the last node points to the first node

(* head_ref) -> next = previous;

* head_ref = previous;

}

// Function to print a circular linked list

empty printList (Node * head)

{

yes (head == NULL)

come back;

Node * temp = head;

do {

cout << temp-> data << "";

temp = temp-> next;

} while (temp! = head);

}

// Controller program to test above munotes.in

## Page 110

110main integer ()

{

// Create a circular linked list

// 1-> 2-> 3-> 4-> 1

Node * head = getNode (1);

head-> next = getNode (2);

head-> next-> next = getNode (3);

head-> next-> next-> next = getNode (4);

head-> next-> next-> next-> next = head;

cout << "Given list of linked circulars:";

printList (head);

reverse (and head);

cout << "\ nInverted circular linked list:";

printList (head);

returns 0;

}

Production:

Given the linked circular list: 1 2 3 4

Inverted circular linked list: 4 3 2 1

Question:

1. What differentiates a circular linked list from a normal linked list?

a) You cannot have the ‘next’ pointer point to null in a circular linked

list

b) It is faster to traverse the circular linked list

c) You may or may not have the ‘next’ pointer point to null in a

circular linked list

d) Head node is known in circular linked list

munotes.in

## Page 111

1112. Which of the following application makes use of a circular linked list?

a) Undo operation in a text editor

b) Recursive function calls

c) Allocating CPU to resources

d) Implement Hash Tables

3. Which of the following is false about a circular linked list?

a) Every node has a successor

b) Time complexity of inserting a new node at the head of the list is O(1)

c) Time complexity for deleting the last node is O(n)

d) We can traverse the whole circular linked list by starting from any point

4. Consider a small circular linked list. How to detect the presence of

cycles in this list effectively?

a) Keep one node as head and traverse another temp node till the end to

check if its ‘next points to head

b) Have fast and slow pointers with the fast pointer advancing two nodes

at a time and slow pointer advancing by one node at a time

c) Cannot determine, you have to pre-define if the list contains cycles

d) Circular linked list itself represents a cycle. So no new cycles cannot be

generated

3. Objective: To implement the doubly linked list using C / C ++

Theory:

● In a single linked list, each node has a link to the next node in the

sequence. So we can only cross from node to node in one direction

and we cannot cross backwards. We can solve this type of problem

by using a list of double bonds. A list of double bonds can be

defined as follows ...

● The double-linked list is a sequence of items where each item has

links to the previous item and the next item in the sequence.

● In a double-linked list, each node has a link to its previous node

and to the next node. So, we can go forward using the next field

and we can go back using the previous field. munotes.in

## Page 112

112

Program

Important points to remember

● In a double-linked list, the first node must always point towards the

head.

● The previous field of the first node must always be NULL.

● The next field of the last node must always be NULL.

Doubly linked list operations

● Insertion

● deletion

● Show

Insertion

In a list of double bonds, the insert operation can be performed in three

ways as follows ...

● Insert at the beginning of the list

● Enter to the end of the list

● Insert in a specific position in the list

Insert at the beginning of the list

We can use the following steps to insert a new node at the beginning of

the double bond list.

Step 1: Create a newNode with the specified value and newNode → above

as NULL.

Step 2: Check if the list is empty (head == NULL)

Step 3: If empty, set NULL to newNode → next and newNode to header.

Step 4: If it's not empty, set head to newNode → ne xt a nd newNode to

head.

munotes.in

## Page 113

113Enter to the end of the list

We can use the following steps to insert a new node at the end of the

double-linked list ...

Step 1: Create a newNode with the specified value and newNode → next

as NULL.

Step 2: Check if the list is empty (head == NULL)

Step 3: If empty, set NULL to newNode → p r e v i o u s a n d n e w N o d e t o

header.

Step 4: If it is not empty, define a node pointer temperature and initialize

with head.

Step 5: Keep moving the temperature to the next node until it reaches the

last node in the list (until temp → next equals NULL).

Step 6: Assign newNode to temp → n e x t a n d t e m p t o n e w N o d e →

previous.

Insert in a specific position in the list (after a node)

We can use the following steps to insert a new node after a node in the

double-bound list ...

Step 1: Create a new node with a certain value.

Step 2: Check if the list is empty (head == NULL)

Step 3: If empty, set NULL to newNode → p r e v i o u s a n d n e w N o d e →

next and set newNode as header.

Step 4: If it is not empty, define two pointers to node temp1 and temp2

and initialize temp1 with head.

Step 5: keep moving temp1 to your next node until you reach the node

after which we want to insert the newNode (as long as temp1 → data is

equal to the position, here the position is the value of the node after which

we want to insert the newNode ).

Step 6: Check every time that temp1 has been reached on the last node. If

the last node is reached, 'The specified node is not in the list! Insertion not

possible !!! 'and terminate the function. Otherwise, move temp1 to the

next node.

Step 7: Assign temp1 → next to temp2, newNode to temp1 → next, temp1

to newNode → p r e v i o u s , t e m p 2 t o n e w N o d e → n e x t a n d n e w N o d e t o

temp2 → previous.

munotes.in

## Page 114

114deletion

In a list of double bonds, the delete operation can be performed in three

ways as follows ...

● Delete from the top of the list

● Remove from the end of the list

● Delete a specific node

Delete from the top of the list

We can use the following steps to remove a node from the beginning of

the double bond list ...

Step 1: Check if the list is empty (head == NULL)

Step 2: If blank, display 'List is empty! Deletion is not possible and

terminate the function.

Step 3: If it is not empty, define a pointer to the 'temp' node and initialize

with head.

Step 4: Check if the list has only one node (temp → p r e v i o u s e q u a l t o

temp → next)

Step 5: If TRUE, set the head to NULL and remove the temperature

(setting the conditions of the empty list)

Step 6: If FALSE, assign temp → n e x t t o h e a d e r , N U L L t o h e a d e r →

above and remove temp.

Remove from the end of the list

We can use the following steps to remove a knot from the end of the

double bond list ...

Step 1: Check if the list is empty (head == NULL)

Step 2: If blank, display 'List is empty! Deletion is not possible and

terminate the function.

Step 3: If it is not empty, define a pointer to the 'temp' node and initialize

with head.

Step 4: Check if the list has only one node (temp → previous and temp →

next are both NULL)

Step 5: If TRUE, assign NULL to the header and remove the temperature.

And finish the show. (Setti ng the empty list condition)

Step 6: If FALSE, keep moving the temperature until it reaches the last

node in the list. (until the next → temperature equal to NULL)

Step 7: NULL at temp → previous → next and remove temp. munotes.in

## Page 115

115Remove a specific node from the list

We can use the following steps to remove a specific node from the double

bond list ...

Step 1: Check if the list is empty (head == NULL)

Step 2: If blank, display 'List is empty! Deletion is not possible and

terminate the function.

Step 3: If it is not empty, define a pointer to the 'temp' node and initialize

with head.

Step 4: Keep moving the temperature until you reach the exact knot to

remove or the last knot.

Step 5: If the last node is reached, display 'The specified node is not in the

list! It cannot be canceled !!! 'and terminate the function.

Step 6: If the exact node we want to remove is reached, check if the list

has only one node or not

Step 7: If the list has only one node and this is the node to remove, set the

header to NULL and remove temp (free (temp)).

Step 8: If the list contains multiple no des, check if temp is the first node in

the list (temp == head).

Step 9: If temp is the first node, move the head to the next node (head =

head → next), set the head of the previous one to NULL (head → previous

= NULL) and remove the temperature.

Step 10: If temp is not the first node, check if it is the last node in the list

(temp → next == NULL).

Step 11: If temp is the last node, set temp from previous or next to NULL

(temp → previous → next = NULL) and remove temp (free (temp)).

Step 12 - If temp is not the first node and not the last node, set the temp

from the previous of the next to the temp of the next (temp → previous →

next = temp → n e x t ) , t e m p o f t h e n e x t o f t h e p r e v i o u s t o t e m p o f t h e

previous ( temp → next → previous = temp → previous) and delete temp

(free (temp)).

Visualization of a double linked list

We can use the following steps to view the elements of a list of double

bonds ...

Step 1: Check if the list is empty (head == NULL)

Step 2: If blank, show 'List is empty !!!' and terminate the function.

Step 3: If it is not empty, define a pointer to the 'temp' node and initialize

with head. munotes.in

## Page 116

116Step 4: Show 'NULL <---'.

Step 5: Continue viewing the temperature → data with an arrow (<===>)

until the temperature reaches the last node

Step 6 - Finally, display temp → date with the arrow pointing to NULL

(temp → date ---> NULL).

Program

#include

#include

void insertAtBeginning (int);

void insertAtEnd (int);

void insertAtAfter (int, int);

void deleteBeginning ();

void deleteEnd ();

void deleteSpecific (int);

blank display ();

Structure node

{

int data;

struct Node * previous, * next;

} * head = NULL;

main vacuum ()

{

int choice1, choice2, value, position;

clrscr ();

while (1)

{

printf ("\ n *********** MENU ************* \ n");

printf ("1. Enter \ n2. Delete \ n3. Screen \ n4. Exit \ nEnter your

choice:");

scanf ("% d", & choice1);

Change () munotes.in

## Page 117

117 {

case 1: printf ("Insert the value to insert:");

scanf ("% d", & value);

while (1)

{

printf ("\ nSelect from the following insert options \ n");

printf ("1. At the beginning \ n2. At the end \ n3. After a node \ n4. Cancel

\ nEnter your choice:");

scanf ("% d", & choice2);

switch (option 2)

{

case 1: insertAtBeginning (value);

break time;

case 2: insertAtEnd (value);

break time;

case 3: printf ("Enter the position after which you want to insert:");

scanf ("% d", & location);

insertAfter (value, position);

break time;

case 4: go to EndSwitch;

default: printf ("\ nSelect the correct insert option! \ n");

}

}

case 2: while (1)

{

printf ("\ nSelect from the following delete options \ n");

printf ("1. At the beginning \ n2. At the end \ n3. Specific node \ n4.

Cancel \ nEnter your choice:");

scanf ("% d", & choice2);

switch (option 2)

{ munotes.in

## Page 118

118 case 1: deleteBeginning ();

break time;

case 2: deleteEnd ();

break time;

case 3: printf ("Enter the value of the node to be removed:");

scanf ("% d", & location);

deleteSpecic (location);

break time;

case 4: go to EndSwitch;

default: printf ("\ nSelect the correct delete option! \ n");

}

}

Limit switch: pause;

case 3: display ();

break time;

case 4: exit (0);

default: printf ("\ nSelect the correct option!");

}}}

void insertAtBeginning (int value)

{

struct Node * newNode;

newNode = (struct Node *) ma lloc (sizeof (struct Node));

newNode -> data = value;

newNode -> previous = NULL;

yes (head == NULL)

{

newNode -> next = NULL;

head = newNode;

}

the rest munotes.in

## Page 119

119 {

newNode -> next = head;

head = newNode;

}

printf ("\ nThe entry was successful!");

}

void insertAtEnd (int value)

{

struct Node * newNode;

newNode = (struct Node *) ma lloc (sizeof (struct Node));

newNode -> data = value;

newNode -> next = NULL;

yes (head == NULL)

{

newNode -> previous = NULL;

head = newNode;

}

the rest

{

struct Node * temp = head;

while (temp -> next! = NULL)

temp = temp -> next;

temp -> next = newNode;

newNode -> previous = temp;

}

printf ("\ nThe entry was successful!");

}

void insertAfter (int value, int location)

{

struct Node * newNode; munotes.in

## Page 120

120 newNode = (struct Node *) ma lloc (sizeof (struct Node));

newNode -> data = value;

yes (head == NULL)

{

newNode -> previous = newNode -> next = NULL;

head = newNode;

}

the rest

{

struct Node * temp1 = head, temp2;

while (temp1 -> data! = position)

{

yes (temp1 -> next == NULL)

{

printf ("The indicated node is not in the list !!!");

go to EndFunction;

}

the rest

{

temp1 = temp1 -> next;

}}

temp2 = temp1 -> next;

temp1 -> next = newNode;

newNode -> previous = temp1;

newNode -> next = temp2;

temp2 -> previous = newNode;

printf ("\ nThe entry was successful!");

}

Final function:

} munotes.in

## Page 121

121void deleteBeginning ()

{

yes (head == NULL)

printf ("The list is empty! Could not delete it!");

the rest

{

struct Node * temp = head;

yes (temp -> previous == temp -> next)

{

head = NULL;

free (temperature);

}

the rest{

head = temp -> next;

head -> front = NULL;

free (temperature);

}

printf ("\ n Deletio n successful !!!");

}}

void deleteEnd ()

{

yes (head == NULL)

printf ("The list is empty! Could not delete it!");

the rest

{

struct Node * temp = head;

yes (temp -> previous == temp -> next)

{

head = NULL;

free (temperature); munotes.in

## Page 122

122 }

the rest{

while (temp -> next! = NULL)

temp = temp -> next;

temp -> previous -> next = NULL;

free (temperature);

}

printf ("\ n Deletio n successful !!!");

}}

void deleteSpecific (int delValue)

{

yes (head == NULL)

printf ("The list is empty! Could not delete it!");

the rest

{

struct Node * temp = head;

while (temp -> data! = delValue)

{

yes (temp -> next == NULL)

{

printf ("\ nThe indicated node is not in the list !!!");

go to FineFunction;

}

the rest

{

temp = temp -> next;

}

}

yes (temp == head)

{ munotes.in

## Page 123

123 head = NULL;

free (temperature);

}

the rest

{

temp -> previous -> next = temp -> next;

free (temperature);

}

printf ("\ n Deletio n successful !!!");

}

End function:

}

blank screen ()

{

yes (head == NULL)

printf ("\ nList is empty !!!");

the rest

{

struct Node * temp = head;

printf ("\ nThe elements of the list are: \ n");

printf ("NULL <---");

while (temp -> next! = NULL)

{

printf ("% d <===>", temp -> data);

}

printf ("% d ---> NULL", temp -> data);

}}

munotes.in

## Page 124

124Production

1) Count the nodes in the doubly linked list

#include

using the std namespace;

// structure of the node

node structure {

int data;

Next node *;

Previous node *;

};

class LinkedList {

private:

Knot * head;

public:

Linked List () {

head = NULL;

}

// Add a new item to the end of the list munotes.in

## Page 125

125 void push_back (int newElement) {

Node * newNode = new Node ();

newNode-> data = newElement;

newNode-> next = NULL;

newNode-> prev = NULL;

if (head == NULL) {

head = newNode;

} the rest {

Node * temp = head;

while (temp-> next! = NULL)

temp = temp-> next;

temp-> next = newNode;

newNode-> prev = temp;

}

}

// count the nodes in the list

int countNodes () {

Node * temp = head;

int i = 0;

while (temp! = NULL) {

i ++;

temp = temp-> next;

}

I return;

}

// show the contents of the list

void PrintList () {

Node * temp = head;

if (temp! = NULL) {

cout << "The list contains:"; munotes.in

## Page 126

126 while (temp! = NULL) {

cout < data << "";

temp = temp-> next;

}

cout << endl;

} the rest {

cout << "The list is empty. \ n";

}}};

// test the code

int main () {

LinkedList MyList;

// Add four items to the list.

MyList.push_back (10);

MyList.push_back (20);

MyList.push_back (30);

MyList.push_back (40);

// Show the contents of the list.

MyList.PrintList ();

// number of nodes in the list

cout << "No. of nodes:" << MyList.countNodes ();

returns 0;

}

}

Production:

The list contains: 10 20 30 40

Number of nodes: 4

munotes.in

## Page 127

1272) Find an item in a doubly linked list

Given a doubly linked list (DLL) containing N nodes and an integer X, the

task is to find the pos ition of the entire X in the doubly linked list. If no

such position is found, print -1.

Examples:

Input: 15 <=> 16 <=> 8 <=> 7 <=> 13, X = 8

Production: 3

Explanation: X (= 8) is present at the third node of the doubly linked list.

Therefore, the required output is 3

Input: 5 <=> 3 <=> 4 <=> 2 <=> 9, X = 0

Exit: -1

Explanation: X (= 0) is not present in the doubly linked list.

Therefore, the required output is -1

Approach: Follow the steps below to fix the problem:

● Initialize a variable, say pos, to store the position of the node

that contains the X data valu e in the doubly linked list.

● Initializes a pointer, such as temp, to store the parent node of

the doubly linked list.

● Iterate over the linked list and for each node check if the data

value of that node equals X or not. If determined to be true,

print pos.

● Otherwise, press -1.

Program:

#include

using the std namespace;

// Structure of a node

// the doubly linked list

node structure {

// Store the data value

// of a node

int data; munotes.in

## Page 128

128 // Store the pointer

// to the next node

Next node *;

// Store the pointer

// to the previous node

Previous node *;

};

// Function to insert a node into the

// start of the doubly linked list

push empty (node ** head_ref, int new_data)

{

// Allocate memory for a new node

Node * new_node

= (Node *) malloc (size of (Node structure));

// Enter the data

new_node-> data = new_data;

// As the node is added to the

// start, prev is always NULL

new_node-> prev = NULL;

// Connect the previous list to the new node

new_node-> next = (* head_ref);

// If the head po inter is not NULL

if ((* head_ref)! = NULL) { munotes.in

## Page 129

129

// Change the previous header

// from node to new node

(* head_ref) -> prev = new_node;

}

// Move your head to point to the new node

(* head_ref) = new_node;

}

// Function to find the position of

// an integer in a doubly linked list

search int (node ** head_ref, int x)

{

// Store the root node

Temp node = head_ref;

// Stores the position of the integer

// in the doubly linked list

int position = 0;

// Loop through the doubly linked list

while (temp-> data! = x

&& temp-> forward! = NULL) {

// Update position

position ++;

munotes.in

## Page 130

130 // Update temperature

temp = temp-> next;

}

// If the integer is not present

// in the doubly linked list

if (temp-> data! = x)

return -1;

// If the integer present in

// the doubly linked list

return (pos + 1);

}

// Driver code

main integer ()

{

Node * head = NULL;

intX = 8;

// Create the doubly linked list

// 18 <-> 15 <-> 8 <-> 9 <-> 14

push (and head, 14);

push (and head, 9);

push (and head, 8);

push (and head, 15);

push (and head, 18);

cout << search (& testa, X);

returns 0;

} munotes.in

## Page 131

131Production: 3

1) Reverse a doubly linked list

Given a doubly linked list, the task is to reverse the given doubly linked

list.

See the following diagrams, for example.

(a) Double linked original list

(b) Reverse doubly linked list

Here is a simple method to reverse a doubly linked list. All we need to do

is swap the previous and next pointers for all nodes, change the previous

header (or start), and change the header pointer to the end.

Program:

#include

using the std namespace;

/ * a node from the doubly linked list * /

Node class

{

public:

int data;

Next node *;

Previous node *;

};

/ * Function to invert a doubly linked list * / munotes.in

## Page 132

132reverse void (node ** head_ref)

{

Node * temp = NULL;

Current * node = * head_ref;

/ * swaps next and previous for all nodes

doubly linked list * /

while (current! = NULL)

{

temp = current-> previous;

current-> previous = current-> next;

current-> next = temp;

current = current-> previous;

}

/ * Before changing the head, check that the speakers are empty

list and list with a single node * /

yes (temp! = NULL)

* head_ref = temp-> previous;

}

/ * UTILITY FUNCTIONS * /

/ * Function to insert a node in the

start of list doubly linked * /

push empty (node ** head_ref, int new_data)

{

/ * assign node * /

Node * new_node = new node ();

/ * I enter the data * /

new_node-> data = new_data; munotes.in

## Page 133

133

/ * since we are adding at the beginning,

prev is always NULL * /

new_node-> prev = NULL;

/ * associate the list above with the new node * /

new_node-> next = (* head_ref);

/ * change the old main node to a new node * /

if ((* head_ref)! = NULL)

(* head_ref) -> prev = new_node;

/ * move head to point to new node * /

(* head_ref) = new_node;

}

/ * Function to print the nodes in a given doubly linked list

This function is the same as printList () of an individually linked list * /

empty printList (node * node)

{

while (node! = NULL)

{

cout << node-> data << "";

node = node-> next;

}

}

/ * Driver code * /

main integer ()

{

/ * Start with empty list * /

Node * head = NULL; munotes.in

## Page 134

134

/ * We create an ordered linked list to test the functions

The created linked list will be 10-> 8-> 4-> 2 * /

press (& testa, 2);

push (and head, 4);

push (and head, 8);

push (and head, 10);

cout << "Original linked list" << endl;

printList (head);

/ * Double linked list inverse * /

reverse (and head);

cout << "\ nInverted linked list" << endl;

printList (head);

returns 0;

}

Production:

Original linked list

10 8 4 2

The inverted linked list is

2 4 8 10

munotes.in

## Page 135

135Questions:

1. Which of the following is false about a doubly linked list?

a) We can navigate in both the directions

b) It requires more space than a singly linked list

c) The insertion and deletion of a node take a bit longer

d) Implementing a doubly linked list is easier than singly linked list

2. What is a memory effi cient doubly linked list?

a) Each node has only one pointer to traverse the list back and forth

b) The list has breakpoints for faster traversal

c) An auxiliary singly li nked list acts as a he lper list to traverse

through the doubly linked list

d) A doubly linked list that uses bitwise AND operator for storing

addresses

3. How do you calculate th e pointer difference in a memory efficient

double linked list?

a) head xor tail

b) pointer to previous nod e xor pointer to next node

c) pointer to previous n ode – pointer to next node

d) pointer to next node – pointer to previous node

4. the following doubly linke d list: head-1-2-3-4-5-tail. What will be

the list after performing the given sequence of operations?

N o d e t e m p = new Node(6,head,head.getNext());

h e a d . s e t N e x t ( t e m p ) ;

t e m p . g e t N e x t ( ) . s e t P r e v ( t e m p ) ;

Node temp1 = tail.getPrev();

tail.setPrev(temp1.getPrev());

temp1. getPrev().setNext(tail);

a) head-6-1-2-3-4-5-tail

b) head-6-1-2-3-4-tail

c) head-1-2-3-4-5-6-tail

d) head-1-2-3-4-5-tail munotes.in

## Page 136

1364. Objective: Add two polynomials using a linked list

Theory:

Given two polynomial numbers represented by a linked list. Writing a

function that aggregates these lists means adding the coefficients that have

the same variable powers.

Example:

Entrance:

1st number = 5x2 + 4x1 + 2x0

2nd number = -5x1 - 5x0

Production:

5x2-1x1-3x0

Entrance:

1st number = 5x3 + 4x2 + 2x0

2nd number = 5x ^ 1 - 5x ^ 0

Production:

5x3 + 4x2 + 5x1 - 3x0

munotes.in

## Page 137

137Program:

// use linked lists

#include

using the std namespace;

// Structure of the node containing power and coefficient of

// variable

node structure {

int coeff;

internal power;

struct Node * next;

};

// Function to create a new node

empty create_node (int x, int y, struct Node ** temp)

{

Structure node * r, * z;

z = * temperature;

if (z == NULL) {

r = (struct Node *) malloc (sizeof (struct Node));

r-> coeff = x;

r-> pow = y;

* temperature = r;

r-> next = (struct Node *) malloc (sizeof (struct Node));

r = r-> next;

r-> next = NULL;

}

the rest {

r-> coeff = x;

r-> pow = y;

r-> next = (struct Node *) malloc (sizeof (struct Node)); munotes.in

## Page 138

138 r = r-> next;

r-> next = NULL;

}

}

// Sum function of two polynomial numbers

void polyadd (struct Node * poly1, struct Node * poly2,

Structure node * poles)

{

while (poly1-> next && poly2-> next) {

// If the power of the first poly nomial is greater than the second,

// then store the first one as is and move its pointer

if (poly1-> pow> poly2-> pow) {

poli-> pow = poli1-> pow;

poly-> coeff = poly1-> coeff;

poly1 = poly1-> next;

}

// If the power of the second polyn omial is greater than the first,

// then store the second as is and move its pointer

else if (poli1-> pow pow) {

poli-> pow = poli2-> pow;

poly-> coeff = poli2-> coeff;

poly2 = poly2-> next;

}

// If the power of both polynomials is the same, then

// add their coefficients

the rest {

poli-> pow = poli1-> pow;

poly-> coeff = poly1-> coeff + poli2-> coeff; munotes.in

## Page 139

139 poly1 = poly1-> next;

poly2 = poly2-> next;

}

// Dynamically create a new node

poly-> next

= (struct Node *) malloc (sizeof (struct Node));

poli = poly-> next;

poly-> next = NULL;

}

while (poly1-> next || poly2-> next) {

if (poly1-> next) {

poli-> pow = poli1-> pow;

poly-> coeff = poly1-> coeff;

poly1 = poly1-> next;

}

if (poly2-> next) {

poli-> pow = poli2-> pow;

poly-> coeff = poli2-> coeff;

poly2 = poly2-> next;

}

poly-> next

= (struct Node *) malloc (sizeof (struct Node));

poli = poly-> next;

poly-> next = NULL;

}

}

// Show linked list

empty show (knot structure * knot)

{ munotes.in

## Page 140

140 while (node-> next! = NULL) {

printf ("% dx ^% d", node-> coeff, node-> pow);

node = node-> next;

if (node-> coeff> = 0) {

if (node-> next! = NULL)

printf ("+");

}

}

}

// Controller code

main integer ()

{

struct Node * poly1 = NULL, * poly2 = NULL, * poly = NULL;

// Create the first list of 5x ^ 2 + 4x ^ 1 + 2x ^ 0

create_node (5, 2, & poly1);

create_node (4, 1, & poly1);

create_node (2, 0, & poly1);

// Create a second list of -5x ^ 1 - 5x ^ 0

create_node (-5, 1 and poly2);

create_node (-5, 0 and poly2);

printf ("1st number:");

show (poly1);

printf ("\ n2nd number:");

show (poly2);

poly = (struct Node *) ma lloc (sizeof (struct Node));

// The function adds two polynomial numbers munotes.in

## Page 141

141 polyadd (poly1, poly2, poly);

// Show the list of results

printf ("\ nPolynomial added:");

show (poles);

returns 0;

}

Production:

1st number: 5x ^ 2 + 4x ^ 1 + 2x ^ 0

Second number: -5x ^ 1-5x ^ 0

Aggregate polynomial: 5x ^ 2-1x ^ 1-3x ^ 0

munotes.in

## Page 142

142Module V

1. Point: Implementation of qu eued linked lists

Objective:

Use the queues for basic time simulations. Be able to recognize the

properties of the problem where stacks, queues and deque are suitable data

structures. Being able to implement the abstract data type list as a linked

list using the reference node and model.

Theory:

● Due to the disadvantages discussed in the previous section of this

tutorial, the matrix implementation cannot be used for large-scale

applications where queues are implemented. One of the array

implementation alternatives is the queue linked list

implementation.

● The storage requirement of the linked representation of a queue

with n items is o (n) while the time requirement for operations is o

(1).

● In a linked queue, each node of the queue consists of two parts,

namely the data part and the association part. Each item in the

queue points to the next immediate item in memory.

● There are two pointers in memory in the linked queue: front

pointer and back pointer. The fron t pointer contains the address of

the starting element in the queue, while the back pointer contains

the address of the last element in the queue.

● Insertion and removal are performed at the back and front

respectively. If both the front and back are NULL, it indicates that

the queue is empty.

● The linked representation of the queue is shown in the following

figure.

Queued operation linked

There are two basic operations that can be implemented on linked

queues. The operations are Insert and Delete. munotes.in

## Page 143

143Operation entry

The insert operation adds the queue by adding an item to the end of

the queue. The new item will be the last item in the queue.

First, allocate the memory for the new ptr node using the following

declaration.

1. Ptr = (structure node *) malloc (size of (structure node));

There can be two scenarios of putting this new ptr node into the linked

queue.

In the first scenario, we put an item in an empty queue. In this case, the

front = NULL condition becomes tr ue. Now the new element will be

added as the only element in the queue and the next front and back pointer

will point to NULL.

ptr -> data = element;

yes (front == NULL)

{

front = ptr;

posterior = ptr;

front -> next = NULL;

rear -> next = NULL;

}

In the second case, the queue contains more than one element. The

front = NULL condition becomes false. In this scenario, you need to

update the final trailing pointer so that the next trailing pointer points to

the new ptr node. Since this is a linked queue, we also need to make the

back pointer point to the newly added ptr node. We also need to make the

pointer to the next end point NULL.

posterior -> next = ptr;

posterior = ptr;

back-> next = NULL;

This puts the item in the queue. The algorithm and implementation

of C are shown below.

munotes.in

## Page 144

144Algorithm

Step 1: Allocate space for the new PTR node

Step 2: SET PTR -> DATA = VAL

Step 3: IF FRONT = NULLSET FRONT = REAR = PTRSET FRONT ->

NEXT = REAR -> NEXT = NULLELSESET REAR -> NEXT =

PTRSET REAR = PTRSET REAR -> NEXT = NULL [END OF IF]

Step 4: FINISH

Program:

insert empty (struct node * ptr, int element;)

{

ptr = (structure node *) malloc (size of (structure node));

yes (ptr == NULL)

{

printf ("\ nOVERFLOW \ n");

come back;

}

the rest

{

ptr -> data = element;

yes (front == NULL)

{

front = ptr;

posterior = ptr;

front -> next = NULL;

rear -> next = NULL;

}

the rest

{

posterior -> next = ptr;

posterior = ptr; munotes.in

## Page 145

145 back-> next = NULL;

}}}

deletion

● The delete operation removes the item inserted first of all items in

the queue. First of all, we need to check if the list is empty or not.

The condition front == NULL becomes true if the list is empty, in

this case we simply write underflow in the console and exit.

● Otherwise, we will remove the element that the front pointer points

to. To do this, copy the node pointe d to by the front pointer to the

ptr pointer. Now, move the front pointer, point to your next node

and release the node pointed to by the ptr node. This is done using

the following statements.

ptr = in front;

front = front -> forward;

free (ptr);

Algorithm

Step 1: IF FRONT = NULL Type "Underflow" Go to step 5 [END OF IF]

Step 2: SET PTR = FRONT

Step 3: SET FRONT = FRONT -> NEXT

Step 4: FREE RPP

Step 5: FINISH

Program:

remove void (structure node * ptr)

{

yes (front == NULL)

{

printf ("\ nUNDERFLOW \ n");

come back;

}

the rest

{ munotes.in

## Page 146

146 ptr = in front;

front = front -> forward;

free (ptr);

}}

Program:

#include

#include

structure node

{

int data;

next structure node *;

};

front structure knot *;

knot back structure *;

blank insert ();

cancel cancel ();

blank display ();

main vacuum ()

{

int choice;

while (choice! = 4)

{

printf ("\ n ************************* Main menu

****************** ***********\North");

printf ("\ n ========= ===================================

= =================== \ n ");

printf ("\ n1.insert an item \ n2. Delete an item \ n3. Show queue \

n4.Sexit \ n");

printf ("\ nPlease enter your choice?");

scanf ("% d", & option);

change (choice) munotes.in

## Page 147

147 {

Case 1:

to insert();

break time;

case 2:

To remove();

break time;

case 3:

show();

break time;

case 4:

output (0);

break time;

default:

printf ("\ nPlease enter a valid choice ?? \ n");

}

}

}

blank insert ()

{

struct node * ptr;

int element;

ptr = (structure node *) malloc (size of (structure node));

yes (ptr == NULL)

{

printf ("\ nOVERFLOW \ n");

come back;

}

the rest

{ munotes.in

## Page 148

148 printf ("\ nPlease insert value? \ n");

scanf ("% d", & element);

ptr -> data = element;

yes (front == NULL)

{

front = ptr;

posterior = ptr;

front -> next = NULL;

rear -> next = NULL;

}

the rest

{

posterior -> next = ptr;

posterior = ptr;

back-> next = NULL;

}

}

}

delete delete ()

{

struct node * ptr;

yes (front == NULL)

{

printf ("\ nUNDERFLOW \ n");

come back;

}

the rest

{

ptr = in front;

front = front -> forward; munotes.in

## Page 149

149 free (ptr);

}

}

blank screen ()

{

struct node * ptr;

ptr = in front;

yes (front == NULL)

{

printf ("\ n Empty queue \ n");

}

the rest

{printf ("\ nprint values ..... \ n");

while (ptr! = NULL)

{

printf ("\ n% d \ n", ptr -> data);

ptr = ptr -> next;

}}}

Production:

***********Main menu**********

==============================

1.Enter a subject

2.Remove an item

3. Show the queue

4.exit

Enter your choice? 1

Enter value?

123

***********Main menu**********

==============================

munotes.in

## Page 150

1501.Enter a subject

2.Remove an item

3. Show the queue

4.exit

Enter your choice? 1

Enter value?

90

***********Main menu**********

==============================

1.Enter a subject

2.Remove an item

3. Show the queue

4.exit

Enter your choice? 3

print values .....

123

90

***********Main menu**********

==============================

1.Enter a subject

2.Remove an item

3. Show the queue

4.exit

Enter your choice? 2

***********Main menu**********

==============================

1.Enter a subject

2.Remove an item

3. Show the queue

4.exit

Enter your choice? 3

print values ..... munotes.in

## Page 151

15190

***********Main menu**********

==============================

1.Enter a subject

2.Remove an item

3. Show the queue

4.exit

Enter your choice? 4

2. Objective: Implementation of the circular queue array

Objective:

The circular queue solves the main limitation of the normal queue.

In a normal queue, after some insertion and deletion, there will be blank,

unusable space.

Theory:

There was a limitation in the impl ementation of the Queue. If the

back reaches the final position of the queue, there may be gaps at the

beginning that cannot be used. So, to overcome these limitations, the

concept of a circular queue was introduced.

As we can see in the image above, the back is in the last position of

the queue and the front is pointing somewhere instead of position 0. In the

array above, there are only two elements and three other positions are

empty. . The rear is in the last position of the tail; if we try to insert the

element, it will show that there are no empty spaces in the queue. There is

a solution to avoid such a waste of memory space by moving both munotes.in

## Page 152

152elements to the left and adjusting the front and rear ends accordingly. This

is not a practically good approach because changing all the elements will

take time. The effective approach to avoiding memory waste is to use the

data structure of the circular queue.

What is a circular queue?

A circular queue is similar to a linear queue in that it too is based

on the FIFO (First in, first out) principle except that the last position is

connected to the first position in a ci rcular queue that forms a circle. Also

known as Ring Buffer.

Circular queued operations

The operations that can be performed on a circular queue are as follows:

● Front: used to get the front element of the tail.

● Back - Used to retrieve the back item from the queue.

● enQueue (value): This fu nction is used to insert the new value into

the queue. The new element is always inserted from the back.

● deQueue (): This function removes an item from the queue.

Deletion in a queue is always done from the front end.

Circular glue applications

The circular queue can be used in the following scenarios:

● Memory Management: The circular queue provides memory

management. As we have already seen in linear queues, memory is

not handled very efficiently. But in the case of a circular queue,

memory is managed efficiently by placing items in an unused

location.

● CPU scheduling: The operating system also uses the circular queue

to insert processes and then run them.

● Traffic System: In a computer controlled traffic system,

semaphores are one of the best examples of a circular queue. Each

traffic light turns on one by one afte r each time interval. As the red

light is on for one minute, then the yellow light for one minute and

then the green light. After the green light, the red light turns on. munotes.in

## Page 153

153Queued operation

The stages of the queuing operation are as follows:

● First, we will check if the queue is full or not.

● Initially, front and rear are set to -1. When we put the first element

in a queue, both the front and the back are set to 0.

● When we insert a new element, the back is increased, i.e. back =

back + 1.

Scenarios for inserting an element

There are two scenarios wh ere the queue is not full:

● If rear! = Max - 1, the back will increase to mod (maxsize) and the

new value will be inserted at the end of the queue.

● Yes in front! = 0 and back = max - 1, it means the queue is not full,

so set the back value to 0 and put the new element there.

There are two cases in which the element cannot be inserted:

● When front == 0 && rear = max-1, it means the front is in the first

position of the tail and the back is in the last position of the tail.

● front == rear + 1;

Algorithm:

Phase 1: S (REAR + 1)% MAX = FRONT

Write "OVERFLOW"

Go to step 4

[End OF S]

Step 2: IF FRONT = -1 and BACK = -1

SET FRONT = REAR = 0

OTHERWISE IF REAR = MAX - 1 and FRONT! = 0

REAR ADJUSTMENT = 0

THE REST

REAR ADJUSTMENT = (REAR + 1)% MAX munotes.in

## Page 154

154[END OF S]

Step 3: CONFIGURE QUEUE [REAR] = VAL

Step 4: EXIT

Tail pull operation

The steps of the remove the queue operation are as follows:

● First, let's check if the queue is empty or not. If the queue is empty,

we cannot perform the queue cancel operation.

● When the element is removed, the front value is reduced by 1.

● If there is only one element left that needs to be removed, the front

and back are reset to -1.

Algorithm:

Step 1: IF FRONT = -1

Enter "UNDERFLOW"

Go to step 4

[END of S]

Step 2: SET VAL = QUEUE [FRONT]

Step 3: IF FRONT = REAR

SET FRONT = REAR = -1

THE REST

IF FRONT = MAX -1

FRONT SET = 0

THE REST

SET FRONT = FRONT + 1

[END of S]

[END OF S]

Step 4: EXIT

We understand the queuing and unblocking operation via the schematic

representation. munotes.in

## Page 156

156

Program:

Program:

#include

# define maximum 6

munotes.in

## Page 157

157int queue [max]; // declaration of the array

front int = -1;

back int = -1;

// function to put an item in a circular queue

empty queuing (int element)

{

if (front == - 1 && rear == - 1) // c ondition to verify that the queue is

empty

{

front = 0;

rear = 0;

tail [back] = element;

}

else if ((rear + 1)% max == front) // condition to check that the queue is

full

{

printf ("The queue is overflowing ..");

}

the rest

{

rear = (rear + 1)% max; // the rear is increased

tail [back] = element; // assign a value to the rearmost queue.

}}

// function to remove the item from the queue

int dequeue ()

{

if ((front == - 1) && (rear == - 1)) // condition to verify that the queue is

empty

{

printf ("\ nQueue is underflow ..");

} munotes.in

## Page 158

158 else if (front == rear)

{

printf ("\ nThe removed item from the queue is% d", queue [front]);

front = -1;

rear = -1;

}

the rest

{

printf ("\ nThe removed item from the queue is% d", queue [front]);

front = (front + 1)% max;

}}

// function to display the elements of a queue

blank screen ()

{

int i = front;

yes (front == - 1 && rear == - 1)

{

printf ("\ n The queue is empty ..");

}

the rest

{

printf ("\ nThe elements of a queue are:");

while (i <= behind)

{

printf ("% d,", tail [i]);

i = (i + 1)% maximum;

}}}

main integer ()

{

int choice = 1, x; // declaration of variables munotes.in

## Page 159

159

while (option <4 && opti on! = 0) // while loop

{

printf ("\ n Press 1: Insert an element");

printf ("\ nPress 2: Delete an item");

printf ("\ nPress 3: Show item");

printf ("\ nPlease enter your choice");

scanf ("% d", & option);

change (choice)

{

Case 1:

printf ("Insert the element to insert");

scanf ("% d", & x);

tail (x);

break time;

case 2:

dequeue ();

break time;

case 3:

show();

}}

returns 0;

}

munotes.in

## Page 160

160Production:

Questions:

1. Which of the following propertie s is associated with a queue?

a) First In Last Out

b) First In First Out

c) Last In First Out

d) Last In Last Out

2. In a circular queue, how do you increment the rear end of the queue?

a) rear++

b) (rear+1) % CAPACITY

c) (rear % CAPACITY)+1 munotes.in

## Page 161

161d) rear–

3. What is the term for insert ing into a full queue known as?

a) overflow

b) underflow

c) null pointer exception

d) program won’t be compiled

4. What is the need for a circular queue?

a) effective usage of memory

b) easier computations

c) to delete elements based on priority

d) implement LIFO pr inciple in queues

3. Objective: Priority queue using the linked list in C

Objective:

The priority queue (also known as a stripe) is used to keep track of

unexplored paths, where a lower bound on the total path length is lower

and has the highest priority.

Theory:

The queue is a FIFO data structure where the element that is

inserted first is the first to be remove d. A priority queue is a type of queue

in which items can be inserted or removed based on priority. It can be

implemented using a linked queue, stack, or list data structure. The

priority queue is implemented following these rules:

● The data or items with the highest priority will run before the data

or items with the lowest priority.

● If two items have the same priority, they will be executed in the

sequence in which they are added to the list.

A node in a linked list to implement th e priority queue will contain three

parts:

● Data: will store the integer value.

● Address: will store the addr ess of a subsequent node

● Priority: will store the priority, wh ich is an integer value. It can

range from 0 to 10, where 0 represents the highest priority and 10

represents the lowest priority.

munotes.in

## Page 162

162Example

Entrance

Production

Algorithm:

Start

Step 1-> Declare a tree node

Declare data, priority

Declare a structure node * below

Step 2-> In the Node function * newNode (int d, int p)

Set Node * temp = (Node *) malloc (size of (Node))

Set temp-> data = d

Set temp-> priority = p

Set temperature-> next = NULL

Return temperature

Step 3-> In the int peek function (Node ** head)

return (* head) -> data

Step 4-> In the pop void function (Node ** head)

Set node * temp = * head

Set (* head) = (* head) -> next

free (temporary)

Step 5-> In the push function (Node ** head, int d, int p)

Set node * start = (* head)

Set Node * temp = new Node (d, p) munotes.in

## Page 163

163 If (* head) -> priority> p then,

Set temperature-> next = * head

Set (* head) = temp

The rest

Loop While start-> next! = NULL && start-> next-> priority

Set start = start-> next

Set temperature-> next = start-> next

Set start-> next = temperature

Step 6-> In the int isEmpt y (Node ** head) function

Return (* head) == NULL

Step 7-> In the in t main () function

Set node * pq = newNode (7, 1)

Push call function (& pq, 1, 2)

Push call function (& pq, 3, 3)

Push function call (& pq, 2, 0)

While loop (! IsEmpty (& pq))

Print the results obtained by peek (& pq)

Call function pop (& pq)

To stop

Program:

#include

#include

// priority node

typedef struct node {

int data;

int priority;

next structure node *;

} Node;

Node * newNode (int d, int p) {

Node * temp = (Node *) malloc (size of (Node)); munotes.in

## Page 164

164 temp-> data = d;

temp-> priority = p;

temp-> next = NULL;

return temperature;

}

int peek (knot ** head) {

return (* header) -> data;

}

empty pop (knot ** head) {

Node * temp = * head;

(* head) = (* head) -> next;

free (temperature);

}

push empty (node ** head, int d, int p) {

Knot * start = (* head);

Node * temp = newNode (d, p);

if ((* head) -> priority> p) {

temp-> next = * head;

(* head) = temperature;

} the rest {

while (start-> next! = NULL &&

start-> next-> priority

start = start-> next;

}

// Or at the end of the list

// or in the requested location

temp-> next = start-> next;

start-> next = temp;

}

} munotes.in

## Page 165

165// Function to verify that the queue is empty

int isEmpty (node ** head) {

return (* head) == NULL;

}

// main function

int main () {

Node * pq = newNode (7, 1);

press (& pq, 1, 2);

press (& pq, 3, 3);

press (& pq, 2, 0);

while (! isEmpty (& pq)) {

printf ("% d", see (& pq));

pop (& pq);

}

returns 0;

}

Production

2 7 1 3

Questions:

1. With what data st ructure can a priority queue be implemented?

a) Array

b) List

c) Heap

d) Tree

2. Which of the following is not an application of priority queue?

a) Huffman codes

b) Interrupt handling in operating system

c) Undo operation in text editors

d) Bayesian spam filter munotes.in

## Page 166

1663. What is not a disadvantage of priority scheduling in operating

systems?

a) A low priority process might have to wait indefini tely for the CPU

b) If the system crashes, the lo w priority systems may be lost

permanently

c) Interrupt handling

d) Indefinite blocking

4. Which of the following is not an advantage of a priority queue?

a) Easy to implement

b) Processes with different prio rity can be efficiently handled

c) Applications with differing requirements

d) Easy to delete elements in any case

4. Objective: Implement double-ended queuing in C / C ++

Objective:

Double Ended Queue is also a queue data structure where insert

and delete operations are performed on both ends (front and back). This

means that we can insert both in th e front and back position and we can

remove in both the front and back position.

Theory:

Dequeue stands for Double Ended Tail. In the tail, the insertion

takes place from one end while the removal from the other end. The end

where the insertion takes place is known as the posterior end, while the

end where the removal takes place is known as the anterior end.

Deque is a linear data structure in which insert and delete

operations are performed from both ends. We can say that deque is a

generalized version of the coda.

Let's take a look at some properties of deque.

● Deque can be used both as a stack and as a queue, as it allows

insert and delete operations at both ends. munotes.in

## Page 167

167Then the insert and delete operation can be performed from the side.

The stack follows the LIFO rule in which both insertion and removal can

be done from one end; therefore, we conclude that deque can be

considered as a stack.

Then the insertion can be done from one end and the removal can

be done from the other end. The queue follows the FIFO rule where the

element is inserted on one side and removed on the other. Therefore, we

conclude that the deque can also be regarded as the tail.

There are two types of queues, restricted entry queue and restricted

exit queue.

1. Restricted Input Queue: Restricted Input Queue means that some

restrictions are applied to the input. In the restricted input queue, insert

is applied to one end while removal is applied to both ends.

2. Restricted Exit Queue: Restricted Exit Queue means that some

restrictions apply to the delete opera tion. In a restricted exit queue,

removal can only be applied from one end, while insertion is possible

from both ends.

Operations in Deque

The operations applied in deque are as follows:

● Insert in the front

● Delete from the end

● insert in the back

● remove from the back munotes.in

## Page 168

168In addition to insertion and removal, we can also perform deque inspection

operations. Through the peek operatio n, we can get the front and rear

element of the tail.

We can perform two more operations on removing the queue:

● isFull (): this function returns true if the stack is full; otherwise, it

returns a false value.

● isEmpty (): this function returns true if the stack is empty;

otherwise, it returns a false value.

Memory representation

The deque can be implemented using two data structures, namely a

circular array and a doubly linked list. To implement the deque using a

circular matrix, we first need to know what a circular matrix is.

What is a circular matrix?

An array is said to be circular if the last element of the array is

connected to the first element of the array. Suppose the size of the array is

4 and the array is full but the first position of the array is empty. If we

want to insert the array element, it will not show any overflow condition

since the last element is connected to the first element. The value we want

to insert will be added to the first position of the array.

Deque implementation using a circular array

Below are the steps to perform the operations on the Deque:

Queued operation

1. Initially, we are considering that the deque is empty, so both the

front and the back are set to -1, i.e. f = -1 and r = -1. munotes.in

## Page 169

1692. Since the deque is empty, inserting an element from the front or

back would be the same. Suppose we entered element 1, so front is

equal to 0 and back is also equal to 0.

3. Suppose we want to insert the next element from behind. To insert

the element from the back, we must first increase the back, that is,

back = back + 1. Now, the back points to the second element and

the front points to the first element.

4. Suppose we reinsert the element from the back. To insert the

element, we will first increment the back and now the back points

to the third element.

5. If we want to insert the element from the front and insert an

element from the front, we need to decrease the value of the front

by 1. If we decrease the front by 1, then the front points to position

-1, which is not a position valid in an array. Then, we set the edge

as (n -1), which is equal to 4 since n is 5. Once we set the edge, we

will enter the value as show n in the following figure:

munotes.in

## Page 170

170Tail pull operation

1. If the front points to the last element of the array and we want to

perform the delete operation from the front. To remove any

elements from the front, we must set front = front + 1. Currently

the value of the front is equal to 4, and if we increase the value of

the front, it becomes 5, which is not a valid index. So we conclude

that if front points to the last elem ent, then front is set to 0 in case

of a delete operation.

2. If we want to remove the element from the back, we have to

decrease the value of the back by 1, that is, back = back-1 as

shown in the following figure:

3. If the back points to the first element and we want to remove the

element from the back, then we need to set rear = n-1 where n is

the size of the array as shown in the figure below:

munotes.in

## Page 171

171

Let's create a deque program.

The following are the six functions we used in the following program:

● enqueue_front (): is used to insert the element from the front-end.

● enqueue_rear (): used to insert the element from the back.

● dequeue_front (): used to remove the interface element.

● dequeue_rear (): is used to delete the element from the back.

● getfront (): used to return the front element of the deque.

● getrear (): used to return the element after the deque.

Program:

#defined size 5

#include

int deque [size];

int f = -1, r = -1;

// the enqueue_front function will insert the value from the front

void enqueue_front (int x)

{

if ((f == 0 && r == size-1) || (f == r + 1))

{

printf ("what is full");

}

plus if ((f == - 1) && (r == - 1))

{

munotes.in

## Page 172

172 f = r = 0;

deque [f] = x;

}

yes no (f == 0)

{

f = dimension-1;

deque [f] = x;

}

the rest

{

f = f-1;

deque [f] = x;

}}

// the enqueue_rear function will insert the value from behind

void enqueue_rear (int x)

{

if ((f == 0 && r == size-1) || (f == r + 1))

{

printf ("what is full");

}

plus if ((f == - 1) && (r == - 1))

{

r = 0;

deque [r] = x;

}

plus if (r == size-1)

{

r = 0;

deque [r] = x;

}

the rest

{

r ++;

deque [r] = x; munotes.in

## Page 173

173 }}

// the display function prints the entire value of deque.

blank screen ()

{

int i = f;

printf ("\ n Elements in a deque:");

while (i! = r)

{

printf ("% d", deque [i]);

i = (i + 1)% of the dimension;

}

printf ("% d", deque [r]);

}

// The getfront function retrieves the first value of the deque.

empty getfront ()

{

if ((f == - 1) && (r == - 1))

{

printf ("What is empty");

}

the rest

{

printf ("\ nThe value of the front is:% d", deque [f]);

}}

// The getrear function retrieves the last value of the deque.

getrear empty ()

{

if ((f == - 1) && (r == - 1))

{

printf ("What is empty");

}

the rest

{

printf ("\ nThe bottom value is:% d", deque [r]); munotes.in

## Page 174

174 }}

// The dequeue_front () function removes the element from the front

empty dequeue_front ()

{

if ((f == - 1) && (r == - 1))

{

printf ("What is empty");

}

if not (f == r)

{

printf ("\ nThe deleted item is% d", deque [f]);

f = -1;

r = -1;

}

plus if (f == (size-1))

{

printf ("\ nThe deleted item is% d", deque [f]);

f = 0;

}

the rest

{

printf ("\ nThe deleted item is% d", deque [f]);

f = f + 1;

}}

// the dequeue_rear () function removes the element from the back

dequeue_rear empty ()

{

if ((f == - 1) && (r == - 1))

{

printf ("What is empty");

}

if not (f == r)

{

printf ("\ nThe deleted item is% d", deque [r]); munotes.in

## Page 175

175 f = -1;

r = -1;

}

if not (r == 0)

{

printf ("\ nThe deleted item is% d", deque [r]);

r = dimension-1;

}

the rest

{

printf ("\ nThe deleted item is% d", deque [r]);

r = r-1;

}}

main integer ()

{

// entering a value from the front.

enqueue_front (2);

// entering a value from the front.

enqueue_front (1);

// entering a value from behind.

rear_tail (3);

// entering a value from behind.

enqueue_rear (5);

// entering a value from behind.

enqueue_rear (8);

// Call the view function to retrieve the deque values

show();

// Get the front value front

getfront ();

// Get the return value.

getrear ();

// remove a foreground value

dequeue_front ();

// clear a value from the back munotes.in

## Page 176

176dequeue_rear ();

// Call the view function to retrieve the deque values

show();

returns 0;

}

Production:

Question:

1. What is a dequeue?

a) A queue with insert/delete defined for both front and rear ends of the queue

b) A queue implemented with a doubly linked list

c) A queue implemented with both singly and doubly linked lists

d) A queue with insert/delete defined for front side of the queue

2. What are the applications of dequeue?

a) A-Steal job scheduling algorithm

b) Can be used as both stack and queue

c) To find the maximum of all sub arrays of size k

d) To avoid collision in hash tables

3. What is the time complexity of deleting from the rear end of the dequeue

implemented with a singly linked list?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n 2)

munotes.in

## Page 177

177Module VI (Tree)

Experiment No-1

Aim:

Creating Binary search tree.

Objective:

Writing C++ program to create binary search tree.

Theory:

A binary tree is a special type of tr ee that can only have up to two

children. This means that a particular node in a binary tree can have no

child, one child, or two children but not more. A Binary search tree is a

type of binary tree.

Binary Search Tree is a data structure in which nodes are arranged

in a specific order.

It has one root node (topmost node in hierarchy).

The left subtree of a root node contains value lesser than the root

node’s value.

The right subtree of a root node contains value greater than the

root node’s value.

The left and right subtree of the root node each must also be a

binary search tree.

Some of the important terms are as follows:

Root: T h e r o o t n o d e i s t h e t o p m o s t n o d e i n t h e t r e e h i e r a r c h y . I n o t h e r

words, the root node is the one that doesn't have any parent.

Child node: I f t h e n o d e i s a d e s c e n d a n t o f a n y n o d e , t h e n t h e n o d e i s

known as a child node.

Parent: If the node contains any sub-node, then that node is said to be the

parent of that sub-node.

Sibling: The nodes that have the same parent are known as siblings.

Leaf Node : The node of the tree, which doesn't have any child node, is

called a leaf node. A leaf node is the bottom-most node of the tree. There munotes.in

## Page 178

178can be any number of leaf nodes present in a general tree. Leaf nodes can

also be called external nodes.

Internal nodes: A n o d e t h a t h a s a t l e a s t o n e c h i l d n o d e i s k n o w n a s a n

internal node.

Ancestor node: An ancestor of a node is any predecessor node on a path

from the root to that node.

Descendant: T h e i m m e d i a t e s u c c e s s o r o f t h e g i v e n n o d e i s k n o w n a s a

descendant of a node.

Algorithm:

Inserting node in BST

1. Allocate the memory for tree.

2. Set the data part to the value and set the left and right pointer of

tree, point to NULL.

3. If the item to be inserted is the first element of the tree, then the

left and right of this node will point to NULL.

4. Else, check whether the item is le ss than the root element of the

tree, if this is true, then recursiv ely perform this operation with the

left sub tree of the root.

5. If this is false, then perform this operation recursively with the

right sub-tree of the root. 11

6 19

4 9

Binary search Tree Example 22 ROOT

Right Sub Tree Left Sub Tree

munotes.in

## Page 179

179Program:

#include

#include

#include

using namespace std;

void insert(int);

struct node

{

int data;

struct node *left;

struct node *right;

};

struct node *root;

int main ()

{

int choice,item;

do

{

cout<<"\nEnter the item whic h you want to insert?\n";

cin>>item;

insert(item);

cout<<"\n Press 0 to insert more? \n";

cin>>choice;

}while(choice == 0);

return 0;

}

void insert(int item)

{

struct node *ptr, *parentptr , *nodeptr;

ptr = (struct node *) malloc(sizeof (struct node));

if(ptr == NULL)

{ munotes.in

## Page 180

180cout<<"cannot insert";

}

else

{

ptr -> data = item;

ptr -> left = NULL;

ptr -> right = NULL;

if(root == NULL)

{

root = ptr;

root -> left = NULL;

root -> right = NULL;

}

else

{

parentptr = NULL;

nodeptr = root;

while(nodeptr != NULL)

{

parentptr = nodeptr;

if(item < nodeptr->data)

{

nodeptr = nodeptr -> left;

}

else

{

nodeptr = nodeptr -> right;

}

}

if(item < parentptr -> data)

{

parentptr -> left = ptr; munotes.in

## Page 181

181}

else

{

parentptr -> right = ptr;

}

}

cout<<"Node Inserted";

}

OUTPUT:

Question:

1) The following numbers are inserted into an empty binary search

tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of

the binary search tree (the height is the maximum distance of a leaf

node from the root)?

A. 2

B. 3

C. 5

D. 4

munotes.in

## Page 182

1822) Construct a Binary search tree by inserting the following numbers

from left to right:

11,6,8,19,4,10,5,18,43,49,31

3) A binary search tree is generated by inserting in order the

following integers:

50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24

The number of nodes in the left subtree and right subtree of the

root respectively is

A. (4, 7)

B. (7, 4)

C. (8, 3)

D. (3, 8)

Experiment No2

Aim:

Traversal of Binary Search Tree

Objective:

W r i t i n g c + + p r o g r a m t o t r a v e r s e t h r o u g h t h e B i n a r y S e a r c h t r e e

using all the three method.

Theory:

Traversal refers to the process of visiting each node in a tree

(binary search tree). Because, all nodes are connected via edges (links),

traversing always start from the root (head) node. That is, we cannot

randomly access a node in a tree. There are three ways in which we can

traverse a binary search tree −

1) In-order Traversal

2) Pre-order Traversal

3) Post-order Traversal

1) In Order Traversal (left-root-right)

In this traversal method, the left subtree is visited first, then the

root and later the right sub-tree. If a bi nary tree is traverse d in in-order, the

output will produce sorted key va lues in an ascending order. munotes.in

## Page 183

183Example:

If the above binary search tree is traversed using In-Order

Traversal method then the node traver se will be in the following order:-

8-10-12-16-17-20-24

In the above example we start from 16, and following in-order

traversal, we move to its left subtree 10. 10 is also traversed in-order. The

process goes on until all the nodes are visited.

2) Pre-Order Traversal (Root-Left-Right)

In this traversal method, the root nod e is visited first, then the left

subtree and finally the right subtree.

Consider the fig 2.1, if this binary search tree is traversed using Pre-

Order Traversal method, then the node t r a v e r s e w i l l b e i n t h e f o l l o w i n g

order: -

16-10-8-12-20-17-24

We start from 16, and following pre-order traversal, we first

visit 16 itself and then move to its left subtree 10. 10 is also traversed pre-

order. The process goes on until all the nodes are visited. 16

10

8 12 20

24 17 Root

Left-Sub Tree Right Sub Tree

Fig:2.1

munotes.in

## Page 184

1843) Post-Order Traversal (Left-Right-Root)

In this traversal method, the root node is visited last, hence it is

called as Post Order Traversal. First, we traverse the left subtree, then the

right subtree and finally the root node.

Consider the fig 2.1, if this bina ry search tree is traversed using

Post-Order Traversal method, then the node traverse will be in the

following order: -

8-12-10-17-24-20-16

We start from 16, and following post-order tr aversal, we first visit

the left subtree 10. 10 i s a l s o t r a v e r s e d p o s t - o r d e r . T h e p r o c e s s g o e s o n

until all the nodes are visited.

Algorithm:

Inorder(tree)

1. Traverse the left subtree, i.e., call Inorder(left-subtree)

2. Visit the root.

3. Traverse the right subtree, i.e., call Inorder(right-subtree)

Preorder (tree)

1. Visit the root.

2. Traverse the left subtree, i.e., call Preorder(left-subtree)

3. Traverse the right subtree, i.e., call Preorder(right-subtree)

Postorder(tree)

1. Traverse the left subtree, i.e., call Postorder(left-subtree)

2. Traverse the right subtree, i.e., call Postorder(right-subtree)

3. Visit the root.

Program:

# include

# include

using namespace std;

// Binary Search Tree Node Declaration

struct node

{

int info;

struct node *left; munotes.in

## Page 185

185 struct node *right;

}*root;

// Class Declaration for Binary Search Tree

class BST

{

public:

void insert(node *,node *) ;

void preorder(node *);

void inorder(node *);

void postorder(node *);

void display(node *, int);

BST()

{

root = NULL;

}

};

// Main Contains Menu

int main()

{

int choice, num;

BST bst;

node *temp;

while (1)

{

// Main menu for Binary Search Tree Operations

cout<<"-----------------"< cout<<"Operations on BST"< cout<<"-----------------"< cout<<"1.Insert Element "<

## Page 186

186 cout<<"2.Inorder Traversal"< cout<<"3.Preorder Traversal"< cout<<"4.Pos torder Traver sal"< cout<<"5.Display"< cout<<"6.Quit"< cout<<"Enter your choice : ";

cin>>choice;

switch(choice)

{

case 1:

temp = new node;

cout<<"Enter the number to be inserted : ";

cin>>temp->info;

bst.insert(root, temp);

break;

c a s e 2 :

cout<<"Inorder Traversal of BST:"< bst.inorder(root);

cout< break;

case 3:

cout<<"Preorder Traversal of BST:"< bst.preorder(root);

cout< break;

case 4:

cout<<"Postorder Traversal of BST:"< bst.postorder(root);

cout< break;

case 5:

cout<<"Display BST:"<

## Page 187

187 bst.display(root,1);

cout< break;

case 6:

exit(1);

default:

cout<<"Wrong choice"< }

}

}

// Inserting Element into the Binary Search Tree

void BST::insert(node *tree, node *newnode)

{

if (root == NULL)

{

root = new node;

root->info = newnode->info;

root->left = NULL;

root->right = NULL;

cout<<"Root Node is Added"< return;

}

if (tree->info == newnode->info)

{

cout<<"Element already in the tree"< return;

}

if (tree->info > newnode->info)

{

if (tree->left != NULL)

{ munotes.in

## Page 188

188 insert(tree->left, newnode);

}

else

{

tree->left = newnode;

(tree->left)->left = NULL;

(tree->left)->right = NULL;

cout<<"Node Added To Left"< return;

}

}

else

{

if (tree->right != NULL)

{

insert(tree->right, newnode);

}

else

{

tree->right = newnode;

(tree->right)->left = NULL;

(tree->right)->right = NULL;

cout<<"Node Added To Right"< return;

}

}

}

// Pre Order Traversal

void BST::preorder(node *ptr)

{

if (root == NULL) munotes.in

## Page 189

189 {

cout<<"Tree is empty"< return;

}

if (ptr != NULL)

{

cout<info<<" ";

preorder(ptr->left);

preorder(ptr->right);

}

}

// In Order Traversal

void BST::inorder(node *ptr)

{

if (root == NULL)

{

cout<<"Tree is empty"< return;

}

if (ptr != NULL)

{

inorder(ptr->left);

cout<info<<" ";

inorder(ptr->right);

}

}

// Postorder Traversal

void BST::postorder(node *ptr)

{

if (root == NULL) munotes.in

## Page 190

190 {

cout<<"Tree is empty"< return;

}

if (ptr != NULL)

{

postorder(ptr->left);

postorder(ptr->right);

cout<info<<" ";

}

}

// Display Binary Search Tree Structure

void BST::display(node *ptr, int level)

{

int i;

if (ptr != NULL)

{

display(ptr->right, level+1);

cout< if (ptr == root)

cout<<"Root->: ";

else

{

for (i = 0;i < level;i++)

cout<<" ";

}

cout<info;

display(ptr->left, level+1);

}

}

munotes.in

## Page 191

191Output:

munotes.in

## Page 192

192

Question:

1) What is the specialty about the in-order traversal of a binary search

tree?

a) It traverses in a non-increasing order

b) It traverses in an increasing order

c) It traverses in a random fashion

d) It traverses based on priority of the node

2) The in-order and preorder traversal of a binary tree are d b e a f c g

and a b d e c f g, respectively. The post-order traversal of the

binary tree is:

a) d e b f g c a

b) e d b g f c a

c) e d b f g c a

d) d e f g b c a

3) Construct a binary search tree with the below information.

The preorder traversal of a binary search tree 10, 4, 3, 5, 11, 12.

a) 11

10 12

5 3 4munotes.in

## Page 193

193b)

c)

d)

Experiment No :3

Aim:

Finding Maximum and Minimum Node of the binary search tree.

Objective:

Writing c++ program to find maximum and minimum node of the binary

search tree.

Theory:

As in the binary search tree, nodes less than root node goes to the

left and nodes greater than root node goes to the right. So, in Binary

Search Tree, we can find maximum node by traversing right pointers until 12

10 11

5 3 410

4 11

3 5 1210

4 11

5 3 12

munotes.in

## Page 194

194we reach the rightmost node. Similarly, we can find minimum node by

traversing left pointer until we reach the leftmost node.

For example, consider the following Binary Search Tree,

As shown in the above figure, the minimum node is obtained by traversing

left sub tree and maximum node is obtained by traversing right sub tree.

In the above example 8 is the minimum node and 30 is the maximum node

of the binary search tree.

Algorithm:

Finding Minimum Node:

1. Starting from the root node go to its left child.

2. Keep traversing the left children of each node until a node with no

left child is reached. That node is a node with minimum value.

Finding Maximum Node:

1. Starting from the root node go to its right child.

2. Keep traversing the right children of each node until a node with

no right child is reached. That node is a node with maximum value.

Program:

// C++ program to find maximum or minimum element in binary search

tree

# include 14

10

8 12 20

30 18 Root

Minimum Node Maximum Node

munotes.in

## Page 195

195# include

using namespace std;

struct node

{

int key;

struct node *left, *right;

};

// A function to create a new BST node

struct node *newNode(int item)

{

struct node *temp = (struct node *)malloc(sizeof(struct node));

temp->key = item;

temp->left = temp->right = NULL;

return temp;

}

/* A function to insert a new node with given value or key in BST */

struct node* insert(struct node* node, int key)

{

struct node *newNode(int );

/* If the tree is empty, return a new node */

if (node == NULL) return newNode(key);

/* Otherwise, recur down the tree */

if (key < node->key)

node->left = insert(node->left, key);

else if (key > node->key)

node->right = insert(node->right, key);

/* return the (unchanged) node pointer */

return node;

}

/* Given a non-empty binary search tree,

return the minimum data value found in that

tree. Note that the entire tree does not need

to be searched. */

int minValue(struct node* node)

{

struct node* current = node; munotes.in

## Page 196

196

/* loop down to find the leftmost leaf */

while (current->left != NULL)

{

current = current->left;

}

return(current->key);

}

/* Given a non-empty binary search tree,

return the maximum data value found in that

tree. Note that the entire tree does not need

to be searched. */

int maxValue(struct node* node)

{

struct node* current = node;

while (current->right != NULL)

{

current = current->right;

}

return(current->key);

}

int main()

{

int maxValue(struct node* );

struct node* insert(struct node* , int );

int minValue(struct node* );

struct node *root = NULL;

root = insert(root, 8);

insert(root, 3);

insert(root, 10);

insert(root, 1);

insert(root, 6);

insert(root, 4);

insert(root, 7);

insert(root, 5);

insert(root, 10);

insert(root, 9);

insert(root, 13);

insert(root, 11); munotes.in

## Page 197

197 insert(root, 18);

insert(root, 12);

insert(root, 2);

cout << "\n Minimum value in BST is " << minValue(root)< cout << "\n Maximum value in BST is " << maxValue(root);

return 0;

}

Output:

Question:

1) What will be the minimum element of the binary search tree if no

left subtree exist?

2) Which of the following is false about a binary search tree?

a) The left child is always lesser than its parent

b) The right child is always greater than its parent

c) The left and right sub-trees should also be binary search trees

d) In order sequence gives decreasing order of elements

3) What are the worst case and averag e case complexities of a binary

search tree?

a) O(n), O(n)

b) O(logn), O(logn)

c) O(logn), O(n)

d) O(n), O(logn) munotes.in

## Page 198

198Experiment:4

Aim:

Counting number of nodes in binary search tree.

Objectives:

Writing c++ program to count number of nodes in the binary

search tree.

Theory:

To count number of nodes in the binary search tree we can use the

following formula: -

Total No. of nodes in BST=Total No. of nodes in left sub-tree +

Total no. of node in right sub-tree + 1

In the above binary search tree, the total number of Nodes is 6.

No. of nodes in Left Sub-tree=3

No. of nodes in Right sub-tree=2

No. of Root Node=1

So, the total no of nodes will be = 3+2+1=6.

Algorithm:

1. Initialize “count” variable as 1.

2. If root is NULL, return 0.

3. Else, count = count + countNodes(root -> left) and

count = count + countNodes(root -> right).

4. Then, return count.

5. End If 25

16 39

14 17

Binary search Tree 40 ROOT

Right Sub Tree Left Sub Tree

munotes.in

## Page 199

199Program:

#include

using namespace std;

int n=1;

struct node

{

i n t d a t a ;

n o d e * l e f t ;

n o d e * r i g h t ;

};

struct node* getNode(int data)

{

n o d e * n e w N o d e = n e w n o d e ( ) ;

n e w N o d e - > d a t a = d a t a ;

n e w N o d e - > l e f t = N U L L ;

n e w N o d e - > r i g h t = N U L L ;

r e t u r n n e w N o d e ;

}

struct node* Insert(struct node* root, int data)

{

i f ( r o o t = = N U L L )

r e t u r n g e t N o d e ( d a t a ) ;

i f ( d a t a < r o o t - > d a t a )

r o o t - > l e f t = I n s e r t ( r o o t - > l e f t , d a t a ) ;

e l s e i f ( d a t a > r o o t - > d a t a )

r o o t - > r i g h t = I n s e r t ( r o o t - > r i g h t , d a t a ) ;

r e t u r n r o o t ;

}

int CountNodes(node*root)

{

i f ( r o o t = = N U L L )

r e t u r n 0 ;

i f ( r o o t - > l e f t ! = N U L L )

{

n = n + 1 ; munotes.in

## Page 200

200 n = C o u n t N o d e s ( r o o t - > l e f t ) ;

}

i f ( r o o t - > r i g h t ! = N U L L )

{

n = n + 1 ;

n = C o u n t N o d e s ( r o o t - > r i g h t ) ;

}

r e t u r n n ;

}

int main()

{

n o d e * r o o t = N U L L ;

r o o t = I n s e r t ( r o o t , 3 ) ;

I n s e r t ( r o o t , 4 ) ;

I n s e r t ( r o o t , 2 ) ;

I n s e r t ( r o o t , 5 ) ;

I n s e r t ( r o o t , 1 ) ;

I n s e r t ( r o o t , 6 ) ;

I n s e r t ( r o o t , 8 ) ;

c o u t < < " T o t a l N u m b e r o f N o d e s i n t h e B S T =

"<

r e t u r n 0 ;

}

Output:

munotes.in

## Page 201

201Questions:

1) What are sub trees in binary search tree?

2) How to calculate height of the binary search tree?

3) What are the various application of binary search tree?

Experiment No-5

Aim:

Creating Max Heap

Objective:

Writing c++ program to create max heap data structure.

Theory:

Heap : A Heap is a special Tree-based data structure in which the tree is a

complete binary tree, that is, each level of the tree is completely filled,

except possibly the bottom leve l. At this level, it is filled from left to right.

Generally, Heaps can be of two types:

Max-Heap : In a Max-Heap the key present at the root node must be

greatest among the keys present at all of it’s children. The same property

must be recursively true for all sub-trees in that Binary Tree.

Min-Heap : In a Min-Heap the key present at the root node must be

minimum among the keys present at all of it’s children. The same property

must be recursively true for all sub-trees in that Binary Tree.

Note: Heap data Structure is implemented using Arrays in

Programming Languages.

Example of Max-Heap

99

40 50

10 15

MaxHeap 40ROOT

50munotes.in

## Page 202

202In the above figure , 99 is the root node and it is the highest node

in the tree.In left sub tree 40 is parent of 10 and 15, which is again

greater.In right sub tree 50 is the parent of 50 and 40,which is also greater.

Array Representation of the above max-heap:

Note: In Heap data structure two no des can have same value, that is

repetition of the value is allo wed in heap data structure.

Algorithm:

1. Create a new node at the end of heap.

2. Assign new value to the node.

3. Compare the value of this child node with its parent.

4. If value of parent is less than child, then swap them.

5. Repeat step 3 & 4 until Heap property holds (i.e. parent >= child).

Program:

#include

using namespace std;

void max_heap(int *a, int m, int n) {

int j, t;

t = a[m];

j = 2 * m;

while (j <= n) {

if (j < n && a[j+1] > a[j])

j = j + 1;

if (t > a[j])

break;

else if (t <= a[j]) {

a[j / 2] = a[j];

j = 2 * j;

}

}

a[j/2] = t;

return;

}

void build_maxheap(int *a,int n) {

int k;

for(k = n/2; k >= 1; k--) { 99 40 50 10 15 50 40

Index

0 1 2 3 4 5 6

munotes.in

## Page 203

203 max_heap(a,k,n);

}

}

int main() {

int n, i;

cout<<"enter no of elements of array\n";

cin>>n;

int a[30];

for (i = 1; i <= n; i++) {

cout<<"enter elements"<<" "<<(i)< cin>>a[i];

}

build_maxheap(a,n);

cout<<"Max Heap\n";

for (i = 1; i <= n; i++) {

cout< }

}

Output:

munotes.in

## Page 204

204Questions:

1. Consider a binary max-heap implemented using an array. Which

one of the following arrays represents a binary max-heap? (GATE

CS 2009)

a) 25,12,16,13,10,8,14

b) 25,12,16,13,10,8,14

c) 25,14,16,13,10,8,12

d) 25,14,12,13,10,8,16

2. When do you need to use a heap?

3. Construct a max heap using [12,10,9,8,5,2].

Experiment No-6

Aim: Creating Min Heap

Objective:

Writing c++ program to create min heap data structure.

Theory:

Heap : A Heap is a special Tree-based data structure in which the tree is a

complete binary tree, that is, each level of the tree is completely filled,

except possibly the bottom leve l. At this level, it is filled from left to right.

Generally, Heaps can be of two types:

Max-Heap : In a Max-Heap the key present at the root node must be

greatest among the keys present at all of it’s children. The same property

must be recursively true for all sub-trees in that Binary Tree.

Min-Heap : In a Min-Heap the key present at the root node must be

minimum among the keys present at all of it’s children. The same property

must be recursively true for all sub-trees in that Binary Tree.

Example of Min-Heap

10

14 15

25 30

MinHeap 27ROOT

42

35 44 33 munotes.in

## Page 205

205In the above figure, 10 is the root node and it is the smallest node in the

tree. Same is true for every sub node.In min heap,the value of the root

node is less than or equal to either of its children.

Array Representation of the above min-heap:

Note: In Heap data structure two no des can have same value, that is

repetition of the value is allo wed in heap data structure.

Algorithm:

1. Create a new node at the end of heap.

2. Assign new value to the node.

3. Compare the value of this child node with its parent.

4. If value of parent is greater than child, then swap them.

5. Repeat step 3 & 4 until Heap property holds(i.e parent <= child).

Program:

#include

#include

using namespace std;

void min_heap(int *a, int m, int n){

int j, t;

t= a[m];

j = 2 * m;

while (j <= n) {

if (j < n && a[j+1] < a[j])

j = j + 1;

if (t < a[j])

break;

else if (t >= a[j]) {

a[j/2] = a[j];

j = 2 * j;

}

}

a[j/2] = t;

return;

}

void build_minheap(int *a, int n) { 10 14 15 25 30 42 27 44 35 33

Index

0 1 2 3 4 5 6 7 8 9

munotes.in

## Page 206

206 int k;

for(k = n/2; k >= 1; k--) {

min_heap(a,k,n);

}

}

int main() {

int n, i;

cout<<"enter no of elements of array\n";

cin>>n;

int a[30];

for (i = 1; i <= n; i++) {

cout<<"enter element"<<" "<<(i)< cin>>a[i];

}

build_minheap(a, n);

cout<<"Min Heap\n";

for (i = 1; i <= n; i++) {

cout< }

getch();

}

Output:

munotes.in

## Page 207

207Questions:

1. In a min-heap, element with the lowest key is always in which

node?

a) Leaf node

b) Root node

c) First node of left sub tree

d) First node of right sub tree

2. Which one of the following array elements represents a binary min

heap?

a) 12 10 8 25 14 17

b) 8 10 12 25 14 17

c) 25 17 14 12 10 8

d) 14 17 25 10 12 8

3. The ascending heap property is ___________

a) A[Parent(i)] =A[i]

b) A[Parent(i)] <= A[i]

c) A[Parent(i)] >= A[i]

d) A[Parent(i)] > 2 * A[i]

Experiment No:7

Aim:

Performing Reheap Up operation on max-Heap and min Heap.

Objective:

Writing c++ program to perform reheap operation i.e insert new

element in the Heap.

Theory:

Reheap Up is used when inserting new element in the heap.

Whenever new element is added in the heap it is always added to the first

empty leaf at the bottom level from th e leftmost side. After that heap is

rearranged so that newly added element reached its proper place. For max

heap swapping is done, if new value is greater than previous/parent node.

For min heap swapping is done, if new value is smaller than

previous/parent node.

munotes.in

## Page 208

208Suppose the Heap is a Max-Heap as shown below:

The new element to be inserted is 15.

Process:

Step 1: Insert the new element at the end.

Step 2: Heapify the new element following bottom-up approach.

15 is more than its parent 3, swap them.

8

5

3 2 4ROOT

158

5 3

2 4ROOT

158

5 3

2 4ROOT

munotes.in

## Page 209

20915 is again more than its parent 8, swap them.

Therefore, the final heap after insertion is:

This Entire process is Known as ReHeap Up. The process of insertion

to Min-heap is similar to that of Max-heap but only one difference is that

the value of parent node is always lesser than the child node.

Algorithm:

To insert an element into heap we need to follow 2 steps:

1. Insert the element at last position of the heap and increase the size

of heap n to n+1.

2. Recursively test and swap the new value with previous/parent node

as long as the heap property is not satisfied. For max heap swap if

new value is greater than previous/parent node. For min heap swap

if new value is smaller than previous/parent node.

85

3 2 4ROOT

1585

3 2 4ROOT

15

munotes.in

## Page 210

210Program:

C++ program to insert new element in Max-Heap:

#include

#include

using namespace std;

int main(){

int n,i,m; //n is no of elements,i is normal integer and m is used to

not change n

cout<<"How Much Elements are in Your Heap: ";

cin>>n;

long H[n+5]; //H is Ar ray to take input the elements of heap

cout<<"Enter All Elements of Max Heap in Sequential

Representation:"< for(i=1;i<=n;i++){

cin>>H[i];

}

cout<

cout<<"Before Insertion:"< for(i=1;i<=n;i++){

cout< }

cout<

cout<<"What will you Insert Now: ";

cin>>H[n+1]; //Inserting new element at the last of heap tree

cout< m=n=n+1; //Increasing total element number in heap

while(H[m]>H[m/2]){ //Taking in exact position the inserted

element

swap(H[m],H[m/2]);

m=m/2;

}

munotes.in

## Page 211

211 cout<<"After Insertion:"< for(i=1;i<=n;i++){

cout< }

cout< return 0;

}

Output:

C++ program to insert new element in Min-Heap:

#include

#include

using namespace std;

int main(){

int n,i,m; //n is no of elements,i is normal integer and m is used to

not change n

cout<<"How Much Elements are in Your Heap: ";

cin>>n;

long H[n+5]; //H is Ar ray to take input the elements of heap munotes.in

## Page 212

212 cout<<"Enter All Elements of Min-Heap in Sequential

Representation:"< for(i=1;i<=n;i++){

cin>>H[i];

}

cout<

cout<<"Before Insertion:"< for(i=1;i<=n;i++){

cout< }

cout<

cout<<"What will you Insert Now: ";

cin>>H[n+1]; //Inserting new element at the last of heap tree

cout< m=n=n+1; //Increasing total element number in heap

while(H[m]element

swap(H[m],H[m/2]);

m=m/2;

}

cout<<"After Insertion:"< for(i=1;i<=n;i++){

cout< }

cout< return 0;

}

munotes.in

## Page 213

213Output:

Question:

1. What is the correct way of adding new element to the heap?

2. Explain reheap up process in detail?

3. What is mean by Heapify?

Experiment No:8

Aim:

Performing Reheap down operation on max-Heap and min Heap.

Objective:

Writing c++ program to perform reheap down i.e deletion of

element from the Heap.

Theory:

Reheap down is used when deleting an element from the heap. The

standard deletion operation on Heap is to delete the element present at the

root node of the Heap. That is if it is a Max Heap, the standard deletion

operation will delete the maximum element and if it is a Min heap, it will

delete the minimum element.

Since deleting an element at any intermediary position in the heap

can be costly, so we can simply replace the element to be deleted by the

last element and delete the last element of the Heap.

munotes.in

## Page 214

214Suppose the Heap is a Max-Heap as:

The element to be deleted is root, i.e. 20.

Process:

The last element is 13.

Step 1: Replace the last element with root, and delete it.

18 19

15 13ROOT 2018 19

15 13ROOT20

18 19

15 13ROOT

munotes.in

## Page 215

215

Step 2: Heapify root.

Final Heap:

This Entire process is Known as ReHeap Down.

Algorithm:

1. Replace the root or element to be deleted by the last element.

2. Delete the last element from the Heap and decrease the size of

heap by 1.

3. Since, the last element is now placed at the position of the root

node or at deleted element place. Recursively test and swap the

replaced value with next/child nodes as long as the heap property

is not satisfied. For max heap swap if replaced value is smaller

than next/child nodes. For min heap swap if replaced value is

greater than next/child nodes.

Program:

// C++ program for implement deletion in Heaps

#include

using namespace std;

// To heapify a subtree rooted with node i which is

// an index of arr[] and n is the size of heap

void heapify(int arr[], int n, int i)

{

i n t l a r g e s t = i ; / / I n i t i a l i z e l a r g e s t a s r o o t

i n t l = 2 * i + 1 ; / / l e f t = 2 * i + 1

i n t r = 2 * i + 2 ; / / r i g h t = 2 * i + 2

/ / I f l e f t c h i l d i s l a r g e r t h a n r o o t

i f ( l < n & & a r r [ l ] > a r r [ l a r g e s t ] ) 1819

15 13ROOT

munotes.in

## Page 216

216 l a r g e s t = l ;

/ / I f r i g h t c h i l d i s l a r g e r t h a n l a r g e s t s o f a r

i f ( r < n & & a r r [ r ] > a r r [ l a r g e s t ] )

l a r g e s t = r ;

/ / I f l a r g e s t i s n o t r o o t

i f ( l a r g e s t ! = i ) {

s w a p ( a r r [ i ] , a r r [ l a r g e s t ] ) ;

/ / R e c u r s i v e l y h e a p i f y t h e a f f e c t e d s u b - t r e e

h e a p i f y ( a r r , n , l a r g e s t ) ;

}

}

// Function to delete the root from Heap

void deleteRoot(int arr[], int& n)

{

/ / G e t t h e l a s t e l e m e n t

i n t l a s t E l e m e n t = a r r [ n - 1 ] ;

/ / R e p l a c e r o o t w i t h l a s t e l e m e n t

a r r [ 0 ] = l a s t E l e m e n t ;

/ / D e c r e a s e s i z e o f h e a p b y 1

n = n - 1 ;

/ / h e a p i f y t h e r o o t n o d e

h e a p i f y ( a r r , n , 0 ) ;

}

/* A utility function to print array of size n */

void printArray(int arr[], int n)

{

f o r ( i n t i = 0 ; i < n ; + + i )

c o u t < < a r r [ i ] < < " " ;

c o u t < < " \ n " ;

}

int main()

{

/ / A r r a y r e p r e s e n t a t i o n o f M a x - H e a p

/ / 8 munotes.in

## Page 217

217 / / / \

/ / 5 3

/ / / \

/ / 2 4

i n t a r r [ ] = { 8 , 5 , 3 , 4 , 2 } ;

i n t n = s i z e o f ( a r r ) / s i z e o f ( a r r [ 0 ] ) ;

cout<<"\n Array repr esentation of heap before deletion\n";

p r i n t A r r a y ( a r r , n ) ;

d e l e t e R o o t ( a r r , n ) ;

cout<<"\n Array representation of heap After deletion\n";

p r i n t A r r a y ( a r r , n ) ;

r e t u r n 0 ;

}

Output:

Question:

1. How many arrays are required to perform deletion operation in a

heap?

a. 1

b. 2

c. 3

d. 4 munotes.in

## Page 218

218

2. What is the time taken to perform a delete min operation?

a. O(N)

b. O(N log N)

c. O(log N)

d. O(N2)

3. Which element from the heap can be deleted?

Self-Learning Topics:

Expression Tree:

The expression tree is a binary tree in which each internal node

corresponds to the operator and each leaf node corresponds to the operand.

So, for example, expression tree for

4 + ((6+9) *3) would be:

Heap Sort:

Heap sort is a comparison-based sorting technique based on Heap

data structure Heap sort involves building a Heap data structure from the

given array and then utilizing th e Heap to sort the array.

+

4 *

6 93 +munotes.in

## Page 219

219

Module VII

Experiment No:1

Aim:

Graph Creation using Adjacency matrix

Objective:

Writing C++ program for representation of a graph using

adjacency matrix.

Theory:

A Graph is a non-linear data structure consisting of nodes and

edges. The nodes are sometimes also referred to as vertices and the edges

are lines or arcs that connect any two nodes in the graph. In other words,

we can say that, A Graph consists of a finite set of vertices (or nodes) and

set of Edges which connect a pair of nodes.

In the above Graph, the set of vertices V = {0,1,2,3,4} and the set of

edges E = {01, 12, 23, 34, 40, 14,24}.

Graph Terminology

Adjacency: A vertex is said to be adjacent to another vertex if there is an

edge connecting them. Vertices 2 and 0 are not adjacent because there is

no edge between them. 0

1 4

2 3

Graph Vertices Edge

munotes.in

## Page 220

220Path: A sequence of edges that allows you to go from vertex A to vertex

B is called a path. 0-1-2-4 is a path from vertex 0 to vertex 4.

Directed Graph: The edges in such a graph are represented by arrows to

show the direction of the edge.

Graph Representation:

The following are the two most commonly used representations of a

graph.

1. Adjacency Matrix

2. Adjacency List

Adjacency matrix representation of the Graph:

An adjacency matrix is used to represent adjacent nodes in the

graph. Two nodes are said to be adjacent if there is an edge connecting

them. We represent graph in the form of matrix in Adjacency matrix

representation. For a graph G, if there is an edge between two vertices a

and b then we denote it 1 in matrix. If there is no edge then denote it with

0 in matrix.

Adjacency Matrix is a 2D array of size V x V where V is the

number of vertices in a graph. Let the 2D array be adj [][], a slot adj[i][j] =

1 indicates that there is an edge from vertex i to vertex j. Adjacency matrix

for undirected graph is always symmetric. Adjacency Matrix is also used

to represent weighted graphs. If adj[i][j] = w, then there is an edge from

vertex i to vertex j with weight w.

Consider the following Graph and its Adjacency matrix Representation:

B

C A

D

Undirected Graph munotes.in

## Page 221

221

Adjacency matrix representation of the above undirected graph:

A B C D

A 0 1 0 1

B 1 0 1 0

C 0 1 0 1

D 1 0 1 0

Adjacency matrix representation of the above Directed graph:

A B C D

A 0 1 0 1

B 0 0 1 0

C 0 0 0 0

D 0 0 1 0

Algorithm:

1. Create a 2D array (say Adj[N+1] [N+1]) of size NxN and initialize

all value of this matrix to zero. Store all the edges of the graph in

arr [] []. B

CA

D

Directed Graph

munotes.in

## Page 222

2222. For each edge in the arr [][], Update value at Adj[X][Y] and

Adj[Y][X] to 1, denotes that there is a edge between X and Y.

3. Display the Adjacency Matrix after the above operation for all the

pairs in arr[][] is completed.

Program:

#include

using namespace std;

int vertArr[20][20]; //the adjacency matrix initially 0

int count = 0;

void displayMatrix(int v) {

int i, j;

for(i = 0; i < v; i++) {

for(j = 0; j < v; j++) {

cout << vertArr[i][j] << " ";

}

cout << endl;

}

}

void add_edge(int u, int v) { //function to add edge into the matrix

vertArr[u][v] = 1;

vertArr[v][u] = 1;

}

int main() {

int v = 5; //there are 6 vertices in the graph

add_edge(0, 1);

add_edge(0, 2);

add_edge(0, 4);

add_edge(1, 3);

add_edge(3, 2);

add_edge(2, 4);

displayMatrix(v); munotes.in

## Page 223

223 return 0;

}

Output:

Note: The above output is for the following graph:

Question:

1) Give various application of graph data structure in our daily life.

2) Given below the Adjacency matrix representation of the

graph,Draw the Graph: 1

3 0

2 4 munotes.in

## Page 224

224

A B C D

A 0 1 1 0

B 0 0 0 1

C 0 0 0 1

D 0 0 0 0

3) Which of the following statements for a simple graph is correct?

a) Every path is a trail

b) Every trail is a path

c) Every trail is a path as well as every path is a trail

d) None of the mentioned

Experiment No:2

Aim:

Performing Breadth First Search (BFS) traversal on Graph data structure.

Objective:

Writing C++ program to perfor m BFS traversal on Graph.

Theory:

Graph Traversal:

There are two types of graph traversal algorithms. These are called the

Breadth First Search (BFS)and Depth First Search (DFS).

Breadth First Search (BFS)

The Breadth First Search (BFS) traversal is an algorithm, which is

used to visit all of the nodes of a gi ven graph. In this traversal algorithm

one node is selected and then all of the adjacent nodes are visited one by

one. After completing all of the adja cent vertices, it moves further to

check another vertices and checks its adjacent vertices again. This process

will continue until all nodes are visited.

munotes.in

## Page 225

225Here, are important rules for using BFS algorithm:

A queue (FIFO-First in First Out) data structure is used by BFS.

You mark any node in the graph as root and start traversing the

data from it.

BFS traverses all the nodes in the graph and keeps dropping them

as completed.

BFS visits an adjacent unvisited node, marks it as done, and inserts

it into a queue.

Removes the previous vertex from the queue in case no adjacent

vertex is found.

BFS algorithm iterates until all the vertices in the graph are

successfully traversed and marked as completed.

There are no loops caused by BFS during the traversing of data

from any node.

Consider the following graph:

Traversal of the above graph Using BFS will be: 1-2-3-5-4.

According to BFS traversa l method, first step is to visit any vertex,

so we have visited 1. Next step is to explore that visited vertex, that means

we have to visit adjacent vertex of 1, so we have visited 2,3 and 5 . Again

we have to visit any unvisited vertex, so we have visited 4.

Algorithm:

A standard BFS implementation puts each vertex of the graph into one of

two categories:

1. Visited

2. Not Visited 2

4 1

35

Undirected Graph munotes.in

## Page 226

226The purpose of the algorithm is to mark each vertex as visited while

avoiding cycles.

The algorithm is as follows:

1. Start by putting any one of the graph's vertices at the back of a

queue.

2. Take the front item of the queue and add it to the visited list.

3. Create a list of that vertex's adjacent nodes. Add the ones which

aren't in the visited list to the back of the queue.

4. Keep repeating steps 2 and 3 until the queue is empty.

5. The graph might have two different disconnected parts so to make

sure that we cover every vertex, we can also run the BFS algorithm

on every node.

Program:

#include

#include

#include

using namespace std;

int cost[10][10],i,j,k,n,qu[10],front,rare,v,visit[10],visited[10];

int main()

{

int m;

cout <<"Enter no of vertices:";

cin >> n;

cout <<"Enter no of edges:";

cin >> m;

cout <<"\nEDGES \n";

for(k=1; k<=m; k++)

{

cin >>i>>j;

cost[i][j]=1;

}

cout <<"Enter initial vertex to traverse from:";

cin >>v;

cout <<"Visitied vertices:";

cout < visited[v]=1;

k=1;

while(k

## Page 227

227 {

for(j=1; j<=n; j++)

if(cost[v][j]!=0 && visited[j]!=1 && visit[j]!=1)

{

visit[j]=1;

qu[rare++]=j;

}

v=qu[front++];

cout< k++;

visit[v]=0;

visited[v]=1;

}

return 0;

}

Output:

Note: In the above program,while entering edges give space between two

vertexes of the edges.

munotes.in

## Page 228

228Questions:

1. The Date structure used in standard implementation of Breadth

First Search is?

a) Stack

b) Queue

c) LinkedList

d) Tree

2. In BFS,how many times a node is visited?

a) Once

b) Twice

c) Equivalent to number of indegree of the node

d) Thrice

3. Who describe the Best First Search algorithm using heuristic

evaluation rule?

a) Judea Pearl

b) Max Bezzel

c) Franz Nauck

d) Alan Turing

Experiment No:3

Aim:

Finding Minimum Spanning tree using Kruskal’s algorithm.

Objective:

Writing c++ program to find minimum spanning tree using

Kruskal’s algorithm from a given graph.

Theory:

For any connected and undirected graph, a spanning tree of that

graph is a subgraph that is a tree and connects all the vertices together. A

single graph can have many different spanning trees.

A minimum spanning tree (MST) or minimum weight spanning

tree for a weighted, connected, undirected graph is a spanning tree with a

weight less than or equal to the weight of every other spanning tree. The munotes.in

## Page 229

229weight of a spanning tree is the sum of weights given to each edge of the

spanning tree.

A minimum spanning tree has (V – 1) edges where V is the

number of vertices in the given graph.

Consider the following weighted graph.

To find the MST using Kruskal’s algorithm we have to follow the

following steps:

1) Remove any loop present in the graph. Check for any parallel edges in

the graph and remove any one (Edge with maximum weight will be

removed).

In above graph, there is two edges from A-B, they are called as

parallel edges, one with weight 5 and other with weight 10. So, the

edge with weight 10 will be removed.

2) Next, we have to sort the edges according to their weight in the

ascending order.

C D A B

E F73

8

3265

24 C D A B

E

Weighted Graph F 73

8

32 65

2 410

munotes.in

## Page 230

230So, for our example it will be:

Weight Edge

2 BD

2 DE

3 CD

3 AC

4 BE

5 AB

6 CB

7 AF

8 FC

3) Now pick all edges one by one from the sorted list of edges

Pick edge B-D: No cycle is formed, include it.

Pick edge D-E: No cycle is formed, include it.

Pick edge C-D: No cycle is formed, include it.

D B

E2

2 C 3 D B

E2

2 D B

2

munotes.in

## Page 231

231Pick edge A-C: No cycle is formed, include it.

Pick edge B-E: Since including this edge results in the cycle, discard it.

Pick edge A-B: Since including this edge results in the cycle, discard it.

Pick edge C-B: Since including this edge results in the cycle, discard it.

Pick edge A-F: No cycle is formed, include it.

Pick edge F-C: Since including this edge results in the cycle, discard it.

So, the final minimum spanning tree using Kruskal’s algorithm will be:

Algorithm:

Kruskal’s Algorithm

This algorithm will create spanning tree with minimum weight, from a

given weighted graph.

1. Begin

2. Remove loop and parallel edge.

3. Create the edge list of given graph, with their weights.

4. Sort the edge list according to their weights in ascending order. DB

E2

2C3 A

3

F 7 D B

E2

2 C 3 A

3

F 7 DB

E2

2C 3 A

3

munotes.in

## Page 232

2325. Draw all the nodes to create skeleton for spanning tree.

6. Pick up the edge at the top of the edge list (i.e., edge with

minimum weight).

7. Remove this edge from the edge list.

8. Connect the vertices in the skeleton with given edge. If by

connecting the vertices, a cycle is created in the skeleton, then

discard this edge.

9. Repeat steps 5 to 7, until n-1 edge s are added or list of edges is

over.

10. Return

Program:

// C++ program for Kruskal's algorithm

// to find Minimum Spanning Tree of a

// given connected, undirected and weighted

// graph

#include

using namespace std;

// a structure to represent a

// weighted edge in graph

class Edge {

public:

i n t s r c , d e s t , w e i g h t ;

};

// a structure to represent a connected,

// undirected and weighted graph

class Graph {

public:

/ / V - > N u m b e r o f v e r t i c e s , E - > N u m b e r o f e d g e s

i n t V , E ;

/ / g r a p h i s r e p r e s e n t e d a s a n a r r a y o f e d g e s .

/ / S i n c e t h e g r a p h i s u n d i r e c t e d , t h e e d g e

/ / f r o m s r c t o d e s t i s a l s o e d g e f r o m d e s t

/ / t o s r c . B o t h a r e c o u n t e d a s 1 e d g e h e r e .

E d g e * e d g e ;

}; munotes.in

## Page 233

233

// Creates a graph with V vertices and E edges

Graph* createGraph(int V, int E)

{

G r a p h * g r a p h = n e w G r a p h ;

g r a p h - > V = V ;

g r a p h - > E = E ;

g r a p h - > e d g e = n e w E d g e [ E ] ;

r e t u r n g r a p h ;

}

// A structure to represent a subset for union-find

class subset {

public:

i n t p a r e n t ;

i n t r a n k ;

};

// A utility function to find set of an element i

// (uses path compression technique)

int find(subset subsets[], int i)

{

/ / f i n d r o o t a n d m a k e r o o t a s p a r e n t o f i

/ / ( p a t h c o m p r e s s i o n )

i f ( s u b s e t s [ i ] . p a r e n t ! = i )

s u b s e t s [ i ] . p a r e n t

= f i n d ( s u b s e t s , s u b s e t s [ i ] . p a r e n t ) ;

r e t u r n s u b s e t s [ i ] . p a r e n t ;

}

// A function that does union of two sets of x and y

// (uses union by rank)

void Union(subset subsets[], int x, int y)

{

i n t x r o o t = f i n d ( s u b s e t s , x ) ;

i n t y r o o t = f i n d ( s u b s e t s , y ) ;

/ / A t t a c h s m a l l e r r a n k t r e e u n d e r r o o t o f h i g h munotes.in

## Page 234

234 / / r a n k t r e e ( U n i o n b y R a n k )

i f ( s u b s e t s [ x r o o t ] . r a n k < s u b s e t s [ y r o o t ] . r a n k )

s u b s e t s [ x r o o t ] . p a r e n t = y r o o t ;

e l s e i f ( s u b s e t s [ x r o o t ] . r a n k > s u b s e t s [ y r o o t ] . r a n k )

s u b s e t s [ y r o o t ] . p a r e n t = x r o o t ;

/ / I f r a n k s a r e s a m e , t h e n m a k e o n e a s r o o t a n d

/ / i n c r e m e n t i t s r a n k b y o n e

e l s e {

s u b s e t s [ y r o o t ] . p a r e n t = x r o o t ;

s u b s e t s [ x r o o t ] . r a n k + + ;

}

}

// Compare two edges according to their weights.

// Used in qsort() for sorting an array of edges

int myComp(const void* a, const void* b)

{

E d g e * a 1 = ( E d g e * ) a ;

E d g e * b 1 = ( E d g e * ) b ;

r e t u r n a 1 - > w e i g h t > b 1 - > w e i g h t ;

}

// The main function to construct MST using Kruskal's

// algorithm

void KruskalMST(Graph* graph)

{

i n t V = g r a p h - > V ;

E d g e r e s u l t [ V ] ; / / T n i s w i l l s t o r e t h e r e s u l t a n t M S T

i n t e = 0 ; / / A n i n d e x v a r i a b l e , u s e d f o r r e s u l t [ ]

i n t i = 0 ; / / A n i n d e x v a r i a b l e , u s e d f o r s o r t e d e d g e s

/ / S t e p 1 : S o r t a l l t h e e d g e s i n n o n - d e c r e a s i n g

/ / o r d e r o f t h e i r w e i g h t . I f w e a r e n o t a l l o w e d t o

/ / c h a n g e t h e g i v e n g r a p h , w e c a n c r e a t e a c o p y o f

/ / a r r a y o f e d g e s

q s o r t ( g r a p h - > e d g e , g r a p h - >E, sizeof(graph->edge[0]),

m y C o m p ) ;

/ / A l l o c a t e m e m o r y f o r c r e a t i n g V s s u b s e t s

s u b s e t * s u b s e t s = n e w s u b s e t [ ( V * s i z e o f ( s u b s e t ) ) ] ; munotes.in

## Page 235

235

/ / C r e a t e V s u b s e t s w i t h s i n g l e e l e m e n t s

f o r ( i n t v = 0 ; v < V ; + + v )

{

s u b s e t s [ v ] . p a r e n t = v ;

s u b s e t s [ v ] . r a n k = 0 ;

}

/ / N u m b e r o f e d g e s t o b e t a k e n i s e q u a l t o V - 1

w h i l e ( e < V - 1 & & i < g r a p h - > E )

{

/ / S t e p 2 : P i c k t h e s m a l l e s t e d g e . A n d i n c r e m e n t

/ / t h e i n d e x f o r n e x t i t e r a t i o n

E d g e n e x t _ e d g e = g r a p h - > e d g e [ i + + ] ;

i n t x = f i n d ( s u b s e t s , n e x t _ e d g e . s r c ) ;

i n t y = f i n d ( s u b s e t s , n e x t _ e d g e . d e s t ) ;

/ / I f i n c l u d i n g t h i s e d g e d o e s ' t c a u s e c y c l e ,

/ / i n c l u d e i t i n r e s u l t a n d i n c r e m e n t t h e i n d e x

/ / o f r e s u l t f o r n e x t e d g e

i f ( x ! = y ) {

r e s u l t [ e + + ] = n e x t _ e d g e ;

U n i o n ( s u b s e t s , x , y ) ;

}

/ / E l s e d i s c a r d t h e n e x t _ e d g e

}

/ / p r i n t t h e c o n t e n t s o f r e s u l t [ ] t o d i s p l a y t h e

/ / b u i l t M S T

c o u t < < " F o l l o w i n g a r e t h e e d g e s i n t h e c o n s t r u c t e d "

" M S T \ n " ;

i n t m i n i m u m C o s t = 0 ;

f o r ( i = 0 ; i < e ; + + i )

{

c o u t < < r e s u l t [ i ] . s r c < < " - - " < < r e s u l t [ i ] . d e s t

< < " = = " < < r e s u l t [ i ] . w e i g h t < < e n d l ;

m i n i m u m C o s t = m i n i m u m C o s t + r e s u l t [ i ] . w e i g h t ;

}

c o u t < < " M i n i m u m C o s t S p a n n i n g T r e e : " < < m i n i m u m C o s t munotes.in

## Page 236

236 < < e n d l ;

}

int main()

{

i n t V = 6 ; / / N u m b e r o f v e r t i c e s i n g r a p h

i n t E = 8 ; / / N u m b e r o f e d g e s i n g r a p h

G r a p h * g r a p h = c r e a t e G r a p h ( V , E ) ;

/ / a d d e d g e 0 - 1

g r a p h - > e d g e [ 0 ] . s r c = 0 ;

g r a p h - > e d g e [ 0 ] . d e s t = 1 ;

g r a p h - > e d g e [ 0 ] . w e i g h t = 4 ;

/ / a d d e d g e 0 - 5

g r a p h - > e d g e [ 1 ] . s r c = 0 ;

g r a p h - > e d g e [ 1 ] . d e s t = 5 ;

g r a p h - > e d g e [ 1 ] . w e i g h t = 2 ;

/ / a d d e d g e 1 - 2

g r a p h - > e d g e [ 2 ] . s r c = 1 ;

g r a p h - > e d g e [ 2 ] . d e s t = 2 ;

g r a p h - > e d g e [ 2 ] . w e i g h t = 6 ;

/ / a d d e d g e 2 - 3

g r a p h - > e d g e [ 3 ] . s r c = 2 ;

g r a p h - > e d g e [ 3 ] . d e s t = 3 ;

g r a p h - > e d g e [ 3 ] . w e i g h t = 3 ;

/ / a d d e d g e 3 - 4

g r a p h - > e d g e [ 4 ] . s r c = 3 ;

g r a p h - > e d g e [ 4 ] . d e s t = 4 ;

g r a p h - > e d g e [ 4 ] . w e i g h t = 2 ;

// add edge 4-5

g r a p h - > e d g e [ 5 ] . s r c = 4 ;

g r a p h - > e d g e [ 5 ] . d e s t = 5 ;

g r a p h - > e d g e [ 5 ] . w e i g h t = 4 ;

// add edge 5-1

g r a p h - > e d g e [ 6 ] . s r c = 5 ;

g r a p h - > e d g e [ 6 ] . d e s t = 1 ;

g r a p h - > e d g e [ 6 ] . w e i g h t = 5 ; munotes.in

## Page 237

237

// add edge 5-2

g r a p h - > e d g e [ 7 ] . s r c = 5 ;

g r a p h - > e d g e [ 7 ] . d e s t = 2 ;

g r a p h - > e d g e [ 7 ] . w e i g h t = 1 ;

/ / F u n c t i o n c a l l

K r u s k a l M S T ( g r a p h ) ;

r e t u r n 0 ;

}

Output:

Questions:

1. Every graph has only one minimum spanning tree.

a) True

b) False

2. Which of the following is not the algorithm to find the minimum

spanning tree of the given graph?

a) Boruvka’s algorithm

b) Prim’s algorithm

c) Kruskal’s algorithm

d) Bellman–Ford algorithm

munotes.in

## Page 238

2383. Kruskal’s algorithm is a ______

a) divide and conquer algorithm

b) dynamic programming algorithm

c) greedy algorithm

d) approximation algorithm

4. Consider the given graph.

What is the weight of the minimum spanning tree using the Kruskal’s

algorithm?

a) 24

b) 23

c) 15

d) 19

Self-Learning Topic:

Shortest Path algorithm:

In computer networks, the shortest path algorithms aim to find the optimal

paths between the network nodes so that routing cost is minimized.

Some common shortest path algorithms are −

1. Bellman Ford’s Algorithm

2. Dijkstra’s Algorithm

3. Floyd Warshall’s Algorithm

c d

a

b f e 7

7

1044

2 2

6

munotes.in