Graphs-Menu Driven Program

#include<iostream.h>
#include<stdio.h>
#include<conio.h>
struct adjnode
{
char dest;
adjnode *link;
};
struct node
{
char data;
node *next;
adjnode *adj;
};

node *first,*last,*start;

void enteradj(node* ptr)
{ int nadj;
cout<<” no of adjacent node present??”;
cin>>nadj;

if(nadj>0)
{
adjnode *beg,*end;
beg=new(adjnode);
ptr->adj=beg;
cout<<“enter the first adjacent member/destination”;
cin>>beg->dest;
beg->link=NULL;
for(int a=1;a<nadj;a++)
{
end=new(adjnode);
cout<<“enter destination”;
cin>>end->dest;
fflush(stdin);
end->link=NULL;
beg->link=end;
beg=end;
}
}
}
void findnode()
{ int flag=0;
char ch;
node *ptr;
ptr=start;
cout<<“enter the node to be found”;
cin>>ch;
fflush(stdin);
while(ptr!=NULL)
{
if(ch==ptr->data)
{
flag=1;
break;
}
ptr=ptr->next;
}
if(flag==1)
{
cout<<“yes the item is present”;
}
else{
cout<<“unsuccessful search”;
}
}

void insertnode()
{
node *ptr;
ptr=new(node);
cout<<“enter data”;
cin>>ptr->data;
ptr->next=NULL;
last->next=ptr;
last=ptr;
enteradj(ptr);
}
void deletenode()
{ node *ptr,*save;
char dlt;
int flag=0;
cout<<“enter data to be deleted”;
cin>>dlt;
ptr=start;
if(dlt==ptr->data)
{
start=start->next;
delete ptr;
}
else
{ptr=start->next;
save=start;
while(ptr!=NULL)
{
if(ptr->data==dlt)
{flag=1;
save->next=ptr->next;
delete ptr;
}
else
{
save=ptr;
ptr=ptr->next;
}
}
}
if(flag==0)
{
cout<<“unsuccessful”;
}
}
int main()
{
int n;
cout<<“enter n”;
cin>>n;
first=new(node);
cout<<“enter the first data”;
cin>>first->data;
first->next=NULL;
start=first;
fflush(stdin);
enteradj(first);

for(int b=1;b<n;b++)
{
last=new(node);
cout<<“enter the data of node”;
cin>>last->data;
fflush(stdin);
enteradj(last);
last->next=NULL;
first->next=last;
first=last;
}
int choice;

do
{
cout<<” enter 1 to insert a node”;
cout<<“\n 2 to delete a node containing particular data”;
cout<<“\n 3 to find a node”;
cout<<“\n 4 to exit”;
cin>>choice;
switch(choice)
{
case 1: insertnode();
break;
case 2: deletenode();
break;
case 3: findnode();
break;
}
}while(choice!=4);
getch();
return 0;
}

Topological Sort

#include<iostream.h>
#include<stdio.h>
#include<conio.h>
struct adjnode
{
char dest;
adjnode *link;
};
struct node
{
char data;
int degree;
int q;
node *next;
adjnode *adj;
};

node *first,*last,*start;
int n,flag;
int rear,front;
char queue[50];
void enteradj(node* ptr)
{ int nadj;
cout<<” no of adjacent node present??”;
cin>>nadj;

if(nadj>0)
{
adjnode *beg,*end;
beg=new(adjnode);
ptr->adj=beg;
cout<<“enter the first adjacent member/destination”;
cin>>beg->dest;
beg->link=NULL;
for(int a=1;a<nadj;a++)
{
end=new(adjnode);
cout<<“enter destination”;
cin>>end->dest;
fflush(stdin);
end->link=NULL;
beg->link=end;
beg=end;
}
}
else
{
ptr->adj=NULL;
}
}
void calculatedegree()
{ node *n;
adjnode *ptr;
n=start;
while(n!=NULL)
{

ptr=n->adj;
while(ptr!=NULL)
{
ptr=ptr->link;
n->degree++;
}
cout<<“\n “<<n->degree;
n=n->next;
}
}

void insert(int flag)
{ node *ptr;
ptr=start;
while(ptr!=NULL)
{
if((ptr->degree==0)&&(flag==1))
{queue[rear]=ptr->data;
ptr->q=1;

cout<<“\n the data entered is”<<queue[rear];
rear++;
}
else
{
if((ptr->degree==0)&&(ptr->q==0))
{
queue[rear]=ptr->data;
ptr->q=1;

cout<<“entered data is”<<queue[rear];
rear++;
}
}
ptr=ptr->next;
}
}
node* find(char info)
{
node *ptr;
ptr=start;
while(ptr!=NULL)
{
if(ptr->data==info)
{
break;
}
ptr=ptr->next;
}
return ptr;
}
void adjcalculate(char info)
{
node *loc,*loc1;
loc=find(info);
adjnode *p;
p=loc->adj;
while(p!=NULL)
{
loc1= find(p->dest);
loc1->degree–;
cout<<“degree of adjacent members : “<<loc1->degree;
p=p->link;
cout<<“\n”;

}
}

int main()
{
clrscr();
cout<<“enter n”;
cin>>n;
first=new(node);
cout<<“enter the first data”;
cin>>first->data;
first->next=NULL;
start=first;
fflush(stdin);
enteradj(first);
cout<<“enter degree”;
cin>>first->degree;
first->q=0;
for(int b=1;b<n;b++)
{
last=new(node);
cout<<“enter the data of node”;
cin>>last->data;
fflush(stdin);
enteradj(last);
last->next=NULL;
cout<<“enter degree”;
cin>>last->degree;
last->q=0;
first->next=last;
first=last;
}
char temp;
front=rear=0;
flag=1;
while(front<=rear)
{
insert(flag);
temp=queue[front];
front++;
cout<<“rear is”<<rear;
adjcalculate(temp);
flag=0;
}
cout<<“rear is”<<rear;
int j=0;
while(j<=rear)
{
cout<<queue[j];
j++;
cout<<“\n”;
}
getch();
return 0;
}

VALUE OF POSTFIX

#include<iostream.h>
#include<conio.h>
void push( int stack[],int top,int n, int d);
int pop(int stack[],int top);

int main()
{
int stack[100];
int n,top;
int temp;
top=-1;
char string[20];
cout<<“enter the postfix expression”;
gets(string);
char *ptr;
ptr=string;
while(ptr!=NULL)
{
if(isdigit(*(&ptr)))
{ temp=*(&ptr);
push(stack,top,n,temp);
}
else
{ char operator;
operator= *(&ptr) ;
int d1,d2,val;
d1=pop(stack,top);
d2=pop(stack,top);
switch(operator)
{
case ‘+’: val=d2+d1;
push(stack,top,n,val);
break;
case ‘-‘: val=d2-d1;
push(stack,top,n,val);
break;
case ‘*’: val=d2*d1;
push(stack,top,n,val);
break;
case ‘/’: val=d2/d1;
push(stack,top,n,val);
break;
case ‘^’: int c=1;
for(int i=1;i<=d1;i++)
{
c=d2*c;
}
val=c;
push(stack,top,n,val);
break;
}
}
ptr++;
}
int finalvalue;
finalvalue=pop(stack,top);
getch();
return 0;
}

void push(int stack[],int top,int n,int d)
{
if(n>100)
{
cout<<“overflow”;
exit(0);
}
else
{
top++;
stack[top]=d;
}
}

int pop(int stack[],int top)
{ int popval;
if(top<0)
{
cout<<“underflow”;
exit(0);
}
else
{
popval=stack[top];
top–;
return popval;
}
}

Stack(using linked list)

#include<iostream.h>
#include<conio.h>
struct node
{
int data;
node *next;
};
node* push(node* top);
node* pop(node* top);
void display(node* top);
void main()
{
clrscr();
int choice;
node* top;
top=NULL;
do
{
cout<<” 1 for push \n 2 for pop \n 3 for display \n 4 for quit”;
cin>>choice;
switch(choice)
{
case 1:
top= push(top);
break;

case 2: top=pop(top);
break;
case 3: display(top);
break;
}
}
while(choice!=4);
getch();
}
node* push(node* top)
{
node* x;
x=new node;
cout<<“enter value”;
cin>>x->data;
x->next=top;
top=x;
return top;
}
node* pop(node* top)
{ int v;
if(top==NULL)

{
cout<<“stack empty”;
return top;
}
else
{
node *x;
x=top;
top=top->next;
v=x->data;
cout<<“popped value”<<v;
delete x;
return top;
}
}
void display(node* top)
{
while(top!=NULL)
{
cout<<top->data;
cout<<“\n”;
top=top->next;
}
}

 

Queue( using linked list)

#include<iostream.h>
#include<conio.h>
struct node
{
int info;
node *next;
};
node* insert(node* rear);
node* delet(node* front);
void display(node* front);
int main()
{
node *front,*rear;
front=rear=NULL;
int choice;
do
{
cout<<” enter 1 for insert \n 2 for delete \n 3 for display \n 4 for exit”;
cin>>choice;
switch(choice)
{
case 1:rear=insert(rear);
if(front==NULL)
{
front=rear;
}
break;
case 2:front=delet(front);
if(front==NULL)
{
rear=front;
}
break;
case 3:display(front);
break;
}
}while(choice!=4);
getch();
return 0;
}
node* insert( node* rear)
{
node *temp;
temp=new(node);
cout<<“enter info”;
cin>>temp->info;
temp->next=NULL;
if(rear!=NULL)
{
rear->next=temp;
}
rear=temp;
cout<<“info is “<<rear->info;
return rear;
}
node* delet(node* front)
{
if(front==NULL)
{
cout<<” underflow”;
return front;
}
else
{
node *ptr;
ptr=front;
ptr->info=front->info;
cout<<“deleted value is “<<ptr->info;
front=front->next;
delete ptr;

}
return front;
}
void display(node* front)
{
node *ptr;
ptr=front;
while(ptr!=NULL)
{
cout<<“info is”<<ptr->info;
ptr=ptr->next;
}
}

QUEUE(linear)

#include<iostream.h>
#include<conio.h>
void insert(int queue[],int &rear,int val,int n);
int delet(int queue[],int &front,int &rear );
void display(int queue[],int &front,int &rear);
void main()
{
clrscr();
int queue[50],front,rear,choice,val,p;
front=rear=0;
do
{
cout<<” 1 for insert \n 2 for delet \n 3 for display \n 4 for quit”;
cin>>choice;
switch(choice)
{
case 1: cout<<“enter val”;
cin>>val;
insert(queue,rear,val,30);
break;

case 2: p=delet(queue,front,rear);
if(p!= -9999)
{
cout<<“deleted value is”<<p;
}
break;
case 3: display(queue,front,rear);
break;
}
}
while(choice!=4);
getch();
}
void insert(int queue[],int &rear,int val,int n)
{
if(rear<n)
{

queue[rear++]=val;
}
else{
cout<<“queue full”;
}
}
int delet(int queue[],int &front,int &rear)
{ int v;
if(front==rear)
{
cout<<“queue empty”;
return -9999;
}
else
{ v=queue[++front];
return v;
}
}
void display(int queue[],int &front,int &rear)
{ int i;
if(front<rear)
{
for(i=front+1;i<=rear;i++)
{
cout<<queue[i];
cout<<“\n”;
}
}
}

Stack(linear)

#include<conio.h>
#include<iostream.h>
#include<process.h>
void insert(int[],int,int);
void display(int[],int);
const int size=50;
void main()
{
char ch;
int stack[size],item,top=-1,res;
while(ch==’y’||ch==’Y’)
{
char ch;
cout<<“enter element”;
cin>>item;
insert(stack,top,item);
cout<<“do u want to enter more elements”;
cin>>ch;
}
display(stack,top);
getch();
}

void insert(int stack[],int top,int item)
{
if(top==size-1)
{
cout<<“overflow”;
exit(1);
}
else
{
top++;
stack[top]=item;
}
}
void display(int stack[],int top)
{
int i=0;
for(i=0;i<top;i++)
cin>>stack[i];
}

Circular Doubly Linked List

#include< stdio.h >
#include< stdlib.h >
struct list
{
int num;
struct list *next;
struct list *prev;
};

struct list *node;

void create(struct list *n)
{
char ch;
node=n;
printf(“\nWant to create location(y/n):-“);
scanf(“%c”,&ch);
fflush(stdin);

while(ch!=’n’)
{
fflush(stdin);
node->next=(struct list *)malloc(sizeof(struct list));
node->next->prev=node;
node=node->next;
printf(“\Enter value:-“);
scanf(“%d”,&node->num);
fflush(stdin);
printf(“\Any more (y/n)”);
scanf(“%c”,&ch);
}

node->next=n;
n->prev=node;
}

void display(struct list *n)
{
node=n->next;

while(node!=n)
{
printf(“%d\n”,node->num);
node=node->next;
}

}

void insert(struct list *n)
{
struct list *node,*new1;
int c=1,count;
node=n;
new1=(struct list*)malloc(sizeof(struct list));
printf(“\nEnter the location where the new location will be inserted:”);
scanf(“%d”,&count);
printf(“\Enter value:-“);
scanf(“%d”,&new1->num);

do
{
if(c==count)
break;
node=node->next;
c++;
}while(node!=n);

new1->next=node->next;
node->next->prev=new1;
node->next=new1;
new1->prev=node;
}

void main()
{
struct list *start;
clrscr();
start=(struct list*)malloc(sizeof(struct list));
/* header node without any value */
create(start);
printf(“Now display the value of the circular lists:-\n”);
display(start);
insert(start);
printf(“\nAfter insertion, the list is\n”);
display(start);
getch();
}

Header Linked List

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

struct list
{
char name[100];
struct list *next;
};
struct list *start;

void insert()
{
int c=1,count;
struct list *p,*node,*new1;
printf(“\n which location you want to insert:”);
scanf(“%d”,&count);

node=start;
p=node->next;
new1=(struct list *)stdlib(sizeof(struct list));
printf(“\Enter Name:-“);
scanf(“%s”,&new1->name);

while(p!=NULL)
{
if(c==count)
break;
node=node->next;
p=p->next;
c++;
}

node->next=new1;
new1->next=p;
}

void del()
{
int c=1,count;
struct list *p,*node;
printf(“\nwhich location you want to delete:”);
scanf(“%d”,&count);

node=start;
p=node->next;

while(p->next!=NULL)
{
if(c==count)
break;
node=node->next;
p=p->next;
c++;
}

node->next=p->next;
free(p);
}

void create(struct list *node)
{
char ch;
start=node;
printf(“\nEnter value for the header node (****):-“);
scanf(“%s”,&node->name);
fflush(stdin);
node->next=NULL;
printf(“\nWant to create another node(y/n):-“);
scanf(“%c”,&ch);
fflush(stdin);

while(ch!=’n’)
{
fflush(stdin);
node->next=(struct list *)stdlib(sizeof(struct list));
node=node->next;
printf(“\Enter Name:-“);
scanf(“%s”,&node->name);
fflush(stdin);
node->next=NULL;
printf(“\Any more (y/n)”);
scanf(“%c”,&ch);
}

node->next=start;
/*last node is connected with the header node */
}

void display(struct list *node)
{
int x=0;
node=node->next;

while(x==0)
{
printf(“%s\n”,node->name);
node=node->next;
if(strcmp(node->name,”****”)==0)
x=1;
}

}

void main()
{
struct list *node=(struct list *)stdlib(sizeof(struct list));
clrscr();
create(node);
printf(“Now display the Names of the circular list:-\n”);
display(node);
del();
printf(“\nAfter deletion\n”);
display(node);
insert();
printf(“\nAfter insertion\n”);
display(node);
getch();
}

Linked List (menu driven)

#include<iostream.h>
#include<conio.h>

struct node
{
int data;
node *next;
}

void insert();
void deleterec();
void count();

void main()
{
clrscr();
int choice;
int n;
node *first,*last,*ptr;

first=new(node);
cout<<“enter the first data”;
cin>>first->data;
first->next=NULL;
ptr=first;

cout<<“enter the number of recors”;
cin>>n;

for(int a=0;a<n-1;a++)
{
last=new(node);
cout<<“\n enter data”;
cin>>last->data;
last-next=NULL;
first->next=last;
first=last;
}

do
{
cout<<” enter 1 for insertion
enter 2 for deletion
enter 3 for counting
enter 4 for exit”;
cin>>choice;

switch(choice)
{
case 1: insert();
break;
case 2: deleterec();
break;
case 3: count();
break;

default:cout<<“enter corrct choice”;
}

}while(choice!=4)

getch();
}

void insert(node *ptr)
{
int d;
cout<<“enter the data”;
cin>>d;
node *x;

if(d<ptr->data);
{
x=new(node);
x->data=d;
x->next=ptr;
}

else
{
while(d>ptr->data)
{
ptr=ptr->next;
}
x=new(node);
x->data=d;
x->next=ptr->next;
ptr=x;
}
}

void deleterec(node *ptr)
{
node *last;
last=NULL;
int temp,dlt;
cout<<“enter data to be deleted”;
cin>>dlt;

if(dlt==ptr->data)
{
temp=ptr->data;
ptr=ptr->next;\\delete statement to be used or not
}

else
{
while(dlt>ptr->data)
{
ptr=ptr->next;
last=ptr;
}
dlt=ptr->data;
last->next=ptr->next;
}
}

void count(node *ptr)
{
int count;
while(ptr!=NULL)
{
ptr=ptr->next;
count++;
}
cout<<“the number of entries is “<<count;
}