DATA STRUCTURE AND ALGORITHM

(ECE181512)
LAB MANUAL
FOR B.E. E&T, V-SEMESTER

Prepared by:
Dr. Mukut Senapati
Asst. Prof., E&TE Dept.

DEPT. OF ELECTRONICS AND TELECOMMUNICATION ENGINEERING

ASSAM ENGINEERING COLLEGE
JALUKBARI-781013

DATA STRUCTURE AND ALGORITHM (ECE181512)

LAB MANUAL
FOR B.E. E&T, V-SEMESTER
 LIST OF EXPERIMENTS

EXP. EXPERIMENT TITLE

No.
1 Write a program to implement stack using array.
2 Write a program to implement Stack using linked list.
3 Write a program to implement a circular linked list.
4 Write a program to implement a Doubly Linked List.
5 Write a program to implement queue using array.
6 Write a program to implement queue using linked list.
7 Write a program to implement circular queue using linked list.
8 Write a program to implement a deque.
9 Write a program to implement priority queue using array.
10 Write a program to implement a linked list in descending order.
11 Write a program to insert an element in a sorted linked list.
12 Write a program to sort any six integers using linked list.
13 There are two linked lists A and B containing the following data:

A: 7, 5, 3, 1, 20
B: 6, 25, 32, 11, 9
Write a function to combine the two lists such that the resulting list contains nodes in the
following elements:
7, 6, 5, 25, 3, 32, 1, 11, 20, 9

14 Write a program to add two polynomial using linked list. You are not allowed to create any
additional node while writing the addition function.
15 Write a program to merge two sorted linked list, restricting common elements to occur only
once only.
16 Write a program to delete the minimum value from a linked list.
17 Write a program to remove a specified node from a given Doubly Linked List and insert it at the
end of the list.
18 Write a program to split a linked list in such a way that one list will have odd position elements
and other will have even position elements. Starting position is one.
19 Write a program to reverse a string using stack and implement the stack using linked list.
20 Write a program to generate a random matrix of 0’s and 1’s of order 4×4 and run the program
for four times and draw all the four graphs.
21 Write a program to sort some words using linked list.
22 Write a program to sort some three digits number by comparing the leftmost to rightmost digit.

Example: 358 264 187 (compare 8 of 358 with 4 of 264)

Step1 264 358 187
Similarly you compare all the digits and exchange the numbers.

23 Write a program to implement merge sort algorithm.

24 Write a program to implement insertion sort algorithm.
25 Write a program to implement bubble sort algorithm.
26 Write a program to implement selection sort algorithm.
27 Write a program to implement the Radix sort algorithm.
28 Write a program to implement the quick sort algorithm.
29 Write a program to implement linear search and binary search.
30 Write a program to find the inorder, preorder, and postorder traversal in a binary tree.
31 Write a program to implement a binary search tree.
32 Write a program to convert an infix expression to postfix expression.
33 Write a program to convert an infix expression to prefix expression.
34 Write a program to convert to evaluate a postfix expression.
35 Write a program using stack to convert decimal to binary, octal, and hexadecimal number
system.
36 Write a program to a check a given expression containing balanced parentheses or not.
37 Write a program to implement Breadth First Search (BFS) in a graph.
38 Write a program to implement Depth First Search (DFS) in a graph.
39 Write a program to implement linear probing to insert a set of integers using the hash function k
mod m in a hash table, where k is the key value and m is the size of hash table. (hash table size
should be at least the size of the array)
40 Write a program to implement quadratic probing to insert a set of integers using the hash function
k mod m in a hash table, where k is the key value and m is the size of hash table. (hash table size
should be at least the size of the array)
1. Write a program to implement stack using array.

Codes:

#include <stdio.h>
int stack[100],i,j,choice=0,n,top=-1;
void push();
void pop();
void show();
void main ()
{
printf("Enter the number of elements in the stack ");
scanf("%d",&n);
printf("*********Stack operations using array*********");
printf("\n----------------------------------------------\n");
while(choice != 4)
{
printf("Chose one from the below options...\n");
printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");
printf("\n Enter your choice \n");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
 show();
break;
}
case 4:
{
printf("Exiting....");
break;
}
default:
{
printf("Please Enter valid choice ");
}
};
}
}

void push ()
{
int val;
if (top == n )
printf("\n Overflow");
else
{
printf("Enter the value?");
scanf("%d",&val);
top = top +1;
stack[top] = val;
}
}

void pop ()
{
if(top == -1)
printf("Underflow");
else
 top = top -1;
}
void show()
{
for (i=top;i>=0;i--)
{
printf("%d\n",stack[i]);
}
if(top == -1)
{
printf("Stack is empty");
}
}
2. Write a program to implement Stack using linked list.

Codes:
#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");
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
{
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;
}
}
}
/* 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;
}
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)
{
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);
}
/* 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;
}

OutPut:
$ cc pgm2.c
$ a.out
1 - Push
2 - Pop
3 - Top
4 - Empty
5 - Exit
6 - Dipslay
7 - Stack Count
8 - Destroy stack
Enter choice : 1
Enter data : 56
Enter choice : 1
Enter data : 80
Enter choice : 2

Popped value : 80
Enter choice : 3
Top element : 56
Enter choice : 1
Enter data : 78

Enter choice : 1
Enter data : 90

Enter choice : 6
90 78 56
Enter choice : 7

No. of elements in stack : 3

Enter choice : 8

All stack elements destroyed

Enter choice : 4

Stack is empty
Enter choice : 5
3. Write a program to implement a circular linked list.

Codes:
#include<stdio.h>
#include<stdlib.h>
struct Node;
typedef struct Node * PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

struct Node
{
int e;
Position next;
};

void Insert(int x, List l, Position p)

{
Position TmpCell;
TmpCell = (struct Node*) malloc(sizeof(struct Node));
if(TmpCell == NULL)
printf("Memory out of space\n");
else
{
TmpCell->e = x;
TmpCell->next = p->next;
p->next = TmpCell;
}
}

int isLast(Position p, List l)

{
return (p->next == l);
}

Position FindPrevious(int x, List l)

{
Position p = l;
while(p->next != l && p->next->e != x)
p = p->next;
return p;
}

Position Find(int x, List l)

{
Position p = l->next;
while(p != l && p->e != x)
p = p->next;
return p;
}

void Delete(int x, List l)

{
Position p, TmpCell;
p = FindPrevious(x, l);
if(!isLast(p, l))
{
TmpCell = p->next;
p->next = TmpCell->next;
free(TmpCell);
}
else
printf("Element does not exist!!!\n");
}

void Display(List l)
{
printf("The list element are :: ");
Position p = l->next;
while(p != l)
{
printf("%d -> ", p->e);
p = p->next;
}
}

void main()
{
int x, pos, ch, i;
List l, l1;
l = (struct Node *) malloc(sizeof(struct Node));
l->next = l;
List p = l;
printf("CIRCULAR LINKED LIST IMPLEMENTATION OF LIST ADT\n\n");
do
{
printf("\n\n1. INSERT\t 2. DELETE\t 3. FIND\t 4. PRINT\t 5. QUIT\n\nEnter the choice
:: ");
scanf("%d", &ch);
switch(ch)
{
case 1:
p = l;
printf("Enter the element to be inserted :: ");
scanf("%d",&x);
printf("Enter the position of the element :: ");
scanf("%d",&pos);
for(i = 1; i < pos; i++)
{
p = p->next;
}
Insert(x,l,p);
 break;

case 2:
p = l;
printf("Enter the element to be deleted :: ");
scanf("%d",&x);
Delete(x,p);
break;

case 3:
p = l;
printf("Enter the element to be searched :: ");
scanf("%d",&x);
p = Find(x,p);
if(p == l)
printf("Element does not exist!!!\n");
else
printf("Element exist!!!\n");
break;

case 4:
Display(l);
break;
}
}while(ch<5);
return 0;
}

Output:
CIRCULAR LINKED LIST IMPLEMENTATION OF LIST ADT

1. INSERT 2. DELETE 3. FIND 4. PRINT 5. QUIT

Enter the choice :: 1

Enter the element to be inserted :: 10
Enter the position of the element :: 1

1. INSERT 2. DELETE 3. FIND 4. PRINT 5. QUIT

Enter the choice :: 1

Enter the element to be inserted :: 20
Enter the position of the element :: 2

1. INSERT 2. DELETE 3. FIND 4. PRINT 5. QUIT

Enter the choice :: 1

Enter the element to be inserted :: 30
Enter the position of the element :: 3

1. INSERT 2. DELETE 3. FIND 4. PRINT 5. QUIT

Enter the choice :: 4

The list element are :: 10 -> 20 -> 30 ->

1. INSERT 2. DELETE 3. FIND 4. PRINT 5. QUIT

Enter the choice :: 5

4. Write a program to implement a Doubly Linked List.

Codes:

#include <stdio.h>
//Represent a node of the doubly linked list
struct node{
int data;
struct node *previous;
struct node *next;
};
//Represent the head and tail of the doubly linked list
struct node *head, *tail = NULL;
//addNode() will add a node to the list
void addNode(int data) {
//Create a new node
struct node *newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = data;
//If list is empty
if(head == NULL) {
//Both head and tail will point to newNode
head = tail = newNode;
//head's previous will point to NULL
head->previous = NULL;
//tail's next will point to NULL, as it is the last node of the list
tail->next = NULL;
}
else {
//newNode will be added after tail such that tail's next will point to newNode
tail->next = newNode;
//newNode's previous will point to tail
newNode->previous = tail;
//newNode will become new tail
tail = newNode;
//As it is last node, tail's next will point to NULL
tail->next = NULL;
 }
}
//display() will print out the nodes of the list
void display() {
//Node current will point to head
struct node *current = head;
if(head == NULL) {
printf("List is empty\n");
return;
}
printf("Nodes of doubly linked list: \n");
while(current != NULL) {
//Prints each node by incrementing pointer.
printf("%d ", current->data);
current = current->next;
}
}

int main()
{
//Add nodes to the list
addNode(1);
addNode(2);
addNode(3);
addNode(4);
addNode(5);

//Displays the nodes present in the list

display();

return 0;
}
OutPut:
Nodes of doubly linked list:
12345
5. Write a program to implement queue using array.

Codes:

#include<stdio.h>
#define n 5
int main()
{
int queue[n],ch=1,front=0,rear=0,i,j=1,x=n;
printf("Queue using Array");
printf("\n1.Insertion \n2.Deletion \n3.Display \n4.Exit");
while(ch)
{
printf("\nEnter the Choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
if(rear==x)
printf("\n Queue is Full");
else
{
printf("\n Enter no %d:",j++);
scanf("%d",&queue[rear++]);
}
break;
case 2:
if(front==rear)
{
printf("\n Queue is empty");
}
else
{
printf("\n Deleted Element is %d",queue[front++]);
x++;
}
break;
case 3:
printf("\nQueue Elements are:\n ");
if(front==rear)
printf("\n Queue is Empty");
else
{
for(i=front; i<rear; i++)
{
printf("%d",queue[i]);
printf("\n");
}
break;
case 4:
exit(0);
 default:
printf("Wrong Choice: please see the options");
}
}
}
return 0;
}

OutPut:

Queue using Array

1.Insertion
2.Deletion
3.Display
4.Exit
Enter the Choice:1
Enter no 1:10
Enter the Choice:1
Enter no 2:54
Enter the Choice:1
Enter no 3:98
Enter the Choice:1
Enter no 4:234
Enter the Choice:3
Queue Elements are:
10
54
98
234
Enter the Choice:2
Deleted Element is 10
Enter the Choice:3
Queue Elements are:
54
98
234
Enter the Choice:4
6. Write a program to implement queue using linked list.

Codes:

// A C program to demonstrate linked list based

// implementation of queue
#include <stdio.h>
#include <stdlib.h>

// A linked list (LL) node to store a queue entry

struct QNode {
int key;
struct QNode* next;
};

// The queue, front stores the front node of LL and rear

// stores the last node of LL
struct Queue {
struct QNode *front, *rear;
};

// A utility function to create a new linked list node.

struct QNode* newNode(int k)
{
struct QNode* temp
= (struct QNode*)malloc(sizeof(struct QNode));
temp->key = k;
temp->next = NULL;
return temp;
}

// A utility function to create an empty queue

struct Queue* createQueue()
{
struct Queue* q
= (struct Queue*)malloc(sizeof(struct Queue));
q->front = q->rear = NULL;
return q;
}

// The function to add a key k to q

void enQueue(struct Queue* q, int k)
{
// Create a new LL node
struct QNode* temp = newNode(k);
 // If queue is empty, then new node is front and rear
// both
if (q->rear == NULL) {
q->front = q->rear = temp;
return;
}

// Add the new node at the end of queue and change rear
q->rear->next = temp;
q->rear = temp;
}

// Function to remove a key from given queue q

void deQueue(struct Queue* q)
{
// If queue is empty, return NULL.
if (q->front == NULL)
return;

// Store previous front and move front one node ahead

struct QNode* temp = q->front;

q->front = q->front->next;

// If front becomes NULL, then change rear also as NULL

if (q->front == NULL)
q->rear = NULL;

free(temp);
}

// Driver code
int main()
{
struct Queue* q = createQueue();
enQueue(q, 10);
enQueue(q, 20);
deQueue(q);
deQueue(q);
enQueue(q, 30);
enQueue(q, 40);
enQueue(q, 50);
deQueue(q);
printf("Queue Front : %d \n", ((q->front != NULL) ? (q->front)->key : -1));
printf("Queue Rear : %d", ((q->rear != NULL) ? (q->rear)->key : -1));
return 0;
}

Output

Queue Front : 40
Queue Rear : 50
7. Write a program to implement circular queue using linked list.

Codes:

/* C Program to implement queue using circular linked list*/

#include<stdio.h>
#include<stdlib.h>
struct node
{
int info;
struct node *link;
}*rear=NULL;

void insert(int item);

int del();
void display();
int isEmpty();
int peek();
int main()
{
int choice,item;
while(1)
{
printf("\n1.Insert\n");
printf("2.Delete\n");
printf("3.Peek\n");
printf("4.Display\n");
printf("5.Quit\n");
printf("\nEnter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
 printf("\nEnter the element for insertion : ");
scanf("%d",&item);
insert(item);
break;
case 2:
printf("\nDeleted element is %d\n",del());
break;
case 3:
printf("\nItem at the front of queue is %d\n",peek());
break;
case 4:
display();
break;
case 5:
exit(1);
default:
printf("\nWrong choice\n");
}/*End of switch*/
}/*End of while*/
}/*End of main()*/

void insert(int item)

{
struct node *tmp;
tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=item;
if(tmp==NULL)
{
printf("\nMemory not available\n");
return;
}

if( isEmpty() ) /*If queue is empty */

 {
rear=tmp;
tmp->link=rear;
}
else
{
tmp->link=rear->link;
rear->link=tmp;
rear=tmp;
}
}/*End of insert()*/

del()
{
int item;
struct node *tmp;
if( isEmpty() )
{
printf("\nQueue underflow\n");
exit(1);
}
if(rear->link==rear) /*If only one element*/
{
tmp=rear;
rear=NULL;
}
else
{
tmp=rear->link;
rear->link=rear->link->link;
}
item=tmp->info;
free(tmp);
 return item;
}/*End of del()*/

int peek()
{
if( isEmpty() )
{
printf("\nQueue underflow\n");
exit(1);
}
return rear->link->info;
}/* End of peek() */

int isEmpty()
{
if( rear == NULL )
return 1;
else
return 0;
}/*End of isEmpty()*/

void display()
{
struct node *p;
if(isEmpty())
{
printf("\nQueue is empty\n");
return;
}
printf("\nQueue is :\n");
p=rear->link;
do
 {
printf("%d ",p->info);
p=p->link;
}while(p!=rear->link);
printf("\n");
}/*End of display()*/

OutPut:

1.Insert
2.Delete
3.Peek
4.Display
5.Quit

Enter your choice : 1

Enter the element for insertion : 1

1.Insert
2.Delete
3.Peek
4.Display
5.Quit

Enter your choice : 1

Enter the element for insertion : 2

1.Insert
2.Delete
3.Peek
4.Display
5.Quit

Enter your choice : 1

Enter the element for insertion : 3

1.Insert
2.Delete
3.Peek
4.Display
5.Quit

Enter your choice : 4

Queue is :
123

1.Insert
2.Delete
3.Peek
4.Display
5.Quit

Enter your choice : 2

Deleted element is 1

1.Insert
2.Delete
3.Peek
4.Display
5.Quit
Enter your choice : 3

Item at the front of queue is 2

1.Insert
2.Delete
3.Peek
4.Display
5.Quit

Enter your choice : 2

Deleted element is 2

1.Insert
2.Delete
3.Peek
4.Display
5.Quit

Enter your choice : 4

Queue is :
3

1.Insert
2.Delete
3.Peek
4.Display
5.Quit

Enter your choice : 2

Deleted element is 3

1.Insert
2.Delete
3.Peek
4.Display
5.Quit

Enter your choice : 2

Queue underflow
8. Write a program to implement a deque.

Codes:
#include <stdio.h>
#define size 5
int deque[size];
int f = -1, r = -1;
// insert_front function will insert the value from the front
void insert_front(int x)
{
if((f==0 && r==size-1) || (f==r+1))
{
printf("Overflow");
}
else if((f==-1) && (r==-1))
{
f=r=0;
deque[f]=x;
}
else if(f==0)
{
f=size-1;
deque[f]=x;
}
else
{
f=f-1;
deque[f]=x;
}
}

// insert_rear function will insert the value from the rear

void insert_rear(int x)
{
if((f==0 && r==size-1) || (f==r+1))
{
 printf("Overflow");
}
else if((f==-1) && (r==-1))
{
r=0;
deque[r]=x;
}
else if(r==size-1)
{
r=0;
deque[r]=x;
}
else
{
r++;
deque[r]=x;
}

// display function prints all the value of deque.

void display()
{
int i=f;
printf("\nElements in a deque are: ");

while(i!=r)
{
printf("%d ",deque[i]);
i=(i+1)%size;
}
printf("%d",deque[r]);
}

// getfront function retrieves the first value of the deque.

void getfront()
{
if((f==-1) && (r==-1))
{
printf("Deque is empty");
}
else
{
printf("\nThe value of the element at front is: %d", deque[f]);
}

// getrear function retrieves the last value of the deque.

void getrear()
{
if((f==-1) && (r==-1))
{
printf("Deque is empty");
}
else
{
printf("\nThe value of the element at rear is %d", deque[r]);
}

// delete_front() function deletes the element from the front

void delete_front()
{
if((f==-1) && (r==-1))
{
printf("Deque is empty");
}
else if(f==r)
 {
printf("\nThe deleted element is %d", deque[f]);
f=-1;
r=-1;

}
else if(f==(size-1))
{
printf("\nThe deleted element is %d", deque[f]);
f=0;
}
else
{
printf("\nThe deleted element is %d", deque[f]);
f=f+1;
}
}

// delete_rear() function deletes the element from the rear

void delete_rear()
{
if((f==-1) && (r==-1))
{
printf("Deque is empty");
}
else if(f==r)
{
printf("\nThe deleted element is %d", deque[r]);
f=-1;
r=-1;

}
else if(r==0)
{
printf("\nThe deleted element is %d", deque[r]);
 r=size-1;
}
else
{
printf("\nThe deleted element is %d", deque[r]);
r=r-1;
}
}

int main()
{
insert_front(20);
insert_front(10);
insert_rear(30);
insert_rear(50);
insert_rear(80);
display(); // Calling the display function to retrieve the values of deque
getfront(); // Retrieve the value at front-end
getrear(); // Retrieve the value at rear-end
delete_front();
delete_rear();
display(); // calling display function to retrieve values after deletion
return 0;
}

OutPut:
9. Write a program to implement priority queue using array.

Codes:
/ C++ program for the above approach

#include <bits/stdc++.h>
using namespace std;

// Structure for the elements in the

// priority queue
struct item {
int value;
int priority;
};

// Store the element of a priority queue

item pr[100000];

// Pointer to the last index

int size = -1;

// Function to insert a new element

// into priority queue
void enqueue(int value, int priority)
{
// Increase the size
size++;

// Insert the element

pr[size].value = value;
pr[size].priority = priority;
}

// Function to check the top element

int peek()
{
 int highestPriority = INT_MIN;
int ind = -1;

// Check for the element with

// highest priority
for (int i = 0; i <= size; i++) {

// If priority is same choose

// the element with the
// highest value
if (highestPriority
== pr[i].priority
&& ind > -1
&& pr[ind].value
< pr[i].value) {
highestPriority = pr[i].priority;
ind = i;
}
else if (highestPriority
< pr[i].priority) {
highestPriority = pr[i].priority;
ind = i;
}
}

// Return position of the element

return ind;
}

// Function to remove the element with

// the highest priority
void dequeue()
{
// Find the position of the element
// with highest priority
 int ind = peek();

// Shift the element one index before

// from the position of the element
// with highest priority is found
for (int i = ind; i < size; i++) {
pr[i] = pr[i + 1];
}

// Decrease the size of the

// priority queue by one
size--;
}

// Driver Code
int main()
{
// Function Call to insert elements
// as per the priority
enqueue(10, 2);
enqueue(14, 4);
enqueue(16, 4);
enqueue(12, 3);

// Stores the top element

// at the moment
int ind = peek();

cout << pr[ind].value << endl;

// Dequeue the top element

dequeue();

// Check the top element

ind = peek();
 cout << pr[ind].value << endl;

// Dequeue the top element

dequeue();

// Check the top element

ind = peek();
cout << pr[ind].value << endl;

return 0;
}

Output
16
14
12
10. Write a program to implement a linked list in descending order.

Codes:

#include <stdio.h>
struct Node {
int data;
struct Node* next;
};
Node* insertNode(int key) {
Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
void tailRecRevese(Node* current, Node* previous, Node** head){
if (!current->next) {
*head = current;
current->next = previous;
return;
}
Node* next = current->next;
current->next = previous;
tailRecRevese(next, current, head);
}
void tailRecReveseLL(Node** head){
if (!head)
return;
tailRecRevese(*head, NULL, head);
}
void printLinkedList(Node* head){
while (head != NULL) {
 printf("%d ", head->data);
head = head->next;
}
printf("
");
}
int main(){
Node* head1 = insertNode(9);
head1->next = insertNode(32);
head1->next->next = insertNode(65);
head1->next->next->next = insertNode(10);
head1->next->next->next->next = insertNode(85);
printf("Linked list : \t");
printLinkedList(head1);
tailRecReveseLL(&head1);
printf("Reversed linked list : \t");
printLinkedList(head1);
return 0;
}

Output:
Linked list : 9 32 65 10 85
Reversed linked list : 85 10 65 32 9
11. Write a program to insert an element in a sorted linked list.

Codes:

/* Program to insert in a sorted list */

#include <stdio.h>
#include <stdlib.h>
/* Link list node */
struct Node {
int data;
struct Node* next;
};
/* function to insert a new_node
in a list. Note that this
function expects a pointer
to head_ref as this can modify the
head of the input linked
list (similar to push())*/
void sortedInsert(struct Node** head_ref,
struct Node* new_node)
{
struct Node* current;
/* Special case for the head end */
if (*head_ref == NULL
|| (*head_ref)->data
>= new_node->data) {
new_node->next = *head_ref;
*head_ref = new_node;
}
else {
/* Locate the node before
the point of insertion */
 current = *head_ref;
while (current->next != NULL
&& current->next->data < new_node->data) {
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}

/* BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert */

/* A utility function to create a new node */
struct Node* newNode(int new_data)
{
/* allocate node */
struct Node* new_node
= (struct Node*)malloc(
sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
new_node->next = NULL;
return new_node;
}
/* Function to print linked list */
void printList(struct Node* head)
{
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
}
/* Driver program to test count function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
struct Node* new_node = newNode(5);
sortedInsert(&head, new_node);
new_node = newNode(10);
sortedInsert(&head, new_node);
new_node = newNode(7);
sortedInsert(&head, new_node);
new_node = newNode(3);
sortedInsert(&head, new_node);
new_node = newNode(1);
sortedInsert(&head, new_node);
new_node = newNode(9);
sortedInsert(&head, new_node);
printf("\n Created Linked List\n");
printList(head);
return 0;
}

Output:
Created Linked List
1 3 5 7 9 10
12. Write a program to sort any six integers using linked list.

Codes:

// C program to implement Bubble Sort on singly linked list

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

/* structure for a node */

struct Node
{
int data;
struct Node *next;
};

/* Function to insert a node at the beginning of a linked list */

void insertAtTheBegin(struct Node **start_ref, int data);

/* Function to bubble sort the given linked list */

void bubbleSort(struct Node *start);

/* Function to swap data of two nodes a and b*/

void swap(struct Node *a, struct Node *b);

/* Function to print nodes in a given linked list */

void printList(struct Node *start);

int main()
{
int arr[] = {12, 56, 2, 11, 1, 90};
int list_size, i;
 /* start with empty linked list */
struct Node *start = NULL;

/* Create linked list from the array arr[].

Created linked list will be 1->11->2->56->12 */
for (i = 0; i< 6; i++)
insertAtTheBegin(&start, arr[i]);

/* print list before sorting */

printf("\n Linked list before sorting ");
printList(start);

/* sort the linked list */

bubbleSort(start);

/* print list after sorting */

printf("\n Linked list after sorting ");
printList(start);

getchar();
return 0;
}

/* Function to insert a node at the beginning of a linked list */

void insertAtTheBegin(struct Node **start_ref, int data)
{
struct Node *ptr1 = (struct Node*)malloc(sizeof(struct Node));
ptr1->data = data;
ptr1->next = *start_ref;
*start_ref = ptr1;
}

/* Function to print nodes in a given linked list */

void printList(struct Node *start)
{
struct Node *temp = start;
printf("\n");
while (temp!=NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
}

/* Bubble sort the given linked list */

void bubbleSort(struct Node *start)
{
int swapped, i;
struct Node *ptr1;
struct Node *lptr = NULL;

/* Checking for empty list */

if (start == NULL)
return;

do
{
swapped = 0;
ptr1 = start;

while (ptr1->next != lptr)

 {
if (ptr1->data > ptr1->next->data)
{
swap(ptr1, ptr1->next);
swapped = 1;
}
ptr1 = ptr1->next;
}
lptr = ptr1;
}
while (swapped);
}

/* function to swap data of two nodes a and b*/

void swap(struct Node *a, struct Node *b)
{
int temp = a->data;
a->data = b->data;
b->data = temp;
}

Output:

Linked list before sorting

90 1 11 2 56 12
Linked list after sorting
1 2 11 12 56 90
14. Write a program to add two polynomial using linked list. You are not allowed to create
any additional node while writing the addition function.

Codes:

// C++ program for addition of two polynomials

// using Linked Lists
#include <bits/stdc++.h>
using namespace std;

// Node structure containing power and coefficient of

// variable
struct Node {
int coeff;
int pow;
struct Node* next;
};

// Function to create new node

void create_node(int x, int y, struct Node** temp)
{
struct Node *r, *z;
z = *temp;
if (z == NULL) {
r = (struct Node*)malloc(sizeof(struct Node));
r->coeff = x;
r->pow = y;
*temp = r;
r->next = (struct Node*)malloc(sizeof(struct Node));
r = r->next;
r->next = NULL;
}
 else {
r->coeff = x;
r->pow = y;
r->next = (struct Node*)malloc(sizeof(struct Node));
r = r->next;
r->next = NULL;
}
}

// Function Adding two polynomial numbers

void polyadd(struct Node* poly1, struct Node* poly2,
struct Node* poly)
{
while (poly1->next && poly2->next) {
// If power of 1st polynomial is greater then 2nd,
// then store 1st as it is and move its pointer
if (poly1->pow > poly2->pow) {
poly->pow = poly1->pow;
poly->coeff = poly1->coeff;
poly1 = poly1->next;
}

// If power of 2nd polynomial is greater then 1st,

// then store 2nd as it is and move its pointer
else if (poly1->pow < poly2->pow) {
poly->pow = poly2->pow;
poly->coeff = poly2->coeff;
poly2 = poly2->next;
}

// If power of both polynomial numbers is same then

 // add their coefficients
else {
poly->pow = poly1->pow;
poly->coeff = poly1->coeff + poly2->coeff;
poly1 = poly1->next;
poly2 = poly2->next;
}

// Dynamically create new node

poly->next
= (struct Node*)malloc(sizeof(struct Node));
poly = poly->next;
poly->next = NULL;
}
while (poly1->next || poly2->next) {
if (poly1->next) {
poly->pow = poly1->pow;
poly->coeff = poly1->coeff;
poly1 = poly1->next;
}
if (poly2->next) {
poly->pow = poly2->pow;
poly->coeff = poly2->coeff;
poly2 = poly2->next;
}
poly->next
= (struct Node*)malloc(sizeof(struct Node));
poly = poly->next;
poly->next = NULL;
}
}
// Display Linked list
void show(struct Node* node)
{
while (node->next != NULL) {
printf("%dx^%d", node->coeff, node->pow);
node = node->next;
if (node->coeff >= 0) {
if (node->next != NULL)
printf("+");
}
}
}

// Driver code
int main()
{
struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL;

// Create first list of 5x^2 + 4x^1 + 2x^0

create_node(5, 2, &poly1);
create_node(4, 1, &poly1);
create_node(2, 0, &poly1);

// Create second list of -5x^1 - 5x^0

create_node(-5, 1, &poly2);
create_node(-5, 0, &poly2);

printf("1st Number: ");

show(poly1);
 printf("\n2nd Number: ");
show(poly2);

poly = (struct Node*)malloc(sizeof(struct Node));

// Function add two polynomial numbers

polyadd(poly1, poly2, poly);

// Display resultant List

printf("\nAdded polynomial: ");
show(poly);

return 0;
}

Output:
1st Number: 5x^2+4x^1+2x^0
2nd Number: -5x^1-5x^0
Added polynomial: 5x^2-1x^1-3x^0
15. Write a program to merge two sorted linked list, restricting common elements to occur
only once only.

Codes:

#include <bits/stdc++.h>
using namespace std;

/* Link list Node */

struct Node {
int key;
struct Node* next;
};

Node* newNode(int key){

Node* temp = new Node;
temp->key = key;
temp->next = NULL;
return temp;
}
int main() {
/* Let us create two sorted linked lists to test
the above functions. Created lists shall be
a: 5->10->15->40
b: 2->3->20 */
Node* a = newNode(5);
a->next = newNode(10);
a->next->next = newNode(15);
a->next->next->next = newNode(40);

Node* b = newNode(2);
b->next = newNode(3);
 b->next->next = newNode(20);
vector<int>v;
while(a!=NULL){
v.push_back(a->key);
a=a->next;
}
while(b!=NULL){
v.push_back(b->key);
b=b->next;
}
sort(v.begin(),v.end());
Node* result= newNode(-1);
Node* temp=result;
for(int i=0;i<v.size();i++){
result->next=newNode(v[i]);
result=result->next;
}
temp=temp->next;
cout<<"Resultant Merge Linked List Is :"<<endl;
while(temp!=NULL){
cout<<temp->key<<" ";
temp=temp->next;
}
return 0;
}

Output
Resultant Merge Linked List Is :
2 3 5 10 15 20 40
16. Write a program to delete the minimum value from a linked list.

Codes:

// C++ implementation of above approach

#include <bits/stdc++.h>
using namespace std;

// Structure of a linked list node

struct Node {
int data;
struct Node* next;
};

// Function to Delete nodes which have

// greater value node(s) on right side
void delNodes(struct Node* head)
{
struct Node* current = head;

// Initialize max
struct Node* maxnode = head;
struct Node* temp;

while (current != NULL && current->next != NULL) {

// If current is greater than max,

// then update max and move current
if (current->next->data <= maxnode->data) {
current = current->next;
maxnode = current;
}
 // If current is smaller than max, then delete current
else {
temp = current->next;
current->next = temp->next;
free(temp);
}
}
}

/* Utility function to insert a node at the beginning */

void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = new Node;
new_node->data = new_data;
new_node->next = *head_ref;
*head_ref = new_node;
}

/* Utility function to print a linked list */

void printList(struct Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}

/* Driver program to test above functions */

int main()
{
struct Node* head = NULL;

/* Create following linked list

12->15->10->11->5->6->2->3 */
push(&head, 3);
push(&head, 2);
push(&head, 6);
push(&head, 5);
push(&head, 11);
push(&head, 10);
push(&head, 15);
push(&head, 12);

printf("Given Linked List: ");

printList(head);

delNodes(head);

printf("\nModified Linked List: ");

printList(head);

return 0;
}

Output:
Given Linked List: 12 15 10 11 5 6 2 3

Modified Linked List: 12 10 5 2

17. Write a program to remove a specified node from a given Doubly Linked List and
insert it at the end of the list.

Codes:

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

/* a node of the doubly linked list */

struct Node {
int data;
struct Node* next;
struct Node* prev;
};

/* Function to delete a node in a Doubly Linked List.

head_ref --> pointer to head node pointer.
del --> pointer to node to be deleted. */
void deleteNode(struct Node** head_ref, struct Node* del)
{
/* base case */
if (*head_ref == NULL || del == NULL)
return;

/* If node to be deleted is head node */

if (*head_ref == del)
*head_ref = del->next;

/* Change next only if node to be deleted is NOT the last node */

if (del->next != NULL)
del->next->prev = del->prev;
 /* Change prev only if node to be deleted is NOT the first node */
if (del->prev != NULL)
del->prev->next = del->next;

/* Finally, free the memory occupied by del*/

free(del);
return;
}

/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginning of the Doubly Linked List */
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

/* put in the data */

new_node->data = new_data;

/* since we are adding at the beginning,

prev is always NULL */
new_node->prev = NULL;

/* link the old list of the new node */

new_node->next = (*head_ref);

/* change prev of head node to new node */

if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;

/* move the head to point to the new node */

 (*head_ref) = new_node;
}

/* Function to print nodes in a given doubly linked list

This function is same as printList() of singly linked list */
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}

/* Driver program to test above functions*/

int main()
{
/* Start with the empty list */
struct Node* head = NULL;

/* Let us create the doubly linked list 10<->8<->4<->2 */

push(&head, 2);
push(&head, 4);
push(&head, 8);
push(&head, 10);

printf("\n Original Linked list ");

printList(head);

/* delete nodes from the doubly linked list */

deleteNode(&head, head); /*delete first node*/
deleteNode(&head, head->next); /*delete middle node*/
 deleteNode(&head, head->next); /*delete last node*/

/* Modified linked list will be NULL<-8->NULL */

printf("\n Modified Linked list ");
printList(head);

getchar();
}

Output:
Original Linked list 10 8 4 2
Modified Linked list 8
18. Write a program to split a linked list in such a way that one list will have odd position
elements and other will have even position elements. Starting position is one.

Codes:

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

// A Linked List Node

struct Node
{
int data;
struct Node* next;
};

// Helper function to print a given linked list

void printList(struct Node* head)
{
struct Node* ptr = head;
while (ptr)
{
printf("%d —> ", ptr->data);
ptr = ptr->next;
}

printf("NULL\n");
}

// Helper function to insert a new node at the beginning of the linked list
void push(struct Node** head, int data)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
 newNode->data = data;
newNode->next = *head;
*head = newNode;
}

// Rearrange a given linked list by separating odd nodes

// from even ones and maintaining their relative order.
// This approach does not use any dummy node.
void rearrangeEvenOdd(struct Node** head)
{
struct Node *odd = NULL, *oddTail = NULL;
struct Node *even = NULL, *evenTail = NULL;

struct Node* curr = *head;

while (curr != NULL)

{
if (curr->data & 1) // current node is odd
{
// handle head for the first odd node
if (odd == NULL) {
odd = oddTail = curr;
}
else {
oddTail->next = curr;
oddTail = oddTail->next;
}
}
else // current node is even
{
// handle head for the first even node
 if (even == NULL) {
even = evenTail = curr;
}
else {
evenTail->next = curr;
evenTail = curr;
}
}
curr = curr->next;
}

// if the list contains at least one even node

if (even)
{
*head = even;
evenTail->next = odd;
}
// special case – list contains all odd nodes
else {
*head = odd;
}

// NULL to terminate the list; otherwise, it will go into an infinite loop

if (oddTail) {
oddTail->next = NULL;
}
}

int main(void)
{
// input keys
 int keys[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int n = sizeof(keys)/sizeof(keys[0]);

struct Node* head = NULL;

for (int i = n - 1; i >=0; i--) {
push(&head, keys[i]);
}

rearrangeEvenOdd(&head);
printList(head);

return 0;
}
Download Run Code

Output:

2 —> 4 —> 6 —> 8 —> 10 —> 1 —> 3 —> 5 —> 7 —> 9 —> NULL
19. Write a program to reverse a string using stack and implement the stack using linked
list.

Codes:

// C program to reverse a string using stack

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

// A structure to represent a stack

struct Stack {
int top;
unsigned capacity;
char* array;
};

// 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->capacity = capacity;
stack->top = -1;
stack->array
= (char*)malloc(stack->capacity * sizeof(char));
return stack;
}

// 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, char item)
{
if (isFull(stack))
return;
stack->array[++stack->top] = item;
}

// Function to remove an item from stack.

// It decreases top by 1
char pop(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top--];
}

// A stack based function to reverse a string

void reverse(char str[])
{
// Create a stack of capacity
// equal to length of string
int n = strlen(str);
struct Stack* stack = createStack(n);

// Push all characters of string to stack

int i;
for (i = 0; i < n; i++)
push(stack, str[i]);

// Pop all characters of string and

// put them back to str
for (i = 0; i < n; i++)
str[i] = pop(stack);
}

// Driver program to test above functions

int main()
{
char str[] = "GeeksQuiz";

reverse(str);
printf("Reversed string is %s", str);

return 0;
}

Output
Reversed string is ziuQskeeG
20. Write a program to generate a random matrix of 0’s and 1’s of order 4×4 and run the
program for four times and draw all the four graphs.

Codes:

// C++ implementation of the approach

#include <bits/stdc++.h>
using namespace std;

// Function to return the next random number

int getNum(vector<int>& v)
{

// Size of the vector

int n = v.size();

// Generate a random number

srand(time(NULL));

// Make sure the number is within

// the index range
int index = rand() % n;

// Get random number from the vector

int num = v[index];

// Remove the number from the vector

swap(v[index], v[n - 1]);
v.pop_back();

// Return the removed number

return num;
}

// Function to generate n non-repeating random numbers

void generateRandom(int n)
{
vector<int> v(n);

// Fill the vector with the values

// 1, 2, 3, ..., n
for (int i = 0; i < n; i++)
v[i] = i + 1;

// While vector has elements

// get a random number from the vector and print it
while (v.size()) {
cout << getNum(v) << " ";
}
}

// Driver code
int main()
{
int n = 8;
generateRandom(n);

return 0;
}

Output:
34586217
23. Write a program to implement merge sort algorithm.

Codes:

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

// Merges two subarrays of arr[].

// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

/* create temp arrays */

int L[n1], R[n2];

/* Copy data to temp arrays L[] and R[] */

for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];

/* Merge the temp arrays back into arr[l..r]*/

i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
 arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}

/* Copy the remaining elements of L[], if there

are any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

/* Copy the remaining elements of R[], if there

are any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

/* l is for left index and r is right index of the

sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
 if (l < r) {
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l + (r - l) / 2;

// Sort first and second halves

mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

merge(arr, l, m, r);
}
}

/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}

/* Driver code */
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);

printf("Given array is \n");

printArray(arr, arr_size);
 mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is \n");

printArray(arr, arr_size);
return 0;
}

Output:
Given array is
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13
24. Write a program to implement insertion sort algorithm.

Codes:

#include <math.h>
#include <stdio.h>

/* Function to sort an array using insertion sort*/

void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;

/* Move elements of arr[0..i-1], that are

greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

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

void printArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
 printf("\n");
}

/* Driver program to test insertion sort */

int main()
{
int arr[] = { 12, 11, 13, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);

insertionSort(arr, n);
printArray(arr, n);

return 0;
}

Output:
5 6 11 12 13
25. Write a program to implement bubble sort algorithm.

Codes:

#include <stdio.h>

void swap(int* xp, int* yp)

{
int temp = *xp;
*xp = *yp;
*yp = temp;
}

// A function to implement bubble sort

void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n - 1; i++)

// Last i elements are already in place

for (j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1])
swap(&arr[j], &arr[j + 1]);
}

/* 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[] = { 5, 1, 4, 2, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}

Output:
Sorted array:
12458
26. Write a program to implement selection sort algorithm.

Codes:

#include <stdio.h>

void swap(int *xp, int *yp)

{
int temp = *xp;
*xp = *yp;
*yp = 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++)
{
// 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

if(min_idx != i)
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]);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}

Output
Sorted array:
11 12 22 25 64
27. Write a program to implement the Radix sort algorithm.

Codes:

#include <iostream>
using namespace std;

// A utility function to get maximum value in arr[]

int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}

// A function to do counting sort of arr[] according to

// the digit represented by exp.
void countSort(int arr[], int n, int exp)
{
int output[n]; // output array
int i, count[10] = { 0 };

// Store count of occurrences in count[]

for (i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;

// Change count[i] so that count[i] now contains actual

// position of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];
 // Build the output array
for (i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}

// Copy the output array to arr[], so that arr[] now

// contains sorted numbers according to current digit
for (i = 0; i < n; i++)
arr[i] = output[i];
}

// The main function to that sorts arr[] of size n using

// Radix Sort
void radixsort(int arr[], int n)
{
// Find the maximum number to know number of digits
int m = getMax(arr, n);

// Do counting sort for every digit. Note that instead

// of passing digit number, exp is passed. exp is 10^i
// where i is current digit number
for (int exp = 1; m / exp > 0; exp *= 10)
countSort(arr, n, exp);
}

// A utility function to print an array

void print(int arr[], int n)
{
for (int i = 0; i < n; i++)
 cout << arr[i] << " ";
}

// Driver Code
int main()
{
int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 };
int n = sizeof(arr) / sizeof(arr[0]);

// Function Call
radixsort(arr, n);
print(arr, n);
return 0;
}

Output
2 24 45 66 75 90 170 802
28. Write a program to implement the quick sort algorithm.

Codes:

#include <stdio.h>

// Function to swap two elements

void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}

// Partition the array using the last element as the pivot

int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);

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

if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

// Function to implement Quick Sort

void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
 quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

// Function to print the array

void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

// Driver program
int main() {
int arr[] = { 10, 7, 8, 9, 1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}

Output
Sorted array:
1 5 7 8 9 10
29. Write a program to implement linear search and binary search.

Codes:

#include <stdio.h>

int search(int arr[], int N, int x)

{
int i;
for (i = 0; i < N; i++)
if (arr[i] == x)
return i;
return -1;
}

// Driver code
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int N = sizeof(arr) / sizeof(arr[0]);

// Function call
int result = search(arr, N, x);
(result == -1)
? printf("Element is not present in array")
: printf("Element is present at index %d", result);
return 0;
}

Output
Element is present at index 3
30. Write a program to find the inorder, preorder, and postorder traversal in a binary tree.

Codes:

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

/* A binary tree node has data, pointer to left child

and a pointer to right child */
struct node {
int data;
struct node* left;
struct node* right;
};

/* Helper function that allocates a new node with the

given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node
= (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return (node);
}

/* Given a binary tree, print its nodes in inorder*/

void printInorder(struct node* node)
{
if (node == NULL)
 return;

/* first recur on left child */

printInorder(node->left);

/* then print the data of node */

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

/* now recur on right child */

printInorder(node->right);
}

/* Driver code*/
int main()
{
struct node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

// Function call
printf("\nInorder traversal of binary tree is \n");
printInorder(root);
getchar();
return 0;
}

Output
Inorder traversal of binary tree is
42513
31. Write a program to implement a binary search tree.

Codes:

#include <iostream>
using namespace std;
struct Node {
int data;
Node *left;
Node *right;
};
Node* create(int item)
{
Node* node = new Node;
node->data = item;
node->left = node->right = NULL;
return node;
}
/*Inorder traversal of the tree formed*/
void inorder(Node *root)
{
if (root == NULL)
return;
inorder(root->left); //traverse left subtree
cout<< root->data << " "; //traverse root node
inorder(root->right); //traverse right subtree
}
Node* findMinimum(Node* cur) /*To find the inorder successor*/
{
while(cur->left != NULL) {
cur = cur->left;
}
 return cur;
}
Node* insertion(Node* root, int item) /*Insert a node*/
{
if (root == NULL)
return create(item); /*return new node if tree is empty*/
if (item < root->data)
root->left = insertion(root->left, item);
else
root->right = insertion(root->right, item);
return root;
}
void search(Node* &cur, int item, Node* &parent)
{
while (cur != NULL && cur->data != item)
{
parent = cur;
if (item < cur->data)
cur = cur->left;
else
cur = cur->right;
}
}
void deletion(Node*& root, int item) /*function to delete a node*/
{
Node* parent = NULL;
Node* cur = root;
search(cur, item, parent); /*find the node to be deleted*/
if (cur == NULL)
return;
if (cur->left == NULL && cur->right == NULL) /*When node has no children*/
{
if (cur != root)
{
if (parent->left == cur)
parent->left = NULL;
else
parent->right = NULL;
}
else
root = NULL;
free(cur);
}
else if (cur->left && cur->right)
{
Node* succ = findMinimum(cur->right);
int val = succ->data;
deletion(root, succ->data);
cur->data = val;
}
else
{
Node* child = (cur->left)? cur->left: cur->right;
if (cur != root)
{
if (cur == parent->left)
parent->left = child;
else
parent->right = child;
}
else
root = child;
 free(cur);
}
}
int main()
{
Node* root = NULL;
root = insertion(root, 45);
root = insertion(root, 30);
root = insertion(root, 50);
root = insertion(root, 25);
root = insertion(root, 35);
root = insertion(root, 45);
root = insertion(root, 60);
root = insertion(root, 4);
printf("The inorder traversal of the given binary tree is - \n");
inorder(root);
deletion(root, 25);
printf("\nAfter deleting node 25, the inorder traversal of the given binary tree is - \n");
inorder(root);
insertion(root, 2);
printf("\nAfter inserting node 2, the inorder traversal of the given binary tree is - \n");
inorder(root);
return 0;
}

Output
After the execution of the above code, the output will be –
32. Write a program to convert an infix expression to postfix expression.

Codes:

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

#define MAX_EXPR_SIZE 100

// Function to return precedence of operators

int precedence(char operator)
{
switch (operator) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
default:
return -1;
}
}

// Function to check if the scanned character

// is an operator
int isOperator(char ch)
{
return (ch == '+' || ch == '-' || ch == '*' || ch == '/'
 || ch == '^');
}

// Main functio to convert infix expression

// to postfix expression
char* infixToPostfix(char* infix)
{
int i, j;
int len = strlen(infix);
char* postfix = (char*)malloc(sizeof(char) * (len + 2));
char stack[MAX_EXPR_SIZE];
int top = -1;

for (i = 0, j = 0; i < len; i++) {

if (infix[i] == ' ' || infix[i] == '\t')
continue;

// If the scanned character is operand

// add it to the postfix expression
if (isalnum(infix[i])) {
postfix[j++] = infix[i];
}

// if the scanned character is '('

// push it in the stack
else if (infix[i] == '(') {
stack[++top] = infix[i];
}

// if the scanned character is ')'

// pop the stack and add it to the
 // output string until empty or '(' found
else if (infix[i] == ')') {
while (top > -1 && stack[top] != '(')
postfix[j++] = stack[top--];
if (top > -1 && stack[top] != '(')
return "Invalid Expression";
else
top--;
}

// If the scanned character is an operator

// push it in the stack
else if (isOperator(infix[i])) {
while (top > -1
&& precedence(stack[top])
>= precedence(infix[i]))
postfix[j++] = stack[top--];
stack[++top] = infix[i];
}
}

// Pop all remaining elements from the stack

while (top > -1) {
if (stack[top] == '(') {
return "Invalid Expression";
}
postfix[j++] = stack[top--];
}
postfix[j] = '\0';
return postfix;
}
// Driver code
int main()
{
char infix[MAX_EXPR_SIZE] = "a+b*(c^d-e)^(f+g*h)-i";

// Function call
char* postfix = infixToPostfix(infix);
printf("%s\n", postfix);
free(postfix);
return 0;
}

Output
abcd^e-fgh*+^*+i-
33. Write a program to convert an infix expression to prefix expression.

Codes:

#include <stdio.h>
#include <string.h>
#include <conio.h>

/* Global Declarations */
int pos = 0;
int top;
int length;
char symbol;
char temp;
char s[30];
char infix;
char prefix;

void push(char sym)

{
top = top + 1;
s[top] = sym;
}

char pop ()
{
char item;
item = s[top];
top = top-1;
return item;
}
int G (char symbol)
{
switch (symbol)
{
case '+':
case '-': return 2;
case '*':
case '/': return 4;
case '^':
case '$': return 5;
case '(': return 0;
case ')': return 9;
default : return 7;
}

}
int F (char symbol)
{
switch (symbol)
{
case '+':
case '-': return 1;
case '*':
case '/': return 3;
case '^':
case '$': return 6;
case '(': return 0;
case '#': return -1;
default : return 8;
}
}

void infix_prefix (char infix[], char prefix[])

{
int i, t1;
top = -1;
length = strlen(infix); expression */
length = length - 1;
pos = length;
t1 = length;

while ( length >= 0)

{
symbol = infix[length];
switch(symbol)
{

case ')': push(symbol);

break;

case '(':
temp = pop();
while( temp != ')')
{
prefix[pos] = temp;
pos--;
temp = pop();
}
if (temp != ')')
{
 prefix[pos--] = pop();
}
break;
case '+':
case '-':
case '*':
case '$':
case '/':
case '^': while(F(s[top]) >= G(symbol))
{
temp = pop();
prefix[pos] = temp;
pos--;
}
push(symbol);
break;
default:
prefix[pos--] = symbol;
break;
}
length--;
{
while(s[] != '#')
{
temp = pop();
prefix[pos--] = temp;
}
for (i = 0; i < t1; i++)
{
prefix[i] = prefix[i + pos + 1];
}
/* MAIN PROGRAM */
void main ()
{
clrscr();
printf("Enter the valid infix expression\n');
scanf("%s",infix);
infix_prefix(infix, prefix);
printf("The prefix expression \n");
printf("%s\n",prefix);
getch();
}

Output
*+ABC
34. Write a program to convert to evaluate a postfix expression.

Codes:

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.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));

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;
}

// 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;
case '-':
push(stack, val2 - val1);
break;
case '*':
push(stack, val2 * val1);
break;
case '/':
 push(stack, val2 / val1);
break;
}
}
}
return pop(stack);
}

// Driver code
int main()
{
char exp[] = "231*+9-";

// Function call
printf("postfix evaluation: %d", evaluatePostfix(exp));
return 0;
}

Output
postfix evaluation: -4
35. Write a program using stack to convert decimal to binary, octal, and hexadecimal
number system.

Codes:

#include<stdio.h>
void convert(int, int);

int main()
{
int num;
printf("Enter a positive decimal number : ");
scanf("%d", &num);
printf("\nBinary number :: ");
convert(num, 2);
printf("\n");
printf("\nOctal number :: ");
convert(num, 8);
printf("\n");
printf("\nHexadecimal number :: ");
convert(num, 16);
printf("\n");

return 0;
}/*End of main()*/

void convert (int num, int base)

{
int rem = num%base;

if(num==0)
return;
 convert(num/base, base);

if(rem < 10)

printf("%d", rem);
else
printf("%c", rem-10+'A' );
}/*End of convert()*/

OUTPUT:
//----------------------OUTPUT ::---------------------------------

//----------------------FIRST RUN ::------------------------------

Enter a positive decimal number : 15

Binary number :: 1111

Octal number :: 17

Hexadecimal number :: F

//-----------------------SECOND RUN ::----------------------------

Enter a positive decimal number : 157

Binary number :: 10011101

Octal number :: 235
Hexadecimal number :: 9D
36. Write a program to a check a given expression containing balanced parentheses or not.

Codes:

#include <stdio.h>
#include <stdlib.h>
#define bool int

// Structure of a stack node

struct sNode {
char data;
struct sNode* next;
};

// Function to push an item to stack

void push(struct sNode** top_ref, int new_data);

// Function to pop an item from stack

int pop(struct sNode** top_ref);

// Returns 1 if character1 and character2 are matching left

// and right Brackets
bool isMatchingPair(char character1, char character2)
{
if (character1 == '(' && character2 == ')')
return 1;
else if (character1 == '{' && character2 == '}')
return 1;
else if (character1 == '[' && character2 == ']')
return 1;
else
return 0;
}

// Return 1 if expression has balanced Brackets

bool areBracketsBalanced(char exp[])
{
int i = 0;

// Declare an empty character stack

struct sNode* stack = NULL;

// Traverse the given expression to check matching

// brackets
while (exp[i]) {
// If the exp[i] is a starting bracket then push
// it
if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
push(&stack, exp[i]);

// If exp[i] is an ending bracket then pop from

// stack and check if the popped bracket is a
// matching pair*/
if (exp[i] == '}' || exp[i] == ')'
|| exp[i] == ']') {

// If we see an ending bracket without a pair

// then return false
if (stack == NULL)
return 0;

// Pop the top element from stack, if it is not

// a pair bracket of character then there is a
 // mismatch.
// his happens for expressions like {(})
else if (!isMatchingPair(pop(&stack), exp[i]))
return 0;
}
i++;
}

// If there is something left in expression then there

// is a starting bracket without a closing
// bracket
if (stack == NULL)
return 1; // balanced
else
return 0; // not balanced
}

// Driver code
int main()
{
char exp[100] = "{()}[]";

// Function call
if (areBracketsBalanced(exp))
printf("Balanced \n");
else
printf("Not Balanced \n");
return 0;
}

// Function to push an item to stack

void push(struct sNode** top_ref, int new_data)
{
// allocate node
struct sNode* new_node
= (struct sNode*)malloc(sizeof(struct sNode));

if (new_node == NULL) {
printf("Stack overflow n");
getchar();
exit(0);
}

// put in the data

new_node->data = new_data;

// link the old list of the new node

new_node->next = (*top_ref);

// move the head to point to the new node

(*top_ref) = new_node;
}

// Function to pop an item from stack

int pop(struct sNode** top_ref)
{
char res;
struct sNode* top;

// If stack is empty then error

if (*top_ref == NULL) {
printf("Stack overflow n");
 getchar();
exit(0);
}
else {
top = *top_ref;
res = top->data;
*top_ref = top->next;
free(top);
return res;
}
}

Output
Balanced
37. Write a program to implement Breadth First Search (BFS) in a graph.

Codes:

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 50
// This struct represents a directed graph using
// adjacency list representation
typedef struct Graph_t {
int V; // No. of vertices
bool adj[MAX_VERTICES][MAX_VERTICES];
} Graph;
// Constructor
Graph* Graph_create(int V)
{
Graph* g = malloc(sizeof(Graph));
g->V = V;
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
g->adj[i][j] = false;
}
}
return g;
}
// Destructor
void Graph_destroy(Graph* g) { free(g); }
// function to add an edge to graph
void Graph_addEdge(Graph* g, int v, int w)
{
g->adj[v][w] = true; // Add w to v’s list.
}
// prints BFS traversal from a given source s
void Graph_BFS(Graph* g, int s)
{
// Mark all the vertices as not visited
bool visited[MAX_VERTICES];
for (int i = 0; i < g->V; i++) {
visited[i] = false;
}
// Create a queue for BFS
int queue[MAX_VERTICES];
int front = 0, rear = 0;
// Mark the current node as visited and enqueue it
visited[s] = true;
queue[rear++] = s;
while (front != rear) {
// Dequeue a vertex from queue and print it
s = queue[front++];
printf("%d ", s);
// Get all adjacent vertices of the dequeued
// vertex s. If a adjacent has not been visited,
// then mark it visited and enqueue it
for (int adjacent = 0; adjacent < g->V;
adjacent++) {
if (g->adj[s][adjacent] && !visited[adjacent]) {
visited[adjacent] = true;
queue[rear++] = adjacent;
}
}
}
}
// Driver program to test methods of graph struct
int main()
{
// Create a graph given in the above diagram
Graph* g = Graph_create(4);
Graph_addEdge(g, 0, 1);
Graph_addEdge(g, 0, 2);
Graph_addEdge(g, 1, 2);
Graph_addEdge(g, 2, 0);
Graph_addEdge(g, 2, 3);
Graph_addEdge(g, 3, 3);
printf("Following is Breadth First Traversal "
"(starting from vertex 2) \n");
Graph_BFS(g, 2);
Graph_destroy(g);
return 0;
}

Output
Following is Breadth First Traversal (starting from vertex 2)
2031
38. Write a program to implement Depth First Search (DFS) in a graph.

Codes:

#include <bits/stdc++.h>
using namespace std;
// Graph class represents a directed graph
// using adjacency list representation
class Graph {
public:
map<int, bool> visited;
map<int, list<int> > adj;
// function to add an edge to graph
void addEdge(int v, int w);
// DFS traversal of the vertices
// reachable from v
void DFS(int v);
};
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::DFS(int v)
{
// Mark the current node as visited and
// print it
visited[v] = true;
cout << v << " ";
// Recur for all the vertices adjacent
// to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
 if (!visited[*i])
DFS(*i);
}
// Driver's code
int main()
{
// Create a graph given in the above diagram
Graph g;
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Following is Depth First Traversal"
" (starting from vertex 2) \n";
// Function call
g.DFS(2);

return 0;
}

// improved by Vishnudev C

Output
Following is Depth First Traversal (starting from vertex 2)
2013
39. Write a program to implement linear probing to insert a set of integers using the hash
function k mod m in a hash table, where k is the key value and m is the size of hash table.
(hash table size should be at least the size of the array).

Codes:

#include <bits/stdc++.h>
using namespace std;
// template for generic type
template <typename K, typename V>
// Hashnode class
class HashNode {
public:
V value;
K key;
// Constructor of hashnode
HashNode(K key, V value)
{
this->value = value;
this->key = key;
}
};
// template for generic type
template <typename K, typename V>
// Our own Hashmap class
class HashMap {
// hash element array
HashNode<K, V>** arr;
int capacity;
// current size
int size;
// dummy node
HashNode<K, V>* dummy;
public:
HashMap()
{
// Initial capacity of hash array
capacity = 20;
size = 0;
arr = new HashNode<K, V>*[capacity];

// Initialise all elements of array as NULL

for (int i = 0; i < capacity; i++)
arr[i] = NULL;

// dummy node with value and key -1

dummy = new HashNode<K, V>(-1, -1);
}
// This implements hash function to find index
// for a key
int hashCode(K key)
{
return key % capacity;
}

// Function to add key value pair

void insertNode(K key, V value)
{
HashNode<K, V>* temp = new HashNode<K, V>(key, value);

// Apply hash function to find index for given key

int hashIndex = hashCode(key);
 // find next free space
while (arr[hashIndex] != NULL
&& arr[hashIndex]->key != key
&& arr[hashIndex]->key != -1) {
hashIndex++;
hashIndex %= capacity;
}
// if new node to be inserted
// increase the current size
if (arr[hashIndex] == NULL
|| arr[hashIndex]->key == -1)
size++;
arr[hashIndex] = temp;
}
// Function to delete a key value pair
V deleteNode(int key)
{
// Apply hash function
// to find index for given key
int hashIndex = hashCode(key);
// finding the node with given key
while (arr[hashIndex] != NULL) {
// if node found
if (arr[hashIndex]->key == key) {
HashNode<K, V>* temp = arr[hashIndex];
// Insert dummy node here for further use
arr[hashIndex] = dummy;
// Reduce size
size--;
return temp->value;
}
 hashIndex++;
hashIndex %= capacity;
}
// If not found return null
return NULL;
}
// Function to search the value for a given key
V get(int key)
{
// Apply hash function to find index for given key
int hashIndex = hashCode(key);
int counter = 0;
// finding the node with given key
while (arr[hashIndex] != NULL) { // int counter =0; // BUG!
if (counter++ > capacity) // to avoid infinite loop
return NULL;
// if node found return its value
if (arr[hashIndex]->key == key)
return arr[hashIndex]->value;
hashIndex++;
hashIndex %= capacity;
}
// If not found return null
return NULL;
}
// Return current size
int sizeofMap()
{
return size;
}
// Return true if size is 0
 bool isEmpty()
{
return size == 0;
}
// Function to display the stored key value pairs
void display()
{
for (int i = 0; i < capacity; i++) {
if (arr[i] != NULL && arr[i]->key != -1)
cout << "key = " << arr[i]->key
<< " value = "
<< arr[i]->value << endl;
}
}
};

// Driver method to test map class

int main()
{
HashMap<int, int>* h = new HashMap<int, int>;
h->insertNode(1, 1);
h->insertNode(2, 2);
h->insertNode(2, 3);
h->display();
cout << h->sizeofMap() << endl;
cout << h->deleteNode(2) << endl;
cout << h->sizeofMap() << endl;
cout << h->isEmpty() << endl;
cout << h->get(2);

return 0;
}

Output
key = 1 value = 1
key = 2 value = 3
2
3
1
0
0
40. Write a program to implement quadratic probing to insert a set of integers using the
hash function k mod m in a hash table, where k is the key value and m is the size of hash
table. (hash table size should be at least the size of the array)

Codes:

#include <bits/stdc++.h>
using namespace std;

// Function to print an array

void printArray(int arr[], int n)
{
// Iterating and printing the array
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
}

// Function to implement the

// quadratic probing
void hashing(int table[], int tsize, int arr[], int N)
{
// Iterating through the array
for (int i = 0; i < N; i++) {
// Computing the hash value
int hv = arr[i] % tsize;

// Insert in the table if there

// is no collision
if (table[hv] == -1)
table[hv] = arr[i];
else {
// If there is a collision
 // iterating through all
// possible quadratic values
for (int j = 0; j < tsize; j++) {
// Computing the new hash value
int t = (hv + j * j) % tsize;
if (table[t] == -1) {
// Break the loop after
// inserting the value
// in the table
table[t] = arr[i];
break;
}
}
}
}
printArray(table, N);
}

// Driver code
int main()
{
int arr[] = { 50, 700, 76, 85, 92, 73, 101 };
int N = 7;

// Size of the hash table

int L = 7;
int hash_table[7];

// Initializing the hash table

for (int i = 0; i < L; i++) {
hash_table[i] = -1;
 }

// Function call
hashing(hash_table, L, arr, N);
return 0;
}

// This code is contributed by gauravrajput1

Output
700 50 85 73 101 92 76