Chapter 13: Advanced Data Structures in C

Introduction

In programming, data structures are essential tools that enable efficient data manipulation and management. Advanced data structures go beyond the basic arrays and linked lists to provide more sophisticated ways to store, organize, and retrieve data. This chapter delves into some of the most commonly used advanced data structures in C: trees, heaps, hash tables, and graphs. Understanding these data structures will significantly enhance your ability to develop complex and efficient C programs.

Trees

Binary Trees

A binary tree is a hierarchical structure in which each node has at most two children, referred to as the left child and the right child. Binary trees are fundamental in various applications such as expression parsing, search operations, and hierarchical data modeling.

Implementation

Here’s a basic implementation of a binary tree node in C:

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

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory error\n");
        return NULL;
    }
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

Binary Search Trees (BST)

A binary search tree is a binary tree with the additional property that the left child of a node contains only nodes with values less than the parent node’s value, and the right child only nodes with values greater.

Operations

Insertion:

Node* insertNode(Node* root, int data) {
    if (root == NULL) {
        root = createNode(data);
        return root;
    }

    if (data < root->data) {
        root->left = insertNode(root->left, data);
    } else {
        root->right = insertNode(root->right, data);
    }

    return root;
}

Searching:

Node* searchNode(Node* root, int data) {
    if (root == NULL || root->data == data)
        return root;

    if (data < root->data)
        return searchNode(root->left, data);

    return searchNode(root->right, data);
}

AVL Trees

An AVL tree is a self-balancing binary search tree where the difference between the heights of the left and right subtrees cannot be more than one for all nodes. Rotations are used to maintain this property after insertions and deletions.

Rotations

Right Rotation:

Node* rightRotate(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;

    x->right = y;
    y->left = T2;

    return x;
}

Left Rotation:

Node* leftRotate(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

    y->left = x;
    x->right = T2;

    return y;
}

Heaps

Heaps are specialized tree-based data structures that satisfy the heap property. In a max heap, for any given node I, the value of I is greater than or equal to the values of its children. In a min heap, the value is less than or equal to its children.

Implementation

Max Heap Insertion:

void maxHeapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        maxHeapify(arr, n, largest);
    }
}

void insertMaxHeap(int arr[], int* n, int key) {
    *n = *n + 1;
    int i = *n - 1;
    arr[i] = key;

    while (i != 0 && arr[(i - 1) / 2] < arr[i]) {
        int temp = arr[i];
        arr[i] = arr[(i - 1) / 2];
        arr[(i - 1) / 2] = temp;

        i = (i - 1) / 2;
    }
}

Hash Tables

Hash tables are a type of data structure that map keys to values for highly efficient lookup. The core concept is the use of a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Implementation

Basic Hash Function:

unsigned int hashFunction(int key) {
    return key % TABLE_SIZE;
}

Insertion:

void insertHashTable(int key, int data) {
    unsigned int index = hashFunction(key);

    while (hashTable[index] != NULL && hashTable[index]->key != -1) {
        ++index;
        index %= TABLE_SIZE;
    }

    hashTable[index] = (struct DataItem*)malloc(sizeof(struct DataItem));
    hashTable[index]->key = key;
    hashTable[index]->data = data;
}

Graphs

Graphs are collections of nodes (vertices) connected by edges. They can represent various real-world systems such as social networks, computer networks, and transportation networks.

Graph Representation

Adjacency Matrix:

#define MAX 100
int graph[MAX][MAX];

void addEdge(int u, int v) {
    graph[u][v] = 1;
    graph[v][u] = 1;
}

Adjacency List:

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

struct Graph {
    int numVertices;
    struct Node** adjLists;
};

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

struct Graph* createGraph(int vertices) {
    struct Graph* graph = malloc(sizeof(struct Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(struct Node*));

    for (int i = 0; i < vertices; i++)
        graph->adjLists[i] = NULL;

    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

Conclusion

Advanced data structures like trees, heaps, hash tables, and graphs provide powerful ways to organize and manipulate data. Mastering these structures is crucial for developing efficient algorithms and solving complex problems. By understanding their implementations and applications, you can significantly enhance your programming skills and create more robust software solutions.