Implementing Menu-Driven Programs for Data Structures in C
1. Circular Singly Linked List Operations
Develop and implement a menu-driven program in C for the following operations on Circular Singly Linked List (CSLL):
- Insertion at front of SLL
- Deletion at end of SLL
- Display the status of SLL
- Exit
#include
#include
struct Node {
int info;
struct Node* link;
};
typedef struct Node* NODE;
NODE last = NULL;
NODE getnode() {
NODE newNode = (NODE)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(1);
}
printf("Enter value to insert: ");
scanf("%d", &newNode->info);
newNode->link = NULL;
return newNode;
}
void insertAtFront() {
NODE temp = getnode();
if (last == NULL) {
last = temp;
temp->link = temp;
} else {
temp->link = last->link;
last->link = temp;
}
printf("Node inserted at the front with value %d.\n", temp->info);
}
void deleteAtRear() {
if (last == NULL) {
printf("List is empty. Cannot delete from rear.\n");
return;
}
NODE prev = NULL, cur = last->link;
if (last->link == last) {
prev = last;
} else {
while (cur->link != last) {
prev = cur;
cur = cur->link;
}
}
if (prev == NULL) {
last = NULL;
} else {
prev->link = last->link;
last = prev;
}
printf("Node with value %d deleted from the rear.\n", cur->info);
free(cur);
}
void display() {
if (last == NULL) {
printf("List is empty.\n");
return;
}
NODE cur = last->link;
printf("Circular Singly Linked List: ");
do {
printf("%d ", cur->info);
cur = cur->link;
} while (cur != last->link);
printf("\n");
}
void main() {
int choice;
while (1) {
printf("\nCircular Singly Linked List Operations:\n");
printf("1. Insert at Front\n");
printf("2. Delete from Rear\n");
printf("3. Display List\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1: insertAtFront(); break;
case 2: deleteAtRear(); break;
case 3: display(); break;
case 4: printf("Exiting the program.\n"); exit(0);
default: printf("Invalid choice! Please try again.\n");
}
}
}
2. Circular Doubly Linked List Operations
Develop and implement a menu-driven program in C for the following operations on Circular Doubly Linked List (CDLL):
- Insertion at front of DLL
- Deletion at front of DLL
- Display the status of DLL
- Exit
#include
#include
struct Node {
int info;
struct Node* rlink;
struct Node* llink;
};
typedef struct Node* NODE;
NODE first = NULL;
NODE last = NULL;
NODE getnode() {
NODE newNode = (NODE)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(1);
}
printf("Enter value to insert: ");
scanf("%d", &newNode->info);
newNode->rlink = newNode->llink = NULL;
return newNode;
}
void insertAtFront() {
NODE temp = getnode();
if (first == NULL) {
first = last = temp;
temp->rlink = temp->llink = temp;
} else {
temp->rlink = first;
temp->llink = last;
last->rlink = temp;
first->llink = temp;
first = temp;
}
printf("Node inserted at the front with value %d.\n", temp->info);
}
void deleteAtFront() {
if (first == NULL) {
printf("List is empty. Cannot delete from front.\n");
return;
}
NODE temp = first;
if (first == last) {
first = last = NULL;
} else {
first = first->rlink;
first->llink = last;
last->rlink = first;
}
printf("Node with value %d deleted from the front.\n", temp->info);
free(temp);
}
void display() {
if (first == NULL) {
printf("List is empty.\n");
return;
}
NODE cur = first;
printf("Circular Doubly Linked List: ");
do {
printf("%d ", cur->info);
cur = cur->rlink;
} while (cur != first);
printf("\n");
}
void main() {
int choice;
while (1) {
printf("\nCircular Doubly Linked List Operations:\n");
printf("1. Insert at Front\n");
printf("2. Delete from Front\n");
printf("3. Display List\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1: insertAtFront(); break;
case 2: deleteAtFront(); break;
case 3: display(); break;
case 4: printf("Exiting the program.\n"); exit(0);
default: printf("Invalid choice! Please try again.\n");
}
}
}
3. Binary Search Tree Operations
Implement a menu-driven program in C for the following operations on Binary Search Tree (BST):
- Create a BST of N integers
- Traverse the BST in Inorder, Preorder, and Postorder
- Exit
#include
#include
struct node {
int data;
struct node *left, *right;
};
typedef struct node* NODE;
NODE createNode(int data) {
NODE newNode = (NODE)malloc(sizeof(struct node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
NODE insert(NODE root, int data) {
if (root == NULL) {
return createNode(data);
}
if (data < root->data) {
root->left = insert(root->left, data);
} else {
root->right = insert(root->right, data);
}
return root;
}
void inorder(NODE root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
void preorder(NODE root) {
if (root != NULL) {
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
void postorder(NODE root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}
void display(NODE root, int level) {
int i;
if (root != NULL) {
display(root->right, level + 1);
printf("\n");
for (i = 0; i < level; i++) {
printf("\t");
}
printf("%d", root->data);
display(root->left, level + 1);
}
}
void main() {
NODE root = NULL;
int n, data, choice;
while (1) {
printf("\nMenu:\n");
printf("1. Create BST of N integers\n");
printf("2. Inorder Traversal\n");
printf("3. Preorder Traversal\n");
printf("4. Postorder Traversal\n");
printf("5. Display Tree Structure\n");
printf("6. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1: printf("Enter the number of elements: ");
scanf("%d", &n);
for (int i = 0; i < n; i++) {
printf("Enter element %d: ", i + 1);
scanf("%d", &data);
root = insert(root, data);
}
break;
case 2: printf("Inorder Traversal: ");
inorder(root);
printf("\n");
break;
case 3: printf("Preorder Traversal: ");
preorder(root);
printf("\n");
break;
case 4: printf("Postorder Traversal: ");
postorder(root);
printf("\n");
break;
case 5: printf("Tree Structure:\n");
display(root, 0);
break;
case 6: exit(0);
default: printf("Invalid choice, please try again.\n");
}
}
}
4. Hashing for Employee Records
Design and develop a C program to implement hashing for a file 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 and quadratic probing techniques.
#include
#include
#include
struct employee {
char name[20];
int key;
} ht[10] = {0};
int lprob(int k);
int qprob(int k);
void main() {
int location, k, choice;
char name[20];
FILE *fp;
fp = fopen("data.txt", "r");
if (fp == NULL) {
printf("Error opening file\n");
return;
}
printf("Enter choice\n");
printf("Enter 1-Linear Probing 2-Quadratic Probing\n");
scanf("%d", &choice);
switch (choice) {
case 1:
for (int i = 0; i < 10; i++) {
fscanf(fp, "%s %d", name, &k);
location = lprob(k);
strcpy(ht[location].name, name);
ht[location].key = k;
}
break;
case 2:
for (int i = 0; i < 10; i++) {
fscanf(fp, "%s %d", name, &k);
location = qprob(k);
strcpy(ht[location].name, name);
ht[location].key = k;
}
break;
default:
printf("Invalid Choice\n");
fclose(fp);
return;
}
printf("Hash Table contents\n");
for (int i = 0; i < 10; i++) {
printf("%d %s %d\n", i, ht[i].name, ht[i].key);
}
fclose(fp);
}
int lprob(int k) {
int location = k % 10;
int i = 0;
while (ht[location].key != 0) {
i++;
location = (k + i) % 10;
}
return location;
}
int qprob(int k) {
int i = 0;
int location = k % 10;
while (ht[location].key != 0) {
i++;
location = (k + (i * i)) % 10;
}
return location;
}
5. Graph Traversal Using BFS and DFS
Design and develop a C program to print all the nodes reachable from a given starting node in a directed graph using BFS method.
#include
void bfs(int a[10][10], int n, int u) {
int f, r, q[10], v;
int s[10] = {0};
printf("The nodes visited from %d: ", u);
f = 0, r = -1;
q[++r] = u;
s[u] = 1;
printf("%d ", u);
while (f <= r) {
u = q[f++];
for (v = 0; v < n; v++) {
if (a[u][v] == 1) {
if (s[v] == 0) {
printf("%d ", v);
s[v] = 1;
q[++r] = v;
}
}
}
}
printf("\n");
}
void main() {
int n, a[10][10], source, i, j;
printf("Enter the number of nodes: ");
scanf("%d", &n);
printf("Enter the adjacency matrix:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) scanf("%d", &a[i][j]);
}
for (source = 0; source < n; source++) {
bfs(a, n, source);
}
}
Design and develop a C program to print all the nodes reachable from a given starting node in a directed graph using DFS method.
#include
int a[10][10], s[10], n;
void dfs(int u) {
int v;
s[u] = 1;
printf("%d ", u);
for (v = 0; v < n; v++) {
if (a[u][v] == 1 && s[v] == 0) dfs(v);
}
}
void read_adjacency_matrix(int a[10][10], int n) {
int i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &a[i][j]);
}
}
}
void main() {
int i, source;
printf("Enter the number of nodes in the graph: ");
scanf("%d", &n);
printf("Enter the adjacency matrix:\n");
read_adjacency_matrix(a, n);
for (source = 0; source < n; source++) {
for (i = 0; i < n; i++) s[i] = 0;
printf("\nThe nodes reachable from %d: ", source);
dfs(source);
}
}