WARSHALL’S ALGORITHM

WARSHALL’S ALGORITHM

SOURCE CODE:


#include “ stdio.h “
#include “ conio.h “
void main()
{
int n,i,j,k,p[10][10],a[10][10];
clrscr();
printf("Enter The Number Of Nodes: ");
scanf("%d",&n);

for(i=0;i < n;i++)
{
printf("\n");
for(j=0;j < n;j++)
{
scanf("%d",&a[i][j]);
}
}
for(i=0;i < n;i++)
{
for(j=0;j < n;j++)
{
if(a[i][j]==0)
p[i][j]=0;
else
p[i][j]=1;
}
}
for(k=0;k < n;k++)
{
for(i=0;i < n;i++)
{
for(j=0;j < n;j++)
{
p[i][j]=p[i][j]||(p[i][k]&&p[k][j]);
}
}
}
printf("\n");
for(i=0;i < n;i++)
{
for(j=0;j < n;j++)
{
printf("%d ",p[i][j]);
}
printf("\n");
}
getch();
}



OUTPUT:


Enter The Number Of Nodes: 4

0
1
0
0

0
0
0
1

0
0
0
0

1
0
1
0

1 1 1 1
1 1 1 1
0 0 0 0

HUFFMAN ALGORTHAM

HUFFMAN ALGORTHAM

CODING:

#include ” stdio.h “
#include “ conio.h “
#define true 1
#define false 0
#define MAXBITS 50
#define MAXSYMBS MAXBITS
#define MAXNODES 2*MAXSYMBS-1
struct codetype
{
int bits[MAXBITS];
int startpos;
};
struct nodetype
{
int frequency;
int parent;
int isleft;
};
void pqinsert(int);
int pqmindelete();
struct nodetype node[MAXNODES];
void main()
{
struct codetype cd,code[MAXSYMBS];
int i;
int no_of_symbols;
int nextavilnode;
int bitcounter;
int leftnode,rightnode;
int root;
int thisnode;
char symbol,alphabet[MAXSYMBS];
clrscr();
for(i=0;i < MAXSYMBS;i++)
{
alphabet[i]=' ';
}
printf("Enter the no-of-symbols:");
scanf("\n%d",&no_of_symbols);
printf("\nEnter the symbol and frequency:");
for(i=0;i < no_of_symbols;i++)
{
scanf("%s%d",&symbol,&node[i].frequency);
pqinsert(i);
alphabet[i]=symbol;
}



for(nextavilnode=no_of_symbols;nextavilnode < 2*no_of_symbols-
1;nextavilnode++)
{
leftnode=pqmindelete();
rightnode=pqmindelete();
node[leftnode].parent=nextavilnode;
node[rightnode].parent=nextavilnode;
node[leftnode].isleft=true;
node[rightnode].isleft=false;
node[nextavilnode].frequency=node[leftnode].frequency+node[rightnode].
frequency;
pqinsert(nextavilnode);
}
root=pqmindelete();
for(i=0;i < no_of_symbols;i++)
{
cd.startpos=MAXBITS;
thisnode=i;
while(thisnode!=root)
{
--cd.startpos;
cd.bits[cd.startpos]=node[thisnode].isleft?0:1;
thisnode=node[thisnode].parent;
}
for(bitcounter=cd.startpos;bitcounter < MAXBITS;bitcounter++)
{
code[i].bits[bitcounter]=cd.bits[bitcounter];
}
code[i].startpos=cd.startpos;
}
printf("\nSymbols Frequency AssignBits");
for(i=0;i < no_of_symbols;i++)
{
printf("\n%c\t%d\t\t",alphabet[i],node[i].frequency);
for(bitcounter=code[i].startpos;bitcounter < MAXBITS;bitcounter++)
{
printf("%d",code[i].bits[bitcounter]);
}
Printf("\n");
}
getch();
}
int rootnodes=-1;
void pqinsert(int which)
{
int thisnode,previous;
if(rootnodes==-1)
{
node[which].parent=-1;
rootnodes=which;
}
else
{
thisnode=rootnodes;
previous=-1;

while(thisnode!=-1&&node[thisnode].frequency < node[which].frequency)
{
previous=thisnode;
thisnode=node[thisnode].parent;
}
node[which].parent=thisnode;
if(previous!=-1)
{
node[previous].parent=which;
}
else
{
rootnodes=which;
}
}
}
int pqmindelete()
{
int thisnode=rootnodes;
rootnodes=node[thisnode].parent;
return thisnode;
}








OUTPUT:

Enter the no-of-symbols:4

Enter the symbol and frequency:
S 21
H 28
A 11
M 7

Symbols Frequency AssignBits
S 21 11

H 28 0

A 11 101

M 7 100

Implementation of Queues

Linked Implementation of Queues
The items are deleted from the front of a queue and inserted at the rear. A pointer to the first element of a list represent the front of the queue. Another pointer to the last element of the list represent the rear of the queue. If (empty(q))
{
Printf(“Queue underflow”);
Exit(1);
}
P=q.front;
X=info(p);
q.front=next(p) ;
if(q.front == null)
q.rear = null;
freenode(p);
return(x);
The operation insert(q,x) is implemented by
P = getnode();
Info(p) = x;
Next(p) = null;
If (q.rear == null)
q.front = p;
else
next(q.rear) = p;
q.rear = p;

Linked Implementation of Queues

Linked Implementation of Queues

The items are deleted from the front of a queue and inserted at the rear. A pointer to the first element of a list represent the front of the queue. Another pointer to the last element of the list represent the rear of the queue.

If (empty(q))

{

Printf(“Queue underflow”);

Exit(1);

}

P=q.front;

X=info(p);

q.front=next(p) ;

if(q.front == null)

q.rear = null;

freenode(p);

return(x);

The operation insert(q,x) is implemented by

P = getnode();

Info(p) = x;

Next(p) = null;

If (q.rear == null)

q.front = p;

else

next(q.rear) = p;

q.rear = p;

Array implementation of lists

Array implementation of lists

A list is simply a collection of nodes, the nodes cannot be ordered by the array ordering; each contain within itself a pointer to its successor. Thus a group of 500 nodes might be declared as an array node as follows.

#define NUMNODES 500

Struct nodetype

{

Int info, next;

};

Struct nodetype node[NUMNODES];

Limitations of the Array Implementation

Under the array implementation, a fixed set of nodes represented by an array is established at the start of execution.

The number of nodes that are needed often cannot be predicted when a program is written.

The number of nodes are declared must remain allocated to the program throughout its execution.

The solution to this problem is to allow nodes that are dynamic rather than static.

Allocating and Freeing Dynamic Variables

Allocating and Freeing Dynamic Variables

If X is any object, &X is a pointers to help implement dynamic linked lists.
In C a pointer variable to an integer can be created by the declaration

Int *p;

Once a variable p has been declared as a pointer to a specific type of object, it must be possible to dynamically create an object of that specific type and assign its address to p.

Malloc dynamically allocates a portion of memory and returns a pointer to an item.

Pi = (int *) malloc(sizeof(int));

Pr = (float *)malloc(sizeof(float));



Linked list using Dynamic variables

The capability of dynamically allocating and freeing a variable.

Struct node
{
Int info;
Struct node * next;
};


Tydedef struct node *NODEPTR;

NODEPTR p;

P=getnode();

NODEPTR getnode()
{
NODEPTR p;
P = (NODEPTR) malloc(sizeof(struct node));
Return(p);
}


Freenode(p);

Circular List

Circular List

The stack as a Circular List

Empty(pstack)

NODEPTR 8pstack;
{
Return((*pstack == NULL) ? TRUE : FALSE);
}




Push(pstack, x)

NODEPTR *pstack;
Int x;
{
NODEPTR P;
P = getnode();
p->info = x;
if (empty(pstack) == TRUE)
*pstack = p;
Else
p->next = (*pstack)->next;
(*pstack) -> next = p;
}



Pop(pstack)

NODEPTR *pstack;
{
Int x;
NODEPTR p;
If (empty(pstack) == TRUE)
{
Printf(“stack underflow”);
Exit(1);
}
P=(*pstack) -> next;
X=p->info;
If ( p == *pstack)
*pstack = NULL;
Else
(*pstack) - > next = p->next;
Freenode(p);
Return(x);
}

Data Structures Lab Manual

Lab Manual Algorithms

Program List


1. Stack using Arrays

2. STACK using Linked List

3. Queues using Arrays

4. Queue using Linked List

5. Tree Traversal

6. Merge sort

7. Graph using DFS

8. Graph Traversal using BFS

9. Warshall’s Algorithm

10. Dijkstra’s Algorithm

11. Huffman Algorithm

12. Insertion sort

Stack using Arrays

Representation of Stack using Arrays

Algorithm:

Step 1: Create a push operation with one argument, the element to be added

Step 2: Create a POP function with one argument, the address of the element to store the popped operation

Step 3: Create a function PEEK with one argument, the address of the element of store the top value

Step 4: Create a function ISEMPTY with no argument for stack empty condition

Step 5: Create a function ISFULL for checking for stack full.

Step 6: Sop the program execution

STACK using Linked List

Representation of STACK using Linked List

Algorithm:


Step 1: Create a structure with data and Link field

Step 2: Allocate the memory for the new node

Step 3: Insert the value into the new node using PUSH operation

Step 4: Release the allocated memory for deleting the item from the structure

Step 5: Create a function to retrieve the contents from the Top of the Stack

Step 6: Create a function for display the items from the stack.

Step 7: Create a function for Is Empty condition

Step 8: Create a function for Is Full condition.

Step 9: Create a function to count the number of nodes in the stack.

Step 10 : Stop the execution.

Queues using Arrays

Queues using Arrays

Algorithm


Step 1: Create a function Enqueue() with two arguments

Step 2: Assign the new element in the array by increasing the Rear variable.

Step 3: Create a function Dequeue with two arguments

Step 4: Increment the Front variable by 1.

Step 5: Create a function Isempty with no arguments

Step 6: Check whether the front pointer and rear is equal to zero.

Step 7: If true, the queue is empty otherwise not empty.

Step 8: Create a function Isfull to check whether the queue is full or not.

Step 10 : Stop the execution.

Queue using Linked List

Representation of Queue using Linked List

Algorithm:

Step 1: Create a structure with data and link field.

Step 2: Allocate a memory for the new node using a getnode().

Step 3: Insert the item into the queue

Step 4: Delete the node by releasing the memory of the node.

Step 5: create a function to retrieve the contents from the top of the queue.

Step 6: Display the contents of the queue by traversing through the queue.

Step 7: Stop the execution.

Tree Traversal

Binary Search Tree Traversal

Aim : To create a binary search tree and do the following traversal

Algorithm :

Preorder Traversal

preorder(node)
print node.value
if node.left ≠ null then preorder(node.left)

if node.right ≠ null then preorder(node.right)

Inorder Traversal

inorder(node)
if node.left ≠ null then inorder(node.left)
print node.value
if node.right ≠ null then inorder(node.right)

Post Order Traversal

postorder(node)
if node.left ≠ null then postorder(node.left)
if node.right ≠ null then postorder(node.right)
print node.value

Merge sort

Merge sort

Aim : To sort the given elements using Merge Sort

Algorithm:

function merge_sort(m)
var list left, right, result
if length(m) < = 1
return m
var middle = length(m) / 2 - 1
for each x in m up to middle
add x to left
for each x in m after middle
add x to right

left = merge_sort(left)
right = merge_sort(right)
if left.last_item > right.first_item
result = merge(left, right)
else
result = append(left, right)
return result

function merge(left,right)
var list result
while length(left) > 0 and length(right) > 0
if first(left) < = first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
end while
if length(left) > 0
append left to result
else
append right to result
return result

Graph using DFS

Depth-first search

Aim : Program to traverse a graph using DFS

Algorithm:

Step 1: consider that the DFS is beginning from the starting vertex A. Process the vertex A and mark it as visited.

Step 2: Using the adjacency matrix of the graph find the vertex along the path which begins vertex A, that has not been visited yet. Process the vertex and consider this as the new vertex and mark the vertex as visited.

Step 3: Repeat Step 2 using the new search vertex. If no vertices back track to the previous node and continue the search from there.

Step 4: When backtracking to the previous search node in step 3 is impossible, the search from the originally chosen search node is complete.

Step 5: If the graph still contains unvisited nodes, choose any vertex that has not been visited and repeat step 1 to 4.

Graph Traversal using BFS

Breadth-first search

Aim : Program to demonstrate Graph Traversal using BFS

Algorithm:

Step 1: Consider any vertex in the graph. Process the vertex A and mark it as visited.

Step 2: Using the adjacency matrix of the graph proceed to the next vertex which has an edge connection wise the vertex considered in step 1.

Step 3: Backtrack to the vertex considered in step 1 descend along an edge towards an unvisited vertex and mark the new vertex as visited

Step 4: Repeat step3 until all vertices adjacent to the node in step 1 have been marked as visited.

Step 5: Stop the execution

Warshall’s Algorithm

Aim : To create a program to find the shortest path in a given graph using Warshall’s Algorithm.

Algorithm :

for(i=0; i < MAXNODES; ++i)
for(j=0; j < MAXNODES; ++j)
path[i][j]=path k-1[i][j] (path k-1[i][k] && path k-1[k][j]);


for(i=0; i < MAXNODES; ++i)
for(j=0; j < MAXNODES; ++j)
path k[i][j] = path k-1[i][j];
for(i=0;i < MAXNODES; ++i)
if(path k-1[i][k] == TRUE)
for(j=0;j < MAXNODES; ++j)
path k[i][j] = path k-1[i][j] path k-1[k][j];

Dijkstra’s Algorithm

Aim: To create a program to find the shortest path in a given graph using Dijkstra’s Algorithm.

Algorithm :

function Dijkstra(Graph, source):
for each vertex v in Graph:
dist[v] := infinity
previous[v] := undefined
dist[source] := 0
Q := the set of all nodes in Graph
while Q is not empty: // The main loop
u := vertex in Q with smallest dist[]
if dist[u] = infinity:
break
remove u from Q
for each neighbor v of u:
alt := dist[u] + dist_between(u, v)
if alt < dist[v]:
dist[v] := alt
previous[v] := u
return previous[]

Huffman Algorithm

Aim : Program for performing the Huffman Algorithm

Algorithm:


For(i=0;i < n; i++)
{
P=maketree(frequency[i]);
Position[i] = p;
Pqinsert(rootnodes, p);
}
While (root nodes contain more than one item)
{
P1=pqmindelete(rootnodes);
P2=pqmindelete(rootnodes);
P=maketree ( info (p1) + info (p2));
Setleft(p, p1);
Setright (p, p2);
Pqinsert(rootnodes, p);}

Root= pqmindelete(rootnodes);
For(i=0;i < n;i++)
{
P=position[i];
Code[i]=the null bit string;
While (p!= root)
{
If(isleft (P))
Code[i]= 0 followed by code[i];
Else
Code[i] = 1 followed by code[i];
P=father(p);
}
}

Insertion sort

Aim: Program to sort the given numbers using Insertion sort.

Algorithm:

insertionSort(array A)

begin
for i := 1 to length[A] - 1 do
begin
value := A[i];
j := i - 1;
while j >= 0 and A[j] > value do
begin
A[j + 1] := A[j];
j := j - 1;
end;
A[j + 1] := value;
end;
end;