Showing posts with label 3rd semester. Show all posts
Showing posts with label 3rd semester. 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

Friday 26 August 2016

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 


Wednesday 24 August 2016

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)

Monday 15 August 2016

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


Sunday 14 August 2016

Strings

Module  1: Strings
  • Printing individual characters of strings
  • 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







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)