## Saturday, January 29, 2011

### Dijkstra’s Algorithm MC9217 DATA STRUCTURES LAB Anna University lab manual download

Aim: To write a program to implement Dijkstra’s algorithm to find the shortest path.

Algorithm:

1. Start
2. Read the value of n
3. Read small dist, newdist, maxnode
4. set for loop of i< 1 to  n-2
5. set for loop of  i< 1 to n
6. Check whether dist[i] =newdist then if n-1 then calculate smalldist=dist[i]
Assign the value of i<j
1. print current
2. check whether dist[i] <small dist if it is true print current value otherwise print newdist[i]
3. Stop

Program Code
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#define MAX 30
#define UNVISITED -1
#define VISITED 1
#define INFINITY 32767
void viewPathMat(int pm[MAX],int n,int len);
int searchPath(int src,int des,int pathMat[MAX],int *minLen);
typedef struct
{
int previous,len,status;
}node;
void main()
{
char ch,s,d;
int i,j,k,src,des,minLen,tot,pathMat[MAX];
clrscr();
printf(“\n DIJKSTRA’S SHORTEST PATH ALGORITHM”);
printf("\n\N Enter total number of vertex:");
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
while(1)
{
printf("\n\n Enter the source node :");
fflush(stdin);
scanf("%c",&s);
printf("\n\n Enter the destination node :");
fflush(stdin);
scanf("%c",&d);
src=toupper(s)-64;
des=toupper(d)-64;
tot=searchPath(src,des,pathMat,&minLen);
viewPathMat(pathMat,tot,minLen);
printf("\n Do you want to continue(y/n):");
ch=getche();
if(ch!='y'  && ch!='Y')
break;} }

void viewPathMat(int pm[MAX],int n,int len)
{
int k;
if(len!=0)
{
printf("\n Minimum length is:%d\n\n Shortest Path is:",len);
for(k=n;k>1;k--)
printf("%c-->",pm[k]+64);printf("%c\n",pm[k]+64);
printf("\n Distance is :      ");
for(k=n;k>1;k--)
{
}
else
printf("\n NO path from source to destination node \n");
}
int searchPath(int src,int des,int pathMat[MAX],int *minLen)
{
node graph[MAX];
int i,k,min,tot=0,curVertex,newLen,u,v;
*minLen=0;
for(i=1;i<=n;i++)
{
graph[i].previous=0;graph[i].len=INFINITY;
graph[i].status=UNVISITED;
}
graph[src].previous=0;graph[src].len=0;
graph[src].status=VISITED;curVertex=src;
while(curVertex!=des){
for(k=1;k<=n;k++){
if(newLen<graph[k].len){
graph[k].previous=curVertex;
graph[k].len=newLen;
}
}
}
min=INFINITY;curVertex=0;
for(i=1;i<=n;i++)
if(graph[i].status==UNVISITED  &&   graph[i].len<min){
min=graph[i].len;curVertex=i;
}
if(curVertex==0) return 0;
graph[curVertex].status=VISITED;
}

while(curVertex!=0){
pathMat[++tot]=curVertex;
curVertex=graph[curVertex].previous;
}
for(i=tot;i>1;i--){
u=pathMat[i];v=pathMat[i-1];
}
return(tot); }

Aim: To write a program to traverse the tree using breadth first search.

Algorithm:

1. Start
2. Read the size value in choice=1 and get the vertex value
3. Set for loop of condition i=1 and i<n
4. Read the number of edges
5. Set for loop of condition j<= no. of edges and j=1
7. if Ch=2 then check a[i][j]==1
then check v[j]=0
printf v[j]
1. If ch==3 for display set for loop i<=n and  print vt[i]
2. Set for loop j<=n and then print the a[i][j]
3. Stop

Program Code
#include<stdio.h>
void insert(int c);
int del();
int front=-1,rear=-1;
int q[30],ans[10],k=0;

void main()
{
int i,j,n,no,a[10][10];
clrscr();
printf("\n Enter the number of Nodes: ");
scanf("%d",&n);
printf("\n Enter the adjacency matrix of the graph:\n ");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("\t %d",a[i][j]);
printf("\n");
}
insert(0);
printf("\bBreadth First Search of the nodes is:\n");
while(rear!=front)
{
i=del();
printf("\t:%d",i+1);
for(j=0;j<n;j++)
{
if (a[i][j]==1)
insert(j);}
}
getch();
}

int del()
{
return q[++front];
}

void insert(int c)
{
int i,count=0;
for(i=0;i<k;i++)

{
if(ans[i]==c)
{
count=1;
break;
}
}
if(count==0)
{
q[++rear]=c;
ans[k++]=c;
}

}

### Depth First Search MC9217 DATA STRUCTURES LAB Anna University lab manual download

Depth First Search MC9217 DATA STRUCTURES LAB Anna University lab manual download

Aim: To write a program to traverse the tree using Depth first search.

Algorithm:

1. Start
2. Read the value of n
3. Set for loop as i<n as i=0
4. Set for loop as j>n as j=0
1. Set for loop i<n and execute check whether (!vis[i]) then
Dfs(i)
1. Stop

Program Code
#include<stdio.h>
#include<conio.h>
#define max 50
int vertex[max];
int visited[max];
void creategraph(int);
void dfs(int,int);
void depthfirst(int);
void main()
{
int ch,n,v;
clrscr();
do
{
printf("\n1.create graph"
"\n2.dfs"
"\n3.exit"
scanf("%d",&ch);
switch(ch)
{
case 1:{ printf("\n Enter no. of vertices to be created");
scanf("%d",&v);
creategraph(v);
break; }
case 2:  depthfirst(v);
break;
case 3:printf("end of the program");
break;
}
}while(ch!=3);
getch();
}
void  creategraph(int v)
{
int i,j,n,m,k;

for(i=0;i<v;i++)
{
printf("\n Enter the node value");
scanf("%d",&vertex[i]);
visited[i]=0;
}

for(j=0;j<v;j++)
printf("for each vertex of the graph");
for(i=0;i<v;i++)
{
printf("\n Enter the no.of adjancey vertices for the vertex %d",vertex[i]);
scanf("%d",&n);
for(j=0;j<n;j++)
{
scanf("%d",&m);
for(k=0;k<v;k++)
{
if(vertex[k]==m)
}
}
}
printf("\n graph created with no. of vertices");
for(i=0;i<v;i++)
{
for(j=0;j<v;j++)
printf("\n");
}
}
void depthfirst(int v)
{
int i;
for(i=0;i<v;i++)
visited[i]=0;
visited[0]=1;
printf("Depth first serach \n");
printf("%d",vertex[0]);
dfs(0,v);
}
{
int j,k;
for(j=0;j<v;j++)
{
if(visited[j]==0)
{
visited[j]=1;
printf("%d",vertex[j]);
dfs(j,v);
}
}
}

### Sort the given list of elements using Quick Sort MC9217 DATA STRUCTURES LAB Anna University lab manual download

Sort the given list of elements using Quick Sort MC9217 DATA STRUCTURES LAB Anna University lab manual download

Aim: To write a program to sort the given list of elements using Quick Sort.

Algorithm:

2. Set the first element in that array as pivot element.
3. Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it.
4. After this partitioning, the pivot is in its final position. This is called the partition operation.
5. Repeat the steps from 2 to sort the sub-list of lesser elements and the sub-list of greater elements.

Program Code
/*QUIC SORT*/
#include<stdio.h>
#include<conio.h>
#include<math.h>
int i,j,n,pivot,a[20];
void quick(int a[],int left, int right);
void swap(int a[],int i, int j);
void main()
{
int a[20],n,i;
clrscr();
printf("\n\tQUICK SORT");
printf("\nEnter the number of elements:");
scanf(" %d",&n);
printf("Enter the elements:");
for(i=1;i<=n;i++)
scanf(" %d",&a[i]);
quick(a,1,n);
printf("\n The sorted elements in the array are:");
for(i=1;i<=n;i++)
printf(" %d",a[i]);
getch();
}

void quick(int a[],int first,int last)
{
if(first<last)
{
pivot=a[first];
i=first;
j=last;
while(i<j)
{
while(a[i]<=pivot&&i<last)
i++;
while(a[j]>=pivot&&j>first)
j--;
if(i<j)
swap(a,i,j);
}
swap(a,first,j);
quick(a,first,j-1);
ick(a,j+1,last);
}
}
void swap(int a[],int i,int j)
{
int temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}

### Sort the given list of numbers using Heap Sort MC9217 DATA STRUCTURES LAB Anna University lab manual download

Sort the given list of numbers using Heap Sort MC9217 DATA STRUCTURES LAB Anna University lab manual download

Aim: To write a program to sort the given list of numbers using heap sort.

Algorithm:

1. Start
2. Read the value of n
3. check while(n>=2) then item =delete heap(a,n)
a[n]=item, n--
1. Insert heap(assigning int var) while (i>1) && (item>a[par]) then
A[i]=a[par], i=par, par=i/2
1. Check if (par<1) then par=1
Delete heap (assign value)
1. Check while (right<=n) then if (Last ) = a[left]&&
[last]=a[right] then a[i]=last
1. Else if [a(left)]=a[right] then
A[i]=a[left], i=left; else a[i]=a[right]
1. Stop

Program Code
#include<stdio.h>
#include<math.h>
void heapsort(int x[],int n);
void main()
{
int a[100],n,i;
clrscr();
printf("\n\tHEAP SORT");
printf("\nEnter the number of elements:");
scanf("%d",&n);
printf("Enter the elements:\n");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
heapsort(a,n);
printf("\n The sorted elements in the array are:");
for(i=1;i<=n;i++)
printf("\n%d",a[i]);
getch();
}
void cheap(int x[20],int n)
{
int s,f,key,q;
for(q=2;q<=n;++q)
{
s=q;
key=x[q];
f=(int)(s/2);
while((s>1)&&(key>x[f]))
{
x[s]=x[f];
s=f;
f=(int)(s/2);
if(f<1)
f=1;
}
x[s]=key;
}
}
void heapsort(int x[20],int n)
{
int i,temp,s,f,key;
cheap(x,n);
for(i=n;i>=2;--i)
{
temp=x[1];
x[1]=x[i];
x[i]=temp;
s=1;
key=x[s];
f=2;
if((f+1)<i)
if(x[f+1]>x[f])
f=f+1;
while((f<=(i-1))&&(x[f]>key))
{
x[s]=x[f];
s=f;
f=2*s;
if((f+1)<i)
if(x[f+1]>x[f])
f=f+1;
else
if(f>n)
f=n;
x[s]=key;
}
}
}

### Binary Search Tree implementation MC9217 DATA STRUCTURES LAB Anna University lab manual download

Binary Search Tree implementation MC9217 DATA STRUCTURES LAB Anna University lab manual download

Aim: To write a program to implement Binary Search Tree

Algorithm:

1. Start
3. If option=1 then read x
And check if root is Null then assign root as t
1. Else store current data as x and print it
If (curr->data=x) then assign left child to curr and check if(curr=null)
Prev->lchild=t
1. Else     Prev=curr, curr=curr->rchild then check if(curr==Null)then pre-> rchild=t
2. Print the value of x
3. Enter the no of deleted x
Check p is not null and then assign lchild as p
1. If p is null then print x
Check P as root then assign c as root. Then delete the node p
1. Stop

Logical Description

### Insertion

Insertion begins as a search would begin; if the root is not equal to the value, we search the left or right subtrees as before. Eventually, we will reach an external node and add the value as its right or left child, depending on the node's value. In other words, we examine the root and recursively insert the new node to the left subtree if the new value is less than the root, or the right subtree if the new value is greater than or equal to the root.

### Deletion

There are several cases to be considered:
• Deleting a leaf: Deleting a node with no children is easy, as we can simply remove it from the tree.
• Deleting a node with one child: Delete it and replace it with its child.
• Deleting a node with two children: Suppose the node to be deleted is called N. We replace the value of N with either its in-order successor (the left-most child of the right subtree) or the in-order predecessor (the right-most child of the left subtree).
Once we find either the in-order successor or predecessor, swap it with N, and then delete it. Since both the successor and the predecessor must have fewer than two children, either one can be deleted using the previous two cases. A good implementation avoids consistently using one of these nodes, however, because this can unbalance the tree.

Program Code
/*BINARY SEARCH TREE*/
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct node
{
int data;
struct node *left,*right;
}*tree;
void create();
void insert();
void del();
struct node *maketree(int);
void display(struct node*);
void setleft(struct node *,int);
void setright(struct node *,int);
void insert()
{
struct node *p,*q;
int num;
printf("\n\t\tEnter The Node Value : ");
scanf("%d",&num);
p=q=tree;
while((num!=p->data)&&(q!=NULL))
{
p=q;
if(num<p->data)
q=p->left;
else
q=p->right;
}
if(num==p->data)
printf("\n\t\tDuplicate Value");
else if(num<p->data)
setleft(p,num);
else
setright(p,num);
}
void main()
{
int ch;
clrscr();
printf("\n\t\t\tBINARY SEARCH TREE");
printf("\n\t\t\t~~~~~~~~~~~~~~~~~~~~~");
printf("\n\t\t\t  1.CREATION");
printf("\n\t\t\t  2.INSERTION");
printf("\n\t\t\t  3.DELETION");
printf("\n\t\t\t  4.DISPLAY");
printf("\n\t\t\t  5.EXIT\n");
do
{
printf("\n\t\tEnter The Choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1: create(); break;
case 2: insert(); break;
case 3: if(tree==NULL)
printf("\n\t Tree Empty");
else
del();
break;
case 4: printf("\n\t\tTREE CONTAINS : ");
display(tree);
printf("\n");
break;
default:printf("\n\t\tEXIT");
}
}while(ch<=4);
getch();
}
struct node *maketree(int val)
{
struct node *t=(struct node *)malloc(sizeof(struct node));
t->data=val;
t->left=t->right=NULL;
return(t);
}
void create()
{
int n,i,num;
printf("\n\t\tEnter The No Of Node :");
scanf("%d",&n);
printf("\n\t\tEnter The No Of Node :");
scanf("%d",&num);
tree=maketree(num);
for(i=2;i<=n;i++)
insert();
}
void display(struct node *p1)
{
if(p1==NULL)
return;
display(p1->left);
printf("%d",p1->data);
display(p1->right);
}
void setleft(struct node *p1,int val)
{
if(p1==NULL)
printf("\n\t\tVoid Insertion");
else if(p1->left!=NULL)
printf("\n\t\tInvalid Insertion");
else
p1->left=maketree(val);
}
void setright(struct node *p1,int val)
{
if(p1==NULL)
printf("\n\t\tVoid Insertion");
else if(p1->right!=NULL)
printf("\n\t\tInvalid Insertion");
else
p1->right=maketree(val);
}
void del()
{
struct node *p,*q,*rp,*f,*s;
int num;
p=tree;
q=NULL;
printf("\n\t\tEnter The Node To Be Deleted : ");
scanf("%d",&num);
while((p!=NULL)&&(p->data!=num))
{
q=p;
p=(num<p->data)?p->left:p->right;
}
if(p==NULL)
{
printf("\n\t\tVoid Deletion");
return;
}
if(p->left==NULL)
rp=p->right;
else if(p->right==NULL)
rp=p->left;
else
{
f=p;
rp=p->right;
s=rp->left;
while(s!=NULL)
{
f=rp;
rp=s;
s=rp->left;
}
if(f!=p)
{
f->left=rp->right;
rp->right=p->right;
}
rp->left=p->left;
}
if(q==NULL)
tree=rp;
else
p=(q->left)?(q->left=rp):(q->right=rp);
}

### Binary Tree Traversals MC9217 DATA STRUCTURES LAB Anna University lab manual download

Binary Tree Traversals MC9217 DATA STRUCTURES LAB Anna University lab manual download

Aim : To write a program to Create a binary search tree and do the following traversals
(i)In-order   (ii) Pre order    (iii) Post order

Algorithm :

1. Start
2. Read the values of ch
3. If ch=1 then it traverse through Inorder
Inorder(T-left)
Print(T->data)
Inorder(T->right)
1. if ch=2 then it traverse through
Postorder         Postorder(T->left)
Postorder(T->right)
Preorder(T->right)
1. if ch=2 then it traverse through
Post order        postorder(T->left)
Postorder(T->right)
Print(T->data)
1. Print the element
2. Stop the process.

Logical Description
The tree structures can be traversed in many different ways. Starting at the root of a binary tree, there are three main steps that can be performed and the order in which they are performed define the traversal type. These steps (in no particular order) are: performing an action on the current node (referred to as "visiting" the node), traversing to the left child node, and traversing to the right child node. Thus the process is most easily described through recursion.
To traverse a non-empty binary tree in preorder, perform the following operations recursively at each node, starting with the root node:
1. Visit the node.
2. Traverse the left subtree.
3. Traverse the right subtree.
To traverse a non-empty binary tree in inorder, perform the following operations recursively at each node, starting with the root node:
1. Traverse the left subtree.
2. Visit the node.
3. Traverse the right subtree.
To traverse a non-empty binary tree in postorder, perform the following operations recursively at each node, starting with the root node:
1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the node.
Program Code
# include<stdio.h>
# include <conio.h>
# include <malloc.h>

struct node
{
struct node *left;
int data;
struct node *right;
};

void main()
{
void insert(struct node **,int);
void inorder(struct node *);
void postorder(struct node *);
void preorder(struct node *);
struct node *ptr;
int will,i,num;
ptr = NULL;
ptr->data=NULL;
clrscr();
printf("Tree Traversal\n");
printf("\nEnter the number of terms to add ");
scanf("%d",&will);
for(i=0;i<will;i++)
{
printf("\nEnter the item");
scanf("%d",&num);
insert(&ptr,num);
}

getch();
printf("\nINORDER TRAVERSAL");
inorder(ptr);
getch();
printf("\nPREORDER TRAVERSAL");
preorder(ptr);
getch();
printf("\nPOSTORDER TRAVERSAL");
postorder(ptr);
getch();
}
void insert(struct node  **p,int num)
{
if((*p)==NULL)
{
(*p)=malloc(sizeof(struct node));
(*p)->left = NULL;
(*p)->right = NULL;
(*p)->data = num;
return;
}
else
{
if(num==(*p)->data)
{
printf("\nREPEATED ENTRY ERROR VALUE REJECTED");
return;
}
if(num<(*p)->data)
{
insert(&((*p)->left),num);
}
else
{
insert(&((*p)->right),num);
}
}
return;
}

void inorder(struct node *p)
{
if(p!=NULL)
{
inorder(p->left);
printf(" %d ",p->data);
inorder(p->right);
}
else
return;
}
void preorder(struct node *p)
{
if(p!=NULL)
{
printf(" %d ",p->data);
preorder(p->left);
preorder(p->right);
}
else
return;
}
void postorder(struct node *p)
{
if(p!=NULL)
{
postorder(p->left);
postorder(p->right);
printf(" %d ",p->data);
}
else
return;
}