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

Topic wise VTU Data Structures questions 15CS33

Complied set of Topic wise VTU Data Structures questions 15CS33 

Module 1:

Pointers                                            Download

Strutures and Unions                      Download

Dynamic Memory allocation           Download

Arrays                                               Download

Strings                                               Download

Module 2:

Stack                                                  Download

Recursion                                          Download

Queue                                                Download 

Lab Program 6 Circular Queue 15CSL38 Data Structures in C Lab

Lab Program 6:

Design, Develop and Implement a menu driven Program in C for the following operations on Circular QUEUE of Characters (Array Implementation of Queue with maximum size MAX)
a. Insert an Element on to Circular QUEUE
b. Delete an Element from Circular QUEUE
c. Demonstrate Overflow and Underflow situations on Circular QUEUE
d. Display the status of Circular QUEUE
e. Exit
Support the program with appropriate functions for each of the above operations

#include <stdio.h>
#include<stdlib.h>
#include<stdio_ext.h>
#define MAX 3

char cq[MAX];
int front = -1, rear = -1;

void insert(char);
void delete();
void display();

void main()
{
             int ch;
             char item;
             while(1)
             {
                            printf("\n\n~~Main Menu~~");
                            printf("\n==> 1. Insertion and Overflow Demo");
                            printf("\n==> 2. Deletion and Underflow Demo");
                            printf("\n==> 3. Display");
                            printf("\n==> 4. Exit");
                            printf("\nEnter Your Choice: ");
                            scanf("%d", &ch);
                            __fpurge(stdin);
                           switch(ch)
                          {
                                           case 1:        printf("\n\nEnter the element to be inserted: ");
                                                              scanf("%c", &item);
                                                              insert(item);
                                                              break;
                                           case 2:        delete();
                                                              break;
                                           case 3:        display();
                                                              break;
                                            case 4:       exit(0);
                                            default:      printf("\n\nPlease enter a valid choice");
                            }
               }
}

void insert(char item)
{
                 if(front == (rear+1)%MAX)
                 {
                              printf("\n\n~~Circular Queue Overflow~~");
                 }
                 else
                 {
                             if(front == -1)
                                             front = rear = 0;
                             else
                                              rear = (rear+1)%MAX;
                             cq[rear] = item;
                  }
}

void delete()
{
                char item;
                if(front == -1)
                {
                              printf("\n\n~~Circular Queue Underflow~~");
                }
                else
                {
                               item = cq[front];
                               printf("\n\nDeleted element from the queue is: %c ",item );
                               

                               if(front == rear) //only one element
                                                front = rear = -1;
                               else
                                               front = (front+1)%MAX;
                 }
}


void display ()
{
                   int i ;
                   if(front == -1)
                   {
                                 printf("\n\nCircular Queue Empty");
                   }
                   else
                   {
                                printf("\nCircular Queue contents are:\n");
                                printf("Front[%d]-> ", front);
                               for(i = front; i != rear ; i = (i+1)%MAX)
                               {
                                                   printf(" %c", cq[i]);
                               }
                               printf(" %c", cq[i]);
                               printf(" <-[%d]Rear", rear);
                    }
}


Output:
~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 1

Enter the element to be inserted: A

~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 1
Enter the element to be inserted: B

~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 1
Enter the element to be inserted: C

~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 1

Enter the element to be inserted: D
~~Circular Queue Overflow~~

~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 3

Circular Queue contents are:
Front[0]-> A B C <-[2]Rear

~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 2

Deleted element from the queue is: A

~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 3

Circular Queue contents are:
Front[1]-> B C <-[2]Rear

~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 1

Enter the element to be inserted: E

~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 3

Circular Queue contents are:
Front[1]-> B C E <-[0]Rear

~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 4


Also Credits to: 
Manoj Taleka  (manoj89biet@gmail.com)
Yashaswini Jogi (jogi.yash@gmail.com)

Delete the substring of length n from the string at specified position (pos)

Delete the substring of length n from the string at specified position (pos)

#include<stdio.h>

#include<string.h>

void main()

{

          char str[20], substr[20];

          int n, pos, i, m;

          printf("\nEnter the string:");

          gets(str);

          printf("\nEnter the position:");

          scanf("%d", &pos);

          printf("\nEnter the number of characters to be deleted:");

          scanf("%d", &n);

          m = strlen(str);

          for(i=pos;i<m-n;i++)

          { 

              str[i] = str[i+n];

          }

          str[i] ='\0';

          printf("\nThe substring is:");

          puts(str);

}

Output:

Enter the string:         abcdefghijkl

Enter the position:     3

Enter the number of characters to be deleted:  5

The substring is:     abcijkl

Strings

Module  1: Strings

• Formatted input and output: character

• Formatted input and output: string

• Unformatted input and output: character

• Unformatted input and output: string

• Printing individual characters of strings

• Convert from lowercase to uppercase using library function

• Convert from uppercase to lowercase using library function

• Length of the string using library function

• Length of the string without using library function

• Reversing a String using library function

• Reversing a String without using library function  

• String copy using library function

• String copy without using library function

• String concatenation using library function

• String concatenation without using library function  

• String comparison using library function

• String comparison without using library function

• Array of strings

• Insert a substring to string at a valid position

• Extract a substring from string 

• Find all occurrences of substring  in a string

• Delete all occurrences of substring from a string

• Delete the substring of length n from the string at specified position (pos)

Delete all occurrences of pattern from a string

Delete all occurrences of pattern (pat) from a string (txt)

#include<stdio.h>

#include<string.h>

void main()

{

                char txt[30],  pat[30];

                int m, n;

                int i, j, found = 0;

                printf("\nEnter the main string:");

                gets(txt);

                printf("\nEnter the pattern to be searched: ");

                gets(pat);

                m = strlen(txt);

                n = strlen(pat);

                for(i=0;  i<=m-n;  i++)

                {

                                found  = 1;

                                for(j=0; j<n; j++)

                                {

                                                if(txt[i+j] != pat[j])

                                                {

                                                                found = 0;

                                                                break;

                                                }

                                }

                                if(found == 1)

                                {

                    /* If pattern is found then shift all characters to left and decrement the string length */

                                                for(j=i;  j<m -n; j++)

                                                {

                                                                txt[j] = txt[j+n];

                                                }

                                                txt[j] = '\0';

                                                m = m - n;

                                 }

                }

                if(found == 0)

                                printf("\nPattern not found");

                else

                {

                                printf("\nAfter deleting pattern the string is: ");

                                puts(txt);

                }

}

Output:

Enter the main string:    hello hii how hii

Enter the pattern to be searched:   hii

After deleting pattern the string is: hello    how

Enter the main string:    hello hii how hii

Enter the pattern to be searched: abc

Pattern not found

Lab Program 5a Evaluation of Suffix Expression 15CSL38 Data Structures in C Lab

Lab Program 5a:

Design, Develop and Implement a Program in C for the following Stack Applications
a. Evaluation of Suffix expression with single digit operands and operators: +, -, *, /, %, ^

 #include<stdio.h>

#include<stdlib.h>

#include<math.h>

int i, top = -1;

int op1, op2, res, s[20];

char postfix[90], symb;

void push(int item)

{

            top = top+1;

            s[top] = item;

}

int pop()

{

            int item;

            item  =  s[top];

            top = top-1;

            return item;

}

void main()

{

            printf("\nEnter a valid postfix expression:\n");

            scanf("%s", postfix);

            for(i=0; postfix[i]!='\0'; i++)

            {

                        symb = postfix[i];

                        if(isdigit(symb))

                        {

                                    push(symb - '0');

                        }

                        else

                        {

                                    op2 = pop();

                                    op1 = pop();

                                    switch(symb)

                                    {

                                                case '+':            push(op1+op2);

                                                                        break;

                                                case '-':             push(op1-op2);

                                                                        break;

                                                case '*':            push(op1*op2);

                                                                        break;

                                                case '/':             push(op1/op2);

                                                                        break;

                                                case '%':           push(op1%op2);

                                                                        break;

                                                case '$':

                                                case '^':            push(pow(op1, op2));

                                                                        break;

                                                default :   push(0);

                                    }

                        }

            }

            res = pop();

            printf("\n Result = %d", res);

}

Output:

To compile in Linux: gcc –lm 5.c

Enter a valid postfix expression:

623+-382/+*2$3+

Result = 52

Enter a valid postfix expression:

42$3*3-84/11+/+

Result = 46

Also Credits to: 

Manoj Taleka  (manoj89biet@gmail.com)

Yashaswini Jogi (jogi.yash@gmail.com)