Data Structures and Algorithms in C: Implementations and Explanations

Posted on Sep 5, 2024 in Computers

1) Implementing a Linear Queue in C

#include<stdio.h>
int q[10], ch, size, front=-1, rear=-1, item, i;
void enqueue()
{
if(rear == size – 1)
printf(“Queue Overflow “);
else
{
if(front== – 1)
front = 0;
printf(“Insert the element in queue : “);
scanf(“%d”, &item);
q[rear++] = item;
}
}
void dequeue()
{
if(front== -1 || front>rear)
{
 printf(“Queue Underflow “);
}
else
{
printf(“Element deleted from queue is : %d “, q[front]);
front++;
 }
}
void display()
{
if(front== -1 || front>rear)
{
 printf(“Queue is empty “);
}
else
{
printf(“Queue is : “);
for(i = front; i < rear; i++)
printf(“%d “, q[i]);
}
}
void main()
{
printf(“Enter the size of STACK “);
scanf(“%d”, &size);
for(;;)
{
printf(“1. Insert 2. Delete 3. DISPLAY “);
printf(“Enter the Choice: “);
scanf(“%d”,&ch);
switch(ch)
{
case 1: enqueue(); break;
 case 2: dequeue();break;
case 3: display(); break;
 }
}
}

2) Implementing a Stack of Integers Using a Singly Linked List in C

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

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

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

void insertFront(struct Node** head, int value) {
    struct Node* newNode = createNode(value);
    newNode->next = *head;
    *head = newNode;
}

void display(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf(“%d “, temp->data);
        temp = temp->next;
    }
    printf(” “);
}

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

    while (1) {
        printf(“Enter your choice: “);
        printf(“1 – Insert at the front “);
        printf(“2 – Display and count nodes “);
        printf(“3 – Exit “);
        scanf(“%d”, &choice);

        switch (choice) {
            case 1:
                printf(“Enter data: “);
                scanf(“%d”, &value);
                insertFront(&head, value);
                break;
            case 2:
                printf(“Linked list contents: “);
                display(head);
                break;
            case 3:
                printf(“Exiting program. “);
                exit(0);
            default:
                printf(“Invalid choice. Try again. “);
        }
    }

    return 0;
}

3) Implementing a Circular Queue in C

#include <stdio.h>
#define MAX_SIZE 10

int cq[MAX_SIZE], front = -1, rear = -1;

int isFull() {
    return (rear + 1) % MAX_SIZE == front;
}

int isEmpty() {
    return front == -1;
}

void enQueue() {
    if (isFull()) {
        printf(“CIRCULAR QUEUE IS FULL “);
        return;
    }
    int item;
    printf(“Enter an element: “);
    scanf(“%d”, &item);
    if (front == -1)
        front = 0;
    rear = (rear + 1) % MAX_SIZE;
    cq[rear] = item;
    printf(“Inserted “);
}

void deQueue() {
    if (isEmpty()) {
        printf(“CIRCULAR QUEUE IS EMPTY “);
        return;
    }
    printf(“Deleted element: %d “, cq[front]);
    if (front == rear)
        front = rear = -1;
    else
        front = (front + 1) % MAX_SIZE;
}

void display() {
    if (isEmpty()) {
        printf(“CIRCULAR QUEUE IS EMPTY “);
        return;
    }
    printf(“Items: “);
    for (int i = front; i != rear; i = (i + 1) % MAX_SIZE)
        printf(“%d “, cq[i]);
    printf(“%d “, cq[rear]);
}

int main() {
    int ch;
    for (;;) {
        printf(“1. Insert 2. Delete 3. Display 4. Exit “);
        printf(“Enter your choice: “);
        scanf(“%d”, &ch);
        switch (ch) {
            case 1: enQueue(); break;
            case 2: deQueue(); break;
            case 3: display(); break;
            case 4: printf(“Exiting program. “); return 0;
            default: printf(“Invalid choice. Try again. “);
        }
    }
}

4) C Functions for Searching and Concatenating Singly Linked Lists

i) Search

void search(struct node *head, int key)
{
 struct node *temp = head;
 while(temp != NULL)
 {
 if(temp->data == key)
 printf(“key found”);
 temp = temp->next;
 }
 printf(“key not found”);
}

ii) Concatenation

void Concat(struct Node *first, struct Node *second)
{
 struct Node *p = first;
 while (p->next != NULL)
 {
 p = p->next;
 }
 p->next = second;
 second = NULL;
}

5) Defining and Representing a Binary Tree

Definition:

A binary tree T is defined as a finite set of nodes such that, ll  T is empty or  T consists of a root and two disjoint binary trees called the left sub tree and the right sub tree. ll

Array Representation:

 A tree can be represented using an array, which is called sequential representation. ll  The nodes are numbered from 1 to n, and one dimensional array can be used to store the nodes. ll  Position 0 of this array is left empty and the node numbered i is mapped to position i of the array ll

Linked Representation:

 Each node has three fields, ll  LeftChild – which contains the address of left subtree ll  RightChild – which contains the address of right subtree.ll   Data – which contains the actual information ll

6) Chained Hashing: Definition, Pros, Cons, and Example

Chained hashing, also known as separate chaining, is a technique used to resolve collisions in hash tables. When two or more keys hash to the same index (known as a collision), chained hashing handles these collisions by maintaining a linked list of all elements that hash to the same index. ll

Pros of Chained Hashing:

1. Simple Implementation: Chained hashing is relatively easy to implement. ll 2. Efficient Insertion and Deletion: Insertion and deletion operations are efficient in chained hashing. ll 3. Dynamic Data Sets: Chained hashing allows for dynamic resizing of the hash table.. ll 4. Adaptability: Chained hashing can handle a wide range of input data distributionsll

Cons of Chained Hashing:

1. Memory Overhead: Chained hashing can have a higher memory overhead compared to other collision resolution techniques. 2. Cache Inefficiency: cache inefficiency, particularly for large hash tables with long linked lists. 3. Performance Degradation: 4. Poor Worst-Case Performance: Chained hashing does not guarantee constant-time performance for lookup operations in the worst case ll

Constructing a Chained Hash Table

To insert the keys: 7, 24, 18, 52, 36, 54, 11, 23 in a chained hash table of 9 memory locations using h(k) = k mod m, we would proceed as follows: ll 1. **Calculate Hash Values:** Apply the hash function h(k) = k mod 9 to each key. ll 2. **Create Linked Lists:** For each hash value, create a linked list to store the keys that hash to that index. ll 3. **Insert Keys:** Insert each key into the corresponding linked list based on its hash value. ll The resulting chained hash table would look like this: ll Index | Keys ll ——- | ——– ll 0 | 7, 23 ll 1 | 11 ll 2 | 18 ll 3 | 24 ll 4 | 36 ll 5 | 52 ll 6 | 54 ll 7 | ll 8 | ll

7) Leftist Trees: Definition, C Declaration, and Example

A leftist tree is a binary tree such that if it is not empty, then shortest (LeftChild (x) >= shortest (RightChild (x ) for every internal node x. ll

C Declaration

 ll struct node ll{ ll  int data; ll struct node *left; ll struct node *right; ll int rank; ll 
};

8)