DATA STRUCTURE (3330704)

ATUL POLYTECHNIC KHADAT

COMPUTER DEPARTMENT

DATA STRUCTURE (3330704)

PROGRAM MANUAL

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 1
 DATA STRUCTURE (3330704)

PROGRAM FOR LINER SEARCH.

#include<stdio.h>
#include<conio.h>
void main()
{
int a[20],n,i,item;
clrscr();
printf("how many elements you want to enter in array::");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("enter element %d:",i+1);
scanf("%d",&a[i]);
}
printf("enter elememt to be searched ::");
scanf("%d",&item);
for(i=0;i<n;i++)
{
if(item==a[i])
{
printf("%d found at position %d \n",item,i+1);
break;
}
}
if(i==n)
printf("item %d not found in array \n",item);
getch();

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 2
 DATA STRUCTURE (3330704)

PROGRAM FOR BINARY SEARCH.

#include<stdio.h>
#include<conio.h>
void main()
{
int a[20],low,high,mid,n,i,item;
clrscr();
printf("how many elements you want to enter in array: ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("enter element %d:",i+1);
scanf("%d",&a[i]);
}
printf("enter elememt to be searched ::");
scanf("%d",&item);

low=0;
high=n-1;
mid = (low+high)/2;

while(item!=a[mid] && low<=high)

{
if(item>a[mid])
low=mid+1;
else
high=mid-1;
mid = (low+high)/2;

}
if(item == a[mid])
printf("%d found at position %d: \n",item,mid+1);

if(low>high)
printf("item %d not found in array \n",item);
getch();

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 3
 DATA STRUCTURE (3330704)

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 4
 DATA STRUCTURE (3330704)

PROGRAM FOR FIND OUT STRING LENGTH.

#include<stdio.h>
#include<conio.h>
void main()
{
int len=0;
char s[10];
clrscr();
printf("enter string:");
gets(s);
while(s[len]!='\0')
{
len++;
}
printf("length: %d",len );
getch();
}

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 5
 DATA STRUCTURE (3330704)

PROGRAM FOR STRING COPY.

#include<stdio.h>
#include<conio.h>
void main()
{
char source[10],dest[10];
int len=0,i;
clrscr();
printf("enter source string:");
gets(source);
while(source[len]!='\0')
len++;
for(i=0;i<=len;i++)
{
dest[i]=source[i];
}
printf("Destination string : %s",dest);
getch();
}

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 6
 DATA STRUCTURE (3330704)

PROGRAM FOR STRING CONCAT.

/*program for concat two string.*/

#include<stdio.h>
#include<conio.h>
void main()
{
char s1[50],s2[50];
int len1=0,len2=0,i,j;
clrscr();
printf("enter first string:");
gets(s1);
printf("enter second string:");
gets(s2);
while(s1[len1]!='\0')
{
len1++;
}
while(s2[len2]!='\0')
{
len2++;
}
for(j=0,i=len1;j<=len2;++i,j++)
{
s1[i]=s2[j];
}
printf("Concat string is : %s",s1);
getch();
}

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 7
 DATA STRUCTURE (3330704)

PROGRAM FOR SUBSTRING.

#include<stdio.h>
#include<conio.h>
void main()
{
char s1[60],s2[60];
int i=0,pos,len;
clrscr();
printf("enter string:");
gets(s1);

printf("Enter the pos:");

scanf("%d",&pos);

printf("Enter the length:");

scanf("%d",&len);

while(i<len)
{
s2[i]=s1[pos+i-1];
i++;
}
s2[i]='\0';
printf("substring is : %s",s2);
getch();
}

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 8
 DATA STRUCTURE (3330704)

PROGRAM FOR COMPARE TWO STRING.

#include<stdio.h>
#include<conio.h>
void main()
{
char s1[50],s2[50];
int len1=0,len2=0,i,flag;
clrscr();
printf("enter first string:");
gets(s1);
printf("enter second string:");
gets(s2);
while(s1[len1]!='\0')
{
len1++;
}
while(s2[len2]!='\0')
{
len2++;
}
if(len1!=len2)
{
printf("Not equal");
}
else
{
flag=0;
for(i=0;i<=len1;++i)
{
if(s1[i]!=s2[i])
{
flag=1;
break;
}
}
if(flag==1){ printf("Not equal"); }
else { printf("Equal"); }
}
getch();
}

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 9
 DATA STRUCTURE (3330704)

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 10
 DATA STRUCTURE (3330704)

PROGRAM FOR INSERT STRING.

#include<stdio.h>
#include<conio.h>
void main()
{
char s1[60],s2[30],final[90];
int len1=0,len2=0,i,j,pos;
clrscr();
printf("enter string:");
gets(s1);
while(s1[len1]!='\0')
{
len1++;
}
printf("Enter the word to be inserted:");
gets(s2);
while(s2[len2]!='\0')
{
len2++;
}

printf("enter position from where you want to insert:");

scanf("%d",&pos);

for(i=0;i<pos;++i)
final[i]=s1[i];

for(i=pos,j=0;j<len2;++j,++i)
final[i]=s2[j];

for(i=len2+pos,j=pos;j<len1;++i,++j)
final[i]=s1[j];

final[len1+len2]= '\0';
printf("New string is : %s",final);

getch();
}

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 11
 DATA STRUCTURE (3330704)

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 12
 DATA STRUCTURE (3330704)

PROGRAM FOR DELETE STRING.

#include<stdio.h>
#include<conio.h>
void del(char *x,int a,int b);
void main()
{
char s1[60];
int pos,len;
clrscr();
printf("enter string:");
gets(s1);

printf("Enter the pos:");

scanf("%d",&pos);

printf("Enter the length:");

scanf("%d",&len);

del(s1,len,pos);
getch();
}

void del(char *x,int a,int b)

{
if((a+b-1) <= strlen(x))
{
strcpy(&x[b-1],&x[a+b-1]);
puts(x);
}

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 13
 DATA STRUCTURE (3330704)

PROGRAM FOR APPEND STRING.

/*program for append string.*/

#include<stdio.h>
#include<conio.h>
void main()
{
char s1[50],s2[50];
int len1=0,len2=0,i,j;
clrscr();
printf("enter first string:");
gets(s1);
printf("enter second string:");
gets(s2);
while(s1[len1]!='\0')
{
len1++;
}
while(s2[len2]!='\0')
{
len2++;
}
for(j=0,i=len1;j<=len2;++i,j++)
{
s1[i]=s2[j];
}
printf("first string after append : %s",s1);
getch();
}

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 14
 DATA STRUCTURE (3330704)

PROGRAM FOR REVERSE STRING.

#include<stdio.h>
#include<conio.h>
void main()
{
int len=0,i,j;
char s1[10],s2[10];
clrscr();
printf("enter string:");
gets(s1);
while(s1[len]!='\0')
{
len++;
}
for(i=0,j=len-1;i<len;++i,--j)
{
s2[j]=s1[i];
}
s2[len] = '\0';
printf("Reverse string: %s",s2 );
getch();
}

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 15
 DATA STRUCTURE (3330704)

PROGRAM FOR CONVERT LOWER CASE STRING INTO UPPER CASE

STRING.

/*program for convert string into UPPER CASE.*/

#include<stdio.h>
#include<conio.h>
void main()
{
int i=0;
char s1[10],s2[10];
clrscr();
printf("enter string:");
gets(s1);
while(s1[i]!='\0')
{
if(s1[i]>=97 && s1[i]<=122)
{
s2[i]=s1[i]-32;
}
else
{
s2[i]=s1[i];
}
i++;
}

s2[i] = '\0';
printf("Upper case string: %s",s2 );
getch();
}

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 16
 DATA STRUCTURE (3330704)

PROGRAM FOR CONVERT UPPER CASE STRING INTO LOWER CASE

STRING.

/*program for convert string into LOWER CASE.*/

#include<stdio.h>
#include<conio.h>
void main()
{
int i=0;
char s1[10],s2[10];
clrscr();
printf("enter uppercase letter string:");
gets(s1);
while(s1[i]!='\0')
{
if(s1[i]>=65 && s1[i]<=90)
{
s2[i]=s1[i]+32;
}
else
{
s2[i]=s1[i];
}
i++;
}

s2[i] = '\0';
printf("Lower case string: %s",s2 );
getch();
}

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 17
 DATA STRUCTURE (3330704)

Implement PUSH & POP algorithm for STACK using ARRAY

#include<stdio.h>
#include<conio.h>
#define size 5
int TOP = -1;
int stack[size];
void push();
void pop();
void display();

void main()
{
int choice;
clrscr();
while(1)
{
printf("1. PUSH \n");
printf("2. POP \n");
printf("3. DISPLAY \n");
printf("4. QUIT \n");
printf("ENTER YOUR CHOICE \n");
scanf("%d",&choice);

switch(choice)
{

case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("wrong choice\n");
}
}

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 18
 DATA STRUCTURE (3330704)

void push()
{
int x;
if(TOP==(size-1))
printf("stack overflow\n");
else
{
printf("enter element to be pushed in stack:");
scanf("%d",&x);
TOP=TOP+1;
stack[TOP]=x;
}
}

void pop()
{
if(TOP == -1)
printf("stack underflow\n");
else
{
printf("popped element is %d\n",stack[TOP]);
TOP=TOP-1;
}
}

void display()
{
int i;
if(TOP == -1)
printf("stack empty\n");
else
{
printf("stack elements:\n");
for(i=TOP;i>=0;i--)
printf("%d\n",stack[i]);
}
}

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 19
 DATA STRUCTURE (3330704)

OUTPUT

PUSH(INSERT) ELEMENT IN STACK

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 20
 DATA STRUCTURE (3330704)

DISPLAY ELEMENTS IN STACK

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 21
 DATA STRUCTURE (3330704)

POP(DELETE) ELEMENT IN STACK

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 22
 DATA STRUCTURE (3330704)

Implement PUSH & POP algorithm for QUEUE using ARRAY

#include<stdio.h>
#include<conio.h>
#define size 5
int REAR = -1;
int FRONT = -1;
int queue[size];
void push();
void pop();
void display();

void main()
{
int choice;
clrscr();
while(1)
{
printf("\n\n*****PROGRAM FOR SIMPLE QUEUE USING ARRAY*****\n");
printf("1. PUSH \n");
printf("2. POP \n");
printf("3. DISPLAY \n");
printf("4. QUIT \n");
printf("ENTER YOUR CHOICE \n");
scanf("%d",&choice);

switch(choice)
{

case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("wrong choice\n");
}

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 23
 DATA STRUCTURE (3330704)

void push()
{
int x;
if(REAR==(size-1))
printf("Queue overflow\n");
else
{
if(FRONT==-1)
FRONT=0;
printf("Input element for adding in Queue:");
scanf("%d",&x);
REAR=REAR+1;
queue[REAR]=x;
}
}

void pop()
{
if(FRONT == -1 || FRONT>REAR)
printf("QUEUE underflow\n");
else
{
printf("Element deleted from QUEUE is %d\n",queue[FRONT]);
FRONT=FRONT+1;
}
}

void display()
{
int i;
if(FRONT == -1)
printf("QUEUE empty\n");
else
{
printf("******QUEUE ELEMENTS ARE******\n");
for(i=FRONT;i<=REAR;i++)
printf("%d\n",queue[i]);
}
}

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 24
 DATA STRUCTURE (3330704)

OUTPUT

PUSH(INSERT) ELEMENT IN QUEUE

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 25
 DATA STRUCTURE (3330704)

DISPLAY ELEMENT IN QUEUE

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 26
 DATA STRUCTURE (3330704)

POP(DELETE) ELEMENT IN QUEUE

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 27
 DATA STRUCTURE (3330704)

Implement PUSH & POP algorithm for CIRCULAR QUEUE using ARRAY
#include<stdio.h>
#include<conio.h>
#define size 5
int REAR = -1;
int FRONT = -1;
int cqueue[size];
void push();
void pop();
void display();

void main()
{
int choice;
clrscr();
while(1)
{
printf("\n\n*****PROGRAM FOR CIRCULAR QUEUE USING ARRAY*****\n");
printf("1. PUSH \n");
printf("2. POP \n");
printf("3. DISPLAY \n");
printf("4. QUIT \n");
printf("ENTER YOUR CHOICE \n");
scanf("%d",&choice);

switch(choice)
{

case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("wrong choice\n");
}
}

}
PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)
C.T.BELANI Page 28
 DATA STRUCTURE (3330704)

void push()
{
int x;

if((FRONT==0 && REAR== size-1) || (FRONT==REAR+1))

printf("Queue overflow\n");

if(FRONT==-1)
{
FRONT=0;
REAR=0;
}
else
{
if(REAR==size-1)
REAR=0;
else
REAR=REAR+1;
}
printf("Input element for adding in Circular Queue:");
scanf("%d",&x);
cqueue[REAR]=x;
}

void pop()
{
if(FRONT == -1)
printf("QUEUE underflow\n");
printf("Element deleted from CIRCULAR QUEUE is %d\n",cqueue[FRONT]);

if(FRONT==REAR)
{
FRONT= -1;
REAR = -1;
}
else
{
if(FRONT==size-1)
FRONT=0;
else
FRONT=FRONT+1;
}
}
PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)
C.T.BELANI Page 29
 DATA STRUCTURE (3330704)

void display()
{
int front_pos=FRONT,rear_pos=REAR;
if(FRONT == -1)
printf("QUEUE empty\n");

printf("******CIRCULAR QUEUE ELEMENTS ARE******\n");

if(front_pos<=rear_pos)
while(front_pos<=rear_pos)
{
printf("%d\n", cqueue[front_pos]);
front_pos++;
}
else
{
while(front_pos<=size-1)
{
printf("%d\n", cqueue[front_pos]);
front_pos++;
}
front_pos=0;
while(front_pos<=rear_pos)
{
printf("%d\n", cqueue[front_pos]);
front_pos++;
}
}
}

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 30
 DATA STRUCTURE (3330704)

OUTPUT

PUSH(INSERT) ELEMENT IN CIRCULAR QUEUE

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 31
 DATA STRUCTURE (3330704)

DISPLAY ELEMENT IN CIRCULAR QUEUE

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 32
 DATA STRUCTURE (3330704)

POP(DELETE) ELEMENT IN CIRCULAR QUEUE

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 33
 DATA STRUCTURE (3330704)

IMPLEMENT RECURSIVE FUNCTION

FACTORIAL

#include<stdio.h>
#include<conio.h>
int fact(int);
void main()
{
int f,n;
clrscr();

printf("enter a number::");
scanf("%d",&n);
f=fact(n);

printf("factorial of %d is %d",n,f);
getch();
}

int fact(int n)
{
int f=1;
if(n==1)
return(f);
f=n*fact(n-1);
return(f);
}

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 34
 DATA STRUCTURE (3330704)

FIBONACI SERIES

#include<stdio.h>
#include<conio.h>
void fib(int,int,int);
void main()
{
int f1=0,f2=1,n;
clrscr();

printf("Enter how many number to generate:");

scanf("%d",&n);

printf(" \n\n***** FIBONACI SERIES ***** \n");

printf("%d\t%d\t",f1,f2);
fib(f1,f2,n-2);
getch();
}

void fib(int f1, int f2,int n)

{

int f3;
f3=f1+f2;
printf("%d\t",f3);
n--;
if(n>0)
fib(f2,f3,n);
}

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 35
 DATA STRUCTURE (3330704)

IMPLEMENT SINGLE LINK LIST (DYNAMIC IMPLEMENTATION)

CREATE NODE
DISPLAY NODE
INSERT AT FIRST POSITION
INSERT AT SPECIFIC POSITION

#include<stdio.h>
#include<malloc.h>
struct node
{
int data;
struct node *link;
}*start;

void create(int);
void display();
void insert_start(int);
void insert_specific(int,int);

void main()
{
int choice,n,m,position,i;
start=NULL;
clrscr();
while(1)
{
printf("\n\n*****PROGRAM FOR SINGLE LINK LIST USING
POINTER*****\n");
printf("1. ENTER 1 FOR CREATE NODE \n");
printf("2. ENTER 2 FOR DISPLAY \n");
printf("3. ENTER 3 FOR INSERT AT FIRST \n");
printf("4. ENTER 4 FOR INSERT AT SPECIFIC POSITION \n");
printf("5. ENTER 5 FOR EXIT\n");
printf("ENTER YOUR CHOICE \n");
scanf("%d",&choice);

switch(choice)
{

case 1:
printf("How many nodes you want:");
scanf("%d",&n);
for(i=0;i<n;i++)
PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)
C.T.BELANI Page 36
 DATA STRUCTURE (3330704)

{
printf("Enter element:");
scanf("%d",&m);
create(m);
}
break;

case 2:
display();
break;

case 3:
printf("Enter element:");
scanf("%d",&m);
insert_start(m);
break;

case 4:
printf("Enter element:");
scanf("%d",&m);
printf("Enter the position after which this elememt is
inserted:");
scanf("%d",&position);
insert_specific(m,position);
break;

case 5:
exit(1);

default:
printf("wrong choice\n");
}
}
}

void create(int inserted_value)

{
struct node *q,*tmp;
tmp=malloc(sizeof(struct node));
tmp->data = inserted_value;
tmp->link=NULL;
if(start==NULL)
start=tmp;
else
PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)
C.T.BELANI Page 37
 DATA STRUCTURE (3330704)

{
q=start;
while(q->link!=NULL)
q=q->link;
q->link=tmp;
}
}

void display()
{
struct node *q;
if(start==NULL)
{
printf("List is empty\n");
return;

}
q=start;
printf("\n**********SINGLE LINK LIST NODES ARE AS FOLLOWS**********\n");
while(q!=NULL)
{
printf( "\n%d",q->data);
q=q->link;
}
}

void insert_start(int inserted_value)

{
struct node *tmp;
tmp= malloc(sizeof(struct node));
tmp->data=inserted_value;
tmp->link=start;
start=tmp;
}

void insert_specific(int inserted_value,int pos)

{
struct node *tmp, *q;
int i;
q=start;
for(i=0;i<pos-1;i++)
{
PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)
C.T.BELANI Page 38
 DATA STRUCTURE (3330704)

q=q->link;
if(q==NULL)
{
printf("There are less than %d elements",pos);
return;
}
}
tmp= malloc(sizeof(struct node));
tmp->link=q->link;
tmp->data=inserted_value;
q->link=tmp;
}

OUTPUT

CREATE NODE

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 39
 DATA STRUCTURE (3330704)

DISPLAY NODE

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 40
 DATA STRUCTURE (3330704)

INSERT AT FIRST POSITION

INSERT AT SPECIFIC POSITION

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 41
 DATA STRUCTURE (3330704)

IMPLEMENT SINGLE LINK LIST (DYNAMIC IMPLEMENTATION)

CREATE NODE
DISPLAY NODE
DELETE NODE
SEARCH NODE

#include<stdio.h>
#include<malloc.h>
struct node
{
int data;
struct node *link;
}*start;

void create(int);
void display();
void del(int);
void search(int);

void main()
{
int choice,n,m,position,i;
start=NULL;
clrscr();
while(1)
{
printf("\n\n*****PROGRAM FOR SINGLE LINK LIST USING
POINTER*****\n");
printf("1. ENTER 1 FOR CREATE NODE \n");
printf("2. ENTER 2 FOR DISPLAY \n");
printf("3. ENTER 3 FOR DELETE \n");
printf("4. ENTER 4 FOR SEARCH \n");
printf("5. ENTER 5 FOR EXIT\n");
printf("ENTER YOUR CHOICE \n");
scanf("%d",&choice);

switch(choice)
{

case 1:
printf("How many nodes you want:");
scanf("%d",&n);
for(i=0;i<n;i++)
PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)
C.T.BELANI Page 42
 DATA STRUCTURE (3330704)

{
printf("Enter element:");
scanf("%d",&m);
create(m);
}
break;

case 2:
display();
break;

case 3:
if(start==NULL)
{
printf("List is empty\n");
continue;
}
printf("Enter the element for deletion:");
scanf("%d",&m);
del(m);
break;

case 4:
printf("Enter the element to be searched:");
scanf("%d",&m);
search(m);
break;

case 5:
exit(1);

default:
printf("wrong choice\n");
}
}
}

void create(int inserted_value)

{
struct node *q,*tmp;
tmp=malloc(sizeof(struct node));
tmp->data = inserted_value;
tmp->link=NULL;
if(start==NULL)
PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)
C.T.BELANI Page 43
 DATA STRUCTURE (3330704)

start=tmp;
else
{
q=start;
while(q->link!=NULL)
q=q->link;
q->link=tmp;
}
}

void display()
{
struct node *q;
if(start==NULL)
{
printf("List is empty\n");
return;

}
q=start;
printf("\n**********SINGLE LINK LIST NODES ARE AS FOLLOWS**********\n");
while(q!=NULL)
{
printf( "\n%d",q->data);
q=q->link;
}
}

void del(int deleted_value)

{
struct node *tmp,*q;
if(start->data == deleted_value)
{
tmp=start;
start=start->link; // first element deleted
free(tmp);
return;
}
q=start;
while(q->link->link != NULL) //elememt deleted in between
{
if(q->link->data == deleted_value)
{
PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)
C.T.BELANI Page 44
 DATA STRUCTURE (3330704)

tmp=q->link;
q->link=tmp->link;
free(tmp);
return;
}
q=q->link;
}

if(q->link->data == deleted_value) //last elememt deleted

{
tmp=q->link;
free(tmp);
q->link=NULL;
return;
}
printf("Element %d not found \n",deleted_value);
}

void search(int search_data)

{
struct node *ptr=start;
int pos=1;
while(ptr!=NULL)
{
if(ptr->data==search_data)
{
printf("Item %d found at position %d\n",search_data,pos);
return;
}
ptr=ptr->link;
pos++;
}
if(ptr == NULL)
printf("Item %d not found in list\n",search_data);
}

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 45
 DATA STRUCTURE (3330704)

OUTPUT

CREATE NODE
DISPLAY NODE

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 46
 DATA STRUCTURE (3330704)

DELETE NODE

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 47
 DATA STRUCTURE (3330704)

SEARCH NODE

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 48
 DATA STRUCTURE (3330704)

IMPLEMENT DOUBLY LINK LIST (DYNAMIC IMPLEMENTATION)

CREATE NODE
DISPLAY NODE
INSERT AT FIRST POSITION
INSERT AT SPECIFIC POSITION

#include<stdio.h>
#include<malloc.h>
struct node
{
struct node *prev;
int data;
struct node *next;
}*start;

void create(int);
void display();
void insert_start(int);
void insert_specific(int,int);

void main()
{
int choice,n,m,position,i;
start=NULL;
clrscr();
while(1)
{
printf("\n\n*****PROGRAM FOR DOUBLY LINK LIST USING
POINTER*****\n");
printf("1. ENTER 1 FOR CREATE NODE \n");
printf("2. ENTER 2 FOR DISPLAY \n");
printf("3. ENTER 3 FOR INSERT AT FIRST \n");
printf("4. ENTER 4 FOR INSERT AT SPECIFIC POSITION \n");
printf("5. ENTER 5 FOR EXIT\n");
printf("ENTER YOUR CHOICE \n");
scanf("%d",&choice);

switch(choice)
{

case 1:
printf("How many nodes you want:");
scanf("%d",&n);
PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)
C.T.BELANI Page 49
 DATA STRUCTURE (3330704)

for(i=0;i<n;i++)
{
printf("Enter element:");
scanf("%d",&m);
create(m);
}
break;

case 2:
display();
break;

case 3:
printf("Enter element:");
scanf("%d",&m);
insert_start(m);
break;

case 4:
printf("Enter element:");
scanf("%d",&m);
printf("Enter the position after which this elememt is
inserted:");
scanf("%d",&position);
insert_specific(m,position);
break;

case 5:
exit(1);

default:
printf("wrong choice\n");
}
}
}

void create(int inserted_value)

{
struct node *q,*tmp;
tmp=malloc(sizeof(struct node));
tmp->data = inserted_value;
tmp->next=NULL;
if(start==NULL)
{
PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)
C.T.BELANI Page 50
 DATA STRUCTURE (3330704)

tmp->prev=NULL;
start->prev=tmp;
start=tmp;
}
else
{
q=start;
while(q->next!=NULL)
q=q->next;
q->next=tmp;
tmp->prev=q;
}
}

void display()
{
struct node *q;
if(start==NULL)
{
printf("List is empty\n");
return;

}
q=start;
printf("\n**********DOUBLY LINK LIST NODES ARE AS FOLLOWS**********\n");
while(q!=NULL)
{
printf( "\n%d",q->data);
q=q->next;
}
}

void insert_start(int inserted_value)

{
struct node *tmp;
tmp= malloc(sizeof(struct node));
tmp->prev=NULL;
tmp->data=inserted_value;
tmp->next=start;
start->prev=tmp;
start=tmp;
}

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 51
 DATA STRUCTURE (3330704)

void insert_specific(int inserted_value,int pos)

{
struct node *tmp, *q;
int i;
q=start;
for(i=0;i<pos-1;i++)
{
q=q->next;
if(q==NULL)
{
printf("There are less than %d elements",pos);
return;
}
}
tmp= malloc(sizeof(struct node));
tmp->data=inserted_value;
q->next->prev=tmp;
tmp->next=q->next;
tmp->prev=q;
q->next=tmp;
}

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 52
 DATA STRUCTURE (3330704)

OUTPUT

CREATE NODE
DISPLAY NODE

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 53
 DATA STRUCTURE (3330704)

INSERT AT FIRST POSITION

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 54
 DATA STRUCTURE (3330704)

INSERT AT SPECIFIC POSITION

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 55
 DATA STRUCTURE (3330704)

IMPLEMENT DOUBLY LINK LIST (DYNAMIC IMPLEMENTATION)

CREATE NODE
DISPLAY NODE
DELETE NODE
COUNT NODE

#include<stdio.h>
#include<malloc.h>

struct node
{
struct node *prev;
int data;
struct node *next;
}*start;

void create(int);
void display();
void del(int);
void count();

void main()
{
int choice,n,m,position,i;
start=NULL;
clrscr();
while(1)
{
printf("\n\n*****PROGRAM FOR DOUBLY LINK LIST USING
POINTER*****\n");
printf("1. ENTER 1 FOR CREATE NODE \n");
printf("2. ENTER 2 FOR DISPLAY \n");
printf("3. ENTER 3 FOR DELETE \n");
printf("4. ENTER 4 FOR COUNT \n");
printf("5. ENTER 5 FOR EXIT\n");
printf("ENTER YOUR CHOICE \n");
scanf("%d",&choice);

switch(choice)
{

case 1:
printf("How many nodes you want:");
scanf("%d",&n);
PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)
C.T.BELANI Page 56
 DATA STRUCTURE (3330704)

for(i=0;i<n;i++)
{
printf("Enter element:");
scanf("%d",&m);
create(m);
}
break;

case 2:
display();
break;

case 3:
printf("Enter element to be deleted:");
scanf("%d",&m);
del(m);
break;

case 4:
count();
break;

case 5:
exit(1);

default:
printf("wrong choice\n");
}
}
}

void create(int inserted_value)

{
struct node *q,*tmp;
tmp=malloc(sizeof(struct node));
tmp->data = inserted_value;
tmp->next=NULL;
if(start==NULL)
{
tmp->prev=NULL;
start->prev=tmp;
start=tmp;
}
PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)
C.T.BELANI Page 57
 DATA STRUCTURE (3330704)

else
{
q=start;
while(q->next!=NULL)
q=q->next;
q->next=tmp;
tmp->prev=q;
}
}

void display()
{
struct node *q;
if(start==NULL)
{
printf("List is empty\n");
return;

}
q=start;
printf("\n**********DOUBLY LINK LIST NODES ARE AS FOLLOWS**********\n");
while(q!=NULL)
{
printf( "\n%d",q->data);
q=q->next;
}
}

void del(int deleted_value)

{
struct node *tmp,*q;
if(start->data == deleted_value)
{
tmp=start;
start=start->next; // first element deleted
free(tmp);
return;
}
q=start;
while(q->next->next != NULL) //elememt deleted in between
{
if(q->next->data == deleted_value)
{
tmp=q->next;
PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)
C.T.BELANI Page 58
 DATA STRUCTURE (3330704)

q->next=tmp->next;
tmp->next->prev=q;
free(tmp);
return;
}
q=q->next;
}

if(q->next->data == deleted_value) //last elememt deleted

{
tmp=q->next;
free(tmp);
q->next=NULL;
return;
}
printf("Element %d not found \n",deleted_value);
}

void count()
{
struct node *q=start;
int cnt=0;
while(q!=NULL)
{
q=q->next;
cnt++;
}
printf("Number of elements are %d\n",cnt);
}

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 59
 DATA STRUCTURE (3330704)

OUTPUT

CREATE NODE
DISPLAY NODE

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 60
 DATA STRUCTURE (3330704)

DELETE NODE

COUNT NODE

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 61
 DATA STRUCTURE (3330704)

IMPLEMENT BUBBLE SORTING

#include<stdio.h>
#include<conio.h>
#define m 20
void main()
{
int a[m],i,j,k,temp,n,exchange;
clrscr();
printf("\n**********BUBBLE SORTING**********");
printf("\n\nEnter the number of elements:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter elements %d:",i+1);
scanf("%d",&a[i]);
}
printf("Unsorted List is: \n");
for(i=0;i<n;i++)
printf("%d\n",a[i]);
printf("\n");

for(i=0;i<n-1;i++)
{
exchange=0;
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;
exchange++;
}
}
}
printf("Sorted List is: \n");
for(i=0;i<n;i++)
printf("%d\n",a[i]);
getch();

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 62
 DATA STRUCTURE (3330704)

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 63
 DATA STRUCTURE (3330704)

IMPLEMENT SELECTION SORTING

#include<stdio.h>
#include<conio.h>
#define m 20
void main()
{
int a[m],i,j,k,temp,n,smallest;
clrscr();
printf("\n**********SELECTION SORTING**********");
printf("\n\nEnter the number of elements:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter elements %d:",i+1);
scanf("%d",&a[i]);
}
printf("Unsorted List is: \n");
for(i=0;i<n;i++)
printf("%d\n",a[i]);
printf("\n");

for(i=0;i<n-1;i++)
{
smallest=i;
for(k=i+1;k<n;k++)
{
if(a[smallest]>a[k])
smallest=k;
}
if(i!=smallest)
{
temp=a[i];
a[i]=a[smallest];
a[smallest]=temp;
}
}
printf("Sorted List is: \n");
for(i=0;i<n;i++)
printf("%d\n",a[i]);
getch();

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 64
 DATA STRUCTURE (3330704)

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 65
 DATA STRUCTURE (3330704)

IMPLEMENT INSERTION SORTING

#include<stdio.h>
#include<conio.h>
#define m 20
void main()
{
int a[m],i,j,k,n;
clrscr();
printf("\n**********INSERTION SORTING**********");
printf("\n\nEnter the number of elements:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter elements %d:",i+1);
scanf("%d",&a[i]);
}
printf("Unsorted List is: \n");
for(i=0;i<n;i++)
printf("%d\n",a[i]);
printf("\n");

for(j=1;j<n;j++)
{
k=a[j];
for(i=j-1;i>=0&&k<a[i];i--)
a[i+1]=a[i];
a[i+1]=k;
}
printf("Sorted List is: \n");
for(i=0;i<n;i++)
printf("%d\n",a[i]);
getch();

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 66
 DATA STRUCTURE (3330704)

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 67
 DATA STRUCTURE (3330704)

IMPLEMENT QUICK SORTING

#include<stdio.h>
#include<conio.h>
#define m 30
void display();
void quick();
enum bool {FALSE,TRUE};
void main()
{
int a[m],i,n;
clrscr();
printf("\n**********QUICK SORTING**********");
printf("\n\nEnter the number of elements:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter elements %d:",i+1);
scanf("%d",&a[i]);
}
printf("Unsorted List is: \n");
display(a,0,n-1);
printf("\n");
quick(a,0,n-1);

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

display(a,0,n-1);
printf("\n");
getch();
}

void quick(int ar[],int low,int up)

{
int piv,temp,left,right;
enum bool pivot_placed = FALSE;
left=low;
right=up;
piv=low;
if(low>=up)
return;
printf("\nSublist :\n");
display(ar,low,up);

while(pivot_placed == FALSE)
PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)
C.T.BELANI Page 68
 DATA STRUCTURE (3330704)

{
while(ar[piv]<=ar[right]&&piv!=right)
right=right-1;
if(piv==right)

pivot_placed == TRUE;
if(ar[piv]>ar[right])
{
temp=ar[piv];
ar[piv]=ar[right];
ar[right]=temp;
piv=right;
}

while(ar[piv]>=ar[left]&&left!=piv)
left=left+1;
if(piv==left)
pivot_placed = TRUE;
if(ar[piv]<ar[left])
{
temp=ar[left];
ar[piv]=ar[left];
ar[left]=temp;
piv=left;
}

printf("\n->Pivot Placed is %d->\n",ar[piv]);

display(ar,low,up);
printf("\n");
quick(ar,low,piv-1);
quick(ar,piv+1,up);
}

void display(int ar[],int low,int up)

{
int i;
for(i=low;i<=up;i++)
printf("%d\n",ar[i]);
}

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 69
 DATA STRUCTURE (3330704)

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 70
 DATA STRUCTURE (3330704)

IMPLEMENT MERGE SORTING

#include<stdio.h>
#include<conio.h>
#define m 30
void main()
{
int a[m],save[m],i,j,k,n,size,l1,l2,h1,h2;
clrscr();
printf("\n**********MERGE SORTING**********");
printf("\n\nEnter the number of elements:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter elements %d:",i+1);
scanf("%d",&a[i]);
}
printf("Unsorted List is: \n");
for(i=0;i<n;i++)
printf("\n%d",a[i]);

for(size=1;size<n;size=size*2)
{
l1=0;
k=0;
while(l1+size<n)
{
h1=l1+size-1;
l2=h1+1;
h2=l2+size-1;
if(h2>=n)
h2=n-1;
i=l1;
j=l2;
while(i<=h1&&j<=h2)
{
if(a[i]<=a[j])
save[k++]=a[i++];
else
save[k++]=a[j++];
}
while(i<=h1)
save[k++]=a[i++];
while(j<=h2)
PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)
C.T.BELANI Page 71
 DATA STRUCTURE (3330704)

save[k++]=a[j++];
l1=h2+1;
}
for(i=l1;k<n;i++)
save[k++]=a[i];
for(i=0;i<n;i++)
a[i]=save[i];
printf("\n\nSize=%d\n \nElements are:",size);
for(i=0;i<n;i++)
printf("\n%d",a[i]);
}

printf("\n \n \nSorted List is: \n");

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

getch();
}

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 72
 DATA STRUCTURE (3330704)

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 73
 DATA STRUCTURE (3330704)

IMPLEMENT SHELL SORTING

#include<stdio.h>
#include<conio.h>
#define m 20
void main()
{
int a[m],i,j,k,n,incre;
clrscr();
printf("\n**********SHELL SORTING**********");
printf("\n\nEnter the number of elements:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter elements %d:",i+1);
scanf("%d",&a[i]);
}
printf("Unsorted List is: \n");
for(i=0;i<n;i++)
printf("%d\n",a[i]);
printf("\n");

printf("Enter maximum increment(odd value):");

scanf("%d",&incre);

while(incre>=1)
{
for(j=incre;j<n;j++)
{
k=a[j];
for(i=j-incre;i>=0 && k<a[i];i=i-incre)
a[i+incre]=a[i];
a[i+incre]=k;
}
printf("\nIncrement = %d\n",incre);
for(i=0;i<n;i++)
printf("\n%d",a[i]);
incre=incre-2;
}
printf("\nSorted List is: \n");
for(i=0;i<n;i++)
printf("\n%d",a[i]);
getch();

}
PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)
C.T.BELANI Page 74
 DATA STRUCTURE (3330704)

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 75
 DATA STRUCTURE (3330704)

IMPLEMENT TREE

#include<stdio.h>
#include<malloc.h>
struct node
{
int info;
struct node *lchild;
struct node *rchild;
}*root;

void insert(int);
void display();
void find();

void main()
{
int choice,n;
root=NULL;
clrscr();
while(1)
{
printf("\n\n*****PROGRAM FOR TREE*****\n");
printf("1. ENTER 1 FOR INSERT\n");
printf("2. ENTER 2 FOR DISPLAY \n");
printf("3. ENTER 3 FOR EXIT\n");
printf("ENTER YOUR CHOICE \n");
scanf("%d",&choice);

switch(choice)
{

case 1:
printf("Enter element to be inserted:");
scanf("%d",&n);
insert(n);
break;

case 2:
display(root,1);
break;

case 3:
exit(1);
PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)
C.T.BELANI Page 76
 DATA STRUCTURE (3330704)

default:
printf("wrong choice\n");
}
}
}

void find(int item,struct node **par,struct node **loc)

{
struct node *ptr,*ptrsave;
if(root==NULL)
{
*loc=NULL;
*par=NULL;
return;
}
if(item<root -> info)
ptr=root->lchild;
else
ptr=root->rchild;
ptrsave=root;

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

void insert(int item)

{
struct node *tmp,*parent,*location;
PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)
C.T.BELANI Page 77
 DATA STRUCTURE (3330704)

find(item,&parent,&location);
if(location!=NULL)
{
printf("Item already present");
return;
}
tmp=(struct node*)malloc(sizeof(struct node));
tmp->info = item;
tmp->lchild=NULL;
tmp->rchild=NULL;
if(parent==NULL)
root=tmp;
else
if(item<parent ->info)
parent->lchild=tmp;
else
parent->rchild=tmp;

void display(struct node *ptr,int level)

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

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 78
 DATA STRUCTURE (3330704)

OUTPUT

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 79
 DATA STRUCTURE (3330704)

PREPAIRED BY ATUL POLYTECHNIC (CE DEPARTMENT)

C.T.BELANI Page 80