Advanced Data Structures lab programs in C
Introduction
One of the most important topics of programming field is advanced data structures, which are used to store, organize, and manage information as well as data for effective, simple access, and data modifications. They are the fundamental components needed to create effective as well as efficient algorithms and software designs. Here, we will see some of the important advanced data structure lab programs within the C language.
Program 1: Implementing various operations on the binary heap.
The heap data structure formed with a binary tree is called a binary heap. It resembles a binary tree which has two constraints:
Shape Property:
The tree may be described as the complete binary tree if all of its levels—with the possible exception of the last, deepest level—are completely filled. If the lowest level of a tree is incomplete, the nodes within it are filled in a left-to-right direction.
Heap property:
Depending on a comparison predicate provided for the heap, every node is either [larger than or equivalent to] or [lower than or equivalent to] each of its offspring.
- There are two possible forms for the heap ordering property:
The min-heap property: It places the lowest-value element at the root and every node's value higher than or equivalent to that of its parent.
The max-heap property: It places the highest value element at the root and each node's value below or equivalent to that of its parent.
- Below is the program implementing various operations on the binary heap.
Program:
#include <stdio.h>
#include <stdlib.h>
#define HEAPCOUNT 150
int total_count = 0;
void insertingHeap(int *data_node, int lower_value, int total_count)
{
int position = (2 * lower_value) + 1, current_ele = data_node[lower_value];
while (position <= total_count)
{
if (position < total_count && data_node[position] > data_node[position + 1])
position++;
if (current_ele <= data_node[position])
break;
else {
data_node[lower_value] = data_node[position];
lower_value = position;
position = (2 * lower_value) + 1;
}
}
data_node[lower_value] = current_ele;
return;
}
void buildingHeap(int *data_node, int n)
{
int lower_value;
for (lower_value = n/2 - 1; lower_value >= 0; lower_value--)
{
insertingHeap(data_node, lower_value, n-1);
}
return;
}
void buildingUp(int *data_node, int index)
{
int value = data_node[index];
while (data_node[(index - 1) / 2] >= value)
{
data_node[index] = data_node[(index - 1) / 2];
if (!index)
break;
index = (index - 1) / 2;
}
data_node[index] = value;
return;
}
void addingNode(int *data_node, int value, int n)
{
data_node[n] = value;
buildingUp(data_node, n);
return;
}
void deletingNode(int *data_node, int n)
{
int value = data_node[0];
data_node[0] = data_node[n];
insertingHeap(data_node, 0, n - 1);
printf("%d is deleted from the heap\n", value);
return;
}
void replacingNode(int *data_node, int value, int n)
{
int i;
data_node[0] = value;
for (i = n/2 - 1; i >= 0; i--)
insertingHeap(data_node, i, n - 1);
return;
}
void displayingNode(int *data_node, int n)
{
int i;
printf ("\nData in the Binary Heap is :\n");
for (i = 0; i <= n; i++)
{
printf ("%d ", data_node[i]);
}
printf ("\n \n");
}
int main()
{
int n, i, *data_node, temp, ch, value;
data_node = (int *)malloc(sizeof(int) * HEAPCOUNT);
printf ("Enter the value between 1-100 :");
scanf("%d", &n);
if (n < 1 || n > 100)
{
printf ("Enter the value within the given range!!\n");
return 0;
}
for (i = 0; i < n; i++)
{
printf ("Input %d:", i + 1);
scanf("%d", &data_node[i]);
total_count++;
}
buildingHeap(data_node, n);
while (n < (HEAPCOUNT -1))
{
printf ("1. Adding the New Node\t 2. Deleting the Node\n");
printf ("3. Replacing the Node\t 4. Displaying the Heap\n");
printf ("5. Exit\nSelect your choice from the above :");
scanf("%d", &ch);
switch(ch)
{
case 1:
printf ("Enter the input value :");
scanf("%d", &value);
addingNode(data_node, value, n);
n++;
break;
case 2:
deletingNode(data_node, n - 1);
n--;
break;
case 3:
printf ("Enter the input value :");
scanf("%d", &value);
replacingNode(data_node, value, n);
break;
case 4:
displayingNode(data_node, n - 1);
break;
case 5:
goto sort;
default:
printf ("Select the correct option!!\n");
break;
}
}
sort:
for (i = n - 1; i > 0; i--)
{
temp = data_node[i];
data_node[i] = data_node[0];
data_node[0] = temp;
insertingHeap(data_node, 0, i - 1);
}
printf ("Sorted Data is : \n");
for (i = 0; i < n; i++)
printf ("%d ", data_node[i]);
printf ("\n");
return 0;
}
Output:
Program 2: Implementing Prism's algorithm in order to find the minimum cost of spanning tree.
Step 1: Choose the edge that will cost the least and add it to your spanning tree.
Step 2: Choose the edge having the lowest cost from all those that are next to the edge that has been chosen.
Step 3: Perform step 2 until all (n-1) edges along with all (n) vertices have been included. And then, there are no cycles in the subgraph which was created.
Program:
#include <stdio.h>
int a, b, c, d, n, i, j, ne = 1;
int visited_node[10] = {0}, mini, mini_cost = 0, total_cost[10][10];
int main()
{
printf("\n PRIM’S ALGORITHM FOR MINIMUM SPANNING TREE \n");
printf("\n Enter the total number of input nodes : ");
scanf("%d", &n);
printf("\n Enter the Adjacency Matrix :\n");
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
scanf("%d", &total_cost[i][j]);
if(total_cost[i][j] == 0)
{
total_cost[i][j] = 999;
}
}
}
visited_node[1] = 1;
printf("\n Final Minimum Spanning Tree is :");
while(ne < n)
{
for(i = 1, mini = 999; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
if(total_cost[i][j] < mini)
{
if(visited_node[i] != 0)
{
mini = total_cost[i][j];
a = c = i;
b = d = j;
}
}
if(visited_node[c] == 0 || visited_node[d] == 0)
{
printf("\n Edge node is %d : (%d, %d) cost : %d", ne++, a, b, mini);
mini_cost += mini;
visited_node[b] = 1;
}
total_cost[a][b] = total_cost[b][a] = 999;
}
}
}
printf("\n Minimun Cost of spanning tree is : %d", mini_cost);
return 0;
}
Output:
Program 3: Implementing Krushkal’s algorithm in order to find minimum cost of spanning tree.
Kruskal's Algorithm: Begin the spanning tree with no nodes or edges, and then iteratively add the least expensive edge which prevents the creating cycle.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
int i, j, k, a, b, c, d, n, ne = 1;
int mini, mini_cost = 0, total_cost[9][9], parent_node[9];
int finding_cost (int);
int uni (int, int);
int main()
{
printf ("\n IMPLEMENTING KRUSKAL’S ALGORITHM FOR THE MINIMUM SPANNING TREE : \n");
printf ("\n Implementing the Kruskal’s algorithm \n");
printf ("\n Enter the total No. of input Vertices : \n");
scanf ("%d", &n);
printf ("\n Enter the Cost an Adjacency Matrix : \n");
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
scanf ("%d", &total_cost[i][j]);
if (total_cost[i][j] == 0)
{
total_cost[i][j] = 999;
}
}
}
printf ("\n Final Minimum Spanning Tree is : ");
printf ("\n The Edges of the Minimum Cost Spanning Tree is : \n");
while (ne < n)
{
for (i = 1, mini = 999; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
if (total_cost[i][j] < mini)
{
mini = total_cost[i][j];
a = c = i;
b = d = j;
}
}
}
c = finding_cost (c);
d = finding_cost (d);
if (uni (c, d))
{
printf ("\n %d Edge Node is : (%d, %d) = %d", ne++, a, b, mini);
mini_cost += mini;
}
total_cost[a][b] = total_cost[b][a] = 999;
}
printf ("\n Minimum Cost of spanning tree using Krushkal's algorithm is : %d \n", mini_cost);
getch();
}
int finding_cost (int i)
{
while (parent_node[i])
{
i = parent_node[i];
}
return i;
}
int uni (int i, int j)
{
if (i != j)
{
parent_node[j] = i;
return 1;
}
return 0;
}
Output:
Program 4: Performing different operations on dictionary using Hashing
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct hashing *hash_table = NULL;
int element_count = 0;
struct node
{
int key, age;
char name[100];
struct node *next_node;
};
struct hashing
{
struct node *head;
int total_count;
};
struct node * creating_node(int key, char *name, int age)
{
struct node *new_node;
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> key = key;
new_node -> age = age;
strcpy(new_node -> name, name);
new_node -> next_node = NULL;
return new_node;
}
void inserting_into_Hashtable(int key, char *name, int age)
{
int hashing_index = key % element_count;
struct node *new_node = creating_node(key, name, age);
if (!hash_table[hashing_index].head)
{
hash_table[hashing_index].head = new_node;
hash_table[hashing_index].total_count = 1;
return;
}
new_node -> next_node = (hash_table[hashing_index].head);
hash_table[hashing_index].head = new_node;
hash_table[hashing_index].total_count++;
return;
}
void deleting_from_Hashtable(int key)
{
int hashing_index = key % element_count, flag = 0;
struct node *temp, *myNode;
myNode = hash_table[hashing_index].head;
if (!myNode)
{
printf("Enter correct data!! \n");
return;
}
temp = myNode;
while (myNode != NULL)
{
if (myNode -> key == key)
{
flag = 1;
if (myNode == hash_table[hashing_index].head)
{
hash_table[hashing_index].head = myNode->next_node;
}
else
{
temp->next_node = myNode->next_node;
}
hash_table[hashing_index].total_count--;
free(myNode);
break;
}
temp = myNode;
myNode = myNode->next_node;
}
if (flag)
{
printf("Data is deleted from the hash table \n");
}
else
{
printf("Enter the correct data!! \n");
}
return;
}
void searching_in_Hashtable(int key)
{
int hashing_index = key % element_count, flag = 0;
struct node *myNode;
myNode = hash_table[hashing_index].head;
if (!myNode)
{
printf("Searching element is out of range!!\n");
return;
}
while (myNode != NULL)
{
if (myNode->key == key)
{
printf("VoterID : %d\n", myNode->key);
printf("Name : %s\n", myNode->name);
printf("Age : %d\n", myNode->age);
flag = 1;
break;
}
myNode = myNode -> next_node;
}
if (!flag)
{
printf("Search element is unavailable in hash table\n");
}
return;
}
void displaying_hashtable()
{
struct node *myNode;
int i;
for (i = 0; i < element_count; i++)
{
if (hash_table[i].total_count == 0)
{
continue;
}
myNode = hash_table[i].head;
if (!myNode)
{
continue;
}
printf("\nData at the index position %d in Hash Table is :\n", i);
printf("VoterID Name Age \n");
while (myNode != NULL)
{
printf("%-12d", myNode->key);
printf("%-15s", myNode->name);
printf("%d\n", myNode->age);
myNode = myNode->next_node;
}
}
return;
}
int main()
{
int n, ch, key, age;
char name[100];
printf("Enter the number of elements : ");
scanf("%d", &n);
element_count = n;
hash_table = (struct hashing *)calloc(n, sizeof (struct hashing));
while (1)
{
printf("\n1. Insertion\t 2. Deletion\n");
printf("3. Searching\t 4. Display\n 5. Exit\n");
printf("Select from the above option : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("Enter the value :");
scanf("%d", &key);
getchar();
printf("Enter the name : ");
scanf("%s", name);
printf("Age:");
scanf("%d", &age);
inserting_into_Hashtable(key, name, age);
break;
case 2:
printf("Enter the element to delete from hash table : ");
scanf("%d", &key);
deleting_from_Hashtable(key);
break;
case 3:
printf("Enter the element to search in the hash table : ");
scanf("%d", &key);
searching_in_Hashtable(key);
break;
case 4:
displaying_hashtable();
break;
case 5:
exit(0);
default:
printf("Please select the correct option!! \n");
break;
}
}
return 0;
}
Output:
