从入门到精通：C语言必备的10大数据结构详解与应用

C语言作为一种基础而强大的编程语言，在计算机科学和软件开发中占据着重要的地位。数据结构是C语言编程中不可或缺的一部分，它影响着程序的效率、可读性和可维护性。以下是对C语言中10种常见数据结构的详细解析及其应用场景。

1. 数组

数组是C语言中最基本的数据结构之一，用于存储具有相同数据类型的元素序列。数组可以通过索引直接访问元素，具有固定的长度。

应用场景

• 存储大量数据，如成绩单、库存信息等。
• 实现其他数据结构，如链表、栈、队列等。

#include <stdio.h>

int main() {
    int numbers[5] = {1, 2, 3, 4, 5};
    printf("The first element is %d\n", numbers[0]);
    return 0;
}

2. 链表

链表是一种非线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

应用场景

• 实现动态数据结构，如栈、队列、双向链表等。
• 管理动态分配的内存。

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

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

void insertAtHead(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

int main() {
    struct Node* head = NULL;
    insertAtHead(&head, 1);
    insertAtHead(&head, 2);
    insertAtHead(&head, 3);
    printf("Linked List: ");
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    return 0;
}

3. 栈

栈是一种后进先出（LIFO）的数据结构，元素只能从一端添加或移除。

应用场景

• 函数调用栈。
• 括号匹配验证。

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

struct Stack {
    int top;
    unsigned capacity;
    int* array;
};

int isFull(struct Stack* stack) {
    return stack->top == stack->capacity - 1;
}

int isEmpty(struct Stack* stack) {
    return stack->top == -1;
}

void push(struct Stack* stack, int item) {
    if (isFull(stack))
        return;
    stack->array[++stack->top] = item;
}

int pop(struct Stack* stack) {
    if (isEmpty(stack))
        return -1;
    return stack->array[stack->top--];
}

int main() {
    struct Stack stack = { -1, 5, malloc(5 * sizeof(int)) };
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    printf("Popped element is %d\n", pop(&stack));
    return 0;
}

4. 队列

队列是一种先进先出（FIFO）的数据结构，元素只能从一端添加，从另一端移除。

应用场景

• 任务调度。
• 缓冲区管理。

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

struct Queue {
    int front, rear, size;
    unsigned capacity;
    int* array;
};

int isFull(struct Queue* queue) {
    return queue->size == queue->capacity;
}

int isEmpty(struct Queue* queue) {
    return queue->size == 0;
}

void enqueue(struct Queue* queue, int item) {
    if (isFull(queue))
        return;
    queue->array[queue->rear++] = item;
    queue->size++;
}

int dequeue(struct Queue* queue) {
    if (isEmpty(queue))
        return -1;
    int item = queue->array[queue->front++];
    queue->size--;
    return item;
}

int main() {
    struct Queue queue = { 0, 0, 5, 5, malloc(5 * sizeof(int)) };
    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);
    printf("Dequeued element is %d\n", dequeue(&queue));
    return 0;
}

5. 树

树是一种非线性数据结构，由节点组成，每个节点包含数据和一个或多个子节点。

应用场景

• 文件系统。
• 组织结构。

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

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

struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

struct Node* insert(struct Node* node, int data) {
    if (node == NULL) return newNode(data);
    if (data < node->data)
        node->left = insert(node->left, data);
    else if (data > node->data)
        node->right = insert(node->right, data);
    return node;
}

int main() {
    struct Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
    return 0;
}

6. 图

图是一种复杂的数据结构，由节点和边组成，节点可以表示实体，边表示实体之间的关系。

应用场景

• 社交网络。
• 路径规划。

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

struct Graph {
    int numVertices;
    int** adjMatrix;
};

struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->numVertices = vertices;
    graph->adjMatrix = (int**)malloc(vertices * sizeof(int*));
    for (int i = 0; i < vertices; i++)
        graph->adjMatrix[i] = (int*)malloc(vertices * sizeof(int));
    for (int i = 0; i < vertices; i++)
        for (int j = 0; j < vertices; j++)
            graph->adjMatrix[i][j] = 0;
    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    graph->adjMatrix[src][dest] = 1;
    graph->adjMatrix[dest][src] = 1;
}

int main() {
    struct Graph* graph = createGraph(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);
    return 0;
}

7. 散列表

散列表是一种基于散列函数的数据结构，用于存储键值对。

应用场景

• 字典。
• 缓存。

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

#define TABLE_SIZE 10

struct HashNode {
    int key;
    int value;
    struct HashNode* next;
};

struct HashTable {
    struct HashNode* hashTable[TABLE_SIZE];
};

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

struct HashTable* createHashTable() {
    struct HashTable* table = (struct HashTable*)malloc(sizeof(struct HashTable));
    for (int i = 0; i < TABLE_SIZE; i++)
        table->hashTable[i] = NULL;
    return table;
}

void insert(struct HashTable* table, int key, int value) {
    int index = hashFunction(key);
    struct HashNode* newNode = (struct HashNode*)malloc(sizeof(struct HashNode));
    newNode->key = key;
    newNode->value = value;
    newNode->next = table->hashTable[index];
    table->hashTable[index] = newNode;
}

int main() {
    struct HashTable* table = createHashTable();
    insert(table, 10, 100);
    insert(table, 20, 200);
    insert(table, 30, 300);
    printf("Value of key 20 is %d\n", table->hashTable[hashFunction(20)]->value);
    return 0;
}

8. 跳表

跳表是一种基于链表的数据结构，通过增加多级索引来提高查找效率。

应用场景

• 实现有序集合。
• 缓存。

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

#define MAX_LEVEL 5

struct Node {
    int key;
    struct Node* forward[MAX_LEVEL];
};

struct Node* createNode(int key) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->key = key;
    for (int i = 0; i < MAX_LEVEL; i++)
        newNode->forward[i] = NULL;
    return newNode;
}

void insert(struct Node** head, int key) {
    struct Node* node = createNode(key);
    struct Node* temp = *head;
    int level = 0;
    while (temp != NULL && level < MAX_LEVEL) {
        node->forward[level] = temp->forward[level];
        temp->forward[level] = node;
        temp = temp->forward[0];
        level++;
    }
    *head = node;
}

int main() {
    struct Node* head = NULL;
    insert(&head, 1);
    insert(&head, 3);
    insert(&head, 5);
    insert(&head, 7);
    insert(&head, 9);
    return 0;
}

9. 堆

堆是一种基于完全二叉树的数据结构，常用于实现优先队列。

应用场景

• 优先队列。
• 排序。

#include <stdio.h>
#include <stdlib.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 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) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    for (int i = n - 1; i >= 0; i--) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    heapSort(arr, n);
    printf("Sorted array is \n");
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

10. 并查集

并查集是一种用于处理一些不交集的合并及查询问题的数据结构。

应用场景

• 路径压缩。
• 查询压缩。

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

#define MAX_SIZE 100

int parent[MAX_SIZE];

int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

void unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY)
        parent[rootX] = rootY;
}

int main() {
    int n = 5;
    parent[0] = 0;
    parent[1] = 1;
    parent[2] = 2;
    parent[3] = 3;
    parent[4] = 4;
    unionSets(1, 2);
    unionSets(2, 3);
    unionSets(4, 5);
    printf("Root of 3 is %d\n", find(3));
    printf("Root of 4 is %d\n", find(4));
    return 0;
}

通过以上对C语言中10种常见数据结构的详解与应用，相信您已经对这些数据结构有了更深入的了解。在实际编程过程中，合理选择和使用数据结构能够使程序更加高效、易读和易维护。希望这些内容对您的学习和实践有所帮助。