Computer Laboratory

Manual

Data Structures
and
Algorithm
s
(CSC-102)

Prepared By:

SYEDA NAZIA ASHRAF

Computer Science Department

Sindh Madressatul Islam University, Aiwan-e-Tijarat Road, Karachi

http://www.smiu.edu.pk
Lab No: Index Page No:

1 To find the largest element in an array. 1

1 Linear and Binary Search of an element in an array 3

2 Inserting and deleting an element into a Linear array 6

3 Sorting an Array by using Selection Sort 8

4 Sorting an Array by using Quick Sort 10

5 Perform Bubble Sort 12

6 Implement Linked List 14

7 Implement Double Linked List 18

8 Implement Stack as Linked List 22

9 Convert Infix to Postfix Expression 24

10 Evaluation of Postfix Expression 27

11 Implement Queue as Linked List 30

12 Perform Matrix Addition, Subtraction, Multiplication and Transpose operations 32

13 Implement Binary Search Tree 35

14 Implement Binary Tree traversal 38

 Data Structures & Algorithm Manual

LAB No: 1

Largest Element in Array

Objective

To find the Largest element in an Array.

Theory:
An Array is collection of cells of the same type. The cells are numbered with consecutive
integers. Array cells are contiguous in computer memory. The memory can be thought of
as an array.

Algorithm
A nonempty array DATA with N numerical values is given. This algorithm finds the
location LOC and value MAX of the largest element of DATA. The variable K is used as a
counter.

Step 1: [Initialize] set K: =1, LOC: =1 and MAX: =DATA[1]

Step 2: [Increment counter] set K: =K+1.
Step 3: [Test counter] if K>N, then
Write LOC, MAX, and Exit.
Step 4: [Compute and update] if MAX<DATA[K], then
Set LOC: =K and MAX: =DATA[K].
Step 5: [Repeat loop] Go to step 2

Algorithm (Rewritten using a repeat-while loop rather than Go to statement)

1.​ [ Initializ e] Set K: = 1 & LOC: = 1 and MAX: =DATA[1]
2.​ Repeat step 3 and 4 while K < = N:
3.​ If MAX<DATA[K], then
Set LOC: = K and MAX: =DATA[K].
[End of If structure]
4.​ SetK:= K + 1
[End of Step 2 loop]
5.​Write: LOC, MAX.
6.​Exit.

Lab Assignment
Find the largest element in array using the above two algorithms.
Data Structures & Algorithm Manual
Data Structures & Algorithm Manual
 Data Structures & Algorithm Manual

LAB No: 2(A)

LINEAR AND BINARY SEARCH OF AN ARRAY
Objective

To find the linear and binary search of an element in an array

Theory:

A linear array DATA with N elements and a specific ITEM of information are given. This
algorithm finds the location LOC of ITEM in the array DATA or sets LOC=0.

Algorithm

1.​ Set k := 1 & loc : = 0

2.​ Repeat step 3 & 4 while loc : = 0 &k < = n
3.​ If (item =
data[k]) loc : =
k
Else
K=k+1
4.​If loc : = 0 ,then
Print “no. not
found” Else
Print “loc is the location of item”
5.​ Exit

Linear search

#include<stdio.h>
#include<conio.h>
void main()
{
int a[100],n,i,item,loc=-1;
clrscr(); printf("\nEnter the number of
element:"); scanf("%d",&n);
printf("Enter the number:\n");
for(i=0;i<=n-1;i++)
{
scanf("%d",&a[i]);
}
printf("Enter the no. to be search\n");
scanf("%d",&item);
 Data Structures & Algorithm Manual

for(i=0;i<=n-1;i++)
{
if(item==a[i])
{
loc=i
break;
}
}
if(loc>=0)

printf("\n%dis found in position%d",item,loc+1);

else
printf("\nItem does not exist");
getch();
}
 Data Structures & Algorithm Manual

​
​
​
 Data Structures & Algorithm Manual

LAB No: 2(B)

Objective

To Find the Binary Search by Using Array

Search a sorted array by repeatedly dividing the search interval in half.

Algorithm:

1.​low = 1,high = n
2.​ Repeat step 3 to 5 while low <= high
3.​ mid = (low + high)
4.​ If a[mid] = x
Print “ found at mid”
Return
5.​ If (a[mid] <
x) low = mid
+1
Else
High = mid – 1
6.​Print “x not found”
7.​ Exit

Program:

#include<stdio.h>
#include<conio.h>
void main()
{
int a[100],i,loc,mid,beg,end,n,flag=0,item;
clrscr();
printf("How many elements");
scanf("%d",&n);
printf("Enter the element of the array\n");
for(i=0;i<=n-1;i++)
{
scanf("%d",&a[i]);
 Data Structures & Algorithm Manual

}
printf("Enter the element to be searching\n");
scanf("%d",&item);
loc=0;
beg=0; end=n-1;
while((beg<=end)&&(item!=a[mid]))
{
mid=((beg+end)/2);
if(item==a[mid])
{
printf("search is successfull\n");
loc=mid;
printf("position of the item%d\n",loc+1);
flag=flag+1;
}

else

if(item<a[mi
d])
end=mid-
1;

beg=mid+1;
if(flag==0)
{

printf("search is not successful\n");

}
getch();
}
Data Structures & Algorithm Manual
 Data Structures & Algorithm Manual

Lab No: 2
Objective: Inserting and deleting an
element into a Linear Array

(A)​ Delete an element into linear array

Theory

Algorithm

Program

void main(void)
{
int a[50],size,i,pos;
clrscr();
printf("Enter size of array: ");
scanf("%d",&size);
printf("Enter elements of array:\n
"); for (i=0;i<size;i++)
scanf("%d",&a[i]);
printf("Enter the position of element you want to delete: ");
scanf("%d",&pos);
if(pos<=0 || pos>size)​ // Boundary
checking printf("Invalid position");
else
for (i= pos-1; i<size-1; i++)
a[i] = a[i+1];

size--;
printf("Array elements after deletion are:\n");
for (i=0; i<=size-1; i++)
printf("%d\n",a[i]);
getch();
}
 Data Structures & Algorithm Manual

(B)​ Insert an element from linear array

Theory
Inserting it into the final data structure in its proper order with respect to items already
inserted
Algorithm
function insert(array A)
for i from 1 to length[A]-1 do
value := A[i]
j := i-1
while j >= 0 and A[j] > value do
A[j+1] := A[j]
j := j-1 done
A[j+1] = value
done

Program:
void main(void)
{
int a[50],size,i,num,pos;
clrscr();
printf("Enter size of array: ");
scanf("%d",&size);
printf("Enter elements of array:\n
"); for (i=0;i<size;i++)
scanf("%d",&a[i]);
printf("Enter data element you want to insert: ");
scanf("%d",&num);
printf("Enter Position: ");
scanf("%d",&pos);
if(pos<=0 || pos>size+1)​ // Boundary
checking printf("Invalid position");
else
for (i= size-1; i>=pos-1; i--)
{
a[i+1] = a[i];
}
a[pos-1] = num;
size++;
printf("Array elements after insertion
are:\n"); for (i=0; i<=size-1; i++)
printf("%d\n",a[i]);
getch();
}
Data Structures & Algorithm Manual
 Data Structures & Algorithm Manual

LAB No: 3
Objective: Algorithm to Sort Array Using Selection Sort
Theory
Selection sort performs sorting by repeatedly putting the largest element in the
unprocessed portion of the array to the end of the unprocessed portion until the whole
array is sorted.

1.​ For (i = 0; i <=n-2 ; i++)

min = a[i]
for (j = i+1 ; j <=n-1 ; j++)
If (min >a[j])
Swap (min,a[j])
2.​Exit

(A)​ Selection Sort

Program:
#include<stdio.h>
#include<conio.h>
void main()
{
int a[100],n,i,j,temp,loc,min;
clrscr();
printf("\How many elements:\n");
scanf("%d",&n);
printf("Enter the element of array\n");
for(i=0;i<=n-1;i++)
{
scanf("%d",&a[i]);
}
min=a[0];
for(i=0;i<=n-1;i++)
{
min=a[i];
loc=i;
for(j=i+1;j<=n-1;j++)
{
if(a[j]<min)
{
 Data Structures & Algorithm Manual

min=a[j];
loc=j;
}
}
if(loc!=1)
{
temp=a[i];
a[i]=a[loc];
a[loc]=temp;
}
}
printf("The number after selection sorting are:\n");
for(i=0;i<=n-1;i++)
{
 Data Structures & Algorithm Manual

(B)​ Insertion sort:

Insertion sort is an elementary sorting algorithm. It has a time complexity of Θ(n2),Insertion
sort is well suited for sorting small data sets or for the insertion of new elements into a
sorted sequence.
PROGRAM:
#include<stdio.h>
void main()
{
int A[20], N, Temp, i, j;
clrscr();
printf("\n\n\t ENTER THE NUMBER OF TERMS...: ");
scanf("%d", &N);
printf("\n\t ENTER THE ELEMENTS OF THE ARRAY...:");
for(i=0; i<N; i++)
{
gotoxy(25,11+i);
scanf("\n\t\t%d", &A[i]);
}
for(i=1; i<N; i++)
{
Temp = A[i];
j = i-1;
while(Temp<A[j] && j>=0)
{
A[j+1] = A[j];
j = j-1;
}
A[j+1] = Temp;
}
printf("\n\tTHE ASCENDING ORDER LIST IS...:\n");
for(i=0; i<N; i++)
printf("\n\t\t\t%d", A[i]);
getch();
}
Data Structures & Algorithm Manual
 Data Structures & Algorithm Manual

LAB No: 4

Objective
Sorting an Array by using Quick Sort

Program

#include <stdio.h>

void swap(int* a, int* b);

// Partition function
int partition(int arr[], int low, int high) {

int j;
// Choose the pivot
int pivot = arr[high];

// Index of smaller element and indicates

// the right position of pivot found so far
int i = low - 1;

// Traverse arr[low..high] and move all smaller

// elements to the left side. Elements from low to
// i are smaller after every iteration
for (j = low; j <= high - 1; j++) {
​ if (arr[j] < pivot) {
​ i++;
​ swap(&arr[i], &arr[j]);
​ }
}

// Move pivot after smaller elements and

// return its position
swap(&arr[i + 1], &arr[high]);
return i + 1;
}

// The QuickSort function implementation

void quickSort(int arr[], int low, int high) {
if (low < high) {

​ // pi is the partition return index of pivot

 Data Structures & Algorithm Manual

​ int pi = partition(arr, low, high);

​ // Recursion calls for smaller elements

​ // and greater or equals elements
​ quickSort(arr, low, pi - 1);
​ quickSort(arr, pi + 1, high);
}
}

void swap(int* a, int* b) {

int temp = *a;
*a = *b;
*b = temp;
}

int main() {

int arr[50], i, n;
clrscr();

printf("Enter number of element: ");

scanf("%d", &n);

printf("Enter %d elements: \n", n);

for(i=0; i<=n-1; i++)
scanf("%d", &arr[i]);

quickSort(arr, 0, n - 1);
for (i = 0; i < n; i++) {
​ printf("%d ", arr[i]);
}
getch();
return 0;
}
 Data Structures & Algorithm Manual

​
 Data Structures & Algorithm Manual

​ ​ ​ ​ ​ ​ ​ LAB No: 5
Objective Theory: Bubble Sort
Sort by comparing each adjacent pair of items in a list in turn, swapping the items if
necessary, and repeating the pass through the list until no swaps are done.

Algorithm

1.​ Repeat steps 2 & 3 for k = 1 to N-1

2.​ Set ptr =1
3.​ Repeat while ptr <= N-k
4.​ (a) If data[ptr] > data[ptr + 1],then
Interchange data[ptr] and data[ptr + 1]
(b) ptr = ptr + 1
5.​ Exit

Bubble sort

#include<stdio.h>
#include<conio.h>
void main()
{
int a[100],n,i,j,temp;
clrscr();
printf("How many elements");
scanf("%d",&n);
printf("Enter the element of array");
for(i=0;i<=n-1;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<=n-1;i++)
{
for(j=0;j<=n-1-i;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
printf("Element of array after the sorting are:\n");
for(i=0;i<=n-1;i++)
{
printf("%d\n",a[i]);
}
getch();
}
​ ​ ​ ​ ​ ​ ​
Data Structures & Algorithm Manual
 Data Structures & Algorithm Manual

LAB No: 5

Objective Theory Implement Linked List

A list implemented by each item having a link to the next item, also known
as singly linked list.

1.​ t = newmode( )
2.​ Enter info to be inserted
3.​ Read n
4.​ t info = n
5.​ t next = start
6.​ Start = t

INSERTION
BEGIN
1.​ t next = start
2.​ start = t
Retur
n
MIDDLE
1.​ Enter info of the node after which new node to be inserted
2.​ Read x
3.​ p = start
4.​ Repeat step 5 until p info < > x
5.​ p = p next
6.​ t next = p next
7.​ p next = t
8.​ Return

LAST
1.​ p = start
2.​ Repeat step 3 until p next NULL
3.​ p = p next
4.​ t next = NULL
5.​ p next = t
6.​ Return

DELETION
BEGIN
1.​ x = start
2.​ start = start next
3.​ delnode(x)

MIDDLE
1.​ Enter the info of node to be deleted
2.​ Read n
3.​ p = start
 Data Structures & Algorithm Manual

4.​ c = start
5.​ while (c info < > NULL)
p=c
c = c next
6.​ p next = c next
7.​delnode ( c )
8.​ Return

LAST
1.​ p=
start c = start
2.​ while (c next < >
NULL) p = c
c = c next
3.​ p next = c next
4.​ delnode ( c)
5.​ Return

TRAVERSAL
1.​ p = start
2.​ while (p < >
NULL) Print p info
P = p next
3.​ Return

Program

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct node
{
int info;
struct node *next;
};
typedef struct node NODE;
NODE *start;
void createmptylist(NODE **start)
{
*start=(NODE *)NULL;
}
void traversinorder(NODE *start)
{
while(start != (NODE *) NULL)
{
printf("%d\n",start->info);
start=start->next;
}
}
void insertatbegin(int item)
{
NODE *ptr;
ptr=(NODE *)malloc(sizeof(NODE));
ptr->info=item;
if(start==(NODE *)NULL)
ptr->next=(NODE *)NULL;
else
 Data Structures & Algorithm Manual

ptr->next=start;
start=ptr;
}
void insert_at_end(int item)
{
NODE *ptr,*loc;
ptr=(NODE *)malloc(sizeof(NODE));
ptr->info=item;
ptr->next=(NODE *)NULL;
if(start==(NODE*)NULL)
start=ptr;
else
{
loc=start;
while(loc->next!=(NODE *)NULL)
loc=loc->next;
loc->next=ptr;
}
}
void insert_spe(NODE *start,int item)
{
NODE *ptr,*loc;
int temp,k;
for(k=0,loc=start;k<temp;k++)
{
loc=loc->next;
if(loc==NULL)
{
printf("node in the list at less than one\n");
return;
}
}
ptr=(NODE *)malloc(sizeof(NODE));
ptr->info=item;
ptr->next=loc->next;;
loc->next=ptr;
}
void main()
{
int choice,item,after;
char ch; clrscr();
createmptylist(start);
do
{
printf("1.Insert element at begin \n");
printf("2. insert element at end positon\n");
printf("3. insert specific the position\n");
printf("4.travers the list in order\n");
printf("5. exit\n");
printf("enter your choice\n");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("Enter the item\n");
scanf("%d",&item);
insertatbegin(item);
break;
case 2: printf("Enter the item\n");
scanf("%d",&item);
 Data Structures & Algorithm Manual

insert_at_end(item
);
break;
case 3: printf("Enter the item\n");
scanf("%d",&item);
insert_spe(start,item);
break;
case 4: printf("\ntravers the list\n");
traversinorder(start);
break;
case 5: return;
}
fflush(stdin);
printf("do your want continous\n");
scanf("%c",&ch);
}while((ch='y')||(ch='y'));
getch();
}
 Data Structures & Algorithm Manual

​​ ​ ​ ​ ​ LAB No: 7
Objective Implement Double Linked List

Theory

A variant of a linked list in which each item has a link to the previous item as well as the
next, this allows easily accessing list items backward as well as forward and deleting any
item in constant time. It only performs O (log n) comparisons. Also known as two-way
linked list, symmetrically linked list.

1.​ t = new node

2.​ Enter “the info to be inserted”
3.​ Read n
4.​ t info = n
5.​ t next = NULL
6.​ t prev NULL

INSERTION
BEGIN
1.​ If start =
NULL start = t
2.​ else
t next = NULL
t next prev = t
start= t
Return

MIDDLE
1.​ Print “ enter info of the node after which you want to insert”
2.​ Read x
3.​ p = start
4.​ Repeat while p< >
NULL If (p info = n)
t next = p next p
next = t
t prev = p
p next prev = t
Return
Else
P = p next
5.​ Print x not found

t next =
NULL p
next = t

DELETION
BEGIN
1.​ p = start
2.​ p next prev = NULL
3.​ start = p next
4.​ start = p next
5.​ delnode(p)
 Data Structures & Algorithm Manual

6.​ Return

MIDDLE
1.​ Enter “info of the node to be deleted”
2.​ Read x
3.​ p = start
4.​ Repeat until p< > NULL

If(pinfo = x) p prev next =

pnext p next prev = p
prev delnode(p)
Retur
n Else
P = p next
5.​ Print “x not found”

LAST
1.​ P = start
2.​ Repeat while p< >
NULL If(p next =
NULL) Delnode(p)
3.​ Return

DISPLAY
1.​ p = start
2.​ Repeat while p < >
NULL Print p info
P = p next

PROGRAM:

#include<stdio.h>
#include<conio.h>
int select();
struct rec
{
char name[80];
struct rec *next;
};
struct rec *rear;
struct rec *create(struct rec *list);
struct rec *insert1(struct rec *node);
struct rec *insert2(struct rec *node);
struct rec *insert3(struct rec *node);
struct rec *insert4(struct rec *node);
struct rec *delete(struct rec *node);
void *display(struct rec *list);
int nodes;
main()
{
struct rec *first=NULL;
int choice;
clrscr();
do
{
choice=select();
 Data Structures & Algorithm Manual

switch(choice)
{
case 1: first=create(first);continue;
case 2: first=insert1(first);continue;
case 3: first=insert2(first);continue;
case 4: first=insert3(first);continue;
case 5: first=insert4(first);continue;
case 6: first=delete(first);continue;
case 7: display(first);continue;
case 8: puts("END");exit(0);
}
}while(choice!=8);
}
int select()
{
int selection;
do
{
puts("Enter 1: create the list");
puts("Enter 2: insert in the beginnig of the list");
puts("Enter 3: insert after a node in the list");
puts("Enter 4: insert before a node in the list");
puts("Enter 5: insert in the end of the list"); puts("Enter
6: delete the list");
puts("Enter 7: display the list");
puts("Enter 8: END");
puts("Enter your choice");
scanf("%d",&selection);
}while(selection<1||selection>8);
return selection;
}
struct rec *create(struct rec *first)
{
struct rec *element;
first=(struct rec*)malloc(sizeof(struct rec));
puts("Enter/name/word/text: To quit enter*");
scanf(" %[^\n]",first->name);
first->next=first;
rear=first;
rear->next=first;for(;;)
{
element=(struct rec*)malloc(sizeof(struct rec));
scanf(" %[^\n]",element->name);
if(strcmp(element->name,"*")==0)break;
element->next=first;
rear->next=element;
rear= element;
}
return(first);
}
struct rec *insert1(struct rec *first)
{
struct rec *node;
node=(struct rec*)malloc(sizeof(struct rec));
puts("Enter node/name to be inserted");
scanf(" %[^\n]",node->name);
if(first==NULL)
 Data Structures & Algorithm Manual

{
node->next=first;
rear=first;
}
else
{
node->next=first;
first=node;
rear->next=first;
}
return(first);
}
struct rec *insert2(struct rec *first)
{
struct rec *current,*prior,*x;
struct rec *node;current=first;
node=(struct rec*)malloc(sizeof(struct rec));
puts("Enter node/name after which new node to be inserted");
scanf(" %[^\n]\n",node->name);
x=(struct rec*)malloc(sizeof(struct rec));
puts("Enter node/name to be inserted");
scanf(" %[^\n]",x->name);
while(current!=rear && current!=NULL)
{
if(strcmp(current->name,node->name)==0)
{
x->next=current->next;
current->next=x;
return(first);
}
else current=current->next;
}
if(strcmp(current->name,node->name)==0)
{
x->next=first;
rear->next=x;
rear=x;
return(first);
}
puts("Node does not exist in the list");
return(first);
}
struct rec *insert3(struct rec *first)
{
struct rec *node,*current,*x,*prior;
current=first;
node=(struct rec*)malloc(sizeof(struct rec));
puts("Enter node/name before which new node to be inserted");
scanf(" %[^\n]",node->name);
x=(struct rec*)malloc(sizeof(struct rec));
puts("Enter node/name to be inserted");
scanf(" %[^\n]",x->name);
if(strcmp(current->name,node->name)==0)
{
x->next=first;
first=x;
return(first);
}
while(current!=NULL)
 Data Structures & Algorithm Manual

{ prior=current;
current=current->next;
if(strcmp(current->name,node->name)==0)
{
x->next=current;
prior->next=x;
return(first);
}
}
puts("Node does not exist in the list");
return(first);
}
struct rec *insert4(struct rec *first)
{
struct rec *element;
element=(struct rec*)malloc(sizeof(struct rec));
puts("Enter node/name to be inserted at the end of list");
scanf(" %[^\n]",element->name);
element->next=first;
rear->next=element;
rear=element;
return(first);
}
struct rec *delete(struct rec *first)
{
struct rec *current,*prior,*node;
current=first;
node=(struct rec*)malloc(sizeof(struct rec));
puts("Enter node/name to be delete"); scanf("
%[^\n]",node->name);
if(strcmp(current->name,node->name)==0)
{
first=current->next;
rear->next=first;
free(current);
return(first);
}
while(current!=rear && current!=NULL)
{ prior=current;
current=current->next;
if(strcmp(current->name,node->name)==0)
{
prior->next=current->next;
free(current);
return(first);
}
}
if(strcmp(current->name,node->name)==0)
{
prior->next=current->next;
prior->next=first;
rear=prior;
free(current);
return(first);
}
puts("Node does not exist in the list"); return(first);
}
void *display(struct rec *first)
{
 Data Structures & Algorithm Manual

int node=0;
do
{
node++;
printf("%s\n",first->name);
first=first->next;
}
while((first!=rear->next)&&(first!=NULL));
printf("Nuber of nodes= %d\n",node);
}
Data Structures & Algorithm Manual
 Data Structures & Algorithm Manual

​ ​ ​ ​ ​ ​ ​ LAB No: 8
Objective Implement Stack as Linked List

Theory

A collection of items in which only the most recently added item may be removed,
the latest added item is at the top, basic operations are push and pop. Often top and
is Empty are available, too. Also known as "last-in, first-out" or LIFO.
Algorithm

PUSH( )
1.​ t = newnode( )
2.​ Enter info to be inserted
3.​ Read n
4.​ t info = n
5.​ t next = top
6.​ top = t
7.​ Return

POP( )
1.​ If (top = NULL)
Print “ underflow”
Return
2.​ x = top
3.​ top = top next
4.​ delnode(x)
5.​ Return

Stack using linked list

Program

#include<stdio.h>
#include<conio.h>
struct stack
{
int no;
struct stack *next;
}
*start=NULL;
typedef struct stack st;
void push();
int pop(); void
display(); void
main()
{
char ch;
int choice,item;
do
{
clrscr();
printf("\n 1: push");
 Data Structures & Algorithm Manual

printf("\n 2: pop");
printf("\n 3: display");
printf("\n Enter your choice");
scanf("%d",&choice);
switch (choice)
{
case 1: push();
break;
case 2: item=pop();
printf("The delete element in %d",item); break;
case 3: display();
break;
default : printf("\n Wrong choice");
};
printf("\n do you want to continue(Y/N)");
fflush(stdin);
scanf("%c",&ch);
}
while (ch=='Y'||ch=='y');
}
void push()
{
st *node;
node=(st *)malloc(sizeof(st));
printf("\n Enter the number to be insert");
scanf("%d",&node->no);
node->next=start;
start=node;
}
int pop()
{
st *temp;
temp=start;
if(start==NULL)
{
printf("stack is already empty");
getch();
exit();
}
else
{
start=start->next; free(temp);
}
return(temp->no);
}
void display()
{
st *temp;
temp=start;
while(temp->next!=NULL)
{
printf("\nno=%d",temp->no);
temp=temp->next;
}printf("\nno=%d",temp->no);
}
Data Structures & Algorithm Manual
 Data Structures & Algorithm Manual

LAB No: 9
Objective: Convert Infix to Postfix Expression

Theory
In Infix Notation, Operators are placed between operands.
In Postfix Notation, Operators are placed after operands.

Algorithm
Q arithmetic expression

P postfix expression
1.​ Push “(“onto Stack, and add “)” to the end of Q.
2.​ Scan Q from left to right and repeat Step 3 to 6 for each element of Q until the stack
is empty:
3.​ If an operand is encountered, add it to P.
4.​ If a left parenthesis is encountered, push it onto stack.
5.​ If an operator is encountered, then:
(a)​ Repeatedly pop from the stack and add to P each operator (on the top
of stack) which has the same precedence as or higher precedence than
[operator].
(b)​ Add [opearator] to
stack. [End of If structure.]
6.​ If a right parenthesis is encountered, then:
(a)​ Repeatedly pop from the stack and add to P each operator (on the top
of stack) until a left parenthesis is encountered.
(b)​ Remove the left parenthesis. [Do not add the left parenthesis to
P.] [End of If structure.]
[End of Step2 loop.]
7.​ Exit.

PROGRAM:-

#include <stdio.h>

#include <conio.h>

#include

<string.h>

#include <ctype.h>

char stack[100];

int top=0;
 Data Structures & Algorithm Manual

char exp[100];

struct table

{
char s[2]; int isp; int icp;
}pr[7];

int isp(char c)

int i;

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

if(pr[i].s[0]==c)

return(pr[i].isp);

return 0;

int icp(char c)

int i;

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

if(pr[i].s[0]==c)

return(pr[i].icp);

return 0;

void main()

int i;

clrscr();

strcpy(pr[0].s,"^");

pr[0].isp=3;

pr[0].icp=4;
strcpy(pr[1].s,"*"); pr[1].isp=2;
pr[1].icp=2;
strcpy(pr[2].s,"/");
 Data Structures & Algorithm Manual

pr[2].isp=2;

pr[2].icp=2;

strcpy(pr[3].s,"+");

pr[3].isp=1;

pr[3].icp=1;
strcpy(pr[4].s,"-");

pr[4].isp=1;

pr[4].icp=1;
strcpy(pr[5].s,"(");

pr[5].isp=0;

pr[5].icp=4;
strcpy(pr[6].s,"=")

; pr[6].isp=-1;

pr[6].icp=0;
clrscr();

stack[top]='=';

printf("enter the infix expression");

gets(exp);

i=0;
printf("the postfix expression is ") while(i<strlen(exp))
{

if(isalpha(exp[i])==0)

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

while(stack[top]!='('){

printf("%c",stack[top])

; top--;

top--;

}
 Data Structures & Algorithm Manual

else{

while(isp(stack[top])>=icp(exp[i]))

printf("%c",stack[top])

; top--;

top++;

stack[top]=exp[i];

else

printf("%c",exp[i]);

i++;

while(top>0)

printf("%c",stack[top])

; top--;

getch();

OUTPUT:-

enter the infix expression a*(s+d/f)+c

the postfix expression is asdf/+*c+

Data Structures & Algorithm Manual
 Data Structures & Algorithm Manual

LAB No: 10
Objective
Evaluate Postfix Expression

Postfix notation is a notation for writing arithmetic expressions in which the

operands appear after their operators. There are no precedence rules to learn, and
parentheses are never needed. Because of this simplicity, some popular hand-held
calculators use postfix notation to avoid the complications of the multiple
parentheses required in non-trivial infix expressions. You are to write a computer
program that simulates how these postfix calculators evaluate expressions.

Algorithm

P postfix expression
1.​ Add a right parenthesis “)” at the end of P. [This act as sentinel.]
2.​Scan P from left to right and repeat steps 3 and 4 for
each element of P until the sentinel “)” is
encountered,
3.​ If an operand is encountered, put it on stack
4.​ If an operator is encountered, then:
(a)​ Remove the top two elements of stack, where A is the
top element and B is the next-to-top element.
(b)​ Evaluate B [operator] A.
(c)​ Place the result of (b) on
stack. [End of If structure]
[End of Step 2 loop.]
5.​ Set value equal to the top element on stack.
6.​ Exit.

Evaluation of postfix expression

Program:
#include<stdio.h>
#include<conio.h> float stack[10]; int top=-1;
void push(char);
float pop();
float eval(char [],float[]);
void main()
{
int i=0;
char suffix[20];
float value[20],result;
clrscr();
printf("Enter a valid postfix expression\t");
gets(suffix);
while (suffix[i]!='\0')
 Data Structures & Algorithm Manual

{
if(isalpha(suffix[i]))
{
fflush(stdin);
printf("\nEnter the value of %c",suffix[i]);
scanf("%f",&value[i]);
}
i++;
}
result=eval(suffix,value);
printf("The result of %s=%f",suffix,result); getch();
}
float eval(char suffix[],float data[])
{
int i=0;
float op1,op2,res; char
ch;
while(suffix[i]!='\0')
{ ch=suffix[i];
if(isalpha(suffix[i]))
{
push(data[i]);
}
else
{
op2=pop();
op1=pop();
switch(ch)
{
case '+' : push(op1+op2);
break;
case '-' : push(op1-op2);
break;
case '*' : push(op1+op2);
break;
case '/' :push(op1/op2);
break;
case '^' : push(pow(op1,op2));
break;
}
}
i++;
} res=pop();
return(res);
}
void push(char num)
{ top=top+1;
stack[top]=num;
}
float pop()
{
float num;
num=stack[top];
top=top-1;
return(num);
}
Data Structures & Algorithm Manual
 Data Structures & Algorithm Manual

LAB No: 11

Objective
Implement Queue as Linked List
Theory
Linked list queue is the same as a queue built using an array. Both store data. Both
place data at the front of the queue and remove data from the front of the queue.
However, in an array queue, data is stored in an array element. In a linked list
queue, data is stored in a node of a linked list. The linked list queue consists of three
major components: the node, the Linked List class definition, and the Queue Linked
List class definition. Collectively, they are assembled to organized data into a
queue.

Algorithm
CREATE
1.​ t = new node
2.​ Enter info to be inserted
3.​ Read n
4.​ t info = n
5.​ t next = front
6.​ front = t

INSERTION
1.​ r next = t
2.​ t next = NULL
3.​ Return

DELETION
1.​ x = front
2.​ front = front next
3.​ delnode(x)
4.​ Return

DISPLAY
1.​ If (front = NULL)
Print “ empty
queue” Return
Else
P = start
Repeat until (p< > NULL)
Print p info
P=p
next
Return

Program

#include<stdio.h>
#include<conio.h>
struct queue
 Data Structures & Algorithm Manual

{
int no;
struct queue *next;
}
*start=NULL;
void add();
int del();
void traverse();
void main()
{
int ch; char
choice; do
{
clrscr();
printf("----1. add\n");
printf("----2. delete\n");
printf("----3. traverse\n");
printf("----4. exit\n");
printf("Enter your choice\n");
scanf("%d",&ch);
switch(ch)
{
case 1: add();
break;
case 2: printf("the delete element is\n%d",del());
break;
case 3: traverse();
break;
case 4: return;
default : printf("wrong choice\n");
};
fflush(stdin);
scanf("%c",&choice);
}
while(choice!=4);
}
void add()
{
struct queue *p,*temp;
temp=start;
p=(struct queue*)malloc(sizeof(struct queue));
printf("Enter the data");
scanf("%d",&p->no);
p->next=NULL;
if(start==NULL)
{
start=p;
}
else
{
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=p;
}
}
int del()
{
 Data Structures & Algorithm Manual

struct queue *temp;

int value;
if(start==NULL)
{
printf("queue is empty");
getch();
return(0);
}
else
{
temp=start;
value=temp->no;
start=start->next;
free(temp);
}
return(value);
}
void traverse()
{
struct queue *temp;
temp=start;
while(temp->next!=NULL)
{
printf("no=%d",temp->no);
temp=temp->next;
}
printf("no=%d",temp->no);
getch();
}
Data Structures & Algorithm Manual
 Data Structures & Algorithm Manual

​​ ​ ​ ​
​​ ​ ​ ​ ​ LAB No: 11
Objective: Perform Matrix Addition, Subtraction, Multiplication and Transpose operations
Theory
Matrices
Vectors and Matrices are mathematical terms, which refer to collections of numbers which
are analogous, respectively, to linear and two-dimensional arrays. That is,
(a)​ An n-element vector is V is list of n numbers usually given in the
form V = (V1,V2,…….,Vn)
(b)​An m x n matrix A is an array of m . n numbers arranged in m rows and n
columns as follows:
A11 A12​ A1n
A21 A22​ A2n
A31 A32​ A3n
A =​ ……………………........
Am1 Am2​ Amn

A matrix is a rectangular array of numbers. For example,

is a 2 3 matrix A = (aij), where for i = 1, 2 and j = 1, 2, 3, the element of the matrix in

row i and column j is aij. We use uppercase letters to denote matrices and corresponding
subscripted lowercase letters to denote their elements. The set of all m n matrices with
real-valued entries is denoted Rm n. In general, the set of m n matrices with entries
drawn from a set S is denoted Sm n.

The transpose of a matrix A is the matrix AT obtained by exchanging the rows and
columns of A. For the matrix A ,
 Data Structures & Algorithm Manual

Algorithm
Matmula (A,B,C,M,P,N)
Let A be an M X P matrix array, and let B be a P X N matrix array. This algorithm stores
the product of A and B in an MXN matrix array C.
1.​ Repeat step 2 to 4 for I=1 to M:
2.​ Repeat step 3 AND 4 for J=1 to N:
3.​ Set C[I,J]:=0.[Initializes C[I,J]. ]
4.​ Repeat for K=1 to P:
C[I,J]:=C[I,J]+A[I,K]*B[K,J
]
[End of inner loop.]
[End of step 2 middle
loop.]
[End of step 1 outer loop.]
5.​ Exit.

Program

Theory
A technique for processing the nodes of a tree in some order

Algorithm

Preorder(root)
If root = null then exit
Process root->info
Preorder root->left;
Preorder root->right
Exit

Inorder(root)
If root = null then exit
Inorder root->left
Process root->info
Inorder root->right Exit

Postorder(root)
If root = null then exit
Postorder root->left
Postorder root->right
Postorder root->info
exit

// traversing a tree
 Data Structures & Algorithm Manual

#include<stdio.h>
struct rec
{
long num;
struct rec *left;
struct rec *right;
};
struct rec *tree=NULL;
struct rec *insert(struct rec *tree,long num);
void preorder(struct rec *tree);
void inorder(struct rec *tree);
void postorder(struct rec *tree);
int count=1;
main()
{
int choice;
long digit;
do
{
choice=select();
switch(choice)
{
case 1: puts("Enter integer: To quit enter 0");
scanf("%ld",&digit);
while(digit!=0)
{
tree=insert(tree,digit);
scanf("%ld",&digit);
}continue;
case 2: puts("\npreorder traversing TREE");
preorder(tree);continue;
case 3: puts("\ninorder traversing TREEE");
inorder(tree);continue;
case 4: puts("\npostorder traversing TREE");
postorder(tree);continue;
case 5: puts("END");exit(0);
}
}while(choice!=5);
}
int select()
{
int selection;
do
{
puts("Enter 1: Insert a node in the BT");
puts("Enter 2: Display(preorder)the BT");
puts("Enter 3: Display(inorder)the BT");
puts("Enter 4: Display(postorder)the BT");
puts("Enter 5: END");
puts("Enter your choice");
scanf("%d",&selection);
if((selection<1)||(selection>5))
{
puts("wrong choice:Try again");
getch(); }
}while((selection<1)||(selection>5));
return (selection);
 Data Structures & Algorithm Manual

}
struct rec *insert(struct rec *tree,long digit)
{
if(tree==NULL)
{
tree=(struct rec *)malloc(sizeof(struct rec));
tree->left=tree->right=NULL;
tree->num=digit;count++;
else
}
if(count%2==0)
tree->left=insert(tree->left,digit);
else
​ tree->right=insert(tree->right,digit);
return(tree);
​ ​ ​ }
void preorder(struct rec *tree)
{
if(tree!=NULL)
{
printf("%12ld\n",tree->num);
preorder(tree->left);
preorder(tree->right);
}
}
void inorder(struct rec *tree)
{
if(tree!=NULL)
{
inorder(tree->left);
printf("%12ld\n",tree->num);
inorder(tree->right);
}
}
void postorder(struct rec *tree)
{
if(tree!=NULL)
{
postorder(tree->left);
postorder(tree->right);
printf("%12ld\n",tree->num);
}

int select()
{
int selection;
do
{
puts("Enter 1: Insert a node in the BT");
puts("Enter 2: Display(preorder)the BT");
puts("Enter 3: Display(inorder)the BT");
puts("Enter 4: Display(postorder)the BT");
puts("Enter 5: END");
puts("Enter your choice");
scanf("%d",&selection);
 Data Structures & Algorithm Manual

if((selection<1)||(selection>5))
{
puts("wrong choice:Try again");
getch(); }
}while((selection<1)||(selection>5));
return (selection);
}
struct rec *insert(struct rec *tree,long digit)
{
if(tree==NULL)
{
tree=(struct rec *)malloc(sizeof(struct
rec)); tree->left=tree->right=NULL;
tree->num=digit;count++;
}
else
if(count%2==0)
tree->left=insert(tree->left,digit);
else tree->right=insert(
tree->right,digit);
return(tree);
}

void preorder(struct rec *tree)

{
if(tree!=NULL)

{
printf("%12ld\n",tree->num);
preorder(tree->left);
preorder(tree->right);
}
}
void inorder(struct rec *tree)
{
if(tree!=NULL)
{
inorder(tree->left);
printf("%12ld\n",tree->num);
inorder(tree->right);
}
}
void postorder(struct rec *tree)
{
if(tree!=NULL)
{
postorder(tree->left);
postorder(tree->right);
printf("%12ld\n",tree->num);
}

}
Data Structures & Algorithm Manual
 Data Structures & Algorithm Manual

LAB No: 12
Objective Theory: Algorithm to
implement Binary Search Tree

A binary search tree is a tree where each node contains a value, and for each
node, the left subtree only contains values less than the value of the node and the right
subtree only contains greater values. This allows us to find the node for any value in
O(logN) average time.

INSERTION

Algorithm

1.​ t = newnode
2.​ t info = n
3.​ t left = t right = NULL
4.​ If (root =
NULL) root = t
return
5.​ ptr = root
6.​ Repeat step 7 until ptr = NULL
7.​ If (ptr info > n)
If (ptr left = NULL)
Ptr left = t
Retur
n Else
Ptr = ptr left
Else
If (ptr right = NULL)
Ptr right = t
Retur
n Else
Ptr = ptr right

DELETION

Algorithm

1.​ If (root = NULL)

Print “Empty tree
“ Return
2.​ ptr = root, par = NULL
3.​ Repeat step 4 & 5 until (ptr info = n or ptr = NULL)
4.​ par = ptr
5.​ If (ptr info > n)
 Data Structures & Algorithm Manual

ptr = ptr left

Else
Ptr = ptr right
6.​ If ptr = NULL
print “ no. not present”

Program

#include<stdio.h>
#include<conio.h>
struct rec
{
long num;
struct rec *left;
struct rec *right;
};
struct rec *tree,*second,*head;
struct rec *insert(struct rec *tree,long num);
struct rec *copy(struct rec *tree);
void inorder(struct rec *tree);
main()
{
int choice;
long digit;
do
{
choice=select();
switch(choice)
{
case 1:puts("Enter integers:To quit enter 0");
scanf("%ld",&digit);
while(digit!=0)
{
tree=insert(tree,digit);
scanf("%ld",&digit);
}continue;
case 2: copy(tree);continue;
case 3: puts("Inorder traversing TREE");
inorder(tree);continue;
case 4: puts("END");exit(0);
}
}while(choice!=4);
}
int select()
{
int selection;
do
{
puts("Enter 1: Insert a node in the BST");
puts("Enter 2: Copy a tree to another BST");
puts("Enter 3: Display(inorder)the BST");
puts("Enter 4: END");
puts("Enter your choice");
scanf("%d",&selection);
if((selection<1)||(selection>4))
 Data Structures & Algorithm Manual

{puts("Wrong choice: Try again");

getchar();
}
}while((selection<1)||(selection>4));
return selection;
}
struct rec *insert(struct rec *tree,long digit)
{
if(tree==NULL)
{
tree=(struct rec *)malloc(sizeof(struct rec));
tree->left=tree->right=NULL;
tree->num=digit;
}
else
if(digit<tree->num)
tree->left=insert(tree->left,digit);
else if(digit>tree->num)
tree->right=insert(tree->right,digit);
else if(digit==tree->num)
{puts("Duplicate nodes: program exited");exit(0);
}
return(tree);
}
struct rec *copy(struct rec *tree)
{
second=(struct rec *)malloc(sizeof(struct rec));
head=second;
if(tree!=NULL)
{
second->num=tree->num;
if(tree->left!=NULL)
{
second->left->num=tree->left->num;
copy(tree->right);
}
if(tree->right!=NULL)
{
second->right->num=tree->num;
copy(tree->left);
}
}
return(head);
}
void inorder(struct rec *tree)
{
if(tree!=NULL)
{
inorder(tree->left);
printf("%12ld\n",tree->num);
inorder(tree->right);
}
}
 LAB No: 13
Implement Binary Tree traversal

Theory

A tree means visiting all the nodes of a tree in order. There are three different methods of traversing a
binary tree: there are three types of the tree traversal

●​ Preorder: Displays the nodes visited using a preorder traversal algorithm, and displays
the resulting expression.
●​ Inorder: Displays the nodes visited using a inorder traversal algorithm, and displays
the resulting expression.
●​ Postorder: Displays the nodes visited using a postorder traversal algorithm, and
displays the resulting expression.

Algorithm

Preorder(root)
If root = null then exit
Process root->info
Preorder root->left;
Preorder root->right
Exit

Inorder(root)
If root = null then exit
Inorder root->left
Process root->info
Inorder root->right
Exit

Postorder(root)
If root = null then exit
Postorder root->left
Postorder root->right
Postorder root->info
exit

traversing a tree program

#include<stdio.h>
struct rec
{
long num;
struct rec
*left;
 struct rec *right;
};
struct rec *tree=NULL;
struct rec *insert(struct rec *tree,long num);
void preorder(struct rec *tree);
void inorder(struct rec *tree);
void postorder(struct rec *tree);
int count=1;
main()
{
int choice;
long digit;
do
{
choice=select();
switch(choice)
{
case 1: puts("Enter integer: To quit enter 0");
scanf("%ld",&digit);
while(digit!=0)
{
tree=insert(tree,digit);
scanf("%ld",&digit);

}continue;
case 2: puts("\npreorder traversing
TREE"); preorder(tree);continue;
case 3: puts("\ninorder traversing
TREEE"); inorder(tree);continue;
case 4: puts("\npostorder traversing
TREE"); postorder(tree);continue;
case 5: puts("END");exit(0);
}
}while(choice!=5);
}
int select()
{
int selection;
do
{
puts("Enter 1: Insert a node in the BT");
puts("Enter 2: Display(preorder)the BT");
puts("Enter 3: Display(inorder)the BT");
puts("Enter 4: Display(postorder)the BT");
puts("Enter 5: END");
puts("Enter your choice");
 scanf("%d",&selection);
if((selection<1)||(selection>5))
{
puts("wrong choice:Try again");
getch(); }
}while((selection<1)||(selection>5))
; return (selection);
}
struct rec *insert(struct rec *tree,long digit)
{
if(tree==NULL)
{
tree=(struct rec *)malloc(sizeof(struct
rec)); tree->left=tree->right=NULL;
tree->num=digit;count++;
}
else
if(count%2==0)
tree->left=insert(tree->left,digit);
else
tree->right=insert(tree->right,digit);
return(tree);
}
void preorder(struct rec *tree)
{
if(tree!=NULL)
{
printf("%12ld\n",tree->num)
; preorder(tree->left);
preorder(tree->right);
}
}
void inorder(struct rec *tree)
{
if(tree!=NULL)

{
inorder(tree->left);
printf("%12ld\n",tree->num)
; inorder(tree->right);
}
}
void postorder(struct rec *tree)
{
if(tree!=NULL)
{
postorder(tree->left);
postorder(tree->right);
printf("%12ld\n",tree->num)
;
}

int select()
{
int selection;
do
{
puts("Enter 1: Insert a node in the BT");
puts("Enter 2: Display(preorder)the BT");
puts("Enter 3: Display(inorder)the BT");
puts("Enter 4: Display(postorder)the BT");
puts("Enter 5: END");
puts("Enter your choice");
scanf("%d",&selection);
if((selection<1)||(selection>5))
{
puts("wrong choice:Try again");
getch(); }
}while((selection<1)||(selection>5))
; return (selection);
}
struct rec *insert(struct rec *tree,long digit)
{
if(tree==NULL)
{
tree=(struct rec *)malloc(sizeof(struct
rec)); tree->left=tree->right=NULL;
tree->num=digit;count++;
}
else
if(count%2==0)
tree->left=insert(tree->left,digit);
else
tree->right=insert(tree->right,digit);
return(tree);
}
void preorder(struct rec *tree)
{
if(tree!=NULL)

{
 printf("%12ld\n",tree->num)
; preorder(tree->left);
preorder(tree->right);
}
}
void inorder(struct rec *tree)
{
if(tree!=NULL)
{
inorder(tree->left);
printf("%12ld\n",tree->num)
; inorder(tree->right);
}
}
void postorder(struct rec *tree)
{
if(tree!=NULL)
{
postorder(tree->left);
postorder(tree->right);
printf("%12ld\n",tree->num)
;
}

}
 LAB No: 14
Implementation of Priority Queue Using Heaps

Theory
▪​ A heap is a complete binary tree that conforms to the heap order.

▪​ The heap order property: in a (min) heap, for every node X, the key in the parent is smaller than
(or equal to) the key in X.

▪​ Or, the parent node has key smaller than or equal to both of its children nodes.

ALGORITHM:-

Step 1: Start the Program

Step 2: heap is a binary tree with two important properties:

•​For any node n other than the root, n.key >= n.parent.key. In other words, the

parent always has more priority than its children.

•​If the heap has height h, the first h−1 levels are full, and on the last

level the nodes are all packed to the left.

Step 4: implement the queue as a linked list, the element with most priority will be the

first element of the list, so retrieving the content as well as removing this element are both O(1)
operations. However, inserting a new object in its right position requires traversing the list element
by element, which is an O(n) operation.

Step 3: Insert Element in Queue

void insert (Object o, int priority) - inserts in the queue the specified object with

the specified priority

Algorithm insert (Object o, int priority)

Input: An object and the corresponding priority

Output: The object is inserted in the heap with the corresponding

priority lastNode 🡨 getLast()​//get the position at which to insert

lastNode.setKey(priority)
 lastnode.setContent(o

) n lastNode

while n.getParent()! =

null and

n.getParent().getKey()

> priority

swap(n,n.getParent())

Step 4: Object DeleteMin() - removes from the queue the object with most priority

Algorithm removeMin()

lastNode <- getLast()

value lastNode.getContent()

swap(lastNode, root)

update lastNode

return value

PROGRAM:-

#include<iostream.h>

#include<conio.h>

#include<stdio.h>

#include<stdlib.h>

#include<process.h>

struct heapnode

int capacity;

int size;

int *elements;

};
int isFull(struct heapnode *h)

if(h->capacity==h->size)

return 1;

else

return 0;

int isEmpty(struct heapnode *h)

if(h->size==0)

return 1;

else

return 0;

void display(struct heapnode *h)

printf("\nPriority Queue Display :");

if(isEmpty(h))

printf("\nPriority queue is

empty"); return;

else

for(int i=1;i<=h->size;i++)

printf("%d\t",h->elements[i]);

struct heapnode * initialize()

{
struct heapnode *t; int maxelements;
printf("\nEnter the Size of the Priority queue :");

scanf("%d",&maxelements);

if(maxelements<5)

printf("Priority queue size is to small");

getch();

exit(0);

t=(struct heapnode *)malloc(sizeof(struct heapnode *));

if(t==NULL)

printf("out of space!");

getch();

exit(0);

t->elements=(int *)malloc((maxelements+1)*sizeof(int));
if(t->elements==NULL)
{

printf("Out of space");

getch();

exit(0);

t->capacity=maxelements

; t->size=0;

t->elements=0;

return t;

void insert(int x,struct heapnode *h)

{

int i;

if(isFull(h))

printf("Priority queue is

full"); return;

for(i=++h->size;h->elements[i/2]>x;i/=2)

h->elements[i]=h->elements[i/2}

h->elements[i]=x;

int deleteMin(struct heapnode *h)

int i,child;

int MinElement,LastElement;
if(isEmpty(h))

printf("Priority queue is empty");

return 0;

}
MinElement=h->elements[1];

LastElement=h->elements[h->size--]

for(i=1;i*2<=h->size;i=child)

child=i*2;

if(child!=h->size&&h->elements[child+1]<h->elements[child])

child++;
 if(LastElement>h->elements[child])

h->elements[i]=h->elements[child];

else

break;

h->elements[i]=LastElement;

return MinElement;

}
void main()

int ch,ins,del;

struct heapnode *h;

clrscr();

printf("\nPriority Queue using Heap");

h=initialize();

while(1)

printf("\n1. Insert\n2. DeleteMin\n3. Display\n4.

Exit"); printf("\nEnter u r choice :");

scanf("%d",&ch);

switch(ch)

case 1:

printf("\nEnter the element:");

scanf("%d",&ins);

insert(ins,h);

break;

case 2:

del=deleteMin(h);
 printf("\nDeleted element is %d",del);

getch();

break;

case 3:

display(h);

getch();

break;

case 4:

exit(0);

OUTPUT:

Priority Queue using Heap

Enter the Size of the Priority queue :14

1.​Insert

2.​DeleteMin

3.​Display

4.​Exit

Enter u r choice :1

Enter the element:10

1.​Insert

2.​DeleteMin

3.​Display
4.​Exit

Enter u r choice :1

Enter the element:34

1.​Insert

2.​DeleteMin

3.​Display

4.​Exit

Enter u r choice :1

Enter the element:24

1.​Insert

2.​DeleteMin

3.​Display

4.​Exit

Enter u r choice :1

Enter the element:67

1.​Insert

2.​DeleteMin

3.​Display

4.​Exit

Enter u r choice :3

Priority Queue Display :10​ 34​ 24​ 67

1.​Insert

2.​DeleteMin

3.​Display

4.​Exit

Enter u r choice :2

Deleted element is 10
1.​Insert

2.​DeleteMin

3.​Display

4.​Exit

Enter u r choice :2

Deleted element is 24

1.​Insert

2.​DeleteMin

3.​Display

4.​Exit

Enter u r choice :3

Priority Queue Display :34​ 67

1.​Insert

2.​DeleteMin

3.​Display

4.​Exit

Enter u r choice :4
 LAB No: 14
Implement Hashing Techniques

Theory
▪​ An array in which TableNodes are not stored consecutively

▪​ Their place of storage is calculated using the key and a hash function

▪​ Keys and entries are scattered throughout the array.

ALGORITHM:-

1.​ Start the program

2.​ Get the array size.
3.​ Get the elements of the array.
4.​ Get the key value of the element to be searched.
5.​ Find the position of the element by taking the remainder of the division of the array size
by the key.
6.​ Print the element in that position.
7.​ Terminate the program.

PROGRAM:-

#include<stdio.h>

#include<conio.h

>

#include<math.h

> void main()

int a[125],key,size,i,h;

clrscr();

printf("\n Enter the array

size:"); scanf("%d",&size);

printf("\n Enter the array

element:"); for(i=0;i<size;i++)
{

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

printf("Enter the key value");

scanf("%d",&key);

h=key%size;

while(h!=i)

i++;

printf("The

element is

%d",a[i]);

getch();

OUTPUT:

Enter the array size:4

Enter the array element:23

90

24

12

Enter the key

value0 The element

is 23