学懂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 数组

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

示例：数组求和

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

3.2 链表

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

示例：单链表的基本操作

#include <stdio.h>
#include <stdlib.h>// 节点结构
struct Node {int data;struct Node* next;
};// 创建新节点
struct Node* createNode(int data) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = data;newNode->next = NULL;return newNode;
}// 打印链表
void printList(struct Node* head) {struct Node* temp = head;while (temp != NULL) {printf("%d -> ", temp->data);temp = temp->next;}printf("NULL\n");
}// 插入节点
void insertAtEnd(struct Node** head, int data) {struct Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;return;}struct Node* temp = *head;while (temp->next != NULL) {temp = temp->next;}temp->next = newNode;
}int main() {struct Node* head = NULL;insertAtEnd(&head, 1);insertAtEnd(&head, 2);insertAtEnd(&head, 3);printList(head); // 输出: 1 -> 2 -> 3 -> NULLreturn 0;
}

3.3 栈

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

示例：栈的实现

#include <stdio.h>
#include <stdlib.h>#define MAX 100struct Stack {int top;int arr[MAX];
};// 初始化栈
struct Stack* createStack() {struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));stack->top = -1; // 栈为空return stack;
}// 判断栈是否为空
int isEmpty(struct Stack* stack) {return stack->top == -1;
}// 入栈
void push(struct Stack* stack, int item) {if (stack->top == MAX - 1) {printf("栈溢出\n");return;}stack->arr[++stack->top] = item;
}// 出栈
int pop(struct Stack* stack) {if (isEmpty(stack)) {printf("栈为空\n");return -1;}return stack->arr[stack->top--];
}// 查看栈顶元素
int peek(struct Stack* stack) {if (isEmpty(stack)) {printf("栈为空\n");return -1;}return stack->arr[stack->top];
}int main() {struct Stack* stack = createStack();push(stack, 1);push(stack, 2);push(stack, 3);printf("栈顶元素是: %d\n", peek(stack)); // 输出: 3printf("出栈元素: %d\n", pop(stack)); // 输出: 3printf("栈顶元素是: %d\n", peek(stack)); // 输出: 2return 0;
}

3.4 队列

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

示例：队列的实现

#include <stdio.h>
#include <stdlib.h>#define MAX 100struct Queue {int front, rear;int arr[MAX];
};// 初始化队列
struct Queue* createQueue() {struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));queue->front = queue->rear = -1; // 队列为空return queue;
}// 判断队列是否为空
int isEmpty(struct Queue* queue) {return queue->front == -1;
}// 入队
void enqueue(struct Queue* queue, int item) {if (queue->rear == MAX - 1) {printf("队列满\n");return;}if (isEmpty(queue)) {queue->front = 0;}queue->arr[++queue->rear] = item;
}// 出队
int dequeue(struct Queue* queue) {if (isEmpty(queue)) {printf("队列为空\n");return -1;}int item = queue->arr[queue->front];if (queue->front >= queue->rear) {queue->front = queue->rear = -1; // 队列空了} else {queue->front++;}return item;
}int main() {struct Queue* queue = createQueue();enqueue(queue, 1);enqueue(queue, 2);enqueue(queue, 3);printf("出队元素: %d\n", dequeue(queue)); // 输出: 1printf("出队元素: %d\n", dequeue(queue)); // 输出: 2return 0;
}

3.5 树

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

示例：二叉树的遍历

#include <stdio.h>
#include <stdlib.h>struct Node {int data;struct Node* left;struct Node* right;
};// 创建新节点
struct Node* createNode(int data) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = data;newNode->left = newNode->right = NULL;return newNode;
}// 先序遍历
void preOrder(struct Node* root) {if (root != NULL) {printf("%d ", root->data);preOrder(root->left);preOrder(root->right);}
}// 中序遍历
void inOrder(struct Node* root) {if (root != NULL) {inOrder(root->left);printf("%d ", root->data);inOrder(root->right);}
}// 后序遍历
void postOrder(struct Node* root) {if (root != NULL) {postOrder(root->left);postOrder(root->right);printf("%d ", root->data);}
}int main() {struct Node* root = createNode(1);root->left = createNode(2);root->right = createNode(3);root->left->left = createNode(4);root->left->right = createNode(5);printf("先序遍历: ");preOrder(root); // 输出: 1 2 4 5 3printf("\n");printf("中序遍历: ");inOrder(root); // 输出: 4 2 5 1 3printf("\n");printf("后序遍历: ");postOrder(root); // 输出: 4 5 2 3 1printf("\n");return 0;
}

3.6 图

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

示例：邻接表表示的图

#include <stdio.h>
#include <stdlib.h>struct Node {int dest;struct Node* next;
};struct Graph {int vertices;struct Node** adjLists;
};// 创建图
struct Graph* createGraph(int vertices) {struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));graph->vertices = vertices;graph->adjLists = (struct Node**)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 = (struct Node*)malloc(sizeof(struct Node));newNode->dest = dest;newNode->next = graph->adjLists[src];graph->adjLists[src] = newNode;
}// 打印图
void printGraph(struct Graph* graph) {for (int v = 0; v < graph->vertices; v++) {struct Node* temp = graph->adjLists[v];printf("\n 对于顶点 %d: ", v);while (temp) {printf("%d -> ", temp->dest);temp = temp->next;}printf("NULL");}
}int main() {struct Graph* graph = createGraph(5);addEdge(graph, 0, 1);addEdge(graph, 0, 4);addEdge(graph, 1, 2);addEdge(graph, 1, 3);addEdge(graph, 1, 4);addEdge(graph, 2, 3);addEdge(graph, 3, 4);printGraph(graph); // 打印图的邻接表表示return 0;
}

3.7 排序与查找

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

示例：快速排序

#include <stdio.h>void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}int partition(int arr[], int low, int high) {int pivot = arr[high];int i = (low - 1);for (int j = low; j < high; 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);}
}int main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1);printf("排序后的数组: \n");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}

示例：冒泡排序

#include <stdio.h>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]) {// 交换 arr[j] 和 arr[j+1]int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);bubbleSort(arr, n);printf("排序后的数组: \n");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}