#include
#include
void main()
{
int list[10],curr,last,sorted;
int walker,temp,i,n;
clrscr();
curr=0;
sorted=0;
printf("enter the elements:");
scanf("%d",&n);
last=n-1;
printf("Enter the Elements To Be Sorted:\n");
for(i=0;i
while(curr
walker=last;
sorted=1;
while(walker>curr)
{
if(list[walker]
sorted=0;
temp=list[walker];
list[walker]=list[walker-1];
list[walker-1]=temp;
}
walker=walker-1;
}
curr=curr+1;
}
printf("The Sorted Elements are:\n");
for(i=0;i
getch();
}
------------------------------------------------------------------------------------
/* Program for selection sort */
#include
#include
void main( )
{
int arr[20];
int i, j, temp, n;
clrscr( ) ;
printf("Enter the no. of elements for sorting");
scanf("%d",&n);
for( i=0 ; i
printf("enter the numbers to be sorted");
scanf("%d",&arr[i]);
}
printf ( "Selection sort.\n" ) ;
printf ( "\nArray before sorting:\n") ;
for ( i = 0 ; i
for ( i = 0 ; i
for ( j = i + 1 ; j
if ( arr[i] > arr[j] )
{
temp = arr[i] ;
arr[i] = arr[j] ;
arr[j] = temp ;
}
}
}
printf ( "\n\nArray after sorting:\n") ;
for ( i = 0 ; i
getch( ) ;
}
-------------------------------------------------------------------------------------
//3. Insertion Sort
#include
#include
void insertion(int list[],int last)
{
int hold,walker,current;
for(current=1;current<=last;current++)
{
hold=list[current];
for(walker=current-1;walker>=0 && hold
list[walker+1]=hold;
}
}
void main()
{
int a[100],n,i;
clrscr();
printf("Enter number of elements in array: ");
scanf("%d",&n);
printf("\nEnter %d elements: \n\n",n);
for(i=0;i
scanf("%d",&a[i]);
}
insertion(a,n-1);
printf("\n\nSorted list is:\n\n");
for(i=0;i
printf("%5d",a[i]);
}
getch();
}
/*
Output:
Enter number of elements in array: 6
Enter 6 elements:
89 23 44 39 1 27
Sorted list is:
1 23 27 39 44 89
*/
-------------------------------------------------------------------------------------
//1.4 SHELL SORT
#include
#include
void shell(int list[],int last)
{
int hold;
int incre;
int w;
int curr;
incre=last/2;
while(incre!=0)
{
for(curr=incre;curr<=last;curr++)
{
hold=list[curr];
w=curr-incre;
while(w>=0 && hold
list[w+incre]=list[w];
w=(w-incre);
}
list[w+incre]=hold;
}
incre=incre/2;
}
}
void main()
{
int a[100],n,i;
clrscr();
printf("Enter number of elements in array: ");
scanf("%d",&n);
printf("\nEnter %d elements: \n\n",n);
for(i=0;i
scanf("%d",&a[i]);
}
shell(a,n-1);
printf("\n\nSorted list is:\n\n");
for(i=0;i
printf("%5d",a[i]);
}
getch();
}
-------------------------------------------------------------------------------------
/**********************************************************************/
/*Program : To show sorting technique*/
/*Purpose : Program to sort list of elements using quick sort*/
/**********************************************************************/
#include
#include
#define SIZE 20
/**************Function Declaration Begin**********/
void Quick_sort(int A[],int n);
int Partition(int A[],int n);
void get_elements(int A[],int n);
void show_elements(int A[],int n);
/**************Function Declaration End**********/
void main()
{
int n,A[SIZE];
clrscr();
printf(“\n\t\t Program for Quick sort:”);
printf(“\n\n\t\t How many numbers you want to store in the array:”);
scanf(“%d”,&n);
get_elements(A,n);
Quick_sort(A,n);
show_elements(A,n);
getch();
}
/********** inputting elements **********/
/********** Function Definition begins **********/
void get_elements( int A[],int n)
{
int i;
printf(“\n Enter %d elements\n”,n);
for (i=0;i
scanf(“%d”,&A[i]);
printf(“\n Array before sorting: “);
for(i=0;i
printf(“%d “,A[i]);
printf(“\n”);
}
/********** Function Definition ends **********/
/********** displaying elements **********/
/********** Function Definition begins **********/
void show_elements(int A[],int n)
{
int i;
printf(“\n Array after sorting: “);
for(i=0;i
{
printf(“%d “,A[i]);
}
printf(“\n”);
}
/********** Function Definition ends **********/
/******************* Quick Sorting technique *****************/
/********** Function Definition begins **********/
void Quick_sort(int A[],int n)
{
int pivot;
if(n<=1)
{
return;
}
pivot=Partition(A,n);
Quick_sort(A,pivot);
Quick_sort(A+pivot+1,n-pivot-1);
}
/********** Function Definition ends **********/
/******************* partitioning technique *****************/
/********** Function Definition begins **********/
int Partition(int A[],int n)
{
int pivot,l,r,s;
pivot=A[0]; /* Fixing first element as pivot*/
l=0; r=n-1;
for( ; ; )
{
while(l
{
l++;
}
while(lpivot)
{
r—;
}
if(l==r)
{
if(A[r]>pivot)
{
l=l-1;
}
break;
}
s=A[l];
A[l]=A[r];
A[r]=s;
}
s=A[0];
A[0]=A[l];
A[l]=s;
return l;
}
/********** Function Definition ends **********/
/* OUTPUT
Program for Quick sort:
How many numbers you want to store in the array:6
Enter 6 elements
66
55
44
33
22
11
Array before sorting: 66 55 44 33 22 11
Array after sorting: 11 22 33 44 55 66
*/
-------------------------------------------------------------------------------------
//2. Heap Sort
#include
#include
void reheapup(int *heap,int newnode)
{
int parent;
int hold;
if(newnode)
{
parent=(newnode-1)/2;
if(heap[newnode]>heap[parent])
{
hold=heap[parent];
heap[parent]=heap[newnode];
heap[newnode]=hold;
reheapup(heap,parent);
}
}
}
void reheapdown(int *heap,int root,int last)
{
int hold,leftkey;
int rightkey,largechildkey;
int largechildindex;
if((root*2+1)<=last)
{
leftkey=heap[root*2+1];
if((root*2+2)<=last)
rightkey=heap[root*2+2];
else
rightkey=-1;
if(leftkey>rightkey)
{
largechildkey=leftkey;
largechildindex=root*2+1;
}
else
{
largechildkey=rightkey;
largechildindex=root*2+2;
}
if(heap[root]
hold=heap[root];
heap[root]=heap[largechildindex];
heap[largechildindex]=hold;
reheapdown(heap,largechildindex,last);
}
}
}
void heap(int list[],int last)
{
int sorted;
int holddata;
int walker;
for(walker=1;walker<=last;walker++)
reheapup(list,walker);
sorted=last;
while(sorted>0)
{
holddata=list[0];
list[0]=list[sorted];
list[sorted]=holddata;
sorted--;
reheapdown(list,0,sorted);
}
}
void main()
{
int a[100],n,i;
clrscr();
printf("Enter number of elements in array: ");
scanf("%d",&n);
printf("\nEnter %d elements: \n\n",n);
for(i=0;i
scanf("%d",&a[i]);
}
heap(a,n-1);
printf("\n\nSorted list is:\n\n");
for(i=0;i
printf("%5d",a[i]);
}
getch();
}
/*
Output:
Enter number of elements in array: 6
Enter 6 elements:
89 23 44 39 1 27
Sorted list is:
1 23 27 39 44 89
*/
-------------------------------------------------------------------------------------
//2.1 SEQUENTIAL SEARCH
#include
#include
void main()
{
int i,j,x,d,t,flag;
int a[20];
clrscr();
printf("enter dimension :");
scanf("%d",&d);
printf("\nenter %d values:",d);
for(i=0;i
printf("\nelements of array a : \n");
for(i=0;i
printf("\n enter value to be searched :");
scanf("%d",&x);
for(i=0;i
if(x==a[i])
{
flag=1;
printf("%d is located at location %d",x,i+1);
break;
}
else
flag=0;
}
if(flag==0)
printf("%d element not present.",x);
getch();
}
-------------------------------------------------------------------------------------
//2.2 BINARYSEARCH
#include
#include
void main()
{
int i,j,x,d,t;
int low,high,mid;
int a[20];
clrscr();
printf("enter dimension :");
scanf("%d",&d);
printf("\nenter %d values:",d);
for(i=0;i
printf("\nelements of array a : \n");
for(i=0;i
for(i=0;i
for(j=i+1;j
if(a[i]>a[j])
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}
printf("\nsorted array a : \n");
for(i=0;i
printf("\n enter value to be searched :");
scanf("%d",&x);
low=0;
high=d;
while(low<=high)
{
mid=(low+high)/2;
if(x
else if(x>a[mid])
low=mid+1;
else if(x==a[mid])
{
printf("%d is located at location %d",x,mid+1);
break;
}
else
printf("element not present in the list");
}
getch();
}
-------------------------------------------------------------------------------------
/* Program of stack using array*/
#include
#include
#include
#include
#define MAX 5
int push();
int pop();
int display();
//int exit(int status);
int stacktop();
int top = -1;
int stack_arr[MAX];
main()
{
int choice;
clrscr();
while(1)
{
printf("1.Push\n");
printf("2.Pop\n");
printf("3.Display\n");
printf("4.Stack Top\n");
printf("5.Empty Stack\n");
printf("6.Full Stack\n");
printf("7.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1 :
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
stacktop();
break;
case 5:
emptyStack();
break;
case 6:
fullStack();
break;
case 7:
exit(1);
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of while*/
getch();
}/*End of main()*/
push()
{
int pushed_item;
if(top == (MAX-1))
printf("Stack Overflow\n");
else
{
printf("Enter the element to be pushed in stack : ");
scanf("%d",&pushed_item);
top=top+1;
stack_arr[top] = pushed_item;
printf("Element is successfully inserted");
}
}/*End of push()*/
pop()
{
if(top == -1)
printf("\nStack Underflow");
else
{
printf("\nPopped element is : %d",stack_arr[top]);
top=top-1;
}
}/*End of pop()*/
display()
{
int i;
if(top == -1)
printf("Stack is empty\n");
else
{
printf("Stack elements :\n");
for(i = top; i >=0; i--)
printf("%d\n", stack_arr[i]);
}
}/*End of display()*/
stacktop()
{
if(top==-1)
printf("\nstack is empty");
else
printf("\nstack top = %d",stack_arr[top]);
}
emptyStack()
{
if(top==-1)
printf("\nStack is empty");
else
printf("\nStack is not empty");
}
fullStack()
{
if(top==(MAX-1))
printf("\nStack is full ");
else
printf("\nStack is not full");
}
-------------------------------------------------------------------------------------
//STACK LINK LIST
#include
#include
#include
struct stack
{
int data;
struct stack *next;
};
struct stack *top=NULL,*tmp;
void push();
void pop();
void display();
void count();
void main()
{
int opt=0;
clrscr();
while(opt!=5)
{
printf("\n1 push\n 2 pop\n 3 count\n 4 display\n 5 exit\n");
scanf("%d",&opt);
switch(opt)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
count();
break;
case 4:
display();
break;
case 5:
exit();
break;
}
}
}
void push()
{
tmp=(struct stack *)malloc(sizeof(struct stack));
printf("enter element");
scanf("%d",tmp->data);
tmp->next=NULL;
top->next=tmp;
top=tmp;
}
void pop()
{
if(top==NULL)
printf("underflow");
else
{ int tmp;
tmp=top->data;
printf("\nvalue poped=%d\n",tmp);
free(top);
top=top->next;
// return(tmp);
}
}
void count()
{
int count=0;
if(top==NULL)
printf("stack is empty");
else
tmp=top;
while(tmp!=NULL)
count++;
printf("\ntotal elements=%d\n",count);
}
void display()
{
if(top==NULL)
printf("stack is empty");
else
{ tmp=top;
while(tmp!=NULL)
{
printf("elements are %d\n",tmp->data);
tmp=tmp->next;
}
}
}
-------------------------------------------------------------------------------------
//5 CIRCULAR QUEUE
#include
#include
#include
/*struct Qnode
{
int info;
struct Qnode *link;
}*front1=NULL,*rear1=NULL;
*/
void Insert(int);
void Delete();
void display();
int exit(int status);
int qarr[10];
int front=-1,rear=-1;
void Cir_QArr();
void main()
{
char ans;
int ch;
clrscr();
do
{
fflush(stdin);
Cir_QArr();break;
printf("Do you want to continue(y/n)");
scanf("%c",&ans);
}while(ans=='y');
getch();
}
void Cir_QArr()
{
int ch,no,i;
char ans;
printf("Enter the choice\n");
do
{
fflush(stdin);
printf(" 1)Insert a element\n 2)Remove Element\n 3)Display queue\n 4)Quit\n ");
scanf("%d",&ch);
switch(ch)
{
case 1:if((rear==9&&front==0)||(front==(rear+1)))
printf(" Queue is full");
else
{
printf("Enter element \n");
scanf("%d",&no);
if(front==-1)
{
front=0;
rear=0;
}
else
if(rear==9)
rear=0;
else
rear=rear+1;
qarr[rear]=no;
}
break;
case 2: if(front==rear)
{
front=-1;
rear=-1;
}
if (front==-1)
printf(" Queue is empty");
else
{
no=qarr[front];
if(front==9)
front=0;
else
front=front+1;
printf("Removed element is %d ",no);
} break;
case 3: if(front<0)
printf("Queue is empty");
else
{
printf("\n\tSTACK ELEMENTS \n");
if(front<=rear)
{
for(i=front;i<=rear;i++)
printf(" %d",qarr[i]);
}
else
{
i=front%10;
while(i!=rear)
{
printf(" %d",qarr[i]);
i++;
i=i%10;
}
printf(" %d",qarr[i]);
}
}
case 4: exit(0);
default:
printf("Wrong choice");
}
fflush(stdin);
printf("\nDo you want to continue(y/n)");
scanf("%c",&ans);
}while(ans=='y');
}
-------------------------------------------------------------------------------------
//SINGLY LINK LIST
#include
#include
#include
void add(int);
void display();
int count();
void insert(int,int);
void removeitem(int);
int search(int);
void sort(void);
void reverse();
struct node
{
int data;
struct node *link;
}*p;
void main()
{
int num,position,option;
p=NULL;
while(1)
{
clrscr();
printf("\n\t\t You can perform following operation \n\n");
printf("\n\t\t 1:Add an item");
printf("\n\t\t 2:Display");
printf("\n\t\t 3:Count list");
printf("\n\t\t 4:Insert ");
printf("\n\t\t 5:Remove");
printf("\n\t\t 6:Search");
printf("\n\t\t 7:Sort");
printf("\n\t\t 8:Reverse");
printf("\n\t\t 0:Exit");
printf("\n\t\t Enter Your option ");
scanf("%d",&option);
switch(option)
{
case 1:
printf("\n\n\tEnter a number: ");
scanf("%d",&num);
add(num);
//printf("\n\n\t\tPress any key to continue . . .");
getch();
break;
case 2:
display();
//printf("\n\n\t\t Press any key to continue . . .");
getch();
break;
case 3:
num=count();
printf("\n\n\t\tSize of your list is %d",num);
//printf("\n\n\t\t Press any key to continue . . .");
getch();
break;
case 4:
printf("\n\t\tEnter Position: ");
scanf("%d",&position);
if((position>=1)&&(position<=count()+1))
{
printf("\n\t\tEnter number: ");
scanf("%d",&num);
insert(position,num);
}
else
printf("\n\t\tInvalid Position!");
//printf("\n\n\t\tPress any key to continue . . .");
getch();
break;
case 5:
printf("\n\t\tEnter your position: ");
scanf("%d",&position);
if((position>=1)&&(position<=count()))
removeitem(position);
else
printf("\n\t\tInvalid Position!");
printf("\n\n\t\t Do you want to continue . . .");
getch();
break;
case 6:
printf("\n\n\t\tEntered the numbere to be searched: ");
scanf("%d",&num);
position=search(num);
if(position==-1)
printf("\n\t\tNumber not found!");
else
printf("\n\t\tnumber found at position %d",position );
//printf("\n\n\t\tPress any key to continue . . .");
getch();
break;
case 7:
sort();
printf("\n\n\t\tFinished sorting.");
display();
//printf("\n\n\t\tPress any key to continue . . .");
break;
case 8:
reverse();
printf("\n\n\t\tLink list reversed");
display();
//printf("\n\n\t\tPress any key to continue . . .");
getch();
break;
case 0:
exit(0);
default:
printf("\n \t\t Invalid Option! ");
}
}
}
void add(int n)
{
struct node *q=p;
if(p==NULL)
{
p=(struct node *)malloc(sizeof(struct node));
p->data=n;
p->link=NULL;
}
else
{
while(q->link!=NULL)
q=q->link;
q->link=(struct node *)malloc(sizeof(struct node));
q->link->data=n;
q->link->link=NULL;
}
printf("\n\n\tNode added successfully.");
}
void display()
{
struct node *q=p;
if(p==NULL)
printf("No linked list exists");
else
{
printf("\n\n");
while(q!=NULL)
{
printf("%d ",q->data);
q=q->link;
}
}
printf("\n\n\tFinished displaying linked list.");
}
int count()
{
struct node *q=p;
int i=0;
if(p==NULL)
return 0;
else
{
while(q!=NULL)
{
q=q->link;
i++;
}
}
return i;
}
void insert(int position,int num)
{
struct node *q=p;
struct node *temp;
int i;
if(position==1)
{
p=(struct node *)malloc(sizeof(struct node));
p->data=num;
p->link=q;
}
else if(position==1+count())
{
add(num);
}
else
{
for(i=1;i<=position-2;i++)
q=q->link;
temp=q->link;
q->link=(struct node*)malloc(sizeof(struct node));
q->link->data=num;
q->link->link=temp;
}
}
void removeitem(int pos)
{
struct node *q=p,*temp;
int i;
if(pos==1)
{
p=p->link;
free(q);
}
for(i=1;i<=pos-2;i++)
q=q->link;
temp=q->link;
q->link=q->link->link;
free(temp);
printf("\n\n\t\tNumber removed successfully.");
}
int search(int num)
{
int flag=0;
int position=1;
struct node *q=p;
while(q!=NULL)
{
if(q->data==num)
{
flag=1;
break;
}
position++;
q=q->link;
}
if(flag==1)
return position;
else
return -1;
}
void sort()
{
int temp;
struct node *i,*j;
for(i=p;i!=NULL;i=i->link)
{
for(j=i->link;j!=NULL;j=j->link)
{
if(i->data > j->data)
{
temp=i->data;
i->data=j->data;
j->data=temp;
}
}
}
}
void reverse()
{
struct node *q=p, *temp;
p=p->link;
q->link=NULL;
while(p->link!=NULL)
{
temp=p->link;
p->link=q;
q=p;
p=temp;
}
p->link=q;
}
-------------------------------------------------------------------------------------
//Circular Linked List
#include
#include
typedef struct lnk_lst
{
int data;
struct lnk_lst *next;
};
typedef struct lnk_lst node;
void add_at_end(node **q,int no)
{
node *temp,*r;
if(*q==NULL)
{
temp=(node *)malloc(sizeof(node));
temp->data=no;
*q=temp;
temp->next=*q;
}
else
{
temp=*q;
while(temp->next!=*q)
temp=temp->next;
r=(node*)malloc(sizeof(node));
r->data=no;
r->next=*q;
temp->next=r;
}
}
void del(node **q,int no)
{
node *temp,*old,*last;
last=*q;
while(last->next!=*q)
last=last->next;
temp=*q;
old=NULL;
do
{
old=temp;
temp=temp->next;
}
while(temp->data!=no && temp!=(*q));
if(temp==*q)
{
*q=temp->next;
last->next=*q;
}
else if(temp!=(*q))
old->next=temp->next;
}
int traverse(node *q)
{
int c=0;
while(q!=NULL)
{
q=q->next;
c++;
}
return(c);
}
void display(node *q)
{
node *temp;
temp=q;
printf("\n\n");
do
{
printf("%5d",temp->data);
temp=temp->next;
}
while(temp!=q);
}
void main()
{
node *head=NULL;
int ch,n,loc;
while(1)
{
clrscr();
printf("1. Add an element\n");
printf("2. Display\n");
printf("3. Delete an element\n");
printf("4. Traverse\n");
printf("5. Exit\n");
printf("\nEnter your choice: ");
scanf("%d",&ch);
if(ch==1 || ch==3)
{
printf("\nEnter element: ");
scanf("%d",&n);
}
switch(ch)
{
case 1:
add_at_end(&head,n);
display(head);
break;
case 2:
display(head);
break;
case 3:
del(&head,n);
display(head);
break;
case 4:
printf("\n\nElements in list = %d",traverse(head));
break;
case 5:
exit(0);
default:
printf("\nWrong choice");
}
getch();
}
}
/*
Output:
1. Add an element
2. Display
3. Delete an element
4. Count number of elements
5. Exit
Enter your choice: 1
Enter element: 201
201
Enter your choice: 1
Enter element: 202
201 202
1. Add an element
2. Display
3. Delete an element
4. Count number of elements
5. Exit
Enter your choice: 1
Enter element: 203
201 202 203
Enter your choice: 3 ( delete )
Enter element: 202
201 203
*/
-------------------------------------------------------------------------------------
//Doubly Linked List
#include
#include
typedef struct lnk_lst
{
int data;
struct lnk_lst *next;
struct lnk_lst *prev;
};
typedef struct lnk_lst node;
void add_at_end(node **q,int no)
{
node *temp,*r;
if(*q==NULL)
{
temp=(node *)malloc(sizeof(node));
temp->data=no;
temp->next=NULL;
temp->prev=NULL;
*q=temp;
}
else
{
temp=*q;
while(temp->next!=NULL)
temp=temp->next;
r=(node*)malloc(sizeof(node));
r->data=no;
r->next=NULL;
r->prev=temp;
temp->next=r;
}
}
void add_at_beg(node **q,int no)
{
node *temp;
temp=(node*)malloc(sizeof(node));
temp->data=no;
temp->next=*q;
(*q)->prev=temp;
*q=temp;
}
void add_after_loc(node **q,int no,int loc)
{
node *temp,*r;
int i;
temp=*q;
for(i=0;i
temp=temp->next;
if(temp==NULL)
{
printf("There are less elements");
return;
}
}
r=(node*)malloc(sizeof(node));
r->data=no;
r->next=temp->next;
r->prev=temp;
temp->next->prev=r;
temp->next=r;
}
void del(node **q,int no)
{
node *temp,*old;
temp=*q;
old=NULL;
while(temp->data!=no && temp!=NULL)
{
old=temp;
temp=temp->next;
}
if(temp==*q)
{
*q=temp->next;
(*q)->prev=NULL;
}
else if(temp!=NULL)
{
old->next=temp->next;
temp->next->prev=old;
}
}
int count(node *q)
{
int c=0;
while(q!=NULL)
{
q=q->next;
c++;
}
return(c);
}
void display(node *q)
{
printf("\n\nLinked List:\n\n");
while(q!=NULL)
{
printf("%5d",q->data);
q=q->next;
}
}
void main()
{
node *head=NULL;
int ch,n,loc;
while(1)
{
clrscr();
printf("1. Add at end\n");
printf("2. Add at beginning\n");
printf("3. Add after location\n");
printf("4. Display\n");
printf("5. Delete an element\n");
printf("6. Count number of elements\n");
printf("7. Exit\n");
printf("\nEnter your choice: ");
scanf("%d",&ch);
if(ch==1 || ch==2 || ch==3 || ch==5)
{
printf("\nEnter element: ");
scanf("%d",&n);
}
switch(ch)
{
case 1:
add_at_end(&head,n);
display(head);
break;
case 2:
add_at_beg(&head,n);
display(head);
break;
case 3:
printf("\nEnter location: ");
scanf("%d",&loc);
add_after_loc(&head,n,loc);
display(head);
break;
case 4:
display(head);
break;
case 5:
del(&head,n);
display(head);
break;
case 6:
printf("\n\nElements in list = %d",count(head));
break;
default:
exit(0);
}
getch();
}
}
-------------------------------------------------------------------------------------
//12 Adjmatrix del
#include
#define max 20
int adj[max][max],n;
void main()
{ int choice,node,origin,destin;
create_graph();
while(1)
{ printf("1.Insert a node\n2.Insert an edge\n ");
printf("3.Delete a node\n4.Delete an edge\n");
printf("5.Dispaly\n6.Exit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{ case 1: insert_node(); break;
case 2: printf("Enter an edge to be inserted : ");
fflush(stdin);
scanf("%d %d",&origin,&destin);
insert_edge(origin,destin); break;
case 3: printf("Enter a node to be deleted : ");
fflush(stdin);
scanf("%d",&node);
delete_node(node);break;
case 4: printf("Enter an edge to be deleted : ");
fflush(stdin);
scanf("%d %d",&origin,&destin);
del_edge(origin,destin);break;
case 5: display(); break;
case 6: exit();
default: printf("Wrong choice\n");break;
}/*End of switch*/
}/*End of while*/
}/*End of main()*/
create_graph()
{
int i,max_edges,origin,destin;
printf("Enter number of nodes : ");
scanf("%d",&n);
max_edges=n*(n-1); /* Taking directed graph */
for(i=1;i<=max_edges;i++)
{
printf("Enter edge %d( 0 0 ) to quit : ",i);
scanf("%d %d",&origin,&destin);
if((origin==0) && (destin==0))
break;
if( origin > n || destin > n || origin<=0 || destin<=0)
{
printf("Invalid edge!\n");
i--;
}
else
adj[origin][destin]=1;
}/*End of for*/
}/*End of create_graph()*/
display()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%4d",adj[i][j]);
printf("\n");
}
}/*End of display()*/
insert_node()
{
int i;
n++; /*Increase number of nodes in the graph*/
printf("The inserted node is %d \n",n);
for(i=1;i<=n;i++)
{
adj[i][n]=0;
adj[n][i]=0;
}
}/*End of insert_node()*/
delete_node(char u)
{
int i,j;
if(n==0)
{ printf("Graph is empty\n");
return;
}
if( u>n )
{ printf("This node is not present in the graph\n");
return;
}
for(i=u;i<=n-1;i++)
for(j=1;j<=n;j++)
{
adj[j][i]=adj[j][i+1]; /* Shift columns left */
adj[i][j]=adj[i+1][j]; /* Shift rows up */
}
n--; /*Decrease the number of nodes in the graph */
}/*End of delete_node*/
insert_edge(char u,char v)
{
if(u > n)
{
printf("Source node does not exist\n");
return;
}
if(v > n)
{
printf("Destination node does not exist\n");
return;
}
adj[u][v]=1;
}/*End of insert_edge()*/
del_edge(char u,char v)
{
if(u>n || v>n || adj[u][v]==0)
{
printf("This edge does not exist\n");
return;
}
adj[u][v]=0;
}/*End of del_edge()*/
-------------------------------------------------------------------------------------
//12.1 adj_matrix
#include
#define max 20
int adj[ max ][ max ]; /*Adjacency matrix */
int n; /* Denotes number of nodes in the graph */
main()
{
int max_edges, i, j, origin, destin;
char graph_type;
printf( "Enter number of nodes : " );
scanf( "%d", &n );
printf( "Enter type of graph, directed or undirected (d/u) : " );
fflush( stdin );
scanf( "%c", &graph_type );
if ( graph_type == 'u' )
max_edges = n * ( n - 1 ) / 2;
else
max_edges = n * ( n - 1 );
for ( i = 1;i <= max_edges;i++ )
{
printf( "Enter edge %d( 0 0 to quit ) : ", i );
scanf( "%d %d", &origin, &destin );
if ( ( origin == 0 ) && ( destin == 0 ) )
break;
if ( origin > n || destin > n || origin <= 0 || destin <= 0 )
{
printf( "Invalid edge!\n" );
i--;
}
else
{
adj[ origin ][ destin ] = 1;
if ( graph_type == 'u' )
adj[ destin ][ origin ] = 1;
}
} /*End of for*/
printf( "The adjacency matrix is :\n" );
for ( i = 1;i <= n;i++ )
{
for ( j = 1;j <= n;j++ )
printf( "%4d", adj[ i ][ j ] );
printf( "\n" );
}
} /*End of main()*/
-------------------------------------------------------------------------------------
//12.2 adj_lst
#include
struct edge;
struct node
{
struct node *next;
char name;
struct edge *adj;
}*start = NULL;
struct edge
{
char dest;
struct edge *link;
};
struct node *find( char item );
main()
{
int choice;
char node, origin, destin;
while ( 1 )
{
printf( "1.Insert a node\n" );
printf( "2.Insert an edge\n" );
printf( "3.Delete a node\n" );
printf( "4.Delete an edge\n" );
printf( "5.Display\n" );
printf( "6.Exit\n" );
printf( "Enter your choice : " );
scanf( "%d", &choice );
switch ( choice )
{
case 1:
printf( "Enter a node to be inserted : " );
fflush( stdin );
scanf( "%c", &node );
insert_node( node );
break;
case 2:
printf( "Enter an edge to be inserted : " );
fflush( stdin );
scanf( "%c %c", &origin, &destin );
insert_edge( origin, destin );
break;
case 3:
printf( "Enter a node to be deleted : " );
fflush( stdin );
scanf( "%c", &node );
/*This fn deletes the node from header node list*/
delete_node( node );
/* This fn deletes all edges coming to this node */
delnode_edge( node );
break;
case 4:
printf( "Enter an edge to be deleted : " );
fflush( stdin );
scanf( "%c %c", &origin, &destin );
del_edge( origin, destin );
break;
case 5:
display();
break;
case 6:
exit();
default:
printf( "Wrong choice\n" );
break;
} /*End of switch*/
} /*End of while*/
} /*End of main()*/
insert_node( char node_name )
{
struct node * tmp, *ptr;
tmp = malloc( sizeof( struct node ) );
tmp->name = node_name;
tmp->next = NULL;
tmp->adj = NULL;
if ( start == NULL )
{
start = tmp;
return ;
}
ptr = start;
while ( ptr->next != NULL )
ptr = ptr->next;
ptr->next = tmp;
} /*End of insert_node()*/
delete_node( char u )
{
struct node * tmp, *q;
if ( start->name == u )
{
tmp = start;
start = start->next; /* first element deleted */
free( tmp );
return ;
}
q = start;
while ( q->next->next != NULL )
{
if ( q->next->name == u ) /* element deleted in between */
{
tmp = q->next;
q->next = tmp->next;
free( tmp );
return ;
}
q = q->next;
} /*End of while*/
if ( q->next->name == u ) /* last element deleted */
{
tmp = q->next;
free( tmp );
q->next = NULL;
}
} /*End of delete_node()*/
delnode_edge( char u )
{
struct node * ptr;
struct edge *q, *start_edge, *tmp;
ptr = start;
while ( ptr != NULL )
{
/* ptr->adj points to first node of edge linked list */
if ( ptr->adj->dest == u )
{
tmp = ptr->adj;
ptr->adj = ptr->adj->link; /* first element deleted */
free( tmp );
continue; /* continue searching in another edge lists */
}
q = ptr->adj;
while ( q->link->link != NULL )
{
if ( q->link->dest == u ) /* element deleted in between */
{
tmp = q->link;
q->link = tmp->link;
free( tmp );
continue;
}
q = q->link;
} /*End of while*/
if ( q->link->dest == u ) /* last element deleted */
{
tmp = q->link;
free( tmp );
q->link = NULL;
}
ptr = ptr->next;
} /*End of while*/
} /*End of delnode_edge()*/
insert_edge( char u, char v )
{
struct node * locu, *locv;
struct edge *ptr, *tmp;
locu = find( u );
locv = find( v );
if ( locu == NULL )
{
printf( "Source node not present ,first insert node %c\n", u );
return ;
}
if ( locv == NULL )
{
printf( "Destination node not present ,first insert node %c\n", v );
return ;
}
tmp = malloc( sizeof( struct edge ) );
tmp->dest = v;
tmp->link = NULL;
if ( locu->adj == NULL ) /* item added at the begining */
{
locu->adj = tmp;
return ;
}
ptr = locu->adj;
while ( ptr->link != NULL )
ptr = ptr->link;
ptr->link = tmp;
} /*End of insert_edge()*/
struct node *find( char item )
{
struct node *ptr, *loc;
ptr = start;
while ( ptr != NULL )
{
if ( item == ptr->name )
{
loc = ptr;
return loc;
}
else
ptr = ptr->next;
}
loc = NULL;
return loc;
} /*End of find()*/
del_edge( char u, char v )
{
struct node * locu, *locv;
struct edge *ptr, *tmp, *q;
locu = find( u );
if ( locu == NULL )
{
printf( "Source node not present\n" );
return ;
}
if ( locu->adj->dest == v )
{
tmp = locu->adj;
locu->adj = locu->adj->link; /* first element deleted */
free( tmp );
return ;
}
q = locu->adj;
while ( q->link->link != NULL )
{
if ( q->link->dest == v ) /* element deleted in between */
{
tmp = q->link;
q->link = tmp->link;
free( tmp );
return ;
}
q = q->link;
} /*End of while*/
if ( q->link->dest == v ) /* last element deleted */
{
tmp = q->link;
free( tmp );
q->link = NULL;
return ;
}
printf( "This edge not present in the graph\n" );
} /*End of del_edge()*/
display()
{
struct node * ptr;
struct edge *q;
ptr = start;
while ( ptr != NULL )
{
printf( "%c ->", ptr->name );
q = ptr->adj;
while ( q != NULL )
{
printf( " %c", q->dest );
q = q->link;
}
printf( "\n" );
ptr = ptr->next;
}
} /*End of display()*/
-------------------------------------------------------------------------------------
//13 DpthFS using adj matrix
#include
#define MAX 20
typedef enum boolean{false,true} bool;
int adj[MAX][MAX],n; /* Denotes number of nodes in the graph */
bool visited[MAX];
void main()
{ int i,v,choice;
create_graph();
while(1)
{ printf("\n1. Adjacent vertices\n2. Depth First Search using stack\n");
printf("3. Exit\nEnter your choice : ");
scanf("%d",&choice);
switch(choice)
{ case 1:printf("Enter node to find adjacent vertices : ");
scanf("%d", &v);
printf("Adjacent Vertices are : ");
adj_nodes(v);break;
case 2:printf("Enter starting node for Depth First Search : ");
scanf("%d",&v);
for(i=1;i<=n;i++)
visited[i]=false;
dfs(v);break;
case 3:exit(1);
default:printf("Wrong choice\n");break;
}/*End of switch*/
}/*End of while*/
}/*End of main()*/
create_graph()
{ int i,max_edges,origin,destin;
printf("Enter number of nodes : ");
scanf("%d",&n);
max_edges=n*(n-1);
for(i=1;i<=max_edges;i++)
{ printf("Enter edge %d( 0 0 to quit ) : ",i);
scanf("%d %d",&origin,&destin);
if((origin==0) && (destin==0))
break;
if( origin > n || destin > n || origin<=0 || destin<=0)
{ printf("Invalid edge!\n");
i--;
}
else
{ adj[origin][destin]=1;
}
}
}/*End of create_graph()*/
adj_nodes(int v)
{ int i;
for(i=1;i<=n;i++)
if(adj[v][i]==1)
printf("%d ",i);
printf("\n");
}/*End of adj_nodes()*/
dfs(int v)
{ int i,stack[MAX],top=-1,pop_v,j,t;
int ch; top++; stack[top]=v;
while (top>=0)
{ pop_v=stack[top];
top--; /*pop from stack*/
if( visited[pop_v]==false)
{ printf("%d ",pop_v);
visited[pop_v]=true;
}
else
continue;
for(i=n;i>=1;i--)
{ if( adj[pop_v][i]==1 && visited[i]==false)
{ top++; /* push all unvisited neighbours of pop_v */
stack[top]=i;
}/*End of if*/
}/*End of for*/
}/*End of while*/
}/*End of dfs()*/
-------------------------------------------------------------------------------------
//21) Program for Depth first search
#include
#include
#define MAX 10
void buildgraph(int [][MAX],int);
void dfs(int, int [][MAX], int [], int);
void main()
{
int n, adj[MAX][MAX], i, visit[MAX];
clrscr();
printf("Enter number of nodes: ");
scanf("%d", &n);
buildgraph(adj, n);
for(i=0;i
visit[i]=0;
}
for(i=0;i
if(visit[i]==0)
dfs(i,adj,visit,n);
}
getch();
}
void buildgraph(int adj[][MAX], int n)
{
int i,j;
for(i=0;i
for(j=0;j
printf("Enter 1/0 for [%d][%d]", i,j);
scanf("%d", &adj[i][j]);
}
}
}
void dfs(int i, int adj[][MAX], int visit[], int n)
{
int j;
visit[i]=1;
printf("\nVisited %d",i);
for(j=0;j
if(visit[j]==0 && adj[i][j]==1)
dfs(j,adj,visit,n);
}
}
-------------------------------------------------------------------------------------
//20) Program for Breadth first search
#include
#include
#include
struct node
{
int data;
struct node *link;
};
void buildgraph(int[][10],int);
struct node *addqueue(int,struct node*);
struct node *delqueue(struct node*,int*);
void bfs(int[][10],int[],int,int,struct node*);
void main()
{
int adj[10][10],n,visit[10],i;
struct node *q=NULL;
clrscr();
printf("enter no. of nodes");
scanf("%d",&n);
buildgraph(adj,n);
for(i=0;i
for(i=0;i
if(visit[i] == 0)
bfs(adj,visit,i,n,q);
}
getch();
}
void buildgraph(int adj[][10], int n)
{
int i,j;
for(i=0;i
for(j=0;j
printf("Enter 1/0 for [%d][%d]", i,j);
scanf("%d", &adj[i][j]);
}
}
}
struct node *addqueue(int x, struct node *q)
{
struct node *t,*temp;
t=(struct node *)malloc(sizeof(struct node));
t->data=x;
t->link=NULL;
if(q == NULL)
q=t;
else
{
temp=q;
while(temp->link!=NULL)
temp=temp->link;
temp->link=t;
}
return q;
}
struct node *delqueue(struct node *q, int *x)
{
struct node *temp;
if(q==NULL)
return NULL;
*x=q->data;
q=q->link;
return q;
}
void bfs(int adj[][10], int visit[], int x, int n,struct node *q)
{
int j,*y,k;
q=addqueue(x,q);
q=delqueue(q,y);
k=*y;
do
{
if(visit[k] == 0)
{
visit[k]=1;
printf("\nvisited %d",k);
}
for(j=0;j
if(visit[j]==0 && adj[k][j]==1)
q=addqueue(j,q);
}
q=delqueue(q,y);
}while(q!=NULL);
}
-------------------------------------------------------------------------------------
//14 prims mst
#include
#include
#define MAX 10
#define TEMP 0
#define PERM 1
#define FALSE 0
#define TRUE 1
#define infinity 9999
struct node
{
int predecessor, status,dist; /*Distance from predecessor */
};
struct edge
{
int u,v;
};
int adj[MAX][MAX];
int n;
void main()
{ int i,j,path[MAX],wt_tree,count;
struct edge tree[MAX];
// clrscr();
create_graph();
printf("Adjacency matrix is :\n");
display();
count = maketree(tree,&wt_tree);
printf("Weight of spanning tree is : %d\n", wt_tree);
printf("Edges to be included in spanning tree are : \n");
for(i=1;i<=count;i++)
{ printf("%d->",tree[i].u);
printf("%d\n",tree[i].v);
}
}/*End of main()*/
create_graph()
{ int i,max_edges,origin,destin,wt;
printf("Enter number of vertices : ");
scanf("%d",&n);
max_edges=n*(n-1)/2;
for(i=1;i<=max_edges;i++)
{ printf("Enter edge %d(0 0 to quit) : ",i);
scanf("%d %d",&origin,&destin);
if((origin==0) && (destin==0))
break;
printf("Enter weight for this edge : ");
scanf("%d",&wt);
if( origin > n || destin > n || origin<=0 || destin<=0)
{ printf("Invalid edge!\n");
i--;
}
else
{ adj[origin][destin]=wt;
adj[destin][origin]=wt;
}
}/*End of for*/
if(i
exit(1);
}
}/*End of create_graph()*/
display()
{ int i,j;
for(i=1;i<=n;i++)
{ for(j=1;j<=n;j++)
printf("%3d",adj[i][j]);
printf("\n");
}
}/*End of display()*/
int all_perm(struct node state[MAX] )
{ int i;
for(i=1;i<=n;i++)
if( state[i].status == TEMP )
return FALSE;
return TRUE;
}/*End of all_perm()*/
int maketree(struct edge tree[MAX],int *weight)
{
struct node state[MAX];
int i,k,min,count,current,newdist,m,u1,v1;
*weight=0;
for(i=1;i<=n;i++)
{
state[i].predecessor=0;
state[i].dist = infinity;
state[i].status = TEMP;
}
state[1].predecessor=0;
state[1].dist = 0;
state[1].status = PERM;
/*Start from first node*/
current=1;
count=0; /*count represents number of nodes in tree */
while( all_perm(state) != TRUE ) /*Loop till all the nodes become PERM*/
{ for(i=1;i<=n;i++)
{ if ( adj[current][i] > 0 && state[i].status == TEMP )
{ if( adj[current][i] < state[i].dist )
{ state[i].predecessor = current;
state[i].dist = adj[current][i];
}
}
}/*End of for*/
min=infinity;
for(i=1;i<=n;i++)
{ if(state[i].status == TEMP && state[i].dist < min)
{
min = state[i].dist;
current=i;
}
}/*End of for*/
state[current].status=PERM;
u1=state[current].predecessor;
v1=current;
count++;
tree[count].u=u1;
tree[count].v=v1;
*weight=*weight+adj[u1][v1];
}/*End of while*/
return (count);
}/*End of maketree()*/
-------------------------------------------------------------------------------------
/* Program for creating a minimum spanning tree from Kruskal's algorithm */
#include
#define MAX 20
struct edge
{
int u,v,weight;
struct edge *link;
}*front = NULL;
int father[MAX]; /*Holds father of each node */
struct edge tree[MAX]; /* Will contain the edges of spanning tree */
int n; /*Denotes total number of nodes in the graph */
int wt_tree=0; /*Weight of the spanning tree */
int count=0; /* Denotes number of edges included in the tree */
void make_tree();
void insert_tree(int i,int j,int wt); /*Inserting an edge in the tree */
void insert_pque(int i,int j,int wt); /*Inserting edges in the priority queue */
struct edge *del_pque();/*Deleting an edge from the priority queue*/
void main()
{
int i;
create_graph();
make_tree();
printf("Edges to be included in spanning tree are :\n");
for(i=1;i<=count;i++)
{
printf("%d->",tree[i].u);
printf("%d\n",tree[i].v);
}
printf("Weight of this minimum spanning tree is : %d\n", wt_tree);
}/*End of main()*/
create_graph()
{
int i,wt,max_edges,origin,destin;
printf("Enter number of nodes : ");
scanf("%d",&n);
max_edges=n*(n-1)/2;
for(i=1;i<=max_edges;i++)
{ printf("Enter edge %d(0 0 to quit): ",i);
scanf("%d %d",&origin,&destin);
if( (origin==0) && (destin==0) )
break;
printf("Enter weight for this edge : ");
scanf("%d",&wt);
if( origin > n || destin > n || origin<=0 || destin<=0)
{ printf("Invalid edge!\n");
i--;
}
else
insert_pque(origin,destin,wt);
}/*End of for*/
if(i
exit(1);
}
}/*End of create_graph()*/
void make_tree()
{
struct edge *tmp;
int node1,node2,root_n1,root_n2;
while( count < n-1) /*Loop till n-1 edges included in the tree*/
{ tmp=del_pque();
node1=tmp->u;
node2=tmp->v;
printf("n1=%d ",node1);
printf("n2=%d ",node2);
while( node1 > 0)
{ root_n1=node1;
node1=father[node1];
}
while( node2 >0 )
{ root_n2=node2;
node2=father[node2];
}
printf("rootn1=%d ",root_n1);
printf("rootn2=%d\n",root_n2);
if(root_n1!=root_n2)
{ insert_tree(tmp->u,tmp->v,tmp->weight);
wt_tree=wt_tree+tmp->weight;
father[root_n2]=root_n1;
}
}/*End of while*/
}/*End of make_tree()*/
void insert_tree(int i,int j,int wt)
{ printf("This edge inserted in the spanning tree\n");
count++;
tree[count].u=i;
tree[count].v=j;
tree[count].weight=wt;
}/*End of insert_tree()*/
void insert_pque(int i,int j,int wt)
{ struct edge *tmp,*q;
tmp = (struct edge *)malloc(sizeof(struct edge));
tmp->u=i; tmp->v=j; tmp->weight = wt;
/*Queue is empty or edge to be added has weight less than first edge*/
if( front == NULL || tmp->weight < front->weight )
{ tmp->link = front;
front = tmp;
}
else
{ q = front;
while( q->link != NULL && q->link->weight <= tmp->weight )
q=q->link;
tmp->link = q->link; q->link = tmp;
if(q->link == NULL) /*Edge to be added at the end*/
tmp->link = NULL;
}/*End of else*/
}/*End of insert_pque()*/
struct edge *del_pque()
{ struct edge *tmp;
tmp = front;
printf("Edge processed is %d->%d %d\n",tmp->u,tmp->v,tmp->weight);
front = front->link;
return tmp;
}/*End of del_pque()*/
-------------------------------------------------------------------------------------
//16 DijkstraSP
#include
#define MAX 10
#define TEMP 0
#define PERM 1
#define infinity 9999
struct node
{ int predecessor,status;
int dist; /*minimum distance of node from source*/
};
int adj[MAX][MAX]; int n;
void main()
{ int i,j,source,dest,shortdist,count,path[MAX];
create_graph();
printf("The adjacency matrix is :\n");
display();
while(1)
{ printf("Enter source node(0 to quit) : ");
scanf("%d",&source);
printf("Enter destination node(0 to quit) : ");
scanf("%d",&dest);
if(source==0 || dest==0)
exit(1);
count = findpath(source,dest,path,&shortdist);
if(shortdist!=0)
{ printf("Shortest distance is : %d\n Shortest Path is : ", shortdist);
for(i=count;i>1;i--) printf("%d->",path[i]);
printf("%d\n ",path[i]);
}
else
printf("There is no path from source to destination node\n");
}/*End of while*/
}/*End of main()*/
create_graph()
{ int i,max_edges,origin,destin,wt;
printf("Enter number of vertices : ");
scanf("%d",&n);
max_edges=n*(n-1);
for(i=1;i<=max_edges;i++)
{ printf("Enter edge %d(0 0 to quit) : ",i);
scanf("%d %d",&origin,&destin);
if((origin==0) && (destin==0))
break;
printf("Enter weight for this edge : ");
scanf("%d",&wt);
if( origin > n || destin > n || origin<=0 || destin<=0)
{ printf("Invalid edge!\n");
i--;
}
else
adj[origin][destin]=wt;
}/*End of for*/
}/*End of create_graph()*/
display()
{ int i,j;
for(i=1;i<=n;i++)
{ for(j=1;j<=n;j++)
printf("%3d",adj[i][j]);
printf("\n");
}
}/*End of display()*/
int findpath(int s,int d,int path[MAX],int *sdist)
{ struct node state[MAX];
int i,min,count=0,current,newdist,u,v;
*sdist=0;
/* Make all nodes temporary */
for(i=1;i<=n;i++)
{ state[i].predecessor=0;
state[i].dist = infinity;
state[i].status = TEMP;
}
/*Source node should be permanent*/
state[s].predecessor=0;
state[s].dist = 0;
state[s].status = PERM;
/*Starting from source node until destination is found*/
current=s;
while(current!=d)
{ for(i=1;i<=n;i++)
{ /*Checks for adjacent temporary nodes */
if ( adj[current][i] > 0 && state[i].status == TEMP )
{ newdist=state[current].dist + adj[current][i];
/*Checks for Relabeling*/
if( newdist < state[i].dist )
{ state[i].predecessor = current;
state[i].dist = newdist;
}
}
}/*End of for*/
/*Search for temporary node with minimum distand make it current node*/
min=infinity;
current=0;
for(i=1;i<=n;i++)
{ if(state[i].status == TEMP && state[i].dist < min)
{ min = state[i].dist;
current=i;
}
}/*End of for*/
if(current==0) /*If Source or Sink node is isolated*/
return 0;
state[current].status=PERM;
}/*End of while*/
/* Getting full path in array from destination to source */
while( current!=0 )
{
count++;
path[count]=current;
current=state[current].predecessor;
}
/*Getting distance from source to destination*/
for(i=count;i>1;i--)
{
u=path[i];
v=path[i-1];
*sdist+= adj[u][v];
}
return (count);
}/*End of findpath()*/
-------------------------------------------------------------------------------------
//17 warshall's spt matrix
#include
#define infinity 9999
#define MAX 20
main()
{
int i, j, k, n;
int adj[ MAX ][ MAX ], path[ MAX ][ MAX ];
printf( "Enter number of vertices : " );
scanf( "%d", &n );
printf( "Enter weighted matrix :\n" );
for ( i = 0;i < n;i++ )
for ( j = 0;j < n;j++ )
scanf( "%d", &adj[ i ][ j ] );
printf( "Weighted matrix is :\n" );
display( adj, n );
/*Replace all zero entries of adjacency matrix with infinity*/
for ( i = 0;i < n;i++ )
for ( j = 0;j < n;j++ )
if ( adj[ i ][ j ] == 0 )
path[ i ][ j ] = infinity;
else
path[ i ][ j ] = adj[ i ][ j ];
for ( k = 0;k < n;k++ )
{
printf( "Q%d is :\n", k );
display( path, n );
for ( i = 0;i < n;i++ )
for ( j = 0;j < n;j++ )
path[ i ][ j ] = minimum( path[ i ][ j ] , path[ i ][ k ] + path[ k ][ j ] );
}
printf( "Shortest path matrix Q%d is :\n", k );
display( path, n );
} /*End of main() */
minimum( int a, int b )
{
if ( a <= b )
return a;
else
return b;
} /*End of minimum()*/
display( int matrix[ MAX ][ MAX ], int n )
{
int i, j;
for ( i = 0;i < n;i++ )
{
for ( j = 0;j < n;j++ )
printf( "%7d", matrix[ i ][ j ] );
printf( "\n" );
}
} /*End of display()*/
-------------------------------------------------------------------------------------
//priority queue
#include
#include
#include
struct Qnode
{
int info;
struct Qnode *link;
}*front1=NULL,*rear1=NULL;
void Insert(int);
void Delete();
void display();
int qarr[10];
int front=-1,rear=-1;
void Cir_QArr();
void Cir_Qlink();
void main()
{
char ans;
int ch;
clrscr();
printf("Enter the choice\n");
do
{
fflush(stdin);
printf("Enter 1)Circular Queue usin Array 2)Circular Queue using Linked list\n");
scanf("%d",&ch);
switch(ch)
{
case 1:Cir_QArr();break;
case 2:Cir_Qlink(); break;
}
fflush(stdin);
printf("Do you want to continue(y/n)");
scanf("%c",&ans);
}while(ans=='y');
getch();
}
void Cir_QArr()
{
int ch,no,i;
char ans;
printf("Circular Queue using Array\n");
printf("Enter the choice\n");
do
{
fflush(stdin);
printf("Enter 1)Insert a element 2)Remove Element 3) Display queue\n");
scanf("%d",&ch);
switch(ch)
{
case 1:if((rear==9&&front==0)||(front==(rear+1)))
printf(" Queue is full");
else
{
printf("Enter element \n");
scanf("%d",&no);
if(front==-1)
{
front=0;
rear=0;
}
else
if(rear==9)
rear=0;
else
rear=rear+1;
qarr[rear]=no;
}
break;
case 2: if(front==rear)
{
front=-1;
rear=-1;
}
if (front==-1)
printf(" Queue is empty");
else
{
no=qarr[front];
if(front==9)
front=0;
else
front=front+1;
printf("Removed element is %d ",no);
} break;
case 3: if(front<0)
printf("Queue is empty");
else
{
printf("\n\tSTACK ELEMENTS \n");
if(front<=rear)
{
for(i=front;i<=rear;i++)
printf(" %d",qarr[i]);
}
else
{
i=front%10;
while(i!=rear)
{
printf(" %d",qarr[i]);
i++;
i=i%10;
}
printf(" %d",qarr[i]);
}
}
}
fflush(stdin);
printf("\nDo you want to continue(y/n)");
scanf("%c",&ans);
}while(ans=='y');
}
void Cir_Qlink()
{
int ch,no;
char ans;
printf("Circular Queue using Linked list\n");
printf("Enter your choice: \n");
do
{
fflush(stdin);
printf("enter 1)Insert 2)Delete 3)Display \n");
scanf("%d",&ch);
switch(ch)
{
case 1:printf("enter no: " );
scanf("%d",&no);
Insert(no);
break;
case 2:Delete();
break;
case 3:display();
}
fflush(stdin);
printf("Do you want to continue(y/n)\n");
scanf("%c",&ans);
}while(ans=='y');
}
void Insert(int no)
{
struct Qnode *temp;
temp=malloc(sizeof(struct Qnode));
temp->info=no;
temp->link=NULL;
if(front1==NULL)
front1=temp;
else
rear1->link=temp;
rear1=temp;
printf("%d is inserted\n",no);
}
void Delete()
{
if(front1==NULL)
printf("Queue is empty\n");
else
{
struct Qnode *temp;
temp=front1;
printf("Removed element is %d\n",temp->info);
front1=front1->link;
free(temp);
}
}
void display()
{
if(front1==NULL)
printf("Queue is empty\n");
else
{
struct Qnode *temp;
temp=front1;
printf("Elements are:\n");
while(temp!=NULL)
{
printf("%d\n",temp->info);
temp=temp->link;
}
}
}
