Kathmandu College of Technology

Lokanthali, 16 Bhaktapur

Lab Reports On
DATA STRUCTURE AND ALGORITHMS
(CAAC-152)
Faculty of Humanities and Social Sciences
Tribhuvan University
Kirtipur, Nepal

Date: 2079/09/08

Submitted By: Submitted To:

Name: Sakar Prasad Mainali Department of BCA

Roll No: 15 (Fifteen) -
Faculty: Bachelor in Computer Application - Prashant Gautam
Year//Part: 2nd Year, 2077 // 3rd Semester (Lecturer/Supervisor)
 TABLE OF CONTENTS

Lab No. TOPIC

Lab 1 Lab Exercise of Stack Operations

Lab 2 Lab Exercise of Stack Implementation

Lab 3 Lab Exercise of Queue Operations

Lab 4 Lab Exercise of Recursion

Lab 5 Lab Exercise of Sorting
Lab 6 Lab Exercise of Searching & Probing
Lab 7 Lab Exercise of List Operation
Lab 8 Lab Exercise of Linked Lists
Lab 9 Lab Exercise of Trees
Lab 10 Lab Exercise of Graphs

(Notice: Print out the cover page and table of content

whereas all the programs must be in A4 Size paper
with handwritten and make your necessary adjustment
yourself to the provided contents.)
Lab1: Lab Exercise of Stack Operations
#include<stdio.h>
int stack[100],choice,n,top,x,i;
void push(void);
void pop(void);
void display(void);
int main()
{
//clrscr();
top=-1;
printf("\n Enter the size of STACK[MAX=100]:");
scanf("%d",&n);
printf("\n\t STACK OPERATIONS USING ARRAY");
printf("\n\t--------------------------------");
printf("\n\t [Link]\n\t [Link]\n\t [Link]\n\t [Link]");
do
{
printf("\n Enter the Choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("\n\t EXIT POINT ");
break;
 }
default:
{
printf ("\n\t Please Enter a Valid
Choice(1/2/3/4)");
}

}
}
while(choice!=4);
return 0;
}
void push()
{
if(top>=n-1)
{
printf("\n\tSTACK is over flow");

}
else
{
printf(" Enter a value to be pushed:");
scanf("%d",&x);
top++;
stack[top]=x;
}
}
void pop()
{
if(top<=-1)
{
printf("\n\t Stack is under flow");
}
else
{
printf("\n\t The popped elements is %d",stack[top]);
top--;
}
}
void display()
{
if(top>=0)
{
printf("\n The elements in STACK \n");
for(i=top; i>=0; i--)
printf("\n%d",stack[i]);
printf("\n Press Next Choice");
}
 else
{
printf("\n The STACK is empty");
}

Lab2: Lab Exercise of Stack Implementation

a. Infix to postfix
#include<stdio.h>
#include<stdlib.h> /* for exit() */
#include<ctype.h> /* for isdigit(char ) */
#include<string.h>

#define SIZE 100

/* declared here as global variable because stack[]

* is used by more than one fucntions */
char stack[SIZE];
int top = -1;

/* define push operation */

void push(char item)

{
if(top >= SIZE-1)
{
printf("\nStack Overflow.");
}
else
{
top = top+1;
stack[top] = item;
}
}

/* define pop operation */

char pop()
{
char item ;

if(top <0)
{
printf("stack under flow: invalid infix expression");
getchar();
 /* underflow may occur for invalid expression */
/* where ( and ) are not matched */
exit(1);
}
else
{
item = stack[top];
top = top-1;
return(item);
}
}

/* define function that is used to determine whether any symbol is

operator or not
(that is symbol is operand)
* this fucntion returns 1 if symbol is opreator else return 0 */

int is_operator(char symbol)

{
if(symbol == '^' || symbol == '*' || symbol == '/' || symbol == '+'
|| symbol =='-')
{
return 1;
}
else
{
return 0;
}
}

/* define fucntion that is used to assign precendence to operator.

* Here ^ denotes exponent operator.
* In this fucntion we assume that higher integer value
* means higher precendence */

int precedence(char symbol)

{
if(symbol == '^')/* exponent operator, highest precedence*/
{
return(3);
}
else if(symbol == '*' || symbol == '/')
{
return(2);
}
else if(symbol == '+' || symbol == '-') /* lowest
precedence */
{
 return(1);
}
else
{
return(0);
}
}

void InfixToPostfix(char infix_exp[], char postfix_exp[])

{
int i, j;
char item;
char x;

push('('); /* push '(' onto stack */

strcat(infix_exp,")"); /* add ')' to infix
expression */

i=0;
j=0;
item=infix_exp[i]; /* initialize before loop*/

while(item != '\0') /* run loop till end of infix expression

*/
{
if(item == '(')
{
push(item);
}
else if( isdigit(item) || isalpha(item))
{
postfix_exp[j] = item; /* add operand symbol
to postfix expr */
j++;
}
else if(is_operator(item) == 1) /* means symbol is
operator */
{
x=pop();
while(is_operator(x) == 1 && precedence(x)>=
precedence(item))
{
postfix_exp[j] = x; /* so pop all
higher precendence operator and */
j++;
x = pop(); /* add them to postfix
expresion */
}
 push(x);
/* because just above while loop will terminate we have
Poppeed one extra item
for which condition fails and loop terminates, so that
one*/

push(item); /* push current oprerator

symbol onto stack */
}
else if(item == ')') /* if current symbol is ')' then
*/
{
x = pop(); /* pop and keep popping until
*/
while(x != '(') /* '(' encounterd */
{
postfix_exp[j] = x;
j++;
x = pop();
}
}
else
{ /* if current symbol is neither operand not '(' nor ')' and
nor
operator */
printf("\nInvalid infix Expression.\n"); /* the it
is illegeal symbol */
getchar();
exit(1);
}
i++;

item = infix_exp[i]; /* go to next symbol of infix expression

*/
} /* while loop ends here */
if(top>0)
{
printf("\nInvalid infix Expression.\n"); /* the it is
illegeal symbol */
getchar();
exit(1);
}

postfix_exp[j] = '\0'; /* add sentinel else puts() fucntion */

/* will print entire postfix[] array upto SIZE */

}
/* main function begins */
int main()
{
char infix[SIZE], postfix[SIZE]; /* declare infix string
and postfix string */

/* why we asked the user to enter infix expression

* in parentheses ( )
* What changes are required in porgram to
* get rid of this restriction since it is not
* in algorithm
* */
printf("ASSUMPTION: The infix expression contains single letter
variables and single digit constants only.\n");
printf("\nEnter Infix expression : ");
gets(infix);

InfixToPostfix(infix,postfix); /* call to convert

*/
printf("Postfix Expression: ");
puts(postfix); /* print postfix expression */

return 0;
}

b. Postfix evaluation
#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>

int stack[20];
int top = -1;

void push(int x)
{
stack[++top] = x;
}

int pop()
{
return stack[top--];
}

int main()
{
char exp[20];
char *e;
int n1,n2,n3,num;
printf("Enter the expression :: ");
scanf("%s",exp);
e = exp;
while(*e != '\0')
{
if(isdigit(*e))
{
num = *e - 48; // originally ASCII Value
push(num);
}
else
{
n1 = pop();
n2 = pop();
switch(*e)
{
case '^':
{
n3 = n1 ^ n2;
break;
}
case '+':
{
n3 = n1 + n2;
break;
}
case '-':
{
n3 = n2 - n1;
break;
}
case '*':
{
n3 = n1 * n2;
break;
}
case '/':
{
n3 = n2 / n1;
break;
}
}
push(n3);
}
 e++;
}
printf("\nThe result of expression %s = %d\n\n",exp,pop());
return 0;
}
Lab3: Lab Exercise of Queue Operations

a. linear queue

#include <stdio.h>
#include <stdlib.h>
struct Queue
{
int size;
int front;
int rear;
int *Q;
};

void create(struct Queue *q,int size) ;

void enqueue(struct Queue *q,int x);
int dequeue(struct Queue *q);
void Display(struct Queue q) ;

int main()
{
int maxsize;
struct Queue q;
printf("Enter the size of queue:");
scanf("%d",&maxsize);
create(&q,maxsize);
int choice;
int item;
do
{
printf("[Link] element to queue \n");
printf("[Link] element from queue \n");
printf("[Link] all elements of queue \n");
printf("[Link] \n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter item to insert:");
scanf("%d",&item);
enqueue(&q,item);
break;
case 2:
printf("The Dequeued item is %d ",dequeue(&q));
 break;
case 3:
printf("Items in the queue are:\n");
Display(q);
break;
case 4:
exit(1);
default:
printf("Wrong choice \n");
}
}while(choice<5);

return 0;
}

void create(struct Queue *q,int size)

{
q->size=size;
q->front=q->rear=-1;
q->Q=(int *)malloc(q->size*sizeof(int));
}

void enqueue(struct Queue *q,int x)

{
if(q->rear==q->size-1)
printf("Queue is Full");
else
{
q->rear++;
q->Q[q->rear]=x;
}
}

int dequeue(struct Queue *q)

{
int x=-1;
if(q->front==q->rear)
printf("Queue is Empty\n");
else
{
q->front++;
x=q->Q[q->front];
}
return x;

void Display(struct Queue q)

 {
int i;
for(i=[Link]+1;i<=[Link];i++)
printf("%d ",q.Q[i]);
printf("\n");
}

b. circular queue
#include <stdio.h>
#include <stdlib.h>
struct Queue
{
int size;
int front;
int rear;
int *Q;
};
void create(struct Queue *q,int size) ;
void enqueue(struct Queue *q,int x);
int dequeue(struct Queue *q) ;
void Display(struct Queue q);

int main()
{
int maxsize;
struct Queue q;
printf("Enter the size of queue:");
scanf("%d",&maxsize);
create(&q,maxsize);
int choice;
int item;
do
{
printf("\[Link] element to queue \n");
printf("\[Link] element from queue \n");
printf("\[Link] all elements of queue \n");
printf("\[Link] \n");
printf("\tEnter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter item to insert:");
scanf("%d",&item);
 enqueue(&q,item);
break;
case 2:
printf("The Dequeued item is %d\n ",dequeue(&q));
break;
case 3:
printf("Items in the queue are:\n");
Display(q);
break;
case 4:
exit(1);
default:
printf("Wrong choice \n\n");
}
}while(choice<5);

return 0;
}
void create(struct Queue *q,int size)
{
q->size=size;
q->front=q->rear=0;
q->Q=(int *)malloc(q->size*sizeof(int));
}

void enqueue(struct Queue *q,int x)

{
if((q->rear+1)%q->size==q->front)
printf("Queue is Full\n");

else
{
q->rear=(q->rear+1)%q->size;
q->Q[q->rear]=x;
}
}

int dequeue(struct Queue *q)

{
int x=-1;
if(q->front==q->rear)
printf("Queue is Empty\n");

else
{
q->front=(q->front+1)%q->size;
x=q->Q[q->front];
}
 return x;
}

void Display(struct Queue q)

{
int i=[Link]+1;
do
{
printf("%d ",q.Q[i]);
i=(i+1)%[Link];
}while(i!=([Link]+1)%[Link]);

printf("\n");
}
 Lab4: Lab Exercise of Recursion

a. factorial
#include <stdio.h>
int main() {
int n, i;
unsigned long long fact = 1;
printf("Enter an integer: ");
scanf("%d", &n);

// shows error if the user enters a negative integer

if (n < 0)
printf("Error! Factorial of a negative number doesn't exist.");
else {
for (i = 1; i <= n; ++i) {
fact *= i;
}
printf("Factorial of %d = %llu", n, fact);
}

return 0;
}

b. Fibonacci
#include<stdio.h>
int main()
{
int n1=0,n2=1,n3,i,number;
printf("Enter the number of elements:");
scanf("%d",&number);
printf("\n%d %d",n1,n2);//printing 0 and 1
for(i=2;i<number;++i)//loop starts from 2 because 0 and 1 are already
printed
{
n3=n1+n2;
printf(" %d",n3);
n1=n2;
n2=n3;
}
return 0;
}

c. Tower of Hanoi
//1. Implement TOH problem using Recursion.//

#include<stdio.h>
void TOH(int n,char x,char y,char z) {
if(n>0) {
TOH(n-1,x,z,y);
printf("\n%c to %c",x,y);
TOH(n-1,z,y,x);
}
}
int main() {
int n=5;
TOH(n,'A','B','C');
}

d. Greatest Common Divisor(GDC)

#include <stdio.h>
long gcd(int x, int y);
int main()
{
int Num1, Num2;

printf("Please Enter two integer Values \n");

scanf("%d %d", &Num1, &Num2);

printf("GCD of %d and %d is %d.", Num1, Num2, gcd(Num1, Num2));

return 0;
}
long gcd(int x, int y)
{
if (y == 0) {
return x;
}
else {
return gcd(y, x % y);
}
}
 Lab5: Lab Exercise of Sorting

a. Bubble Sort
#include <stdio.h>
#include<stdlib.h>
void swap(int *x,int *y)
{
int temp=*x;
*x=*y;
*y=temp;
}
void Bubble(int A[], int n)
{
int i,j,flag=0;
for(i=0;i<n-1;i++) //passes//
{
flag=0;
for(j=0;j<n-i-1;j++) //comparision//
{
if(A[j]>A[j+1]) //adjacent//
{
swap(&A[j],&A[j+1]);
flag=1;
}
}
if(flag==0)
break;
}
}

int main()
{
int A[100],n, i;
printf("How may elements: ");
scanf("%d", &n);
printf("Enter %d elements: ",n);
for(i=0;i<n;i++)
{
scanf("%d", &A[i]);
}
Bubble(A,n);

for(i=0;i<n;i++)
printf("%d\t", A[i]);
printf("\n");
return 0;
}
 b. Insertion Sort
#include <stdio.h>
#include<stdlib.h>

void Insertion(int A[],int n)

{
int i,j,x;
for(i=1;i<n;i++)
{
j=i-1;
x=A[i];
while(j> -1 && A[j]>x)
{
A[j+1]=A[j];
j--;
}
A[j+1]=x;
}
}

int main()
{
int A[100],n, i;
printf("How many elements: ");
scanf("%d", &n);
printf("Enter %d elements: ",n);
for(i=0;i<n;i++)
{
scanf("%d", &A[i]);
}
Insertion(A,n);

for(i=0;i<n;i++)
printf("%d\t",A[i]);
printf("\n");
return 0;
}

c. Selection Sort
#include <stdio.h>
#include<stdlib.h>

void swap(int *x,int *y)

{
int temp=*x;
 *x=*y;
*y=temp;
}
void SelectionSort(int A[],int n)
{
int i,j,min;
for(i=0;i<n-1;i++)
{
min=i;
for(j=i+1;j<n;j++)
{
if(A[j]<A[min])
min=j;
}

if(min!=i)
{
swap(&A[i],&A[min]);
}

}
}
int main()
{
int A[100],n,i;
printf("How many elements: ");
scanf("%d", &n);
printf("Enter %d elements: ",n);
for(i=0;i<n;i++)
{
scanf("%d", &A[i]);
}

SelectionSort(A,n);
for(i=0;i<n;i++)
printf("%d\t",A[i]);
printf("\n");
return 0;
}

d. quick Sort
#include <stdio.h>
#include<stdlib.h>

void swap(int *x,int *y)

{
int temp=*x;
 *x=*y;
*y=temp;
}

int partition(int A[],int l,int h)

{
int pivot=A[l];
int i=l,j=h;
do
{
do{
i++; // i search for element greater than pivot
}while(A[i]<=pivot); //increment i until you found element
greater than pivot

do
{
j--; // j search for element smaller than pivot
}while(A[j]>pivot); //Decrement j until you found element
less than or equal to pivot

if(i<j)
swap(&A[i],&A[j]);
}while(i<j);

swap(&A[l],&A[j]);
return j;
}

void QuickSort(int A[],int l,int h)

{
int j;
if(l<h)
{
j=partition(A,l,h);
QuickSort(A,l,j);
QuickSort(A,j+1,h);
}
}

int main()
{
int i,n, A[100];
printf("Enter how many numbers :");
scanf("%d", &n);
printf("Enter %d elements: ",n);
for(i=0;i<n;i++)
 {
scanf("%d",&A[i]);
}

QuickSort(A,0,n);
for(i=0;i<n;i++)
printf("%d\t",A[i]);
printf("\n");
return 0;
}

e. Merge sort
#include <stdio.h>
#include<stdlib.h>

void Merge(int A[],int l,int mid,int h)

{
int i=l,j=mid+1,k=l;
int B[100];
while(i<=mid && j<=h)
{
if(A[i]<A[j])
B[k++]=A[i++];
else
B[k++]=A[j++];
}
for(;i<=mid;i++)
B[k++]=A[i];
for(;j<=h;j++)
B[k++]=A[j];

for(i=l;i<=h;i++)
A[i]=B[i];
}

void MergeSort(int A[],int l,int h)

{
int mid;
if(l<h) //if there is more than one items in the array
{
mid=(l+h)/2;
MergeSort(A,l,mid);
MergeSort(A,mid+1,h);
Merge(A,l,mid,h);
}
}
int main()
{

int A[100], i,n;

printf("Enter how many numbers: ");
scanf("%d",&n);
printf("Enter %d elements: ",n);
for(i=0;i<n;i++)
scanf("%d",&A[i]);

MergeSort(A,0,9);
for(i=0;i<n;i++)
printf("%d\t",A[i]);
printf("\n");
return 0;
}

f. Radix sort
#include<stdio.h>

// Function to find largest element

int largest(int a[], int n)
{
int large = a[0], i;
for(i = 1; i < n; i++)
{
if(large < a[i])
large = a[i];
}
return large;
}

// Function to perform sorting

void RadixSort(int a[], int n)
{
int bucket[10][10], bucket_count[10];
int i, j, k, remainder, NOP=0, divisor=1, large, pass;

large = largest(a, n);

printf("The large element %d\n",large);
while(large > 0)
{
NOP++;
large/=10;
}
 for(pass = 0; pass < NOP; pass++)
{
for(i = 0; i < 10; i++)
{
bucket_count[i] = 0;
}
for(i = 0; i < n; i++)
{
remainder = (a[i] / divisor) % 10;
bucket[remainder][bucket_count[remainder]] = a[i];
bucket_count[remainder] += 1;
}

i = 0;
for(k = 0; k < 10; k++)
{
for(j = 0; j < bucket_count[k]; j++)
{
a[i] = bucket[k][j];
i++;
}
}
divisor *= 10;

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

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

//program starts here

int main()
{
int i, n, a[10];
printf("Enter the number of elements :: ");
scanf("%d",&n);
printf("Enter the elements :: ");
for(i = 0; i < n; i++)
{
scanf("%d",&a[i]);
}
RadixSort(a,n);
printf("The sorted elements are :: ");
for(i = 0; i < n; i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}
 g. shell Sort
/*
* C Program to sort an array in ascending order using Shell Sort
*/

#include <stdio.h>
void swap(int *a, int *b)
{
*a=*a + *b;
*b=*a - *b;
*a=*a - *b;
return ;
}

// Function definition of sort array using shell sort

void shellsort(int arr[], int nums)
{
// i -> gap/interval
for (int i = nums / 2; i > 0; i = i / 2)
{
// Traverse j till we reach the end of the sublist.
for (int j = i; j < nums; j++)
{
for(int k = j - i; k >= 0; k = k - i)
{
if (arr[k+i] >= arr[k])
{
break;
}
else
{
swap(&arr[k], &arr[k+i]);
}
}
}
}
return ;
}

int main()
{
int nums;
printf("Enter total no. of elements :: ");
scanf("%d", &nums);
int arr[nums];
printf("Enter the array:: \n");
//scan the array elements.
 for (int k = 0 ; k < nums; k++)
{
scanf("%d", &arr[k]);
}

//Call the function of shell sort, bypassing the array base pointer
to the first element.
shellsort(arr, nums);

// After the sorting the array is

printf("Sorted array is: \n");
for (int k = 0; k < nums; k++)
{
printf("%d ", arr[k]);
}
return 0;
}

h. Heap Sort
#include <stdio.h>
/* function to heapify a subtree. Here 'i' is the
index of root node in array a[], and 'n' is the size of heap. */
void heapify(int a[], int n, int i)
{
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // left child
int right = 2 * i + 2; // right child
// If left child is larger than root
if (left < n && a[left] > a[largest])
largest = left;
// If right child is larger than root
if (right < n && a[right] > a[largest])
largest = right;
// If root is not largest
if (largest != i) {
// swap a[i] with a[largest]
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;

heapify(a, n, largest);
}
}
/*Function to implement the heap sort*/
void heapSort(int a[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
 heapify(a, n, i);
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
/* Move current root element to end*/
// swap a[0] with a[i]
int temp = a[0];
a[0] = a[i];
a[i] = temp;

heapify(a, i, 0);
}
}
/* function to print the array elements */
void printArr(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
printf("%d", arr[i]);
printf(" ");
}

}
int main()
{
int a[] = {48, 10, 23, 43, 28, 26, 1};
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
heapSort(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}
 Lab6: Lab Exercise of Searching & Probing
a. binary search
#include<stdio.h>
int main()
{
int c, first, last, middle, n, search, array[100];
printf("Enter number of elements: ");
scanf("%d",&n);
printf("Enter %d integers:\n", n);
for (c = 0; c < n; c++)
scanf("%d",&array[c]);
printf("Enter the value to find: ");
scanf("%d", &search);
first = 0;
last = n - 1;
middle = (first+last)/2;
while (first <= last) {
if (array[middle] < search)
first = middle + 1;
else if (array[middle] == search) {
printf("%d is present at index %d.\n", search, middle+1);
break;
}
else
last = middle - 1;
middle = (first + last)/2;
}
if (first > last)
printf("Not found! %d is not present in the list.\n", search);
return 0;
}

b. linear search
#include<stdio.h>

int main()
{
int a[20],i,x,n;
printf("How many elements?");
scanf("%d",&n);

printf("Enter array elements: ");

for(i=0;i<n;++i)
scanf("%d",&a[i]);
 printf("\nEnter element to search: ");
scanf("%d",&x);

for(i=0;i<n;++i)
if(a[i]==x)
break;

if(i<n)
printf("Element found at index %d.",i);
else
printf("Element not found.");

return 0;
}

c. Linear Probing
#include<stdio.h>
#include<stdlib.h>
#define TABLE_SIZE 10

int h[TABLE_SIZE]={NULL};

void insert()
{

int key,index,i,flag=0,hkey;
printf("\nenter a value to insert into hash table\n");
scanf("%d",&key);
hkey=key%TABLE_SIZE;
for(i=0;i<TABLE_SIZE;i++)
{

index=(hkey+i)%TABLE_SIZE;

if(h[index] == NULL)
{
h[index]=key;
break;
}

if(i == TABLE_SIZE)

printf("\nElement cannot be inserted...\n");

}
void search()
{

int key,index,i,flag=0,hkey;
printf("\nEnter search element:\n");
scanf("%d",&key);
hkey=key%TABLE_SIZE;
for(i=0;i<TABLE_SIZE; i++)
{
index=(hkey+i)%TABLE_SIZE;
if(h[index]==key)
{
printf("Value is found at index %d.\n",index);
break;
}
}
if(i == TABLE_SIZE)
printf("\n Value is not found.\n");
}
void display()
{
int i;
printf("\nElements in the hash table are \n");
for(i=0;i< TABLE_SIZE; i++)
printf("\nat index %d \t value = %d",i,h[i]);
}
main()
{
int opt,i;
while(1)
{
printf("\nPress 1. Insert\t 2. Display \t3. Search \[Link] \
n");
scanf("%d",&opt);
switch(opt)
{
case 1:
insert();
break;
case 2:
display();
break;
case 3:
search();
break;
case 4:exit(0);
}
}
}
 d. quadratic Probing
#include<stdio.h>
#include<stdlib.h>
#define TABLE_SIZE 10

int h[TABLE_SIZE]={NULL};

void insert()
{

int key,index,i,flag=0,hkey;
printf("\nEnter a value to insert into hash table.\n");
scanf("%d",&key);
hkey=key%TABLE_SIZE;
for(i=0;i<TABLE_SIZE;i++)
{

index=(hkey+i*i)%TABLE_SIZE;

if(h[index] == NULL)
{
h[index]=key;
break;
}
}
if(i == TABLE_SIZE)
printf("\nElement cannot be inserted.\n");
}
void search()
{

int key,index,i,flag=0,hkey;
printf("\nEnter search element.\n");
scanf("%d",&key);
hkey=key%TABLE_SIZE;
for(i=0;i<TABLE_SIZE; i++)
{
index=(hkey+i*i)%TABLE_SIZE;
if(h[index]==key)
{
printf("Value is found at index %d",index);
break;
}
}
if(i == TABLE_SIZE)
printf("\n Value is not found\n");
}
void display()
{
int i;

printf("\nElements in the hash table are \n");

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

printf("\nat index %d \t value = %d",i,h[i]);

}
main()
{
int opt,i;
while(1)
{
printf("\nPress 1. Insert\t 2. Display \t3. Search \[Link] \
n");
scanf("%d",&opt);
switch(opt)
{
case 1:
insert();
break;
case 2:
display();
break;
case 3:
search();
break;
case 4:exit(0);
}
}
}

e. Double Hashing
#include<stdio.h>
#include<stdlib.h>
#define TABLE_SIZE 10

int h[TABLE_SIZE]={NULL};

void insert()
{

int key,index,i,flag=0,hkey,hash2;
 printf("\nEnter a value to insert into hash table.\n");
scanf("%d",&key);
hkey=key%TABLE_SIZE;
hash2 = 7-(key %7);
for(i=0;i<TABLE_SIZE;i++)
{
index=(hkey+i*hash2)%TABLE_SIZE;
if(h[index] == NULL)
{
h[index]=key;
break;
}
}
if(i == TABLE_SIZE)
printf("\nElement cannot be inserted.\n");
}
void search()
{

int key,index,i,flag=0,hash2,hkey;
printf("\nEnter search element.\n");
scanf("%d",&key);
hkey=key%TABLE_SIZE;
hash2 = 7-(key %7);
for(i=0;i<TABLE_SIZE; i++)
{
index=(hkey+i*hash2)%TABLE_SIZE;
if(h[index]==key)
{
printf("Value is found at index %d.",index);
break;
}
}
if(i == TABLE_SIZE)
printf("\n Value is not found.\n");
}
void display()
{

int i;
printf("\nElements in the hash table are \n");
for(i=0;i< TABLE_SIZE; i++)
printf("\nat index %d \t value = %d",i,h[i]);

}
main()
{
int opt,i;
 while(1)
{
printf("\nPress 1. Insert\t 2. Display \t3. Search \[Link] \
n");
scanf("%d",&opt);
switch(opt)
{
case 1:
insert();
break;
case 2:
display();
break;
case 3:
search();
break;
case 4:exit(0);
}
}
}
 Lab7: Lab Exercise of List Operation
a. List as an ADT
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 10

void create();
void insert();
void deletion();
void search();
void display();
int a,b[20], n, p, e, f, i, pos;

main()
{
int ch;
char g='y';
do
{
printf("\n Main Menu");
printf("\n [Link] \n [Link] \n [Link] \n [Link] \n
[Link]\n [Link] \n");
printf("\n Enter your Choice:");
scanf("%d", &ch);
switch(ch)
{
case 1:
create();
break;

case 2:
deletion();
break;

case 3:
search();
break;

case 4:
insert();
break;

case 5:
display();
break;
 case 6:
exit(1);
break;

default:
printf("\n Enter the correct choice:");
}
printf("\n Do u want to continu[Link] ");
scanf("\n%c", &g);
}
while(g=='y'||g=='Y');
getch();
}
void create()
{
printf("\n Enter the number of elements: ");
scanf("%d", &n);
for(i=0;i<n;i++)
{
printf("\n Enter the %d Element: ",i+1);
scanf("%d", &b[i]);
}

}
void deletion()
{
printf("\n Enter the position you want to delete:: ");
scanf("%d", &pos);
if(pos>=n)
{
printf("\n Invalid Location:: ");
}
else
{
for(i=pos+1;i<n;i++)
{
b[i-1]=b[i];
}
n--;
}
printf("\n The Elements after deletion: ");
for(i=0;i<n;i++)
{
printf("\t%d", b[i]);
}
}
void search()
{
 printf("\n Enter the Element to be searched: ");
scanf("%d", &e);

for(i=0;i<n;i++)
{
if(b[i]==e)
{
printf("Value is in the %d Position.", i);
}
else
{
printf("Value %d is not in the list:: ", e);
continue;
}
}
}
void insert()
{
printf("\n Enter the position u need to insert:: ");
scanf("%d", &pos);

if(pos>=n)
{
printf("\n Invalid Location:: ");
}
else
{
for(i=MAX-1;i>=pos-1;i--)
{
b[i+1]=b[i];
}
printf("\n Enter the element to insert::\n");
scanf("%d",&p);
b[pos]=p;
n++;
}
printf("\n The list after insertion::\n");
display();
}
void display()
{
printf("\n The Elements of The list ADT are: ");
for(i=0;i<n;i++)
{
printf("\n\n%d", b[i]);
}
}
 Lab8: Lab Exercise of Linked Lists
a. Singly LL
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<malloc.h> //for malloc function
#include<process.h> //for exit function

struct node
{
int info;
struct node *next;
};

typedef struct node NodeType;

NodeType *head=NULL;
//head=NULL;
void insert_atfirst(int);
void insert_givenposition(int);
void insert_atend(int);
void delet_first();
void delet_last();
void delet_nthnode();
void display();
void count_nodes();

int main()
{
int choice;
int item;

do
{
printf("\nSingly Linked List Implementation\
n=================================\n");
printf("[Link] first\[Link] at given position\
[Link] at last \[Link] firstnode\[Link] last node\[Link]
nth node\[Link] nodes\[Link] items\[Link]\
n=================================\n");
printf("\n\nEnter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter item to be inserted: ");
scanf("%d", &item);
 insert_atfirst(item);
break;
case 2:
printf("Enter item to be inserted: ");
scanf("%d", &item);
insert_givenposition(item);
break;
case 3:
printf("Enter item to be inserted: 1");
scanf("%d", &item);
insert_atend(item);
break;
case 4:
delet_first();
break;
case 5:
delet_last();
break;
case 6:
delet_nthnode();
break;
case 7:
count_nodes();
break;
case 8:
display();
break;
case 9:
exit(1);
break;
default:
printf("invalid choice\n");
break;
}
}while(choice<10);
getch();
}

/************function definitions**************/
void insert_atfirst(int item)
{
NodeType *nnode;
nnode=(NodeType*)malloc(sizeof(NodeType));
nnode->info=item;
nnode->next=head;
head=nnode;
}
void insert_givenposition(int item)
{
NodeType *nnode;
NodeType *temp;
temp=head;
int p,i;
nnode=( NodeType *)malloc(sizeof(NodeType));
nnode->info=item;
if (head==NULL)
{
nnode->next=NULL;
head=nnode;
}
else
{
printf("Enter Position of a node at which you want to insert an
new node\n");
scanf("%d",&p);
for(i=1;i<p-1;i++)
{
temp=temp->next;
}
nnode->next=temp->next;
temp->next=nnode;
}
}

void insert_atend(int item)

{
NodeType *nnode;
NodeType *temp;
temp=head;
nnode=( NodeType *)malloc(sizeof(NodeType));
nnode->info=item;
if(head==NULL)
{
nnode->next=NULL;
head=nnode;
}
else
{
while(temp->next!=NULL)
{
temp=temp->next;
}
nnode->next=NULL;
temp->next=nnode;
}
}

void delet_first()
{
NodeType *temp;
if(head==NULL)
{
printf("Void deletion\n");
return;
}
else
{
temp=head;
head=head->next;
free(temp);
}
}

void delet_last()
{
NodeType *hold,*temp;
if(head==NULL)
{
printf("Void deletion\n");
return;
}
else if(head->next==NULL)
{
hold=head;
head=NULL;
free(hold);
}
else
{
temp=head;
while(temp->next->next!=NULL)
{
temp=temp->next;
}
hold=temp->next;
temp->next=NULL;
free(hold);
}
}

void delet_nthnode()
{
NodeType *hold,*temp;
 int pos, i;
if(head==NULL)
{
printf("Void deletion\n");
return;
}
else
{
temp=head;
printf("Enter position of node which node is to be deleted\n");
scanf("%d",&pos);
for(i=1;i<pos-1;i++)
{
temp=temp->next;
}
hold=temp->next;
temp->next=hold->next;
free(hold);
}
}

void display()
{
NodeType *temp;
temp=head;
while(temp!=NULL)
{
printf("%d\t",temp->info);
temp=temp->next;
}
}
void count_nodes()
{
int cnt=0;
NodeType *temp;
temp=head;
while(temp!=NULL)
{
cnt++;
temp=temp->next;
}
printf("total nodes=%d",cnt);
}
 b. Doubly LL
#include<stdio.h>
#include<stdlib.h>
struct node
{
struct node *prev;
struct node *next;
int data;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void insertion_specified();
void deletion_beginning();
void deletion_last();
void deletion_specified();
void display();
void search();
void main ()
{
int choice = 0;
while(choice != 9)
{
printf("\nDoubly Linked List Implementation\
n=================================\n");
printf("\[Link] first\[Link] at last\[Link] node after
given position\[Link] firstnode\[Link] lastnode\[Link] node
after the given data\[Link] node\[Link] items\[Link]\
n=================================\n");

printf("\nEnter your choice: ");

scanf("\n%d",&choice);
switch(choice)
{
case 1:
insertion_beginning();
break;
case 2:
insertion_last();
break;
case 3:
insertion_specified();
break;
case 4:
deletion_beginning();
break;
case 5:
 deletion_last();
break;
case 6:
deletion_specified();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void insertion_beginning()
{
struct node *ptr;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter Item value: ");
scanf("%d",&item);

if(head==NULL)
{
ptr->next = NULL;
ptr->prev=NULL;
ptr->data=item;
head=ptr;
}
else
{
ptr->data=item;
ptr->prev=NULL;
ptr->next = head;
head->prev=ptr;
head=ptr;
}
 printf("\nNode inserted.\n");
}

}
void insertion_last()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *) malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value: ");
scanf("%d",&item);
ptr->data=item;
if(head == NULL)
{
ptr->next = NULL;
ptr->prev = NULL;
head = ptr;
}
else
{
temp = head;
while(temp->next!=NULL)
{
temp = temp->next;
}
temp->next = ptr;
ptr ->prev=temp;
ptr->next = NULL;
}

}
printf("\nNode inserted.\n");
}
void insertion_specified()
{
struct node *ptr,*temp;
int item,loc,i;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\n OVERFLOW");
}
 else
{
temp=head;
printf("Enter the location: ");
scanf("%d",&loc);
for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\n There are less than %d elements.", loc);
return;
}
}
printf("Enter value: ");
scanf("%d",&item);
ptr->data = item;
ptr->next = temp->next;
ptr -> prev = temp;
temp->next = ptr;
temp->next->prev=ptr;
printf("\nNode inserted.\n");
}
}
void deletion_beginning()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nNode deleted.\n");
}
else
{
ptr = head;
head = head -> next;
head -> prev = NULL;
free(ptr);
printf("\nNode deleted.\n");
}

}
void deletion_last()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nNode deleted.\n");
}
else
{
ptr = head;
if(ptr->next != NULL)
{
ptr = ptr -> next;
}
ptr -> prev -> next = NULL;
free(ptr);
printf("\nNode deleted.\n");
}
}
void deletion_specified()
{
struct node *ptr, *temp;
int val;
printf("\n Enter the data after which the node is to be deleted:
");
scanf("%d", &val);
ptr = head;
while(ptr -> data != val)
ptr = ptr -> next;
if(ptr -> next == NULL)
{
printf("\nCan't delete.\n");
}
else if(ptr -> next -> next == NULL)
{
ptr ->next = NULL;
}
else
{
temp = ptr -> next;
ptr -> next = temp -> next;
temp -> next -> prev = ptr;
free(temp);
 printf("\nNode deleted.\n");
}
}
void display()
{
struct node *ptr;
printf("\n Printing Values...\n");
ptr = head;
while(ptr != NULL)
{
printf("%d\n",ptr->data);
ptr=ptr->next;
}
}
void search()
{
struct node *ptr;
int item,i=0,flag;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List.\n");
}
else
{
printf("\nEnter item which you want to search: ");
scanf("%d",&item);
while (ptr!=NULL)
{
if(ptr->data == item)
{
printf("\nItem found at location %d.",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("\nItem not found.\n");
}
}
}
c. circular-singly LL
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;

void beginsert ();

void lastinsert ();
void begin_delete();
void last_delete();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 7)
{
printf("\nCircular-Singly Linked List Implementation\
n=================================\n");
printf("\[Link] in begining\[Link] at last\[Link] from
Beginning\[Link] from last\[Link] for an element\[Link]\[Link]\
n=================================\n");
printf("\nEnter your choice: ");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
beginsert();
break;
case 2:
lastinsert();
break;
case 3:
begin_delete();
break;
case 4:
last_delete();
break;
case 5:
search();
break;
case 6:
 display();
break;
case 7:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void beginsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter the node data: ");
scanf("%d",&item);
ptr -> data = item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
}
else
{
temp = head;
while(temp->next != head)
temp = temp->next;
ptr->next = head;
temp -> next = ptr;
head = ptr;
}
printf("\nNode inserted.\n");
}
}
void lastinsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
 printf("\nOVERFLOW\n");
}
else
{
printf("\nEnter Data: ");
scanf("%d",&item);
ptr->data = item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
}
else
{
temp = head;
while(temp -> next != head)
{
temp = temp -> next;
}
temp -> next = ptr;
ptr -> next = head;
}

printf("\nNode inserted.\n");
}
}
void begin_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nUNDERFLOW");
}
else if(head->next == head)
{
head = NULL;
free(head);
printf("\nNode deleted.\n");
}
else
{ ptr = head;
while(ptr -> next != head)
ptr = ptr -> next;
ptr->next = head->next;
free(head);
head = ptr->next;
printf("\nNode deleted.\n");
 }
}
void last_delete()
{
struct node *ptr, *preptr;
if(head==NULL)
{
printf("\nUNDERFLOW");
}
else if (head ->next == head)
{
head = NULL;
free(head);
printf("\nNode deleted.\n");
}
else
{
ptr = head;
while(ptr ->next != head)
{
preptr=ptr;
ptr = ptr->next;
}
preptr->next = ptr -> next;
free(ptr);
printf("\nNode deleted.\n");
}
}

void search()
{
struct node *ptr;
int item,i=0,flag=1;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List...\n");
}
else
{
printf("\nEnter item which you want to search: ");
scanf("%d",&item);
if(head ->data == item)
{
printf("Item found at location %d.",i+1);
flag=0;
}
else
 {
while (ptr->next != head)
{
if(ptr->data == item)
{
printf("Item found at location %d.",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
}
if(flag != 0)
{
printf("Item not found.\n");
}
}
}
void display()
{
struct node *ptr;
ptr=head;
if(head == NULL)
{
printf("\nNothing to print.");
}
else
{
printf("\n Printing values... \n");

while(ptr -> next != head)

{

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

ptr = ptr -> next;
}
printf("%d\n", ptr -> data);
}
}
 d. circular-doubly LL
#include<stdio.h>
#include<stdlib.h>
struct node
{
struct node *prev;
struct node *next;
int data;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void deletion_beginning();
void deletion_last();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\nCircular-Doubly Linked List Implementation\
n=================================\n");
printf("\[Link] in Beginning\[Link] at last\[Link]
from Beginning\[Link] from last\[Link]\[Link]\[Link]\
n=================================\n");
printf("\nEnter your choice: ");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
insertion_beginning();
break;
case 2:
insertion_last();
break;
case 3:
deletion_beginning();
break;
case 4:
deletion_last();
break;
case 5:
search();
break;
case 6:
display();
 break;
case 7:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void insertion_beginning() {
struct node *ptr,*temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else {
printf("\nEnter Item value: ");
scanf("%d",&item);
ptr->data=item;
if(head==NULL)
{
head = ptr;
ptr -> next = head;
ptr -> prev = head;
}
else {
temp = head;
while(temp -> next != head)
{
temp = temp -> next;
}
temp -> next = ptr;
ptr -> prev = temp;
head -> prev = ptr;
ptr -> next = head;
head = ptr;
}
printf("\nNode inserted.\n");
}
}
void insertion_last()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *) malloc(sizeof(struct node));
if(ptr == NULL)
 {
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value: ");
scanf("%d",&item);
ptr->data=item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
ptr -> prev = head;
}
else
{
temp = head;
while(temp->next !=head)
{
temp = temp->next;
}
temp->next = ptr;
ptr ->prev=temp;
head -> prev = ptr;
ptr -> next = head;
}
}
printf("\nNode inserted.\n");
}
void deletion_beginning()
{
struct node *temp;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == head)
{
head = NULL;
free(head);
printf("\nNode deleted.\n");
}
else
{
temp = head;
while(temp -> next != head)
{
temp = temp -> next;
 }
temp -> next = head -> next;
head -> next -> prev = temp;
free(head);
head = temp -> next;
}
}
void deletion_last()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == head)
{
head = NULL;
free(head);
printf("\nNode deleted.\n");
}
else
{
ptr = head;
if(ptr->next != head)
{
ptr = ptr -> next;
}
ptr -> prev -> next = head;
head -> prev = ptr -> prev;
free(ptr);
printf("\nNode deleted.\n");
}
}
void display()
{
struct node *ptr;
ptr=head;
if(head == NULL)
{
printf("\nNothing to print.");
}
else
{
printf("\n Printing values ... \n");

while(ptr -> next != head)

{
printf("%d\n", ptr -> data);
 ptr = ptr -> next;
}
printf("%d\n", ptr -> data);
}
}
void search()
{
struct node *ptr;
int item,i=0,flag=1;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List.\n");
}
else
{
printf("\nEnter item which you want to search: \n");
scanf("%d",&item);
if(head ->data == item)
{
printf("Item found at location %d.",i+1);
flag=0;
}
else
{
while (ptr->next != head)
{
if(ptr->data == item)
{
printf("Item found at location %d.",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
}
if(flag != 0)
{
printf("Item not found.\n");
}
}
}
 e. Stack as LL
// Stack as a Linked List Implementation
#include <stdio.h>
#include <stdlib.h>

struct Node {
int info;
struct Node *next;
}*top=NULL;

void push(int x);

int pop();
void Display();

int main()
{
int choice;
int item;
while(1)
{
printf("\[Link] item to stack Linked List \n");
printf("[Link] item from stack Linked List \n");
printf("[Link] all elements of Stack \n");
printf("[Link] \n");
printf("\nEnter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter item to push:");
scanf("%d",&item);
push(item);
break;
case 2:
printf("The popped item is %d\n",pop());
Display();
break;
case 3:
printf("Items in the stacks are:\n");
Display();
break;
case 4:
exit(1);
default:
printf("Wrong choice \n");
}
 }
return 0;
}

void push(int x)
{
struct Node *newnode;
newnode=(struct Node*)malloc(sizeof(struct Node));
if(newnode==NULL)
printf("stack is full\n");
else
{
newnode->info=x;
newnode->next=top;
top=newnode;
}
}

int pop()
{
struct Node *t;
int x=-1;
if(top==NULL)
printf("Stack is Empty\n");
else
{
t=top;
top=top->next;
x=t->info;
free(t);
}
return x;
}

void Display()
{
struct Node *p;
p=top;
while(p!=NULL)
{
printf("%d ",p->info);
p=p->next;
}
printf("\n");
}
 f. Queue as LL
// Queue Linked List Implementation
#include <stdio.h>
#include <stdlib.h>

struct Node {
int info;
struct Node *next;
}*front=NULL,*rear=NULL;

void enqueue(int x);

int dequeue();
void Display();

int main()
{
int choice;
int item;
while(1)
{
printf("\[Link] element to queue linked list \n");
printf("[Link] element from queue linked list \n");
printf("[Link] all elements of queue linked list \n");
printf("[Link] \n");
printf("\nEnter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter item to insert:");
scanf("%d",&item);
enqueue(item);
break;
case 2:
printf("The Dequeued item is %d\n ",dequeue());
break;
case 3:
printf("Items in the queue are:\n");
Display();
break;
case 4:
exit(1);
default:
printf("Wrong choice \n");
}
}
 return 0;
}
void enqueue(int item)
{
struct Node *newnode;
newnode=(struct Node*)malloc(sizeof(struct Node));
if(newnode==NULL)
printf("Queue is FUll.\n");
else
{
newnode->info=item;
newnode->next=NULL;
if(front==NULL) //if empty
front=rear=newnode;
else
{
rear->next=newnode;
rear=newnode;
}
}
}
int dequeue()
{
int x=-1;
struct Node* temp;
if(front==NULL)
printf("Queue is Empty.\n");
else
{
x=front->info;
temp=front;
front=front->next;
free(temp);
}
return x;
}

void Display()
{
struct Node *p=front;
while(p)
{
printf("%d ",p->info);
p=p->next;
}
printf("\n");
}
Lab9: Lab Exercise of Trees

a. AVL tree
/*
* AVL Tree Program in C
*/

#include<stdio.h>
#include<stdlib.h>

// structure of the tree node

struct node
{
int data;
struct node* left;
struct node* right;
int ht;
};

// global initialization of root node

struct node* root = NULL;

// function prototyping
struct node* create(int);
struct node* insert(struct node*, int);
struct node* delete(struct node*, int);
struct node* search(struct node*, int);
struct node* rotate_left(struct node*);
struct node* rotate_right(struct node*);
int balance_factor(struct node*);
int height(struct node*);
void inorder(struct node*);
void preorder(struct node*);
void postorder(struct node*);

int main()
{
int user_choice, data;
char user_continue = 'y';
struct node* result = NULL;

while (user_continue == 'y' || user_continue == 'Y')

{
printf("\n\n------- AVL TREE --------\n");
printf("\n1. Insert");
printf("\n2. Delete");
printf("\n3. Search");
printf("\n4. Inorder");
printf("\n5. Preorder");
printf("\n6. Postorder");
printf("\n7. EXIT");

printf("\n\nEnter Your Choice: ");

scanf("%d", &user_choice);

switch(user_choice)
{
case 1:
printf("\nEnter data: ");
scanf("%d", &data);
root = insert(root, data);
break;

case 2:
printf("\nEnter data: ");
scanf("%d", &data);
root = delete(root, data);
break;

case 3:
printf("\nEnter data: ");
scanf("%d", &data);
result = search(root, data);
if (result == NULL)
{
printf("\nNode not found!");
}
else
{
printf("\n Node found");
}
break;
case 4:
inorder(root);
break;

case 5:
preorder(root);
break;

case 6:
postorder(root);
break;

case 7:
 printf("\n\tProgram Terminated\n");
return 1;

default:
printf("\n\tInvalid Choice\n");
}

printf("\n\nDo you want to continue? ");

scanf(" %c", &user_continue);
}

return 0;
}

// creates a new tree node

struct node* create(int data)
{
struct node* new_node = (struct node*) malloc (sizeof(struct
node));

// if a memory error has occurred

if (new_node == NULL)
{
printf("\nMemory can't be allocated\n");
return NULL;
}
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}

// rotates to the left

struct node* rotate_left(struct node* root)
{
struct node* right_child = root->right;
root->right = right_child->left;
right_child->left = root;

// update the heights of the nodes

root->ht = height(root);
right_child->ht = height(right_child);

// return the new node after rotation

return right_child;
}

// rotates to the right

struct node* rotate_right(struct node* root)
{
struct node* left_child = root->left;
root->left = left_child->right;
left_child->right = root;

// update the heights of the nodes

root->ht = height(root);
left_child->ht = height(left_child);

// return the new node after rotation

return left_child;
}

// calculates the balance factor of a node

int balance_factor(struct node* root)
{
int lh, rh;
if (root == NULL)
return 0;
if (root->left == NULL)
lh = 0;
else
lh = 1 + root->left->ht;
if (root->right == NULL)
rh = 0;
else
rh = 1 + root->right->ht;
return lh - rh;
}

// calculate the height of the node

int height(struct node* root)
{
int lh, rh;
if (root == NULL)
{
return 0;
}
if (root->left == NULL)
lh = 0;
else
lh = 1 + root->left->ht;
if (root->right == NULL)
rh = 0;
else
rh = 1 + root->right->ht;
 if (lh > rh)
return (lh);
return (rh);
}

// inserts a new node in the AVL tree

struct node* insert(struct node* root, int data)
{
if (root == NULL)
{
struct node* new_node = create(data);
if (new_node == NULL)
{
return NULL;
}
root = new_node;
}
else if (data > root->data)
{
// insert the new node to the right
root->right = insert(root->right, data);

// tree is unbalanced, then rotate it

if (balance_factor(root) == -2)
{
if (data > root->right->data)
{
root = rotate_left(root);
}
else
{
root->right = rotate_right(root->right);
root = rotate_left(root);
}
}
}
else
{
// insert the new node to the left
root->left = insert(root->left, data);

// tree is unbalanced, then rotate it

if (balance_factor(root) == 2)
{
if (data < root->left->data)
{
root = rotate_right(root);
}
 else
{
root->left = rotate_left(root->left);
root = rotate_right(root);
}
}
}
// update the heights of the nodes
root->ht = height(root);
return root;
}

// deletes a node from the AVL tree

struct node * delete(struct node *root, int x)
{
struct node * temp = NULL;

if (root == NULL)
{
return NULL;
}

if (x > root->data)
{
root->right = delete(root->right, x);
if (balance_factor(root) == 2)
{
if (balance_factor(root->left) >= 0)
{
root = rotate_right(root);
}
else
{
root->left = rotate_left(root->left);
root = rotate_right(root);
}
}
}
else if (x < root->data)
{
root->left = delete(root->left, x);
if (balance_factor(root) == -2)
{
if (balance_factor(root->right) <= 0)
{
root = rotate_left(root);
}
else
 {
root->right = rotate_right(root->right);
root = rotate_left(root);
}
}
}
else
{
if (root->right != NULL)
{
temp = root->right;
while (temp->left != NULL)
temp = temp->left;

root->data = temp->data;
root->right = delete(root->right, temp->data);
if (balance_factor(root) == 2)
{
if (balance_factor(root->left) >= 0)
{
root = rotate_right(root);
}
else
{
root->left = rotate_left(root->left);
root = rotate_right(root);
}
}
}
else
{
return (root->left);
}
}
root->ht = height(root);
return (root);
}

// search a node in the AVL tree

struct node* search(struct node* root, int key)
{
if (root == NULL)
{
return NULL;
}

if(root->data == key)
{
 return root;
}

if(key > root->data)

{
search(root->right, key);
}
else
{
search(root->left, key);
}
}

// inorder traversal of the tree

void inorder(struct node* root)
{
if (root == NULL)
{
return;
}

inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
// preorder traversal of the tree
void preorder(struct node* root)
{
if (root == NULL)
{
return;
}
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
// postorder traversal of the tree
void postorder(struct node* root)
{
if (root == NULL)
{
return;
}
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
 b. BST
/*
* C Program to Construct a Binary Search Tree and perform deletion,
inorder traversal on it
*/
#include <stdio.h>
#include <stdlib.h>
struct btnode
{
int value;
struct btnode *l;
struct btnode *r;
}*root = NULL, *temp = NULL, *t2, *t1;

void delete1();
void insert();
void delete();
void inorder(struct btnode *t);
void create();
void search(struct btnode *t);
void preorder(struct btnode *t);
void postorder(struct btnode *t);
void search1(struct btnode *t,int data);
int smallest(struct btnode *t);
int largest(struct btnode *t);

int flag = 1;
void main()
{
int ch;

printf("\nOPERATIONS ---");
printf("\n1 - Insert an element into tree\n");
printf("2 - Delete an element from the tree\n");
printf("3 - Inorder Traversal\n");
printf("4 - Preorder Traversal\n");
printf("5 - Postorder Traversal\n");
printf("6 - Exit\n");
while(1)
{
printf("\nEnter your choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
insert();
 break;
case 2:
delete();
break;
case 3:
inorder(root);
break;
case 4:
preorder(root);
break;
case 5:
postorder(root);
break;
case 6:
exit(0);
default :
printf("Wrong choice, Please enter correct choice ");
break;
}
}
}
/* To insert a node in the tree */
void insert()
{
create();
if (root == NULL)
root = temp;
else
search(root);
}
/* To create a node */
void create()
{
int data;

printf("Enter data of node to be inserted : ");

scanf("%d", &data);
temp = (struct btnode *)malloc(1*sizeof(struct btnode));
temp->value = data;
temp->l = temp->r = NULL;
}

/* Function to search the appropriate position to insert the new node

*/
void search(struct btnode *t)
{
if ((temp->value > t->value) && (t->r != NULL)) /* value more
than root node value insert at right */
 search(t->r);
else if ((temp->value > t->value) && (t->r == NULL))
t->r = temp;
else if ((temp->value < t->value) && (t->l != NULL)) /* value
less than root node value insert at left */
search(t->l);
else if ((temp->value < t->value) && (t->l == NULL))
t->l = temp;
}

/* recursive function to perform inorder traversal of tree */

void inorder(struct btnode *t)
{
if (root == NULL)
{
printf("No elements in a tree to display");
return;
}
if (t->l != NULL)
inorder(t->l);
printf("%d -> ", t->value);
if (t->r != NULL)
inorder(t->r);
}

/* To check for the deleted node */

void delete()
{
int data;

if (root == NULL)
{
printf("No elements in a tree to delete");
return;
}
printf("Enter the data to be deleted : ");
scanf("%d", &data);
t1 = root;
t2 = root;
search1(root, data);
}

/* To find the preorder traversal */

void preorder(struct btnode *t)
{
if (root == NULL)
{
printf("No elements in a tree to display");
 return;
}
printf("%d -> ", t->value);
if (t->l != NULL)
preorder(t->l);
if (t->r != NULL)
preorder(t->r);
}

/* To find the postorder traversal */

void postorder(struct btnode *t)
{
if (root == NULL)
{
printf("No elements in a tree to display ");
return;
}
if (t->l != NULL)
postorder(t->l);
if (t->r != NULL)
postorder(t->r);
printf("%d -> ", t->value);
}

/* Search for the appropriate position to insert the new node */

void search1(struct btnode *t, int data)
{
if ((data>t->value))
{
t1 = t;
search1(t->r, data);
}
else if ((data < t->value))
{
t1 = t;
search1(t->l, data);
}
else if ((data==t->value))
{
delete1(t);
}
}

/* To delete a node */
void delete1(struct btnode *t)
{
int k;
/* To delete leaf node */
if ((t->l == NULL) && (t->r == NULL))
{
if (t1->l == t)
{
t1->l = NULL;
}
else
{
t1->r = NULL;
}
t = NULL;
free(t);
return;
}

/* To delete node having one left hand child */

else if ((t->r == NULL))
{
if (t1 == t)
{
root = t->l;
t1 = root;
}
else if (t1->l == t)
{
t1->l = t->l;

}
else
{
t1->r = t->l;
}
t = NULL;
free(t);
return;
}

/* To delete node having right hand child */

else if (t->l == NULL)
{
if (t1 == t)
{
root = t->r;
t1 = root;
}
else if (t1->r == t)
t1->r = t->r;
 else
t1->l = t->r;
t == NULL;
free(t);
return;
}

/* To delete node having two child */

else if ((t->l != NULL) && (t->r != NULL))
{
t2 = root;
if (t->r != NULL)
{
k = smallest(t->r);
flag = 1;
}
else
{
k =largest(t->l);
flag = 2;
}
search1(root, k);
t->value = k;
}
}
/* To find the smallest element in the right sub tree */
int smallest(struct btnode *t)
{
t2 = t;
if (t->l != NULL)
{
t2 = t;
return(smallest(t->l));
}
else
return (t->value);
}

/* To find the largest element in the left sub tree */

int largest(struct btnode *t)
{
if (t->r != NULL)
{
t2 = t;
return(largest(t->r));
}
else
return(t->value);
}
 c. B-tree
typedef char DATA;

struct node
{
DATA d;
struct node *left;
struct node *right;
};

typedef struct node NODE;

typedef NODE *BTREE;

BTREE newnode(void);
BTREE init_node(DATA d, BTREE p1, BTREE p2);
BTREE create_tree(DATA a[], int i, int size);
void preorder (BTREE root);
void inorder (BTREE root);
void postorder (BTREE root);

/**********************
* binarytree.c:
***********************/
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

BTREE new_node()
{
return ((BTREE)malloc(sizeof(NODE)));
}

BTREE init_node(DATA d1, BTREE p1, BTREE p2)

{
BTREE t;

t = new_node();
t->d = d1;
t->left = p1;
t->right = p2;
return t;
}

/* create a linked binary tree from an array */

BTREE create_tree(DATA a[], int i, int size)
{
if (i >= size)
 return NULL;
else
return(init_node(a[i],
create_tree(a, 2*i+1, size),
create_tree(a, 2*i+2, size)));
}

/* preorder traversal */
void preorder (BTREE root)
{
if (root != NULL) {
printf("%c ", root->d);
preorder(root -> left);
preorder(root -> right);
}
}

/* Inorder traversal */
void inorder (BTREE root)
{
if (root != NULL) {
inorder(root -> left);
printf("%c ", root->d);
inorder(root -> right);
}
}

/* postorder binary tree traversal */

void postorder (BTREE root)

{
if (root != NULL) {
postorder(root -> left);
postorder(root -> right);
printf("%c ", root->d);
}
}

/***************************
* program.c
***************************/
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define ARRAY_SIZE 10
int main(void)
{
char a[ARRAY_SIZE] = {'g','d','i','b','f','h','j','a','c','e'};
 BTREE root;

root = create_tree(a, 0, ARRAY_SIZE) ;

assert(root != NULL);
printf("PREORDER\n");
preorder(root);
printf("\n");
printf("INORDER\n");
inorder(root);
printf("\n");
printf("POSTORDER\n");
postorder(root);
printf("\n");
}
 Lab10: Lab Exercise of Graphs
a. Graph Traversal
- BFS
#include<stdio.h>
#include<conio.h>
int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1;
void bfs(int v) {
for (i=1;i<=n;i++)
if(a[v][i] && !visited[i])
q[++r]=i;
if(f<=r) {
visited[q[f]]=1;
bfs(q[f++]);
}
}
void main() {
int v;

printf("\n Enter the number of vertices:");

scanf("%d",&n);
for (i=1;i<=n;i++) {
q[i]=0;
visited[i]=0;
}
printf("\n Enter graph data in matrix form:\n");
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
scanf("%d",&a[i][j]);
printf("\n Enter the starting vertex:");
scanf("%d",&v);
bfs(v);
printf("\n The node which are reachable are:\n");
for (i=1;i<=n;i++)
if(visited[i])
printf("%d\t",i); else
printf("\n BFS is not possible");
getch();
}
 -DFS
#include<stdio.h>

void DFS(int);
int G[10][10],visited[10],n; //n is no of vertices and graph is
sorted in array G[10][10]
void main()
{
int i,j;
printf("Enter number of vertices:");

scanf("%d",&n);
//read the adjecency matrix
printf("\nEnter adjecency matrix of the graph:");

for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
//visited is initialized to zero
for(i=0;i<n;i++)
visited[i]=0;
DFS(0);
}
void DFS(int i)
{
int j;
printf("\n%d",i);
visited[i]=1;
for(j=0;j<n;j++)
if(!visited[j]&&G[i][j]==1)
DFS(j);
}

b. Dijkstra’s Algorithm
// C program for Dijkstra's single source shortest path
// algorithm. The program is for adjacency matrix
// representation of the graph

#include <limits.h>
#include <stdbool.h>
#include <stdio.h>

// Number of vertices in the graph

#define V 9
// A utility function to find the vertex with minimum
// distance value, from the set of vertices not yet included
// in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
// Initialize min value
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;

return min_index;
}

// A utility function to print the constructed distance

// array
void printSolution(int dist[])
{
printf("Vertex \t\t Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t\t\t %d\n", i, dist[i]);
}

// Function that implements Dijkstra's single source

// shortest path algorithm for a graph represented using
// adjacency matrix representation
void dijkstra(int graph[V][V], int src)
{
int dist[V]; // The output array. dist[i] will hold the
// shortest
// distance from src to i

bool sptSet[V]; // sptSet[i] will be true if vertex i is

// included in shortest
// path tree or shortest distance from src to i is
// finalized

// Initialize all distances as INFINITE and stpSet[] as

// false
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;

// Distance of source vertex from itself is always 0

dist[src] = 0;

// Find shortest path for all vertices

for (int count = 0; count < V - 1; count++) {
 // Pick the minimum distance vertex from the set of
// vertices not yet processed. u is always equal to
// src in the first iteration.
int u = minDistance(dist, sptSet);

// Mark the picked vertex as processed

sptSet[u] = true;

// Update dist value of the adjacent vertices of the

// picked vertex.
for(int v = 0; v < V; v++)

// Update dist[v] only if is not in sptSet,

// there is an edge from u to v, and total
// weight of path from src to v through u is
// smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v]
&& dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}

// print the constructed distance array

printSolution(dist);
}

// driver's code
int main()
{
/* Let us create the example graph discussed above */
int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

// Function call
dijkstra(graph, 0);

return 0;
}
 c. Kruskal’s Algorithm
#include<stdio.h>

#define MAX 30

typedef struct edge

{
int u,v,w;
}edge;

typedef struct edgelist

{
edge data[MAX];
int n;
}edgelist;

edgelist elist;

int G[MAX][MAX],n;
edgelist spanlist;

void kruskal();
int find(int belongs[],int vertexno);
void union1(int belongs[],int c1,int c2);
void sort();
void print();

void main()
{
int i,j,total_cost;
printf("\nEnter number of vertices:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
kruskal();
print();
}

void kruskal()
{
int belongs[MAX],i,j,cno1,cno2;
elist.n=0;

for(i=1;i<n;i++)
for(j=0;j<i;j++)
{
if(G[i][j]!=0)
{
[Link][elist.n].u=i;
[Link][elist.n].v=j;
[Link][elist.n].w=G[i][j];
elist.n++;
}
}

sort();
for(i=0;i<n;i++)
belongs[i]=i;
spanlist.n=0;
for(i=0;i<elist.n;i++)
{
cno1=find(belongs,[Link][i].u);
cno2=find(belongs,[Link][i].v);
if(cno1!=cno2)
{
[Link][spanlist.n]=[Link][i];
spanlist.n=spanlist.n+1;
union1(belongs,cno1,cno2);
}
}
}

int find(int belongs[],int vertexno)

{
return(belongs[vertexno]);
}

void union1(int belongs[],int c1,int c2)

{
int i;
for(i=0;i<n;i++)
if(belongs[i]==c2)
belongs[i]=c1;
}

void sort()
{
int i,j;
edge temp;
for(i=1;i<elist.n;i++)
for(j=0;j<elist.n-1;j++)
if([Link][j].w>[Link][j+1].w)
{
temp=[Link][j];
[Link][j]=[Link][j+1];
[Link][j+1]=temp;
}
}

void print()
{
int i,cost=0;
for(i=0;i<spanlist.n;i++)
{
printf("\n%d\t%d\t
%d",[Link][i].u,[Link][i].v,[Link][i].w);
cost=cost+[Link][i].w;
}

printf("\n\nCost of the spanning tree=%d",cost);

}

d. Prim’s Algorithm
#include<stdio.h>
#include<stdlib.h>

#define infinity 9999

#define MAX 20

int G[MAX][MAX],spanning[MAX][MAX],n;

int prims();

int main()
{
int i,j,total_cost;
printf("Enter no. of vertices:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
total_cost=prims();
printf("\nspanning tree matrix:\n");
for(i=0;i<n;i++)
{
printf("\n");
for(j=0;j<n;j++)
printf("%d\t",spanning[i][j]);
}
printf("\n\nTotal cost of spanning tree=%d",total_cost);
return 0;
}

int prims()
{
int cost[MAX][MAX];
int u,v,min_distance,distance[MAX],from[MAX];
int visited[MAX],no_of_edges,i,min_cost,j;
//create cost[][] matrix,spanning[][]
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(G[i][j]==0)
cost[i][j]=infinity;
else
cost[i][j]=G[i][j];
spanning[i][j]=0;
}
//initialise visited[],distance[] and from[]
distance[0]=0;
visited[0]=1;
for(i=1;i<n;i++)
{
distance[i]=cost[0][i];
from[i]=0;
visited[i]=0;
}
min_cost=0; //cost of spanning tree
no_of_edges=n-1; //no. of edges to be added
while(no_of_edges>0)
{
//find the vertex at minimum distance from the tree
min_distance=infinity;
for(i=1;i<n;i++)
if(visited[i]==0&&distance[i]<min_distance)
{
v=i;
min_distance=distance[i];
}
u=from[v];
//insert the edge in spanning tree
spanning[u][v]=distance[v];
spanning[v][u]=distance[v];
no_of_edges--;
visited[v]=1;
//updated the distance[] array
for(i=1;i<n;i++)
if(visited[i]==0&&cost[i][v]<distance[i])
{
distance[i]=cost[i][v];
from[i]=v;
}
min_cost=min_cost+cost[u][v];
}
return(min_cost);
}

e. Floyd-Warshall’s Algorithm
#include <stdio.h>
#include <stdlib.h>

void floydWarshall(int **graph, int n)

{
int i, j, k;
for (k = 0; k < n; k++)
{
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
if (graph[i][j] > graph[i][k] + graph[k][j])
graph[i][j] = graph[i][k] + graph[k][j];
}
}
}
}

int main(void)
{
int n, i, j;
printf("Enter the number of vertices: ");
scanf("%d", &n);
int **graph = (int **)malloc((long unsigned) n * sizeof(int *));
for (i = 0; i < n; i++)
{
graph[i] = (int *)malloc((long unsigned) n * sizeof(int));
}
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
if (i == j)
graph[i][j] = 0;
else
 graph[i][j] = 100;
}
}
printf("Enter the edges: \n");
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
printf("[%d][%d]: ", i, j);
scanf("%d", &graph[i][j]);
}
}
printf("The original graph is:\n");
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
printf("%d ", graph[i][j]);
}
printf("\n");
}
floydWarshall(graph, n);
printf("The shortest path matrix is:\n");
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
printf("%d ", graph[i][j]);
}
printf("\n");
}
return 0;
}