目录
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 -> NULL return 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)); // 输出: 3 printf("出栈元素: %d\n", pop(stack)); // 输出: 3 printf("栈顶元素是: %d\n", peek(stack)); // 输出: 2 return 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)); // 输出: 1 printf("出队元素: %d\n", dequeue(queue)); // 输出: 2 return 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 3 printf("\n"); printf("中序遍历: "); inOrder(root); // 输出: 4 2 5 1 3 printf("\n"); printf("后序遍历: "); postOrder(root); // 输出: 4 5 2 3 1 printf("\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;}4. 总结
通过以上实例，可以更好地理解 C 语言中的数据结构与算法。这些结构与算法是编程的基石，掌握它们对于解决复杂问题至关重要。建议通过实际编程练习、参加算法竞赛等方式，不断提升自己的能力和经验。