Showing posts with label Module 5. Show all posts
Showing posts with label Module 5. Show all posts

Thursday 17 November 2016

Evaluation of Binary Expression Tree

Evaluation of Expression Tree


#include<stdio.h>
#include<malloc.h>
#include<math.h>
#include<ctype.h>

struct node
{
            char data;
            struct node *lchild;
            struct node *rchild;
};

typedef struct node * NODE;

NODE getnode()
{
    NODE x;
    x = (NODE)malloc(sizeof(struct node));
    x->lchild =NULL;
    x->rchild = NULL;
    return x;
}

NODE create_tree(char postfix[])
{
            NODE temp, s[70];
            char symb;
            int i, top = -1;
            for(i=0; postfix[i] != '\0' ; i++)
            {
                        symb = postfix[i] ;
                        temp = getnode();
                        temp->data = symb;
                        if(isalnum(symb))
                        {
                                                s[++top] = temp;    //push operand to the stack
                        }
                        else
                        {
                                                temp->rchild = s[top--];    //pop second operand from stack and make it rchild
                                                temp->lchild = s[top--];    // pop first operand from stack and make it lchild
                                                s[++top] = temp;            //push operator node to stack
                        }
            }
            return s[top--];        //return the root of expression tree
}

float evaluate(NODE root)
{
            float num;
            switch(root->data)
            {
                        case '+': return evaluate(root->lchild)+evaluate(root->rchild);
                        case '-': return evaluate(root->lchild)-evaluate(root->rchild);
                        case '*': return evaluate(root->lchild)*evaluate(root->rchild);
                        case '/': return evaluate(root->lchild)/evaluate(root->rchild);
                        case '^':
                        case '$': return  pow(evaluate(root->lchild),evaluate(root->rchild));
                        default: if(isalpha(root->data))
                                    {
                                                printf("\n%c = ", root->data);
                                                scanf("%f", &num);
                                                return num;
                                    }
                                    else
                                                return root->data  - '0';
            }
}

void main()
{
            char postfix[60];
            float res;
            NODE root = NULL;
            printf("\nEnter the postfix expression: ");
            scanf("%s", postfix);

            root = create_tree(postfix);
            res = evaluate(root);
            printf("\nResult of expression is = %f", res);
}

Output:
Case 1:
Enter the postfix expression: 632-5*+1^7+
Result of expression is = 18.000000

Case 2:
Enter the postfix expression: abc-d*+e^f+
e = 1
a = 6
b = 3
c = 2
d = 5
f = 7
Result of expression is = 18.000000

Breadth First Search (BFS)

Breadth First Search (BFS)

#include<stdio.h>
#include<stdlib.h>
void bfs(int v);
int a[50][50], n, visited[50];
int q[20], front = -1,rear = -1;

void creategraph()
{
            int i, j;
            printf("\nEnter the number of vertices in graph:  ");
            scanf("%d",&n);
            printf("\nEnter the adjacency matrix:\n");
            for(i=1; i<=n; i++)
                        for(j=1;j<=n;j++)
                                                scanf("%d", &a[i][j]);
}

void bfs(int v)
{
            int i, cur;
            visited[v] = 1;
            q[++rear] = v;
            printf("\nNodes reachable from starting vertex %d are: ", v);
            while(front!=rear)
            {
                        cur = q[++front];
                        for(i=1;i<=n;i++)
                        {
                                    if((a[cur][i]==1)&&(visited[i]==0))
                                    {
                                        q[++rear]=i;
                                                visited[i]=1;
                                                printf("%d ", i);
                                    }
                        }
            }

}

int main()
{
            int ch, start, i, j;
            creategraph();

            for(i=1;i<=n;i++)
                        visited[i]=0;
            printf("\nEnter the starting vertex: ");
            scanf("%d", &start);
             bfs(start);
             for(i=1;i<=n;i++)
             {
                                    if(visited[i]==0)
                                                printf("\nThe vertex that is not reachable is %d" ,i);
             }
}


Output:
Enter the number of vertices in graph:  4
Enter the adjacency matrix:
0          1          0          1
0          0          1          0
0          0          0          1
0          0          0          0
Enter the starting vertex: 1
Nodes reachable from starting vertex 1 are: 2 4 3


Enter the number of vertices in graph:  4
Enter the adjacency matrix:
0          1          0          1
0          0          1          0
0          0          0          1
0          0          0          0
Enter the starting vertex: 2
Nodes reachable from starting vertex 2 are: 3 4
The vertex that is not reachable is 1

Depth First Search (DFS)

Depth First Search


#include<stdio.h>
#include<stdlib.h>
void dfs(int v);
int a[50][50], n, visited[50];
int s[20], top = -1, count=0;

void creategraph()
{
            int i, j;
            printf("\nEnter the number of vertices in graph:  ");
            scanf("%d",&n);
            printf("\nEnter the adjacency matrix:\n");
            for(i=1; i<=n; i++)
                        for(j=1;j<=n;j++)
                                                scanf("%d", &a[i][j]);
}

void dfs(int v)
{
            int i;
            visited[v]=1;
            s[++top] = v;
            for(i=1;i<=n;i++)
            {
                        if(a[v][i] == 1&& visited[i] == 0 )
                        {
                                    dfs(i);
                                    count++;
                        }
            }
}

int main()
{
            int ch, start, i, j;
            creategraph();
            for(i=1;i<=n;i++)
                        visited[i]=0;
            printf("\n Enter the starting vertex:\t");
            scanf("%d", &start);
            dfs(start);
            printf("\nNodes reachable from starting vertex %d are:\n", start);
            for(i=1;i<=count;i++)
                        printf("%d\t", s[i]);

}


Output:
Enter the number of vertices in graph:  4
Enter the adjacency matrix:
0          1          0          1
0          0          1          0
0          0          0          1
0          0          0          0

Enter the starting vertex:     1
Nodes reachable from starting vertex 1 are:
2       3       4


Enter the number of vertices in graph:  4
Enter the adjacency matrix:
0          1          0          1
0          0          1          0
0          0          0          1
0          0          0          0
Enter the starting vertex:     2
Nodes reachable from starting vertex 2 are:

3       4

Thursday 10 November 2016

Radix Sort

C program to sort an array elements using Radix Sort





#include<stdio.h>
#include<stdlib.h>

struct node
{
    int info ;
    struct node *link;
};
typedef struct node * NODE;
NODE bucket[10];
int n, a[20];


int largest()
{
    int i, large = a[0];
    for(i=0;i<n;i++)                        /*First find the largest number in the array*/
    {
        if(a[i] > large)
            large = a[i];
    }
    return large;
}

void insert_rear(int item, int rem)
{
      NODE cur, tmp;
      tmp = (NODE)malloc(sizeof(struct node));
      tmp->info = item;
      tmp->link = NULL;

      if(bucket[rem] == NULL)
      {
            bucket[rem] = tmp;
            return;
      }
      else
      {
           cur = bucket[rem];
           while(cur->link != NULL)
          {
                 cur = cur->link;
           }
           cur->link = tmp;
      }
}

void radix_sort()
{
        NODE p;
        int i, m,k, large, pass = 0, rem, divisor=1, j;
        large = largest();      /*largest number in the array*/
        printf("\nLargest Element is %d", large);

        while(large != 0)           /*Finds number of digits in the largest number*/
        {
            pass++;
            large = large/10 ;
        }
        printf("\nNumber of passes are %d", pass);

        for(m=1; m<=pass; m++)
        {
               printf("\n\n::::Pass %d::::", m);
               for(i=0;i<=9;i++)           /*initialize the buckets: Total 9 buckets*/
                      bucket[i] = NULL;
               for(i=0;i<n;i++)
               {
                     rem = (a[i] / divisor) %10;
                     insert_rear(a[i], rem);
               }
               for(i=0; i<=9 ; i++)
              {
                    printf("\nbucket(%d) -> ",i);
                    p = bucket[i];
                    while(p!=NULL)
                   {
                           printf("%d ",p->info);
                           p = p->link;
                    }
              }

            /*Taking the elements of linked lists in array*/
             i = 0;
             for(k=0;k<=9;k++)
             {
                  p = bucket[k];
                  while(p!=NULL)
                 {
                      a[i++] = p->info;
                      p = p->link;
                 }
            }
            divisor = divisor*10;
        }
}

void main()
{
    int i;
    printf("\nEnter the number of elements in the list : ");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        printf("\nEnter element %d : ",i+1);
        scanf("%d",&a[i]);
    }

    printf("\nUnsorted list is :\n");
    for(i=0;i<n;i++)
        printf("%d ",a[i]);

    radix_sort();
    printf("\nSorted list is :\n");
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
}

Output:

Enter the number of elements in the list : 10
Enter element 1 : 179
Enter element 2 : 208
Enter element 3 : 306
Enter element 4 : 93
Enter element 5 : 859
Enter element 6 : 984
Enter element 7 : 55
Enter element 8 : 9
Enter element 9 : 271
Enter element 10 : 33
Unsorted list is :
179   208   306   93   859   984   55   9   271   33
Largest Element is 984
Number of passes are 3

::::Pass 1::::
bucket(0) ->
bucket(1) -> 271
bucket(2) ->
bucket(3) -> 93 33
bucket(4) -> 984
bucket(5) -> 55
bucket(6) -> 306
bucket(7) ->
bucket(8) -> 208
bucket(9) -> 179 859 9

::::Pass 2::::
bucket(0) -> 306 208 9
bucket(1) ->
bucket(2) ->
bucket(3) -> 33
bucket(4) ->
bucket(5) -> 55 859
bucket(6) ->
bucket(7) -> 271 179
bucket(8) -> 984
bucket(9) -> 93

::::Pass 3::::
bucket(0) -> 9 33 55 93
bucket(1) -> 179
bucket(2) -> 208 271
bucket(3) -> 306
bucket(4) ->
bucket(5) ->
bucket(6) ->
bucket(7) ->
bucket(8) -> 859
bucket(9) -> 984
Sorted list is :
9   33   55   93   179   208   271   306   859   984



Address Calculation Sort

C Program to sort array elements using Address Calculation Sort



#include<stdio.h>
#include<stdlib.h>

struct node
{
       int info;
       struct node *link;
};
typedef struct node * NODE;
NODE head[10];
int n,i,a[20];

int hash_fn(int number,  int k)
{
             /*Find kth digit of the number :example: if its 356 then kth digit will be 3 or if its 29 then kth digit will be 2*/
        int digit, i;
        for(i = 1 ; i <=k ; i++)
        {
              digit = number % 10 ;
              number = number /10 ;
        }
        return digit;       //address
}


/* Finds number of digits in the largest element of the list */
int large_dig()
{
       int large = a[0],ndig = 0 ;
       for(i=0;i<n;i++)                        /*First find the largest number in the array*/
      {
              if(a[i] > large)
                      large = a[i];
       }
       printf("\nLargest Element is %d",large);

      while(large != 0)           /*Finds number of digits in the largest number*/
      {
               ndig++;
               large = large/10 ;
      }
      printf("\nNumber of digits in it are %d", ndig);
      return(ndig);
}


/*Inserts the number in linked list in sorted manner*/
void insert(int num, int addr)
{
      NODE cur ,tmp;
      tmp = (NODE)malloc(sizeof(struct node));
      tmp->info = num;

      /*list empty or item to be added in beginning */
       if(head[addr] == NULL || num < head[addr]->info)
      {
            tmp->link = head[addr];
            head[addr] = tmp;
            return;
      }
     else
     {
            cur = head[addr];
            while(cur->link != NULL && cur->link->info < num)
                      cur = cur->link;
            tmp->link = cur->link;
            cur->link = tmp;
     }
}

void addr_sort()
{
       int i, k, dig, addr;
       NODE p;
       k = large_dig();        /*number of digits in the largest number*/
       for(i=0;i<=9;i++)
               head[i]=NULL;
       for(i=0;i<n;i++)
      {
               addr = hash_fn(a[i], k);
               insert(a[i], addr);
       }

      for(i=0; i<=9 ; i++)
      {
              printf("\nhead(%d) -> ", i);
              p = head[i];
              while(p!=NULL)
             {
                    printf("%d ", p->info);
                    p = p->link;
              }
      }
     /*Taking the elements of linked lists in array*/
      i = 0;
      for(k=0;k<=9;k++)
      {
               p = head[k];
               while(p!=NULL)
              {
                       a[i++] = p->info;
                       p = p->link;
               }
      }
}

void main()
{
      int i;
      printf("\nEnter the number of elements in the list : ");
      scanf("%d", &n);
      for(i=0;i<n;i++)
      {
             printf("\nEnter element %d : ",i+1);
             scanf("%d",&a[i]);
      }

      printf("\nUnsorted list is :\n");
      for(i=0;i<n;i++)
            printf("%d ",a[i]);

      addr_sort();
      printf("\nSorted list is :\n");
      for(i=0;i<n;i++)
              printf("%d ",a[i]);
}


Output:

Enter the number of elements in the list : 15
Enter element 1 : 12
Enter element 2 : 345
Enter element 3 : 567
Enter element 4 : 367
Enter element 5 : 789
Enter element 6 : 23
Enter element 7 : 15
Enter element 8 : 56
Enter element 9 : 567
Enter element 10 : 899
Enter element 11 : 123
Enter element 12 : 321
Enter element 13 : 678
Enter element 14 : 67
Enter element 15 : 45
Unsorted list is :
12   345   567  367   789   23   15   56   567   899   123   321   678   67   45
Largest Element is 899
Number of digits in it are 3

head(0) -> 12  15  23  45  56  67
head(1) -> 123
head(2) ->
head(3) -> 321  345  367
head(4) ->
head(5) -> 567  567
head(6) -> 678
head(7) -> 789
head(8) -> 899
head(9) ->
Sorted list is :
12   15   23   45   56   67   123   321   345   367   567   567   678   789  899


Monday 7 November 2016

Insertion Sort

C Program to sort the elements using Insertion Sort

#include<stdio.h>
int n, a[20];

void insertion_sort()
{
       int i, j, temp;
       for(i=1; i<n ;i++)
      {
              temp = a[i];
              j = i-1;
              while(j>=0 &&  temp < a[j])
             {
                    a[j+1] = a[j];
                    j = j-1;
             }
             a[j+1] = temp;
       }
}

void main()
{
       int i;
       printf("\nEnter the number of elements: ");
       scanf("%d",&n);

      printf("\nEnter the array elements:");
      for(i=0;i<n;i++)
           scanf("%d", &a[i]);

      insertion_sort();

     printf("\nThe array elements after insertion sort: ");
     for(i=0;i<n;i++)
            printf("%d ", a[i]);
}

Output:
Enter the number of elements: 7
Enter the array elements:  89     45      68       90       29       34       17
The array elements after insertion sort: 17       29       34         45        68        89       90