Index:
(1) Implementation of Stack using Arrays
(2) Linear Queue
(3) Priority Queue
(4) Circular Queue
(5) Operations on Link List
(6) Doubly Link List
(7) MERGING TWO DOUBLY LINKED LISTS(ASCENDING ORDER)
(8) Manipulation of Link List
(9) Sorting Queue (Bubble sort,Merge sort,Radix Sort)
(10) Binary search tree
(11) Heap Sort
(12) Hash Table
(13) Implementation of graph using Adjacency matrix
(14) Implementation of undirected graph using Adjacency matrix
(15) Dijkstra's algorithm
(16) Breadth-first search(BFS) Algorithm
(17) Depth-first search(DFS) Algoritm
(18) Index Sequential Search
(19) Sequential Search,Binary Search,Interpolation Search
(20) CREATING CIRCULAR HEADER LINKED LIST
---------------------------------------------------------------------------------------------------------------------------------
Programs:
(1) Implementation of Stack using Arrays
#include <stdio.h>
#include <conio.h>
#define MAX 10
void push(void);
void pop(void);
void display(void);
int top = -1;
int stack[MAX];
void main(void)
{
int option = 0;
int i;
for(i=0; i<MAX; i++)
{
stack[i] = 0;
}
while (option != 4)
{
clrscr();
printf("Stack Implementation Using Arrays & Global Declarations :-\n");
printf("Options Available are :-\n");
printf("1] Push\n2] Pop\n3] Display\n4] Exit\n\nEnter Option - ");
scanf("%d",&option);
switch (option)
{
case 1 : push(); break;
case 2 : pop(); break;
case 3 : display(); break;
case 4 : break;
default : printf("Error - Invalid Option");
getch();
break;
}
}
clrscr();
printf("\n\n\tEnd of Program");
getch();
}
void push(void)
{
int value;
if (top == (MAX-1))
{
printf("Stack Overflow. Can NOT Push");
getch();
return;
}
printf("Enter value - ");
scanf("%d", &value);
stack[++top] = value;
return;
}
void pop(void)
{
if (top == -1)
{
printf("Stack Underflow. Can NOT Pop");
getch();
return;
}
printf("Value popped = %d\n", stack[top]);
getch();
stack[top--] = 0;
return;
}
void display(void)
{
int i;
if (top == -1)
{
printf("Stack Empty. Can NOT Display");
getch();
return;
}
printf("Total Stack elements = %d\n\n", (top+1));
for (i = top; i >= 0; i--)
{
printf("%d - %d\n", (i+1), stack[i]);
}
getch();
return;
}
---------------------------------------------------------------------------------------------------------------------------------
(2) Linear Queue
#include <stdio.h>
#include<ctype.h>
int q[5];
int front, rear;
void main()
{
void add(int);
int del();
void display();
int option=1,i,num;
front = 0;
rear = 0;
clrscr();
printf("\nProgram for queue demonstration through array\n\n");
while(option !=4)
{
printf("\nMAIN MENU:\n1.Add element to queue\n2.Delete element from the queue\n3.Display elements in the queue\n4.Exit\n");
scanf("%d",&option);
switch(option)
{
case 1:
printf("\nEnter the data... ");
scanf("%d",&num);
add(num);
break;
case 2:
i=del();
printf("\nValue returned from delete function is %d ",i);
break;
case 3:
display();
break;
case 4:
break;
}
}
getch();
}
void add(int a)
{
if(rear>5)
{
printf("\n\nQUEUE FULL");
return;
}
else
{
q[rear]=a;
rear++;
printf("\n\nValue of rear = %d \n\nValue of front is %d\n\n",rear,front);
}
}
int del()
{
int a;
if(front == rear)
{
printf("\n\nQUEUE EMPTY");
return(0);
}
else
{
a=q[front];
front++;
}
return(a);
}
void display()
{
int i;
if (front <= rear)
{
printf("Total elements in the queue = %d\n\n", (rear-front));
for (i = front; i <= (rear-1); i++)
printf("%d - %d\n", (i-front), q[i]);
}
return;
}
---------------------------------------------------------------------------------------------------------------------------------
(3) Priority Queue
# include<stdio.h>
# include<conio.h>
struct node
{
int priority;
int info;
struct node *link;
}*front = NULL;
void insert()
{
struct node *tmp,*q;
int added_item,item_priority;
tmp = (struct node *)malloc(sizeof(struct node));
printf("Input the item value to be added in the queue : ");
scanf("%d",&added_item);
printf("Enter its priority : ");
scanf("%d",&item_priority);
tmp->info = added_item;
tmp->priority = item_priority;
/*Queue is empty or item to be added has priority more than first
item*/
if( front == NULL || item_priority < front->priority )
{
tmp->link = front;
front = tmp;
}
else
{
q = front;
while( q->link != NULL && q->link->priority <= item_priority )
q=q->link;
tmp->link = q->link;
q->link = tmp;
}/*End of else*/
}/*End of insert()*/
void del()
{
struct node *tmp;
if(front == NULL)
printf("Queue Underflow\n");
else
{
tmp = front;
printf("Deleted item is %d\n",tmp->info);
front = front->link;
free(tmp);
}
}/*End of del()*/
void display()
{
struct node *ptr;
ptr = front;
if(front == NULL)
printf("Queue is empty\n");
else
{
printf("Queue is :\n");
printf("Priority Item\n");
while(ptr != NULL)
{
printf("%5d %5d\n",ptr->priority,ptr->info);
ptr = ptr->link;
}
}/*End of else */
}/*End of display() */
void main()
{
int choice;
clrscr();
while(choice!=4)
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Quit\n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch(choice)
{
case 1:
insert();
break;
case 2:
del();
break;
case 3:
display();
break;
case 4:
exit(1);
default :
printf("Wrong choice\n");
}/*End of switch*/
}/*End of while*/
}/*End of main()*/
---------------------------------------------------------------------------------------------------------------------------------
(4) Circular Queue
#include <stdio.h>
#include <conio.h>
#define MAX 10
void add(void);
void delete(void);
void display(void);
int front = -1;
int rear = -1;
int queue[MAX];
void main(void)
{
int option = 0;
int i;
for(i=0; i<MAX; i++)
{
queue[i] = 0;
}
while (option != 4)
{
clrscr();
printf("Queue Implementation Using Arrays & Global Declarations :-\n");
printf("----- -------------- ----- ------ - ------ ------------\n\n");
printf("Options Available are :-\n");
printf("1] Add\n2] Delete\n3] Display\n4] Exit\n\nEnter Option - ");
flushall(); scanf("%d",&option); switch (option) {
case 1 : add(); break;
case 2 : delete(); break;
case 3 : display(); break;
case 4 : break;
default : printf("Error - Invalid Option"); getch(); break; }
}
clrscr(); printf("\n\n\tEnd of Program"); getch();
}
void add(void)
{
int value;
if (((rear+1)%MAX) == front)
{
printf("Queue Overflow. Can NOT Add"); getch(); return;
}
printf("Enter value - ");
flushall(); scanf("%d", &value); rear = ++rear%MAX; queue[rear] = value;
if (front == -1) front++; return;
}
void delete(void)
{
if (front == -1)
{
printf("Queue Underflow. Can NOT Delete"); getch(); return;
}
printf("Value deleted = %d\n", queue[front]); getch(); queue[front] = 0;
if (front == rear) front = rear = -1; else front = ++front%MAX; return;
}
void display(void)
{
int i;
if (front == -1)
{
printf("Queue Empty. Can NOT Display"); getch(); return;
}
if (front <= rear)
{
printf("Total elements in the queue = %d\n\n", (rear-front+1));
for (i = front; i <= rear; i++)
printf("%d - %d\n", (i-front+1), queue[i]);
}
else
{
printf("Total elements in the queue = %d\n\n", (MAX-front+rear+1));
for (i=front; i<MAX; i++)
printf("%d - %d\n", (i-front+1), queue[i]);
for (i=0; i<=rear; i++)
printf("%d - %d\n", (MAX-front+i+1), queue[i]);
}
getch();
}
---------------------------------------------------------------------------------------------------------------------------------
(5) Operations on Link List
#include<stdio.h>
#include<conio.h>
typedef struct
{
int count;
int *pos;
int *head;
}HEAD;
typedef struct
{
int data;
int *link;
}NODE;
int flag;
HEAD *createHead()
{
HEAD *pnew;
pnew=(HEAD *)malloc(sizeof(HEAD));
if(pnew)
{
pnew->head=NULL;
pnew->count=0;
printf("Memory Allocated");
}
else
{
pnew=NULL;
}
return pnew;
}
void insertnode(HEAD *plist,int datain)
{
int loc,i;
NODE *pnew,*ppre,*temp;
ppre=plist->head;
pnew=(NODE *)malloc(sizeof(NODE));
if(pnew==NULL)
{
printf("Memory Overflow");
}
else
{
pnew->data=datain;
}
if(ppre==NULL)
{
pnew->link=plist->head;
plist->head=pnew;
pnew->link=NULL;
}
else if(plist->count>=1)
{
temp=ppre;
printf("Enter the position at wich data is to be inserted");
scanf("%d",&loc);
for(i=0;i<loc-1;i++)
{
ppre=temp;
temp=temp->link;
}
pnew->link=ppre->link;
ppre->link=pnew;
}
plist->count=plist->count+1;
printf("Data Inserted");
}
void merging(HEAD *plist1,HEAD *plist2)
{
NODE *p;
if(plist1->count==0)
{
plist1->head=plist2->head;
}
else
{
p=plist1->head;
while(p->link!=NULL)
{
p=p->link;
}
p->link=plist2->head;
plist1->count=plist1->count+plist2->count;
printf("List2 Merged");
printf("Total Elements in List1=%d",plist1->count);
}
}
void concatenation(HEAD *plist1,HEAD *plist2)
{
NODE *p1,*p2,*pnew;
int n,i;
printf("Enter the Number of Node to be Concatenated");
scanf("%d",&n);
if(plist1->count==0)
{
p2=plist2->head;
pnew=(NODE *)malloc(sizeof(NODE));
pnew->data=p2->data;
plist1->head=pnew;
p1=plist1->head;
i=1;
while(i<n)
{
p2=p2->link;
pnew=(NODE *)malloc(sizeof(NODE));
pnew->data=p2->data;
p1->link=pnew;
i++;
p1=pnew;
}
}
else
{
p1=plist1->head;
p2=plist2->head;
while(p1->link!=NULL)
{
p1=p1->link;
}
i=1;
while(i<=n)
{
pnew=(NODE *)malloc(sizeof(NODE));
pnew->data=p2->data;
p1->link=pnew;
p1=p1->link;
i++;
p2=p2->link;
}
}
p1->link=NULL;
plist1->count=plist1->count+n;
printf("List2 Concatenated");
printf("The number of elements in the List I=%d",plist1->count);
}
void traverse(HEAD *plist)
{
NODE *p;
if(plist->head==NULL)
{
printf("List Empty");
}
else
{
p=plist->head;
while(p!=NULL)
{
printf("%d",p->data);
p=p->link;
}
printf("\nNumber of elements in list=%d",plist->count);
}
}
void unions(HEAD *plist1,HEAD *plist2)
{
NODE *p1,*p2;
int f;
if(plist1->count==0 && plist2->count==0)
{
printf("BOth List Empty");
}
else
{
if(plist1->count==0)
{
printf("Output is");
traverse(plist2);
}
if(plist2->count==0)
{
printf("Output is");
traverse(plist1);
}
else
{
p1=plist1->head;
while(p1!=NULL)
{
printf("%d",p1->data);
p1=p1->link;
}
p2=plist2->head;
while(p2!=NULL)
{
p1=plist1->head;
while(p1!=NULL)
{
if(p2->data==p1->data)
{
f=0;
}
else
{
f=1;
}
p1=p1->link;
}
if(f==1)
{
printf("%d",p2->data);
}
p2=p2->link;
}
}
}
}
void intersection(HEAD *plist1,HEAD *plist2)
{
NODE *p1,*p2;
int f;
if(plist1->count==0 || plist2->count==0)
{
printf("Intersection Failed");
}
else
{
p1=plist1->head;
p2=plist2->head;
while(p2!=NULL)
{
p1=plist1->head;
while(p1!=NULL)
{
if(p1->data==p2->data)
{
f=1;
break;
}
else
{
f=0;
}
p1=p1->link;
}
if(f==1)
{
printf("%d",p2->data);
}
p2=p2->link;
}
}
}
void main()
{
HEAD *plist1,*plist2;
int choice,datain;
clrscr();
plist1=createHead();
plist2=createHead();
while(1)
{
printf("\n1.Create List I");
printf("\n2.Create List II");
printf("\n3.Display List I");
printf("\n4.Display List II");
printf("\n5.Merge List");
printf("\n6.Concatenation");
printf("\n7.Union");
printf("\n8.Intersection");
printf("\n9.Exit");
printf("Enter the Choice");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter the element to be inserted");
scanf("%d",&datain);
insertnode(plist1,datain);
break;
case 2:
printf("Enter the element to be inserted");
scanf("%d",&datain);
insertnode(plist2,datain);
break;
case 3:
traverse(plist1);
break;
case 4:
traverse(plist2);
break;
case 5:
merging(plist1,plist2);
break;
case 6:
concatenation(plist1,plist2);
break;
case 7:
unions(plist1,plist2);
break;
case 8:
intersection(plist1,plist2);
break;
case 9:
exit(1);
break;
}
}
getch();
}
---------------------------------------------------------------------------------------------------------------------------------
(6) Doubly Link List
#include <stdio.h>
#include <stdlib.h>
void create();
void display();
void count();
void insert();
void sort();
void dissort();
void _delete();
void reverse();
void disrev();
void search();
struct student
{
char name[100];
int marks;
struct student *next;
struct student *prev;
}*p,*head1,*tail1,*head,*tail,*lnode,*ptr,*temp,*ptr4,*ptr5,*ptr7;
int cnt=0,n;
void main(void)
{
struct student *lnode;
int n,no,i;
char ans,temp1[100];
clrscr();
do
{
printf("\nEnter 1 to create the list");
printf("\nEnter 2 to display the list");
printf("\nEnter 3 to count the list");
printf("\nEnter 4 to sort the list and 6 to display");
printf("\nEnter 5 to append the list");
printf("\nEnter 7 to delete a node");
printf("\nEnter 8 to reverse the list and 9 to display");
printf("\nEnter 10 to search the data in the list ");
printf("\nEnter your choice\n");
scanf("%d",&no);
switch(no)
{
case 1:
{
create();
break;
}
case 2:
{
display();
break;
}
case 3:
{
count();
break;
}
case 4:
{
sort();
break;
}
case 6:
{
dissort();
break;
}
case 5:
{
insert();
break;
}
case 7:
{
_delete();
break;
}
case 8:
{
reverse();
break;
}
case 9:
{
disrev();
break;
}
case 10:
{
search();
break;
}
default:
{
printf("\nNo option");
}
}
fflush(stdin);
printf("\nWish to continue(y/n)\n");
scanf("%c",&ans);
}while(ans=='y');
}
void create()
{
int i=0,n;
printf("\nEnter size of the list..\n");
scanf("%d",&n);
printf("\nEnter %d student name and marks...\n",n);
for(i = 1; i <= n; i++)
{
lnode = (struct student *)malloc(sizeof(struct student));
scanf("%s%d",lnode->name,&lnode->marks);
cnt++;
if(head == NULL)
{
head = lnode;
lnode->prev = NULL;
}
else
{
tail->next = lnode;
lnode->prev = tail;
}
tail = lnode;
lnode->next = NULL;
}
}
void insert()
{
printf("\nEnter student name and marks...\n");
lnode = (struct student *)malloc(sizeof(struct student));
scanf("%s%d",lnode->name,&lnode->marks);
cnt++;
if(head == NULL)
{
head = lnode;
lnode->prev = NULL;
}
else
{
tail->next = lnode;
lnode->prev = tail;
}
tail = lnode;
lnode->next = NULL;
}
void display()
{
printf("\nStudents name and marks..\n");
for(lnode = head; lnode != NULL; lnode = lnode->next)
{
printf("\n%s\t%d",lnode->name,lnode->marks);
}
}
void count()
{
printf("\nNumber of nodes in the list==\n");
printf("%d",cnt);
}
void sort()
{
int i;
char temp1[100];
p=head;
while(p!=NULL)
{
lnode = (struct student *)malloc(sizeof(struct student));
for(i=0;i<20;i++)
{
lnode->name[i]=p->name[i];
}
lnode->marks=p->marks;
if(head1 == NULL)
{
head1 = lnode;
lnode->prev = NULL;
}
else
{
tail1->next = lnode;
lnode->prev = tail1;
}
tail1 = lnode;
lnode->next = NULL;
p=p->next;
}
for(ptr4=head1;ptr4!=NULL;ptr4=ptr4->next)
{
for(ptr5=head1;ptr5!=NULL;ptr5=ptr5->next)
{
if(ptr4->marks<=ptr5->marks)
{
for(i=0;i<20;i++)
{
temp1[i]=ptr4->name[i];
}
temp=ptr4->marks;
for(i=0;i<20;i++)
{
ptr4->name[i]=ptr5->name[i];
}
ptr4->marks=ptr5->marks;
for(i=0;i<20;i++)
{
ptr5->name[i]=temp1[i];
}
ptr5->marks=temp;
}
}
}
ptr=head1;
while(ptr->next!=NULL)
{
if(!strcmp(ptr->name,ptr->next->name) && (ptr->marks == ptr->next->marks))
{
ptr7=ptr->next->next;
free(ptr->next);
ptr->next = ptr7;
}
else
{
ptr = ptr->next;
}
}
}
void dissort()
{
ptr=head1;
while(ptr!= NULL)
{
printf("\n%s\t%d",ptr->name,ptr->marks);
ptr=ptr->next;
}
}
void _delete()
{
int num;
ptr=head;
printf("\nEnter the node number which is to be deleted\n");
scanf("%d",&num);
while(cnt != n)
{
if(num == cnt)
{
//free(ptr);
ptr7=ptr->next->next;
free(ptr->next);
free(ptr->prev);
ptr->next = ptr7;
}
cnt--;
ptr=ptr->next;
}
while(head != NULL)
{
if(lnode->prev == NULL)
head = lnode->next;
else
lnode->prev->next = lnode->next;
if(lnode->next == NULL)
tail = lnode->prev;
else
lnode->next->prev = lnode->prev;
}
}
void reverse()
{
int i;
char temp1[100];
p=head;
while(p!=NULL)
{
lnode = (struct student *)malloc(sizeof(struct student));
for(i=0;i<20;i++)
{
lnode->name[i]=p->name[i];
}
lnode->marks=p->marks;
if(head1 == NULL)
{
head1 = lnode;
lnode->prev = NULL;
}
else
{
tail1->next = lnode;
lnode->prev = tail1;
}
tail1 = lnode;
lnode->next = NULL;
p=p->next;
}
for(ptr4=head1;ptr4!=NULL;ptr4=ptr4->next)
{
for(ptr5=head1;ptr5!=NULL;ptr5=ptr5->next)
{
if(ptr4->marks>=ptr5->marks)
{
for(i=0;i<20;i++)
{
temp1[i]=ptr4->name[i];
}
temp=ptr4->marks;
for(i=0;i<20;i++)
{
ptr4->name[i]=ptr5->name[i];
}
ptr4->marks=ptr5->marks;
for(i=0;i<20;i++)
{
ptr5->name[i]=temp1[i];
}
ptr5->marks=temp;
}
}
}
ptr=head1;
while(ptr->next!=NULL)
{
if(!strcmp(ptr->name,ptr->next->name) && (ptr->marks == ptr->next->marks))
{
ptr7=ptr->next->next;
free(ptr->next);
ptr->next = ptr7;
}
else
{
ptr = ptr->next;
}
}
}
void disrev()
{
ptr=head1;
while(ptr!= NULL)
{
printf("\n%s\t%d",ptr->name,ptr->marks);
ptr=ptr->next;
}
}
void search()
{
int i,pt;
char temp1[100];
p=head;
while(p!=NULL)
{
lnode = (struct student *)malloc(sizeof(struct student));
for(i=0;i<20;i++)
{
lnode->name[i]=p->name[i];
}
lnode->marks=p->marks;
if(head1 == NULL)
{
head1 = lnode;
lnode->prev = NULL;
}
else
{
tail1->next = lnode;
lnode->prev = tail1;
}
tail1 = lnode;
lnode->next = NULL;
p=p->next;
}
for(ptr4=head1;ptr4!=NULL;ptr4=ptr4->next)
{
for(ptr5=head1;ptr5!=NULL;ptr5=ptr5->next)
{
if(ptr4->marks<=ptr5->marks)
{
for(i=0;i<20;i++)
{
temp1[i]=ptr4->name[i];
}
temp=ptr4->marks;
for(i=0;i<20;i++)
{
ptr4->name[i]=ptr5->name[i];
}
ptr4->marks=ptr5->marks;
for(i=0;i<20;i++)
{
ptr5->name[i]=temp1[i];
}
ptr5->marks=temp;
}
}
}
ptr=head1;
p=head;
printf("\nEnter data to be searched\n");
scanf("%s%d",p->name,&p->marks);
while(ptr->next!=NULL)
{
if(!strcmp(ptr->name,p->name) && (ptr->marks == p->marks))
{
pt=1;
break;
}
else
{
ptr = ptr->next;
}
}
if(pt==1)
{
printf("%s %d is in the list",p->name,p->marks);
printf("\nData found");
}
else
{
printf("data not found");
}
}
---------------------------------------------------------------------------------------------------------------------------------
(7) MERGING TWO DOUBLY LINKED LISTS(ASCENDING ORDER)
# include <stdio.h>
# include <malloc.h>
struct Double
{
int info;
struct Double *next;
struct Double *previous;
};
int i;
struct Double start, start1, *new1, *local;
void Doubly_insertion (struct Double * );
void Doubly_Create (struct Double * );
void Display (struct Double *);
/* Function create a list of five nodes */
void Doubly_Create (struct Double *node)
{
start.next = NULL; /* Empty list */
start.previous = NULL;
node = &start; /* Point to the start of the list */
for (i = 1; i < 10; i += 2)
{
node->next = (struct Double *) malloc(sizeof(struct Double ));
node->next->previous = node;
node = node->next;
node->info = i;
node->next = NULL;
}
}
void Doubly_insertion (struct Double *node)
{
struct Double *new1;
start1.next = NULL; /* Empty list */
start1.previous = NULL;
new1 = &start1; /* Point to the start of the list */
for (i = 2; i <= 10; i += 2)
{
new1->next = (struct Double *) malloc(sizeof(struct Double ));
new1->next->previous = new1;
new1= new1->next;
new1->info = i;
new1->next = NULL;
}
new1 = start1.next;
printf("\n Second list is as follows");
while(new1)
{
printf("\n 0x%x", new1);
printf(" %d", new1->info);
new1 = new1->next;
}
new1 = start1.next;
while(new1)
{
int found = 0;
local = (struct Double *) malloc(sizeof(struct Double));
local = new1;
new1 = new1->next;
node = start.next;
do
{
if ( node->info > local->info )
{
local->next = node;
local->previous = node->previous;
node->previous->next = local;
node->previous = local;
found = 1;
break;
}
else
node = node->next;
} while ((node->next) && (! found));
if (! found)
if (node->info> local->info)
{
local->next = node;
local->previous = node->previous;
node->previous->next = local;
node->previous = local;
}
else
{
local->next = NULL;
local->previous = node;
node->next = local;
}
}
}
/* Display the list */
void Display (struct Double *node)
{
node = start.next;
while (node)
{
printf("\n 0x%x", node);
printf(" %d", node->info);
node = node->next;
}
}
/* Function main */
void main()
{
struct Double *node = (struct Double *) malloc(sizeof(struct Double));
Doubly_Create (node);
printf("\n First list is as follows\n");
Display (node);
Doubly_insertion (node);
printf("\n List after merging above two lists (Ascending order)\n");
Display (node);
getch();
}
---------------------------------------------------------------------------------------------------------------------------------
(8) Manipulation of Link List
#include<stdio.h>
#include<conio.h>
typedef struct
{
int count;
int *pos;
int *rear;
int *link;
}HEAD;
typedef struct
{
int data;
int *link;
}NODE;
int i,flag;
HEAD *createhead();
void insertnode(HEAD *,int);
void traverse(HEAD *);
void deletenode(HEAD *);
void copylist(HEAD *);
void count1(HEAD *);
void destroylist(HEAD *);
void reverselist(HEAD *);
void searchlist(HEAD *,int);
void main()
{
HEAD *plist;
int choice,datain;
clrscr();
plist=createhead();
while(1)
{
printf("\n\n1.Insert Linked List Node");
printf("\n\n2.Display List");
printf("\n\n3.Delete List");
printf("\n\n4.Search");
printf("\n\n5.Count");
printf("\n\n6.Copy");
printf("\n\n7.Reverse");
printf("\n\n8.Exit");
printf("\n\nEnter the Choice");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\n\nEnter the element to be inserted");
scanf("%d",&datain);
insertnode(plist,datain);
break;
case 2:
traverse(plist);
break;
case 3:
deletenode(plist);
break;
case 4:
printf("\n\nEnter the element to be searched");
scanf("%d",&datain);
searchlist(plist,datain);
break;
case 5:
count1(plist);
break;
case 6:
copylist(plist);
break;
case 7:
reverselist(plist);
break;
case 8:
destroylist(plist);
break;
case 9:
exit(1);
break;
}
}
getch();
}
HEAD *createhead()
{
HEAD *pnew;
pnew=(HEAD *)malloc(sizeof(HEAD));
if(pnew)
{
pnew->link=NULL;
pnew->count=0;
pnew->rear=0;
printf("\n\nMemory Allocated");
}
else
{
pnew=NULL;
}
return pnew;
}
void traverse(HEAD *plist)
{
NODE *p;
if(plist->link==NULL)
{
printf("\n\nList Empty");
}
else
{
p=plist->link;
i=0;
while(i<plist->count)
{
printf("%d\t",p->data);
p=p->link;
i++;
}
printf("\n\nNumber of elements in list=%d",plist->count);
}
}
void deletenode(HEAD *plist)
{
NODE *p,*ppre,*temp;
int num,i;
p=plist->link;
ppre=plist->link;
printf("\n\nEnter the location to be deleted");
scanf("%d",&num);
if(num>plist->count)
{
printf("\n\nLocation Invalid");
}
else
{
if(num==1 && plist->count==1)
{
plist->link=NULL;
plist->rear=NULL;
free(ppre);
plist->count=plist->count-1;
printf("\n\nNumber is Deleted");
}
else if(num==1)
{
plist->link=ppre->link;
free(ppre);
plist->count=plist->count-1;
printf("\n\nNumber is Deleted");
}
else
{
for(i=1;i<num;i++)
{
ppre=p;
p=p->link;
}
ppre->link=p->link;
free(p);
if(num==plist->count)
{
plist->rear=ppre;
}
plist->count=plist->count-1;
printf("\n\nNumber is Deleted");
}
printf("\n\nNumber of Elements in linked list=%d",plist->count);
}
}
void searchlist(HEAD *plist,int data)
{
NODE *p1,*p2;
int i,flag;
p2=plist->link;
p1=plist->rear;
if(p2->data==data)
{
printf("\n\nData is present at First Location");
}
/* else if(p1->data=data)
{
printf("\n\nData is present at Last Location");
}*/
else
{
i=0;
p1=p2->link;
while(p1->link!=plist)
{
if(p1->data==data)
{
printf("\n\nData is present at %d location",i);
flag=1;
break;
}
else
{
p1=p1->link;
i++;
}
}
}
if(flag==0)
{
printf("\n\nData is not present");
}
}
void copylist(HEAD *plist1)
{
HEAD *plist2;
NODE *p1,*pcopy,*ppre;
int i;
plist2=createhead();
p1=plist1->link;
i=1;
while(i<=plist1->count)
{
pcopy=(NODE *)malloc(sizeof(NODE));
pcopy->data=p1->data;
if(i==1)
{
plist2->link=pcopy;
}
else
{
ppre->link=pcopy;
}
p1=p1->link;
ppre=pcopy;
i++;
}
pcopy->link=plist2;
plist2->rear=pcopy;
plist2->count=plist1->count;
printf("\n\nNumber of elements copied are %d",plist2->count);
printf("\n\nList1 is copied into List2");
printf("\n\nThe Contents of List2");
traverse(plist2);
}
void destroylist(HEAD *plist)
{
NODE *p;
while(plist->count!=0)
{
p=plist->link;
plist->link=p->link;
plist->count=plist->count-1;
free(p);
}
free(plist);
printf("\n\nLinked LIst Destroyed");
}
void count1(HEAD *plist)
{
printf("\n\nNumber of Elements in List %d",plist->count);
}
void reverselist(HEAD *plist1)
{
HEAD *plist2;
NODE *p1,*prev,*ppre2;
int i;
int cnt;
plist2=createhead();
cnt=plist1->count;
while(cnt!=0)
{
i=1;
p1=plist1->link;
prev=(NODE *)malloc(sizeof(NODE));
while(i<cnt)
{
p1=p1->link;
i++;
}
prev->data=p1->data;
if(plist2->count==0)
{
plist2->link=prev;
plist2->count=plist2->count+1;
ppre2=prev;
}
else
{
ppre2->link=prev;
ppre2=ppre2->link;
plist2->count=plist2->count+1;
}
cnt--;
}
prev->link=plist2;
traverse(plist2);
}
void insertnode(HEAD *plist,int datain)
{
int loc,i;
NODE *pnew,*ppre,*temp;
ppre=plist->link;
pnew=(NODE *)malloc(sizeof(NODE));
if(pnew==NULL)
{
printf("\n\nMemory Overflow");
}
else
{
pnew->data=datain;
}
if(ppre==NULL)
{
pnew->link=plist->link;
plist->link=pnew;
pnew->link=plist;
plist->rear=pnew;
}
else
{
printf("\n\nEnter the position at which data is to be inserted");
scanf("%d",&loc);
if(loc>plist->count)
{
temp=plist->rear;
temp->link=pnew;
pnew->link=plist;
plist->rear=pnew;
}
else
{
for(i=1;i<loc-1;i++)
{
temp=ppre;
ppre=ppre->link;
}
pnew->link=ppre->link;
ppre->link=pnew;
}
plist->count=plist->count+1;
printf("\n\nData Inserted");
}
}
---------------------------------------------------------------------------------------------------------------------------------
(9) Sorting Queue (Bubble sort,Merge sort,Radix Sort)
#include<stdio.h>
#include<conio.h>
#include<math.h>
#define MAXNOS 100
void radixsort(int *x, int n)
{
struct
{
int data;
int next;
} node[MAXNOS];
int front[10];
int rear[10];
int i, j, k;
int p, q, y;
int exp;
int first;
for (i=0; i<(n-1); i++)
{
node[i].data = x[i];
node[i].next = (i+1);
}
node[n-1].data = x[n-1];
node[n-1].next = -1;
first = 0;
for (k=1; k<5; k++)
{
for (i=0; i<10; i++)
{
front[i] = -1;
rear[i] = -1;
}
while ( first != -1 )
{
p = first;
first = node[first].next;
y = node[p].data;
exp = (int) pow((double)10, (double)(k-1));
j = (y/exp)%10;
q = rear[j];
if (q == -1)
{
front[j] = p;
}
else
{
node[q].next = p;
}
rear[j] = p;
}
for (j=0; j<10 && front[j] == -1; j++)
;
first = front[j];
while (j<= 9)
{
for (i=j+1; i<10 && front[i] == -1; i++)
;
if (i<=9)
{
p = i;
node[rear[j]].next = front[i];
}
j = i;
}
node[rear[p]].next = -1;
}
for (i=0; i<n; i++)
{
x[i] = node[first].data;
first = node[first].next;
}
}
void readarray(int x[],int n)
{
int i;
printf("\n\nEnter the Elements=");
for(i=0;i<n;i++)
{
scanf("%d",&x[i]);
}
}
void printarray(int x[],int n)
{
int i;
printf("\n\nArray Elements=\n");
for(i=0;i<(n);i++)
{
printf("%d\t",x[i]);
}
}
void swaparray(int *x,int *y)
{
int temp;
temp=*x;
*x=*y;
*y=temp;
}
void bubblesort(int x[],int n)
{
int i,j;
for(i=0;i<(n);i++)
{
for(j=0;j<(n-(i+1));j++)
{
if(x[j]>x[j+1])
{
swaparray(&x[j],&x[j+1]);
}
}
}
}
void mergesort(int *x, int n)
{
int aux[MAXNOS];
int i, j, k;
int size;
int l1;
int u1;
int l2;
int u2;
size = 1;
while (size < n)
{
l1 = 0;
k = 0;
while ((l1+size) < n )
{
l2 = l1 + size;
u1 = l2 - 1;
u2 = ((l2+size-1) < n)? (l2+size-1) : (n-1);
for (i=l1, j=l2; i<=u1 && j<=u2; k++)
{
if (x[i] <= x[j])
{
aux[k] = x[i++];
}
else
{
aux[k] = x[j++];
}
}
for ( ; i<=u1; k++)
{
aux[k] = x[i++];
}
for ( ; j<=u2; k++)
{
aux[k] = x[j++];
}
l1 = u2 + 1;
}
for (i=l1; k<n; i++)
{
aux[k++] = x[i];
}
for (i=0; i<n; i++)
{
x[i] = aux[i];
}
size = size * 2;
}
}
void main()
{
int choice;
int a[MAXNOS];
int m,m1;
int i,i1;
int n;
char s;
clrscr();
printf("Implementing Sorting Techniques\n");
printf("-------- ----- ---- - -------------\n\n");
// printf("%d",(int) pow((double)10,0));
do
{
printf("\n\n1.Bubble Sort.\n\n2.Merge Sort.\n\n3.Radix Sort.\n\n4.Exit");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Bubble Sort\n");
printf("-------- ----- ---- - -------------\n\n");
printf("Enter how many numbers will be input for sorting - ");
scanf("%d",&n);
readarray(a,n);
printarray(a,n);
printf("\n\nAfter Sorting=\n");
bubblesort(a,n);
printarray(a,n);
break;
case 2:
input :
printf("Straight Merge Sort - Non-Recursive\n");
printf("-------- ----- ---- - -------------\n\n");
printf("Enter how many numbers will be input for sorting - ");
scanf("%d", &m);
if (m < 2 || m > MAXNOS)
{
printf("Error - input value is out of range...");
getch();
goto input;
}
printf("Enter the numbers one by one -\n");
for (i=0; i<m; i++)
{
printf("%2d - ", (i+1));
scanf("%d", &a[i]);
}
mergesort(a, m);
printf("\n\nSorted numbers are - \n");
for (i=0; i<m; i++)
printf("%d\t", a[i]);
break;
case 3:
input_1 :
printf("Radix Sort\n");
printf("----- ---- \n\n");
printf("Enter how many numbers will be input for sorting - ");
scanf("%d", &m1);
if (m1 < 2 || m1 > MAXNOS)
{
printf("Error - input value is out of range...");
getch();
goto input_1;
}
printf("Enter the numbers one by one -\n");
for (i1=0; i1<m1; i1++)
{
input_2 :
printf("%2d - ", (i1+1));
scanf("%d", &a[i1]);
if ( a[i1] >= 1000 && a[i1] <= 9999 )
{
continue;
}
else
{
printf("\nEnter four digit integer numbers only.\n");
getch();
goto input_2;
}
}
radixsort(a, m1);
printf("\n\nSorted numbers are - \n");
for (i1=0; i1<m1; i1++)
printf("%d\t", a[i1]);
break;
case 4:
exit();
break;
}
}while(s!='n');
printf("Do you want to continue : Y/N");
scanf("%s",&s);
getch();
}
---------------------------------------------------------------------------------------------------------------------------------
(10) Binary search tree
#include<stdio.h>
#include<conio.h>
struct tree
{
int data;
struct tree *left;
struct tree *right;
};
struct tree *gettree()
{
return (struct tree *)malloc(sizeof(struct tree));
}
struct tree *instree(struct tree *root,int x)
{
struct tree *p=root,*q=NULL,*c;
if(p==NULL)
{
p=gettree();
p->data=x;
p->left=NULL;
p->right=NULL;
return p;
}
while(p!=NULL && p->data!=x)
{
q=p;
if(p->data<x)
p=p->right;
else
p=p->left;
}
if(p->data!=x || p==NULL)
{
p=gettree();
p->data=x;
p->left= NULL;
p->right=NULL;
if(q->data<x)
q->right=p;
else
q->left=p;
}
return root;
}
void inorder(struct tree *root)
{
if(root!=NULL)
{
inorder(root->left);
printf("%d\t",root->data);
inorder(root->right);
}
}
void preorder(struct tree *root)
{
if(root)
{
printf("%d\t",root->data);
preorder(root->left);
preorder(root->right);
}
}
void postorder(struct tree *root)
{
if(root)
{
postorder(root->left);
postorder(root->right);
printf("%d\t",root->data);
}
}
/*DELETION*/
struct tree *deltree(struct tree *root,int x)
{
struct tree *p=root,*q,*f,*s;
if(x==root->data)
{
s=f=root->right;
if(f->left==NULL)
{
f->left=root->left;
s=f;
free(root);
}
else
{
while(s->left!=NULL)
{
f=s;
s=s->left;
}
f->left=s->right;
s->left=root->left;
s->right=root->right;
free(root);
}
return s;
}
while(p!=NULL && p->data!=x)
{
q=p;
if(p->data<x)
p=p->right;
else
p=p->left;
}
if(p==NULL)
{
printf("\nData not found\n");
getch();
exit(1);
}
else
{
if(p->right==NULL && p->left==NULL) //LEAF NODE
{
if(x < q->data)
q->left=NULL;
else
q->right=NULL;
free(p);
return root;
}
if(p->right==NULL || p->left==NULL)
{
if(p->right==NULL) //left subtree
{
if(x < q->data)
q->left=p->left;
else
q->right=p->left;
free(p);
return root;
}
else
{
if(x < q->data)
q->left=p->right;
else
q->right=p->right;
free(p);
return root;
}
}
if(p->right!=NULL && p->left!=NULL)
{
s=p->right;
while(s->left!=NULL)
{
f=s;
s=s->left;
}
if(x < q->data)
q->left=s;
else
q->right=s;
if(s->right!=NULL)
{
f->left=s->right;
s->left=p->left;
s->right=p->right;
}
else
s->left=p->left;
free(p);
return root;
}
}
}
main()
{
int x;
struct tree *root=NULL;
clrscr();
printf("\nEnter data item: For Termination Enter -1:\n");
scanf("%d",&x);
while(x!=-1)
{
root=instree(root,x);
scanf("%d",&x);
}
printf("\nINORDER:\n");
inorder(root);
printf("\nPREORDER:\n");
preorder(root);
printf("\nPOSTORDER:\n");
postorder(root);
printf("\nEnter the data in the node to be deleted:");
scanf("%d",&x);
root=deltree(root,x);
if(root==NULL)
printf("\nTree is empty");
else
{
printf("\nINORDER:\n");
inorder(root);
printf("\nPREORDER:\n");
preorder(root);
printf("\nPOSTORDER:\n");
postorder(root);
}
getch();
return 0;
}
---------------------------------------------------------------------------------------------------------------------------------
(11) Heap Sort
#include<stdio.h>
#include<conio.h>
void swap(int *x,int *y)
{
int temp;
temp=*x;
*x=*y;
*y=temp;
}
void readarray(int x[],int n)
{
int i;
printf("Enter the Elements");
for(i=0;i<(n-1);i++)
{
scanf("%d",&x[i]);
}
}
void printarray(int x[],int n)
{
int i;
printf("Array Elements");
for(i=0;i<(n-1);i++)
{
printf("%d\t",x[i]);
}
}
void adjust(int x[],int i,int n)
{
int j,k,flag;
k=x[i];
flag=1;
j=2*i;
while(j<=n && flag)
{
if(j<n && x[j]<x[j+1])
j++;
if(k>=x[j])
flag=0;
else
{
x[j/2]=x[j];
j=j*2;
}
}
x[j/2]=k;
}
void buildinitialheap(int x[],int n)
{
int i;
for(i=(n/2);i>=0;i--)
{
adjust(x,i,n-1);
}
}
void heapsort(int x[],int n)
{
int i;
buildinitialheap(x,n);
for(i=(n-2);i>=0;i--)
{
swap(&x[0],&x[i+1]);
adjust(x,0,i);
}
}
void main()
{
int n,a[10];
clrscr();
printf("Enter the Number of Elements");
scanf("%d",&n);
readarray(a,n);
printarray(a,n);
printf("Sorted Elements");
heapsort(a,n);
printarray(a,n);
getch();
}
---------------------------------------------------------------------------------------------------------------------------------
(12) Hash Table
#include <stdio.h>
#include<conio.h>
#include <string.h>
#include <malloc.h>
#define MAXLEN 80
#define HASHSIZE 23
typedef struct node node;
typedef char *type;
typedef node *hashtable[HASHSIZE];
struct node
{
int val;
type key;
};
int hGetIndex1(type key)
{
int n=0;
char *keyptr;
for(keyptr=key; *keyptr; ++keyptr)
n += *keyptr;
return n%HASHSIZE;
}
int hGetIndex2(type key)
{
long n=0;
int i;
type keyptr;
printf("Function 2:).\n");
for(keyptr=key, i=1; *keyptr; ++keyptr, ++i)
n += i**keyptr;
return n%HASHSIZE;
}
int hGetEmptySlot(hashtable h, int index)
{
int i;
for(i=index+1; i<HASHSIZE; ++i) // index+1 to end of hashtable.
if(!h[i])
return i;
for(i=0; i<index; ++i) // starting from 0 to index-
if(!h[i])
return i;
return -1;
}
int hLinearProbe(hashtable h, type key, int index)
{
int i;
for(i=index+1; i<HASHSIZE; ++i) // index to end of hashtable.
if(h[i] && !strcmp(h[i]->key, key))
return i;
else if(!h[i])
return -1;
for(i=0; i<index; ++i) // starting from 0 to index-1.
if(h[i] && !strcmp(h[i]->key, key))
return i;
else if(!h[i])
return -1;
return -1;
}
void hInsert(hashtable h, type key, int val)
{
node *ptr = (node *)malloc(sizeof(node));
int index = hGetIndex1(key);
if(h[index])
{
index = hGetIndex2(key);
if(h[index])
{
index = hGetEmptySlot(h, index);
if(index == -1)
{
printf("ERROR: Hashtable full.\n");
return;
}
}
}
ptr->key = strdup(key);
ptr->val = val;
h[index] = ptr;
printf("h[%d] = %s.\n", index, key);
}
int hGetVal(hashtable h, type key)
{
int index = hGetIndex1(key);
if(h[index] && strcmp(h[index]->key, key))
{
index = hGetIndex2(key);
if(h[index] && strcmp(h[index]->key, key))
{
index = hLinearProbe(h, key, index);
if(index == -1)
return -1;
}
else if(!h[index])
return -1;
}
else if(!h[index])
return -1;
printf("index=%d ", index);
return h[index]->val;
}
void printHash(hashtable h)
{
int i;
for(i=0; i<HASHSIZE; ++i)
if(h[i])
{
printf("%d: ", i);
printf("%s=%d ", h[i]->key, h[i]->val);
printf("\n");
}
}
int main()
{
char s[MAXLEN];
hashtable h = {"asd"};
int i = 0;
clrscr();
printf("Enter the string to be hashed: ");
gets(s);
while(*s)
{
hInsert(h, s, i++);
printf("Enter the string to be hashed(enter to end): ");
gets(s);
}
printf("Enter the string to be searched: ");
gets(s);
while(*s)
{
printf("%s was inserted at number %d.\n", s, hGetVal(h, s));
printf("\nEnter the string to be searched(enter to end): ");
gets(s);
}
printHash(h);
getch();
return 0;
}
---------------------------------------------------------------------------------------------------------------------------------
(13) Implementation of graph using Adjacency matrix
#include<stdio.h>
#include<conio.h>
#include<process.h>
#define max 20
int adj[max][max];
int n;
void createG()
{
int i,edg,org,dst;
clrscr();
printf("\nEnter the no of nodes");
scanf("%d",&n);
edg=n*(n-1);
for(i=0;i<edg;i++)
{
printf("\n enter edge %d(0,0) to quit:",i);
scanf("%d %d",&org,&dst);
if((org==0)&&(dst==0))
break;
if(org>n||dst>n||org<=0||dst<=0)
{
printf("\n Invalid edge");
i++;
}
else
adj[org][dst]=1;
}
}
void display()
{
int i,j;
printf("\n Adjecency matrix\n");
for(i=0;i<=n;i++)
{
for(j=0;j<=n;j++)
printf("%4d",adj[i][j]);
printf("\n");
}
}
void insertn()
{
int i;
n++;
printf("\n Inserted node is %d ",n);
for(i=1;i<=n;i++)
{
adj[i][n]=0;
adj[n][i]=0;
}
}
void deleten(char u)
{
int i,j;
if(n==0)
{
printf("\n Graph is empty");
return;
}
if(u>n)
{
printf("This node is not present in list");
return;
}
for(i=u;i<=n-1;i++)
for(j=1;j<=n;j++)
{
adj[j][i]=adj[j][i+1];//shift colmns left
adj[i][j]=adj[i+1][j];//shift row up
}
n--;
}
void ins_edg(char u,char v)
{
if(u>n)
{
printf("\nSource node does not exit");
return;
}
if(v>n)
{
printf("\nDestination node does not exit");
return;
}
adj[u][v]=1;
}
void del_edg( char u,char v)
{
if (u>n||v>n||adj[u][v]==0)
{
printf("\n This edge does not exit");
return;
}
adj[u][v]=0;
}
void main()
{
int choice,node,origin,destin;
char c;
clrscr();
createG();
do
{
//clrscr();
printf("\n 1.Insert node\n");
printf("\n 2.Insert edge\n");
printf("\n 3.Delete node\n");
printf("\n 4.Delete edge\n");
printf("\n 5.Display\n");
printf("\n 6.Exit\n");
printf("\n Enter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
insertn();
break;
case 2:
printf("\n Enter edge to be inserted:");
// fflush(stdin);
scanf("%d %d",&origin,&destin);
ins_edg(origin,destin);
break;
case 3:
printf("\n Enter node to be deleted:");
//fflush(stdin);
scanf("%d",&node);
deleten(node);
break;
case 4:
printf("\n Enter edge to be deleted:");
// fflush(stdin);
scanf("%d %d",&origin,&destin);
del_edg(origin,destin);
break;
case 5:
printf("Elements in graph");
display();
break;
case 6:
exit(0);
default:
printf("\nwrong choice\n");
break;
} //end of switch
}while(c!='n');
printf("Do you want to continue Y/N");
scanf("%s",&c);
getch();
}//end of main
---------------------------------------------------------------------------------------------------------------------------------
(14) Implementation of undirected graph using Adjacency matrix
#include <stdio.h>
#include <conio.h>
void main()
{
int adj_mat[10][10];
int n;
int m;
int i,j,k;
input :
clrscr();
printf("Adjacency Matrix - Undirected Graphs\n");
printf("--------- ------ - ---------- ------\n\n");
printf("Enter number of vertices in the undirected graph [0 to exit] - ");
scanf("%d", &n);
if (n < 0 || n >10)
{
printf("Maximum vertices in the undirected graph = %d\n",10);
printf("Error - input value is out of range...[0 to 10]");
getch();
goto input;
}
if (n == 0)
{
goto end;
}
for (i=0; i<10; i++)
{
for (j=0; j<10; j++)
{
adj_mat[i][j] = 0;
}
}
printf("Enter total number of edges in the undirected graph - ");
flushall();
scanf("%d", &m);
for (k=1; k<=m; k++)
{
printf("\nEdge no = %2d is between -\n vertex number = ", k);
scanf("%d",&i);
printf("and vertex number = ");
flushall();
scanf("%d",&j);
if (i<1 || i>n || j<1 || j>n)
{
printf("Error - check details of this edge\n");
printf("wrong vertex numbers...");
getch();
goto input;
}
adj_mat[i-1][j-1]=1;
adj_mat[j-1][i-1]=1;
}
clrscr();
printf("Adjecancy Matrix - \n", n);
printf("--------- ------ - \n\n\n");
for (i=0; i<n; i++)
{
for (j=0; j<n; j++)
{
printf(" %d ",adj_mat[i][j]);
}
printf("\n\n");
}
getch();
goto input;
end :
printf("\n\n\bEnd of Program");
getch();
}
---------------------------------------------------------------------------------------------------------------------------------
(15) Dijkstra's algorithm
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#define infinity 9999
#define true 1
#define false 0
int *ct;
int **makeinfinity(int n);
void main()
{
int w,v;
int x,y,i,j;
int p=0;
int **cost,*D;
int *visited;
int vert,edge;
clrscr();
printf("\n Enter No of vertices :: ");
scanf("%d",&vert);
cost=makeinfinity(vert);
D =(int *)malloc(vert*(sizeof(int)));
ct =(int *)malloc(vert*(sizeof(int)));
for(i=1;i<=vert;i++)
visited[i]=false;
printf("\n Enter No of edges :: ");
scanf("%d",&edge);
for(i=0;i<edge;i++)
{
printf("\n Enter Edge%d :: ",i+1);
scanf("%d%d",&x,&y);
printf("\n Enter cost of edge from %d to %d :: ",x,y);
scanf("%d",&cost[x][y]);
}
for(i=2;i<=vert;i++)
{
if(p==0)
{
for(j=1;j<=vert;j++)
D[j]=cost[1][j];
D[1]=infinity;
p++;
ct=D;
}
w=findmin(D,vert);
visited[w]=true;
for(v=2;v<=vert;v++)
{
if(visited[v]!=true)
D[v]=min(D[v],D[w]+cost[w][v]);
}
}
for(i=2;i<=vert;i++)
printf("\nCost of path 1 to %d = %d",i,D[i]);
getch();
free(D);
free(cost);
free(ct);
}
int ** makeinfinity(int n)
{
int i,j;
int **a;
a=(int **)malloc(n*(sizeof(int)));
for(i=0;i<=n;i++)
a[i]=(int *)malloc(n*(sizeof(int)));
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=infinity;
return a;
}
int min(int x,int y)
{
if(x>y)
return y;
else
return x;
}
int findmin(int *D,int vert)
{
int min,i,w;
min=D[2];
w=2;
for(i=2;i<=vert;i++)
{
if(D[i]<min)
{
min=D[i]; w=i;
}
}
D[w]=min;
return w;
}
---------------------------------------------------------------------------------------------------------------------------------
(16) Breadth-first search(BFS) Algorithm
#include <stdio.h>
#include <conio.h>
void main(void)
{
void bfs(int [][10], int [], int);
int adj_mat[10][10];
int visited[10];
int n;
int m;
int start;
int i,j,k;
input :
clrscr();
printf("BFS Traversal - Undirected Graphs - Non-Recursive\n");
printf("--- --------- - ---------- ------ - -------------\n\n");
printf("Enter number of vertices in the undirected graph [0 to exit] - ");
flushall();
scanf("%d", &n);
if (n < 0 || n >10)
{
printf("Maximum vertices in the undirected graph = %d\n",10);
printf("Error - input value is out of range...[0 to 10]");
getch();
goto input;
}
if (n == 0)
{
goto end;
}
for (i=0; i<10; i++)
{
visited[i] = 0;
for (j=0; j<10; j++)
{
adj_mat[i][j] = 0;
}
}
printf("Enter total number of edges in the undirected graph - ");
flushall();
scanf("%d", &m);
for (k=1; k<=m; k++)
{
printf("\nEdge no = %2d is between -\n vertex number = ", k);
flushall();
scanf("%d",&i);
printf("and vertex number = ");
flushall();
scanf("%d",&j);
if (i<1 || i>n || j<1 || j>n)
{
printf("Error - check details of this edge\n");
printf("wrong vertex numbers...");
getch();
goto input;
}
adj_mat[i-1][j-1]=1;
adj_mat[j-1][i-1]=1;
}
printf("\n\nEnter vertex no at which to start BFS [%d to %d] - ", 1, n);
flushall();
scanf("%d",&start);
if (start < 1 || start>n)
{
printf("Error - input value is out of range...[0 to 10]");
getch();
goto input;
}
clrscr();
printf("Adjecancy Matrix - \n", n);
printf("--------- ------ - \n\n\n");
for (i=0; i<n; i++)
{
for (j=0; j<n; j++)
{
printf(" %d ",adj_mat[i][j]);
}
printf("\n\n");
}
printf("\n\n\nBFS Traversal starting at vertex no %d -\n",start);
printf("--- --------- -------- -- ------ -- - -\n\n\n");
bfs(adj_mat,visited,(start-1));
printf("\n\n");
getch();
goto input;
end :
printf("\n\n\bEnd of Program");
getch();
}
void bfs(int adj_mat[][10], int visited[], int start)
{
int i;
int queue[10] = {0};
int first = -1;
int last = -1;
queue[++last] = start;
visited[start] = 1;
printf("%d ",(start+1));
while (first != last)
{
start = queue[++first];
for (i=0; i<10; i++)
{
if (adj_mat[start][i] && visited[i] == 0)
{
queue[++last] = i;
visited[i] = 1;
printf("%d ",(i+1));
}
}
}
}
---------------------------------------------------------------------------------------------------------------------------------
(17) Depth-first search(DFS) Algoritm
#include <stdio.h>
#include <conio.h>
void main(void)
{
void dfs(int [][10], int [], int);
int adj_mat[10][10];
int visited[10];
int n;
int m;
int start;
int i,j,k;
input :
clrscr();
printf("DFS Traversal - Undirected Graphs - Non-Recursive\n");
printf("--- --------- - ---------- ------ - -------------\n\n");
printf("Enter number of vertices in the undirected graph [0 to exit] - ");
flushall();
scanf("%d", &n);
if (n < 0 || n >10)
{
printf("Maximum vertices in the undirected graph = %d\n",10);
printf("Error - input value is out of range...[0 to 10]");
getch();
goto input;
}
if (n == 0)
{
goto end;
}
for (i=0; i<10; i++)
{
visited[i] = 0;
for (j=0; j<10; j++)
{
adj_mat[i][j] = 0;
}
}
printf("Enter total number of edges in the undirected graph - ");
flushall();
scanf("%d", &m);
for (k=1; k<=m; k++)
{
printf("\nEdge no = %2d is between -\n vertex number = ", k);
flushall();
scanf("%d",&i);
printf("and vertex number = ");
flushall();
scanf("%d",&j);
if (i<1 || i>n || j<1 || j>n)
{
printf("Error - check details of this edge\n");
printf("wrong vertex numbers...");
getch();
goto input;
}
adj_mat[i-1][j-1]=1;
adj_mat[j-1][i-1]=1;
}
printf("\n\nEnter vertex no at which to start DFS [%d to %d] - ", 1, n);
flushall();
scanf("%d",&start);
if (start < 1 || start>n)
{
printf("Error - input value is out of range...[0 to 10]");
getch();
goto input;
}
clrscr();
printf("Adjecancy Matrix - \n", n);
printf("--------- ------ - \n\n\n");
for (i=0; i<n; i++)
{
for (j=0; j<n; j++)
{
printf(" %d ",adj_mat[i][j]);
}
printf("\n\n");
}
printf("\n\n\nDFS Traversal starting at vertex no %d -\n",start);
printf("--- --------- -------- -- ------ -- - -\n\n\n");
dfs(adj_mat,visited,(start-1));
printf("\n\n");
getch();
goto input;
end :
printf("\n\n\bEnd of Program");
getch();
}
void dfs(int adj_mat[][10], int visited[], int start)
{
int i;
int stack[10*10] = {0};
int top = -1;
stack[++top] = start;
while (top != -1)
{
start = stack[top--];
if (visited[start] == 0)
{
printf("%d ",(start+1));
visited[start] = 1;
for (i=(10-1); i>=0; i--)
{
if (adj_mat[start][i] && visited[i] == 0)
{
stack[++top] = i;
}
}
}
}
}
---------------------------------------------------------------------------------------------------------------------------------
(18) Index Sequential Search
#include <stdio.h>
#include <conio.h>
#define MAXNOS 100
int indseqsr(int [], int, int [], int, int);
void main(void)
{
int a[MAXNOS] = {0};
int indx[(MAXNOS/10)+2] = {0};
int srch_val;
int found;
int indxsize;
int i, j;
for (i=0; i<MAXNOS; i++)
{
if (i < (MAXNOS/10))
{
a[i] = (i+1)*100 + 10*(i+1);
}
else if ( i < (2*(MAXNOS/10)))
{
a[i] = (i+1)*100 + 20*(i+1);
}
else if ( i < (3*(MAXNOS/10)))
{
a[i] = (i+1)*100 + 30*(i+1);
}
else if ( i < (4*(MAXNOS/10)))
{
a[i] = (i+1)*100 + 40*(i+1);
}
else if ( i < (5*(MAXNOS/10)))
{
a[i] = (i+1)*100 + 50*(i+1);
}
else if ( i < (6*(MAXNOS/10)))
{
a[i] = (i+1)*100 + 60*(i+1);
}
else if ( i < (7*(MAXNOS/10)))
{
a[i] = (i+1)*100 + 70*(i+1);
}
else if ( i < (8*(MAXNOS/10)))
{
a[i] = (i+1)*100 + 80*(i+1);
}
else if ( i < (9*(MAXNOS/10)))
{
a[i] = (i+1)*100 + 90*(i+1);
}
else
{
a[i] = (i+1)*100 + 100*(i+1);
}
}
for (i=0, j=-1; i<MAXNOS; i=i+10)
{
indx[++j] = a[i];
}
if (indx[j] != a[MAXNOS-1])
{
indx[++j] = a[MAXNOS-1];
}
indxsize = j+1;
input :
clrscr();
printf("Index Sequential Search\n");
printf("----- ---------- ------\n\n");
printf("Array of numbers to search from -\n");
for (i=0; i<MAXNOS; i++)
{
printf("%3d - %-5d\t",(i+1),a[i]);
}
printf("\n\nIndex entries -\n");
for (i=0; i<indxsize; i++)
{
printf("%3d - %-5d\t",(i+1),indx[i]);
}
printf("\n\nEnter the number to search for [ 0 to end program] - ");
flushall();
scanf("%d", &srch_val);
if (srch_val == 0)
{
goto end_of_program;
}
found = indseqsr(a, MAXNOS, indx, indxsize, srch_val);
if ( found == -1)
{
printf("\n\n\bKey = %d is NOT found in the data set.\n\n", srch_val);
getch();
}
else
{
printf("\n\n\bKey = %d is found in the data set at position = %d\n\n",
srch_val, (found+1));
getch();
}
goto input;
end_of_program :
printf("\n\n\b End of Program\n");
getch();
}
int indseqsr(int keys[], int n, int index[], int indexsiz, int key)
{
int i, j;
if (key < index[0] || key > index[indexsiz-1])
{
return (-1);
}
i = 0;
while (i < indexsiz)
{
if (index[i] >= key)
{
break;
}
i++;
}
j = i*10;
if (j > (n-1))
{
j = n-1;
}
while (j > ((i-1)*10))
{
if (keys[j] <= key)
{
break;
}
j--;
}
if (keys[j] == key)
{
return (j);
}
else
{
return (-1);
}
}
---------------------------------------------------------------------------------------------------------------------------------
(19) Sequential Search,Binary Search,Interpolation Search
#include <stdio.h>
#include <conio.h>
int sequsrch(int [], int);
void main()
{
int a[10];
int srch_val;
int found;
int i,option=0;
clrscr();
printf("Enter the Array Values:");
for (i=0;i<5;i++)
{
scanf("%d",&a[i]);
}
input :
clrscr();
printf("Please Select the Option:");
printf("\n1.Sequential Search\n2.Binary Search\n3.Interpolation Search");
scanf("%d",&option);
switch(option)
{
case 1: sequsrch(a,srch_val);
printf("Sequential Search With Unordered Data\n");
// seq:found=sequsrch(a,srch_val);
break;
case 2: binsrch(a,srch_val);
printf("Binary Search With Unordered Data\n");
// bin:found=binsrch(a,srch_val);
break;
case 3: intsrch(a,srch_val);
printf("Interpolation Search With Unordered Data\n");
break;
default:printf("Wrong Choice!!!");
break;
}
printf("Array of numbers to search from -\n");
for (i=0;i<5; i++)
{
printf("%d - %d\n",(i+1),a[i]);
}
printf("\n\nEnter the number to search for [ 0 to end program] - ");
scanf("%d", &srch_val);
if (srch_val == 0)
{
goto end_of_program;
}
if(option==1)
{
found = sequsrch(a, srch_val);
}
else if(option ==2)
{
found = binsrch(a, srch_val);
}
else if(option ==3)
{
found = intsrch(a,srch_val);
}
if ( found == -1)
{
printf("\n\n\bKey = %d is NOT found.\n\n", srch_val);
getch();
}
else
{
printf("\n\n\bKey = %d is found at position = %d\n\n",srch_val, (found+1));
getch();
}
goto input;
end_of_program :
printf("\n\n\b End of Program\n");
getch();
}
int sequsrch(int k[], int key)
{
int i;
for (i=0; i<5; i++)
{
if (key == k[i])
{
return (i);
}
}
return (-1);
}
int binsrch(int k[], int key)
{
int low = 0;
int high = (10-1);
int mid;
while (low <= high)
{
mid = (low+high)/2;
if (key == k[mid])
{
return (mid);
}
if (key < k[mid])
{
high = mid-1;
}
else
{
low = mid + 1;
}
}
return (-1);
}
int intsrch(int k[], int key)
{
int low = 0;
int high = (5-1);
int mid;
while (key <= k[high] && key >= k[low])
{
mid = low + (int)(((float)(key-k[low])*(float)(high-low))/
(float)(k[high]-k[low]));
if (key == k[mid])
{
return (mid);
}
if (key < k[mid])
{
high = mid - 1 ;
}
else
{
low = mid + 1;
}
}
return (-1);
}
---------------------------------------------------------------------------------------------------------------------------------
(20) CREATING CIRCULAR HEADER LINKED LIST
# include <stdio.h>
# include <malloc.h>
struct link
{
int info;
struct link *next;
};
int i; /* Represents number of nodes in the list */
int number;
struct link *start, *new1;
void insertion(struct link *);
void create_circular_list(struct link *);
void display(struct link *);
/* Function create a circular header linked list */
void create_circular_list( struct link *node)
{
char ch;
node = start; /* Point to the header node in the list */
node->next = (struct link *) malloc(sizeof(struct link));
i = 0;
printf("\n Input choice n for break: ");
ch = getchar();
while(ch != 'n')
{
node->next = (struct link* ) malloc(sizeof(struct link));
node = node->next;
printf("\n Input the node: %d:", (i+1));
scanf("%d", &node->info);
fflush(stdin);
printf("\n Input choice n for break: ");
ch = getchar();
i++;
}
printf("\n Total nodes = %d", i);
node = start;
node->info = i; /* Assign total number of nodes to the header node */
}
/* Inserting a node in circular header linked */
void insertion(struct link *node)
{
int count = node->info;
int node_number = 0;
int insert_node;
node = start;
node = node->next;
printf("\n Input node number you want to insert: ");
printf("\n Value should be less are equal to the");
printf("\n number of nodes in the list: ");
scanf("%d", &insert_node);
while(count)
{
if((node_number+1) == insert_node)
{
new1 = (struct link* ) malloc(sizeof(struct link));
new1->next = node->next ;
node->next = new1;
printf("\n Input the node value: ");
scanf("%d", &new1->info);
node = node->next;
count--;
}
else
{
node = node->next;
count--;
}
node_number ++;
}
if (count == 0)
{
node = start; /* Points to header node */
node->info = node->info+1;
}
}
/* Display the list */
void display(struct link *node)
{
int count = node->info;
node = start;
node = node->next;
while (count-1)
{
printf("\n 0x%x", node);
printf(" %d ", node->info);
node = node->next;
count --;
}
}
/* Function main */
void main()
{
struct link *node = (struct link *) malloc(sizeof(struct link));
create_circular_list(node);
printf("\n Before inserting a node list is as follows:\n");
display(node);
insertion(node);
printf("\n After inserting a node list is as follows:\n");
display(node);
}
Posts
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.