devbox
盐析白兔
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

学懂C语言（四十）：C语言 数据结构与算法详解

作者：盐析白兔 | 2024-08-09 06:59:48

赞

踩

学懂C语言（四十）：C语言 数据结构与算法详解

目录

1. 数据结构概述

2. 常见算法

3. C语言实现示例

3.1 数组

3.2 链表

3.3 栈

3.4 队列

3.5 树

3.6 图

3.7 排序与查找

示例：冒泡排序

4. 总结

数据结构与算法是计算机科学的核心内容，C语言作为底层编程语言，广泛用于实现各种数据结构和算法。下面将详细讨论一些常见的数据结构及其相关算法。

1. 数据结构概述

数据结构是特定方式组织和存储数据的集合，以便高效地访问和修改。常见的数据结构包括：

  • 线性数据结构

    • 数组：固定大小的元素集合，支持随机访问。
    • 链表：节点组成的集合，每个节点包含数据和指向下一个节点的指针。
      • 单链表：每个节点指向下一个节点。
      • 双链表：每个节点指向前一个和后一个节点。
      • 循环链表：最后一个节点指向第一个节点。

  • 栈：后进先出（LIFO）结构。常用于函数调用管理、表达式求值等。

    • 操作：push（入栈）、pop（出栈）、peek（查看栈顶元素）。

  • 队列：先进先出（FIFO）结构。常用于任务调度、缓冲区管理等。

    • 操作：enqueue（入队）、dequeue（出队）、front（查看队首元素）。

  • 树

    • 二叉树：每个节点最多有两个子节点。
    • 二叉搜索树：左子树所有节点小于根节点，右子树所有节点大于根节点。
    • 平衡树：如 AVL 树、红黑树，保持树的平衡性以提高查询效率。
    • 堆：完全二叉树，满足堆性质（最大堆或最小堆）。

  • 图：由顶点和边组成的结构，表示对象之间的关系。

    • 表示方式：邻接矩阵、邻接表。

  • 哈希表：通过哈希函数将键映射到数组索引，提供快速的查找和插入。

2. 常见算法

算法是对解决特定问题的步骤和逻辑的描述。常见算法包括：

  • 排序算法

    • 冒泡排序：重复遍历数组，比较相邻元素并交换，直到排序完成。
    • 选择排序：每次选择最小的元素，将其放到已排序部分的末尾。
    • 插入排序：将数组分为已排序和未排序部分，逐个插入未排序元素。
    • 快速排序：选择基准元素，将数组分为小于和大于基准的两部分，递归排序。
    • 归并排序：分治法将数组分为两部分，分别排序后合并。

  • 查找算法

    • 线性查找：逐个比较，找到目标元素。
    • 二分查找：在已排序数组中，通过不断将搜索范围减半来查找目标元素。

  • 图算法

    • 深度优先搜索（DFS）：从一个节点出发，尽可能深入到每个分支，再回溯。
    • 广度优先搜索（BFS）：从一个节点出发，先访问所有相邻节点，再从这些节点访问它们的邻居。
    • Dijkstra 算法：求解单源最短路径的贪心算法。
    • A 算法*：启发式搜索算法，常用于路径寻找。

  • 动态规划

    • 解决最优子结构问题，通过保存子问题的结果来减少计算。
    • 常见问题：斐波那契数列、背包问题、最长公共子序列等。

3. C语言实现示例

3.1 数组

数组是一种线性数据结构，支持随机访问。

示例：数组求和

  1. #include <stdio.h>
  2.  
  3. int main() {
  4.     int arr[] = {1, 2, 3, 4, 5};
  5.     int sum = 0;
  6.     int n = sizeof(arr) / sizeof(arr[0]);
  7.  
  8.     for (int i = 0; i < n; i++) {
  9.         sum += arr[i]; // 累加
  10.     }
  11.  
  12.     printf("数组元素的和是: %d\n", sum);
  13.     return 0;
  14. }
3.2 链表

链表是一种动态数据结构，由节点组成，每个节点包含数据和指向下一个节点的指针。

示例：单链表的基本操作

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. // 节点结构
  5. struct Node {
  6.     int data;
  7.     struct Node* next;
  8. };
  9.  
  10. // 创建新节点
  11. struct Node* createNode(int data) {
  12.     struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  13.     newNode->data = data;
  14.     newNode->next = NULL;
  15.     return newNode;
  16. }
  17.  
  18. // 打印链表
  19. void printList(struct Node* head) {
  20.     struct Node* temp = head;
  21.     while (temp != NULL) {
  22.         printf("%d -> ", temp->data);
  23.         temp = temp->next;
  24.     }
  25.     printf("NULL\n");
  26. }
  27.  
  28. // 插入节点
  29. void insertAtEnd(struct Node** head, int data) {
  30.     struct Node* newNode = createNode(data);
  31.     if (*head == NULL) {
  32.         *head = newNode;
  33.         return;
  34.     }
  35.     struct Node* temp = *head;
  36.     while (temp->next != NULL) {
  37.         temp = temp->next;
  38.     }
  39.     temp->next = newNode;
  40. }
  41.  
  42. int main() {
  43.     struct Node* head = NULL;
  44.     insertAtEnd(&head, 1);
  45.     insertAtEnd(&head, 2);
  46.     insertAtEnd(&head, 3);
  47.     printList(head); // 输出: 1 -> 2 -> 3 -> NULL
  48.  
  49.     return 0;
  50. }
3.3 栈

栈是一种后进先出（LIFO）结构，常用于函数调用管理。

示例：栈的实现

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define MAX 100
  5.  
  6. struct Stack {
  7.     int top;
  8.     int arr[MAX];
  9. };
  10.  
  11. // 初始化栈
  12. struct Stack* createStack() {
  13.     struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
  14.     stack->top = -1; // 栈为空
  15.     return stack;
  16. }
  17.  
  18. // 判断栈是否为空
  19. int isEmpty(struct Stack* stack) {
  20.     return stack->top == -1;
  21. }
  22.  
  23. // 入栈
  24. void push(struct Stack* stack, int item) {
  25.     if (stack->top == MAX - 1) {
  26.         printf("栈溢出\n");
  27.         return;
  28.     }
  29.     stack->arr[++stack->top] = item;
  30. }
  31.  
  32. // 出栈
  33. int pop(struct Stack* stack) {
  34.     if (isEmpty(stack)) {
  35.         printf("栈为空\n");
  36.         return -1;
  37.     }
  38.     return stack->arr[stack->top--];
  39. }
  40.  
  41. // 查看栈顶元素
  42. int peek(struct Stack* stack) {
  43.     if (isEmpty(stack)) {
  44.         printf("栈为空\n");
  45.         return -1;
  46.     }
  47.     return stack->arr[stack->top];
  48. }
  49.  
  50. int main() {
  51.     struct Stack* stack = createStack();
  52.     push(stack, 1);
  53.     push(stack, 2);
  54.     push(stack, 3);
  55.  
  56.     printf("栈顶元素是: %d\n", peek(stack)); // 输出: 3
  57.     printf("出栈元素: %d\n", pop(stack)); // 输出: 3
  58.     printf("栈顶元素是: %d\n", peek(stack)); // 输出: 2
  59.  
  60.     return 0;
  61. }
3.4 队列

队列是一种先进先出（FIFO）结构，常用于任务调度和缓冲区管理。

示例：队列的实现

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define MAX 100
  5.  
  6. struct Queue {
  7.     int front, rear;
  8.     int arr[MAX];
  9. };
  10.  
  11. // 初始化队列
  12. struct Queue* createQueue() {
  13.     struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
  14.     queue->front = queue->rear = -1; // 队列为空
  15.     return queue;
  16. }
  17.  
  18. // 判断队列是否为空
  19. int isEmpty(struct Queue* queue) {
  20.     return queue->front == -1;
  21. }
  22.  
  23. // 入队
  24. void enqueue(struct Queue* queue, int item) {
  25.     if (queue->rear == MAX - 1) {
  26.         printf("队列满\n");
  27.         return;
  28.     }
  29.     if (isEmpty(queue)) {
  30.         queue->front = 0;
  31.     }
  32.     queue->arr[++queue->rear] = item;
  33. }
  34.  
  35. // 出队
  36. int dequeue(struct Queue* queue) {
  37.     if (isEmpty(queue)) {
  38.         printf("队列为空\n");
  39.         return -1;
  40.     }
  41.     int item = queue->arr[queue->front];
  42.     if (queue->front >= queue->rear) {
  43.         queue->front = queue->rear = -1; // 队列空了
  44.     } else {
  45.         queue->front++;
  46.     }
  47.     return item;
  48. }
  49.  
  50. int main() {
  51.     struct Queue* queue = createQueue();
  52.     enqueue(queue, 1);
  53.     enqueue(queue, 2);
  54.     enqueue(queue, 3);
  55.     
  56.     printf("出队元素: %d\n", dequeue(queue)); // 输出: 1
  57.     printf("出队元素: %d\n", dequeue(queue)); // 输出: 2
  58.  
  59.     return 0;
  60. }
3.5 树

树是一种分层数据结构，常用于表示层级关系。

示例：二叉树的遍历

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. struct Node {
  5.     int data;
  6.     struct Node* left;
  7.     struct Node* right;
  8. };
  9.  
  10. // 创建新节点
  11. struct Node* createNode(int data) {
  12.     struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  13.     newNode->data = data;
  14.     newNode->left = newNode->right = NULL;
  15.     return newNode;
  16. }
  17.  
  18. // 先序遍历
  19. void preOrder(struct Node* root) {
  20.     if (root != NULL) {
  21.         printf("%d ", root->data);
  22.         preOrder(root->left);
  23.         preOrder(root->right);
  24.     }
  25. }
  26.  
  27. // 中序遍历
  28. void inOrder(struct Node* root) {
  29.     if (root != NULL) {
  30.         inOrder(root->left);
  31.         printf("%d ", root->data);
  32.         inOrder(root->right);
  33.     }
  34. }
  35.  
  36. // 后序遍历
  37. void postOrder(struct Node* root) {
  38.     if (root != NULL) {
  39.         postOrder(root->left);
  40.         postOrder(root->right);
  41.         printf("%d ", root->data);
  42.     }
  43. }
  44.  
  45. int main() {
  46.     struct Node* root = createNode(1);
  47.     root->left = createNode(2);
  48.     root->right = createNode(3);
  49.     root->left->left = createNode(4);
  50.     root->left->right = createNode(5);
  51.  
  52.     printf("先序遍历: ");
  53.     preOrder(root); // 输出: 1 2 4 5 3
  54.     printf("\n");
  55.  
  56.     printf("中序遍历: ");
  57.     inOrder(root); // 输出: 4 2 5 1 3
  58.     printf("\n");
  59.  
  60.     printf("后序遍历: ");
  61.     postOrder(root); // 输出: 4 5 2 3 1
  62.     printf("\n");
  63.  
  64.     return 0;
  65. }
3.6 图

图是由顶点和边组成的结构，表示对象之间的关系。

示例：邻接表表示的图

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. struct Node {
  5.     int dest;
  6.     struct Node* next;
  7. };
  8.  
  9. struct Graph {
  10.     int vertices;
  11.     struct Node** adjLists;
  12. };
  13.  
  14. // 创建图
  15. struct Graph* createGraph(int vertices) {
  16.     struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
  17.     graph->vertices = vertices;
  18.     graph->adjLists = (struct Node**)malloc(vertices * sizeof(struct Node*));
  19.  
  20.     for (int i = 0; i < vertices; i++) {
  21.         graph->adjLists[i] = NULL;
  22.     }
  23.     return graph;
  24. }
  25.  
  26. // 添加边
  27. void addEdge(struct Graph* graph, int src, int dest) {
  28.     struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  29.     newNode->dest = dest;
  30.     newNode->next = graph->adjLists[src];
  31.     graph->adjLists[src] = newNode;
  32. }
  33.  
  34. // 打印图
  35. void printGraph(struct Graph* graph) {
  36.     for (int v = 0; v < graph->vertices; v++) {
  37.         struct Node* temp = graph->adjLists[v];
  38.         printf("\n 对于顶点 %d: ", v);
  39.         while (temp) {
  40.             printf("%d -> ", temp->dest);
  41.             temp = temp->next;
  42.         }
  43.         printf("NULL");
  44.     }
  45. }
  46.  
  47. int main() {
  48.     struct Graph* graph = createGraph(5);
  49.     addEdge(graph, 0, 1);
  50.     addEdge(graph, 0, 4);
  51.     addEdge(graph, 1, 2);
  52.     addEdge(graph, 1, 3);
  53.     addEdge(graph, 1, 4);
  54.     addEdge(graph, 2, 3);
  55.     addEdge(graph, 3, 4);
  56.  
  57.     printGraph(graph); // 打印图的邻接表表示
  58.  
  59.     return 0;
  60. }
3.7 排序与查找

排序与查找是常见的算法问题，涉及如何组织数据以便于访问。

示例：快速排序

  1. #include <stdio.h>
  2.  
  3. void swap(int* a, int* b) {
  4.     int temp = *a;
  5.     *a = *b;
  6.     *b = temp;
  7. }
  8.  
  9. int partition(int arr[], int low, int high) {
  10.     int pivot = arr[high];
  11.     int i = (low - 1);
  12.     for (int j = low; j < high; j++) {
  13.         if (arr[j] < pivot) {
  14.             i++;
  15.             swap(&arr[i], &arr[j]);
  16.         }
  17.     }
  18.     swap(&arr[i + 1], &arr[high]);
  19.     return (i + 1);
  20. }
  21.  
  22. void quickSort(int arr[], int low, int high) {
  23.     if (low < high) {
  24.         int pi = partition(arr, low, high);
  25.         quickSort(arr, low, pi - 1);
  26.         quickSort(arr, pi + 1, high);
  27.     }
  28. }
  29.  
  30. int main() {
  31.     int arr[] = {10, 7, 8, 9, 1, 5};
  32.     int n = sizeof(arr) / sizeof(arr[0]);
  33.     quickSort(arr, 0, n - 1);
  34.     printf("排序后的数组: \n");
  35.     for (int i = 0; i < n; i++) {
  36.         printf("%d ", arr[i]);
  37.     }
  38.     return 0;
  39. }
示例：冒泡排序
  1. #include <stdio.h>
  2.  
  3. void bubbleSort(int arr[], int n) {
  4.     for (int i = 0; i < n - 1; i++) {
  5.         for (int j = 0; j < n - i - 1; j++) {
  6.             if (arr[j] > arr[j + 1]) {
  7.                 // 交换 arr[j] 和 arr[j+1]
  8.                 int temp = arr[j];
  9.                 arr[j] = arr[j + 1];
  10.                 arr[j + 1] = temp;
  11.             }
  12.         }
  13.     }
  14. }
  15.  
  16. int main() {
  17.     int arr[] = {64, 34, 25, 12, 22, 11, 90};
  18.     int n = sizeof(arr) / sizeof(arr[0]);
  19.     bubbleSort(arr, n);
  20.     printf("排序后的数组: \n");
  21.     for (int i = 0; i < n; i++) {
  22.         printf("%d ", arr[i]);
  23.     }
  24.     return 0;
  25. }

4. 总结

通过以上实例，可以更好地理解 C 语言中的数据结构与算法。这些结构与算法是编程的基石，掌握它们对于解决复杂问题至关重要。建议通过实际编程练习、参加算法竞赛等方式，不断提升自己的能力和经验。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/952017
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号