Lap Report | Data Structures and Algorithms | Third Semester

 

TRIBHUVAN UNIVERSITY

MAHENDRA MORANG ADARSH MULTIPLE CAMPUS

BIRATNAGAR, MORANG

 

A Lab Report on

 

“Data Structures and Algorithms”

Submitted in partial fulfilment of the requirement for the award of the degree of

BICTE

(ICT. ED.435)

 

 

 

 

Submitted by:

 

NAME: Vivek *

SYMBOL NO: 77**20

 

Under the guidance of

ER. BIBEK KUMAR SARDAR

Department of Faculty of Education

 

Submitted to:

MAHENDRA MORANG ADARSH MULTIPLE CAMPUS

Faculty of Education

Tribhuvan University

2079

 

 

 

 

INDEX

Lab. No.	Title of the Lab	Date of Lab	Date of Submission	Signature
1	Programming on dynamic memory allocation
2	Programming on linked list
3	Programming on stack
4	Programming on queue
5	Programming with Recursion
6	Programming on tree
7	Programming
8	Programming with  graph

 

I.               Write a program example  of malloc() function.

1. #include<stdio.h>  
2. #include<stdlib.h>  
3. int main(){  
4.   int n,i,*ptr,sum=0;    
5.     printf("Enter number of elements: ");    
6.     scanf("%d",&n);    
7.     ptr=(int*)malloc(n*sizeof(int));  //memory allocated using malloc    
8.     if(ptr==NULL)                         
9.     {    
10.         printf("Sorry! unable to allocate memory");    
11.         exit(0);    
12.     }    
13.     printf("Enter elements of array: ");    
14.     for(i=0;i<n;++i)    
15.     {    
16.         scanf("%d",ptr+i);    
17.         sum+=*(ptr+i);    
18.     }    
19.     printf("Sum=%d",sum);    
20.     free(ptr);     
21. return 0;  
22. }    

Output

Enter elements of array: 3

Enter elements of array: 10

10

10

Sum=30

II.             Write program example of calloc() function.

1. #include<stdio.h>  
2. #include<stdlib.h>  
3. int main(){  
4.  int n,i,*ptr,sum=0;    
5.     printf("Enter number of elements: ");    
6.     scanf("%d",&n);    
7.     ptr=(int*)calloc(n,sizeof(int));  //memory allocated using calloc    
8.     if(ptr==NULL)                         
9.     {    
10.         printf("Sorry! unable to allocate memory");    
11.         exit(0);    
12.     }    
13.     printf("Enter elements of array: ");    
14.     for(i=0;i<n;++i)    
15.     {    
16.         scanf("%d",ptr+i);    
17.         sum+=*(ptr+i);    
18.     }    
19.     printf("Sum=%d",sum);    
20.     free(ptr);    
21. return 0;  
22. }    

Output

Enter elements of array: 3

Enter elements of array: 10

10

10

Sum=30

III.                Write program to create stack with array and linked list implementation.

#include<stdio.h>

#include<process.h>

#include<stdlib.h>

 

#define MAX 5 //Maximum number of elements that can be stored

 

int top=-1,stack[MAX];

void push();

void pop();

void display();

 

void main()

{

int ch;

while(1) //infinite loop, will end when choice will be 4

{

printf("\n*** Stack Menu ***");

printf("\n\n1.Push\n2.Pop\n3.Display\n4.Exit");

printf("\n\nEnter your choice(1-4):");

scanf("%d",&ch);

switch(ch)

{

case 1: push();

break;

case 2: pop();

break;

case 3: display();

break;

case 4: exit(0);

default: printf("\nWrong Choice!!");

}

}

}

 

void push()

{

int val;

if(top==MAX-1)

{

printf("\nStack is full!!");

}

else

{

printf("\nEnter element to push:");

scanf("%d",&val);

top=top+1;

stack[top]=val;

}

}

 

void pop()

{

if(top==-1)

{

printf("\nStack is empty!!");

}

else

{

printf("\nDeleted element is %d",stack[top]);

top=top-1;

}

}

 

void display()

{

int i;

if(top==-1)

{

printf("\nStack is empty!!");

}

else

{

printf("\nStack is...\n");

for(i=top;i>=0;--i)

printf("%d\n",stack[i]);

}

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

IV.                Write a program to solve the problem of TOH.

#include <stdio.h>

#include <stdlib.h>

 

int main()

{

   hanoi(3, 'A', 'B', 'C');

   return 0;

         }

 

void hanoi(int n, char rodFrom, char rodMiddle, char rodTo){

   if(n==1){

       printf("Disk 1 moved from %c to %c \n",rodFrom,rodTo);

       return;

   }

   hanoi(n-1,rodFrom,rodTo,rodMiddle);

   printf("Disk %d moved from %c to %c \n",n,rodFrom,rodTo);

   hanoi(n-1,rodMiddle,rodFrom,rodTo);

 

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

V.                  Write a program to print Fibonacci series.

#include<stdio.h>    

void printFibonacci(int n){    

    static int n1=0,n2=1,n3;    

    if(n>0){    

         n3 = n1 + n2;    

         n1 = n2;    

         n2 = n3;    

         printf("%d ",n3);    

         printFibonacci(n-1);    

    }    

}    

int main(){    

    int n;    

    printf("Enter the number of elements: ");    

    scanf("%d",&n);    

    printf("Fibonacci Series: ");    

    printf("%d %d ",0,1);    

    printFibonacci(n-2);//n-2 because 2 numbers are already printed    

  return 0;  

 }    

Output:

Enter the number of elements:15

0   1 1 2 3 5 8 13 21 34 55 89 144 233 377

VI.                Write a program to calculate factorial.

 

 

#include<stdio.h>

long int multiplyNumbers(int n);

int main() {

    int n;

    printf("Enter a positive integer: ");

    scanf("%d",&n);

    printf("Factorial of %d = %ld", n, multiplyNumbers(n));

    return 0;

}

long int multiplyNumbers(int n) {

    if (n>=1)

        return n*multiplyNumbers(n-1);

    else

        return 1;

}

Run Code

Output

Enter a positive integer: 6

Factorial of 6 = 720

VII.              Write a program to implement binary tree.

#include<stdio.h>

#include<stdlib.h>

struct node

{

int value;

struct node *left_child, *right_child;

};

 

struct node *new_node(int value)

{

struct node *tmp = (struct node *)malloc(sizeof(struct node));

tmp->value = value;

tmp->left_child = tmp->right_child = NULL;

return tmp;

}

 

void print(struct node *root_node) // displaying the nodes!

{

if (root_node != NULL)

{

print(root_node->left_child);

printf("%d \n", root_node->value);

print(root_node->right_child);

}

}

 

struct node* insert_node(struct node* node, int value) // inserting nodes!

{

 

if (node == NULL) return new_node(value);

if (value < node->value)

{

node->left_child = insert_node(node->left_child, value);

}

else if (value > node->value)

{

node->right_child = insert_node(node->right_child, value);

}

return node;

}

 

int main()

{

 

printf("TechVidvan Tutorial: Implementation of a Binary Tree in C!\n\n");

 

struct node *root_node = NULL;

root_node = insert_node(root_node, 10);

insert_node(root_node, 10);

insert_node(root_node, 30);

insert_node(root_node, 25);

insert_node(root_node, 36);

insert_node(root_node, 56);

insert_node(root_node, 78);

 

print(root_node);

 

return 0;

}

Output:-

TechVidvan Tutorial: Implementation of a Binary Tree in C!

10
25
30
36
56
78

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

VIII.            Write a program to implement bubble sort in C.

#include <stdio.h>

int main()
{
  int array[100], n, c, d, swap;

  printf("Enter number of elements\n");
  scanf("%d", &n);

  printf("Enter %d integers\n", n);

  for (c = 0; c < n; c++)
    scanf("%d", &array[c]);

  for (c = 0 ; c < n - 1; c++)
  {
    for (d = 0 ; d < n - c - 1; d++)
    {
      if (array[d] > array[d+1]) /* For decreasing order use '<' instead of '>' */
      {
        swap       = array[d];
        array[d]   = array[d+1];
        array[d+1] = swap;
      }
    }
  }

  printf("Sorted list in ascending order:\n");

  for (c = 0; c < n; c++)
     printf("%d\n", array[c]);

  return 0;
}

 

 

 

 

 

IX.                Write a program to implement selection sort in C.

#include <stdio.h>

int main()
{
  int array[100], n, c, d, position, t;

  printf("Enter number of elements\n");
  scanf("%d", &n);

  printf("Enter %d integers\n", n);

  for (c = 0; c < n; c++)
    scanf("%d", &array[c]);

  for (c = 0; c < (n - 1); c++) // finding minimum element (n-1) times
  {
    position = c;

    for (d = c + 1; d < n; d++)
    {
      if (array[position] > array[d])
        position = d;
    }
    if (position != c)
    {
      t = array[c];
      array[c] = array[position];
      array[position] = t;
    }
  }

  printf("Sorted list in ascending order:\n");

  for (c = 0; c < n; c++)
    printf("%d\n", array[c]);

  return 0;
}

 

 

 

X.                  Write a program to implement graph traversal algorithms BFS.

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#define MAX 5

struct Vertex {

   char label;

   bool visited;

};

//queue variables

int queue[MAX];

int rear = -1;

int front = 0;

int queueItemCount = 0;

//graph variables

//array of vertices

struct Vertex* lstVertices[MAX];

//adjacency matrix

int adjMatrix[MAX][MAX];

//vertex count

int vertexCount = 0;

//queue functions

void insert(int data) {

   queue[++rear] = data;

   queueItemCount++;

}

int removeData() {

   queueItemCount--;

   return queue[front++]; 

}

bool isQueueEmpty() {

   return queueItemCount == 0;

}

//graph functions

//add vertex to the vertex list

void addVertex(char label) {

   struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));

   vertex->label = label;  

   vertex->visited = false;     

   lstVertices[vertexCount++] = vertex;

}

//add edge to edge array

void addEdge(int start,int end) {

   adjMatrix[start][end] = 1;

   adjMatrix[end][start] = 1;

}

//display the vertex

void displayVertex(int vertexIndex) {

   printf("%c ",lstVertices[vertexIndex]->label);

}       

//get the adjacent unvisited vertex

int getAdjUnvisitedVertex(int vertexIndex) {

   int i;

   for(i = 0; i<vertexCount; i++) {

      if(adjMatrix[vertexIndex][i] == 1 && lstVertices[i]->visited == false)

         return i;

   }

   return -1;

}

void breadthFirstSearch() {

   int i;

   //mark first node as visited

   lstVertices[0]->visited = true;

   //display the vertex

   displayVertex(0);   

   //insert vertex index in queue

   insert(0);

   int unvisitedVertex;

   while(!isQueueEmpty()) {

      //get the unvisited vertex of vertex which is at front of the queue

      int tempVertex = removeData();   

      //no adjacent vertex found

      while((unvisitedVertex = getAdjUnvisitedVertex(tempVertex)) != -1) {    

         lstVertices[unvisitedVertex]->visited = true;

         displayVertex(unvisitedVertex);

         insert(unvisitedVertex);               

      }

   }   

   //queue is empty, search is complete, reset the visited flag        

   for(i = 0;i<vertexCount;i++) {

      lstVertices[i]->visited = false;

   }    

}

int main() {

   int i, j;

   for(i = 0; i<MAX; i++) // set adjacency {

      for(j = 0; j<MAX; j++) // matrix to 0

         adjMatrix[i][j] = 0;

   }

   addVertex('S');   // 0

   addVertex('A');   // 1

   addVertex('B');   // 2

   addVertex('C');   // 3

   addVertex('D');   // 4

   addEdge(0, 1);    // S - A

   addEdge(0, 2);    // S - B

   addEdge(0, 3);    // S - C

   addEdge(1, 4);    // A - D

   addEdge(2, 4);    // B - D

   addEdge(3, 4);    // C - D

   printf("\nBreadth First Search: ");

   breadthFirstSearch();

   return 0;

}

 

Output

Breadth First Search: S A B C D

XI.                Write a program to implement graph traversal algorithms DFS.

1.  #include<stdio.h>

2.  #include<conio.h>

3.  int a[20][20],reach[20],n;

4.  void dfs(int v) {

5.    int i;

6.    reach[v]=1;

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

8.      if(a[v][i] && !reach[i]) {

9.           printf("\n %d->%d",v,i);

10.         dfs(i);

11.  }

12.}

13.void main() {

14.  int i,j,count=0;

15.  clrscr();

16.  printf("\n Enter number of vertices:");

17.  scanf("%d",&n);

18.  for (i=1;i<=n;i++) {

19.         reach[i]=0;

20.         for (j=1;j<=n;j++)

21.            a[i][j]=0;

22.  }

23.  printf("\n Enter the adjacency matrix:\n");

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

25.    for (j=1;j<=n;j++)

26.     scanf("%d",&a[i][j]);

27.  dfs(1);

28.  printf("\n");

29.  for (i=1;i<=n;i++) {

30.         if(reach[i])

31.            count++;

32.  }

33.  if(count==n)

34.    printf("\n Graph is connected"); else

35.    printf("\n Graph is not connected");

36.  getch();

37.}