Madhuben and Bhanubhai Patel

Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

Practical 1
1.1 Write a program to insert/delete in linear array at specific position.

#include <stdio.h>

int main()

int arr[100];

int i, item, pos, size=7;

printf("Enter 7 elements: ");

for (i = 0; i < size; i++) // reading array

scanf("%d",&arr[i]);

printf("Array before insertion: "); // print the original array

for (i = 0; i < size; i++)

printf("%d ", arr[i]);

printf("\n");

printf("Enter the element to be inserted: "); // read element to be inserted

scanf("%d",&item);

printf("Enter the position at which the element is to be inserted: ");

// read position at which element is to be inserted

scanf("%d",&pos);

size++; // increase the size

for (i = size-1; i >= pos; i--) // shift elements forward

arr[i] = arr[i - 1];

arr[pos - 1] = item; // insert item at position

printf("Array after insertion: "); // print the updated array

 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

for (i = 0; i < size; i++)

printf("%d ", arr[i]);

printf("\n");

return 0;

#include<stdio.h>

int main()

int key, i, pos = -1, size=5;

int arr[5] = {1, 20, 5, 78, 30};

printf("Array before deletion: ");

for (i = 0; i < size; i++)

printf("%d ", arr[i]);

printf("\n");

printf("Enter element to delete: ");

scanf("%d",&key);

// traverse the array // if any element matches the key, store its position
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

for(i = 0; i < size; i++)

if(arr[i] == key)

pos = i;

break;

if(pos != -1)

for(i = pos; i < size - 1; i++) //shift elements backwards by one position

arr[i] = arr[i+1];

printf("Array after deletion: ");

for(i = 0; i < size - 1; i++)

printf("%d ",arr[i]);

else

printf("Element Not Found\n");

return 0;

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

1.2 Write a program to remove duplicate elements from liner array.

#include <stdio.h>

#include <conio.h>

int main ()

// declare local variables

int arr[20], i, j, k, size;

printf (" Define the number of elements in an array: ");

scanf (" %d", &size);

printf (" \n Enter %d elements of an array: \n ", size);

// use for loop to enter the elements one by one in an array

for ( i = 0; i < size; i++)

scanf (" %d", &arr[i]);

for ( i = 0; i < size; i ++) // use nested for loop to find the duplicate elements in array

for ( j = i + 1; j < size; j++)

if ( arr[i] == arr[j]) // use if statement to check duplicate element

for ( k = j; k < size - 1; k++) // delete the current position of the duplicate element

arr[k] = arr [k + 1];

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

size--; // decrease the size of array after removing duplicate element

j--; // if the position of the elements is changes, don't increase the index j

/* display an array after deletion or removing of the duplicate elements */

printf (" \n Array elements after deletion of the duplicate elements: ");

for ( i = 0; i < size; i++) // for loop to print the array

printf (" %d \t", arr[i]);

return 0;

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

1.3 Write a program to read 10 integers in an array. Sort them out on the basis of number of

digits in each element.

#include <stdio.h>

void main()

int arr1[100];

int n, i, j, tmp;

printf("\n\nsort elements of array in ascending order :\n ");

printf("----------------------------------------------\n");

printf("Input the size of array : ");

scanf("%d", &n);

printf("Input %d elements in the array :\n",n);

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

printf("element - %d : ",i);

scanf("%d",&arr1[i]);

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

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

if(arr1[j] <arr1[i])

tmp = arr1[i];

arr1[i] = arr1[j];
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

arr1[j] = tmp;

printf("\nElements of array in sorted ascending order:\n");

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

printf("%d ", arr1[i]);

printf("\n\n");

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

Practical 2
2.1 Demonstrate the concept of Call by value and Call by Reference.

#include<stdio.h>

void change(int num) {

printf("Before adding value inside function num=%d \n",num);

num=num+100;

printf("After adding value inside function num=%d \n", num);

int main() {

int x=100;

printf("Before function call x=%d \n", x);

change(x); //passing value in function

printf("After function call x=%d \n", x);

return 0;

#include <stdio.h>

void swap(int , int); //prototype of the function

int main()

int a = 10;

int b = 20;
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

printf("Before swapping the values in main a = %d, b = %d\n",a,b);

// printing the value of a and b in main

swap(a,b);

printf("After swapping values in main a = %d, b = %d\n",a,b);

// The value of actual parameters do not change by changing the formal parameters in call by value, a =
10, b = 20

void swap (int a, int b)

int temp;

temp = a;

a=b;

b=temp;

printf("After swapping values in function a = %d, b = %d\n",a,b); // Formal parameters, a = 20, b = 10

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

2.2 Write a program to prints array elements in reverse orders applying pointers

#include<stdio.h>

#define N 5

int main()

int a[N], i, *ptr;

printf("Enter %d integer numbers\n", N);

for(i = 0; i < N; i++)

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

ptr = &a[N - 1];

printf("\nElements of array in reverse order ...\n");

for(i = 0; i < N; i++)

printf("%d\n", *ptr--);

return 0;

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

Practical 3
3.1 Write a program for stack using array for the following operations:

Push, Pop, Peek and IsEmpty.

#include<stdio.h>

int stack[100],choice,n,top,x,i;

void push(void);

void pop(void);

void display(void);

int main()

//clrscr();

top=-1;

printf("\n Enter the size of STACK[MAX=100]:");

scanf("%d",&n);

printf("\n\t STACK OPERATIONS USING ARRAY");

printf("\n\t--------------------------------");

printf("\n\t 1.PUSH\n\t 2.POP\n\t 3.DISPLAY\n\t 4.EXIT");

do

printf("\n Enter the Choice:");

scanf("%d",&choice);

switch(choice)

case 1:
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

push();

break;

case 2:

pop();

break;

case 3:

display();

break;

case 4:

printf("\n\t EXIT POINT ");

break;

default:

printf ("\n\t Please Enter a Valid Choice(1/2/3/4)");

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

while(choice!=4);

return 0;

void push()

if(top>=n-1)

printf("\n\tSTACK is over flow");

else

printf(" Enter a value to be pushed:");

scanf("%d",&x);

top++;

stack[top]=x;

void pop()

if(top<=-1)

printf("\n\t Stack is under flow");

else

{
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

printf("\n\t The popped elements is %d",stack[top]);

top--;

void display()

if(top>=0)

printf("\n The elements in STACK \n");

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

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

printf("\n Press Next Choice");

else

printf("\n The STACK is empty");

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

3.2 Write a program to reverse a list of given numbers using stack.

#include <bits/stdc++.h>

using namespace std;

stack <int> stck;

void pushDigts(int num1){

int rem;

while (num1 > 0){

rem=num1 % 10;
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

stck.push(rem);

num1 = num1 / 10;

int revrseNum(){

int revrs = 0;

int i = 1;

int temp;

int topp;

while (!stck.empty()){

topp=stck.top();

stck.pop();

temp=topp*i;

revrs = revrs + temp;

i *= 10;

return revrs;

int main(){

int Num = 43556;

pushDigts(Num);

cout<<"Reverse of number is: "<<revrseNum();

return 0;

Output Reverse of number is: 65534

 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

3.3 Write a program to check nesting of parenthesis using a stack.

#include<stdio.h>

#include<string.h>

#define MAX 20

#define true 1

#define false 0

int top = -1;

int stack[MAX];

char push(char item) /*Begin of push*/

if(top == (MAX-1))

printf("Stack Overflow\n");

else

top=top+1;

stack[top] = item;

}/*End of push*/

char pop() /*Begin of pop*/

if(top == -1)

printf("Stack Underflow\n");

else

return(stack[top--]);

}/*End of pop*/
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

main() /*Begin of main*/

char exp[MAX],temp;

int i,valid=true;

printf("Enter an algebraic expression : ");

gets(exp);

for(i=0;i<strlen(exp);i++)

if(exp[i]=='(' || exp[i]=='{' || exp[i]=='[')

push( exp[i] );

if(exp[i]==')' || exp[i]=='}' || exp[i]==']')

if(top == -1) /* stack empty */

valid=false;

else

temp=pop();

if( exp[i]==')' && (temp=='{' || temp=='[') )

valid=false;

if( exp[i]=='}' && (temp=='(' || temp=='[') )

valid=false;

if( exp[i]==']' && (temp=='(' || temp=='{') )

valid=false;

if(top>=0) /*stack not empty*/

 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

valid=false;

if( valid==true )

printf("Valid expression\n");

else

printf("Invalid expression\n");

} /*End of main*/
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

Practical 4
4.1 Write a program of conversion of an expression from infix to Postfix, Prefix.

#include<stdio.h>

#include<ctype.h>

char stack[100];

int top = -1;

void push(char x)

stack[++top] = x;

char pop()

if(top == -1)

return -1;

else

return stack[top--];

int priority(char x)

if(x == '(')

return 0;

if(x == '+' || x == '-')

return 1;

if(x == '*' || x == '/')

return 2;
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

return 0;

int main()

char exp[100];

char *e, x;

printf("Enter the expression : ");

scanf("%s",exp);

printf("\n");

e = exp;

while(*e != '\0')

if(isalnum(*e))

printf("%c ",*e);

else if(*e == '(')

push(*e);

else if(*e == ')')

while((x = pop()) != '(')

printf("%c ", x);

else

while(priority(stack[top]) >= priority(*e))

printf("%c ",pop());
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

push(*e);

e++;

while(top != -1)

printf("%c ",pop());

}return 0;

Infix to Prefix

#include<stdio.h>

#include<string.h>

#include<limits.h>

#include<stdlib.h>

# define MAX 100

int top = -1;

char stack[MAX];

// checking if stack is full

int isFull() {

return top == MAX - 1;

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

// checking is stack is empty

int isEmpty() {

return top == -1;

// Push function here, inserts value in stack and increments stack top by 1

void push(char item) {

if (isFull())

return;

top++;

stack[top] = item;

// Function to remove an item from stack. It decreases top by 1

int pop() {

if (isEmpty())

return INT_MIN;

// decrements top and returns what has been popped

return stack[top--];

// Function to return the top from stack without removing it

int peek(){

if (isEmpty())

return INT_MIN;

return stack[top];

// A utility function to check if the given character is operand

 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

int checkIfOperand(char ch) {

return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');

// Fucntion to compare precedence

// If we return larger value means higher precedence

int precedence(char ch)

switch (ch)

case '+':

case '-':

return 1;

case '*':

case '/':

return 2;

case '^':

return 3;

return -1;

// The driver function for infix to postfix conversion

int getPostfix(char* expression)

{
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

int i, j;

for (i = 0, j = -1; expression[i]; ++i)

// Here we are checking is the character we scanned is operand or not

// and this adding to to output.

if (checkIfOperand(expression[i]))

expression[++j] = expression[i];

// Here, if we scan character ‘(‘, we need push it to the stack.

else if (expression[i] == '(')

push(expression[i]);

// Here, if we scan character is an ‘)’, we need to pop and print from the stack

// do this until an ‘(‘ is encountered in the stack.

else if (expression[i] == ')')

while (!isEmpty(stack) && peek(stack) != '(')

expression[++j] = pop(stack);

if (!isEmpty(stack) && peek(stack) != '(')

return -1; // invalid expression

else

pop(stack);

else // if an opertor

while (!isEmpty(stack) && precedence(expression[i]) <= precedence(peek(stack)))

expression[++j] = pop(stack);
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

push(expression[i]);

// Once all inital expression characters are traversed

// adding all left elements from stack to exp

while (!isEmpty(stack))

expression[++j] = pop(stack);

expression[++j] = '\0';

void reverse(char *exp){

int size = strlen(exp);

int j = size, i=0;

char temp[size];

temp[j--]='\0';

while(exp[i]!='\0')

temp[j] = exp[i];

j--;

i++;

strcpy(exp,temp);

void brackets(char* exp){

int i = 0;

while(exp[i]!='\0')
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

if(exp[i]=='(')

exp[i]=')';

else if(exp[i]==')')

exp[i]='(';

i++;

void InfixtoPrefix(char *exp){

int size = strlen(exp);

// reverse string

reverse(exp);

//change brackets

brackets(exp);

//get postfix

getPostfix(exp);

// reverse string again

reverse(exp);

int main()

printf("The infix is: ");

char expression[] = "((a/b)+c)-(d+(e*f))";

printf("%s\n",expression);

InfixtoPrefix(expression);
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

printf("The prefix is: ");

printf("%s\n",expression);

return 0;

4.2 Write a program to evaluate postfix expression.

// C program to evaluate value of a postfix expression

#include <stdio.h>

#include <string.h>

#include <ctype.h>

#include <stdlib.h>

// Stack type

struct Stack

int top;

unsigned capacity;

int* array;

};

// Stack Operations

struct Stack* createStack( unsigned capacity )

struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));

 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

if (!stack) return NULL;

stack->top = -1;

stack->capacity = capacity;

stack->array = (int*) malloc(stack->capacity * sizeof(int));

if (!stack->array) return NULL;

return stack;

int isEmpty(struct Stack* stack)

return stack->top == -1 ;

char peek(struct Stack* stack)

return stack->array[stack->top];

char pop(struct Stack* stack)

if (!isEmpty(stack))

return stack->array[stack->top--] ;

return '$';

void push(struct Stack* stack, char op)

stack->array[++stack->top] = op;
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

// The main function that returns value of a given postfix expression

int evaluatePostfix(char* exp)

// Create a stack of capacity equal to expression size

struct Stack* stack = createStack(strlen(exp));

int i;

// See if stack was created successfully

if (!stack) return -1;

// Scan all characters one by one

for (i = 0; exp[i]; ++i)

// If the scanned character is an operand (number here),

// push it to the stack.

if (isdigit(exp[i]))

push(stack, exp[i] - '0');

// If the scanned character is an operator, pop two

// elements from stack apply the operator

else

int val1 = pop(stack);

int val2 = pop(stack);

switch (exp[i])

case '+': push(stack, val2 + val1); break;

 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

case '-': push(stack, val2 - val1); break;

case '*': push(stack, val2 * val1); break;

case '/': push(stack, val2/val1); break;

return pop(stack);

// Driver program to test above functions

int main()

char exp[] = "231*+9-";

printf ("postfix evaluation: %d", evaluatePostfix(exp));

return 0;

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

Practical 5
5.1 Write a program for queue using array for the following operations:
Enqueue, Dequeue, IsEmpty, IsFull.

/** Queue implementation using array. */

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

#define CAPACITY 100 // Queue capacity

int queue[CAPACITY]; /* Global queue declaration. */

unsigned int size = 0;

unsigned int rear = CAPACITY - 1; // Initally assumed that rear is at end

unsigned int front = 0;

/* Function declaration for various operations on queue */

int enqueue(int data);

int dequeue();

int isFull();

int isEmpty();

int getRear();

int getFront();

/* Driver function */

int main()

int ch, data;

while (1) /* Run indefinitely until user manually terminates */

{
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

/* Queue menu */

printf("--------------------------------------\n");

printf(" QUEUE ARRAY IMPLEMENTATION PROGRAM \n");

printf("--------------------------------------\n");

printf("1. Enqueue\n");

printf("2. Dequeue\n");

printf("3. Size\n");

printf("4. Get Rear\n");

printf("5. Get Front\n");

printf("0. Exit\n");

printf("--------------------------------------\n");

printf("Select an option: ");

scanf("%d", &ch);

switch (ch) /* Menu control switch */

case 1:

printf("\nEnter data to enqueue: ");

scanf("%d", &data);

// Enqueue function returns 1 on success // otherwise 0

if (enqueue(data))

printf("Element added to queue.");

else

printf("Queue is full.");

break;
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

case 2:

data = dequeue();

// on success dequeue returns element removed // otherwise returns INT_MIN

if (data == INT_MIN)

printf("Queue is empty.");

else

printf("Data => %d", data);

break;

case 3:

// isEmpty() function returns 1 if queue is emtpy // otherwise returns 0

if (isEmpty())

printf("Queue is empty.");

else

printf("Queue size => %d", size);

break;

case 4:

if (isEmpty())

printf("Queue is empty.");

else

printf("Rear => %d", getRear());

break;

case 5:

if (isEmpty())

printf("Queue is empty.");

else
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

printf("Front => %d", getFront());

break;

case 0:

printf("Exiting from app.\n");

exit(0);

default:

printf("Invalid choice, please input number between (0-5).");

break;

printf("\n\n");

/** Enqueue/Insert an element to the queue. */

int enqueue(int data)

// Queue is full throw Queue out of capacity error.

if (isFull())

return 0;

rear = (rear + 1) % CAPACITY; // Ensure rear never crosses array bounds

size++; // Increment queue size

queue[rear] = data; // Enqueue new element to queue

return 1; // Successfully enqueued element to queue

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

/** Dequeue/Remove an element from the queue. */

int dequeue()

int data = INT_MIN;

if (isEmpty()) // Queue is empty, throw Queue underflow error

return INT_MIN;

data = queue[front]; // Dequeue element from queue

front = (front + 1) % CAPACITY; // Ensure front never crosses array bounds

size--; // Decrease queue size

return data;

/** Checks if queue is full or not. It returns 1 if queue is full, * overwise returns 0. */

int isFull()

return (size == CAPACITY);

/** * Checks if queue is empty or not. It returns 1 if queue is empty, * otherwise returns 0. */

int isEmpty()

return (size == 0);

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

/** * Gets, front of the queue. If queue is empty return INT_MAX otherwise * returns front of queue. */

int getFront()

return (isEmpty())

? INT_MIN

: queue[front];

/** * Gets, rear of the queue. If queue is empty return INT_MAX otherwise * returns rear of queue. */

int getRear()

return (isEmpty())

? INT_MIN

: queue[rear];

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

5.2 Write a program for circular queue using array for the following operations:
Enqueue, Dequeue, IsEmpty, IsFull.

// Circular Queue implementation in C

#include <stdio.h>

#define SIZE 5

int items[SIZE];

int front = -1, rear = -1;

int isFull() { // Check if the queue is full

if ((front == rear + 1) || (front == 0 && rear == SIZE - 1)) return 1;

return 0;

int isEmpty() { // Check if the queue is empty

if (front == -1) return 1;

return 0;

void enQueue(int element) { // Adding an element

if (isFull())

printf("\n Queue is full!! \n");

else {

if (front == -1) front = 0;

rear = (rear + 1) % SIZE;

items[rear] = element;

printf("\n Inserted -> %d", element);

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

// Removing an element

int deQueue() {

int element;

if (isEmpty()) {

printf("\n Queue is empty !! \n");

return (-1);

} else {

element = items[front];

if (front == rear) {

front = -1;

rear = -1;

// Q has only one element, so we reset the // queue after dequeing it. ?

else {

front = (front + 1) % SIZE;

printf("\n Deleted element -> %d \n", element);

return (element);

// Display the queue

void display() {

int i;

if (isEmpty())

printf(" \n Empty Queue\n");

 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

else {

printf("\n Front -> %d ", front);

printf("\n Items -> ");

for (i = front; i != rear; i = (i + 1) % SIZE) {

printf("%d ", items[i]);

printf("%d ", items[i]);

printf("\n Rear -> %d \n", rear);

int main() {

// Fails because front = -1

deQueue();

enQueue(1);

enQueue(2);

enQueue(3);

enQueue(4);

enQueue(5);

// Fails to enqueue because front == 0 && rear == SIZE - 1

enQueue(6);

display();

deQueue();

display();

enQueue(7);

display();
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

// Fails to enqueue because front == rear + 1

enQueue(8);

return 0;

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

Practical 6
6.1 Write a program for single linked list for the following operations:

1. Count the number of nodes in a given linked list

2. Delete the desired node from linked list

3. Insert the new node after the desired node into the linked list

4. Create a new list by reversing the list

5. Concatenates two linked list

#include <stdio.h>

#include <stdlib.h>

typedef struct Node{

int number;

struct Node* next;

}Node;

void Push(Node** head, int A)

Node* n = malloc(sizeof(Node));

n->number = A;

n->next = *head;

*head = n;

void deleteN(Node** head, int position)

Node* temp;

Node* prev;
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

temp = *head;

prev = *head;

for (int i = 0; i < position; i++) {

if (i == 0 && position == 1) {

*head = (*head)->next;

free(temp);

else {

if (i == position - 1 && temp) {

prev->next = temp->next;

free(temp);

else {

prev = temp;

if (prev == NULL) // position was greater than number of nodes in the

list

break;

temp = temp->next;

void printList(Node* head)

while(head){

printf("[%i] [%p]->%p\n", head->number, head, head->next);

 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

head = head->next;

printf("\n\n");

int main()

Node* list = malloc(sizeof(Node));

list->next = NULL;

Push(&list, 1);

Push(&list, 2);

Push(&list, 3);

printList(list);

deleteN(&list, 1); //delete any position from list

printList(list);

return 0;

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

6.2 Write a program for stack using linked list for the following operations:

Push, Pop, Peek and IsEmpty.

/* * C Program to Implement a Stack using Linked List */

#include <stdio.h>

#include <stdlib.h>

struct node

int info;

struct node *ptr;

}*top,*top1,*temp;

int topelement();

void push(int data);

void pop();

void empty();

void display();

void destroy();

void stack_count();

void create();

int count = 0;

void main()

int no, ch, e;

printf("\n 1 - Push");

printf("\n 2 - Pop");

printf("\n 3 - Top");
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

printf("\n 4 - Empty");

printf("\n 5 - Exit");

printf("\n 6 - Dipslay");

printf("\n 7 - Stack Count");

printf("\n 8 - Destroy stack");

create();

while (1)

printf("\n Enter choice : ");

scanf("%d", &ch);

switch (ch)

case 1:

printf("Enter data : ");

scanf("%d", &no);

push(no);

break;

case 2:

pop();

break;

case 3:

if (top == NULL)

printf("No elements in stack");

else

{
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

e = topelement();

printf("\n Top element : %d", e);

break;

case 4:

empty();

break;

case 5:

exit(0);

case 6:

display();

break;

case 7:

stack_count();

break;

case 8:

destroy();

break;

default :

printf(" Wrong choice, Please enter correct choice ");

break;

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

/* Create empty stack */

void create()

top = NULL;

/* Count stack elements */

void stack_count()

printf("\n No. of elements in stack : %d", count);

/* Push data into stack */

void push(int data)

if (top == NULL)

top =(struct node *)malloc(1*sizeof(struct node));

top->ptr = NULL;

top->info = data;

else

temp =(struct node *)malloc(1*sizeof(struct node));

temp->ptr = top;

temp->info = data;

top = temp;
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

count++;

/* Display stack elements */

void display()

top1 = top;

if (top1 == NULL)

printf("Stack is empty");

return;

while (top1 != NULL)

printf("%d ", top1->info);

top1 = top1->ptr;

/* Pop Operation on stack */

void pop()

top1 = top;

if (top1 == NULL)
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

printf("\n Error : Trying to pop from empty stack");

return;

else

top1 = top1->ptr;

printf("\n Popped value : %d", top->info);

free(top);

top = top1;

count--;

/* Return top element */

int topelement()

return(top->info);

/* Check if stack is empty or not */

void empty()

if (top == NULL)

printf("\n Stack is empty");

else

printf("\n Stack is not empty with %d elements", count);

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

/* Destroy entire stack */

void destroy()

top1 = top;

while (top1 != NULL)

top1 = top->ptr;

free(top);

top = top1;

top1 = top1->ptr;

free(top1);

top = NULL;

printf("\n All stack elements destroyed");

count = 0;

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

6.3 Write a program for queue using linked list for the following operations:

Enqueue, Dequeue, IsEmpty

#include <stdio.h>

#include <stdlib.h>

// Structure to create a node with data and next pointer

struct node {

int data;

struct node *next;

};

struct node *front = NULL;

struct node *rear = NULL;

// Enqueue() operation on a queue

void enqueue(int value) {

struct node *ptr;

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

ptr->data = value;

ptr->next = NULL;

if ((front == NULL) && (rear == NULL)) {

front = rear = ptr;

} else {

rear->next = ptr;

rear = ptr;

printf("Node is Inserted\n\n");

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

// Dequeue() operation on a queue

int dequeue() {

if (front == NULL) {

printf("\nUnderflow\n");

return -1;

} else {

struct node *temp = front;

int temp_data = front->data;

front = front->next;

free(temp);

return temp_data;

// Display all elements of queue

void display() {

struct node *temp;

if ((front == NULL) && (rear == NULL)) {

printf("\nQueue is Empty\n");

} else {

printf("The queue is \n");

temp = front;

while (temp) {

printf("%d--->", temp->data);

temp = temp->next;

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

printf("NULL\n\n");

int main() {

int choice, value;

printf("\nImplementation of Queue using Linked List\n");

while (choice != 4) {

printf("1.Enqueue\n2.Dequeue\n3.Display\n4.Exit\n");

printf("\nEnter your choice : ");

scanf("%d", &choice);

switch (choice) {

case 1:

printf("\nEnter the value to insert: ");

scanf("%d", &value);

enqueue(value);

break;

case 2:

printf("Popped element is :%d\n", dequeue());

break;

case 3:

display();

break;

case 4:

exit(0);

break;
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

default:

printf("\nWrong Choice\n");

return 0;}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

Practical 7
7.1 Write a program to implement doubly linked list for the following
operations:
1. Insert a new node after the desired node
2. Delete the desired node
3. Display the nodes of doubly linked list
4. Count the nodes of doubly linked list

#include<stdio.h>

#include<stdlib.h>

typedef struct node

int data;

struct node *prev, *next;

}node;

node *head, *tail;

void insertAfter(int num)

node *temp, *newnode;

temp = head;

while(temp->data != num)

temp = temp->next;

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

if(temp == NULL)

printf("No such node exists in the list.");

return;

newnode = (node*)malloc(sizeof(node));

printf("Enter the data for new node: ");

scanf("%d", &newnode->data);

newnode->next = temp->next;

newnode->prev = temp;

temp->next = newnode;

if(head == NULL)

head = newnode;

void delete(int num)

node *temp, *oldnode;

temp = head;

while(temp->data != num)

temp = temp->next;

if(temp == NULL)

printf("No such node exists in the list.");

 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

return;

if(temp->next == NULL)

temp->prev->next = NULL;

return;

if(temp == head)

temp->next->prev = NULL;

head = temp->next;

return;

temp->prev->next = temp->next;

temp->next->prev = temp->prev;

void display()

node *temp;

temp = head;

printf("The doubly linked list is: ");

while(temp != NULL)

printf("%d ", temp->data);

temp = temp->next;
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

printf("\n");

void search(int num)

node *temp;

temp = head;

while(temp->data != num)

temp = temp->next;

if(temp == NULL)

printf("No such node exists in the list.");

return;

printf("%d is found in the list.\n", num);

void main()

int choice, num;

head = NULL;

tail = NULL;

printf("Enter the data for first node: ");

scanf("%d", &num);
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

insertAfter(num);

while(1)

printf("Enter the choice:\n");

printf("1. Insert a new node after the desired node.\n");

printf("2. Delete the desired node.\n");

printf("3. Display the nodes of doubly linked list.\n");

printf("4. Search for a given node.\n");

printf("5. Exit\n");

scanf("%d", &choice);

switch(choice)

case 1: printf("Enter the data for new node: ");

scanf("%d", &num);

insertAfter(num);

break;

case 2: printf("Enter the data for the node to be deleted: ");

scanf("%d", &num);

delete(num);

break;

case 3: display();

break;

case 4: printf("Enter the data to be searched: ");

scanf("%d", &num);

search(num);
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

break;

case 5: exit(0);

break;

default: printf("Invalid choice\n");

break;

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

7.2 Write a program in c language to implement circular doubly linked list

for the following operations:

1. Insert a new node after the desired node

2. Delete the desired node

3. Display the nodes of doubly linked list

4. Search a node whether it is present in the list or not

5. Count the total number of nodes present in the list

#include<stdio.h>

#include<stdlib.h>

struct Node

int data;

struct Node *llink;

struct Node *rlink;

};

typedef struct Node *List;

List insert(List head,int item);

List delete(List head,int item);

void display(List head);

List search(List head,int item);

int count(List head);

int main(void)

int choice,ele,item;
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

List head=NULL;

while(1)

printf("\n1.Insert\n2.Delete\n3.Display\n4.Search\n5.Count\n6.Exit\n");

printf("Enter your choice:");

scanf("%d",&choice);

switch(choice)

case 1: printf("Enter the element to be inserted:");

scanf("%d",&ele);

head=insert(head,ele);

break;

case 2: printf("Enter the element to be deleted:");

scanf("%d",&ele);

head=delete(head,ele);

break;

case 3: printf("The list is:");

display(head);

break;

case 4: printf("Enter the element to be searched:");

scanf("%d",&ele);

head=search(head,ele);

break;

case 5: printf("Total number of nodes in the list:");

item=count(head);
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

printf("%d",item);

break;

case 6: exit(0);

default: printf("\nInvalid choice");

return 0;

List insert(List head,int item)

List p,temp;

temp=(List)malloc(sizeof(struct Node));

temp->data=item;

temp->rlink=NULL;

if(head==NULL)

temp->llink=NULL;

head=temp;

else

p=head;

while(p->rlink!=NULL)

p=p->rlink;

p->rlink=temp;
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

temp->llink=p;

return head;

List delete(List head,int item)

List p;

if(head==NULL)

printf("\nList is empty");

return head;

p=head;

while(p!=NULL && p->data!=item)

p=p->rlink;

if(p==NULL)

printf("\n%d not found",item);

return head;

if(head==p)

head=p->rlink;

if(p->llink!=NULL)

p->llink->rlink=p->rlink;

if(p->rlink!=NULL)
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

p->rlink->llink=p->llink;

free(p);

return head;

void display(List head)

List p;

if(head==NULL)

printf("\nList is empty");

return;

p=head;

while(p!=NULL)

printf("%d\t",p->data);

p=p->rlink;

List search(List head,int item)

List p;

int pos=0;

if(head==NULL)

{
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

printf("\nList is empty");

return head;

p=head;

while(p!=NULL)

pos++;

if(p->data==item)

printf("\n%d found at position %d",item,pos);

return head;

p=p->rlink;

printf("\n%d not found",item);

return head;

int count(List head)

List p;

int count=0;

if(head==NULL)

printf("\nList is empty");

return count;
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

p=head;

while(p!=NULL)

count++;

p=p->rlink;

return count;

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

Practical 8
8.1 Write a program to construct a binary search tree.

#include <stdio.h>

#include <stdlib.h>

struct node

int key;

struct node *left, *right;

};

// A utility function to create a new BST node

struct node *newNode(int item)

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

temp->key = item;

temp->left = temp->right = NULL;

return temp;

// A utility function to do inorder traversal of BST

void inorder(struct node *root)

if (root != NULL)

inorder(root->left);

printf("%d \n", root->key);

 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

inorder(root->right);

/* A utility function to insert a new node with given key in BST */

struct node* insert(struct node* node, int key)

/* If the tree is empty, return a new node */

if (node == NULL) return newNode(key);

/* Otherwise, recur down the tree */

if (key < node->key)

node->left = insert(node->left, key);

else if (key > node->key)

node->right = insert(node->right, key);

/* return the (unchanged) node pointer */

return node;

// Driver Program to test above functions

int main()

{
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

/* Let us create following BST

50

/ \

30 70

/ \ / \

20 40 60 80 */

struct node *root = NULL;

root = insert(root, 50);

insert(root, 30);

insert(root, 20);

insert(root, 40);

insert(root, 70);

insert(root, 60);

insert(root, 80);

// print inoder traversal of the BST

inorder(root);

return 0;

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

8.2 Write a program in c language to traverse binary search tree.

#include <stdio.h>

#include <stdlib.h>

struct node

int key;

struct node *left, *right;

};

struct node *newNode(int item)

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

temp->key = item;

temp->left = temp->right = NULL;

return temp;

void inorder(struct node *root)

if (root != NULL)

inorder(root->left);

printf("%d \n", root->key);

inorder(root->right);

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

struct node* insert(struct node* node, int key)

if (node == NULL) return newNode(key);

if (key < node->key)

node->left = insert(node->left, key);

else if (key > node->key)

node->right = insert(node->right, key);

return node;

int main()

struct node *root = NULL;

root = insert(root, 50);

insert(root, 30);

insert(root, 20);

insert(root, 40);

insert(root, 70);

insert(root, 60);

insert(root, 80);

inorder(root);

return 0;

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

Practical 9
9.1 Write a program to demonstrate DFS and BFS.

#include<stdio.h>

#include<stdlib.h>

// A structure to represent a queue

struct Queue

int front, rear, size;

unsigned capacity;

int* array;

};

// A structure to represent a stack

struct Stack

int top;

unsigned capacity;

int* array;

};

// A structure to represent a graph. A graph

// is represented as an array of adjacency

// lists. Size of array will be V (number of

// vertices in graph)

struct Graph

{
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

int V;

struct AdjList* array;

};

// A structure to represent an adjacency list

struct AdjList

int dest;

struct AdjList* next;

};

// A structure to represent a node in adjacency list

struct AdjListNode

int dest;

struct AdjListNode* next;

};

// Function to create a stack of given capacity.

// It initializes size of stack as 0

struct Stack* createStack(unsigned capacity)

struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));

stack->top = -1;

stack->capacity = capacity;

stack->array = (int*) malloc(stack->capacity * sizeof(int));

return stack;

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

// Stack is full when top is equal to the last index

int isFull(struct Stack* stack)

return (stack->top == stack->capacity - 1);

// Stack is empty when top is equal to -1

int isEmpty(struct Stack* stack)

return (stack->top == -1);

// Function to add an item to stack. It increases

// top by 1

void push(struct Stack* stack, int item)

if (isFull(stack))

return;

stack->array[++stack->top] = item;

// Function to remove an item from stack. It

// decreases top by 1

int pop(struct Stack* stack)

if (isEmpty(stack))

return INT_MIN;

return stack->array[stack->top--];
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

// Function to create a queue of given capacity.

// It initializes size of queue as 0

struct Queue* createQueue(unsigned capacity)

struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));

queue->front = queue->size = 0;

queue->rear = capacity - 1; // This is important, see the enqueue

queue->capacity = capacity;

queue->array = (int*) malloc(queue->capacity * sizeof(int));

return queue;

// Queue is full when size becomes equal to the

// capacity

int isFull(struct Queue* queue)

return (queue->size == queue->capacity);

// Queue is empty when size is 0

int isEmpty(struct Queue* queue)

return (queue->size == 0);

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

// Function to add an item to the queue.

// It changes rear and size

void enqueue(struct Queue* queue, int item)

if (isFull(queue))

return;

queue->array[queue->rear] = item;

queue->rear = (queue->rear + 1)%queue->capacity;

queue->size = queue->size + 1;

printf("%d enqueued to queue\n", item);

// Function to remove an item from queue.

// It changes front and size

int dequeue(struct Queue* queue)

if (isEmpty(queue))

return INT_MIN;

int item = queue->array[queue->front];

queue->front = (queue->front + 1)%queue->capacity;

queue->size = queue->size - 1;

return item;

// Function to get front of queue

int front(struct Queue* queue)

{
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

if (isEmpty(queue))

return INT_MIN;

return queue->array[queue->front];

// Function to get rear of queue

int rear(struct Queue* queue)

if (isEmpty(queue))

return INT_MIN;

return queue->array[queue->rear];

// A utility function to create a new adjacency list node

struct AdjListNode* newAdjListNode(int dest)

struct AdjListNode* newNode =

(struct AdjListNode*) malloc(sizeof(struct AdjListNode));

newNode->dest = dest;

newNode->next = NULL;

return newNode;

// A utility function that creates a graph of V vertices

struct Graph* createGraph(int V)

struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));

graph->V = V;
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

// Create an array of adjacency lists. Size of

// array will be V

graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));

// Initialize each adjacency list as empty by

// making head as NULL

int i;

for (i = 0; i < V; ++i)

graph->array[i].head = NULL;

return graph;

// Adds an edge to an undirected graph

void addEdge(struct Graph* graph, int src, int dest)

// Add an edge from src to dest. A new node is

// added to the adjacency list of src. The node

// is added at the begining

struct AdjListNode* newNode = newAdjListNode(dest);

newNode->next = graph->array[src].head;

graph->array[src].head = newNode;

// Since graph is undirected, add an edge from

// dest to src also

newNode = newAdjListNode(src);

newNode->next = graph->array[dest].head;
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

graph->array[dest].head = newNode;

// A utility function to print the adjacenncy list

// representation of graph

void printGraph(struct Graph* graph)

int v;

for (v = 0; v < graph->V; ++v)

struct AdjListNode* pCrawl = graph->array[v].head;

printf("\n Adjacency list of vertex %d\n head ", v);

while (pCrawl)

printf("-> %d", pCrawl->dest);

pCrawl = pCrawl->next;

printf("\n");

// A utility function to create a new adjacency list node

struct AdjListNode* newAdjListNode(int dest)

struct AdjListNode* newNode =

(struct AdjListNode*) malloc(sizeof(struct AdjListNode));

newNode->dest = dest;
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

newNode->next = NULL;

return newNode;

// Utility function to create a graph of given number of vertices

struct Graph* createGraph(int V)

struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));

graph->V = V;

// Create an array of adjacency lists. Size of

// array will be V

graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));

// Initialize each adjacency list as empty by

// making head as NULL

int i;

for (i = 0; i < V; ++i)

graph->array[i].head = NULL;

return graph;
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

9.2 Write a program in c language for giving a directed graph, and check whether the graph contains a
cycle or not. It should printntrue if the given graph contains at least one cycle, else it should print
false.

#include <stdio.h>

#include <stdbool.h>

#define V 4

bool isCyclicUtil(int v, bool visited[], bool *rs)

if(visited[v] == false)

visited[v] = true;

rs[v] = true;

for(int i=0; i<V; i++)

if(adj[v][i] && !visited[i])

if(isCyclicUtil(i, visited, rs))

return true;

else if(rs[i])

return true;

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

rs[v] = false;

return false;

int main()

int i,j;

bool visited[V];

bool rs[V];

int graph[V][V] = {{0, 1, 0, 1},

{1, 0, 1, 1},

{0, 1, 0, 1},

{1, 1, 1, 0}

};

for(i=0; i<V; i++)

visited[i] = false;

rs[i] = false;

for(i=0; i<V; i++)

if(isCyclicUtil(i, visited, rs))

return 1;

return 0;

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

Practical 10
Write a program in c language to implement following sorting techniques:

1. Selection Sort

2. Quick Sort

3. Insertion Sort.

4. Merge Sort

5. Heap Sort

1. Selection Sort

#include <stdio.h>

void swap(int *a, int *b)

int temp = *a;

*a = *b;

*b = temp;

void selectionSort(int arr[], int n)

int i, j, min_idx;

// One by one move boundary of unsorted subarray

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

{
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

// Find the minimum element in unsorted array

min_idx = i;

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

if (arr[j] < arr[min_idx])

min_idx = j;

// Swap the found minimum element with the first element

swap(&arr[min_idx], &arr[i]);

/* Function to print an array */

void printArray(int arr[], int size)

int i;

for (i=0; i < size; i++)

printf("%d ", arr[i]);

printf("n");

// Driver program to test above functions

int main()

int arr[] = {64, 25, 12, 22, 11};

int n = sizeof(arr)/sizeof(arr[0]);
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

selectionSort(arr, n);

printf("Sorted array: \n");

printArray(arr, n);

return 0;

2. Quick Sort
#include <stdio.h>

// A utility function to swap two elements

void swap(int* a, int* b)

int t = *a;

*a = *b;

*b = t;

/* This function takes last element as pivot, places

the pivot element at its correct position in sorted

array, and places all smaller (smaller than pivot)

to left of pivot and all greater elements to right

of pivot */

int partition (int arr[], int low, int high)

 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

int pivot = arr[high]; // pivot

int i = (low - 1); // Index of smaller element

for (int j = low; j <= high- 1; j++)

// If current element is smaller than the pivot

if (arr[j] < pivot)

i++; // increment index of smaller element

swap(&arr[i], &arr[j]);

swap(&arr[i + 1], &arr[high]);

return (i + 1);

/* The main function that implements QuickSort

arr[] --> Array to be sorted,

low --> Starting index,

high --> Ending index */

void quickSort(int arr[], int low, int high)

if (low < high)

{
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

/* pi is partitioning index, arr[p] is now

at right place */

int pi = partition(arr, low, high);

// Separately sort elements before

// partition and after partition

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

/* Function to print an array */

void printArray(int arr[], int size)

int i;

for (i=0; i < size; i++)

printf("%d ", arr[i]);

printf("n");

// Driver program to test above functions

int main()

int arr[] = {10, 7, 8, 9, 1, 5};

int n = sizeof(arr)/sizeof(arr[0]);
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

quickSort(arr, 0, n-1);

printf("Sorted array: n");

printArray(arr, n);

return 0;

3. Insertion Sort
#include<stdio.h>

void insertion_sort(int a[],int n)

int i,j,temp;

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

j=i-1;

temp=a[i];

while((temp<a[j])&&(j>=0))

a[j+1]=a[j];

j=j-1;

if(temp>a[j])

a[j+1]=temp;
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

else

j=j+1;

a[j]=temp;

void main()

int a[30],n,i;

printf("Enter the size of array: ");

scanf("%d",&n);

printf("Enter the array\n");

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

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

insertion_sort(a,n);

printf("Sorted array: \n");

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

printf("%d\t",a[i]);

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

4. Merge Sort
#include<stdio.h>

#define MAX 50

void merge(int arr[], int beg, int mid, int end);

void merge_sort(int arr[], int beg, int end);

int main()

int arr[MAX];

int n, i;

printf("\nEnter no of elements :");

scanf("%d", &n);

printf("\nEnter array elements :");

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

scanf("%d", &arr[i]);
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

merge_sort(arr, 0, n - 1);

printf("\nSorted array :");

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

printf("%d ", arr[i]);

return 0;

void merge_sort(int arr[], int beg, int end)

if (beg < end)

int mid = (beg + end) / 2;

merge_sort(arr, beg, mid);

merge_sort(arr, mid + 1, end);

merge(arr, beg, mid, end);

void merge(int arr[], int beg, int mid, int end)

int i = beg;

int j = mid + 1;
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

int k = beg;

int temp[MAX];

while ((i <= mid) && (j <= end))

if (arr[i] < arr[j])

temp[k] = arr[i];

k++;

i++;

else

temp[k] = arr[j];

k++;

j++;

while (i <= mid)

temp[k] = arr[i];

k++;

i++;

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

while (j <= end)

temp[k] = arr[j];

k++;

j++;

for (i = beg; i <= end; i++)

arr[i] = temp[i];

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

5. Heap Sort
#include<stdio.h>

void heapify(int arr[], int n, int i)

int largest = i; // Initialize largest as root

int l = 2*i + 1; // left = 2*i + 1

int r = 2*i + 2; // right = 2*i + 2

// If left child is larger than root

if (l < n && arr[l] > arr[largest])

largest = l;

// If right child is larger than largest so far

if (r < n && arr[r] > arr[largest])

largest = r;

// If largest is not root

if (largest != i)

swap(&arr[i], &arr[largest]);

// Recursively heapify the affected sub-tree

heapify(arr, n, largest);

}
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

// main function to do heap sort

void heapSort(int arr[], int n)

// Build heap (rearrange array)

for (int i = n / 2 - 1; i >= 0; i--)

heapify(arr, n, i);

// One by one extract an element from heap

for (int i=n-1; i>=0; i--)

// Move current root to end

swap(&arr[0], &arr[i]);

// call max heapify on the reduced heap

heapify(arr, i, 0);

/* A utility function to print array of size n */

void printArray(int arr[], int n)

for (int i=0; i<n; ++i)

printf("%d ",arr[i]);
 Madhuben and Bhanubhai Patel
Institute of Technology
New Vallabh Vidyanagar.
(Constituent College under CVM University)

printf("\n");

// Driver program

int main()

int arr[] = {12, 11, 13, 5, 6, 7};

int n = sizeof(arr)/sizeof(arr[0]);

heapSort(arr, n);

printf("Sorted array is \n");

printArray(arr, n);