DATA STRUCTURES DEPT.

OF CSE

Program Statement:

1. Write a program to sort the elements of an array using sorting by exchange.

Program:

#include<stdio.h>
#include<conio.h>

void bubblesort(int a[ ],int n); /* Function prototype */

main(
)
{ int a[20],n,i;
clrscr( );
printf("\n enter how many elements you want to sort(max.20):");

scanf("%d",&n); /* read number of elements in the list*/

printf("\n enter the %d elements",n);

for(i=0;i<n;i++)
{
printf("\n enter the value for a[%d]:",i);
scanf("%d",&a[i]); /* read the values */
}

printf("\n before sorting the elements are:");

for(i=0;i<n;i++)
{
printf("%d\t",a[i]); /* print unsorted list */
}

bubblesort(a,n); /* function call */

printf("\n after sorting the elements are:");

for(i=0;i<n;i++)
{
printf("%d\t",a[i]); /* print sorted list */
}
getch( );
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 1
 DATA STRUCTURES DEPT. OF CSE

void bubblesort(int a[ ],int n) /* function definition */

{
int i,j,temp;
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;
}
}
}
}

Input:

Output:

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 2
 DATA STRUCTURES DEPT. OF CSE

Program Statement:

2. Write a program to sort the elements of an array using Selection Sort.

Program:

#include<stdio.h>
#include<conio.h>

void selectionsort(int a[ ],int n); /* function prototype */

main(
)
{ int a[20],n,i;
clrscr( );
printf("\n enter how many elements you want to sort(max.20):");

scanf("%d",&n); /* read number of elements in the list*/

printf("\n enter the %d elements",n);

for(i=0;i<n;i++)
{
printf("\n enter the value for a[%d]:",i);
scanf("%d",&a[i]); /* read the values */
}

printf("\n before sorting the elements are:");

for(i=0;i<n;i++)
{
printf("%d\t",a[i]); /* print unsorted list */
}

selectionsort(a,n); /* function call */

printf("\n after sorting the elements are:");

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

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 3
 DATA STRUCTURES DEPT. OF CSE

void selectionsort(int a[ ],int n) /* function definition */

{
int i,j,min,temp;
for(i=0;i<n-1;i++)
{
min=i;
for(j=i+1;j<n;j++) /* select the minimum element in the list*/
{
if(a[j]<a[min])
{
min=j;

}
temp=a[min];
a[min]=a[i];
a[i]=temp;
}
}

Input:

Output:

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 4
 DATA STRUCTURES DEPT. OF CSE

Program Statement:

[Link] a program to implement heap sort.

Program:

#include<stdio.h>
#include<conio.h>

void heapsort(int a[ ],int n);

void buildheap(int a[ ],int n);
void adjust(int a[ ],int i,int n);
void swap(int *x,int *y);

int i,j,k,flag;

void main( )
{
int a[20],n;
clrscr( );
printf("\n Enter how many elements you want to sort(max.20):");
scanf("%d",&n); /* read number of elements in the list*/
printf("\n Enter the %d elements",n);
for(i=0;i<n;i++)
{
printf("\n enter the value for a[%d]:",i);
scanf("%d",&a[i]); /* read the values */
}
printf("\n before sorting, the elements are:");
for(i=0;i<n;i++)
{
printf("%d\t",a[i]); /* print unsorted list */
}

heapsort(a,n);

printf("\n after sorting, the elements are:");

for(i=0;i<n;i++)
{
printf("%d\t",a[i]); /* print sorted list */
}
getch( );
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 5
 DATA STRUCTURES DEPT. OF CSE

void heapsort(int a[ ],int n)

{
buildheap(a,n);
for(i=(n-2);i>=0;i--)
{
swap(&a[0],&a[i+1]);
adjust(a,0,i);
}
}
void buildheap(int a[ ],int n)
{
for(i=(n/2);i>=0;i--)
{
adjust(a,i,n-1);
}
}
void adjust(int a[ ],int i,int n)
{
k=a[i];
flag=1;
j=2*i;
while(j<= n && flag)
{
if(j< n && a[j]< a[j+1])
{
j++;
}
if(k>= a[j])
{
flag=0;
}
else
{
a[j/2]=a[j];
j=j*2;
}
}
a[j/2]=k;
}
void swap(int *x,int *y)
{
int temp;
temp=*x;
*x=*y;
*y=temp;
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 6
 DATA STRUCTURES DEPT. OF CSE

Input:

Output:

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 7
 DATA STRUCTURES DEPT. OF CSE

Program Statement:

4. Write a program to perform Linear Search on the elements of a given array.

Program:

#include<stdio.h>
#include<conio.h>

int a[100],i,n,key,flag=0;

void lsearch(int a[ ],int n,int key); /* function prototype */

main(
)
{ clrscr( );
printf("\n enter how many elements you want to search(max.100):");

scanf("%d",&n); /* read number of elements in the list*/

printf("\n enter the %d elements in list",n);

for(i=0;i<n;i++)
{
printf("\n enter the value for a[%d]:",i);
scanf("%d",&a[i]); /* read the values */
}

printf("\n enter target element(i.e. key element):");

scanf("%d",&key);

lsearch(a,n,key); /* function call */

getch( );
}

void lsearch(int a[ ],int n,int key) /*function definition */

{
for(i=0;i<n;i++)
{
if(a[i]==key)
{
flag=1;
break;
}
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 8
 DATA STRUCTURES DEPT. OF CSE

if(flag>0)
{
printf("\n search is successful");
printf("\n element %d is found at %d position in list",key,i+1);
}

else
{
printf("\n search is unsuccessfull");
printf("\n element %d is not found in list",key);
}
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 9
 DATA STRUCTURES DEPT. OF CSE

Output:

Input:

Output:

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 10
 DATA STRUCTURES DEPT. OF CSE

Program Statement:

5a).Write a program to perform Binary Search on the elements of a given array.

Program:

#include<stdio.h>
#include<conio.h>

main(
)
{ int a[100],l,u,mid,i,n,key,flag=0;

clrscr( );

printf("\n enter how many elements you want to search(max.100):");

scanf("%d",&n); /* read number of elements in the list*/

printf("\n enter the %d elements in ascending order:",n);

for(i=0;i<n;i++)
{
printf("\n enter the value for a[%d]:",i);
scanf("%d",&a[i]); /* read the values */
}

printf("\n enter target element(i.e. key element):");

scanf("%d",&key);

l=0;
u=n-1;
mid=(l+u)/2;
while(l<= u)
{
if(key = = a[mid])
{
flag=1;
break;
}
if(key > a[mid])
{
l=mid+1;
}

else
{
u=mid-1;
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 11
 DATA STRUCTURES DEPT. OF CSE

mid=(l+u)/2;
}

if(flag > 0)
{
printf("\n search is successful");
printf("\n element %d is found at %d position in list",key,mid+1);
}
else
{
printf("\n search is unsuccessfull");
printf("\n element %d is not found in list",key);
}
getch( );
}

Input:

Output:

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 12
 DATA STRUCTURES DEPT. OF CSE

Input:

Output:

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 13
 DATA STRUCTURES DEPT. OF CSE

Program Statement:

5 b)Write a program to perform Binary Search on the elements of a given array using recursion.

Program:

#include<stdio.h>
#include<conio.h>

bsearch(int a[ ],int n,int l,int u,int key); /* function prototype */

main(
)
{ int a[100],l,u,mid,i,n,key,flag;

clrscr( );
printf("\n enter how many elements you want to search(max.100):");

scanf("%d",&n); /* read number of elements in the list*/

printf("\n enter the %d elements in ascending order:",n);

for(i=0;i<n;i++)
{
printf("\n enter the value for a[%d]:",i);
scanf("%d",&a[i]); /* read the values */
}

printf("\n enter target element(i.e. key element):");

scanf("%d",&key);

flag=bsearch(a,n,0,n-1,key); /* function call */

if(flag>0)
{
printf("\n search is successful");
printf("\n element %d is found in list",key);
}
else
{
printf("\n search is unsuccessfull");
printf("\n element %d is not found in list",key);
}
getch( );
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 14
 DATA STRUCTURES DEPT. OF CSE

bsearch(int a[ ],int n,int l,int u,int key) /* function definition */

{
int mid;
if(l > u)
{
return (-1);
}
mid=(l+u)/2;

if(key == a[mid])
{
return(mid);
}
if(key < a[mid])
{
return(bsearch(a,n,l,mid-1,key));
}
else
{
return(bsearch(a,n,mid+1,u,key));
}
}

Run-1:

Input:

Output:

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 15
 DATA STRUCTURES DEPT. OF CSE

Run-2:

Input:

Output:

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 16
 DATA STRUCTURES DEPT. OF CSE

Program Statement:

6 a). Write a program to convert infix expression to postfix expression.

Program:

#include<stdio.h>
#include<conio.h>
#include<ctype.h>

#define MAX 20

char infix[MAX],post[MAX],s[MAX],ch,t,x,ele;
int i=0,j=0,top= -1;

void push(char ele) /* function to push the character */

{
top++;
s[top]=ele;
}

char pop( ) /* function to pop character */

{
ele=s[top];
top--;
return(ele);
}

int priority(char ch) /* function assign priorities */

{
if(ch= ='^')
{
return(4);
}
else if(ch= ='*' || ch= ='/')
{
return(3);
}
else if(ch= ='-' || ch= ='+')
{
return(2);
}
else
{
return(0);
}
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 17
 DATA STRUCTURES DEPT. OF CSE

void check( ) /* function to check the priorities */

{
while(priority(t)<=priority(s[top]))
{
post[j++]=pop( );
}
}

int main( )
{
clrscr( );
printf("\n enter the infix expression:");
scanf("%s",infix);
push('#');
while(infix[i]!='\0')
{
t=infix[i];
if(isalpha(t))
{
post[j++]=t;
}
else
{
if(t=='+' || t=='-' || t=='*' || t=='/' || t=='(' || t==')' || t=='^')
switch(t)
{
case '(': push(t);
break;
case '-':
case '+': check( );
push(t);
break;
case '*':
case '/': check( );
push(t);
break;
case '^': check( );
push(t);
break;
case ')': do
{
x=pop( );
post[j++]=x;
}while(x!= '(' );
j=j-1;
break;
}
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 18
 DATA STRUCTURES DEPT. OF CSE

i=i+1;
}

while(s[top]!='#')
{
post[j++]=pop();
}
post[j]='\0';
printf("\n the postfix notation of given infix %s is %s",infix,post);
getch( );
return 0;
}

Input and Output:

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 19
 DATA STRUCTURES DEPT. OF CSE

Program Statement:

6 b)Write a program to evaluate postfix expression.

Program:

#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#include<math.h>
#include<stdlib.h>

#define MAX 50

char postfix[MAX],ch;
int i=0,top= -1;
float s[MAX],op1,op2,temp,val,res;

float pop( )
{
return (s[top--]);
}
float operate(float op1,float op2,char ch)
{
switch(ch)
{
case '+':temp=op1+op2;
break;
case '-':temp=op1-op2;
break;
case '*':temp=op1*op2;
break;
case '/':temp=op1/op2;
break;
case '^':temp=pow(op1,(int)op2);
break;
}
return(temp);
}
void push(float val)
{
top++;
s[top]=val;
}

Annamacharya Institute of Technology and Sciences Page

,Kadapa 20
 DATA STRUCTURES DEPT. OF CSE

int main( )
{
clrscr( );
printf("\n enter the postfix expression:");
scanf("%s",postfix); while(postfix[i]!='\
0')
{
ch=postfix[i];
if(isalpha(ch))
{
printf("\n enter value for %c:",ch);
scanf("%f",&val);
push(val);

}
else
{
if(ch= ='*' || ch= ='/' || ch= ='+' || ch= ='-' || ch= ='^' )
{
op2=pop( );
op1=pop( );
res=operate(op1,op2,ch);
push(res);
}
}
i=i+1;
}
temp=pop( );
printf("\n the simplified answer for %s is %f",postfix,temp);
getch( );
return 0;
}

Annamacharya Institute of Technology and Sciences Page

,Kadapa 21
 DATA STRUCTURES DEPT. OF CSE

Input:

Output:

Input:

Output:

Annamacharya Institute of Technology and Sciences Page

,Kadapa 22
 DATA STRUCTURES DEPT. OF CSE

Program Statement:

7 a)Write a program to implement stack using arrays.

Program:

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

#define MAX 5

int top= -1;

int a[MAX];

/* function prototypes */

void push( );
void pop( );
void display( );

void push( )
{
int ele;
if(top= =MAX-1)
{
printf("stack is overflow\n");
return;
}

top++;
printf("enter the element:");
scanf("%d",&ele);

a[top]=ele;

}
void pop( )
{
int ele;
if(top= = -1)
{
printf("stack is underflow\n");
return;
}

ele=a[top];
Annamacharya Institute of Technology and Sciences Page
,Kadapa 23
 DATA STRUCTURES DEPT. OF CSE

top- -;
printf("the deleted element is:%d",ele);
}

void display( )
{
int i;
if(top= = -1)
{
printf("stack is underflow\n");
return;
}
printf("the elements are:");
for(i=0;i<=top;i++)
{
printf("%d\t",a[i]);
}
}

main(
)
{ int ch;
clrscr( );

while(1)
{
printf("\n Menu \n");
printf(" 1. push \n");
printf(" 2. pop \n");
printf(" 3. display \n");
printf(" 4. exit \n");

printf("enter your choice:");

scanf("%d",&ch);

switch(ch)
{
case 1:push( );
break;
case 2:pop( );
break;
case 3:display( );
break;
case 4:exit(0);
default:printf("Invalid option\n");
}
}
}

Annamacharya Institute of Technology and Sciences Page

,Kadapa 24
 DATA STRUCTURES DEPT. OF CSE

Output:

Annamacharya Institute of Technology and Sciences Page

,Kadapa 25
 DATA STRUCTURES DEPT. OF CSE

Annamacharya Institute of Technology and Sciences Page

,Kadapa 26
 DATA STRUCTURES DEPT. OF CSE

Program Statement:

7 b)Write a program to implement queue using arrays

Program:

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

#define MAX 5

int rear = -1,front = -1;

int a[MAX];

/* function prototypes */

void insert( );
void delete( );
void display( );

void insert( )
{
int ele;
if(rear= =MAX-1)
{
printf("queue is overflow\n");
return;
}

printf("enter the element:");

scanf("%d",&ele);

if(front= = -1)
{
rear=0;
front=0;
}
else
{
rear++;
}
a[rear]=ele;

Annamacharya institute of technology and sciences,kadapa Page 27

 DATA STRUCTURES DEPT. OF CSE

void delete( )
{
int ele;
if(rear= = -1)
{
printf("queue is underflow\n");
return;
}

ele=a[front];
if(rear= =front)
{
rear = -1;
front = -1;
}
else
{
front++;
}
printf("the deleted element is:%d",ele);
}

void display( )
{
int i;
if(rear = = -1)
{
printf("queue is underflow\n");
return;
}
printf("the elements are:");
for(i=front;i<= rear;i++)
{
printf("%d\t",a[i]);
}
}

main(
)
{ int ch;
clrscr( );

while(1)
{
printf("\n Menu \n");
printf(" 1. insert \n");
printf(" 2. delete \n");

Annamacharya institute of technology and sciences,kadapa Page 28

 DATA STRUCTURES DEPT. OF CSE

printf(" 3. display \n");

Annamacharya institute of technology and sciences,kadapa Page 29

 DATA STRUCTURES DEPT. OF CSE

printf(" 4. exit \n");

printf("enter your choice:");

scanf("%d",&ch);

switch(ch)
{
case 1:insert( );
break;
case 2:delete( );
break;
case 3:display( );
break;
case 4:exit(0);
default:printf("Invalid option\n");
}
}
}

Output:

Annamacharya institute of technology and sciences,kadapa Page 30

 DATA STRUCTURES DEPT. OF CSE

Annamacharya institute of technology and sciences,kadapa Page 31

 DATA STRUCTURES DEPT. OF CSE

Program Statement:

7c) Write a program to implement circular queue using arrays

Program:

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

#define MAX 5

int rear= -1,front= -1;

int a[MAX];

/* function prototypes */

void insert( );
void delete( );
void display( );

void insert( )
{
int ele;
if(front= =(rear+1) % MAX)
{
printf(" circular queue is overflow\n");
return;
}

printf("enter the element:");

scanf("%d",&ele);

if(front= = -1)
{
rear=0;
front=0;
}
else
{
rear=(rear+1) % MAX;
}
a[rear]=ele;

Annamacharya institute of technology and sciences,kadapa Page 32

 DATA STRUCTURES DEPT. OF CSE

void delete( )
{
int ele;
if(rear= = -1)
{
printf(" circular queue is underflow\n");
return;
}

ele=a[front];
if(rear= =front)
{
rear = -1;
front= -1;
}
else
{
front=(front+1) % MAX;

}
printf("the deleted element is:%d",ele);
}

void display( )
{
int i;
if(rear= = -1)
{
printf("circular queue is underflow\n");
return;
}
printf("the elements are:");
if(front<= rear)
{
for(i=front;i<=rear;i++)
{
printf("%d\t",a[i]);
}
}
else
{
for(i=front;i<MAX;i++)
{
printf("%d\t",a[i]);
}
for(i=0;i<= rear;i++)
{
printf("%d\t",a[i]);
Annamacharya institute of technology and sciences,kadapa Page 33
 DATA STRUCTURES DEPT. OF CSE

}
}
}

main(
)
{ int ch;
clrscr( );

while(1)
{
printf("\n Menu \n");
printf(" 1. insert \n");
printf(" 2. delete \n");
printf(" 3. display \n");
printf(" 4. exit \n");

printf("enter your choice:");

scanf("%d",&ch);

switch(ch)
{
case 1:insert( );
break;
case 2:delete( );
break;
case 3:display( );
break;
case 4:exit(0);
default:printf("Invalid option\n");
}
}
}

Annamacharya institute of technology and sciences,kadapa Page 34

 DATA STRUCTURES DEPT. OF CSE

Output:

Annamacharya institute of technology and sciences,kadapa Page 35

 DATA STRUCTURES DEPT. OF CSE

Program Statement:

7 d)Write a program to implement stack using linked lists

Program:

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

#define NULL 0

struct node
{
int data;
struct node *link;
}*temp,*head,*temp1,*top;

/* function prototypes */

void push();
void pop();
void display();

void push()
{
int ele;

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

scanf("%d",&ele);

temp=(struct node*)malloc(sizeof(struct node));

if(temp==NULL)
{
printf("\n memory allocation error");
return;
}

if(head->link==NULL)
{
temp->data=ele;
head->link=temp;

Annamacharya institute of technology and sciences,kadapa Page 36

 DATA STRUCTURES DEPT. OF CSE

temp->link=NULL;
top=temp;
}

else
{
temp->link=head->link;
head->link=temp;
temp->data=ele;
top=temp;
}
}

void pop()
{
int ele;

if(top==NULL)
{
printf("\n linked stack is empty");
return;
}
temp=top;
temp1=temp->link;
head->link=temp1;
ele=temp->data;

free(temp);
top=temp1;

printf("\n the deleted element is:%d",ele);

}

void display()
{
if(head->link==NULL)
{
printf("\n linked stack is empty");
return;
}
printf("\n the elements are:");

temp=head->link; while(temp!
=NULL)
{
printf("%d\t",temp->data);

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 37
 DATA STRUCTURES DEPT. OF CSE

temp=temp->link;
}
}

main()
{
int ch;

top=NULL;

clrscr();

while(1)
{
printf("\n Menu");
printf("\n [Link]
")
;
printf("\n [Link] ” );
printf("\n [Link] ");
printf("\n [Link] ");

printf("\n enter your choice:");

scanf("%d",&ch);

switch(ch)
{
case 1:push();
break;
case 2:pop();
break;
case 3:display();
break;
case 4:exit(0);

default:printf("\n invalid option");

}
}
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 38
 DATA STRUCTURES DEPT. OF CSE

Input and Output

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 39
 DATA STRUCTURES DEPT. OF CSE

Program Statement:

7 e) Write a program to implement queue using linked lists

Program:

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

#define NULL 0

struct node
{
int data;
struct node *link;
}*temp,*head,*front,*rear;

/* function prototypes

*/ void insert();
void delete();
void display();

void insert()
{
int ele;

printf("\n Enter the

element:");
scanf("%d",&ele);

temp=(struct node*)malloc(sizeof(struct node));

if(temp==NULL)
{
printf("\n memory allocation
error"); return;
}

if(head->link==NULL)
{
temp->data=ele;
head->link=temp;
temp->link=NULL;

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 40
 DATA STRUCTURES DEPT. OF CSE

front=rear=temp;
}

else
{
temp->link=NULL;
rear->link=temp;
temp->data=ele;
rear=temp;
}
}

void delete()
{
int ele;

if(front==NULL)
{
printf("\n linked queue is
empty"); return;
}
if(front==rear)
{
ele=front->data;
front=rear=NULL;
}
else
{
ele=front->data;
temp=front;
front=front->link;
free(temp);
}

printf("\n the deleted element is:%d",ele);

}

void display()
{
if(rear==NULL)
{
printf("\n linked queue is
empty"); return;
}
printf("\n the elements are:");

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 41
 DATA STRUCTURES DEPT. OF CSE

temp=front;
while(temp!=rear-
>link)
{
printf("%d\t",temp->data);
temp=temp->link;
}
}

main()
{
int
ch;

front=rear=NULL;

clrscr();

while(1)
{
printf("\n Menu\n");
printf("\n [Link] \n");
printf("\n [Link] \n");
printf("\n [Link] \n");
printf("\n [Link] \n");

printf("\n enter your

choice:"); scanf("%d",&ch);

switch(ch)
{
case 1:insert();
break;
case 2:delete();
break;
case 3:display();
break;
case 4:exit(0);

default:printf("\n invalid option");

}
}
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 42
 DATA STRUCTURES DEPT. OF CSE

Input and Output

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 43
 DATA STRUCTURES DEPT. OF CSE

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 44
 DATA STRUCTURES DEPT. OF CSE

Program Statement:

7 f)Write a program to implement circular queue using linked lists.

Program:

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

#define NULL 0

struct Node
{
int data;
struct Node *link;
}*head,*temp,*front,*rear,*temp1;

void enqueue( );
void dequeue( );
void display( );

void enqueue( )
{
int ele;
printf("\n\t Enter the element:");
scanf("%d",&ele);
temp=(struct Node*)malloc(sizeof(struct Node));
if(temp= =NULL)
{
printf("\n Memory allocation error");
return;
}
if(front= =NULL)
{
temp->data=ele;
head->link=temp;
front=rear=temp;
rear->link=head;
}

else
{
temp1=head->link;
while(temp1->link!=head)

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 45
 DATA STRUCTURES DEPT. OF CSE

{
temp1=temp1->link;
}
temp1->link=temp;
temp->data=ele;
rear=temp;
rear->link=head;

}
}
void dequeue( )
{
int ele;
if(front= =NULL)
{
printf("\n\t linked circular queue is empty");
return;
}
if(front= =rear)
{
temp=head->link;
ele=front->data;
head->link=NULL;
front=rear=NULL;
free(temp);
}
else
{
temp=head->link;
head->link=temp->link;
ele=front->data;
front=temp->link;
rear->link=head;
free(temp);
}
printf("\n\t The deleted element is %d",ele);
}

void display()
{
if(rear= =NULL)
{
printf("\n\t linked circular queue is empty");
return;
}
printf("\n\t The elements are:");
temp=front;
while(temp!=rear)
{

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 46
 DATA STRUCTURES DEPT. OF CSE

printf("%d\t",temp->data);
temp=temp->link;
}
printf("%d\t",temp->data);
}
void main( )
{
int ch;
front=rear=NULL;
clrscr( );
while(1)
{
printf("\n Menu ");
printf("\n [Link]");
printf("\n [Link]");
printf("\n [Link]");
printf("\n [Link]");
printf("\n\t Enter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: enqueue( );
display( );
break;
case 2: dequeue( );
display( );
break;
case 3: display( );
break;
case 4: exit(0);
default:printf("\n invalid option");
}
}
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 47
 DATA STRUCTURES DEPT. OF CSE

Output:

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 48
 DATA STRUCTURES DEPT. OF CSE

Program Statement:

8 .Write a program to perform the operations creation, insertion, deletion, and traversing a singly
linked list.

Program:

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

#define NULL 0

struct node
{
int data;
struct node *link;
}*temp,*head,*temp1,*next;

/* function prototype */

void insertf(); /* insertion as a first node

*/ void insertl(); /* insertion as a last node */
void insertsp(); /* insertion at the specified position */
void deletef(); /* deletion as a first node */
void deletel(); /* deletion as a last node */
void deletesp(); /* deletion at the specified position */

void insertf()
{
int ele;

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

scanf("%d",&ele);

temp=(struct node*)malloc(sizeof(struct node));

if(temp==NULL)
{
printf("\n memory allocation error");
return;
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 49
 DATA STRUCTURES DEPT. OF CSE

if(head->link==NULL)
{
temp->data=ele;
head->link=temp;
temp->link=NULL;
}

else
{
temp->link=head->link;
head->link=temp;
temp->data=ele;
}
}

void insertl()
{
int ele;

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

scanf("%d",&ele);

temp=(struct node*)malloc(sizeof(struct node));

if(temp==NULL)
{
printf("\n memory allocation error");
return;
}

if(head->link==NULL)
{
temp->data=ele;
head->link=temp;
temp->link=NULL;
}
else
{
temp1=head->link;
while(temp1->link!=NULL)
{
temp1=temp1->link;
}
temp1->link=temp;
temp->data=ele;

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 50
 DATA STRUCTURES DEPT. OF CSE

temp->link=NULL;
}
}

void insertsp()
{
int ele;
int pos,i;

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

scanf("%d",&ele);

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

scanf("%d",&pos);

temp=(struct node*)malloc(sizeof(struct node));

if(temp==NULL)
{
printf("\n memory allocation error");
return;
}

if(head->link==NULL)
{
temp->data=ele;
head->link=temp;
temp->link=NULL;
}
else
{
temp1=head; i=1;
while(i<pos)
{
temp1=temp1->link; i+
+;
}
temp->link=temp1->link;
temp1->link=temp;
temp->data=ele;
}
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 50
 DATA STRUCTURES DEPT. OF CSE

void deletef()
{
int ele;
if(head->link==NULL)
{
printf("\n singly linked list is
empty"); return;
}
temp=head->link;
temp1=temp->link;
head->link=temp1;
ele=temp->data;

free(temp);
printf("\n the deleted element is:%d",ele);
}

void deletel()
{
int ele;

if(head->link==NULL)
{
printf("\n singly linked list is
empty"); return;
}

temp1=head; while(temp1-
>link!=NULL)
{
temp=temp1;
temp1=temp1->link;
}
temp->link=NULL;
ele=temp1->data;

free(temp1);

printf("\n the deleted element is:%d",ele);

}

void deletesp()
{
int ele;
int pos,i;

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 51
 DATA STRUCTURES DEPT. OF CSE

if(head->link==NULL)
{
printf("\n singly linked list is
empty"); return;
}

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

scanf("%d",&pos);

temp1=head;
i=0;
while(i<pos)
{
temp=temp1;
i++;
temp1=temp1->link;
}
temp->link=temp1->link;
ele=temp1->data;
printf("\n the deleted element is:%d",ele);

free(temp1);

void display()
{
if(head->link==NULL)
{
printf("\n singly linked list is
empty"); return;
}
printf("\n the elements are:");

temp=head->link; while(temp!
=NULL)
{
printf("%d\t",temp->data);
temp=temp->link;
}
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 52
 DATA STRUCTURES DEPT. OF CSE

main()
{
int ch;

head->link=NULL; clrscr();

while(1)
{
printf("\n Menu\n");
printf("\n [Link] at front \n");
printf("\n [Link] at last \n");
printf("\n [Link] at any specified position \n");
printf("\n [Link] at front \n");
printf("\n [Link] at last \n");
printf("\n [Link] at any specified position \n");
printf("\n [Link] \n");
printf("\n [Link] \n");

printf("\n enter your choice:");

scanf("%d",&ch);

switch(ch)
{
case 1:insertf();
break;
case 2:insertl();
break;
case 3:insertsp();
break;
case 4:deletef();
break;
case 5:deletel();
break;
case 6:deletesp();
break;
case 7:display();
break;
case 8:exit(0);
default:printf("\n invalid option");
}
}
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 53
 DATA STRUCTURES DEPT. OF CSE

Run:

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 54
 DATA STRUCTURES DEPT. OF CSE

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 55
 DATA STRUCTURES DEPT. OF CSE

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 56
 DATA STRUCTURES DEPT. OF CSE

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 57
 DATA STRUCTURES DEPT. OF CSE

Program Statement:

9 Write a program to perform the operations creation, insertion, deletion, and traversing a
doubly linked list.

Program:

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

#define NULL 0
struct node
{
int data;
struct node *flink;
struct node *blink; /* flink->forward link & blink->backword link */
}*next,*head,*temp,*temp1;

void insertF( ); //insertion as a first node

void insertE( ); //insertion as a last node
void insertA( ); //insertion at the specified location
void deleteF( ); //deletion as a first node
void deleteE( ); //deletion as a lst node
void deleteA( ); //deletion at the specified location
void fDisplay( ); //forward display
void bDisplay( ); //backword display

void insertF( )
{
int ele;
printf("\n\t Enter the element:");
scanf("%d",&ele);
temp=(struct node*)malloc(sizeof(struct node));
if(temp= =NULL)
{
printf("\n Memory allocation error");
return;
}

if(head->flink= =NULL)
{
head->flink=temp;
temp->data=ele;

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 58
 DATA STRUCTURES DEPT. OF CSE

temp->blink=head;
temp->flink=NULL;
}
else
{
temp->flink=head->flink;
temp->blink=head;
head->flink=temp;
temp->data=ele;
temp1=temp->flink;
temp1->blink=temp;
}
}
void insertE( )
{
int ele;
printf("\n\t Enter the element:");
scanf("%d",&ele);
temp=(struct node*)malloc(sizeof(struct node));
if(temp= =NULL)
{
printf("\n Memory allocation error");
return;
}
if(head->flink= =NULL)
{
temp->data=ele;
temp->blink=head;
head->flink=temp;
temp->flink=NULL;
}
else
{
temp1=head->flink;
while(temp1->flink!=NULL)
{
temp1=temp1->flink;
}
temp1->flink=temp;
temp->data=ele;
temp->flink=NULL;
temp->blink=temp1;
}
}
void insertA( )
{
int ele;
int pos,i;
printf("\n\t Enter the element:");

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 59
 DATA STRUCTURES DEPT. OF CSE

scanf("%d",&ele);
printf("\n\t Enter the position:");
scanf("%d",&pos);
temp=(struct node*)malloc(sizeof(struct node));
if(temp= =NULL)
{
printf("\n Memory allocation error");
return;
}
if(head->flink= =NULL)
{
temp->data=ele;
head->flink=temp;
temp->blink=head;
temp->flink=NULL;
}
else
{
temp1=head;
i=1;
while(i<pos)
{
temp1=temp1->flink; i+
+;
}
temp->flink=temp1->flink;
temp1->flink=temp;
temp->data=ele;
temp->blink=temp1;
temp=temp->flink;
temp->blink=temp;
}
}
void deleteF( )
{
int ele;
if(head->flink= =NULL)
{
printf("\n\t Doubly linked list is empty");
return;
}
temp=head->flink;
temp1=temp->flink;
head->flink=temp1;
temp1->blink=head;
ele=temp->data;
free(temp);
printf("\n\t The deleted element is %d",ele);
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 60
 DATA STRUCTURES DEPT. OF CSE

void deleteE( )
{
int ele;
if(head->flink= =NULL)
{
printf("\n\t Doubly linked list is empty");
return;
}
temp1=head;
while(temp1->flink!=NULL)
{
temp=temp1;
temp1=temp1->flink;
}
temp->flink=NULL;
ele=temp1->data;
free(temp1);
printf("\n\t The deleted element is %d",ele);
}
void deleteA( )
{
int ele;
int pos,i;
if(head->flink= =NULL)
{
printf("\n\t Doubly linked list is empty");
return;
}
printf("\n\t Enter the position:");
scanf("%d",&pos);
temp1=head;
i=0;
while(i<pos)
{
temp=temp1;
i++;
temp1=temp1->flink;
}

temp->flink=temp->flink;
temp=temp->flink;
temp->blink=temp1->blink;
ele=temp1->data;
printf("\n\t The deleted element is %d",ele);
free(temp1);
}
void fDisplay( )
{
if(head->flink= =NULL)

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 61
 DATA STRUCTURES DEPT. OF CSE

{
printf("\n\t Doubly linked list is empty");
return;
}
printf("\n\t the elements are:");
temp=head->flink;
while(temp!=NULL)
{
printf("%d\t",temp->data);
temp=temp->flink;
}
}
void bDisplay( )
{
if(head->flink= =NULL)
{
printf("\n\t Doubly linked list is empty");
return;
}
temp=head;
while(temp->flink!=NULL)
{
temp=temp->flink;
}
printf("\n\t The elements are:");
temp1=temp;
while(temp1->blink!=NULL)
{
printf("%d\t",temp1->data);
temp1=temp1->blink;
}
}

void main( )
{
int ch;
head->flink=NULL;
head->blink=NULL;
clrscr( );
while(1)
{
printf("\n Menu \n");
printf(" [Link] at front \n");
printf(" [Link] at end \n");
printf(" [Link] at any position \n");
printf(" [Link] at front \n");
printf(" [Link] at end \n");
printf(" [Link] at any position \n");

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 62
 DATA STRUCTURES DEPT. OF CSE

printf(" [Link] \n");

printf(" [Link] \n");
printf(" [Link] \n");

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

scanf("%d",&ch);

switch(ch)
{
case 1: insertF( );
break;
case 2: insertE( );
break;
case 3: insertA( );
break;
case 4: deleteF( );
break;
case 5: deleteE( );
break;
case 6: deleteA( );
break;
case 7: fDisplay( );
break;
case 8: bDisplay( );
break;
case 9: exit(0); default:printf("\
nInalid option");
}
}
}

Output:

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 63
 DATA STRUCTURES DEPT. OF CSE

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 64
 DATA STRUCTURES DEPT. OF CSE

Program Statement:

10 a) Write a program to remove duplicates from ordered arrays

Program:

#include<stdio.h>
#include<conio.h>
main()
{
int a[20],n,i,j;
clrscr();
printf("\n Enter number of elements in
array:"); scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\n Enter value for
a[%d]:",i); scanf("%d",&a[i]);
}
printf("\n The array elements are:");
for(i=0;i<n;i++)
{
printf(" %d\t",a[i]);
}

for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[j]==a[i])
{
while(j<n)
{
a[j]=a[j+1];
j++;
}
n=n-1;
}
}
}
printf("\n\n\n After removing duplicate array elements array elements are:");
for(i=0;i<n;i++)
{
printf(" %d\t",a[i]);
}
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 65
 DATA STRUCTURES DEPT. OF CSE

Input:

Output:

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 66
 DATA STRUCTURES DEPT. OF CSE

Program Statement:

10 b)Write a program to remove duplicates from unordered arrays.

Program:

#include<stdio.
h>
#include<conio.
h> void main()
{
int
a[20],n,i,j,k;
clrscr();
printf("\n Enter number of elements in
array:"); scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\n Enter value for a[%d]:",i);
scanf("%d",&a[i]);
}
printf("\n The array elements are:");
for(i=0;i<n;i++)
{
printf(" %d\t",a[i]);
}
for(i=0; i < n; i++)
{
for(j=i+1; j < n; )
{
if(a[j] == a[i])
{
for(k=j; k < n;k++)
{
a[k] = a[k+1];
}
n--;
}
else
{
j+
} +;
}
}
printf("\n\n\n After removing duplicate array elements array
elements are:"); for(i=0;i<n;i++)
{
printf(" %d\t",a[i]);
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 67
 DATA STRUCTURES DEPT. OF CSE

Input:

Output:

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 68
 DATA STRUCTURES DEPT. OF CSE

Program Statement:

[Link] a program to sort numbers using insertion sort.

Program:

#include<stdio.h>
#include<conio.h>

void insertionsort(int a[],int n); /* function prototype */

main()
{
int a[20],n,i;
clrscr();
printf("\n enter how many elements you want to sort(max.20):");

scanf("%d",&n); /* read number of elements in the list */

printf("\n enter the %d elements",n);

for(i=0;i<n;i++)
{
printf("\n enter the value for a[%d]:",i);
scanf("%d",&a[i]); /* read the values */
}

printf("\n before sorting, the elements are:");

for(i=0;i<n;i++)
{
printf("%d\t",a[i]); /* print unsorted list */
}

insertionsort(a,n); /* function call

*/ printf("\n after sorting, the elements are:");

for(i=0;i<n;i++)
{
printf("%d\t",a[i]); /* print sorted list */
}
getch();
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 69
 DATA STRUCTURES DEPT. OF CSE

void insertionsort(int a[],int n) /* function definition */

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

Input:

Output:

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 70
 DATA STRUCTURES DEPT. OF CSE

Program Statement:

12 Write a program to sort numbers using quick sort.

Program:

#include<stdio.h>
#include<conio.h>

void quicksort(int a[],int l,int u);

main()
{
int a[20],n,i;
clrscr();
printf("\n enter how many elements you want to sort(max.20):");

scanf("%d",&n); /* read number of elements in the list */

printf("\n enter the %d elements",n);

for(i=0;i<n;i++)
{
printf("\n enter the value for a[%d]:",i);
scanf("%d",&a[i]); /* read the values */
}

printf("\n before sorting, the elements are:");

for(i=0;i<n;i++)
{
printf("%d\t",a[i]); /* print unsorted list */
}

quicksort(a,0,n-1);

printf("\n after sorting, the elements are:");

for(i=0;i<n;i++)
{
printf("%d\t",a[i]); /* print sorted list */
}
getch();
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 71
 DATA STRUCTURES DEPT. OF CSE

void quicksort(int a[],int l,int u)

{
int key=l,i=l,j=u,temp;
while(i<j)
{
while(a[key]>=a[i])
{
i++;
}
while(a[key]<a[j])
{
j--;
}
if(i<j)
{
a[i]=(a[i]+a[j]) - (a[j]=a[i]); /* single line swapping */
}
a[key]=(a[key]+a[j])-(a[j]=a[key]);
quicksort(a,l,j-1);
quicksort(a,j+1,u);
}

Run:

Input:

Output:

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 72
 DATA STRUCTURES DEPT. OF CSE

Program statement:
13. Write a program for tic tac toe game

#include<bits/stdc++.h>
using namespace std;

#define COMPUTER 1
#define HUMAN 2

#define SIDE 3 // Length of the board

// Computer will move with 'O'

// and human with 'X'
#define COMPUTERMOVE 'O'
#define HUMANMOVE 'X'

// A function to show the current board status

void showBoard(char board[][SIDE])
{
printf("\n\n");

printf("\t\t\t %c | %c | %c \n", board[0][0],

board[0][1], board[0][2]);
printf("\t\t\t--------------\n");
printf("\t\t\t %c | %c | %c \n", board[1][0],
board[1][1], board[1][2]);
printf("\t\t\t--------------\n");
printf("\t\t\t %c | %c | %c \n\n", board[2][0],
board[2][1], board[2][2]);

return;
}

// A function to show the instructions

void showInstructions()
{
printf("\t\t\t Tic-Tac-Toe\n\n");
printf("Choose a cell numbered from 1 to 9 as below"
" and play\n\n");

printf("\t\t\t 1 | 2 | 3 \n");
printf("\t\t\t--------------\n");
printf("\t\t\t 4 | 5 | 6 \n");
printf("\t\t\t--------------\n");
printf("\t\t\t 7 | 8 | 9 \n\n");

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

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 73
 DATA STRUCTURES DEPT. OF CSE

return;
}

// A function to initialise the game

void initialise(char board[][SIDE], int moves[])
{
// Initiate the random number generator so that
// the same configuration doesn't arises
srand(time(NULL));

// Initially the board is empty

for (int i=0; i<SIDE; i++)
{
for (int j=0; j<SIDE; j++)
board[i][j] = ' ';
}

// Fill the moves with numbers

for (int i=0; i<SIDE*SIDE; i++)
moves[i] = i;

// randomise the moves

random_shuffle(moves, moves + SIDE*SIDE);

return;
}

// A function to declare the winner of the game

void declareWinner(int whoseTurn)
{
if (whoseTurn == COMPUTER)
printf("COMPUTER has won\n");
else
printf("HUMAN has won\n");
return;
}

// A function that returns true if any of the row

// is crossed with the same player's move
bool rowCrossed(char board[][SIDE])
{
for (int i=0; i<SIDE; i++)
{
if (board[i][0] == board[i][1] &&
board[i][1] == board[i][2] &&
board[i][0] != ' ')
return (true);
}
return(false);

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 74
 DATA STRUCTURES DEPT. OF CSE

// A function that returns true if any of the column

// is crossed with the same player's move
bool columnCrossed(char board[][SIDE])
{
for (int i=0; i<SIDE; i++)
{
if (board[0][i] == board[1][i] &&
board[1][i] == board[2][i] &&
board[0][i] != ' ')
return (true);
}
return(false);
}

// A function that returns true if any of the diagonal

// is crossed with the same player's move
bool diagonalCrossed(char board[][SIDE])
{
if (board[0][0] == board[1][1] &&
board[1][1] == board[2][2] &&
board[0][0] != ' ')
return(true);

if (board[0][2] == board[1][1] &&

board[1][1] == board[2][0] &&
board[0][2] != ' ')
return(true);

return(false);
}

// A function that returns true if the game is over

// else it returns a false
bool gameOver(char board[][SIDE])
{
return(rowCrossed(board) || columnCrossed(board)
|| diagonalCrossed(board) );
}

// A function to play Tic-Tac-Toe

void playTicTacToe(int whoseTurn)
{
// A 3*3 Tic-Tac-Toe board for playing
char board[SIDE][SIDE];

int moves[SIDE*SIDE];

// Initialise the game

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 75
 DATA STRUCTURES DEPT. OF CSE

initialise(board, moves);

// Show the instructions before playing

showInstructions();

int moveIndex = 0, x, y;

// Keep playing till the game is over or it is a draw

while (gameOver(board) == false &&
moveIndex != SIDE*SIDE)
{
if (whoseTurn == COMPUTER)
{
x = moves[moveIndex] / SIDE;
y = moves[moveIndex] % SIDE;
board[x][y] = COMPUTERMOVE;
printf("COMPUTER has put a %c in cell %d\n",
COMPUTERMOVE, moves[moveIndex]+1);
showBoard(board);
moveIndex ++;
whoseTurn = HUMAN;
}

else if (whoseTurn == HUMAN)

{
x = moves[moveIndex] / SIDE;
y = moves[moveIndex] % SIDE;
board[x][y] = HUMANMOVE;
printf ("HUMAN has put a %c in cell %d\n",
HUMANMOVE, moves[moveIndex]+1);
showBoard(board);
moveIndex ++;
whoseTurn = COMPUTER;
}
}

// If the game has drawn

if (gameOver(board) == false &&
moveIndex == SIDE * SIDE)
printf("It's a draw\n");
else
{
// Toggling the user to declare the actual
// winner
if (whoseTurn == COMPUTER)
whoseTurn = HUMAN;
else if (whoseTurn == HUMAN)
whoseTurn = COMPUTER;

// Declare the winner

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 76
 DATA STRUCTURES DEPT. OF CSE

declareWinner(whoseTurn);
}
return;
}

// Driver program
int main()
{
// Let us play the game with COMPUTER starting first
playTicTacToe(COMPUTER);

return (0);
}
Run on IDE
Output:
Tic-Tac-Toe

Choose a cell numbered from 1 to 9 as below and play

1|2 |3
--------------
4|5 |6
--------------
7|8 |9

- - - - - - - - - -

COMPUTER has put a O in cell 6

| |
--------------
| |O
--------------
| |

HUMAN has put a X in cell 7

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 77
 DATA STRUCTURES DEPT. OF CSE

| |
--------------
| |O
--------------
X| |

COMPUTER has put a O in cell 5

| |
--------------
|O |O
--------------
X| |

HUMAN has put a X in cell 1

X| |
--------------
|O |O
--------------
X| |

COMPUTER has put a O in cell 9

X| |
--------------
|O |O
--------------
X| |O

HUMAN has put a X in cell 8

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 78
 DATA STRUCTURES DEPT. OF CSE

X| |
--------------
|O |O
--------------
X|X |O

COMPUTER has put a O in cell 4

X| |
--------------
O|O |O
--------------
X|X |O

COMPUTER has won

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 79
 DATA STRUCTURES DEPT. OF CSE

Program Statement:
14. Write a program to search a word in a given file and display all the positions.

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

int main(int argc, char const *argv[])

{
int num =0;
char word[2000];
char *string;

FILE *in_file = fopen("[Link]", "r");

if (in_file == NULL)
{
printf("Error file missing\n");
exit(-1);
}
Printf(“Enter the word to be searched\n”);
scanf("%s",word);

printf("%s\n", word);

while(!feof(in_file))
{
fscanf(in_file,"%s",string);
if(!strcmp(string,word))
num++;
}
printf(" the word %s found in the file %d times\n",word,num );
return 0;
}
Output:
[Link] file

All that glitters is not gold. Is she wearing gold.

Enter the word to be searched
gold
the word gold found in the file 2 times.

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 80
 DATA STRUCTURES DEPT. OF CSE

Program Statement:

15. Write a program to perform operations creation, insertion, deletion and traversing on a
binary search tree.

Program:

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

#define NULL 0
/* class is created for the implementation of
BST */ struct node
{
int info;
struct node
*lchild; struct
node *rchild;
};
typedef struct node *NODE;

struct node *root;

/* public functions declarations */

void find(int,NODE *,NODE

*); void
case_a(NODE,NODE); void
case_b(NODE,NODE); void
insert(int);
void del(int);
void
preorder(NODE);
void inorder(NODE);
void
postorder(NODE);
void
display(NODE,int);

/* function to find the item form the tree

*/ void find(int item,NODE *par,NODE

*loc)
{
NODE ptr,ptrsave;
Annamacharya Institute of Technology and Page
Sciences ,Kadapa 81
 DATA STRUCTURES DEPT. OF CSE

if(root==NULL) /* tree empty */

{
*loc=NULL;
*par=NUL
L; return;
}
if(item==root->info) /* item is at root */

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 82
 DATA STRUCTURES DEPT. OF CSE

{
*loc=root;
*par=NUL
L; return;
}
if(item<root->info) /* initialize ptr and ptrsave */
{
ptr=root->lchild;
}
else
{
ptr=root->rchild;
}
ptrsave=root;

while(ptr!=NULL)
{
if(item==ptr->info)
{
*loc=ptr;
*par=ptrsav
e; return;
}
ptrsave=ptr;
if(item<ptr-
>info)
{
ptr=ptr->lchild;
}
else
{
ptr=ptr->rchild;
}
} /* end of while */

*loc=NULL; /* item not found */

*par=ptrsave;

} /* end of find() */

void case_a(NODE par,NODE loc)

{
if(par==NULL) /* item to be deleted is root node */
{
root=NULL;
}
else
{
if(loc==par->lchild)
{
par->lchild=NULL;

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 83
 DATA STRUCTURES DEPT. OF CSE

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 84
 DATA STRUCTURES DEPT. OF CSE

else
{
par->rchild=NULL;
}
}
} /* end of cse_a() */

void case_b(NODE par,NODE loc)

{
NODE child;

/* initialize child */

if(loc->lchild!=NULL) /*item to be deleted has lchild */

{
child=loc->lchild;
}
else /* item to be deleted has rchild */
{
child=loc->rchild;
}
if(par==NULL)/* item to be deleted is root node */
{
root=child;
}

else
{
if(loc==par->lchild) /* item is lchild of its parent */
{
par->lchild=child;
}
else /* item is rchild of its parent */
{
par->rchild=child;
}
}
} /* end of case_b() */

/* this function will insert an element to the

tree */ void insert(int item)

{
NODE tmp,parent,location;

find(item,&parent,&location);
if(location!=NULL)
{
printf("\n\t Item already
present"); return;
}
/* crearting new node to insert */

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 85
 DATA STRUCTURES DEPT. OF CSE

tmp=(NODE)new(struct
node); tmp->info=item;
tmp-
>lchild=NULL;
tmp-
>rchild=NULL;
if(parent==NUL
L)
{
root=tmp;
}
else
{
if(item<parent->info)
{
parent->lchild=tmp;
}
else
{
parent->rchild=tmp;
}
}
} /* end of insert() */

/* function to delete a node

*/ void del(int item)

{
NODE parent,location;
if(root==NULL)
{
printf("\n\t Tree is empty");
return;
}
find(item,&parent,&location);
if(location==NULL)
{
printf("\n Item not present in
tree"); return;
}
if(location->lchild==NULL && location->rchild==NULL)
{
case_a(parent,location);
}
if(location->lchild!=NULL && location->rchild==NULL)
{
case_b(parent,location);
}
if(location->lchild==NULL && location->rchild!=NULL)
{
case_b(parent,location);
}
delete(location);
Annamacharya Institute of Technology and Page
Sciences ,Kadapa 86
 DATA STRUCTURES DEPT. OF CSE

}/* end of del() */

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 87
 DATA STRUCTURES DEPT. OF CSE

/* function to traverse in a preorder

fashion */ void preorder(NODE ptr)
{
if(root==NULL)
{
printf("\n\t Tree is empty");
return;
}
if(ptr!=NULL)
{
printf("%d\t",ptr-
>info); preorder(ptr-
>lchild);
preorder(ptr-
>rchild);
}
} /* end of preorder() */
/* function or inorder traversal */

void inorder(NODE ptr)

{
if(root==NULL)
{
printf("\n\t Tree is empty");
return;
}
if(ptr!=NULL)
{
inorder(ptr->lchild);
printf("%d\t",ptr-
>info); inorder(ptr-
>rchild);
}
} /* end of inorder() */

/* this function will travel in a postorder

fashion */ void postorder(NODE ptr)

{
if(root==NULL)
{
printf("\n\t Tree is empty");
return;
}
if(ptr!=NULL)
{
postorder(ptr-
>lchild);
postorder(ptr-
>rchild); printf("%d\
t",ptr->info);
Annamacharya Institute of Technology and Page
Sciences ,Kadapa 88
 DATA STRUCTURES DEPT. OF CSE

}
} /* end of postorder() */

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 89
 DATA STRUCTURES DEPT. OF CSE

/* function to display all the nodes of the tree */

void display(NODE ptr,int level)

{
int i;
if(root==NULL)
{
printf("\n\t Tree is empty");
}

if(ptr!=NULL)
{
display(ptr-
>rchild,level+1);
printf("\n");
for(i=0;i<level;i++)
{
printf(" ");
}
printf("%d\t",ptr->info);
display(ptr-
>lchild,level+1);
}
} /* end of display() */

void main()
{
int ch,n;
root=NUL
L; clrscr();
while(1)
{
printf("\n Menu");
printf("\n
[Link]");
printf("\n
[Link]");
printf("\n [Link] traversal");
printf("\n [Link] traversal");
printf("\n [Link]
traversal"); printf("\n
[Link]");
printf("\n [Link]");

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

scanf("%d",&ch);

switch(ch)
{
case 1:
printf("\n Enter the number to be
Annamacharya Institute of Technology and Page
Sciences ,Kadapa 90
 DATA STRUCTURES DEPT. OF CSE

inserted:"); scanf("%d",&n);
insert(n);
break;
case 2:

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 91
 DATA STRUCTURES DEPT. OF CSE

printf("\n Enter the number to be

deleted:"); scanf("%d",&n);
del(n)
;
break
;

case 3:
preorder(root);
break;
case 4:
inorder(root);
break;
case 5:
postorder(root);
break;
case 6:
display(root,1);
break;
case 7:
exit(0)
; default:
printf("\n wrong choice");
}
}

Output:

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 92
 DATA STRUCTURES DEPT. OF CSE

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 93
 DATA STRUCTURES DEPT. OF CSE

Program Statement:

16 Write a program to implement breadth first search on graphs

Program:

#include<stdio.h>
#include<conio.h>

char delet();
void
insert(char);
void bfs();

char queue[20],g[20],x;
int a[20][20],m,n,i,j,state[20],front=0,rear=-1;

void main()
{
clrscr();
printf("\n\t Enter number of nodes of
graph:"); scanf("%d",&n);
printf("\n\t Enter the nodes of graph (In alphabets):");
for(i=1;i<=n;i++)
{
scanf("%c",&g[i]);
}
printf("\n Instructions \n press 1 if edge exists otherwise press 0 \n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%c to %c",g[i],g[j]);
scanf("%d",&a[i][j]);
}
}
printf("\n the order of visiting the nodes:");
for(i=1;i<=n;i++)
{
state[i]=1;
}
state[1]=2;
insert(g[1]);
bfs();
getch();
}

void bfs()
{
x=delet();
Annamacharya Institute of Technology and Page
Sciences ,Kadapa 94
 DATA STRUCTURES DEPT. OF CSE

for(i=1;i<=n;i++)
{
if(g[i]==x)
{
break;
}
}
state[i]=3;
printf("%c",g[i
]);

for(j=1;j<=n;j++)
{
if(a[i][j]== 1 && state[j] ==1)
{
state[j]=2
;
insert(g[j]
);
}
}
if(front<=rear)
{
bfs();
}
}

void insert(char x)
{
rear++;
queue[rear]
=x;
}
char delet()
{
char x;
x=queue[front]
; front++;
return(x);
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 95
 DATA STRUCTURES DEPT. OF CSE

Output:

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 96
 DATA STRUCTURES DEPT. OF CSE

Program statement

[Link] a program to implement dfs on graphs

#include<stdio.h>
void DFS(int);
int G[10][10],visited[10],n;
void main()
{
int i,j;
printf("Enter number of vertices:");
scanf("%d",&n);
printf("\nEnter adjecency matrix of the graph:");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
for(i=0;i<n;i++)
visited[i]=0;
printf(dfs order is :”);
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);
}

Output:

Enter number of vertices 4

Enter adjancency matrix 0110
1011
1000
0100

Dfs order is : 0 13 2

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 97
 DATA STRUCTURES DEPT. OF CSE

Program statement:

18 Write a program to sort the numbers using merge sort

Program:

#include<stdio.h>
#include<conio.h>

/* function prototypes */

void mergesort(int a[],int l,int u);

void merge(int a[],int l,int mid,int u);

main()
{
int a[20],n,i;
clrscr();
printf("\n enter how many elements you want to sort(max.20):");

scanf("%d",&n); /* read number of elements in the list */

printf("\n enter the %d elements",n);

for(i=0;i<n;i++)
{
printf("\n enter the value for a[%d]:",i);
scanf("%d",&a[i]); /* read the values */
}

printf("\n before sorting, the elements are:");

for(i=0;i<n;i++)
{
printf("%d\t",a[i]); /* print unsorted list */
}

mergesort(a,0,n-1); /* function call

*/ printf("\n after sorting, the elements are:");

for(i=0;i<n;i++)
{
printf("%d\t",a[i]); /* print sorted list */
}

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 98
 DATA STRUCTURES DEPT. OF CSE

getch();
}

void mergesort(int a[],int l,int u) /* function definition */

{
int mid;
if(l<u)
{
mid=(l+u)/2;
mergesort(a,l,mid);
mergesort(a,mid+1,u);
merge(a,l,mid,u);
}
}

void merge(int a[],int l,int mid,int u)

{
int i=l,j=mid+1,k=0,b[50];
while(i<=mid && j<=u)
{
if(a[i]<=a[j])
{
b[k]=a[i];
k=k+1,i=i+1;
}
else
{
b[k]=a[j];
k=k+1,j=j+1;
}
}
while(i<=mid)
{
b[k]=a[i];
k=k+1,i=i+1;
}
while(j<=u)
{
b[k]=a[j];
k=k+1,j=j+1;
}
for(k=0;k<=u-l;k++)
{
a[k+l]=b[k];

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 99
 DATA STRUCTURES DEPT. OF CSE

}
}

Input:

Output:

Annamacharya Institute of Technology and Page

Sciences ,Kadapa 100
 DATA STRUCTURES DEPT. OF CSE

program Statement:

19. Write a Program to perform different operations on B Tress

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

#define MAX 4
#define MIN 2

struct btreeNode {
int val[MAX + 1], count;
struct btreeNode *link[MAX + 1];
};

struct btreeNode *root;

/* creating new node */

struct btreeNode * createNode(int val, struct btreeNode *child) {
struct btreeNode *newNode;
newNode = (struct btreeNode *)malloc(sizeof(struct btreeNode));
newNode->val[1] = val;
newNode->count = 1;
newNode->link[0] = root;
newNode->link[1] = child;
return newNode;
}

/* Places the value in appropriate position */

void addValToNode(int val, int pos, struct btreeNode *node,
struct btreeNode *child) {
int j = node->count;
while (j > pos) {
node->val[j + 1] = node->val[j];
node->link[j + 1] = node->link[j];
j--;
}
node->val[j + 1] = val;
node->link[j + 1] = child;
node->count++;
}

/* split the node */

void splitNode (int val, int *pval, int pos, struct btreeNode *node,
struct btreeNode *child, struct btreeNode **newNode) {
int median, j;

if (pos > MIN)

Annamacharya Institute of Technology and Page 101
Sciences ,Kadapa
 DATA STRUCTURES DEPT. OF CSE

median = MIN + 1;
else
median = MIN;

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

j = median + 1;
while (j <= MAX) {
(*newNode)->val[j - median] = node->val[j];
(*newNode)->link[j - median] = node->link[j];
j++;
}
node->count = median;
(*newNode)->count = MAX - median;

if (pos <= MIN) {

addValToNode(val, pos, node, child);
} else {
addValToNode(val, pos - median, *newNode, child);
}
*pval = node->val[node->count];
(*newNode)->link[0] = node->link[node->count];
node->count--;
}

/* sets the value val in the node */

int setValueInNode(int val, int *pval,
struct btreeNode *node, struct btreeNode **child) {

int pos;
if (!node) {
*pval = val;
*child = NULL;
return 1;
}

if (val < node->val[1]) {

pos = 0;
} else {
for (pos = node->count;
(val < node->val[pos] && pos > 1); pos--);
if (val == node->val[pos]) {
printf("Duplicates not allowed\n");
return 0;
}
}
if (setValueInNode(val, pval, node->link[pos], child)) {
if (node->count < MAX) {
addValToNode(*pval, pos, node, *child);
} else {
splitNode(*pval, pval, pos, node, *child, child);

Annamacharya Institute of Technology and Page 102

Sciences ,Kadapa
 DATA STRUCTURES DEPT. OF CSE

return 1;
}
}
return 0;
}

/* insert val in B-Tree */

void insertion(int val) {
int flag, i;
struct btreeNode *child;

flag = setValueInNode(val, &i, root, &child);

if (flag)
root = createNode(i, child);
}

/* copy successor for the value to be deleted */

void copySuccessor(struct btreeNode *myNode, int pos) {
struct btreeNode *dummy;
dummy = myNode->link[pos];

for (;dummy->link[0] != NULL;)

dummy = dummy->link[0];
myNode->val[pos] = dummy->val[1];

/* removes the value from the given node and rearrange values */
void removeVal(struct btreeNode *myNode, int pos) {
int i = pos + 1;
while (i <= myNode->count) {
myNode->val[i - 1] = myNode->val[i];
myNode->link[i - 1] = myNode->link[i];
i++;
}
myNode->count--;
}

/* shifts value from parent to right child */

void doRightShift(struct btreeNode *myNode, int pos) {
struct btreeNode *x = myNode->link[pos];
int j = x->count;

while (j > 0) {
x->val[j + 1] = x->val[j];
x->link[j + 1] = x->link[j];
}
x->val[1] = myNode->val[pos];
x->link[1] = x->link[0];
x->count++;

Annamacharya Institute of Technology and Page 103

Sciences ,Kadapa
 DATA STRUCTURES DEPT. OF CSE

x = myNode->link[pos - 1];
myNode->val[pos] = x->val[x->count];
myNode->link[pos] = x->link[x->count];
x->count--;
return;
}

/* shifts value from parent to left child */

void doLeftShift(struct btreeNode *myNode, int pos) {
int j = 1;
struct btreeNode *x = myNode->link[pos - 1];

x->count++;
x->val[x->count] = myNode->val[pos];
x->link[x->count] = myNode->link[pos]->link[0];

x = myNode->link[pos];
myNode->val[pos] = x->val[1];
x->link[0] = x->link[1];
x->count--;

while (j <= x->count) {

x->val[j] = x->val[j + 1];
x->link[j] = x->link[j + 1];
j++;
}
return;
}

/* merge nodes */
void mergeNodes(struct btreeNode *myNode, int pos) {
int j = 1;
struct btreeNode *x1 = myNode->link[pos], *x2 = myNode->link[pos - 1];

x2->count++;
x2->val[x2->count] = myNode->val[pos];
x2->link[x2->count] = myNode->link[0];

while (j <= x1->count) {

x2->count++;
x2->val[x2->count] = x1->val[j];
x2->link[x2->count] = x1->link[j];
j++;
}

j = pos;
while (j < myNode->count) {
myNode->val[j] = myNode->val[j + 1];
myNode->link[j] = myNode->link[j + 1];

Annamacharya Institute of Technology and Page 104

Sciences ,Kadapa
 DATA STRUCTURES DEPT. OF CSE

j++;
}
myNode->count--;
free(x1);
}

/* adjusts the given node */

void adjustNode(struct btreeNode *myNode, int pos) {
if (!pos) {
if (myNode->link[1]->count > MIN) {
doLeftShift(myNode, 1);
} else {
mergeNodes(myNode, 1);
}
} else {
if (myNode->count != pos) {
if(myNode->link[pos - 1]->count > MIN) {
doRightShift(myNode, pos);
} else {
if (myNode->link[pos + 1]->count > MIN) {
doLeftShift(myNode, pos + 1);
} else {
mergeNodes(myNode, pos);
}
}
} else {
if (myNode->link[pos - 1]->count > MIN)
doRightShift(myNode, pos);
else
mergeNodes(myNode, pos);
}
}
}

/* delete val from the node */

int delValFromNode(int val, struct btreeNode *myNode) {
int pos, flag = 0;
if (myNode) {
if (val < myNode->val[1]) {
pos = 0;
flag = 0;
} else {
for (pos = myNode->count;
(val < myNode->val[pos] && pos > 1); pos--);
if (val == myNode->val[pos]) {
flag = 1;
} else {
flag = 0;
}
}

Annamacharya Institute of Technology and Page 105

Sciences ,Kadapa
 DATA STRUCTURES DEPT. OF CSE

if (flag) {
if (myNode->link[pos - 1]) {
copySuccessor(myNode, pos);
flag = delValFromNode(myNode->val[pos], myNode->link[pos]);
if (flag == 0) {
printf("Given data is not present in B-Tree\n");
}
} else {
removeVal(myNode, pos);
}
} else {
flag = delValFromNode(val, myNode->link[pos]);
}
if (myNode->link[pos]) {
if (myNode->link[pos]->count < MIN)
adjustNode(myNode, pos);
}
}
return flag;
}

/* delete val from B-tree */

void deletion(int val, struct btreeNode *myNode) {
struct btreeNode *tmp;
if (!delValFromNode(val, myNode)) {
printf("Given value is not present in B-Tree\n");
return;
} else {
if (myNode->count == 0) {
tmp = myNode;
myNode = myNode->link[0];
free(tmp);
}
}
root = myNode;
return;
}

/* search val in B-Tree */

void searching(int val, int *pos, struct btreeNode *myNode) {
if (!myNode) {
return;
}

if (val < myNode->val[1]) {

*pos = 0;
} else {
for (*pos = myNode->count;
(val < myNode->val[*pos] && *pos > 1); (*pos)--);
if (val == myNode->val[*pos]) {

Annamacharya Institute of Technology and Page 106

Sciences ,Kadapa
 DATA STRUCTURES DEPT. OF CSE

printf("Given data %d is present in B-Tree", val);

return;
}
}
searching(val, pos, myNode->link[*pos]);
return;
}

/* B-Tree Traversal */
void traversal(struct btreeNode *myNode) {
int i;
if (myNode) {
for (i = 0; i < myNode->count; i++) {
traversal(myNode->link[i]);
printf("%d ", myNode->val[i + 1]);
}
traversal(myNode->link[i]);
}
}

int main() {
int val, ch;
while (1) {
printf("1. Insertion\t2. Deletion\n");
printf("3. Searching\t4. Traversal\n");
printf("5. Exit\nEnter your choice:");
scanf("%d", &ch);
switch (ch) {
case 1:
printf("Enter your input:");
scanf("%d", &val);
insertion(val);
break;
case 2:
printf("Enter the element to delete:");
scanf("%d", &val);
deletion(val, root);
break;
case 3:
printf("Enter the element to search:");
scanf("%d", &val);
searching(val, &ch, root);
break;
case 4:
traversal(root);
break;
case 5:
exit(0);
default:
printf("U have entered wrong option!!\n");

Annamacharya Institute of Technology and Page 107

Sciences ,Kadapa
 DATA STRUCTURES DEPT. OF CSE

break;
}
printf("\n");
}
}

Output:

1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:1
Enter your input:70

1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:1
Enter your input:17

1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:1
Enter your input:67

1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:1
Enter your input:89

1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:4
17 67 70 89

1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:3
Enter the element to search:70
Given data 70 is present in B-Tree

1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:2

Annamacharya Institute of Technology and Page 108

Sciences ,Kadapa
 DATA STRUCTURES DEPT. OF CSE

Enter the element to delete:17

1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:4
67 70 89

1. Insertion 2. Deletion
3. Searching 4. Traversal
5. Exit
Enter your choice:5

Annamacharya Institute of Technology and Page 109

Sciences ,Kadapa