Showing posts with label 15cs33. Show all posts
Showing posts with label 15cs33. Show all posts

Wednesday, 5 April 2017

Data Structures and Applications(15CS33): Module 4

Posted by at No comments:
Labels: , , , , , , ,

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



Posted by at No comments:
Labels: , ,

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


Posted by at No comments:
Labels: , , ,

Friday, 30 September 2016

Binary Search Tree: Deleting node

Binary Search Tree: Deleting node


#include<stdio.h>
#include<stdlib.h>
struct BST
{
            int data;
            struct BST *lchild,  *rchild;
};
typedef struct BST * NODE;

NODE get_node()
{
            NODE temp;
            temp = (NODE) malloc(sizeof(struct BST));
            temp->lchild = NULL;
            temp->rchild = NULL;
            return temp;
}

void insert(NODE root, NODE newnode)
{
            if (newnode->data < root->data)
            {
                        if (root->lchild == NULL)
                                    root->lchild = newnode;
                        else
                                    insert(root->lchild, newnode);
            }
            if (newnode->data > root->data)
            {
                        if (root->rchild == NULL)
                                    root->rchild = newnode;
                        else
                                    insert(root->rchild, newnode);
            }
}
void inorder(NODE root)
{
            if(root != NULL)
            {
                        inorder(root->lchild);
                        printf("%d ", root->data);
                        inorder(root->rchild);
            }
}

NODE delete_item(NODE root, int item)
{
            NODE cur, parent, succ, psucc, child;
            if(root == NULL)
            {
                        printf("\nTree is empty. Nothing to delete");
                        return NULL;
            }
           
                /*Obtain the node to be deleted and its parent*/
            parent = NULL;
            cur = root;
            while(cur!=NULL)
            {
                        if(item == cur->data)
                                                break;
                        parent = cur;
                        if(item < cur->data)
                                                cur = cur->lchild;
                        else if(item > cur->data)
                                                cur = cur->rchild;
            }
            if(cur == NULL)
            {
                        printf("\nItem not found");
                        return root;
            }
            /*If item is found then delete it: node to be deleted is cur*/
            if(cur->lchild ==NULL)             /*if cur node's left subtree is empty , obtain non empty right subtree */
                        child = cur->rchild;
            else  if(cur->rchild ==NULL)     /*if cur node's left subtree is empty , obtain non empty right subtree */
                        child = cur->lchild;
            else
            {
                        /*Find the inorder successor and its parent*/
                        psucc = cur;
                        succ = cur->rchild;

                                /*Find the minimum node (inorder successor) in the right subtree of cur node*/
                        while(succ->lchild != NULL)                 
                        {
                                                psucc = succ;
                                                succ = succ->lchild;
                        }
                        if(cur == psucc)
                                    succ->lchild  = cur->lchild;
                        else
                        {
                                    succ->lchild = cur->lchild;       /* attach left of node to be deleted(cur) to the left of successor */
                                    psucc->lchild = succ->rchild;     /* attach right of successor to the left of parent of successor*/
                                    succ->rchild = cur->rchild;    /*attach right of node to be deleted(cur) to the right of successor*/
                        }
                        child = succ;
                        printf("\nsuccessor data = %d", child->data);
            }          
            if(parent == NULL)              /*if parent does not exist return child as root*/
                        return child;

            if(parent->lchild  == cur)
                         parent->lchild = child;
             else
                        parent->rchild = child;
            free(cur);
            return root;
}

void main()
{
            int val, i,n, item;
            NODE root = NULL, newnode, del;
            printf("\nEnter the number of elements: ");
            scanf("%d",&n);
            for(i=1;i<=n;i++)
            {
                        newnode = get_node();
                        printf("\nEnter The node value: ");
                        scanf("%d", &val);
                        newnode->data = val;
                        if (root == NULL)
                                    root = newnode;
                        else
                                    insert(root, newnode);
            }

             printf("\nInorder display before deletion: ");
            inorder(root);
            printf("\nEnter the Item to be deleted: ");
            scanf("%d", &item);
            del = delete_item(root, item);
            printf("\nInorder display after deletion: ");
            inorder(del);
}
Output1:
Enter the number of elements: 8
Enter The node value: 45
Enter The node value: 39
Enter The node value: 56
Enter The node value: 54
Enter The node value: 55
Enter The node value: 78
Enter The node value: 61
Enter The node value: 80
Inorder display before deletion: 39    45        54        55        56        61        78        80
Enter the Item to be deleted: 78
Inorder display after deletion: 39       45        54        55        56        61        80

Output2:
Enter the number of elements: 8
Enter The node value: 45
Enter The node value: 39
Enter The node value: 56
Enter The node value: 54
Enter The node value: 55
Enter The node value: 78
Enter The node value: 61
Enter The node value: 80
Inorder display before deletion: 39    45        54        55        56        61        78        80
Enter the Item to be deleted: 54
Inorder display after deletion: 39       45        55        56        61        78        80

Output3:
Enter the number of elements: 8
Enter The node value: 45
Enter The node value: 39
Enter The node value: 56
Enter The node value: 54
Enter The node value: 55
Enter The node value: 78
Enter The node value: 61
Enter The node value: 80
Inorder display before deletion: 39    45        54        55        56        61        78        80
Enter the Item to be deleted: 45
Inorder display after deletion: 39       54        55        56        61        78        80


Output4:
Enter the number of elements: 9
Enter The node value: 45
Enter The node value: 39
Enter The node value: 56
Enter The node value: 54
Enter The node value: 55
Enter The node value: 78
Enter The node value: 61
Enter The node value: 65
Enter The node value: 80

Inorder display before deletion: 39    45        54        55        56        61        65        78        80
Enter the Item to be deleted: 56
successor data = 61

Inorder display after deletion: 39       45        54        55        61        65        78        80
Posted by at No comments:
Labels: , , ,

Binary Search Tree: Count number of Leaf nodes

Count number of leaf nodes in Binary Search Tree



#include<stdio.h>
#include<stdlib.h>
struct BST
{
            int data;
            struct BST *lchild;
            struct BST *rchild;
};
typedef struct BST * NODE;
int leaf=0;

NODE get_node()
{
            NODE temp;
            temp = (NODE) malloc(sizeof(struct BST));
            temp->lchild = NULL;
            temp->rchild = NULL;
            return temp;
}

void insert(NODE root, NODE newnode)
{
            if (newnode->data < root->data)
            {
                        if (root->lchild == NULL)
                                    root->lchild = newnode;
                        else
                                    insert(root->lchild, newnode);
            }
            if (newnode->data > root->data)
            {
                        if (root->rchild == NULL)
                                    root->rchild = newnode;
                        else
                                    insert(root->rchild, newnode);
            }
}

int leaf_nodes(NODE root)
{
            if(root == NULL)
                        return 0;
            if(root->lchild == NULL && root->rchild==NULL)
                        leaf++;
            leaf_nodes(root->lchild);
            leaf_nodes(root->rchild);
            return leaf;
}

void main()
{
            int val, i,n, ln;
            NODE root = NULL, newnode;
            printf("\nEnter the number of elements: ");
            scanf("%d",&n);
            for(i=1;i<=n;i++)
            {
                        newnode = get_node();
                        printf("\nEnter The node value: ");
                        scanf("%d", &val);
                        newnode->data = val;
                        if (root == NULL)
                                    root = newnode;
                        else
                                    insert(root, newnode);
            }

            ln = leaf_nodes(root);
            printf("\nTotal number of leaf nodes is: %d", ln);
}

Output:
Enter the number of elements: 12
Enter The node value: 6
Enter The node value: 9
Enter The node value: 5
Enter The node value: 2
Enter The node value: 8
Enter The node value: 15
Enter The node value: 24
Enter The node value: 14
Enter The node value: 7
Enter The node value: 8
Enter The node value: 5
Enter The node value: 2
Total number of leaf nodes is: 4
Posted by at No comments:
Labels: , ,
Subscribe to: Posts (Atom)