Data structure lab program
DS program output Click Here
Data Structure All Questions👇👇👇
These questions I have made my self if anything happens wrong I am not responsible 🙂
1) Singly linked list👇👇👇
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int value;
struct node *next;
};
void insert();
void display();
void delete();
int count();
typedef struct node DATA_NODE;
DATA_NODE *head_node,*first_node,*temp_node=0,*prev_node,*next_node;
int data;
void main()
{
int option=0;
printf("**Singly linked list all operation**\n");
while(option<5)
{ printf("\n");
printf("1:Insert\n");
printf("2:Delete\n");
printf("3:Display\n");
printf("4:Count\n");
printf("5:Exit\n");
printf("Enter your option: ");
scanf("%d",&option);
switch(option)
{
case 1: insert(); break;
case 2: delete(); break;
case 3: display(); break;
case 4: count(); break;
case 5: exit(0);
default : exit(0);
}}}
void insert()
{
printf("Enter element for insert: ");
scanf("%d",&data);
temp_node=(DATA_NODE*)malloc(sizeof(DATA_NODE));
temp_node->value=data;
if(first_node==0)
first_node=temp_node;
else
head_node->next=temp_node;
temp_node->next=0;
head_node=temp_node;
fflush(stdin);
}
void delete()
{
int count_value,pos,i=0;
count_value=count();
temp_node=first_node;
/*printf("\nDisplay linked list: ");
printf("%d\n",temp_node->value);*/
printf("Enter the position for delete element: ");
scanf("%d",&pos);
if(pos>0&&pos<=count_value)
{
if(pos==1)
{
temp_node=temp_node->next;
first_node=temp_node;
printf("Deletion successful !!!\n");
}
else
{
while(temp_node!=0)
{
if(i==(pos-1))
{
prev_node->next=temp_node->next;
if(i==(count_value-1))
{
head_node=prev_node;
}
printf("Deletion successful !!!\n");
break;
}
else
{i++;
prev_node=temp_node;
temp_node=temp_node->next;
}}}}
else
printf("Invalid position\n");
}
void display()
{
int count=0;
temp_node=first_node;
printf("Display linked list: ");
while(temp_node!=0)
{
printf("%d ",temp_node->value);
count++;
temp_node=temp_node->next;
}
printf("\nNumber of item in linked list: %d\n",count);
}
int count()
{
int count=0;
temp_node=first_node;
while(temp_node!=0)
{
count++;
temp_node=temp_node->next;
}
printf("\nNumber of item in linked list: %d\n",count);
return count;
}
Pdf download: click here
Output------> click here
2) Doubly linked list 👇👇
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
struct node *prev;
int data;
struct node *next;
}*head=NULL;
void createafter();
void createbeg();
void display();
void delet();
void insertpos();
void main()
{
int ch;
do
{
printf("\nenter your choice \n1.create\n2.display\n3.deletin\n4.createbeg\n");
printf("5.insertpos\n6.exit\n");
scanf("%d",&ch);
switch(ch){
case 1:createafter(); break;
case 2:display(); break;
case 3:delet(); break;
case 4:createbeg(); break;
case 5:insertpos(); break;
case 6:exit(0);
default:printf("\n wrong cholce");
}}
while(ch!=6);
}
void createafter()
{
struct node *newnode,*temp;
newnode=(struct node *)malloc(sizeof(struct node));
printf("\n enter data part");
scanf("%d",&newnode->data);
if(head==NULL)
{
newnode->prev=NULL;
newnode->next=NULL;
head=newnode;
}
else
{
temp=head;
while(temp->next!=NULL)
temp=temp->next;
temp->next=newnode;
newnode->next=NULL;
}}
void display()
{
struct node *ptr;
ptr=head;
while(ptr!=NULL)
{
printf("element are: %d\n",ptr->data);
ptr=ptr->next;
}
}
void delet()
{
int val;
struct node *temp,*ptr;
printf("\nenter value to delete");
scanf("%d",&val);
temp=head;
if(temp->data==val)
{
head=head->next;
head->prev=NULL;
printf("\n%d element is deleted successfully",val);
free(temp);
}
else
{
while(temp->data!=val)
{
ptr=temp;
temp=temp->next;
}
ptr->next=temp->next;
temp->next->prev=ptr;
printf("\n%d element is deleted successfully",val);
free(temp);
}}
void createbeg()
{
struct node *newnode,*temp;
newnode=(struct node*)malloc(sizeof(struct node));
printf("\n enter data part");
scanf("%d",&newnode->data);
if(head==NULL)
{
newnode->prev=NULL;
newnode->next=NULL;
head=newnode;
}
else
{
newnode->next=head;
newnode->prev=NULL;
head->prev=newnode;
head=newnode;
}
}
void insertpos()
{
}
Pdf download: click here
Output -----> click here
3) Circular linked list 👇👇👇
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
}*head=NULL;
void create();
void createbeg();
void display();
void delete();
void main()
{
int ch;
do{
printf("\nenter your choice\n1.create\n2.display\n 3.delete\n4.createbeg\n5.exit\n");
scanf("%d",&ch);
switch(ch)
{
case 1: create();break;
case 2: display();break;
case 3: delete();break;
case 4: createbeg();break;
case 5: exit(0);break;
default: printf("wrong choice\n");
}}
while(ch!=5);
}
void create()
{
struct node *newnode,*temp;
newnode=(struct node*)malloc(sizeof(struct node));
printf("enter data part: ");
scanf("%d",&newnode->data);
if(head==NULL)
{
newnode->next=head;
head=newnode;
}
else
{
temp=head;
while(temp->next!=head)
temp=temp->next;
newnode->next=head;
temp->next=newnode;
}
}
void display()
{
struct node *ptr;
ptr=head;
while(ptr->next!=head){
printf("%d ",ptr->data);
ptr=ptr->next;}
printf("%d ",ptr->data);
}
void delete()
{ int val;
struct node *ptr,*temp,*prev;
printf("enter value to delete: ");
scanf("%d",&val);
temp=head;
ptr=head;
if(temp->data==val)
{ while(temp->next!=head)
temp=temp->next;
head=head->next;
temp->next=head;
free(ptr);
printf("Deletion successful");
}
else
{ while(temp->data!=val)
{ prev=temp;
temp=temp->next;
}
prev->next=temp->next;
free(temp);
printf("element deletion successful\n");
}}
void createbeg()
{
struct node *newnode,*temp;
newnode=(struct node*)malloc(sizeof(struct node));
printf("enter data part: ");
scanf("%d",&newnode->data);
if(head==NULL)
{
newnode->next=newnode;
head=newnode;
}
else
{
newnode->next=head;
temp=head;
while(temp->next!=head)
temp=temp->next;
newnode->next=head;
temp->next=newnode;
head=newnode;
}}
Output -----> click here
4) Stack 👇👇👇
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define size 10
struct stack
{
int s[size];
int top;
}st;
int stfull()
{
if (st.top>=size-1)
return 1;
else
return 0;
}
void push()
{
int item;
st.top++;
st.s[st.top]=item;
}
int stemp()
{
if (st.top==-1)
return 1;
else
return 0;
}
int pop()
{
int item ;
item =st.s[st.top];
st.top--;
return(item);
}
void display()
{
int i;
if(stemp())
printf("\n stack is empty ");
else
{
for(i=st.top;i>=0;i--)
printf("\n %d",st.s[i]);
}
}
void main ()
{
int item,choice;
char ans;
st.top=-1;
printf("\n implementation of stack");
do
{
printf("\n Main menu ");
printf("\n 1. push 2.pop 3.display 4.exit");
scanf("%d",&choice);
switch (choice)
{
case 1: printf("\n enter the element for push\n");
scanf("%d",&item);
if(stfull())
printf("\n stack is full ");
else
push(item);
break;
case 2: if(stemp())
printf("\n empty stack ");
else
{
//item=pop();
printf("\n the popped Element is %d",item);
item=pop();
break;
}
case 3: display();
break;
case 4: exit(0);
}
getch();
printf("do u want to continue");
scanf("%c",&ans);
}
while(ans=='y'||ans=='Y');
getch();
}
}
Output -----> click here
5) Queue 👇👇👇
#include<stdio.h>
#include<conio.h>
struct node
{
int data;
struct node *next;
}
*front=NULL , *rear=NULL;
void insert()
{
int value;
struct node*newnode;
newnode =(struct node*)malloc(sizeof(struct node));
printf("enter data : ");
scanf("%d",&value);
newnode->data=value;
newnode->next=NULL;
if(front==NULL)
front=rear=newnode;
else
{
rear->next=newnode;
rear=newnode;
}
printf("Insertion successfull!!!");
}
void delete()
{
if(front==NULL)
printf("queue is empty");
else
{
struct node* temp=front;
front=front->next;
printf("\n deletion element %d",temp->data);
free(temp);
}}
void display()
{
if(front==NULL)
printf("queue is empty");
else
{
struct node* temp=front;
while(temp->next!=NULL)
{
printf("%d--->",temp->data);
temp=temp->next;
}
printf("%d-->NULL",temp->data);
}}
void main()
{
int choice,value;
clrscr();
printf("\nqueue implementation\n");
while(1)
{
printf("\n ***MENU***\n");
printf("\n1.insert\n2.delete\n3.display\n4.exit\n");
printf("enter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("enter the value: ");
scanf("%d",&choice);
insert(value); break;
case 2: delete(); break;
case 3: display(); break;
case 4: exit(0);
}}}
Output -----> click here
6) linear search 👇👇👇
#include<stdio.h>
void main ()
{
int a[10] = {10, 23, 40, 1, 2, 0, 14, 13, 50, 9};
int item,i,flag;
printf("\nEnter Item which is to be searched\n");
scanf("%d",&item);
for (i = 0; i< 10; i++)
{
if(a[i] == item)
{
flag = i+1;
break;
}
else
flag = 0;
}
if(flag != 0)
{
printf("\nItem found at location %d\n",flag);
}
else
{
printf("\nItem not found\n");
}
}
Output -----> click here
7) Binary search 👇👇👇
#include <stdio.h>
int recursivebinarysearch( int array[],int start_index,int end_index,int element)
{
if(end_index>=start_index)
{
int middle=start_index+(end_index-start_index)/2;
if(array[middle]==element)
return middle;
if(array[middle]>element)
return recursivebinarysearch(array,start_index,middle-1,element);
return recursivebinarysearch(array,middle+1,end_index,element);
}
return-1;
}
int main(void)
{
int array[]={1,4,7,9,16,56,70};
int n=7;
int element =56;
int found_index=recursivebinarysearch(array,0,n-1,element);
if (found_index==-1)
{
printf("element not found in the array");
}
else{
printf("element found at index:%d",found_index);
}
return 0;
}
8) Bfs ( Breadth first search )
#include<stdio.h>
#include<conio.h>
int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1;
void bfs(int v)
{
for(i=1;i<=n;i++)
if(a[v][i]&&!visited[i])
q[++r]=i;
if(f<=r)
{
visited[q[f]]=1;
bfs(q[f++]);
}
}
void main()
{
int v;
printf("\n enter the number of vertixes:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
q[i]=0;
visited[i]=0;
}
printf("\n enter graphs data in matrix form:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
}
printf("\n enter the starting vertex:");
scanf("%d",&v);
bfs(v);
printf("\n the node which are reachable are:");
for(i=1;i<=n;i++)
{
if(visited[i]!=0)
printf("%d\t",i);
else
{
printf("\n Bfs is not possible,not all nodes are reachable");
break;
}
}
}
Output ----> Click here
9) Dfs ( Depth first search )
#include<stdio.h>
#include<conio.h>
int a[20][20],reach[20],n;
void dfs(int v)
{
int i;
reach[v]=1;
for(i=1;i<=n;i++)
if(a[v][i]&&!reach[i])
{
printf("%d %d ",v,i);
dfs(i);
}
}
void main()
{
int i,j,count=0;
printf("\n enter number of vertixes");
scanf("%d",&n);
for(i=1;i<=n;i++)
reach[i]=0;
for(j=1;j<=n;j++)
a[i][j]=0;
printf("\n enter the adjacency matrix\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
dfs(1);
printf("\n");
for(i=1;i<=n;i++)
{
if(reach[i])
count++;
}
if(count==n)
printf("graph is connected");
else
printf("\n graph is not connected");
getch();
}
Output will upload soon
10) Knuth-Morris-pratt ( Lead Program )
include<stdio.h>
#include<string.h>
#include<stdlib.h>
int *cpf(char *pattern, int psize )
{
int k=-1,i=1;
int *pi=malloc(sizeof(int)*psize);
if(!pi)
return NULL;
pi[0]=k;
for(i=0;i<psize;i++)
{
while(k>-1&&pattern[k+1]!=pattern[i])
k=pi[k];
if(pattern[i]!=pattern[k+1])
k++;
pi[i]=k;
}
return pi;
}
int kmp(char *target, int tsize, char *pattern, int psize )
{ int i;
int *pi= cpf(pattern,psize);
int k=-1;
if(!pi)
return -1;
for(i=0;i<tsize;i++)
{
while(k>-1&&pattern[k+1]!=target[i])
k=pi[k];
if(target[i]==pattern[k+1])
k++;
if(k==psize-1)
{
free(pi);
return i-k;
}}
free(pi);
return -1;
}
int main (int argc, const char *argv[])
{
char target[]="ABC ABCDAB ABCDABCDABDE";
char *ch=target;
char pattern[]="ABCDABD";
int i;
i=kmp(target, strlen(target),pattern, strlen(pattern));
if(i<=0)
printf("matched @: %s\n",ch);
return 0;
}
Output I will upload soon.
If any thing you notice wrong in this post then please let me know.
0 Comments