C++数据结构深入理解：练习题助你精通原理与应用

 # 摘要 本文从C++语言的角度出发，深入探讨了数据结构的基本原理和实践技巧。文章首先介绍了数据结构的重要性，分类，以及C++标准模板库（STL）。随后，通过具体实践技巧，讲解了线性表、栈、队列、树结构的实现和应用。第三章详述了图结构、字符串匹配算法以及散列表和哈希算法的高级应用。第四章则着重于数据结构在算法中的应用，包括排序和搜索算法的优化。最后，文章通过综合练习题的分析与解答，加深了对数据结构理论和实践相结合的理解。整体而言，本文旨在为读者提供一个全面的C++数据结构学习路径，同时强调理论与实践相结合的重要性。 # 关键字 C++；数据结构；时间复杂度；空间复杂度；算法应用；实践技巧 参考资源链接：[50道C++编程练习题及解答.doc](https://wenku.csdn.net/doc/6401ad3dcce7214c316eecfb?spm=1055.2635.3001.10343) # 1. C++数据结构概述与原理 ## 1.1 数据结构的定义与重要性 数据结构是组织和存储数据的方式，它影响着算法的效率和软件的性能。一个良好的数据结构选择可以减少算法的时间复杂度，优化内存使用，使问题解决更高效。 ## 1.2 C++中数据结构的分类 C++中的数据结构可以分为两大类：线性数据结构如数组、链表、栈和队列；非线性数据结构如树、图。理解这些数据结构的基本特性对于选择合适的数据结构来解决特定问题是至关重要的。 ## 1.3 时间复杂度和空间复杂度分析 时间和空间复杂度是衡量算法效率的两个重要指标。时间复杂度描述了算法执行所需时间的增长趋势，而空间复杂度则描述了算法运行过程中占用存储空间的增长趋势。 ## 1.4 C++标准模板库（STL）概览 STL是C++库的一个重要组成部分，它提供了一系列模板类和函数来实现常用数据结构和算法。熟悉STL的容器、迭代器、函数对象以及算法可以帮助开发者更加高效地进行软件开发。 # 2. 基础数据结构的实践技巧 ## 2.1 线性表的实现 ### 2.1.1 数组与链表的比较 数组和链表是两种最基础的数据结构，它们在计算机科学中的地位至关重要。尽管它们在实现线性表时都各有千秋，但其内在的差异导致它们在性能上的表现各有优劣。 数组是一种基于连续内存空间的数据结构，它允许通过索引快速访问任何元素。这种特性使得数组的随机访问非常高效，但在添加或删除元素时需要移动大量元素以保持连续性，这导致其插入和删除操作的效率较低。 相比之下，链表则不需要连续的内存空间，每个节点存储数据以及指向下一个节点的指针。这使得链表在插入和删除操作上非常高效，因为只需要修改指针即可。然而，链表的缺点是其不支持随机访问，要访问第n个元素需要从头节点开始顺序访问，这使得其访问效率较低。 #### 数组的实现特点： - **空间连续性**：所有元素的内存地址是连续的。 - **时间复杂度**：随机访问的时间复杂度为O(1)，插入和删除操作（在非尾部）的时间复杂度为O(n)。 - **内存分配**：一次性分配整块连续内存空间。 - **适用场景**：适用于读操作多，插入和删除操作少的场景。 #### 链表的实现特点： - **空间不连续**：元素之间通过指针链接，内存空间不需要连续。 - **时间复杂度**：访问任意元素的时间复杂度为O(n)，插入和删除操作的时间复杂度为O(1)，如果已知具体节点位置。 - **内存分配**：动态分配，按需申请内存空间。 - **适用场景**：适用于插入和删除操作频繁的场景。 ### 2.1.2 动态数组（vector）的使用和原理 动态数组，或称为向量（在C++中称为vector），是一种封装了动态内存管理功能的数组类型，它能够根据元素的添加和删除动态地调整自己的大小。 动态数组的核心特性是提供了类似数组的索引访问方式，同时支持动态调整大小。当向量的大小超过当前分配的内存时，它会自动创建一个更大的内存空间，将原有元素复制过去，并释放原有空间。这个过程对用户是透明的，因此使用起来非常方便。 #### 动态数组实现原理： - **内存管理**：当数组空间不足时，动态扩展数组容量。通常采用容量翻倍的策略，即创建一个新的更大的数组，并将原数组的数据复制过去。 - **时间复杂度**：随机访问仍然是O(1)，插入和删除操作在平均情况下为O(1)，但在最坏情况下（即扩容时）会涉及到大量数据的复制，此时时间复杂度为O(n)。 - **迭代器支持**：大多数动态数组提供迭代器支持，允许高效地遍历元素。 #### 动态数组的使用示例代码： ```cpp #include <iostream> #include <vector> int main() { std::vector<int> vec; // 创建一个int类型的动态数组 // 动态添加元素 for (int i = 0; i < 10; ++i) { vec.push_back(i); // 使用push_back向向量尾部添加元素 } // 遍历向量 for (int num : vec) { std::cout << num << " "; // 输出向量中的每个元素 } return 0; } ``` 在上述代码中，我们创建了一个int类型的vector，向其添加了10个整数，并使用范围for循环进行遍历。由于vector在C++中广泛使用，它是线性表实践技巧中不可或缺的部分。 # 3. 高级数据结构详解与应用 ## 3.1 图的表示与算法 ### 3.1.1 图的概念及其存储结构 图是一种复杂的数据结构，它由顶点（vertices）和边（edges）组成，可以用来描述元素之间的关系。图的表示方法主要分为邻接矩阵和邻接表。邻接矩阵是一个二维数组，其中索引代表顶点，矩阵的值表示边的存在与否及其权重。邻接表则使用链表来存储每个顶点的邻接顶点，适用于边数较少的情况。 为了更好地理解图的存储结构，我们来看下面的代码块，展示了一个简单的图的邻接矩阵的实现。 ```cpp #include <vector> // 图的类定义 class Graph { private: int numVertices; // 顶点的数量 std::vector<std::vector<int>> adjMatrix; // 邻接矩阵 public: Graph(int numVertices) : numVertices(numVertices), adjMatrix(numVertices, std::vector<int>(numVertices, 0)) {} // 添加边 void addEdge(int i, int j) { adjMatrix[i][j] = 1; // 有向图 // 如果是无向图，还需要加上下面这行 // adjMatrix[j][i] = 1; } // 打印邻接矩阵 void printMatrix() { for (int i = 0; i < numVertices; ++i) { for (int j = 0; j < numVertices; ++j) { std::cout << adjMatrix[i][j] << " "; } std::cout << std::endl; } } }; int main() { Graph g(4); // 创建一个拥有4个顶点的图 g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.printMatrix(); // 打印邻接矩阵 return 0; } ``` 这段代码定义了一个`Graph`类，使用邻接矩阵来存储图的信息。`addEdge`函数用于添加边，通过将对应的矩阵位置标记为1来表示顶点间的连接。`printMatrix`函数用于打印图的邻接矩阵，帮助我们直观地看到图的结构。 在逻辑分析中，我们首先创建了一个包含四个顶点的图实例。然后，我们添加了五条边来构建图的结构，最后打印出了邻接矩阵。 理解图的存储结构对于实现图的相关算法至关重要，例如图的遍历（深度优先搜索与广度优先搜索）和最短路径算法（如Dijkstra与Floyd-Warshall算法）。 ### 3.1.2 图的遍历算法（深度优先搜索与广度优先搜索） 图的遍历算法用于访问图中的每个顶点一次。其中，深度优先搜索（DFS）和广度优先搜索（BFS）是最常用的两种图遍历算法。 #### 深度优先搜索（DFS） 深度优先搜索从初始顶点开始，沿着一条路径深入直到无法继续，然后回溯到上一个分叉点继续搜索。 ```cpp void DFSUtil(int v, std::vector<bool>& visited) { // 标记当前顶点为已访问 visited[v] = true; std::cout << v << " "; // 递归访问所有未访问的邻居 for (int i = 0; i < adjMatrix.size(); ++i) { if (adjMatrix[v][i] == 1 && !visited[i]) { DFSUtil(i, visited); } } } void DFS(int startVertex) { std::vector<bool> visited(adjMatrix.size(), false); DFSUtil(startVertex, visited); } // 示例调用 int main() { Graph g(4); // 添加边的代码省略，参见上一节代码示例 DFS(0); // 以顶点0开始进行DFS遍历 return 0; } ``` 这段代码中，我们实现了DFS算法。通过递归函数`DFSUtil`，我们从一个顶点开始，访问所有未被访问的邻接顶点，直到所有顶点都被访问。`DFS`函数初始化一个访问状态数组，然后调用`DFSUtil`函数开始搜索。 #### 广度优先搜索（BFS） 广度优先搜索逐层访问图中的所有顶点，从起始顶点开始，先访问所有邻接顶点，然后再对这些邻接顶点的邻接顶点进行访问。 ```cpp #include <queue> void BFS(int startVertex) { std::vector<bool> visited(adjMatrix.size(), false); std::queue<int> q; visited[startVertex] = true; q.push(startVertex); while (!q.empty()) { int v = q.front(); q.pop(); std::cout << v << " "; for (int i = 0; i < adjMatrix.size(); ++i) { if (adjMatrix[v][i] == 1 && !visited[i]) { visited[i] = true; q.push(i); } } } } // 示例调用 int main() { Graph g(4); // 添加边的代码省略，参见上一节代码示例 BFS(0); // 以顶点0开始进行BFS遍历 return 0; } ``` 在这个BFS算法实现中，我们使用了队列来存储待访问的顶点。算法开始时，将起始顶点加入队列，并标记为已访问。随后，不断地从队列中取出顶点进行访问，并将其未被访问的邻接顶点加入队列。 深度优先搜索与广度优先搜索的选择取决于具体问题的需求，DFS适用于寻找路径和检测环，而BFS适用于最短路径问题和层次遍历。 ### 3.1.3 最短路径算法（Dijkstra与Floyd-Warshall） #### Dijkstra算法 Dijkstra算法用于在带权图中寻找最短路径，适用于没有负权边的图。Dijkstra算法使用优先队列来优化搜索效率，是一种贪心算法。 ```cpp #include <iostream> #include <queue> #include <climits> void Dijkstra(const std::vector<std::vector<int>>& adjMatrix, int startVertex) { int numVertices = adjMatrix.size(); std::vector<int> dist(numVertices, INT_MAX); // 存储从起始点到每个点的最短距离 std::vector<bool> visited(numVertices, false); std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq; dist[startVertex] = 0; pq.push({0, startVertex}); while (!pq.empty()) { int u = pq.top().second; pq.pop(); if (visited[u]) continue; visited[u] = true; for (int v = 0; v < numVertices; ++v) { if (!visited[v] && adjMatrix[u][v] && dist[u] != INT_MAX && dist[u] + adjMatrix[u][v] < dist[v]) { dist[v] = dist[u] + adjMatrix[u][v]; pq.push({dist[v], v}); } } } // 打印结果 for (int i = 0; i < numVertices; ++i) { std::cout << "Vertex " << i << " Distance from Source " << startVertex << " : " << dist[i] << std::endl; } } // 示例调用 int main() { Graph g(9); // 创建一个拥有9个顶点的图 // 添加边和权重的代码省略，参见上一节代码示例 Dijkstra(g.adjMatrix, 0); // 以顶点0为起始点执行Dijkstra算法 return 0; } ``` 上述代码展示了Dijkstra算法的实现。算法使用了一个优先队列来保证每次都能获取到当前距离源点最近的顶点。这样，我们可以逐步更新所有顶点到源点的距离，并最终找到最短路径。 #### Floyd-Warshall算法 Floyd-Warshall算法是一种动态规划算法，用于寻找带权图中所有顶点对之间的最短路径。它适用于含有负权边的图，但不允许负权环路。 ```cpp void FloydWarshall(std::vector<std::vector<int>>& adjMatrix) { int numVertices = adjMatrix.size(); std::vector<std::vector<int>> dist(adjMatrix); // 三重循环进行动态规划 for (int k = 0; k < numVertices; k++) { for (int i = 0; i < numVertices; i++) { for (int j = 0; j < numVertices; j++) { if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; } } } } // 打印最终的距离矩阵 for (int i = 0; i < numVertices; i++) { for (int j = 0; j < numVertices; j++) { std::cout << dist[i][j] << " "; } std::cout << std::endl; } } // 示例调用 int main() { Graph g(4); // 创建一个拥有4个顶点的图 // 添加边和权重的代码省略，参见上一节代码示例 FloydWarshall(g.adjMatrix); // 执行Floyd-Warshall算法 return 0; } ``` 这段代码中，我们使用了一个二维数组`dist`来存储从每个顶点到其他所有顶点的距离。通过三重循环，我们不断更新`dist`数组，最终得到任意两个顶点之间的最短路径。 Floyd-Warshall算法和Dijkstra算法各有优势，Floyd-Warshall可以解决所有顶点对的最短路径问题，但时间复杂度较高（O(n^3)），适用于顶点数量较少的图。Dijkstra算法适合单源最短路径问题，时间复杂度较低，但在存在负权边的图中不适用。 # 4. 数据结构在算法中的应用 ## 4.1 排序算法与数据结构选择 ### 4.1.1 常见排序算法的对比分析 排序算法是处理数据时不可或缺的基础算法，不同的排序算法适用于不同的数据结构和场景。我们首先对比分析常见排序算法的特性： - 冒泡排序：简单直观，通过不断比较相邻元素，交换位置直到最大或最小元素“冒泡”到序列的一端。它的时间复杂度为O(n^2)，是原地排序，不需要额外存储空间。 - 选择排序：在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置。时间复杂度为O(n^2)，也是原地排序。 - 插入排序：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。时间复杂度同样为O(n^2)，适合小规模数据。 - 快速排序：通过一次划分将待排序的数组分为独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再递归地对这两部分数据分别进行快速排序，达到整个序列有序。时间复杂度平均为O(nlogn)，但在最坏情况下退化为O(n^2)。 - 归并排序：采用分治法的一个非常典型的应用。它将数组分成两半，对每一部分递归地应用归并排序，然后将结果归并在一起。时间复杂度稳定为O(nlogn)。 - 堆排序：利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。堆排序的时间复杂度为O(nlogn)。 从上述排序算法的特性来看，冒泡、选择和插入排序由于其时间复杂度较高，主要适用于小规模数据的排序。而快速排序、归并排序和堆排序则更适合大规模数据的排序需求。 ### 4.1.2 各种排序算法的时间空间复杂度 时间复杂度和空间复杂度是衡量排序算法性能的两个关键指标，下面以表格形式详细对比这些指标： | 排序算法 | 最佳时间复杂度 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | |----------|----------------|----------------|----------------|------------| | 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | | 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | | 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | | 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn) | | 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | | 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 从时间复杂度来看，归并排序和快速排序的平均效率较高，都是O(nlogn)，但归并排序需要额外的存储空间。堆排序虽然在空间复杂度上有优势，但是其在实际应用中略逊于快速排序。选择排序、冒泡排序和插入排序在最坏情况下的时间复杂度都是O(n^2)，适用于数据量不大的情况。 ### 4.1.3 特定数据结构下的排序优化 各种排序算法都基于特定的数据结构。例如，堆排序利用堆数据结构，快速排序通过划分操作，归并排序涉及合并操作。针对不同的数据结构，排序算法也需进行相应的调整。下面用代码展示快速排序在不同场景下的优化： ```cpp // 基于数组的快速排序 void quickSortArray(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); // 划分 quickSortArray(arr, low, pi - 1); // 递归左子序列 quickSortArray(arr, pi + 1, high); // 递归右子序列 } } // 基于链表的快速排序 void quickSortList(LinkedList* list) { if (list->next == nullptr) return; // 只有一个节点 Node* pivot = list->next; // 划分点 Node* left = nullptr, *right = nullptr; Node* current = list->next; // 从第二个节点开始遍历 while (current != nullptr) { Node* next = current->next; if (current->value <= pivot->value) { // 小于等于pivot的节点挂到left链表 current->next = left; left = current; } else { // 大于pivot的节点挂到right链表 current->next = right; right = current; } current = next; } // 递归排序left和right链表 quickSortList(left); quickSortList(right); // 将left链表的节点顺序挂在pivot节点之前 LinkedList* lList = new LinkedList(left); lList->append(pivot); // 将right链表的节点顺序挂在pivot之后 pivot->next = right; } // 划分函数 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 swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } ``` 在上述代码中，我们实现了基于数组和链表的快速排序。链表的快速排序需要额外的步骤来处理节点的连接，但它不受数组下标的限制，特别适合于大数据量的链式存储结构。 ## 4.2 搜索算法与数据结构选择 ### 4.2.1 二分搜索与数据结构的关系 二分搜索是一种在有序数组中查找特定元素的快速搜索算法。其时间复杂度为O(logn)，这使得它在数据量大时仍然能保持较高的搜索效率。二分搜索的实现依赖于有序数组这一数据结构，因此数组是否有序直接影响到二分搜索的性能。 ### 4.2.2 平衡二叉树在搜索中的应用 平衡二叉树（如AVL树或红黑树）能够在动态数据集合中维护有序结构，支持高效的动态数据插入和删除操作，同时保证在最坏情况下查找效率仍为O(logn)。这种数据结构在实际应用中尤其常见，如C++ STL中的`map`和`set`容器。 ```cpp // AVL树的查找操作 // 注意：以下代码仅为查找功能的简化示例，不包含完整的AVL树插入和平衡功能 Node* find(Node* root, int key) { if (root == nullptr || root->value == key) { return root; } else if (key < root->value) { return find(root->left, key); } else { return find(root->right, key); } } ``` 在上述代码中，`find`函数在AVL树中查找指定值。由于AVL树是自平衡的，它确保了树的高度保持在log(n)，从而保证了查找操作的时间复杂度为O(logn)。 ## 4.3 算法设计策略与数据结构 ### 4.3.1 分治法与递归树 分治法是一种将大问题分解为小问题，然后递归地解决这些小问题，最后合并这些子问题的解决方案来得到原问题的解。递归树是分治法在算法设计中的一个直观表示。 ```mermaid flowchart TD A[大问题] -->|分解| B[子问题1] A -->|分解| C[子问题2] A -->|分解| D[子问题3] B -->|递归解决| E[子问题1结果] C -->|递归解决| F[子问题2结果] D -->|递归解决| G[子问题3结果] E -->|合并| H[最终解] F -->|合并| H G -->|合并| H ``` 在上述mermaid流程图中，递归树展示了分治法解决大问题的过程，先分解再递归解决问题，最后将结果合并。 ### 4.3.2 动态规划中的数据结构运用 动态规划是解决多阶段决策问题的一种策略。在动态规划中，数据结构的运用非常关键，通常会用到数组或多维数组来存储中间状态。对于有重叠子问题的场景，我们可以使用哈希表来优化空间复杂度，通过记录已经解决的子问题的结果来避免重复计算。 ```cpp // 动态规划解决斐波那契数列问题 int fibonacci(int n) { if (n <= 1) { return n; } int a = 0, b = 1, c = 0; for (int i = 2; i <= n; ++i) { c = a + b; a = b; b = c; } return c; } ``` 在上述代码中，`fibonacci`函数通过动态规划的方式解决斐波那契数列问题。我们使用三个变量`a`、`b`和`c`来存储连续的三个数，从而避免了递归方法中的重复计算。 在本章节中，我们深入探讨了排序算法与数据结构选择，特别是针对不同场景的排序算法优化。我们还分析了搜索算法在不同数据结构下的应用，并通过实际代码展示了这些理论在实践中的应用。此外，我们探索了算法设计策略，特别是在分治法和动态规划中数据结构的运用，为读者在解决复杂问题时提供了有效的思考方法和工具。 # 5. 综合练习题分析与解答 在这一章中，我们通过分析和解答一些精选的编程练习题，旨在巩固前面章节中介绍的理论知识，并展示如何在实际编程中应用这些知识。通过具体的案例，我们将学习如何选择合适的数据结构解决特定问题，以及如何优化算法性能。 ## 5.1 题目一：平衡二叉树的构建与操作 ### 5.1.1 题目描述与分析 **题目描述：** 给定一个无序的整数数组，编写一个程序构建一个平衡二叉搜索树（AVL树）。要求实现以下操作：插入新节点、删除节点、以及查找最小值和最大值节点。 **分析：** 平衡二叉树（AVL树）是一种自平衡的二叉搜索树，要求任何节点的两个子树的高度差不能超过1。在构建AVL树时，需要在每次插入或删除操作后检查树的平衡性，并进行适当的旋转操作以恢复平衡。 ### 5.1.2 实现思路与代码展示 **实现思路：** 1. 创建AVL树的节点结构。 2. 实现节点插入功能，并在每次插入后更新节点高度。 3. 实现旋转操作：左旋、右旋、左右旋、右左旋。 4. 在插入和删除操作后检查节点平衡，并根据需要执行旋转。 5. 实现查找最小值和最大值的功能。 ```cpp struct AVLNode { int key, height; AVLNode *left, *right; AVLNode(int d) : key(d), height(1), left(nullptr), right(nullptr) {} }; // 获取节点的高度 int height(AVLNode *N) { if (N == nullptr) return 0; return N->height; } // 右旋转示例代码 AVLNode* rightRotate(AVLNode *y) { AVLNode *x = y->left; AVLNode *T2 = x->right; // 旋转 x->right = y; y->left = T2; // 更新高度 y->height = max(height(y->left), height(y->right)) + 1; x->height = max(height(x->left), height(x->right)) + 1; // 返回新的根节点 return x; } // ... 其他旋转操作的实现 // 插入节点，并可能进行旋转以保持树平衡 AVLNode* insert(AVLNode* node, int key) { // ... 插入逻辑 // ... 检查平衡并旋转 } // 查找最小值节点 AVLNode* findMin(AVLNode* node) { while (node && node->left != nullptr) node = node->left; return node; } // 查找最大值节点 AVLNode* findMax(AVLNode* node) { while (node && node->right != nullptr) node = node->right; return node; } // 主函数 int main() { AVLNode *root = nullptr; // 插入节点的示例 root = insert(root, 10); root = insert(root, 20); root = insert(root, 30); // ... 其他操作 } ``` ## 5.2 题目二：图的最短路径问题 ### 5.2.1 题目描述与分析 **题目描述：** 给定一个有向图，所有边的权重都为正，使用Dijkstra算法或Floyd-Warshall算法找到从单个源点到所有其他顶点的最短路径。 **分析：** Dijkstra算法适用于没有负权边的图，它使用贪心策略，每次找到距离源点最近的未被访问顶点，然后对其进行松弛操作。Floyd-Warshall算法是动态规划算法，它可以处理包含负权边的图，但不适用于存在负权回路的情况。 ### 5.2.2 实现思路与代码展示 **实现思路：** 1. 实现Dijkstra算法，使用优先队列优化寻找最小距离顶点的过程。 2. 实现Floyd-Warshall算法，通过三层嵌套循环计算所有顶点对之间的最短路径。 ```cpp // Dijkstra算法示例代码 void dijkstra(vector<vector<pair<int, int>>>& graph, int src) { int V = graph.size(); vector<int> dist(V, INT_MAX); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; dist[src] = 0; pq.push({0, src}); while (!pq.empty()) { int u = pq.top().second; pq.pop(); for (auto &edge : graph[u]) { int v = edge.first; int weight = edge.second; if (dist[v] > dist[u] + weight) { dist[v] = dist[u] + weight; pq.push({dist[v], v}); } } } // 输出结果 for (int i = 0; i < V; ++i) cout << "Vertex " << i << " Distance from Source " << src << ": " << dist[i] << endl; } // Floyd-Warshall算法示例代码 void floydWarshall(vector<vector<int>>& graph) { int V = graph.size(); vector<vector<int>> dist(graph); for (int k = 0; k < V; k++) for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j]; // 输出结果 for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) cout << "dist[" << i << "][" << j << "] = " << (dist[i][j] == INT_MAX ? "INF" : to_string(dist[i][j])) << endl; } // 主函数 int main() { vector<vector<pair<int, int>>> graph; // ... 初始化图 int source = 0; dijkstra(graph, source); vector<vector<int>> graphFloyd; // ... 初始化图 floydWarshall(graphFloyd); } ``` ## 5.3 题目三：字符串模式匹配算法设计 ### 5.3.1 题目描述与分析 **题目描述：** 编写一个程序实现KMP算法，用于在一个主字符串中查找一个模式字符串。 **分析：** KMP算法的核心在于一个前缀函数，它计算模式字符串的最长相同前后缀。在不匹配时，前缀函数允许算法利用已知信息，将模式字符串向前移动到正确的位置，从而避免重新检查已经匹配的字符。 ### 5.3.2 实现思路与代码展示 **实现思路：** 1. 计算模式字符串的前缀表。 2. 遍历主字符串，使用前缀表进行匹配。 3. 在不匹配时，根据前缀表的信息移动模式字符串。 ```cpp // KMP算法前缀表计算示例代码 void computeLPSArray(string str, int M, int* lps) { int len = 0; // length of the previous longest prefix suffix lps[0] = 0; // lps[0] is always 0 int i = 1; while (i < M) { if (str[i] == str[len]) { len++; lps[i] = len; i++; } else { // (str[i] != str[len]) if (len != 0) { len = lps[len - 1]; // Note that we do not increment i here } else { // if (len == 0) lps[i] = 0; i++; } } } } // KMP算法模式匹配示例代码 void KMPSearch(string pat, string txt) { int M = pat.size(); int N = txt.size(); // 创建lps数组 int lps[M]; // 计算lps数组 computeLPSArray(pat, M, lps); int i = 0; // txt的索引 int j = 0; // pat的索引 while (i < N) { if (pat[j] == txt[i]) { j++; i++; } if (j == M) { cout << "Found pattern at index " << i - j << endl; j = lps[j - 1]; } // 不匹配的情况 else if (i < N && pat[j] != txt[i]) { // 不需要匹配lps[0..lps[j-1]]字符，因为它们已经匹配了 if (j != 0) j = lps[j - 1]; else i = i + 1; } } } // 主函数 int main() { string txt = "ABABDABACDABABCABAB"; string pat = "ABABCABAB"; KMPSearch(pat, txt); } ``` ## 5.4 题目四：哈希表在海量数据处理中的应用 ### 5.4.1 题目描述与分析 **题目描述：** 给定一组海量数据（如数百万个整数），设计一个高效的算法统计每个元素出现的频率。 **分析：** 在处理大量数据时，哈希表是一种理想的数据结构，因为它提供平均常数时间的插入和查询操作。对于频率统计问题，可以使用哈希表来快速累计每个元素的出现次数。 ### 5.4.2 实现思路与代码展示 **实现思路：** 1. 遍历数据集，对每个元素应用哈希函数，将元素映射到哈希表中的索引。 2. 在哈希表中更新对应元素的计数。 3. 考虑到哈希冲突，使用链表或开放寻址法处理冲突。 ```cpp #include <iostream> #include <unordered_map> // 使用unordered_map作为哈希表 void countFrequencies(const std::vector<int>& data) { std::unordered_map<int, int> frequencyMap; for (int num : data) { frequencyMap[num]++; } // 输出频率统计结果 for (auto& pair : frequencyMap) { std::cout << "Number " << pair.first << " appears " << pair.second << " times." << std::endl; } } // 主函数 int main() { std::vector<int> hugeDataSet = { /* 海量数据填充 */ }; countFrequencies(hugeDataSet); } ``` 以上各题的代码展示只是实现思路的一个简单示例，实际的实现可能会根据具体的数据结构和算法复杂性有所不同。通过这些练习题的分析和解答，读者可以进一步加深对数据结构及其在算法中应用的理解。