DATA STRUCTURES LAB MANUAL

EX.NO.1      
IMPLEMENTATION OF SINGLY LINKED LIST

AIM:

         To   implement the  singly linked list program using C.

ALGORITHM:

 STEP 1: Start the program

STEP 2: Define node structure and read the choice of operation.

STEP 3: Enter the element to be insert, then assign some temporary node and add 

              data to the data  field.
              Then list next is null assign the list->next to new node
               Else new node next =pnext and pnext=new node
STEP 4: Create the memory using malloc function.
STEP 5: Check whether the next field is NULL or not.

STEP 6:  Enter the element to be delete, then
               Create a new temp node using malloc function and
               assign the p=find previous(x) then, pnext !=null perform
               the following   temp=pnext,   pnext=tempnext   
STEP 7: Delete the element free(temp)

STEP 8: Display the element in the list

STEP 9: Stop the program


















PROGRAM:            SINGLY LINKED LIST

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include<stdlib.h>
void insert(int );
void deletion(int );
void display();
void main()
{
int data, ch;
clrscr();
printf("1.insert\n2.delete\n3.display\n4.exit");
do
{
printf("\nenter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\n enter the element to insert:");
scanf("%d", data);
insert(data);
break;
case 2: printf("\n enter the element to deleted:");
scanf("%d",&data);
deletion(data);
break;
case 3:display();
break;
case 4: exit(0);
}
}
while(ch<4);
getch();
}
struct node*find(int);
struct node*findprevious(int);
struct node
{
int element;
struct node *next;
}*list=NULL,*p;
void insert(int x)
{
struct node *newnode;
int pos;
newnode=malloc(sizeof(struct node));
newnode->element=x;
if(list->next==NULL)
{
list->next=newnode;
newnode->next=NULL;
}
else
{
printf("\nenter the value after which the element to be inserted:");
scanf("%d",&pos);
p=find(pos);
newnode->next=p->next;
p->next=newnode;
}
}
struct node*find(int s)
{
p=list->next;
while(p!=NULL&&p->element!=s)
p=p->next;
return p;
}
void deletion(int x)
{
struct node*temp;
temp=malloc(sizeof(struct node));
p=findprevious(x);
if(p->next!=NULL)
{
temp=p->next;
p->next=temp->next;
printf("\n the deleted element is %d",temp->element);
free(temp);
}
else
printf("\nelement not found is the list");
}
struct node*findprevious(int s)
{
p=list;
while(p!=NULL&&p->element!=s)
p=p->next;
return p;
}
void display()
{
if(list->next==NULL)
printf("\n list is empty");
else
{
p=list->next;
printf("\n the content of the list are:");
while(p!=NULL)
{
printf("%d->",p->element);
p=p->next;
}
printf("NULL");
}
}

OUTPUT:

1.INSERT BEGIN
2.INSERT END
3.DELETE
4. DISPLAY
5.EXIT

Enter your choice : 1
Enter the data to be inserted: 25
Enter your choice: 2
Enter the data to be inserted: 65
Enter your choice: 3
Enter the data to be deleted: 25
Data 25 is deleted
Enter the choice: 3
The contents are : 65
Enter your choice: 5






















RESULT:
        Thus   the implementation of singly linked list   has been done.








EX.NO:1B 
IMPLEMENTATION OF DOUBLY LINKED LISTS


AIM:
             To  implement the doubly linked list by using ‘C’ program.

ALGORITHM:
 Step 1: Start the process.
 Step 2:  Initialize the variable del, x , choice and using switch
     case perform insertion, deletion, display operation.
 Step 3: Using malloc function allocate the memory space and
            initialize the tree structure.
 Step 4: Perform the operations such as insert, delete, display.
 Step 5: Enter the element to be inserted.
 Step 6: Enter the choice 2 to delete the element.
 Step 6: Enter the choice 3 to display all the content of lists.
 Step 7: Get the result.
 Step 8: Stop the program.



























PROGRAM:            DOUBLY LINKED LIST

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include<stdlib.h>
struct node
{
int data;
struct node *lptr,*rptr;
}*head;
struct node *insbeg(int x,struct node *first);
struct node *insend(int x,struct node *first);
void display(struct node *first);
struct node*dele(struct node *first,int del);
void main()
{
 int choice,x,del;
 head=NULL;
 clrscr();
 printf("1.InsertBegin\n2.InsertEnd\n3.delete");
 printf("\n4.Display\n5.Exit");
 while(1)
 {
 printf("\nEnter Your chioce::");
 scanf("%d",&choice);
 switch(choice)
 {
    case 1: printf("\n Enter the data to be inserted:");
        scanf("%d",&x);
        head=insbeg(x,head);
        break;
    case 2: printf("\nEnter the data to be inserted:");
        scanf("%d",&x);
        head=insend(x,head);
        break;
    case 3:
        printf("\n Enter the date to be deleted:");
        scanf("%d",&del);
        head=dele(head,del);
        break;
    case 4:
        display(head);
        break;
    case 5:
        exit(0);
    default:
        printf("\n Invalid Entry !!!!");
        }    }
    getch();
    }
    struct node *insbeg(int x,struct node *first)
    {
    struct node *new,*cur,*prev;
    new=malloc(sizeof(struct node));
    if(first==NULL)
    {
        new -> data=x;
        new->lptr=NULL;
        new->rptr=NULL;
        return new;
    }
    else
    {
      new->data=x;
      new->lptr=NULL;
      new->rptr=first;
      return new;
     }    }
    struct node *insend(int x,struct node *first)
    {
      struct node *new,*cur,*prev;
      new=malloc(sizeof(struct node));
      if(first==NULL)
      {
       new -> data=x;
        new->lptr=NULL;
        new->rptr=NULL;
        return new;
      }
      else
      {
    cur=first;
    while(cur->rptr!=NULL)
    {
        prev=cur;
        cur=cur->rptr;
    }
    cur->rptr=new;
    new->data=x;
    new->lptr=cur;
    new->rptr=NULL;
    return first;
      }   }
   void display(struct node *first)
   {
    struct node *temp;
    temp=first;
    if(temp==NULL)
    printf("\n No data present !!!");
    while(temp!=NULL)
    {
    printf("%d\t",temp->data);
    temp=temp->rptr;
    }
    getch();
    }
    struct node *dele(struct node *first, int del)
    {
    struct node *prev,*cur;
    cur=first;
    if(first==NULL)
    {
    printf("data no present");
    getch();
    }
    else if(first->data==del)
    {
    printf("\n data %d is deleted",first->data);
    first=first->rptr;
    getch();
    return first;
    }
    else
    {
    while(cur->rptr!=NULL&&cur->data!=del)
    printf("\n data not present");
    if(cur->rptr!=NULL&&cur->data==del)
    {
    prev->rptr=cur->rptr;
    (cur->rptr)->lptr=prev;
    printf("\n data%d is deleted",cur->data);
    }
    else if(cur->rptr==NULL&&cur->data==del)
    {
    prev->rptr=NULL;
    printf("\n data %d is deleted",cur->data);
    }
     getch();
     return first;
     }   
 }

















OUTPUT:
1.INSERT BEGIN
2.INSERT END
3.DELETE
4. DISPLAY
5.EXIT

Enter your choice : 1
Enter the data to be inserted: 25
Enter your choice: 2
Enter the data to be inserted: 65
Enter your choice: 3
Enter the data to be deleted: 25
Data 25 is deleted
Enter the choice: 3
The contents are : 65
Enter your choice: 5
















RESULT:
            Thus the implementation of doubly linked list program has been done.



















EX.NO.2
IMPLEMENTATION OF POLYNOMIAL ADDITION

AIM:
      To implement a polynomial addition program using c.

ALGORITHM:
  Step 1: Start the process.
 Step 2:Create the structure of poly
 Step 3:.Enter the value of first polynomial coefficient and power.
 Step 4: Display the first polynomial
 Step 5: Enter the value of second polynomial coefficient and power
 Step 6: Display the second polynomial
 Step 7: Check whether the second polynomial power is > first polynomial                      
set poly power =poly two power, poly coeffi=poly2 coeff
Else check whether the first polynomial power is > second polynomial              set poly power =poly one  power, poly coeffi=poly1 coeff
 Step 8: Else add the coefficients.
 Step 9: Display the results
 Step 10: Stop the program.

























PROGRAM:
POLYMOMIAL ADDITION
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include<stdlib.h>
struct link
{
int coeff;
int pow;
struct link *next;
};
struct link *poly1=NULL, *poly2=NULL,*poly=NULL;
void create(struct link *node)
{
char ch;
do
{
printf("\n enter coeff");
scanf("%d",&node->coeff);
printf("\nenter power");
scanf("%d",&node->pow);
node->next=(struct link*)malloc(sizeof(struct link));
node=node->next;
node->next=NULL;
printf("\ncontinue(y/n):");
ch=getch();
}
while(ch=='y'||ch=='y');
}
void display(struct link *node)
{
while(node->next!=NULL)
{
printf("%dx^%d",node->coeff,node->pow);
node=node->next;
if(node->next!=NULL)
printf("+");
}
}
void polyadd(struct link *poly1, struct link *poly2,struct link *poly)
{
while(poly1->next&&poly2->next)
{
if(poly1->pow>poly2->pow)
{
poly->pow=poly1->pow;
poly->coeff=poly1->coeff;
poly1=poly1->next;
}
else if(poly1->pow<poly2->pow)
{
poly->pow=poly2->pow;
poly->coeff=poly2->coeff;
poly2=poly2->next;
}
else
{
poly->pow=poly1->pow;
poly->coeff=poly1->coeff+poly2->coeff;
poly1=poly1->next;
poly2=poly2->next;
}
poly->next=(struct link*)malloc(sizeof(struct link));
poly=poly->next;
poly->next=NULL;
}
while(poly1->next||poly2->next)
{
if(poly1->next)
{
poly->pow=poly1->pow;
poly->coeff=poly1->coeff;
poly1=poly1->next;
}
if(poly2->next)
{
poly->pow=poly2->pow;
poly->coeff=poly2->coeff;
poly2=poly2->next;
}
poly->next=(struct link*)malloc(sizeof(struct link));
poly=poly->next;
poly->next=NULL;
}
}
void main()
{
poly1=(struct link*)malloc(sizeof(struct link));
poly2=(struct link*)malloc(sizeof(struct link));
poly=(struct link*)malloc(sizeof(struct link));
clrscr();
printf("\enter the first polynomial");
create(poly1);
printf("\nfirst polynomial");
display(poly1);
printf("\nenter the second polynomial");
create(poly2);
printf("\nsecond polynominal");
display(poly2);
polyadd(poly1,poly2,poly);
printf("\n addition of two polynominal");
display(poly);
getch();
}

OUTPUT:

ENTER THE FIRST POLYNOMIAL:
ENTER  THE COEFF 2
ENTER  POWER 3
CONTINUE(Y/N):Y

ENTER  THE COEFF 3
ENTER  POWER 2
CONTINUE(Y/N):Y
FIRST POLYNOMIAL 2X^3+3X^2


ENTER THE  SECOND POLYNOMIAL:
ENTER  THE COEFF 2
ENTER  POWER 3
CONTINUE(Y/N):Y

ENTER  THE COEFF 2
ENTER  POWER 3
CONTINUE(Y/N):Y
SECOND  POLYNOMIAL 2X^3+2X^3
ADDITION OF TWO POLYNOMIALS  4X^3 +3X^2+2X^3


     






















RESULT:

      Thus the implementation of polynomial addition using c program  has been done.



EX.NO:3
IMPLEMENTATION OF INFIX TO POSTFIX
AIM:
      To write a ‘c’ program for implementation of infix to postfix expression.
ALGORITHM:
       Step 1: Start the program.
       Step 2: Declare the variable and enter the choice of operation.
       Step 3: Perform the operation  such as push ,pop,into post operation
       Step 4: Perform push operation when   the character is operand then
                     insert an element into the top of the stack.
       Step 5: Perform pop operation when   the character is operator then
                     Remove the  top element from  the stack.
       Step 6: According to the input operator ,it will perform push or pop
                   operation.
       Step  7: Get the result.
       Step 8: Print the result.
       Step 9: Stop the program.























PROGRAM:            INFIX TO POSTFIX

#include<stdio.h>
#include<conio.h>
char inf[40],post[40];
int top=0,st[20];
void postfix();
void push(int);
char pop();
void main()
{
  clrscr();
  printf("Enter your infix expression");
  scanf("%s",inf);
  postfix();
  getch();
}
void postfix()
{
 int i,j=0,len;
 len=strlen(inf);
 for(i=0;i<len;i++)
  {
    switch(inf[i])
    {      case '+':
        while(st[top]>=1)
        {
        post[j++]=pop();
        }
        push(1);
        break;
      case '-':
        while(st[top]>=1)
        {
        post[j++]=pop();
        }
        push(2);
        break;
      case '*':
        while(st[top]>=3)
        {
        post[j++]=pop();
        }
        push(3);
        break;
      case '/':
        while(st[top]>=3)
        {
        post[j++]=pop();
        }
        push(4);
        break;
      case '^':
        while(st[top]>=4)
        {
        post[j++]=pop();
        }
        push(5);
        break;
      case '(':
        push(0);
        break;
      case ')':
        while(st[top]!=0)
        post[j++]=pop();
        top--;
        break;

      default: post[j++]=inf[i];
  }  }
 while(top>0)
 post[j++]=pop();
 printf("The postfix expression is =>\n\n %s",post);
}
void push(int data)
{
   top++;
   st[top]=data;
}
char pop()
{
 int e1;
 char e;
 e1=st[top];
 top--;
 switch(e1)
 {
   case 1:
      e='+';
      break;
   case 2:
     e='-';
      break;
   case 3:
      e='*';
      break;
 case 4:
    e='/';
      break;
 case 5:
    e='^';
      break;
 }
 return(e);
}


OUTPUT:

         ENTER THE INFIX EXPRESSION: A+B
        THE POSTFIX EXPRESSION IS : AB+



















RESULT:

             Thus the conversion of  infix to postfix expression has been implemented successfully.

























EX.NO.4          IMPLEMENTATION OF ARRAY-BASED CIRCULAR QUEUE


AIM:
        To implement the circular queue program using array.
ALGORITHM:
Step 1: Start the program
Step 2:Read the choice of operation using switch case.
Step 3:To create the item creation enter the total number
           of items and enter the element number
Step 4:Push the item .
Step 5:Get the item request from the customer
Step 6: Reject the item.
Step 7: Response from producer.
Step 8:Stop the program.


























CIRCULAR QUEUE

PROGRAM:               
#include<stdio.h>
#include<conio.h>
#define x 20
int a[x],f,r,n;void push(int a[],int t)
{
if(f==1)
f++;
r++;
if(r>n-1)
r=0;
a[r]=t;
}
void pop()
{
a[f]=0;
f++;
if(f>n-1)
f=0;
printf("\n");
printf("ITEMS AFTER REJECTION:\N");
}
void display(int a[])
{
int i;
printf("RESPONSE TIME FROM THE PRODUCER:");
for(i=0;i<=n-1;i++)
printf("%d\t",a[i]);
}
void ins(int a[])
{
int k;
clrscr();
if(((f==0)&&(r==n-1))||(r+1==f))
{
printf("\n");
printf("\n ITEM IS NOT AVAILABLE" );
}
else
{
printf("\n ENTER THE ITEMS:");
scanf("%d",&k);
if(r==n-1)
{
r=0;
a[r]=k;
}
else
{
r++;
a[r]=k;
}
display(a);
}
}
void create()
{
int i,t;
clrscr();
f=r=-1;
printf("ENTER THE TOTAL NO. OF ITEMS:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("ENTER THE ELEMENT:");
scanf("%d",&t);
if(t==999)
break;
push(a,t);
}
}
void main()
{
int s,t,i,opt;
char ch='y';
do
{
clrscr();
printf("\n CIRCULAR QUEUE USING ARRAY" );
printf("\n1.PRODUCER(ITEM CREATION)" );
printf("\n2.REQUEST FROM CONSUMER:" );
printf("\n3.REJECT ITEM" );
printf("\n4.RESPONSE FROM PRODUCER: " );
printf("\n5.EXIT" );
printf("\nENTER UR CHOICE" );
scanf("%d",&opt);
switch(opt)
{
case 1:
create();
display(a);
getch();
break;
case 2:
ins(a);
getch();
break;
case 3:
clrscr();
pop(a);
display(a);
getch();
break;
case 4:
clrscr();
display(a);
getch();
break;
default:
exit(0);
}}
while(opt!=5);
}

OUTPUT:

Circular queue using arrays
 1.Producer(item creation)
 2. request from customer
 3.reject items
 4.response from producer
 5.exit..

Enter your choice:1
Enter the total number of items:6
Enter the items:1
Enter the items:2
Enter the items:3
Enter the items:999
Response item from producer 1  2  3  0  0  0
Enter your choice:2
Enter the items:4

Response item from producer 1  2  3  4 0  0
Enter your choice:2
Enter the items:5
Response item from producer 1  2  3  4  5 0


RESULT:
                Thus the circular queue using array has been successfully executed.
















Ex.No.5
IMPLEMENTATION OF TREE TRAVERSAL
AIM:
       To implement the tree traversal such as in-order, pre-order, post order operation using  C Program.

ALGORITHM:
  Step 1: Start the program and declare the variables.
  Step 2: Get the number of elements to construct the tree and construct the
   binary search tree.
  Step 3: Enter the choice to perform operation 
  Step 4: To perform in-order traversals
    Process the left sub tree
    Process  the root
    Process the right sub tree
   Step 5: To perform the preorder traversals
    Process  the root
    Process the left sub tree
    Process the right sub tree
  Step 6: To perform the postorder traversals
•    Process the left sub tree
•    Process the right sub tree
•    Process  the root
 Step  7: Get the result.
 Step 8 : Print the result.
 Step 9: Stop the program.

















PROGRAM:                TREE TRAVERSAL

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
typedef struct tree *node;
node insert(int,node t);
void inorder(node t);
void preorder(node t);
void postorder(node t);
struct tree
{
 int data;
 struct tree *right,*left;
 }*root;
 void main()
 {
 node t=null;
 int data,ch,i=0,n;
 clrscr();
 printf("\n enter the number of elements in the tree");
 scanf("%d",&n);
 printf("\nthe elements are");
 while(i<n)
 {
   scanf("%d",&data);
   t=insert(data,t);
   i++;
   }
   printf("1.inorder\t2.preorder\t3.postorder\t4.exit");
   do
   {
   printf("\n enter your choice");
   scanf("%d",&ch);
     switch(ch)
     {
     case 1:printf("inorder traversal of the given tree");
        inorder(t);
        break;
     case 2:printf("preorder traversal of the given tree");
        preorder(t);
        break;
     case 3:printf("postorder traversal of the given tree");
        postorder(t);
        break;
     default:printf("exit");
         exit(0);
         }         }while(ch<4);
         getch();
         }
         node insert(int x,node t)
         {
         struct tree *newnode;
         newnode=malloc(sizeof(struct tree));
         if(newnode==null)
           printf("out of space");
         else
         {
         if(t==null)
         {
           newnode->data=x;
           newnode->left=null;
           newnode->right=null;
           t=newnode;
           }
           else
           {
           if(x<t->data)
          t->left=insert(x,t->left);
           else
        t->right=insert(x,t->right);
        }    }
        return t;
        }
           void inorder(node t)
          {
          if(t!=null)
          {
          inorder(t->left);
          printf("%d\t",t->data);
          inorder(t->right);
          }     }
          void preorder(node t)
          {
          if(t!=null)
          {
          printf("%d\t",t->data);
          preorder(t->left);
          preorder(t->right);
          }       }
          void postorder(node t)
          { 
  if(t!=null)
          {
          postorder(t->left);
          postorder(t->right);
          printf("%d\t",t->data);
          }      }





OUTPUT:

        Enter the number of element to construct the tree:3
        The elements are:
                          11
                          10
                           12
             1.Inorder 2.preorder 3.postorder 4.exit
       Enter your choice :1
      In-order traversal’s of the given tree:
           10    11     12
      Enter your choice :2
      Preorder traversal’s of the given tree:
    11    10    12
      Enter your choice :3
      Post-order traversal’s of the given tree:
    10    12    11
      Enter your choice :4















RESULT:

Thus the tree traversal program  such as in-order, pre-order, post-order has been successfully executed.











EX.NO.6    IMPLEMENTATION OF BINARY SEARCH TREE

AIM:
        To implement the binary search tree (BST) using C program.
ALGORITHM:
 Step 1: Start the program.
   Step 2: Define the BST structure and enter the number of elements to be
                inserted.
   Step 3: To insert an element use Insert(data, t).
   Step 4: Enter the element to find the given tree.
   If the tree is empty  print “The search element is not present”
               else if the search element is less than root value ,
               continue the search  in the left sub tree.
               Else if the search element is greater than root value,
               continue the  search in the right sub tree.
              The search element is found, then display the element present.
   Step 5: To find the minimum value in the tree
    Traverse the left sub tree
    Last value in the left sub tree is the minimum value.
   Step 6: To find the maximum value in the tree
•    Traverse the right sub tree
•    Last value in the right sub tree is the maximum value.
  Step 7: Stop the program.


















PROGRAM:            BINARY SEARCH TREE
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
typedef struct tree *node;
node insert(int, node t);
void find(node t, int);
void findmin(node t);
void findmax(node t);
struct tree
{
int data;
struct tree *right,*left;
}*root;
void main()
{
node t=NULL;
int data,s,i=0,n;
char c;
clrscr();
printf("Enter the no of elements:\n");
scanf("%d",&n);
printf("Elements are:\n");
while(i<n)
{
scanf("%d",&data);
t=insert(data,t);
i++;
}
printf("Enter the element to be search\n");
scanf("%d",&s);
find(t,s);
findmin(t);
findmax(t);
getch();
}
node insert(int x,node t)
{
struct tree *newnode;
newnode=malloc(sizeof(struct tree));
if(newnode==NULL)
printf("out of space\n");
else
{
if(t==NULL)
{
newnode->data=x;
newnode->left=NULL;
newnode->right=NULL;
t=newnode;
}
else
{
if(x<t->data)
t->left=insert(x,t->left);
else
t->right=insert(x,t->right);
}   }
return t;
}
void find(node t,int x)
{
if(t==NULL)
printf("search element is %d is found\n",x);
else if(x<t->data)
find(t->left,x);
else
find(t->right,x);
}
void findmin(node t)
{
if(t!=NULL)
{
if(t->left==NULL)
printf(" The minimum element in the tree is %d\n ",t->data);
else
findmin(t->left);
}    }
void findmax(node t)
{
if(t!=NULL)
{
if(t->right==NULL)
printf("The maximum element in the tree is %d\n",t-> data);
else
findmax(t->right);
}    }
















OUTPUT:

    Enter the number of elements:5
    Elements are :23  45  32  65  12
    Enter the element to be search :32
    Search element 32 is found.
    The minimum element in the tree is 12
    The maximum  element in the tree is 65
























RESULT:
          Thus  the implementation of binary search tree has been done successfully.














EX.NO.7        IMPLEMENTATION OF AVL TREE

AIM:
      To write a C program  for implementing AVL tree.
ALGORITHM:
Step 1: Start the program.
Step 2: Define AVL tree structure and read the choice to perform the operation.
Step 3: Enter the choice 1 to perform the insert operation
i)    if the tree is empty continue the operation to insert
ii)    check the balanced condition
iii)    if the balanced condition is 1  ,0 or -1 insert the element
iv)    otherwise perform the rotation  than insert the element
Step 4:  Enter the choice 2 to display the tree
Step 5:  Perform the in-order operation.
Step 6: Stop the program.






























PROGRAM:            AVL TREE
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include<stdlib.h>
typedef enum{false,true} bool;
struct node
{
int info;
int balance;
struct node *lchild;
struct node *rchild;
};
struct node *insert(int,struct node*,int*);
struct node*search(struct node*,int);
void main()
{
bool htinc;
int info;
int choice;
struct node *root=(struct node*)malloc(sizeof(struct node));
clrscr();
root=null;
printf("1.insert\n");
printf("2.display\n");
printf("3.exit\n");
while(1)
{
printf("enter your choice");
scanf("%d",&choice);
switch(choice)
{
case 1:printf("enter the value to be inserted");
       scanf("%d",&info);
       if(search(root,info)==null)
     root=insert(info,root,&htinc);
       else
      printf("duplicate value ignored");  break;
case 2:if(root==null)
{
    printf("tree is empty");
    continue;
    }
    printf("tree is:\n");
    display(root,1);
    printf("\n\n");
    printf("inorder traversal is");
    inorder(root);
    printf("\n");
    break;
case 3:exit(1);
       default:
       printf("wrong choice\n");
       }/*end of switch*/
       }/*end of while*/
       }/*end of main*/
 struct node* search(struct node *ptr,int info)
 {
 if(ptr!=null)
 if(info<ptr->info)
       ptr=search(ptr->lchild,info);
 else if(info>ptr->info)
       ptr=search(ptr->rchild,info);
       return(ptr);
       }/*end of search*/
struct node *insert(int info,struct node*pptr,int *htinc)
{
    struct node*aptr;
    struct node *bptr;
    if(pptr==null)
    {
    pptr=(struct node*)malloc(sizeof(struct node));
    pptr->info=info;
    pptr->lchild=null;
    pptr->rchild=null;
    pptr->balance=0;
    *htinc=true;
    return(pptr);
    }
  if(info<pptr->info)
  {
  pptr->lchild=insert(info,pptr->lchild,htinc);
  if(*htinc==true)
  {
  switch(pptr->balance)
  {
  case -1: /*right heavy*/
      pptr->balance=0;
      *htinc=false;
      break;
 case 0:/*balanced*/
    pptr->balance=1;
    break;
case 1:/*left heavy*/
       aptr=pptr->lchild;
       if(aptr->balance==1)
       {
       printf("left ot leftrotation");
       pptr->lchild=aptr->rchild;
       aptr->rchild=pptr;
       pptr->balance=0;
       aptr->balance=0;
       pptr=aptr;
       }
       else
       {
       printf("left to right rotation\n");
       bptr=aptr->rchild;
       aptr->rchild=bptr->lchild;
       bptr->lchild=aptr;
       pptr->lchild=bptr->rchild;
       bptr->rchild=pptr;
       if(bptr->balance==1)
        pptr->balance=-1;
       else
        pptr->balance=0;
       if(bptr->balance==-1)
         aptr->balance=1;
       else
       aptr->balance=0;
    bptr->balance=0;
    pptr=bptr;
    }
    *htinc=false;
    }/*end of switch*/
       }/*end of if*/
       }/*end of if*/
    if(info>pptr->info)
    {
    pptr->rchild=insert(info,pptr->rchild,htinc);
    if(*htinc==true)
    {
    switch(pptr->balance)
    {
    case 1:/*left heavy*/
        pptr->balance=0;
        *htinc=false;
        break;
    case 0: /*balanced*/
        pptr->balance=-1;
        break;
    case -1:/*right heavy*/
        aptr=pptr->rchild;
        if(aptr->balance==-1)
        {
        printf("right to right rotation\n");
        pptr->rchild=aptr->lchild;
        aptr->lchild=pptr;
        pptr->balance=0;
        aptr->balance=0;
        pptr=aptr;
        }
        else
        {
        printf("right to left rotation");
        bptr=aptr->lchild;
        aptr->lchild=bptr->rchild;    bptr->rchild=aptr;
        pptr->rchild=bptr->lchild;
        bptr->lchild=pptr;
        if(bptr->balance==-1)
        pptr->balance=1;
        else
        pptr->balance=0;
        if(bptr->balance==1)
        aptr->balance=-1;
        else
        aptr->balance=0;
        bptr->balance=0;
        pptr=bptr;
        }/*end of else*/
        *htinc=false;
           }/*end of switch*/
       }/*end of if*/
       }/*end of if*/
    return(pptr);
    }/*end of insert()*/
    display(struct node *ptr,int level)
    {
    int i;
    if(ptr!=null)
    {
    display(ptr->rchild,level+1);
    printf("/n");
    for(i=0;i<level;i++)
    printf("");
    printf("%d",ptr->info);
    display(ptr->lchild,level+1);
    }/*end of if*/
    }/*end of display*/
    inorder(struct node *ptr)
    {
    if(ptr!=null)
    {
    inorder(ptr->lchild);
    printf("%d",ptr->info);
    inorder(ptr->rchild);
    }    }
  














OUTPUT:


  1. Insert
  2. Display
  3. Exit
Enter the choice :1
Enter the value to be inserted:12
Enter the choice :1
Enter the value to be inserted:23
Enter the choice :2
       Tree is 23 12
In-order traversal is 1223



















RESULT:
Thus the implementation of AVL tree using C program has been done successfully.


















EX.NO.8A
IMPLEMENTATION OF PRIORITY QUEUE - MAXHEAP

AIM:
   To implement the priority queue by using binary max heap technique.
 ALGORITHM:
     Step 1: Start the program
     Step 2: Read the choice of operation such as make heap, insertion, deletion, replace.
     Step 3: Enter the total number of elements to make the heap
     Step 4: Enter the element to be inserted in the max heap
     Step 5:  Enter the element to be deleted in the max heap
     Step 6: Stop the program.

































PROGRAM:            MAX HEAP
#include<conio.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<alloc.h>
 void restoreup(int,int*);
 void restoredown(int,int*,int);
 void makeheap(int*,int);
 void add(int,int*,int*);
 int replace(int,int*,int);
 int del(int*,int*);
 void main()
 {     int a[20];
 int i,n,ch;
 clrscr();
 do     {
 printf("1.makeheap\n");
 printf("2.insertion\n");
 printf("3.deletion\n");
 printf("4.replace\n");
 printf("5.exit\n enter your choice\n");
 scanf("%d",&ch);
 switch(ch)
 {     case 1: printf("\nenter total number of nos\n");
 scanf("%d",&n);
 for(i=1;i<=n;i++)
 scanf("%d",&a[i]);
 makeheap(a,n);
 printf("\nheap\n");
 for(i=1;i<=n;i++)
 printf("%d\t",a[i]);
 break;
 case 2: printf("\nenter number to be inserted\n");
 scanf("%d",&i);
 add(i,a,&n);
 printf("\nelement added %d\t",i);
 printf("\n heap after addition of element:\n");
 for(i=1;i<=n;i++)
 printf("%d\t",a[i]);
 break;
 case 3:  printf("\n here the root node is deleted\n");
 i=del(a,&n);
 printf("\nelement deleted %d\n",i);
 for(i=1;i<=n;i++)
 printf("%d\t",a[i]);
 break;
 case 4: printf("\n \nhere the root node is replaced\n");
 printf("\n \nenter the value to placed in the root node\n");
 scanf("%d",&i);
 i=replace(i,a,n);
 printf("\nelement replaced%d\n",i);
 for(i=1;i<=n;i++)
 printf("%d\n",a[i]);
 break;
 }
 getch();
 }while(ch!=5);
 }
 void restoreup(int i,int *a)
 {     int v;
 v=a[i];
 while(a[i/2]<=v)
 {     a[i]=a[i/2];
 i=i/2;
 }     a[i]=v;     }
 void restoredown(int p,int *a,int n)
 {
 int i,v;
 v=a[p];
 while(p<=n/2)
 {
 i=2*p;
 if((i<n)&&(a[i]<a[i+1]))
 i++;
 if(v>=a[i])
 break;
 a[p]=a[i];
 p=i;
 }     a[p]=v;     }
 void makeheap(int *a,int n)
 {
 int i;
 for(i=n/2;i>=1;i--)
 restoredown(i,a,n);
 }
void add(int v,int *a,int *n)
 {
 (*n)++;
 a[*n]=v;
 restoreup(*n,a);
 }
 int replace(int i,int *a,int n)
 {
 int r=a[1];
 a[1]=i;
 for(i=n/2;i>=1;i--)
 restoredown(i,a,n);
 return r;
 }
 int del( int *a,int *n)
 {
 int v;
 v=a[1];
 a[1]=a[*n];
 (*n)--;
 restoredown(1,a,*n);
 return v;
 }

OUTPUT:
    1 .Make heap
    2. Insertion
   3. Deletion
   4. Replace
   5. Exit
Enter your choice :1
Enter total number of elements to be inserted:3
1 2 3
Heap:
3 2 1
Enter your choice :2
Enter the element to be inserted:47
Element added :47
Heap after insertion of an element:
  47 3 1 2
Enter your choice:3
Here the root node is deleted
Element deleted is 47
3    2  1
Enter your choice :4
Here the root is replaced
Enter the  value to be placed in the root node:23
Element replaced 3
23 2 1
Enter your choice :5




RESULT:

   Thus the implementation of priority queue by using max-heap has been done.
















 EX.NO.8B
IMPLEMENTATION OF PRIORITY QUEUE - MINHEAP

AIM:
       To implement the priority queue by using  binary min heap technique.
 ALGORITHM:
     Step 1: Start the program
     Step 2: Read the choice of operation such as make heap, insertion, deletion, replace.
     Step 3: Enter the total number of elements to make the heap
     Step 4: Enter the element to be inserted in the min heap
     Step 5:  Enter the element to be deleted in the min heap
     Step 6: Stop the program.




































PROGRAM:             MIN HEAP
 #include<conio.h>
 #include<stdio.h>
 #include<stdlib.h>
 #include<alloc.h>
 void restoreup(int,int*);
 void restoredown(int,int*,int);
 void makeheap(int*,int);
 void add(int,int*,int*);
 int replace(int,int*,int);
 int del(int*,int*);
 void main()
 {
     int a[20];
 int i,n,ch;
 clrscr();
     do
 {
 printf("1.makeheap\n");
 printf("2.insertion\n");
 printf("3.deletion\n");
 printf("4.replace\n");
 printf("5.exit\n enter your choice\n");
 scanf("%d",&ch);
 switch(ch)
 {
 case 1: printf("enter total number of nos\n");
 scanf("%d",&n);
 for(i=1;i<=n;i++)
 scanf("%d",&a[i]);
 makeheap(a,n);
 printf("heap: \n");
 for(i=1;i<=n;i++)
 printf("%d\t",a[i]);
 break;
 case 2:  printf("enter number to be inserted\n");
 scanf("%d",&i);
 add(i,a,&n);
 printf("element added%d\n",i);
 printf("heap after addition of element\n");
 for(i=1;i<=n;i++)
 printf("%d\t",a[i]);
 break;
 case 3: printf("here the root node is deleted\n");
 i=del(a,&n);
 printf("\nelement deleted %d\n",i);
 for(i=1;i<=n;i++)
 printf("%d\t",a[i]);
 break;
 case 4: printf("here the root node is replaced\n");
 printf("enter the value to placed in the root node\n");
 scanf("%d",&i);
 i=replace(i,a,n);
  printf("\nelement replaced%d",i);
 for(i=1;i<=n;i++)
 printf("%d\t",a[i]);
 break;
 }
 getch();
 }while(ch!=5);
 }
 void restoreup(int i,int *a)
 {
 int v;
 v=a[i];
 while(a[i/2]>=v)
 {
 a[i]=a[i/2];
 i=i/2;
 }
 a[i]=v;
 }
 void restoredown(int p,int *a,int n)
 {
 int i,v;
 v=a[p];
 while(p<=n/2)
 {
 i=2*p;
 if((i<n)&&(a[i]<a[i+1]));
 else
 i++;
 if(v<=a[i])
 break;
 a[p]=a[i];
 p=i;
 }     a[p]=v;     }
 void makeheap(int *a,int n)
 {     int i;
 for(i=n/2;i>=1;i--)
 restoredown(i,a,n);
 }
void add(int v,int *a,int *n)
 {
 (*n)++;
 a[*n]=v;
 restoreup(*n,a);
 }
 int replace(int i,int *a,int n)
 {     int r=a[1];
 a[1]=i;
 for(i=n/2;i>=1;i--)
 restoredown(i,a,n);
 return r;
 }
 int del( int *a,int *n)
 {     int v;
 v=a[1];
 a[1]=a[*n];
 (*n)--;
 restoredown(1,a,*n);
 return v;     }

OUTPUT:
1. Make heap
      2. Insertion
       3. Deletion
      4. Replace
       5. Exit
Enter your choice :1
Enter total number of elements to be inserted:5
12  13  14  15  16
Heap:
16   15  14 12 13
Enter your choice :2
Enter the element to be inserted:17
Element added :17
Heap after insertion of an element:
  17 15  16  12  13  14
Enter your choice:3
Here the root node is deleted
Element deleted is 17
 16 15 14 12 13
Enter your choice :4
Here the root is replaced
Enter the  value to be placed in the root node:23
Element replaced 3
23  15  14  12  13


RESULT:

       Thus the implementation of priority queue using min heap has been executed.
















EX.NO.9             IMPLEMENTATION OF HASHING

AIM:
           To implement the hash table using C program.
ALGORITHM:
          Step 1: Start the program.
          Step 2:  Enter the choice of operation and declare the variable.
          Step 3:  To perform the insertion operation enter the item into 
                         the hash table.
                                    i)   if the table is empty insert the value
                                    ii) else the item will not to be inserted into the
                                         table.
           Step 4: Enter the item to be retrieved from the table
                                      i) if the item is present in the table print the item
                                      ii) else print “The item is not present in the table”.
           Step 5: Enter the item to be deleted in the hash table
           Step 6: Display the item in the hash table.
           Step 7: Stop the program.

























PROGRAM:    HASHING
#include<stdio.h>
#include<conio.h>
#include<math.h>
int tabsize=10;
int tab[20];
void main()
{
int i,j,ch,res;
int store(int);
void retrieve(int,int *);
void removed(int);
void display();
for(i=0;i<tabsize;i++)
tab[i]=0;
do
{
clrscr();
printf("\hashing with open addressing\n");
printf("\n1.store operation....");
printf("\n2.retrieve operation...");
printf("\n3.remove operation...");
printf("\n4.display..");
printf("\n5.exit..");
printf("\nenter your choice.....");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("enter the item to be placed in a table");
scanf("%d",&i);
res = store(i);
if(res==1)

printf("item stored in the table");
else if(res==2)
printf("there is no free place in the table");
else if(res==0)
printf("item already exists in the table");
getch();
break;
case 2:
printf("enter the item to be retrieved from the table");
scanf("%d",&i);
retrieve(i,&j);
if(j==1)
printf("item is in the teble");
else
printf("Item is not in the table");
getch();
break;
case 3:
printf("Enter the item tobe deleted from the table");
scanf("%d",&i);
removed(i);
break;
case 4:
display();
getch();
break;
case 5:
break;
}    }
while(ch!=5);
}
int store(int item)
{
int loc,ploc,k=1;
int flag=0;
loc = item%tabsize;   
ploc=loc;
if(loc==tabsize)
loc=0;
while(1)
{
if(tab[loc] == 0)
{
tab[loc] = item;
return 1;
}
else if((tab[loc] !=0) &&(tab[loc] != item))
{
/*if collision occurs in the hash table*/
loc = loc+1;
//k++;
if(loc>= tabsize)
loc = 0;
if(ploc == loc)
return 2;
continue;
}
else if (tab[loc] == item)
{
printf("item already exists in the teble");
getch();
return 0;    }
else
{
loc = loc+1;
if(loc == tabsize)
loc = 0;
if(ploc == loc)
return 2;
continue;
}    }    }
void retrieve(int item,int*j)
{
int loc,ploc,k=1;
loc = item%tabsize;
ploc = loc;
if(tab[loc] == item)
{    *j = 1;
return;
}    else
{
loc=loc+pow(k,2);
while(ploc!= loc)
{
if(tab[loc] == item)
{    *j = 1;
return;
}
if(loc == tabsize)
loc = 0;
else
{    loc= loc+1;
}    }
*j = 0;
return;
}    }
void removed(int i)
{
int k=1,loc,ploc;
loc = i % tabsize;
ploc=loc;
if(tab[loc] == i)
{    tab[loc] = 0;
printf("\nItem removed from the hash table...");
getch();
return;
}    else
{    loc=loc+1;
while((loc != ploc)  &&(tab[loc] != i))
{    loc=loc+i;
if(loc==tabsize)
loc=0;
}
if((tab[loc] == i)&&(loc !=ploc))
{
tab[loc] = 0;
printf("\npitem removed from the hash table...");
getch();
return;
}
else if((loc == ploc) &&(tab[loc] != i))
{
printf("item not found the hash table ");
getch();
return;
}    }    }
void display()
{    int i;
for(i=0;i<tabsize;i++)
printf("%d",tab[i]);    }

OUTPUT:
          Hashing with open addressing
                   1. Store operation
                    2. Retrieve operation
                   3. Remove operation
                    4. Display
                    5. Exit
 enter your choice 1
 enter the item to be placed in the table 10
 item stored  in the table
 enter your choice 1
 enter the item to be placed in the table 20
 item stored  in the table
 enter your choice 2
 enter the item to be retrieved  from the table 10
 item is in the table
 enter your choice 3
 enter the item to be deleted from the table 10
 item removed from the hash table
 enter your choice 4
    02000000000


RESULT:
     Thus the hash table implementation has been successfully executed.






















EX.NO.10        IMPLEMENTATION OF TOPOLOGICAL SORT

AIM:
        To implement a topological sort using C program.
 ALGORITHM:
         Step 1: Start the program.
         Step 2: Enter the vertices of the graph.
         Step 3: Enter the adjacency matrix and also calculate the In-degree for every vertex.
         Step 4: Find the minimum in-degree vertex and en-queue that vertex.
         Step 5: Then compare the vertices with adjacency matrix using for loop.
         Step 6:  Display the topological sorting of the given graph.
         Step 7: Stop the program.
  































PROGRAM:            TOPOLOGICAL  SORT
#include<stdio.h>
#include<conio.h>
void main()
{
int k=0, fflag=1,chflag=1,i,j,x,cflag,n,i1,j1,a[50][50],ts[50];
clrscr();
printf("Enter the total no of vertices");
scanf("%d",&n);
printf("Enter the adjacent matrix");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
}    }
printf("The topological sorting of the given graph");
j=0;
while(j<n)
{
chflag=1;
for(i1=0;i1<n;i1++)
{    for(j1=0;j1<n;j1++)    {
if(a[i1][j1]==9)
cflag=1;
else
cflag=0;
fflag=fflag*cflag;
}    chflag*=fflag;        }
if(chflag==1)
exit(0);
cflag=0;
fflag=1;
for(i=0;i<n;i++)
{
if(a[i][j]==0)
cflag=1;
else
cflag=0;
fflag=fflag*cflag;    }
if(fflag==1)
{
for(i=0;i<n;i++)
a[i][j]=9;
ts[k]=j;
printf("v%d-",ts[k]);
k++;
for(i=0;i<n;i++)
{    if(a[j][i]==1)
a[j][i]=0;
}    }
if(j==n-1)
j=0;
else
j++;
}
getch();
}



OUTPUT:
    Enter the number of vertices: 4
      0 1 1 0
      0 0 1 1
      0 0 0 0
      0 0 1 0
The topological sorting of the given graph is v0-V1-V3-V2



















RESULT:

       Thus the implementation of topological sort using C program has been executed.













EX.NO.11         IMPLEMENTATION OF DIJKSTRA’S ALGORITHM
AIM:
      To implement the shortest path algorithm - Dijkstra’s algorithm using C program.
ALGORITHM:
Step 1: Start the program.
Step 2: Enter the total number of vertices
Step 3: Enter the adjacency matrix
Step 4: Enter the source vertex.
Step 5: Calculate the shortest the path between source and destination vertices.
Step 6: Display the path and length of the matrix.
Step 7: Stop the program


































 PROGRAM:        DIJKSTRA’S ALGORITHM
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
int a[25][25],path[25][25],n,s;
/*function used to get the label of the vertex which has minimum distance*/
int search(int *l,int *s1,int n)
{    int i,v,min=999;
for(i=0;i<n;i++)
{    if(*(l+i)!=0)    {
if((*(l+i)<min) && (*(s1+i)==0))
{    min=*(l+i);
v=i;
}    }    }
return(v);    }
void main()
{
int flag,i,j,n,s,set[25],len[25];
char str[25],tmp[25];
char *sp=" ";
clrscr();
printf("enter the total no of vertices");
scanf("%d",&n);
printf("enter the adjacency matrix");
for(i=0;i<n;i++)    {
for(j=0;j<n;j++)    {
scanf("%d",&a[i][j]);        }    }
printf("enter the source vertex:");
scanf("%d",&s);
/*intialize the set array*/
for(i=0;i<n;i++)
set[i] = 0;
for(i=0;i<n;i++)
{    if(a[s][i] == 0 )
{    len[i]= 999;
strcpy(path[i],"-");    }    else    {
len[i] = a[s][i];
itoa(s,str,10);
strcpy(path[i],str);
strcat(path[i],"-");
itoa(i,str,10);
strcat(path[i],str);    }    }
set[s] = 1;
len[s] = 0;
flag = 0;
while(!flag)
{    j=search(&len[0],&set[0],n);
set[j]= 1;
while(i<n)
    {        if(set[i] == 0)
   {       flag =0;
   break;        }
    else
     i++;    }    }
    printf("\nLength matrix\n");
    for(i=0;i<n;i++)
    printf("%d",len[i]);
    printf("\npath matrix\n");
    for(i=0;i<n;i++)
    printf("%s",path[i]);
    getch();
}

OUTPUT:
Enter the total NO of vertices:5
 Enter the adjacency matrix :0 2 0 1 6
 2 0 1 0 4
 0 1  0 2 3
1 0 2 0 7
3 4 3 7 0
Enter the source vertex:0
Length matrix:
0    2  3  1  6
path matrix
-   0-1   0-3 -2   0-3  0-4  j=3
Length matrix:
0     2  3  1  6
path matrix
-   0-1   0-1-2   0-3  0-4  j=1
Length matrix:
0    2  3  1  6
path matrix
-   0-1   0-1 -2   0-3  0-1-2-4  j=2
Length matrix:
0    2  3  1  6
path matrix
-   0-1   0-1-2   0-3  0-1-2-4  j=4
Length matrix:
0    2  3  1  6
path matrix
-0-10-1-20-30-1-2-4

RESULT:

  Thus the calculation of shortest path algorithm using C has been executed.






EX.N0:12    IMPLEMENTATION OF PRIMS ALGORITHM
AIM:
To implement the prim’s algorithm using C program.
ALGORITHM:
Step 1: Start the program.
Step 2: Declare the unvisited node is -1, visited node is 1.
Step 3: Consider any vertex in the graph, process the vertex and add the vertex to the tree.
Step 4: Find the smallest edge from the graph connecting the edge of the vertex, such that
            it does not form a cycle.
Step 5: Add the vertex to the tree, and then making the visited node as 1.
Step 6: repeat the step 4, until the tree contain all the n vertices.
Step 7: Get the shortest path.
Step 8: Stop the program.






















PROGRAM:            PRIM’S ALGORITHM
#include <stdio.h>
#include<conio.h>
#define MAX 30
#define UNVISITED -1
#define VISITED 1
#define INFINITY 32767
typedef struct
{
int previous,len,status;
}node;
typedef struct
{
int s,e;
}tree;
void viewAdjMat();
int visitedAll(node graph[MAX],int n);
int createSpan(tree primSpan[MAX] ,int *minLen);
void viewSpanMat(tree primMat[MAX],int n, int wt);
int adjMat[MAX][MAX] ,n;
void main()
{
char ch,s,d;
int i,j,k,temp,minLen,tot;
tree primSpan[MAX];
FILE *f1;
printf("\n enter the no.of vertices of weighted graph:");
scanf("%d",&n);
if((f1=fopen("C:\\prim.txt","rt"))==NULL)
{
fprintf(stderr,"cannot open input file\n");
return;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
fscanf(f1,"%d",&adjMat[i][j]);
fclose(f1);
printf("\n the adjacency matrix is...\n");
viewAdjMat();
tot=createSpan(primSpan , &minLen);
viewSpanMat(primSpan,tot, minLen);
}
void viewSpanMat(tree primSpan[MAX],int n, int len)
{
int k;
printf("\n spanning tree length is:%d\n\n spannig tree edges are:/n",len);
for(k=1;k<=n;k++)
{
printf("%c--->%c\n",primSpan[k].s+64,primSpan[k].e+64);
printf(" %d\n",adjMat[primSpan[k].s][primSpan[k].e]);
}    }
int visitedAll(node graph[MAX],int n)         {
int k;
for(k=1;k<=n;k++)
if(graph[k].status==UNVISITED)
return 0;      
return 1;
}
void viewAdjMat()
{
int i,j;
printf("\n   ");
for(i=1;i<=n;i++)
printf("%4c",i+64);
printf("\n \n");
for(i=1;i<=n;i++,printf("\n\n"))
for(j=1;j<=n;j++)
{
if(j==1)
printf("%4c",i+64);
printf("%4d",adjMat[i][j]);
}    }
int createSpan(tree primSpan[MAX],int *minLen)
{
node graph[MAX];
int s,e,i,k,min,curVertex,newLen,u,v,tot=0;
*minLen=0;
for(i=1;i<=n;i++)
{
graph[i].previous=0;
graph[i].len=INFINITY;
graph[i].status=UNVISITED;
}
graph[i].previous=0;
graph[i].len=0;
graph[i].status=VISITED;
curVertex=1;
tot=0;
while(visitedAll(graph,n)!=1)
{
for(k=1;k<=n;k++)
{
if(adjMat[curVertex][k]>0 && graph[k].status==UNVISITED)
{
if(adjMat[curVertex][k]<graph[k].len)
{
graph[k].previous=curVertex;
graph[k].len=adjMat[curVertex][k];
}    }    }
min=INFINITY;
for(i=1;i<=n;i++)
if(graph[i].status==UNVISITED &&graph[i].len<min)
{
min=graph[i].len;
curVertex=i;
}
graph[curVertex].status=VISITED;
s=graph[curVertex].previous;
e=curVertex;
tot++;
primSpan[tot].s=s;
primSpan[tot].e=e;
*minLen=*minLen+adjMat[s][e];
}
return (tot);
}


OUTPUT:
The text in the file prim.txt
 0  2  4  1  0  0  0
2  0  0  3  10  0  0
4  0  0  2  0  5  0
1  3  2  0  2  8  4 
0  10  0  2  0  0  6
0  0  5  8  0  0  1
0  0  0  4  6  1  0
Enter the no.of vertices of weighted graph:7
The  adjacency matrix is…
          A  B  C  D  E  F  G
A   0   2   4   1   0   0  0
B   2    0   0   3   10  0  0
C   4    0   0   2    0  5  0
D  1    3  2    0    2  8  4 
E    0   10  0   2    0  0  6
F    0     0   5   8   0  0  1
G    0    0    0    4  6  1  0

Spanning tree length is :12
Spanning tree edges are:
AD
    1
AB
    2
DC
   2
DE
   2
DG
  4
GF
 1
Prim.c
0  2  4  1  0  0  0
2  0  0  3  10  0  0
4  0  0  2  0  5  0
1  3  2  0  2  8  4 
0  10  0  2  0  0  6
0  0  5  8  0  0  1
0  0  0  4  6  1  0



RESULT:
    Thus the implementation of Prim’s algorithm has been successfully done.














EX.NO:13    IMPLEMENTATION OF KNAPSACK PROBLEM
AIM:
To implement the Knapsack problem using C program.
ALGORITHM:
Step 1: Start the program
Step 2: Enter the maximum weight of the bag and number of objects
Step 3: Enter the profit of item
Step 4: Check the profit of item I divided by weight of item I < profit of 
           item j divided  by  weight of item j, then increment the number of object.
Step 5: Then initialize capacity equal to max value.
Step 6: Then find solution vector of the items
Step 7: Then calculate p[i]*x[i] and w[i]*x[i].
Step 8: Get the optimum solution
Step 9: Stop the program.































PROGRAM:        KNAPSACK PROBLEM
  #include<stdio.h>
  #include<conio.h>
  int i,j,n,temp,index[20];
  float p[20],w[20],x[20],max,capacity;
  void read_input();
  void knapsack(float [],float [],float [],float, int);
  void display_output();
 void main()
  {
   clrscr();
   read_input();
   knapsack( p, w, x,max,n);
   display_output();
   getch();
  }
  void read_input()
  {
  printf("enter the maximum weight of the bag:");
  scanf("%f",&max);
  printf("enterr the number of objects;");
  scanf("%d",&n);
  for(i=0;i<n;i++)
  {
  printf("\n enter the weihht of %d item w[%d]:",i+1,i+1);
  scanf("%f",&w[i]);
  printf("enter the profit of %d item p[%d]:",i+1,i+1);
  scanf("%f",&p[i]);
  }      }
void knapsack(float p[],float w[],float x[],float max,int n)
{
for(i=0;i<n;index[temp]=i,i++)
{
for(temp=0,j=0;j<n;j++)
{
if((i!=j)&&(p[i]/w[i])<(p[j]/w[j]))
{
temp++;
}    }    }
capacity=max;
for(i=0;i<n;i++)
{
if(w[index[i]]>capacity)
break;
x[index[i]]=1.0;
capacity=capacity/w[index[i]];
}    }

void display_output()
{
float profit=0.0,max_cap=0.0;
for(i=0;i<n;i++)
{
profit=profit+(x[i]*p[i]);
}
for(i=0;i<n;i++)
{
max_cap=max_cap+(w[i]*x[i]);
}    {
printf("\n the optimal solution is ........\n");
printf("\n %9s %9 %9s %9s %7s ","weight","profit","x");
printf("\n %8s %9s %9s %9s","i","w[i]","p[i]","x[i]");
for(i=0;i<n;i++)
printf("\n %9d %9.2f %9.2f %9.2f",i+1,w[i],p[i],x[i]);
printf("\n \n the sum ofp[i]*x[i]=% .2f",profit);
printf("\n \n the sum if w[i]*x[i]=%.2f",max_cap);
}    }

KNAPSACK OUTPUT:
Enter the maximum weight of bag: 5
Enter the no of objects:4
Enter the weight of 1 item w[1] 2
Enter the profit of 1 item p[1] 3
Enter the weight of 2 item w[2] 2
Enter the profit of 2 item p[2] 3
Enter the weight of 3 item w[3] 2
Enter the profit of 3 item p[3] 3
Enter the weight of 4 item w[4] 3
Enter the profit of 4 item p[4] 2
The optimal solution is
           Weight        profit           x
   I         W[i]             p[i]         x[i]

  1       2.00             3.00           0.00
  2       2.00             3.00           0.00
  3       2.00             3.00           0.00
  4        2.00            3.00           2.50
The sum of p[i]*x[i] =7.500000
The sum of  w[i]*x[i]=5.000000

RESULT:   
Thus the implementation of Knapsack problem has been successfully done.














EX.NO.14    BRANCH AND BOUND ALGORITHM FOR TRAVELLING    

                                            SALESMAN    PROBLEM

AIM:
To write a C program to implement traveling sales man problem.

ALGORITHM:

     Step 1: Start the program
     Step 2: find out all (n -1)! Possible solutions, where n is the number of cities.
     Step 3: Determine the minimum cost by finding out the cost of everyone of these
                  (n -1)! Solutions.
     Step 4: keep the one with the minimum cost.
     Step 5: Stop the program






































PROGRAM:
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
int n;
int a[10][10],list[20],bpath[20];
int i,j,bcost,tbcost;
void get();
void initialize();
void calc(int list[]);
void swap(int x,int y);
void perm(int,int);
void display();
void get()
{
    printf("Enter the number of cities ::");
    scanf("%d",&n);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            if(i!=j)
            {
                if(a[i][j]==-1)
                {
                    printf("Enter the cost travelling from %d to %d is",i+1,j+1);
                    scanf("%d",&a[i][j]);
                    a[j][i]=a[i][j];
                }

            }
            else a[i][j]=0;
        }
        for(i=0;i<n;i++)
            list[i]=i;
}
void initialize()
{
    for(i=0;i<10;i++)
        for(j=0;j<10;j++)
            a[i][j]=-1;
    bcost=0;
}
void calc(int list[])
{
    int t;
    tbcost=0;
    for(j=1;j<n;j++)
    {
        t=a[list[j-1]][list[j]];
        if(t!=0)
            tbcost=tbcost+a[list[j-1]][list[j]];
        else
            tbcost=bcost+1;
    }
}
void swap(int x, int y)
{
    int temp;
    temp=x;
    x=y;
    y=temp;
}
void perm(int k,int m)
{
    int temp,i,j;
    if(k==m)
    {
        calc(list);
        if(bcost==0)
            bcost=tbcost+1;
        if((tbcost<bcost)&&(a[0][list[n-1]])!=0)
        {
            bcost=tbcost;
            for(j=0;j<n;j++)
                bpath[j]=list[j];
        }
    }
    else
    {
        for(i=k;i<=m;i++)
        {
            swap(list[k],list[i]);
            perm(k+1,m);
            swap(list[k],list[i]);
        }
    }
}
void display()
{
    printf("The best path is :: \n");
    for(i=0;i<n;i++)
        printf("%d --> ",bpath[i]+1);
    printf("\nThe cost is %d ",bcost+a[0][bpath[n-1]]);
}
void main()
{
    clrscr();
    initialize();
    get();
    perm(1,n-1);
    display();
    getch();
}


OUTPUT
Enter the number of cities ::3
Enter the cost travelling from 1 to 2 is10
Enter the cost travelling from 1 to 3 is15
Enter the cost travelling from 2 to 3 is20
The best path is ::
1 --> 2 --> 3 -->
The cost is 45









Result:
     
    Thus the branch and bound algorithm for travelling salesman problem has been successfully completed.




























EX.NO.15            RANDOMIZED ALGORITHM.



AIM:
To write a C program to implement randomized algorithm




ALGORITHM:

    Step 1: Start the program.
    Step 2: Generate the random numbers using the mathematical formula.
    Step 3: find the Largest and smallest no.
    Step 4: Stop the program.




































PROGRAM:
#include <stdio.h>
#include <stdlib.h> /* required for randomize() and random() */
#include <conio.h>  /* required for clrscr() */
int gen_rand(void);   /* note these are declarations of functions */
int find_max(int x, int y, int z);
int find_min(int x, int y, int z);
void main(void)
{
   int num1, num2, num3, max, min;
   clrscr();  /* clear the screen */
   num1=gen_rand();
   num2=gen_rand();
   num3=gen_rand();
   max=find_max(num1, num2, num3);
   min=find_min(num1, num2, num3);
   printf("Random numbers are %d, %d, and %d\n", num1, num2, num3);
   printf("Largest is %d.  Smallest is %d.\n", max, min);
}
int gen_rand(void)
/* returns random number in range of 0 to 99 */
{
   int n;
   n=random(100);  /* n is random number in range of 0 - 99 */
   return(n);
}
int find_max( int x, int y, int z)
/* returns largest number */
{
   int max;
   if ((x>=y) && (x>=z))
   {
     max = x;
   }
   else if ((y>=x) && (y>=z))
   {
     max = y;
   }
   else
   {
     max = z;
   }
   return(max);
}
int find_min( int x, int y, int z)
/* returns smallest number */
{
   int min;
   if ((x<=y) && (x<=z))
   {
     min = x;
   }
   else if ((y<=x) && (y<=z))
   {
     min = y;
   }
   else
   {
     min = y;
   }
   return(min);
}




OUTPUT
Random numbers are 1, 0, and 33
Largest is 33.  Smallest is 0.


















Result:
         Thus the Randomized algorithm has been successfully completed.

















Ex.No: 16
                ARRAY IMPLEMENTATION OF STACK
AIM:

     To write a C-program to implement stack using array data structure

      and perform the following stack operations
           1.POP
           2.PUSH
ALGORITHM:

STEP 1:Start
STEP 2:Initialize stack, will=1,i, num
STEP 3:Add element in stack
                      PUSH(S,TOP,X)
                          3.a. [Check overflow condition]
                                 If(TOP>=N) then
                                   Write(“Stack is full”)
                          3.b. [Insert element]
                                   [Increment TOP]
                                  TOP <- TOP+1
                                            S[TOP]<- X
3.c. [Finish the process]                 
STEP 4: Delete element in stack
                       POP(S,TOP)
                           4.a. [Check for underflow condition]
                                 If(TOP <- 0) then
                                 Write(“Stack is empty”)
                        4.b. [Delete element]
                             [Decrement TOP]
                                TOP<- TOP-1
                               Delete S[TOP+1]
                       4.c.[Finish the process]
STEP 5:Stop

















PROGRAM:

#include<stdio.h>
#include<conio.h>
#define size 10
int stack[size],top=0,b;
int res;
void push();
void pop();
void display();
void main()
{
    int c;
    clrscr();
    printf("\n1.Push\n2.Pop\n3.Display");
    do
    {
        printf("\n\nEnter your Choice :: ");
        scanf("%d",&c);
        switch(c)
        {
            case 1:
            push();
            break;
            case 2:
            pop();
            break;
            case 3:
            printf("\n\nContents of stack is \t");
            display();
            break;
            default:
            printf("\nInvalid Choice......");
            exit(0);
        }
    }while(c<4);
    getch();
}
void push()
{
    if(top>=size)
    {
        printf("\nStack Overflow");
        return;
    }
    else
    {
        printf("\nEnter the number to be pushed into the stack :: ");
        scanf("%d",&b);
        top++;
        stack[top]=b;
        printf("\nNumber pushed is %d",stack[top]);
        return;
    }
}
void pop()
{
    if(top==0)
    {
        printf("\nStack Underflow");
        return;
    }
    else
    {
        res=stack[top];
        top--;
        printf("\nDeleted element is %d",res);
        return;
    }
}
void display()
{
    int i;
    if(top==0)
    {
        printf("\nStack Underflow");
        return;
    }
    for(i=top;i>0;i--)
        printf("%d , ",stack[i]);
}

























OUTPUT:

1.Push
2.Pop
3.Display

Enter your Choice :: 1

Enter the number to be pushed into the stack :: 3

Number pushed is 3

Enter your Choice :: 1

Enter the number to be pushed into the stack :: 5

Number pushed is 5

Enter your Choice :: 3

Contents of stack is    5 , 3 ,

Enter your Choice :: 2

Deleted element is 5

Enter your Choice :: 3

Contents of stack is    3 ,

Enter your Choice :: 8

Invalid Choice......

















Result:

        Thus the array implementation of stack has been successfully completed.
Ex No :17                                 BUBBLE SORT USING C

AIM:
       To write a C Program to perform the Bubble Sort.

ALGORITHM:
Step 1:  Start the program.
Step 2:   Take an array unsorted  A[0],A[1],A[2]................ A[n-1] and A[n] as input.      
               then the following steps are followed by bubble sort algorithm to sort the values          
               of an array.
Step 3:  Compare A[0] and A[1] .
Step 4:  If A[0]>A[1] then Swap A[0] and A[1].
Step 5:  Take next A[1] and A[2].
Step 6:  Comapre these values.
Step 7:  If A[1]>A[2]  then swap A[1] and A[2]

             at last compare A[n-1] and A[n].
Step 8: If A[n-1]>A[n] then swap A[n-1] and A[n]. The highest value is reached at nth 
            position. At next iteration leave nth value.
Step 9:  Then apply the same steps repeatedly on A[0],A[1],A[2]................ A[n-1] 
             elements repeatedly until the values of array is sorted.









PROGRAM:
#include<stdio.h>
#include<conio.h>

void bubble(int a[],int n)
{
int i,j,t;
for(i=n-2;i>=0;i--)
{
for(j=0;j<=i;j++)

{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}//end for 1.

}//end function.

void main()
{

int a[100],n,i;

clrscr();

printf("\n\n Enter integer value for total no.s of elements to be sorted: ");
scanf("%d",&n);

for( i=0;i<=n-1;i++)
{ printf("\n\n Enter integer value for element no.%d : ",i+1);
scanf("%d",&a[i]);
}

bubble(a,n);

printf("\n\n Finally sorted array is: ");
for( i=0;i<=n-1;i++)
printf("%3d\n",a[i]);

} //end program.






OUTPUT:
   

    Enter integer value for total no.s of elements to be sorted
     5
  
   Enter integer value for element no 1 : 5
   Enter integer value for element no 2 : 3
   Enter integer value for element no 1 : 8
   Enter integer value for element no 1 : 9
   Enter integer value for element no 1 : 1


               Finally sorted array is    1
                3
                5
                8
                9
















RESULT:

       Thus the Bubble Sort program using C has been completed.