Showing posts with label CBCS. Show all posts
Showing posts with label CBCS. Show all posts

Monday 31 October 2016

Lab Program 11 DFS BFS 15CSL38 Data Structures in C Lab

Lab Program 11

Design, Develop and Implement a Program in C for the
following operations on Graph(G) of Cities
a. Create a Graph of N cities using Adjacency Matrix.
b. Print all the nodes reachable from a given starting node in a digraph using DFS/BFS method

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

int a[50][50], n, visited[50];

int q[20], front = -1,rear = -1;
int s[20], top = -1, count=0;

void bfs(int v)

{
int i, cur;
visited[v] = 1;
q[++rear] = 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);
}
}
}
}

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 )
{
                           printf("%d ", i);
                          dfs(i);
}
}
}

int main()

{

         int ch, start, 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]);
          }

    for(i=1;i<=n;i++)

           visited[i]=0;
    printf("\nEnter the starting vertex: ");
    scanf("%d",&start);

        printf("\n==>1. BFS: Print all nodes reachable from a given starting node");

        printf("\n==>2. DFS: Print all nodes reachable from a given starting node");
        printf("\n==>3:Exit");
        printf("\nEnter your choice: ");
        scanf("%d", &ch);
        switch(ch)
        {
            case 1: printf("\nNodes reachable from starting vertex %d are: ", start);
                    bfs(start);
                    for(i=1;i<=n;i++)
                    {
                        if(visited[i]==0)
                            printf("\nThe vertex that is not reachable is %d" ,i);
                    }
                    break;


            case 2: printf("\nNodes reachable from starting vertex %d are:\n",start);

                    dfs(start);
                    break;
           case 3: exit(0);
           default: printf("\nPlease enter valid choice:");
        }
}

Output:




Case 1:
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


~~~Menu~~~~
==>1. BFS: Print all nodes reachable from a given starting node
==>2. DFS: Print all nodes reachable from a given starting node
==>3:Exit
Enter your choice: 1
Enter the starting vertex: 1
Nodes reachable from starting vertex 1 are: 2       4          3

Case 2:
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
~~~Menu~~~~
==>1. BFS: Print all nodes reachable from a given starting node
==>2. DFS: Print all nodes reachable from a given starting node
==>3:Exit
Enter your choice: 1
Enter the starting vertex: 2
Nodes reachable from starting vertex 2 are:  3      4
The vertex that is not reachable is 1

Case 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
~~~Menu~~~~
==>1. BFS: Print all nodes reachable from a given starting node
==>2. DFS: Print all nodes reachable from a given starting node
==>3:Exit
Enter your choice: 2
Enter the starting vertex:     1
Nodes reachable from starting vertex 1 are:  2       3       4

Case 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
~~~Menu~~~~
==>1. BFS: Print all nodes reachable from a given starting node
==>2. DFS: Print all nodes reachable from a given starting node
==>3:Exit
Enter your choice: 2
Enter the starting vertex:     2
Nodes reachable from starting vertex 2 are:   3       4

Thursday 15 September 2016

Lab Program 12 Hashing 15CSL38 Data Structures in C Lab

Lab program 12

Given a File of N employee records with a set K of Keys(4-digit) which uniquely determine the records in file F.
Assume that file F is maintained in memory by a
Hash Table(HT) of m memory locations with L as the set of memory addresses (2-digit) of locations in HT.
Let the keys in K and addresses in L are integers.
Design and develop a Program in C that uses Hash function
H: K -> L as H(K)=K mod m (remainder method), and implement hashing technique to map a given key K to the address space L.
Resolve the collision (if any) using
linear probing.



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

int key[20],n,m;
int *ht,index;
int count = 0;

void insert(int key)
{
            index = key % m;
            while(ht[index] != -1)
            {
                         index = (index+1)%m;
            }
            ht[index] = key;
            count++;
 }

void display()
{
           int i;
           if(count == 0)
          {
                         printf("\nHash Table is empty");
                         return;
           }

           printf("\nHash Table contents are:\n ");
           for(i=0; i<m; i++)
                      printf("\n T[%d] --> %d ", i, ht[i]);
}


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

         printf("\nEnter the two digit memory locations (m) for hash table:   ");
         scanf("%d", &m);

         ht = (int *)malloc(m*sizeof(int));
         for(i=0; i<m; i++)
                     ht[i] = -1;

         printf("\nEnter the four digit key values (K) for N Employee Records:\n  ");
         for(i=0; i<n; i++)
                    scanf("%d", &key[i]);

         for(i=0;i<n;i++)
        {
                   if(count == m)
                   {
                        printf("\n~~~Hash table is full. Cannot insert the record %d key~~~",i+1);
                        break;
                   }
                   insert(key[i]);
    }

            //Displaying Keys inserted into hash table
             display();
}


Output:
Enter the number of employee  records (N) :   12

Enter the two digit memory locations (m) for hash table:   15

Enter the four digit key values (K) of 'N' Employee Records:
1234
5678
3456
2345
6799
1235
7890
3214
3456
1235
5679
2346

Hash Table contents are:

 T[0] --> 7890
 T[1] --> -1
 T[2] --> -1
 T[3] --> -1
 T[4] --> 1234
 T[5] --> 2345
 T[6] --> 3456
 T[7] --> 6799
 T[8] --> 5678
 T[9] --> 1235
 T[10] --> 3214
 T[11] --> 3456
 T[12] --> 1235
 T[13] --> 5679
 T[14] --> 2346

Monday 5 September 2016

Lab Program 8 Doubly Linked List 15CSL38 Data Structures in C Lab

Lab program 8:

Design, Develop and Implement a menu driven Program in C for the following operations on Doubly Linked List (DLL) of Employee Data with the fields: SSN, Name, Dept, Designation, Sal, PhNo

a. Create a DLL of N Employees Data by using end insertion.
b. Display the status of DLL and count the number of nodes in it
c. Perform Insertion and Deletion at End of DLL
d. Perform Insertion and Deletion at Front of DLL
e. Demonstrate how this DLL can be used as Double Ended Queue
f. Exit

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

struct node
{
         char ssn[25],name[25],dept[10],designation[25];
         int sal;
         long int phone;
         struct node *llink;
         struct node *rlink;
};
typedef struct node* NODE;

NODE first = NULL;
int count=0;


NODE create()
{
          NODE enode;
          enode = (NODE)malloc(sizeof(struct node));
          if( enode== NULL)
          {
                    printf("\nRunning out of memory");
                    exit(0);
           }
           printf("\nEnter the ssn,Name,Department,Designation,Salary,PhoneNo of the employee: \n");
         scanf("%s %s %s %s %d %ld", enode->ssn, enode->name, enode->dept, enode->designation, &enode->sal, &enode->phone);
           enode->llink=NULL;
           enode->rlink=NULL;
           count++;
           return enode;
}

NODE insertfront()
{
         NODE temp;
         temp = create();
          if(first == NULL)
         {
                 return temp;
          }
          temp->rlink = first;
          first->llink = temp;
          return temp;
}

void display()
{
          NODE cur;
          int nodeno=1;
          cur = first;
          if(cur == NULL)
                      printf("\nNo Contents to display in DLL");
          while(cur!=NULL)
         {
        printf("\nENode:%d||SSN:%s|Name:%s|Department:%s|Designation:%s|Salary:%d|Phone no:%ld", nodeno, cur->ssn, cur->name,cur->dept, cur->designation, cur->sal, cur->phone);
                   cur = cur->rlink;
                    nodeno++;
         }
          printf("\nNo of employee nodes is %d",count);
}

NODE deletefront()
{
         NODE temp;
         if(first == NULL)
         {
                   printf("\nDoubly Linked List is empty");
                   return NULL;
         }
         if(first->rlink== NULL)
        {
                  printf("\nThe employee node with the ssn:%s is deleted", first->ssn);
                 free(first);
                 count--;
                  return NULL;
         }
         temp = first;
         first = first->rlink;
         temp->rlink = NULL;
         first->llink = NULL;
         printf("\nThe employee node with the ssn:%s is deleted",temp->ssn);
         free(temp);
         count--;
         return first;
}

NODE insertend()
{
          NODE cur, temp;
          temp = create();

          if(first == NULL)
          {
                    return temp;
          }
         cur= first;
         while(cur->rlink!=NULL)
        {
                  cur = cur->rlink;
         }

         cur->rlink = temp;
         temp->llink = cur;
          return first;
}

NODE deleteend()
{
         NODE prev,cur;
         if(first == NULL)
        {
                 printf("\nDoubly Linked List is empty");
                 return NULL;
        }

        if(first->rlink == NULL)
        {
                   printf("\nThe employee node with the ssn:%s is deleted",first->ssn);
                   free(first);
                   count--;
                   return NULL;
        }

         prev=NULL;
         cur=first;

        while(cur->rlink!=NULL)
        {
                  prev=cur;
                  cur = cur->rlink;
         }

         cur->llink = NULL;
         printf("\nThe employee node with the ssn:%s is deleted",cur->ssn);
         free(cur);
         prev->rlink = NULL;
         count--;
         return first;
}

void deqdemo()
{
       int ch;
       while(1)
      {
              printf("\nDemo Double Ended Queue Operation");
      printf("\n1:InsertQueueFront\n 2: DeleteQueueFront\n 3:InsertQueueRear\n 4:DeleteQueueRear\n 5:DisplayStatus\n 6: Exit \n");
              scanf("%d", &ch);

              switch(ch)
             {
                     case 1: first=insertfront();
                                 break;
                    case 2: first=deletefront();
                               break;
                   case 3: first=insertend();
                               break;
                   case 4: first=deleteend();
                              break;
                    case 5: display();
                               break;
                   default : return;
           }
     }
}

void main()
{
    int ch,i,n;
    while(1)
    {
        printf("\n\n~~~Menu~~~");
        printf("\n1:Create DLL of Employee Nodes");
        printf("\n2:DisplayStatus");
         printf("\n3:InsertAtEnd");
         printf("\n4:DeleteAtEnd");
         printf("\n5:InsertAtFront");
         printf("\n6:DeleteAtFront");
         printf("\n7:Double Ended Queue Demo using DLL");
         printf("\n8:Exit \n");
         printf("\nPlease enter your choice: ");
        scanf("%d",&ch);

        switch(ch)
        {
        case 1 : printf("\nEnter the no of Employees:   ");
                   scanf("%d",&n);
                   for(i=1;i<=n;i++)
                   first = insertend();
                   break;

        case 2:  display();
                   break;

          case 3: first = insertend();
                  break;

          case 4: first = deleteend();
                  break;

          case 5: first = insertfront();
                  break;

          case 6: first = deletefront();
                break;

          case 7: deqdemo();
                  break;

          case 8 : exit(0);
        default: printf("\nPlease Enter the valid choice");
        }
    }
}

Output:
~~~Menu~~~
1:Create DLL of Employee Nodes
2:DisplayStatus
3:InsertAtEnd
4:DeleteAtEnd
5:InsertAtFront
6:DeleteAtFront
7:Double Ended Queue Demo using DLL
8:Exit
Please enter your choice: 1
Enter the no of Employees:   2

Enter the ssn,Name,Department,Designation,Salary,PhoneNo of the employee:
111
aaa
dept1
des1
1000
11111

Enter the ssn,Name,Department,Designation,Salary,PhoneNo of the employee:
222
bbb
dept2
des2
2000
22222

~~~Menu~~~
1:Create DLL of Employee Nodes
2:DisplayStatus
3:InsertAtEnd
4:DeleteAtEnd
5:InsertAtFront
6:DeleteAtFront
7:Double Ended Queue Demo using DLL
8:Exit
Please enter your choice: 2

ENode:1||SSN:111|Name:aaa|Department:dept1|Designation:des1|Salary:1000|Phone no:11111
ENode:2||SSN:222|Name:bbb|Department:dept2|Designation:des2|Salary:2000|Phone no:22222
No of employee nodes is 2

~~~Menu~~~
1:Create DLL of Employee Nodes
2:DisplayStatus
3:InsertAtEnd
4:DeleteAtEnd
5:InsertAtFront
6:DeleteAtFront
7:Double Ended Queue Demo using DLL
8:Exit
Please enter your choice: 3

Enter the ssn,Name,Department,Designation,Salary,PhoneNo of the employee:
333
ccc
dept3
des3
3000
33333

~~~Menu~~~
1:Create DLL of Employee Nodes
2:DisplayStatus
3:InsertAtEnd
4:DeleteAtEnd
5:InsertAtFront
6:DeleteAtFront
7:Double Ended Queue Demo using DLL
8:Exit
Please enter your choice: 2

ENode:1||SSN:111|Name:aaa|Department:dept1|Designation:des1|Salary:1000|Phone no:11111
ENode:2||SSN:222|Name:bbb|Department:dept2|Designation:des2|Salary:2000|Phone no:22222
ENode:3||SSN:333|Name:ccc|Department:dept3|Designation:des3|Salary:3000|Phone no:33333
No of employee nodes is 3

~~~Menu~~~
1:Create DLL of Employee Nodes
2:DisplayStatus
3:InsertAtEnd
4:DeleteAtEnd
5:InsertAtFront
6:DeleteAtFront
7:Double Ended Queue Demo using DLL
8:Exit
Please enter your choice: 5

Enter the ssn,Name,Department,Designation,Salary,PhoneNo of the employee:
444
ddd
dept4
des4
4000
44444

~~~Menu~~~
1:Create DLL of Employee Nodes
2:DisplayStatus
3:InsertAtEnd
4:DeleteAtEnd
5:InsertAtFront
6:DeleteAtFront
7:Double Ended Queue Demo using DLL
8:Exit

Please enter your choice: 2

ENode:1||SSN:444|Name:ddd|Department:dept4|Designation:des4|Salary:4000|Phone no:44444
ENode:2||SSN:111|Name:aaa|Department:dept1|Designation:des1|Salary:1000|Phone no:11111
ENode:3||SSN:222|Name:bbb|Department:dept2|Designation:des2|Salary:2000|Phone no:22222
ENode:4||SSN:333|Name:ccc|Department:dept3|Designation:des3|Salary:3000|Phone no:33333
No of employee nodes is 4

~~~Menu~~~
1:Create DLL of Employee Nodes
2:DisplayStatus
3:InsertAtEnd
4:DeleteAtEnd
5:InsertAtFront
6:DeleteAtFront
7:Double Ended Queue Demo using DLL
8:Exit
Please enter your choice: 4

The employee node with the ssn:333 is deleted

~~~Menu~~~
1:Create DLL of Employee Nodes
2:DisplayStatus
3:InsertAtEnd
4:DeleteAtEnd
5:InsertAtFront
6:DeleteAtFront
7:Double Ended Queue Demo using DLL
8:Exit
Please enter your choice: 6

The employee node with the ssn:444 is deleted

~~~Menu~~~
1:Create DLL of Employee Nodes
2:DisplayStatus
3:InsertAtEnd
4:DeleteAtEnd
5:InsertAtFront
6:DeleteAtFront
7:Double Ended Queue Demo using DLL
8:Exit
Please enter your choice: 2

ENode:1||SSN:111|Name:aaa|Department:dept1|Designation:des1|Salary:1000|Phone no:11111
ENode:2||SSN:222|Name:bbb|Department:dept2|Designation:des2|Salary:2000|Phone no:22222
No of employee nodes is 2

~~~Menu~~~
1:Create DLL of Employee Nodes
2:DisplayStatus
3:InsertAtEnd
4:DeleteAtEnd
5:InsertAtFront
6:DeleteAtFront
7:Double Ended Queue Demo using DLL
8:Exit
Please enter your choice: 7

Demo Double Ended Queue Operation
1:InsertQueueFront
2: DeleteQueueFront
3:InsertQueueRear
4:DeleteQueueRear
5:DisplayStatus
6: Exit
2

The employee node with the ssn:111 is deleted

Demo Double Ended Queue Operation
1:InsertQueueFront
2: DeleteQueueFront
3:InsertQueueRear
4:DeleteQueueRear
5:DisplayStatus
6: Exit
4

The employee node with the ssn:222 is deleted

Demo Double Ended Queue Operation
1:InsertQueueFront
2: DeleteQueueFront
3:InsertQueueRear
4:DeleteQueueRear
5:DisplayStatus
6: Exit
2

Doubly Linked List is empty

Demo Double Ended Queue Operation
1:InsertQueueFront
2: DeleteQueueFront
3:InsertQueueRear
4:DeleteQueueRear
5:DisplayStatus
6: Exit
6

~~~Menu~~~
1:Create DLL of Employee Nodes
2:DisplayStatus
3:InsertAtEnd
4:DeleteAtEnd
5:InsertAtFront
6:DeleteAtFront
7:Double Ended Queue Demo using DLL
8:Exit

Please enter your choice: 8

Also Credits to,
Manoj T