DSA final part B
1. Implement a menu driven Program in C for the following array operations. a) Creating an array of
N Integer Elements b) Display of array Elements with Suitable Headings c) Inserting an Element
(ELEM) at a given valid Position (POS) d) Deleting an Element at a given valid Position (POS) e) Exit.
#include<stdlib.h>
#include <stdio.h>
int arr[100];
int main() {
int i,n,ch,ele,pos;
while(1){
printf("[Link] Array\[Link] Array\[Link] element\[Link] element\[Link]\n");
printf("Enter choice: ");
scanf("%d",&ch);
if(ch==1){
printf("Enter the size: ");
scanf("%d",&n);
printf("Enter elements: ");
for(i=0;i<n;i++) scanf("%d",&arr[i]);
else if(ch==2){
if(n==0) printf("Empty!\n");
else{
printf("Array elements are: ");
for(i=0;i<n;i++) printf("%d ",arr[i]);
printf("\n");
else if(ch==3){
printf("Enter element and position respectively: ");
scanf("%d %d",&ele,&pos);
if(pos>=0 && pos<=n){
for(i=n;i>pos;i--) arr[i]=arr[i-1];
arr[pos]=ele;
n++;
else printf("Invalid position!\n");
else if(ch==4){
printf("Enter position to delete: ");
scanf("%d",&pos);
if(pos>=0 && pos<=n){
for(i=pos;i<n;i++) arr[i]=arr[i+1];
n--;
else printf("Invalid position!\n");
else{
printf("Exiting!\n");
break;
return 0;
2. Write a program to input the following details of n students using structure: roll no-int, name-
string, marks-int, grade-char. Print the names of the students with marks greater than or equal to
75.
#include<stdlib.h>
#include <stdio.h>
struct student{
int marks,roll;
char name[50],grade;
};
int main() {
struct student s[50];
int n,i;
printf("Enter the number of students: ");
scanf("%d",&n);
printf("Enter students details (name,roll,marks and grade respectively) : \n");
for(i=0;i<n;i++) scanf("%s %d %d %c",s[i].name,&s[i].roll,&s[i].marks,&s[i].grade);
printf("Students with marks greater than or equal to 75\n");
for(i=0;i<n;i++){
if(s[i].marks>=75){
printf("%s \n",s[i].name);
return 0;
3. Develop a menu driven Program in C for the following operations on STACK of Integers a) Push an
Element on to Stack. b) Pop an Element from Stack. c) Display the contents of Stack. d) Exit
#include<stdlib.h>
#include <stdio.h>
#define MAX 100
int stack[MAX], top=-1;
void push(int v){
if(top==MAX){
printf("Stack overflow!\n");
return;
else stack[++top]=v;
int pop(){
if(top==-1){
printf("Stack Underflow!\n");
return 0;
else return stack[top--];
void display(){ int i;
if(top==-1){
printf("Stack Underflow!\n");
return;
else{ printf("Stack elements are: \n");
for(i=0;i<=top;i++){
printf("%d ",stack[i]);
printf("\n");
int menu(){ int c;
printf("[Link]\[Link]\[Link]\[Link]\n");
printf("Enter your choice: ");
scanf("%d",&c);
return c;
int main() {
int ch,ele,e;
while(1){
ch=menu();
if(ch==1){
printf("Enter element to push: ");
scanf("%d",&ele);
push(ele);
else if(ch==2){ e=pop();
if(e) printf("%d popped.\n",e);}
else if(ch==3) display();
else break;
return 0;
4. Implement a Program in C for converting a valid Infix Expression to Postfix Expression. Program
should support both parenthesized and free parenthesized expressions with the operators: +, -, *, /,
% (modulus), and alphanumeric operands.
#include<stdlib.h>
#include <stdio.h>
#include<string.h>
#include<ctype.h>
#define MAX 100
char stack[MAX];
int top=-1;
void push(char c){
stack[++top]=c;
char pop(){
return stack[top--];
int priority(char c){
if(c=='+'||c=='-') return 1;
else if(c=='*'||c=='/'||c=='%') return 2;
return 0;
int main() {
char infix[100],postfix[100],ch,d;
int i=0,k=0;
printf("Enter the infix expression: ");
scanf("%s",infix);
while((ch=infix[i++])){
if(isalnum(ch)){
postfix[k++]=ch;
else if(ch=='(') push(ch);
else if(ch==')'){
while(stack[top]!='('){
postfix[k++]=pop();
d=pop();
else{
while(top!=-1 && priority(stack[top])>=priority(ch)){
postfix[k++]=pop();
push(ch);
while(top!=-1) postfix[k++]=pop();
postfix[k]='\0';
printf("Postfix expression is: %s",postfix);
return 0;
5. Evaluate the given valid single digit operand postfix Expression and display the result.
#include<stdlib.h>
#include <stdio.h>
#include<string.h>
#include<ctype.h>
#define MAX 100
int stack[MAX];
int top=-1;
void push(int c){
stack[++top]=c;
int pop(){
return stack[top--];
int main() {
char postfix[100],ch;
int i=0,k,b,a;
printf("Enter postfix expression: ");
scanf("%s",postfix);
while((ch=postfix[i++])){
if(isdigit(ch)) push(ch-'0');
else{
b=pop();
a=pop();
switch(ch){
case '+': push(a+b);
break;
case '-': push(a-b);
break;
case '*': push(a*b);
break;
case '/': push(a/b);
break;
case '%': push(a%b);
break;
k=pop();
printf("Value of given postfix expression is %d",k);
return 0;
6. Implement ordinary Queue data structure. a) Insert an Element. b) Delete an Element. c) Display
the contents of the Queue. d) Exit
#include<stdlib.h>
#include <stdio.h>
#include<string.h>
#include<ctype.h>
#define MAX 100
int queue[MAX],front=0,rear=-1;
void enqueue(int c){
if(rear==MAX-1){
printf("Queue overflow!\n");
return;
else queue[++rear]=c;
int dequeue(){
if(front>rear){
printf("Queue underflow!\n");
return 0;
return queue[front++];
void display(){
int i;
if(front>rear){
printf("Queue underflow!\n");
return;
else{ printf("Queue elements are: \n");
for(i=front;i<=rear;i++){
printf("%d ",queue[i]);
printf("\n");
int main() {
int ch,ele,e;
while(1){
printf("[Link]\[Link]\[Link]\[Link]\n");
printf("Enter a choice: ");
scanf("%d",&ch);
if(ch==1){
printf("Enter element: ");
scanf("%d",&ele);
enqueue(ele);
else if(ch==2){
e=dequeue();
if(e) printf("%d popped\n",e);
else if(ch==3) display();
else break;
}
return 0;
7. Implement circular Queue data structure. a) Insert an Element. b) Delete an Element. c) Display
the contents of the Queue. d) Exit
#include <stdio.h>
#define MAX 5
int q[MAX], front=-1, rear=-1;
void insert(){
int x;
if((rear+1)%MAX==front) printf("Queue Overflow\n");
else{
printf("Enter element: ");
scanf("%d",&x);
if(front==-1) front=0;
rear=(rear+1)%MAX;
q[rear]=x;
printf("Element inserted\n");
void delete(){
if(front==-1) printf("Queue Underflow\n");
else{
printf("Deleted element: %d\n",q[front]);
if(front==rear) front=rear=-1;
else front=(front+1)%MAX;
}
void display(){
int i;
if(front==-1) printf("Queue empty\n");
else{
printf("Queue contents:\n");
i=front;
while(1){
printf("%d ",q[i]);
if(i==rear) break;
i=(i+1)%MAX;
printf("\n");
int menu(){
int ch;
printf("\[Link] [Link] [Link] [Link]\n");
printf("Enter choice: ");
scanf("%d",&ch);
return ch;
int main(){
int ch;
while(1){
ch=menu();
if(ch==1) insert();
else if(ch==2) delete();
else if(ch==3) display();
else if(ch==4) break;
else printf("Invalid choice\n");
return 0;
8. Develop a menu driven Program in C for the following operations on Singly Linked List (SLL) having
an integer Data field. a) Insert node at Front. b) Delete at Rear End. c) Display the contents of SLL. d)
Searching for a node with given value.
#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node *next;
};
struct node* head=NULL;
struct node* createNode(int x){
struct node* n=(struct node*)malloc(sizeof(struct node));
n->data=x;
n->next=NULL;
return n;
void insert_at_front(int x){
struct node* n=createNode(x);
n->next=head;
head=n;
}
void insert_at_rear(int x){
struct node* n=createNode(x);
if(!head) head=n;
else{
struct node* temp=head;
while(temp->next) temp=temp->next;
temp->next=n;
int size_of_ll(){
int count=0;
struct node* temp=head;
while(temp){
count++;
temp=temp->next;
return count;
void delete_front(){
if(!head) printf("List Empty!\n");
else{
struct node* temp=head;
head=head->next;
free(temp);
void delete_rear(){
if(!head) printf("List Empty!\n");
else if(!head->next){
free(head);
head=NULL;
else{
struct node* temp=head;
while(temp->next->next) temp=temp->next;
free(temp->next);
temp->next=NULL;
void display(){
struct node* temp=head;
if(!temp) printf("List Empty!\n");
else{
printf("Linked List elements:\n");
while(temp){
printf("%d ",temp->data);
temp=temp->next;
printf("\n");
int menu(){
int ch;
printf("\[Link] Front [Link] Rear [Link] Front [Link] Rear");
printf("\[Link] [Link] [Link]\n");
printf("Enter choice: ");
scanf("%d",&ch);
return ch;
int main(){
int ch, x;
while(1){
ch=menu();
if(ch==1){
printf("Enter value: ");
scanf("%d",&x);
insert_at_front(x);
else if(ch==2){
printf("Enter value: ");
scanf("%d",&x);
insert_at_rear(x);
else if(ch==3) delete_front();
else if(ch==4) delete_rear();
else if(ch==5) display();
else if(ch==6) printf("Number of nodes: %d\n",size_of_ll());
else if(ch==7) break;
else printf("Invalid choice\n");
return 0;
Circular SLL example (just in case)
#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node *next;
};
struct node *head=NULL;
struct node* createNode(int x){
struct node* n=(struct node*)malloc(sizeof(struct node));
n->data=x;
n->next=n;
return n;
void insert_rear(int x){
struct node *n=createNode(x);
if(!head) head=n;
else{
struct node *temp=head;
while(temp->next!=head) temp=temp->next;
temp->next=n;
n->next=head;
void delete_front(){
if(!head) printf("List Empty\n");
else if(head->next==head){
free(head);
head=NULL;
}
else{
struct node *temp=head,*last=head;
while(last->next!=head) last=last->next;
head=head->next;
last->next=head;
free(temp);
void display(){
if(!head) printf("List Empty\n");
else{
struct node *temp=head;
printf("Circular List:\n");
do{
printf("%d ",temp->data);
temp=temp->next;
}while(temp!=head);
printf("\n");
int count(){
if(!head) return 0;
int c=0;
struct node *temp=head;
do{
c++;
temp=temp->next;
}while(temp!=head);
return c;
int menu(){
int ch;
printf("\[Link] Rear [Link] Front [Link] [Link] [Link]\n");
printf("Enter choice: ");
scanf("%d",&ch);
return ch;
int main(){
int ch,x;
while(1){
ch=menu();
if(ch==1){
printf("Enter value: ");
scanf("%d",&x);
insert_rear(x);
else if(ch==2) delete_front();
else if(ch==3) display();
else if(ch==4) printf("Number of nodes: %d\n",count());
else if(ch==5) break;
else printf("Invalid choice\n");
return 0;
9. Develop a menu driven Program in C for the following operations on Doubly Linked List (DLL)
having an integer Data field. a) Insertion of node at Front of DLL b) Deletion of node at Front of DLL.
c) Count the number of nodes in the list. d) Display the contents of DLL.
#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node *prev;
struct node *next;
};
struct node *head=NULL;
struct node* createNode(int x){
struct node* n=(struct node*)malloc(sizeof(struct node));
n->data=x;
n->prev=NULL;
n->next=NULL;
return n;
void insert_front(int x){
struct node* n=createNode(x);
if(!head) head=n;
else{
n->next=head;
head->prev=n;
head=n;
void delete_front(){
if(!head) printf("List Empty\n");
else{
struct node* temp=head;
head=head->next;
if(head) head->prev=NULL;
free(temp);
int count(){
int c=0;
struct node* temp=head;
while(temp){
c++;
temp=temp->next;
return c;
void display(){
struct node* temp=head;
if(!temp) printf("List Empty\n");
else{
printf("DLL contents:\n");
while(temp){
printf("%d ",temp->data);
temp=temp->next;
printf("\n");
}
int menu(){
int ch;
printf("\[Link] Front [Link] Front [Link] [Link] [Link]\n");
printf("Enter choice: ");
scanf("%d",&ch);
return ch;
int main(){
int ch,x;
while(1){
ch=menu();
if(ch==1){
printf("Enter value: ");
scanf("%d",&x);
insert_front(x);
else if(ch==2) delete_front();
else if(ch==3) printf("Number of nodes: %d\n",count());
else if(ch==4) display();
else if(ch==5) break;
else printf("Invalid choice\n");
return 0;
(CDLL just in case)
#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node *prev;
struct node *next;
};
struct node *head=NULL;
struct node* createNode(int x){
struct node* n=(struct node*)malloc(sizeof(struct node));
n->data=x;
n->prev=n;
n->next=n;
return n;
void insert_rear(int x){
struct node* n=createNode(x);
if(!head) head=n;
else{
struct node* last=head->prev;
last->next=n;
n->prev=last;
n->next=head;
head->prev=n;
void delete_rear(){
if(!head) printf("List Empty\n");
else if(head->next==head){
free(head);
head=NULL;
else{
struct node* last=head->prev;
struct node* newLast=last->prev;
newLast->next=head;
head->prev=newLast;
free(last);
void display(){
if(!head) printf("List Empty\n");
else{
struct node* temp=head;
printf("CDLL contents:\n");
do{
printf("%d ",temp->data);
temp=temp->next;
}while(temp!=head);
printf("\n");
int main(){
insert_rear(10);
insert_rear(20);
insert_rear(30);
display();
delete_rear();
display();
return 0;
10. Implement a menu driven Program in C for the following operations on Binary Search Tree. a)
Create a BST of N Integers: 6, 9, 5, 2, 8, 15, 24, 14, 7, 5, 2. b) Traverse the BST in Inorder, Preorder
and Postorder. c) Exit.
#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node *left, *right;
};
struct node* create(int data){
struct node* n=(struct node*)malloc(sizeof(struct node));
n->data=data;
n->left=n->right=NULL;
return n;
struct node* insert(struct node* root,int data){
if(!root) return create(data);
if(data<root->data)
root->left=insert(root->left,data);
else
root->right=insert(root->right,data);
return root;
void inorder(struct node* root){
if(root){
inorder(root->left);
printf("%d ",root->data);
inorder(root->right);
void preorder(struct node* root){
if(root){
printf("%d ",root->data);
preorder(root->left);
preorder(root->right);
void postorder(struct node* root){
if(root){
postorder(root->left);
postorder(root->right);
printf("%d ",root->data);
int main(){
struct node* root=NULL;
int arr[]={6,9,5,2,8,15,24,14,7,5,2};
int n=11,ch;
while(1){
printf("\[Link] BST\[Link]\[Link]\[Link]\[Link]\n");
scanf("%d",&ch);
if(ch==1){
root=NULL;
for(int i=0;i<n;i++)
root=insert(root,arr[i]);
printf("BST Created\n");
else if(ch==2){
inorder(root);
printf("\n");
else if(ch==3){
preorder(root);
printf("\n");
else if(ch==4){
postorder(root);
printf("\n");
else if(ch==5) break;
return 0;
11. Implement a menu driven Program in C for the following operations on Binary Search Tree. a)
Create a BST of N Integers: 65, 49, 55, 72, 38, 15, 24, 74, 67, 85, 12. b) Find the Maximum and
minimum values in BST. c) Exit
#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node *left, *right;
};
struct node* create(int x){
struct node* n=(struct node*)malloc(sizeof(struct node));
n->data=x;
n->left=n->right=NULL;
return n;
struct node* insert(struct node* root,int x){
if(!root) return create(x);
if(x<root->data)
root->left=insert(root->left,x);
else
root->right=insert(root->right,x);
return root;
int findMin(struct node* root){
while(root->left) root=root->left;
return root->data;
int findMax(struct node* root){
while(root->right) root=root->right;
return root->data;
int menu(){
int ch;
printf("\[Link] BST\[Link] Minimum\[Link] Maximum\[Link]\n");
printf("Enter choice: ");
scanf("%d",&ch);
return ch;
int main(){
struct node* root=NULL;
int ch;
int arr[]={65,49,55,72,38,15,24,74,67,85,12};
int n=11;
while(1){
ch=menu();
if(ch==1){
root=NULL;
for(int i=0;i<n;i++)
root=insert(root,arr[i]);
printf("BST Created\n");
else if(ch==2){
if(root) printf("Minimum value = %d\n",findMin(root));
else printf("Tree empty\n");
else if(ch==3){
if(root) printf("Maximum value = %d\n",findMax(root));
else printf("Tree empty\n");
else if(ch==4) break;
else printf("Invalid choice\n");
return 0;
}
(search function for BST just in case)
#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node *left,*right;
};
struct node* create(int x){
struct node* n=(struct node*)malloc(sizeof(struct node));
n->data=x;
n->left=n->right=NULL;
return n;
struct node* insert(struct node* root,int x){
if(!root) return create(x);
if(x<root->data) root->left=insert(root->left,x);
else root->right=insert(root->right,x);
return root;
int search(struct node* root,int key){
while(root){
if(root->data==key) return 1;
if(key<root->data) root=root->left;
else root=root->right;
return 0;
}
int main(){
struct node* root=NULL;
int arr[]={65,49,55,72,38,15,24,74,67,85,12};
int n=11,key;
for(int i=0;i<n;i++)
root=insert(root,arr[i]);
printf("Enter key to search: ");
scanf("%d",&key);
if(search(root,key))
printf("Key found\n");
else
printf("Key not found\n");
return 0;
12. Design and develop a c program to generate a max heap tree from a given unsorted array.
#include <stdio.h>
void swap(int *a,int *b){
int t=*a;
*a=*b;
*b=t;
void heapify(int arr[],int n,int i){
int largest=i;
int l=2*i+1;
int r=2*i+2;
if(l<n && arr[l]>arr[largest]) largest=l;
if(r<n && arr[r]>arr[largest]) largest=r;
if(largest!=i){
swap(&arr[i],&arr[largest]);
heapify(arr,n,largest);
void buildMaxHeap(int arr[],int n){
for(int i=n/2-1;i>=0;i--)
heapify(arr,n,i);
int main(){
int arr[]={10,40,20,30,50};
int n=sizeof(arr)/sizeof(arr[0]);
buildMaxHeap(arr,n);
printf("Max Heap:\n");
for(int i=0;i<n;i++)
printf("%d ",arr[i]);
return 0;
}
13. Design and develop a C program to implement hashing for data of N employee records, where
each record is uniquely identified by a key K. Use a hash table of size m and hash function H(K)=K
mod m (remainder method) to map keys to locations. Handle collisions using linear probing
technique.
#include <stdio.h>
#define SIZE 10
int ht[SIZE];
void init(){
for(int i=0;i<SIZE;i++)
ht[i]=-1;
int hash(int key){
return key % SIZE;
void insert(int key){
int index = hash(key);
if(ht[index]==-1){
ht[index]=key;
return;
int i=(index+1)%SIZE;
while(i!=index){
if(ht[i]==-1){
ht[i]=key;
return;
i=(i+1)%SIZE;
}
printf("Hash table full\n");
void display(){
printf("Hash Table:\n");
for(int i=0;i<SIZE;i++)
printf("Index %d : %d\n",i,ht[i]);
int main(){
int ch,key;
init();
while(1){
printf("\[Link] [Link] [Link]\n");
scanf("%d",&ch);
if(ch==1){
printf("Enter key: ");
scanf("%d",&key);
insert(key);
else if(ch==2) display();
else if(ch==3) break;
else printf("Invalid choice\n");
return 0;
14. Design and develop a c program to print all the nodes reachable from a given starting node in a
digraph using DFS method.
#include <stdio.h>
#define MAX 10
int adj[MAX][MAX], visited[MAX], n;
void dfs(int v){
visited[v]=1;
printf("%d ",v);
for(int i=0;i<n;i++){
if(adj[v][i] && !visited[i])
dfs(i);
int main(){
int i,j,start;
printf("Enter number of vertices: ");
scanf("%d",&n);
printf("Enter adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&adj[i][j]);
for(i=0;i<n;i++)
visited[i]=0;
printf("Enter starting vertex: ");
scanf("%d",&start);
printf("DFS traversal: ");
dfs(start);
return 0;
(bfs logic just in case)
#include <stdio.h>
#define MAX 10
int adj[MAX][MAX], visited[MAX];
int queue[MAX], front=0, rear=-1;
int n;
void enqueue(int v){
queue[++rear]=v;
int dequeue(){
return queue[front++];
int isEmpty(){
return front>rear;
void bfs(int start){
int v,i;
visited[start]=1;
enqueue(start);
printf("BFS traversal: ");
while(!isEmpty()){
v=dequeue();
printf("%d ",v);
for(i=0;i<n;i++){
if(adj[v][i] && !visited[i]){
visited[i]=1;
enqueue(i);
int main(){
int i,j,start;
printf("Enter number of vertices: ");
scanf("%d",&n);
printf("Enter adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&adj[i][j]);
for(i=0;i<n;i++)
visited[i]=0;
printf("Enter starting vertex: ");
scanf("%d",&start);
bfs(start);x`
return 0;