解锁C语言数据结构实战：50个经典练习题破解编程难题

引言

C语言因其高效性和灵活性，在编程领域拥有广泛的应用。数据结构是C语言编程中不可或缺的一部分，它能够帮助我们高效地处理数据。本文将带领读者通过50个经典练习题，深入理解C语言中的数据结构，提升编程能力。

练习题解析

1. 单链表实现

实现一个单链表，包括插入、删除、查找等功能。

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

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

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

void insertNode(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

void deleteNode(Node** head, int data) {
    Node* temp = *head, *prev = NULL;
    while (temp != NULL && temp->data != data) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return;
    if (prev == NULL) *head = temp->next;
    else prev->next = temp->next;
    free(temp);
}

2. 双向链表实现

实现一个双向链表，包括插入、删除、查找等功能。

typedef struct DoublyNode {
    int data;
    struct DoublyNode* prev;
    struct DoublyNode* next;
} DoublyNode;

DoublyNode* createDoublyNode(int data) {
    DoublyNode* newNode = (DoublyNode*)malloc(sizeof(DoublyNode));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

void insertDoublyNode(DoublyNode** head, int data) {
    DoublyNode* newNode = createDoublyNode(data);
    newNode->next = *head;
    if (*head != NULL) (*head)->prev = newNode;
    *head = newNode;
}

3. 栈实现

实现一个栈，包括入栈、出栈、判断栈空等功能。

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

#define MAX_SIZE 100

typedef struct Stack {
    int data[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack* s) {
    s->top = -1;
}

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

void push(Stack* s, int data) {
    if (s->top == MAX_SIZE - 1) return;
    s->data[++s->top] = data;
}

int pop(Stack* s) {
    if (isEmpty(s)) return -1;
    return s->data[s->top--];
}

4. 队列实现

实现一个队列，包括入队、出队、判断队空等功能。

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

#define MAX_SIZE 100

typedef struct Queue {
    int data[MAX_SIZE];
    int front;
    int rear;
} Queue;

void initQueue(Queue* q) {
    q->front = q->rear = 0;
}

int isEmpty(Queue* q) {
    return q->front == q->rear;
}

void enqueue(Queue* q, int data) {
    if ((q->rear + 1) % MAX_SIZE == q->front) return;
    q->data[q->rear] = data;
    q->rear = (q->rear + 1) % MAX_SIZE;
}

int dequeue(Queue* q) {
    if (isEmpty(q)) return -1;
    int data = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return data;
}

5. 二叉树遍历

实现二叉树的先序、中序、后序遍历。

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

void preOrder(TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preOrder(root->left);
    preOrder(root->right);
}

void inOrder(TreeNode* root) {
    if (root == NULL) return;
    inOrder(root->left);
    printf("%d ", root->data);
    inOrder(root->right);
}

void postOrder(TreeNode* root) {
    if (root == NULL) return;
    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->data);
}

6. 字典树（Trie）实现

实现一个字典树，包括插入、查找、前缀匹配等功能。

typedef struct TrieNode {
    char ch;
    struct TrieNode* children[26];
    int isEndOfWord;
} TrieNode;

TrieNode* createNode(char ch) {
    TrieNode* newNode = (TrieNode*)malloc(sizeof(TrieNode));
    newNode->ch = ch;
    for (int i = 0; i < 26; i++)
        newNode->children[i] = NULL;
    newNode->isEndOfWord = 0;
    return newNode;
}

void insert(TrieNode* root, char* key) {
    TrieNode* curr = root;
    for (int i = 0; key[i]; i++) {
        int index = key[i] - 'a';
        if (!curr->children[index])
            curr->children[index] = createNode(key[i]);
        curr = curr->children[index];
    }
    curr->isEndOfWord = 1;
}

7. 线性查找和二分查找

实现线性查找和二分查找算法。

int linearSearch(int arr[], int size, int x) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == x) return i;
    }
    return -1;
}

int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (arr[m] == x) return m;
        if (arr[m] < x) l = m + 1;
        else r = m - 1;
    }
    return -1;
}

8. 快速排序和归并排序

实现快速排序和归并排序算法。

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

9. 哈希表实现

实现一个哈希表，包括插入、删除、查找等功能。

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

#define TABLE_SIZE 10

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

HashNode* createNode(int key, int value) {
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    newNode->key = key;
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

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

void insert(HashNode** hashTable, int key, int value) {
    int index = hash(key);
    HashNode* newNode = createNode(key, value);
    newNode->next = hashTable[index];
    hashTable[index] = newNode;
}

int find(HashNode** hashTable, int key) {
    int index = hash(key);
    HashNode* temp = hashTable[index];
    while (temp != NULL) {
        if (temp->key == key) return temp->value;
        temp = temp->next;
    }
    return -1;
}

void delete(HashNode** hashTable, int key) {
    int index = hash(key);
    HashNode* temp = hashTable[index], *prev = NULL;
    while (temp != NULL && temp->key != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return;
    if (prev == NULL) hashTable[index] = temp->next;
    else prev->next = temp->next;
    free(temp);
}

10. 动态规划求解斐波那契数列

使用动态规划算法求解斐波那契数列。

int fibonacci(int n) {
    if (n <= 1) return n;
    int fib[n + 1];
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib[n];
}

11. 递归求解汉诺塔问题

使用递归算法求解汉诺塔问题。

void hanoi(int n, char from_rod, char to_rod, char aux_rod) {
    if (n == 1) {
        printf("Move disk 1 from rod %c to rod %c\n", from_rod, to_rod);
        return;
    }
    hanoi(n - 1, from_rod, aux_rod, to_rod);
    printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod);
    hanoi(n - 1, aux_rod, to_rod, from_rod);
}

12. 冒泡排序和选择排序

实现冒泡排序和选择排序算法。

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int t = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = t;
            }
        }
    }
}

void selectionSort(int arr[], int n) {
    int min_idx;
    for (int i = 0; i < n - 1; i++) {
        min_idx = i;
        for (int j = i + 1; j < n; j++)
            if (arr[j] < arr[min_idx]) min_idx = j;
        int t = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = t;
    }
}

13. 插入排序和希尔排序

实现插入排序和希尔排序算法。

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

void shellSort(int arr[], int n) {
    int gap, i, j, temp;
    for (gap = n / 2; gap > 0; gap /= 2) {
        for (i = gap; i < n; i++) {
            temp = arr[i];
            j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

14. 合并排序和归并排序

实现合并排序和归并排序算法。

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

15. 稳定排序和非稳定排序

了解稳定排序和非稳定排序的概念。

稳定排序：在排序过程中，相同元素的相对顺序不会改变。

非稳定排序：在排序过程中，相同元素的相对顺序可能会改变。

常见的稳定排序：插入排序、冒泡排序、归并排序。

常见的非稳定排序：快速排序、选择排序、希尔排序。

16. 最长公共子序列（LCS）

使用动态规划算法求解最长公共子序列（LCS）问题。

int lcs(int X[], int m, int Y[], int n) {
    int L[m + 1][n + 1];

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                L[i][j] = 0;
            else if (X[i - 1] == Y[j - 1])
                L[i][j] = L[i - 1][j - 1] + 1;
            else
                L[i][j] = (L[i - 1][j] > L[i][j - 1]) ? L[i - 1][j] : L[i][j - 1];
        }
    }
    return L[m][n];
}

17. 最小生成树（Prim算法）

使用Prim算法求解最小生成树问题。

#include <limits.h>

void minKey(int key[], int mstSet[], int V) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++)
        if (mstSet[v] == 0 && key[v] < min)
            min = key[v], min_index = v;
    return min_index;
}

void primMST(int graph[V][V]) {
    int parent[V];
    int key[V];
    int mstSet[V];

    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX, mstSet[i] = 0;
    }

    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet, V);
        mstSet[u] = 1;

        for (int v = 0; v < V; v++)
            if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v])
                parent[v] = u, key[v] = graph[u][v];
    }

    printMST(parent, graph, V);
}

18. 最短路径（Dijkstra算法）

使用Dijkstra算法求解最短路径问题。

”`c #include

void minDistance(int dist[], int sptSet[], int V) {

int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
    if (sptSet[v] == 0 && dist[v] <= min)
        min = dist[v], min_index = v;
return min_index;

}

void dijkstra(int graph[V][V], int src) {

int dist[V];
int sptSet[V];

for (

正文

解锁C语言数据结构实战：50个经典练习题破解编程难题

引言

练习题解析

1. 单链表实现

2. 双向链表实现

3. 栈实现

4. 队列实现

5. 二叉树遍历

6. 字典树（Trie）实现

7. 线性查找和二分查找

8. 快速排序和归并排序

9. 哈希表实现

10. 动态规划求解斐波那契数列

11. 递归求解汉诺塔问题

12. 冒泡排序和选择排序

13. 插入排序和希尔排序

14. 合并排序和归并排序

15. 稳定排序和非稳定排序

16. 最长公共子序列（LCS）

17. 最小生成树（Prim算法）

18. 最短路径（Dijkstra算法）

相关阅读

破解浮力难题，轻松掌握解题技巧——浮力练习题答案全解析

掌握CAD绘图技巧，挑战300例经典练习题解析全解析

掌握CAD绘图技巧，挑战实战练习题解析攻略

揭秘古代汉语奥秘：精选练习题答案解析，轻松掌握古文精髓

破解反弹高度：实战练习题解析，轻松提升跳高技巧

掌握消防技能，轻松应对火场挑战：消防设施操作员必练真题解析

揭秘消费者心理：实战练习题助你掌握需求洞察技巧

掌握跑步技巧，轻松解决往返跑难题

形容词变副词，轻松掌握语法技巧挑战赛！

破解形容词奥秘：轻松掌握英语形容词实战技巧大揭秘