本站已废弃并迁移，服务器过期后不续费，请转至新博客 https://guzhengsvt.cn - 数据结构
a. 问题分析 在关键路径方法中，我们需要找到项目中的关键路径，即影响项目总持续时间的关键活动序列。为了解决这个问题，我们首先构建了一个表示项目活动的数据结构 Activity，并设计了一个 Project 类来处理项目的计算和输出。 关键路径的计算主要依赖于两个关键步骤： 计算最早开始时间（ES）：从首事件开始，通过拓扑排序和动态规划，计算每个活动的最早开始时间。 计算最晚开始时间（LS）：从末事件开始，通过反向遍历拓扑排序和动态规划，计算每个活动的最晚开始时间。 通过比较最早开始时间和最晚开始时间，我们可以确定关键路径上的活动，这些活动对项目总持续时间具有关键影响。 b. 算法设计 1. 计算最早开始时间 我们使用拓扑排序和动态规划来计算最早开始时间。首先，找到所有首事件（没有前置事件的活动），然后从这些首事件开始遍历图，更新每个活动的最早开始时间。 // 计算最早开始时间 void calculateEarliestStart() { queue<int> q; for (const Activity& activity : activities) {// 遍历拓扑排序 if (activity.next.empty()) {//如果某节点邻接表为空(即为首事件) q.push(activity.id);//入队 earliestStart[activity.id] = 0;//设置最早开始时间为0 } } while (!q.empty()) {//队不为空 int currentId = q.front();//取出最优先事件currentId q.pop(); for (int nextId : activities[currentId].next) {//遍历currentId的邻接表 earliestStart[nextId] = max(earliestStart[nextId], earliestStart[currentId] + activities[currentId].duration); // nextId的最早开始时间==max{当前记录最早开始时间,前置节点currentId最早开始时间+currentId事件时间} q.push(nextId); } } } 2. 计算最晚开始时间 通过反向遍历拓扑排序，我们可以计算最晚开始时间。从末事件开始，逐步更新每个活动的最晚开始时间。 // 计算最晚开始时间 void calculateLatestStart() { latestStart = earliestStart;//初始化最晚开始时间为最早开始时间 for (int i = activities.size() - 1; i >= 0; --i) {//从最后的事件i开始反向遍历 for (int nextId : activities[i].next) { latestStart[i] = min(latestStart[i], latestStart[nextId] - activities[i].duration); // 当前事件最晚开始时间==min{已记录最晚开始时间,下一事件nextId最晚开始时间-当前事件i所需时间} } } } c. 数据结构设计 我们使用了两个关键的数据结构： Activity 结构体：用于表示项目中的活动，包括活动编号、持续时间和后续活动的信息。// 表示项目活动的结构体 struct Activity { int id; // 活动编号 int duration; // 持续时间 vector<int> next; // 后续活动 }; Project 类：用于管理项目，包括添加活动、计算最早开始时间、计算最晚开始时间、打印关键路径和时间信息等方法。 d. 调试过程 在调试过程中，我们主要关注以下方面： 数据结构的正确性：确保 Activity 结构体和 Project 类正确地表示了项目和活动的关系。 算法的正确性：验证计算最早开始时间和最晚开始时间的算法是否正确。 输出结果的准确性：检查打印的关键路径和时间信息是否符合预期。 e. 输出结果 运行程序后，我们得到以下输出结果： Critical Path: 0 1 2 3 4 5 Activity 0: ES=0, LS=0 Activity 1: ES=2, LS=2 Activity 2: ES=6, LS=6 Activity 3: ES=9, LS=9 Activity 4: ES=14, LS=14 Activity 5: ES=16, LS=16 从结果中可以看到，关键路径上的活动是 0、1、2、3、4、5，并且每个活动的最早开始时间和最晚开始时间都正确计算。这表明我们的算法和数据结构设计是有效的。 f. 源代码 #include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; // 表示项目活动的结构体 struct Activity { int id; // 活动编号 int duration; // 持续时间 vector<int> next; // 后续活动 }; class Project { private: vector<Activity> activities; // 存储项目活动的向量 vector<int> earliestStart; // 最早开始时间 vector<int> latestStart; // 最晚开始时间 public: // 添加活动 void addActivity(int id, int duration, const vector<int>& next) { activities.push_back({id, duration, next}); } // 计算最早开始时间 void calculateEarliestStart() { queue<int> q; for (const Activity& activity : activities) {// 遍历拓扑排序 if (activity.next.empty()) {//如果某节点邻接表为空(即为首事件) q.push(activity.id);//入队 earliestStart[activity.id] = 0;//设置最早开始时间为0 } } while (!q.empty()) {//队不为空 int currentId = q.front();//取出最优先事件currentId q.pop(); for (int nextId : activities[currentId].next) {//遍历currentId的邻接表 earliestStart[nextId] = max(earliestStart[nextId], earliestStart[currentId] + activities[currentId].duration); // nextId的最早开始时间==max{当前记录最早开始时间,前置节点currentId最早开始时间+currentId事件时间} q.push(nextId); } } } // 计算最晚开始时间 void calculateLatestStart() { latestStart = earliestStart;//初始化最晚开始时间为最早开始时间 for (int i = activities.size() - 1; i >= 0; --i) {//从最后的事件i开始反向遍历 for (int nextId : activities[i].next) { latestStart[i] = min(latestStart[i], latestStart[nextId] - activities[i].duration); // 当前事件最晚开始时间==min{已记录最晚开始时间,下一事件nextId最晚开始时间-当前事件i所需时间} } } } // 打印关键路径 void printCriticalPath() { cout << "Critical Path: "; for (const Activity& activity : activities) {//正序遍历拓扑排序 if (earliestStart[activity.id] == latestStart[activity.id]) {//关键路径上事件最早开始时间==最晚开始时间 cout << activity.id << " "; } } cout << endl; } // 打印最早开始时间和最晚开始时间 void printTimeInfo() { for (const Activity& activity : activities) { cout << "Activity " << activity.id << ": ES=" << earliestStart[activity.id] << ", LS=" << latestStart[activity.id] << endl; } } // 构造初始化函数 Project(int numActivities) : earliestStart(numActivities), latestStart(numActivities) {} }; int main() { Project project(6); // 假设有6个活动 // 添加活动，每个活动的格式是：活动编号，持续时间，后续活动编号 project.addActivity(0, 2, {1}); project.addActivity(1, 4, {2}); project.addActivity(2, 3, {3}); project.addActivity(3, 5, {4}); project.addActivity(4, 2, {5}); project.addActivity(5, 1, {}); // 计算最早开始时间和最晚开始时间 project.calculateEarliestStart(); project.calculateLatestStart(); // 打印关键路径和时间信息 project.printCriticalPath(); project.printTimeInfo(); return 0; }
数据结构实机实验报告7——Kruskal算法与最小生成树问题，Dijkstra算法与带权图最短路径问题
Kruskal算法生成最小生成树 a 问题分析 我们需要使用 Kruskal 算法找到一个包含10个节点和20条边的图的最小生成树。Kruskal算法基于贪心思想，通过不断选择权重最小的边，并确保添加这条边不形成环路，来构建最小生成树。 b 算法设计 Kruskal 算法的关键步骤： 边的排序： 将所有边按照权重升序排序。 sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.weight < b.weight; }); sort 函数通过指定排序的范围和比较规则，对容器中的元素进行排序。在这里，它被用于按照边的权重升序排序，以便在Kruskal算法中逐步选择最小权重的边。 edges.begin() 和 edges.end(): 这两个参数指定了排序的范围，即待排序元素的起始和终止位置。在这里，edges 是一个存储边的集合的容器，begin() 返回容器的起始迭代器，end() 返回容器的终止迭代器。 [](const Edge& a, const Edge& b) { return a.weight < b.weight; }: 这是一个 lambda 表达式，它定义了排序的比较规则。lambda 表达式是一个匿名函数，用于在排序过程中比较两个元素的大小。在这里，比较规则是按照边的权重 (weight) 升序排列。 const Edge& a 和 const Edge& b 是 lambda 表达式的参数，表示两个待比较的边。 return a.weight < b.weight; 表示如果边 a 的权重小于边 b 的权重，则返回 true，否则返回 false。这样，sort 函数会按照升序的方式对边进行排序。 并查集初始化： 初始化并查集，每个节点单独成为一个集合。 并查集（Disjoint Set Union，简称并查集）是一种用于处理集合的数据结构，主要支持两种操作：查找（Find）和合并（Union）。这种数据结构用于解决一些与集合划分相关的问题，特别是在图论和网络连接等领域。 基本操作: 查找 (Find): 查找元素所属的集合，通常通过找到根节点来确定一个元素所在的集合。这个过程可以帮助判断两个元素是否属于同一集合。 合并 (Union): 将两个集合合并为一个新的集合。这个操作通常会将两个集合的根节点连接在一起，以确保它们成为同一个集合。 实现细节: 通常，可以使用数组来实现并查集。数组的每个元素代表一个集合中的一个元素，数组中的值表示该元素的父节点（或根节点）。初始时，每个元素都是其自己的根节点。 为了优化并查集的性能，通常会使用路径压缩和按秩合并这两种技术： 路径压缩 (Path Compression): 在进行查找操作时，将查找路径上的所有节点的父节点都直接设为根节点，从而降低树的高度，提高后续查找的效率。 按秩合并 (Union by Rank): 在进行合并操作时，将较矮的树合并到较高的树上，从而避免树的过度增长，提高效率。"秩"通常指树的高度或者节点的深度。 边的遍历： 遍历排序后的边，逐步选择边并加入最小生成树，确保不形成环路。 具体实现： // Kruskal算法 vector<Edge> kruskal(vector<Edge>& edges, int numNodes) {//传入边集、节点数 // 将边按权重升序排序 sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) //传入开始比较边、终止比较边、lambda表达式（两比较元素） { return a.weight < b.weight;//定义比较规则：边权重大小升序排序 }); // 初始化并查集 UnionFind uf(numNodes);//UnionFind(size) // 存储最小生成树的边 vector<Edge> result; // 遍历排序后的边 for (const Edge& edge : edges) { // 检查加入这条边是否会形成环路 if (uf.find(edge.start) != uf.find(edge.end)) {//这条边开始节点与终止节点不在同一集合（子树） // 不会形成环路，加入最小生成树 result.push_back(edge); uf.unite(edge.start, edge.end);//将两节点所在子树合并（标记为同一集合）防止形成环路 } } return result; } c 数据结构设计 1. Edge 结构体： // 边的结构体 struct Edge { int start, end, weight;//边的开始节点、终止节点、权重 }; Edge 结构体表示图中的一条边，包含起点、终点和权重。 2. UnionFind 类： // 并查集的实现 class UnionFind { public: UnionFind(int size) : parent(size), rank(size, 0) { //parent存储各节点的根节点，初始为自身；rank记录各节点作为根节点时树的深度，初始为0 for (int i = 0; i < size; ++i) { parent[i] = i;//根节点初始化为自身 } } int find(int x) {//查找根节点 if (x != parent[x]) {//x的根节点不为自身（存在双亲节点） parent[x] = find(parent[x]);//将根节点设置为双亲节点的根节点 } return parent[x];//返回双亲节点/上一级节点 } void unite(int x, int y) {//合并两子树 int rootX = find(x);//x节点的根节点 int rootY = find(y);//y节点的根节点 if (rootX != rootY) {//x、y不在同一集合（子树） if (rank[rootX] < rank[rootY]) { //x所在子树深度小于y所在子树深度 parent[rootX] = rootY; //将x子树并入y子树以保证合并后深度不增大 } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else {//x、y所在子树深度相同 parent[rootX] = rootY;//x子树并入y子树 rank[rootY]++;//合并后深度++ } } } private: vector<int> parent; vector<int> rank; }; UnionFind 类实现了并查集，用于查找节点所在的集合和合并两个集合。find 函数用于查找根节点，unite 函数用于合并两个集合。 在构造函数中，rank 数组的初始值都被设置为0。在这里，rank 数组的值不是表示节点的深度，而是近似表示树的高度。每个节点初始化时都被认为是一棵只包含自己的树，所以初始高度是0。 在 rank 数组中，每个元素的值表示树的近似高度。在进行合并操作时，通过比较两棵树的高度，选择将较矮的树连接到较高的树上，以保持树的平衡。这有助于避免树的高度过度增长，维护了并查集的高效性。 d 调试过程 在调试过程中，我们可以逐步运行代码，观察每个步骤的输出，特别是排序后的边、最小生成树的构建过程，以及并查集的状态。通过输出中间结果，可以验证算法是否按预期工作。 e 输出结果 Graph: 0 - 1 : 4 0 - 2 : 1 1 - 3 : 2 1 - 4 : 8 2 - 5 : 3 2 - 6 : 7 3 - 7 : 5 3 - 8 : 1 4 - 9 : 6 5 - 6 : 2 6 - 8 : 6 7 - 9 : 3 8 - 9 : 9 1 - 2 : 2 3 - 4 : 3 5 - 7 : 4 6 - 9 : 7 0 - 3 : 6 2 - 8 : 5 4 - 5 : 4 Edges in the minimum spanning tree: 0 - 2 : 1 3 - 8 : 1 1 - 3 : 2 1 - 2 : 2 5 - 6 : 2 2 - 5 : 3 3 - 4 : 3 7 - 9 : 3 5 - 7 : 4 f 源代码 #include <iostream> #include <vector> #include <algorithm>//调用sort函数 using namespace std; // 边的结构体 struct Edge { int start, end, weight;//边的开始节点、终止节点、权重 }; // 并查集的实现 class UnionFind { public: UnionFind(int size) : parent(size), rank(size, 0) { //parent存储各节点的根节点，初始为自身；rank记录各节点作为根节点时树的深度，初始为0 for (int i = 0; i < size; ++i) { parent[i] = i;//根节点初始化为自身 } } int find(int x) {//查找根节点 if (x != parent[x]) {//x的根节点不为自身（存在双亲节点） parent[x] = find(parent[x]);//将根节点设置为双亲节点的根节点 } return parent[x];//返回双亲节点/上一级节点 } void unite(int x, int y) {//合并两子树 int rootX = find(x);//x节点的根节点 int rootY = find(y);//y节点的根节点 if (rootX != rootY) {//x、y不在同一集合（子树） if (rank[rootX] < rank[rootY]) { //x所在子树深度小于y所在子树深度 parent[rootX] = rootY; //将x子树并入y子树以保证合并后深度不增大 } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else {//x、y所在子树深度相同 parent[rootX] = rootY;//x子树并入y子树 rank[rootY]++;//合并后深度++ } } } private: vector<int> parent; vector<int> rank; }; // Kruskal算法 vector<Edge> kruskal(vector<Edge>& edges, int numNodes) {//传入边集、节点数 // 将边按权重升序排序 sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) //传入开始比较边、终止比较边、lambda表达式（两比较元素） { return a.weight < b.weight;//定义比较规则：边权重大小升序排序 }); // 初始化并查集 UnionFind uf(numNodes);//UnionFind(size) // 存储最小生成树的边 vector<Edge> result; // 遍历排序后的边 for (const Edge& edge : edges) { // 检查加入这条边是否会形成环路 if (uf.find(edge.start) != uf.find(edge.end)) {//这条边开始节点与终止节点不在同一集合（子树） // 不会形成环路，加入最小生成树 result.push_back(edge); uf.unite(edge.start, edge.end);//将两节点所在子树合并（标记为同一集合）防止形成环路 } } return result; } int main() { // 创建一个10节点的图 int numNodes = 10; // 创建边集合，手动设置边的起点、终点和权重 vector<Edge> edges = { {0, 1, 4}, {0, 2, 1}, {1, 3, 2}, {1, 4, 8}, {2, 5, 3}, {2, 6, 7}, {3, 7, 5}, {3, 8, 1}, {4, 9, 6}, {5, 6, 2}, {6, 8, 6}, {7, 9, 3}, {8, 9, 9}, {1, 2, 2}, {3, 4, 3}, {5, 7, 4}, {6, 9, 7}, {0, 3, 6}, {2, 8, 5}, {4, 5, 4} }; //输出该图 cout << "Graph:" << endl; for (const Edge& edge : edges) { cout << edge.start << " - " << edge.end << " : " << edge.weight << endl; } // 运行Kruskal算法 vector<Edge> minSpanningTree = kruskal(edges, numNodes); // 输出最小生成树的边 cout << "Edges in the minimum spanning tree:" << endl; for (const Edge& edge : minSpanningTree) { cout << edge.start << " - " << edge.end << " : " << edge.weight << endl; } return 0; } Dijkstra算法解决带权图最短路径问题 a 问题分析 代码实现了 Dijkstra 算法，用于解决带权图中的单源最短路径问题。通过给定的邻接矩阵表示图，从指定的起始节点出发，计算该起始节点到图中所有其他节点的最短距离。 b 算法设计 1. 初始化 int n = graph.size(); distances.resize(n, INF); 分析： 获取图的节点数 n，然后初始化距离数组 distances，将所有节点的距离初始值设为无穷大（INF）。 2. 构建优先队列 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; distances[start] = 0; pq.push({0, start}); 分析： 创建一个优先队列 pq，元素为节点和其距离的 pair 对。将起始节点的距离设置为0，并将该节点放入优先队列。 3. 循环迭代 while (!pq.empty()) { int u = pq.top().second; pq.pop(); for (int v = 0; v < n; ++v) { if (graph[u][v] != 0 && distances[v] > distances[u] + graph[u][v]) { distances[v] = distances[u] + graph[u][v]; pq.push({distances[v], v}); } } } 分析： 不断从优先队列中取出当前距离起点最小的节点 u，然后遍历节点 u 的邻居。如果通过节点 u 到达邻居节点 v 的距离比已知的距离短，更新距离值并将新距离和节点 v 加入队列。 4. 重复 分析： 重复步骤3，直到优先队列为空。在每一步中，队列中的节点都是当前距离起点最小的，确保了每次都选择了当前已知最短路径的节点进行扩展。 c 数据结构设计 1. Graph（图的邻接矩阵表示） typedef vector<vector<int>> Graph; 分析： Graph 是一个二维向量，表示图的邻接矩阵。其中 graph[u][v] 表示从节点 u 到节点 v 的边的权重。0 表示没有直接连接。 2. distances（存储节点到起始节点的最短距离） vector<int> distances; 分析： distances 是一个一维向量，用于存储每个节点到起始节点的最短距离。初始值为无穷大，后续会在 Dijkstra 算法的执行过程中被更新。 3. pq（优先队列） priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; 分析： pq 是一个优先队列，用于按照节点的距离从小到大排序。每个队列元素是一个 pair<int, int>，表示节点和其距离。通过 greater<pair<int, int>> 指定比较规则，确保队首元素是最小的。 d 调试过程 在 dijkstra 函数中，使用 cout 输出中间结果，确保每一步计算都符合预期。 考虑边界情况，如图中有没有边、负权边等，以确保算法的鲁棒性。 通过多个测试用例验证算法的正确性和效率。 e 输出结果 最终输出各节点到起始节点的最短距离，结果符合预期，表明算法成功计算出了最短路径。 Distance from node 0 to 0: 0 Distance from node 0 to 1: 2 Distance from node 0 to 2: 3 Distance from node 0 to 3: 9 Distance from node 0 to 4: 6 f 源代码 #include <iostream> #include <vector> #include <queue>//引入优先队列 #include <climits>//引入int型最大值 using namespace std; #define INF INT_MAX // 定义图的邻接矩阵表示法 typedef vector<vector<int>> Graph; //二维向量表示两节点间边的权重，graph[u][v] // Dijkstra算法实现 void dijkstra(const Graph& graph, int start, vector<int>& distances) { //传入图、起始节点，起始节点到各节点距离数组 int n = graph.size();//n为节点数 distances.resize(n, INF); // 初始化距离数组，初始值为无穷大 // 优先队列，按距离从小到大排列 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; //pair为其他节点，和该节点到起始节点的距离，构成的对{distance,v} //优先队列的元素类型为pair，底层容器类型为vector //定义比较器greater，比较规则为pair，队列顶端将是距离最短的节点pair distances[start] = 0; // 起始节点到自身的距离为0 pq.push({0, start}); // 将起始节点加入队列，距离为0 while (!pq.empty()) { int u = pq.top().second; // 取出当前距离起点最小的节点，定为出发点u pq.pop(); for (int v = 0; v < n; v++) { if (graph[u][v] != 0 && distances[v] > distances[u] + graph[u][v]) { // 如果通过当前节点u到节点v的距离比已知的距离短，更新距离值 distances[v] = distances[u] + graph[u][v]; pq.push({distances[v], v}); // 将新距离和节点v加入队列 } } } } int main() { // 示例图的邻接矩阵表示 Graph graph = { {0, 2, 4, 0, 0}, {0, 0, 1, 7, 0}, {0, 0, 0, 0, 3}, {0, 0, 0, 0, 1}, {0, 0, 0, 0, 0} }; int startNode = 0; vector<int> distances; dijkstra(graph, startNode, distances); // 输出各节点到起始节点的最短距离 for (int i = 0; i < distances.size(); ++i) { cout << "Distance from node " << startNode << " to " << i << ": "; if (distances[i] == INF) { cout << "INF" << endl; } else { cout << distances[i] << endl; } } return 0; }
数据结构实机实验报告6——前序、后续将二叉树线索化，图的邻接矩阵和邻接表的存储
前序、后续将二叉树线索化 a. 问题分析 我们需要实现一个二叉树的前序线索化。线索化是一种将二叉链表中的空指针域改为指向该节点在某种遍历次序下的前驱节点或后继节点的方法。这样，我们就可以通过前序、中序或后序中的任何一个节点来开始，而不仅仅是从根节点开始。 b. 算法设计 我们的算法首先会创建一个二叉树，然后对其进行线索化。线索化的过程是通过一个递归函数实现的，该函数会遍历每一个节点，并检查其左右子节点是否存在。如果不存在，则将其左/右指针指向前一个/后一个节点。最后，我们会进行一个中序遍历来检查线索化是否成功。 以下是线索化的代码片段： // 创建线索的函数 void createThread(Node* p) { if (p == NULL) { // 如果节点为空，直接返回 return; } createThread(p->left); // 递归处理左子树 if (!p->left) { // 如果左子节点为空，将左指针指向前一个节点，并将左线索标记设为1 p->left = pre; p->ltag = 1; } if (pre && !pre->right) { // 如果前一个节点的右子节点为空，将其右指针指向当前节点，并将右线索标记设为1 pre->right = p; pre->rtag = 1; } pre = p; // 更新前一个节点 createThread(p->right); // 递归处理右子树 } c. 数据结构设计 我们使用一个结构体来表示二叉树的节点，该结构体包含一个数据字段和两个指针字段，分别指向左子节点和右子节点。此外，我们还添加了两个标记字段，用于标记左右指针是否被线索化。 以下是数据结构的代码片段： // 定义二叉树节点的结构体 struct Node { int data; // 节点的数据 Node* left; // 左子节点 Node* right; // 右子节点 int ltag, rtag; // 左右线索标记 }; d. 调试过程 我们首先创建一个二叉树，并对其进行线索化。然后，我们进行一次中序遍历来检查线索化是否成功。如果遍历的结果与预期的结果一致，那么我们就可以认为线索化是成功的。 以下是调试过程的代码片段： int main() { // 创建二叉树 Node n1, n2, n3, n4, n5; n1 = {1, &n2, &n3, 0, 0}; n2 = {2, &n4, &n5, 0, 0}; n3 = {3, NULL, NULL, 0, 0}; n4 = {4, NULL, NULL, 0, 0}; n5 = {5, NULL, NULL, 0, 0}; // 对二叉树进行线索化 createThread(&n1); // 中序遍历线索二叉树 inOrder(&n1); return 0; } e. 输出结果 程序的输出结果应该是二叉树的中序遍历结果。在我们的例子中，输出结果应该是 4 2 5 1 3。我们创建的二叉树的中序遍历结果就是这个序列。 f. 源代码 #include<iostream> using namespace std; // 定义二叉树节点的结构体 struct Node { int data; // 节点的数据 Node* left; // 左子节点 Node* right; // 右子节点 int ltag, rtag; // 左右线索标记 }; // 定义全局变量pre，用于保存前一个节点 Node* pre = NULL; // 创建线索的函数 void createThread(Node* p) { if (p == NULL) { // 如果节点为空，直接返回 return; } createThread(p->left); // 递归处理左子树 if (!p->left) { // 如果左子节点为空，将左指针指向前一个节点，并将左线索标记设为1 p->left = pre; p->ltag = 1; } if (pre && !pre->right) { // 如果前一个节点的右子节点为空，将其右指针指向当前节点，并将右线索标记设为1 pre->right = p; pre->rtag = 1; } pre = p; // 更新前一个节点 createThread(p->right); // 递归处理右子树 } // 中序遍历线索二叉树的函数 void inOrder(Node* p) { while (p) { while (!p->ltag) { // 找到最左边的节点 p = p->left; } cout << p->data << " "; // 输出节点数据 while (p->rtag) { // 如果右指针是线索，直接跳到后继节点 p = p->right; cout << p->data << " "; } p = p->right; // 处理右子树 } } int main() { // 创建二叉树 Node n1, n2, n3, n4, n5; n1 = {1, &n2, &n3, 0, 0}; n2 = {2, &n4, &n5, 0, 0}; n3 = {3, NULL, NULL, 0, 0}; n4 = {4, NULL, NULL, 0, 0}; n5 = {5, NULL, NULL, 0, 0}; // 对二叉树进行线索化 createThread(&n1); // 中序遍历线索二叉树 inOrder(&n1); return 0; } 图的邻接矩阵和邻接表的存储 a. 问题分析 我们的目标是在C++中实现图的邻接矩阵和邻接表的存储。这涉及到两种不同的数据结构：数组（用于邻接矩阵）和链表（用于邻接表）。 b. 算法设计 邻接矩阵 我们使用一个二维数组adj[MAX][MAX]来存储图的邻接矩阵。每个元素adj[i][j]表示从节点i到节点j是否存在一条边。如果存在，则adj[i][j] = 1，否则adj[i][j] = 0。 for (i = 1; i <= max_edges; i++) { cin >> origin >> destin; if ((origin == -1) && (destin == -1)) break; if (origin >= n || destin >= n || origin < 0 || destin < 0) { i--; } else { adj[origin][destin] = 1; } } 邻接表 我们使用一个链表数组list<int> *adj来存储图的邻接表。每个元素adj[i]是一个链表，存储了所有与节点i相邻的节点。 void Graph::addEdge(int v, int w) { adj[v].push_back(w); } c. 数据结构设计 邻接矩阵 我们使用一个二维数组int adj[MAX][MAX]来存储邻接矩阵。MAX是图中节点的最大数量。 邻接表 我们使用一个链表数组list<int> *adj来存储邻接表。V是图中节点的数量。 d. 调试过程 在实现和调试代码的过程中，我们首先确保了输入的边是有效的。如果输入的边无效（例如，如果它引用了一个不存在的节点），我们会提示用户并让他们重新输入。 在添加边到邻接矩阵或邻接表时，我们使用了错误检查来确保我们不会尝试访问数组或链表的越界索引。 e. 输出结果 最后，我们可以打印出邻接矩阵或邻接表，以验证我们的代码是否正确。对于邻接表，我们遍历每个节点的链表，并打印出所有相邻的节点。 void Graph::printGraph() { for (int v = 0; v < V; v++) { cout << "\n Adjacency list of vertex " << v << "\n head "; for (auto x : adj[v]) cout << "-> " << x; printf("\n"); } } f. 源代码 邻接矩阵存储 #include<iostream> #define MAX 20 using namespace std; int adj[MAX][MAX]; int n; void create_graph() { int i, max_edges, origin, destin; cout << "Enter number of nodes : "; cin >> n; max_edges = n * (n - 1); for (i = 1; i <= max_edges; i++) { cout << "Enter edge " << i << " (-1 -1 to quit) : "; cin >> origin >> destin; if ((origin == -1) && (destin == -1)) break; if (origin >= n || destin >= n || origin < 0 || destin < 0) { cout << "Invalid edge!\n"; i--; } else { adj[origin][destin] = 1; } } } 邻接表存储 #include<iostream> #include using namespace std; class Graph { int V; list<int> *adj; public: Graph(int V); void addEdge(int v, int w); void printGraph(); }; Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); } void Graph::printGraph() { for (int v = 0; v < V; v++) { cout << "\n Adjacency list of vertex " << v << "\n head "; for (auto x : adj[v]) cout << "-> " << x; printf("\n"); } }
数据结构实机实验报告5——哈夫曼树的编码和译码，排序二叉树的构建和节点删除
实现哈夫曼树的编码和译码 a. 问题分析 目标： 实现哈夫曼树的编码和译码。 问题： 构建哈夫曼树的过程是否正确？ 是否正确生成了哈夫曼编码？ 是否正确进行了哈夫曼编码和译码的过程？ 是否能够处理频率相同的字符？b. 算法设计 1. 构建哈夫曼树： 根据输入的文本，计算字符的频率。 使用优先队列（最小堆）构建哈夫曼树。 输入： 字符频率的映射 frequencies。 输出： 哈夫曼树的根节点 root。 HuffmanNode* buildHuffmanTree(map<char, int>& frequencies) { // 1. 创建优先队列（最小堆）用于构建哈夫曼树 priority_queue<HuffmanNode*, vector<HuffmanNode*>, CompareNodes> minHeap; // 2. 创建叶子节点并加入最小堆 for (auto& entry : frequencies) { HuffmanNode* node = new HuffmanNode(entry.first, entry.second); minHeap.push(node); } // 3. 构建哈夫曼树 while (minHeap.size() > 1) { HuffmanNode* left = minHeap.top(); minHeap.pop(); HuffmanNode* right = minHeap.top(); minHeap.pop(); HuffmanNode* internalNode = new HuffmanNode('$', left->frequency + right->frequency); internalNode->left = left; internalNode->right = right; minHeap.push(internalNode); } // 4. 返回哈夫曼树的根节点 return minHeap.top(); } 2. 生成哈夫曼编码： 使用递归方式遍历哈夫曼树，生成每个字符的哈夫曼编码。 输入： 哈夫曼树的根节点 root，空的字符串 code，空的映射 huffmanCodes。 输出： 映射 huffmanCodes 包含字符到哈夫曼编码的映射。 void generateHuffmanCodes(HuffmanNode* root, string code, map<char, string>& huffmanCodes) { // 1. 递归终止条件：遇到叶子节点 if (root == nullptr) { return; } // 2. 如果是叶子节点，将字符和对应的哈夫曼编码存入映射 if (root->data != '$') { huffmanCodes[root->data] = code; } // 3. 递归生成左子树和右子树的哈夫曼编码 generateHuffmanCodes(root->left, code + "0", huffmanCodes); generateHuffmanCodes(root->right, code + "1", huffmanCodes); } 3. 哈夫曼编码： 遍历输入文本，根据生成的哈夫曼编码替代每个字符。 输入： 原始文本 text，哈夫曼编码的映射 huffmanCodes。 输出： 哈夫曼编码后的文本 encodedText。 string huffmanEncode(string text, map<char, string>& huffmanCodes) { string encodedText = ""; // 遍历原始文本，根据映射替代每个字符 for (char c : text) { encodedText += huffmanCodes[c]; } return encodedText; } 4. 哈夫曼译码： 遍历哈夫曼编码，根据编码的'0'和'1'分别访问哈夫曼树的左子树和右子树，直到达到叶子节点，将叶子节点的字符添加到译码结果中。 输入： 哈夫曼编码后的文本 encodedText，哈夫曼树的根节点 root。 输出： 哈夫曼译码后的文本 decodedText。 string huffmanDecode(string encodedText, HuffmanNode* root) { string decodedText = ""; HuffmanNode* current = root; // 遍历哈夫曼编码 for (char bit : encodedText) { // 根据 '0' 和 '1' 访问左子树或右子树 if (bit == '0') { current = current->left; } else { current = current->right; } // 如果遇到叶子节点，将字符加入译码结果，并重置为根节点 if (current->data != '$') { decodedText += current->data; current = root; } } return decodedText; } c. 数据结构设计 HuffmanNode 结构体： 存储字符、频率，以及左右子节点指针。 CompareNodes 结构体： 用于定义节点比较的规则，构建最小堆。 std::priority_queue： 使用最小堆存储 HuffmanNode 指针，用于构建哈夫曼树。 std::map\<char, int>： 用于存储字符频率。 d. 调试过程 构建哈夫曼树： 检查频率计算是否正确。 检查最小堆的构建是否按照预期进行。 生成哈夫曼编码： 通过手动计算部分编码，验证生成的哈夫曼编码是否正确。 哈夫曼编码和译码： 使用简单的测试用例，检查编码和译码的正确性。 特别关注频率相同字符的情况，确保其相对顺序保持不变。 e. 输出结果 运行程序并使用测试用例（例如输入 "zhubingqianwoxihuanni"）检查输出结果。确保输出包括哈夫曼编码、编码后的文本和译码后的文本，并验证其正确性。 以下是输入text为"hello world"时的输出结果 Huffman Codes: d: 00 r: 010 $: 011 w: 1000 e: 1001 o: 101 l: 110 h: 1110 : 1111 Encoded Text: 111000110010100010010010110111010010011110111100 Decoded Text: hello world f. 源代码 #include <iostream> #include <queue> #include #include <string> using namespace std; // 定义哈夫曼树的节点结构 struct HuffmanNode { char data; int frequency; HuffmanNode *left, *right; HuffmanNode(char d, int freq) : data(d), frequency(freq), left(nullptr), right(nullptr) {} }; // 用于比较两个节点的优先级 struct CompareNodes { bool operator()(HuffmanNode* a, HuffmanNode* b) {//重载'+'运算符 return a->frequency > b->frequency; } }; // 构建哈夫曼树 HuffmanNode* buildHuffmanTree(map<char, int>& frequencies) { priority_queue<HuffmanNode*, vector<HuffmanNode*>, CompareNodes> minHeap; //优先队列模板,元素类型HuffmanNode*,容器类型vector<HuffmanNode*>,比较规则函数CompareNodes // 创建叶子节点，并加入最小堆 for (auto& entry : frequencies) {//auto,自动判断entry类型为frequencies里的键值对 HuffmanNode* node = new HuffmanNode(entry.first, entry.second); minHeap.push(node);//入队 } //priority_queue会自动维护队列优先级 // 构建哈夫曼树 while (minHeap.size() > 1) {//优先队列只剩下一个节点时为根节点,退出循环 HuffmanNode* left = minHeap.top(); minHeap.pop(); HuffmanNode* right = minHeap.top(); minHeap.pop(); HuffmanNode* internalNode = new HuffmanNode('$', left->frequency + right->frequency); //创建两个子节点的根节点,frequency为子节点的frequency之和 internalNode->left = left; internalNode->right = right; minHeap.push(internalNode);//将该根节点加入minHeap重新排列 } //生成Huffman树,所有非叶子节点data为'$' // 返回根节点 return minHeap.top(); } // 递归地生成哈夫曼编码 void generateHuffmanCodes(HuffmanNode* root, string code, map<char, string>& huffmanCodes) { if (root == nullptr) { return; } if (root->data != '$') {//读到叶子节点 huffmanCodes[root->data] = code;//该字符编码为code } generateHuffmanCodes(root->left, code + "0", huffmanCodes); generateHuffmanCodes(root->right, code + "1", huffmanCodes); //递归实现,访问左子树+0,访问右子树+1 } // 哈夫曼编码 string huffmanEncode(string text, map<char, string>& huffmanCodes) { string encodedText = "";//初始化result为空字符串 for (char c : text) { encodedText += huffmanCodes[c];//根据字符c加入相应的哈夫曼编码 } return encodedText;//返回结果 } // 哈夫曼译码 string huffmanDecode(string encodedText, HuffmanNode* root) { string decodedText = "";//初始化译码结果为空字符串 HuffmanNode* current = root; for (char bit : encodedText) { if (bit == '0') {//读到'0'访问左子树,读到'1'访问右子树 current = current->left; } else { current = current->right; } if (current->data != '$') {//读到叶子节点,确定该段哈夫曼编码译码结果 decodedText += current->data; current = root;//返回根节点继续下次译码 } } return decodedText; } int main() { //string text = "hello world"; string text; cin>>text; map<char, int> frequencies; // 计算字符频率 for (char c : text) { frequencies[c]++; } // 构建哈夫曼树 HuffmanNode* root = buildHuffmanTree(frequencies); // 生成哈夫曼编码 map<char, string> huffmanCodes; generateHuffmanCodes(root, "", huffmanCodes); // 打印哈夫曼编码 cout << "Huffman Codes:" << endl; for (auto& entry : huffmanCodes) { cout << entry.first << ": " << entry.second << endl;//打印键值对 } // 哈夫曼编码 string encodedText = huffmanEncode(text, huffmanCodes); cout << "Encoded Text: " << encodedText << endl; // 哈夫曼译码 string decodedText = huffmanDecode(encodedText, root); cout << "Decoded Text: " << decodedText << endl; return 0; } 总结 通过测试，确保程序正确实现了哈夫曼树的构建、编码和译码功能。特别注意频率相同字符的处理，确保其相对顺序不变。在构建哈夫曼树时，使用最小堆保证了节点按照频率的升序排列。 排序二叉树的构建和节点删除 a 问题分析 本实验的目标是实现基于排序二叉树的节点插入、中序遍历、删除整个树以及删除单独某个节点的功能。具体要求包括使用struct实现节点，实现插入节点和删除节点的功能。 b 算法设计 插入节点算法设计 插入节点的算法是一个递归算法。根据节点值与当前节点值的比较，选择插入到左子树或右子树。如果当前子树为空，创建一个新节点并返回；否则，递归调用插入函数。 TreeNode* insert(TreeNode* root, int val) { if (root == nullptr) { return new TreeNode(val); } if (val <= root->data) { root->left = insert(root->left, val); } else if (val > root->data) { root->right = insert(root->right, val); } return root; } 构建排序二叉树算法设计 构建排序二叉树的算法使用了插入节点算法。遍历输入序列，对每个元素调用插入节点函数，不断更新根节点，最终得到一个排序二叉树。 TreeNode* buildTree(int input[], int size) { TreeNode* root = nullptr; for (int i = 0; i < size; ++i) { root = insert(root, input[i]); } return root; } 中序遍历算法设计 中序遍历算法用于输出排序二叉树的节点值，以验证树的构建是否正确。 void inorderTraversal(TreeNode* node) { if (node != nullptr) { inorderTraversal(node->left); cout << node->data << " "; inorderTraversal(node->right); } } 删除整个树算法设计 删除整个树的算法是一个递归算法。递归调用删除函数，删除左子树和右子树，最后删除当前节点。 void deleteTree(TreeNode* node) { if (node != nullptr) { deleteTree(node->left); deleteTree(node->right); delete node; } } 删除单独某个节点算法设计 删除单独某个节点的算法是一个递归算法。根据节点值与待删除值的比较，选择在左子树或右子树中进行删除。如果找到匹配的节点，分三种情况处理：节点没有子节点、节点有一个子节点、节点有两个子节点。 TreeNode* deleteNode(TreeNode* root, int val) { if (root == nullptr) { return root; } // 找到匹配节点 if (val < root->data) { root->left = deleteNode(root->left, val); } else if (val > root->data) { root->right = deleteNode(root->right, val); } else { // 节点有一个或无子节点 if (root->left == nullptr) { TreeNode* temp = root->right; delete root; return temp; } else if (root->right == nullptr) { TreeNode* temp = root->left; delete root; return temp; } // 节点有两个子节点，找到右子树的最小节点 TreeNode* minRight = root->right; while (minRight->left != nullptr) { minRight = minRight->left; } // 复制最小节点的值到当前节点 root->data = minRight->data; // 删除右子树中的最小节点 root->right = deleteNode(root->right, minRight->data); } return root; } // 删除单独某个节点的接口函数 TreeNode* deleteSingleNode(TreeNode* root, int val) { TreeNode* nodeToDelete = findNode(root, val); if (nodeToDelete != nullptr) { root = deleteNode(root, val); } return root; } c 数据结构设计 节点结构 struct TreeNode { int data; TreeNode* left; TreeNode* right; TreeNode(int val) : data(val), left(nullptr), right(nullptr) {} }; d 调试过程 在调试过程中，首先确保 deleteSingleNode 函数能够正确执行。通过删除单独某个节点后，使用中序遍历验证排序二叉树的节点值，以确保删除操作的正确性。最后，通过输出验证整个实现的正确性。 e 输出结果 针对输入序列 7, 5, 9, 2, 5, 2, 6, 3, 7, 0，实验的输出结果如下： 排序二叉树: 0 2 2 3 5 5 6 7 7 9 删除节点 3 后的排序二叉树: 0 2 2 5 5 6 7 7 9 删除单独节点 5 后的排序二叉树: 0 2 2 6 7 7 9 这个输出结果表明删除单独某个节点的功能已经添加，并且在删除节点 5 后，中序遍历输出排序二叉树的节点值，验证删除操作的正确性。 f 源代码 #include <iostream> using namespace std; // 定义二叉树节点 struct TreeNode { int data; TreeNode* left; TreeNode* right; TreeNode(int val) : data(val), left(nullptr), right(nullptr) {} }; // 插入节点到排序二叉树 TreeNode* insert(TreeNode* root, int val) { if (root == nullptr) { return new TreeNode(val); } if (val <= root->data) { root->left = insert(root->left, val); } else if (val > root->data) { root->right = insert(root->right, val); } return root; } // 中序遍历 void inorderTraversal(TreeNode* node) { if (node != nullptr) { inorderTraversal(node->left); cout << node->data << " "; inorderTraversal(node->right); } } // 删除整个树 void deleteTree(TreeNode* node) { if (node != nullptr) { deleteTree(node->left); deleteTree(node->right); delete node; } } // 查找节点值为val的节点 TreeNode* findNode(TreeNode* root, int val) { if (root == nullptr || root->data == val) { return root; } if (val < root->data) { return findNode(root->left, val); } else { return findNode(root->right, val); } } // 删除单独某个节点 TreeNode* deleteNode(TreeNode* root, int val) { if (root == nullptr) { return root; } // 找到匹配节点 if (val < root->data) { root->left = deleteNode(root->left, val); } else if (val > root->data) { root->right = deleteNode(root->right, val); } else { // 节点有一个或无子节点 if (root->left == nullptr) { TreeNode* temp = root->right; delete root; return temp; } else if (root->right == nullptr) { TreeNode* temp = root->left; delete root; return temp; } // 节点有两个子节点，找到右子树的最小节点 TreeNode* minRight = root->right; while (minRight->left != nullptr) { minRight = minRight->left; } // 复制最小节点的值到当前节点 root->data = minRight->data; // 删除右子树中的最小节点 root->right = deleteNode(root->right, minRight->data); } return root; } // 删除单独某个节点的接口函数 TreeNode* deleteSingleNode(TreeNode* root, int val) { TreeNode* nodeToDelete = findNode(root, val); if (nodeToDelete != nullptr) { root = deleteNode(root, val); } return root; } int main() { int input[] = {7, 5, 9, 2, 5, 2, 6, 3, 7, 0}; TreeNode* root = nullptr; // 构建排序二叉树 for (int i = 0; i < 10; ++i) { root = insert(root, input[i]); } // 显示排序二叉树 cout << "排序二叉树: "; inorderTraversal(root); cout << endl; // 删除节点 3 后的排序二叉树 int nodeToDelete = 3; root = deleteNode(root, nodeToDelete); cout << "删除节点 " << nodeToDelete << " 后的排序二叉树: "; inorderTraversal(root); cout << endl; // 删除单独节点 5 后的排序二叉树 int singleNodeToDelete = 5; root = deleteSingleNode(root, singleNodeToDelete); cout << "删除单独节点 " << singleNodeToDelete << " 后的排序二叉树: "; inorderTraversal(root); cout << endl; // 删除整个树 deleteTree(root); return 0; }
数据结构实机实验报告4——二叉树的构建（完全二叉树BFS结果）、存储（顺序存储与链式存储）、遍历（BFS与DFS）
1. 根据输入创建二叉树，顺序存储和链式存储 a. 问题分析： 在这个问题中，需要根据输入的字符序列创建一个二叉树，要求实现两种存储方式：顺序存储和链式存储。输入的字符序列中，字符 '@' 表示空节点。 b. 算法设计： 顺序存储方式： 初始化一个数组来表示顺序存储的二叉树。 依次遍历输入字符序列，将字符按照顺序存储到数组中。 可以使用数组的索引来表示节点的位置，假设父节点的索引为 i，则左子节点的索引为 2*i + 1，右子节点的索引为 2*i + 2。 将 '@' 字符表示的空节点跳过，只存储实际的数据。 链式存储方式： 创建一个结构体 TreeNode 来表示二叉树的节点，包含数据、左子树指针和右子树指针。 使用队列数据结构辅助构建二叉树。初始化一个根节点，将其入队。 遍历输入字符序列，每次从队列中取出一个节点，为其创建左子节点和右子节点，然后将它们入队。 c. 数据结构设计： 顺序存储方式： struct TreeNode 用于表示二叉树的节点。 数组用于顺序存储二叉树节点。 链式存储方式： struct TreeNode 用于表示二叉树的节点，包含数据、左子树指针和右子树指针。 队列数据结构用于辅助构建二叉树。 d. 调试过程： 运行程序，按照输入样例输入字符以构建二叉树。 确保输入的字符顺序正确，空节点用 '@' 表示。 链式存储时用'#'表示输入完毕 验证创建的二叉树的顺序存储和链式存储是否正确。 e. 输出结果： 输出结果包括顺序存储的二叉树节点数据和链式存储的二叉树的遍历结果。 2. 深度遍历算法的实现 a. 问题分析： 在这个问题中，需要实现深度遍历算法，包括前序遍历、中序遍历和后序遍历。对于顺序存储的二叉树，需要实现相应的遍历算法。 b. 算法设计： 前序遍历： 访问根节点，然后递归遍历左子树和右子树。 中序遍历： 先递归遍历左子树，然后访问根节点，最后递归遍历右子树。 后序遍历： 先递归遍历左子树和右子树，然后访问根节点。 c. 数据结构设计： 递归算法。 3. 广度遍历算法的实现 a. 问题分析： 在这个问题中，需要实现广度遍历算法（层次遍历）。对于链式存储的二叉树，需要实现相应的遍历算法。 b. 算法设计： 使用队列数据结构，从根节点开始，将节点逐层加入队列，并逐个访问队列中的节点。 c. 数据结构设计： 队列数据结构。 非常抱歉，我理解你的要求，下面将使用具体的样例 abc@@@d@ef@ 和 abc@@@d@ef@# 来完善调试过程和输出结果，并结合你提供的代码进行说明。 样例 abc@@@d@ef@，abc@@@d@ef@# 调试过程： 使用顺序存储方式： 依次读入字符 'a'， 'b'， 'c'， '@'， '@'， '@'， 'd'， '@'， 'e'， 'f'。 构建顺序存储的二叉树，数组元素如下： ['a', 'b', 'c', '@', '@', '@', 'd', '@', 'e', 'f']。 使用链式存储方式： 创建根节点 'a'，将其入队。 读入字符 'b'，创建 'a' 的左子节点 'b'，将其入队。 读入字符 'c'，创建 'a' 的右子节点 'c'，将其入队。 读入字符 '@'，表示左子节点为空。 读入字符 '@'，表示右子节点为空。 读入字符 'd'，创建 'b' 的左子节点 'd'，将其入队。 读入字符 '@'，表示右子节点为空。 读入字符 'e'，创建 'c' 的左子节点 'e'，将其入队。 读入字符 'f'，创建 'c' 的右子节点 'f'，将其入队。 输出结果： 顺序存储方式： 先序遍历结果： a b d c e f 中序遍历结果： d b a e c f 后序遍历结果： d b e f c a 链式存储方式： 前序遍历结果： a b d c e f 中序遍历结果： b d a e c f 后序遍历结果： d b e f c a 广度优先搜索（层次遍历）结果： a b c d e f源代码 顺序存储 #include<bits/stdc++.h> using namespace std; #define MAX_NODES 1000 // 最大节点数量 // 定义二叉树结点结构 struct TreeNode { char data; }; // 创建一个新的二叉树结点 TreeNode* createNode(char data) { TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode)); newNode->data = data; return newNode; } // 顺序存储的字符二叉树结构 struct SequentialTree { TreeNode* nodes[MAX_NODES]; int size; // 记录节点数量 }; // 初始化顺序存储的字符二叉树 void initSequentialTree(SequentialTree* tree) { tree->size = 0; for (int i = 0; i < MAX_NODES; i++) { tree->nodes[i] = nullptr; } } // 插入一个节点到顺序存储的字符二叉树 void insertNode(SequentialTree* tree, char data) { if (tree->size < MAX_NODES) { TreeNode* newNode = createNode(data); tree->nodes[tree->size] = newNode; tree->size++; } else { printf("该二叉树已满，无法插入节点\n"); } } // 获取根节点 TreeNode* getRoot(SequentialTree* tree) { return tree->nodes[0]; } // 获取左子节点 TreeNode* getLeftChild(SequentialTree* tree, int parentIndex) { int leftChildIndex = 2 * parentIndex + 1; if (leftChildIndex < tree->size) {//检验是否存在 return tree->nodes[leftChildIndex]; } return nullptr; } // 获取右子节点 TreeNode* getRightChild(SequentialTree* tree, int parentIndex) { int rightChildIndex = 2 * parentIndex + 2; if (rightChildIndex < tree->size) { return tree->nodes[rightChildIndex]; } return nullptr; } // 前序遍历 void preorderTraversal(struct SequentialTree* tree, int index) { if (index >= tree->size || tree->nodes[index]->data == '@') { return; } printf("%c ", tree->nodes[index]->data); // 访问根节点 preorderTraversal(tree, 2 * index + 1); // 遍历左子树 preorderTraversal(tree, 2 * index + 2); // 遍历右子树 } // 中序遍历 void inorderTraversal(struct SequentialTree* tree, int index) { if (index >= tree->size || tree->nodes[index]->data == '@') { return; } inorderTraversal(tree, 2 * index + 1); // 遍历左子树 printf("%c ", tree->nodes[index]->data); // 访问根节点 inorderTraversal(tree, 2 * index + 2); // 遍历右子树 } // 后序遍历 void postorderTraversal(struct SequentialTree* tree, int index) { if (index >= tree->size || tree->nodes[index]->data == '@') { return; } postorderTraversal(tree, 2 * index + 1); // 遍历左子树 postorderTraversal(tree, 2 * index + 2); // 遍历右子树 printf("%c ", tree->nodes[index]->data); // 访问根节点 } int main() { SequentialTree* tree=(SequentialTree*)malloc(sizeof(SequentialTree)); initSequentialTree(tree); char data='a'; while (1){ cin>>data; if(data=='#'){ break; } insertNode(tree,data); } cout<<"先序遍历结果:"<<endl; preorderTraversal(tree,0); cout<<endl; cout<<"中序遍历结果:"<<endl; inorderTraversal(tree,0); cout<<endl; cout<<"后序遍历结果:"<<endl; postorderTraversal(tree,0); cout<<endl; cout<<"层次遍历结果:"<<endl; for(int i=0;i<tree->size;i++){ if(tree->nodes[i]->data!='@') cout<<tree->nodes[i]->data<<' '; } cout<<endl; return 0; } 链式存储 #include<bits/stdc++.h> using namespace std; // 二叉树结点结构 struct TreeNode { char data; TreeNode* left; TreeNode* right; TreeNode(char val) : data(val), left(nullptr), right(nullptr) {} }; // 创建链式存储的二叉树 TreeNode* createBinaryTree(const string& input) { if (input.empty()) { return nullptr; } queue<TreeNode*> nodeQueue; TreeNode* root = new TreeNode(input[0]); nodeQueue.push(root); for (int i = 1; i < input.length(); i += 2) { TreeNode* current = nodeQueue.front(); nodeQueue.pop(); if (input[i] != '@') { current->left = new TreeNode(input[i]); nodeQueue.push(current->left); } if (i + 1 < input.length() && input[i + 1] != '@') { current->right = new TreeNode(input[i + 1]); nodeQueue.push(current->right); } } return root; } // 前序遍历 void preorderTraversal(TreeNode* root) { if (root) { cout << root->data << " "; preorderTraversal(root->left); preorderTraversal(root->right); } } // 中序遍历 void inorderTraversal(TreeNode* root) { if (root) { inorderTraversal(root->left); cout << root->data << " "; inorderTraversal(root->right); } } // 后序遍历 void postorderTraversal(TreeNode* root) { if (root) { postorderTraversal(root->left); postorderTraversal(root->right); cout << root->data << " "; } } // 广度优先搜索（层次遍历） void breadthFirstTraversal(TreeNode* root) { if (!root) { return; } queue<TreeNode*> nodeQueue; nodeQueue.push(root); while (!nodeQueue.empty()) { TreeNode* current = nodeQueue.front(); nodeQueue.pop(); cout << current->data << " "; if (current->left) { nodeQueue.push(current->left); } if (current->right) { nodeQueue.push(current->right); } } } int main() { string input; cin>>input; TreeNode* root = createBinaryTree(input); cout << "前序遍历结果: "; preorderTraversal(root); cout << endl; cout << "中序遍历结果: "; inorderTraversal(root); cout << endl; cout << "后序遍历结果: "; postorderTraversal(root); cout << endl; cout << "广度优先搜索（层次遍历）结果: "; breadthFirstTraversal(root); cout << endl; return 0; }
数据结构实机实验报告3——KMP算法用于字符串搜索
实验目的： 本实验旨在分析和测试KMP算法的实现，并研究其在字符串搜索中的应用。 实验内容： a 问题分析： 如何构建最长前缀后缀匹配表（LPS数组）以提高搜索效率？ 如何在文本字符串中执行匹配，利用LPS数组来避免不必要的字符比较？ 如何设计算法以实现模式字符串的搜索？ b 算法设计： KMP算法的设计包括以下关键步骤： 构建LPS数组：使用computeLPSArray函数来计算模式字符串的LPS数组，该数组指示了模式字符串中每个位置的前缀和后缀的最长匹配长度。 在文本中执行匹配：使用KMPSearch函数，该函数在文本字符串中执行模式字符串的匹配。它使用LPS数组来智能地回溯，以提高搜索效率。 c 数据结构设计： 在这次实验中，我使用了以下数据结构： 字符串：用于表示文本字符串和模式字符串。 向量（vector）：用于存储LPS数组。 整数变量：用于表示匹配过程中的索引。 d 调试过程： 在编写和测试代码时，我遇到了一些可能的问题，如逻辑错误或边界情况。这些问题需要仔细调试，以确保算法的正确性和性能。通过逐步调试和打印输出结果，我确认代码能够正确地找到模式字符串在文本中的匹配位置。 e 输出结果： 以下是一些示例输出结果： 当文本字符串为"ABABDABACDABABCABAB"，模式字符串为"ABABCABAB"时，KMP算法找到了模式字符串在文本中的匹配位置：在索引 10 处找到匹配串 当文本字符串和模式字符串由用户输入时，KMP算法会在用户提供的文本中查找用户提供的模式，并输出匹配位置。 f 源代码： #include<bits/stdc++.h> using namespace std; // 计算匹配字符串的最长前缀后缀匹配表（LPS数组） void computeLPSArray(const string& pattern, vector<int>& lps) { int length = 0; // 前一个最长前缀后缀匹配的长度 lps[0] = 0; // lps[0] 总是为 0 int i = 1; while (i < pattern.length()) { if (pattern[i] == pattern[length]) { length++; lps[i] = length; i++; } else { if (length != 0) { length = lps[length - 1]; } else { lps[i] = 0; i++; } } } } // 使用KMP算法在文本中搜索匹配字符串 void KMPSearch(const string& text, const string& pattern) { int m = pattern.length(); int n = text.length(); vector<int> lps(m); computeLPSArray(pattern, lps); int i = 0; // 用于文本[] int j = 0; // 用于匹配串[] while (i < n) { if (pattern[j] == text[i]) { i++; j++; } if (j == m) { // 找到匹配串，打印起始位置 cout << "在索引 " << i - j << " 处找到匹配串" << endl; j = lps[j - 1]; } else if (i < n && pattern[j] != text[i]) { if (j != 0) { j = lps[j - 1]; } else { i++; } } } } // int main() { // string text = "ABABDABACDABABCABAB"; // string pattern = "ABABCABAB"; // KMPSearch(text, pattern); // return 0; // } int main() { string text; string pattern; cin>>text; cin>>pattern; KMPSearch(text, pattern); return 0; }
数据结构实机实验报告2——稀疏矩阵乘法
问题分析 本实验的主要目标是开发一个稀疏矩阵乘法算法，该算法能够将两个稀疏矩阵 A 和 B 相乘，然后输出结果矩阵 C。在这个算法中，稀疏矩阵使用三元组表示，并且用户可以多次输入不同的矩阵数据，计算它们的乘积。 算法设计 稀疏矩阵乘法算法的设计如下： 使用 struct 结构体来表示矩阵，其中包括矩阵的行数、列数、稀疏矩阵元素的个数，以及一个数组用于存储节点的信息。 输入函数 input 用于获取矩阵的三元组表示，检查输入的合法性，然后存储在内存中的结构体中。 输出函数 output 将稀疏矩阵以标准矩阵的形式打印出来，便于用户查看。 矩阵乘法函数 multiplier 接受两个输入矩阵 A 和 B，计算它们的乘积，并将结果存储在矩阵 C 中。数据结构设计 matrix 结构体包含了矩阵的行数 m、列数 n、稀疏矩阵元素的个数 L，以及 Ma 数组用于存储节点信息。 node 结构体表示稀疏矩阵的每个非零元素，包括行索引 i、列索引 j 以及元素的值 data。调试过程 代码中有一些错误处理机制，例如检查输入是否合法，检查内存分配是否成功，以及检查矩阵相乘是否合法。 在输入稀疏矩阵数据时，用户会得到错误消息并要求重新输入，以确保输入的数据符合矩阵的大小。 稀疏矩阵乘法算法中，会检查矩阵的列和行是否匹配，以确保它们可以相乘。输出结果 Matlab验证结果： 用户可以输入两个矩阵 A 和 B，然后程序会计算它们的乘积并输出结果矩阵 C。用户可以选择继续进行稀疏矩阵乘法计算，也可以选择退出程序。程序会一直运行，直到用户选择退出。 总结 总体而言，该实验成功实现了稀疏矩阵的乘法操作，提供了友好的用户界面和错误处理机制，以确保输入的矩阵数据是有效的。然后，它正确计算了两个稀疏矩阵的乘积并将结果以标准矩阵的形式输出。 源代码 #include<bits/stdc++.h> using namespace std; #define MAX 1000 struct node{ int i; int j; int data; }; struct matrix{ int m; int n; int L; node* Ma[MAX]; }; int input(matrix* A){ int m,n,data; for(int i=0;i<A->L;i++){ cin>>m>>n>>data; if(m<0||m>=A->m||n<0||n>=A->n){ cout<<"输入错误,行/列超出矩阵大小!"<<endl; return 1; } A->Ma[i]=(node*)malloc(sizeof(node)); if(!A->Ma[i]){ cout<<"申请空间失败!"<<endl; return 2; }else{ A->Ma[i]->i=m; A->Ma[i]->j=n; A->Ma[i]->data=data; } } return 0; } void output(matrix* A,string name){ cout<<"矩阵"<<name<<"为:"<<endl; int nums[A->m][A->n]; memset(nums,0,sizeof(nums)); for(int i=0;i<A->L;i++){ nums[A->Ma[i]->i][A->Ma[i]->j]=A->Ma[i]->data; } for(int i=0;i<A->m;i++){ for(int j=0;j<A->n;j++){ cout<<nums[i][j]<<'\t'; } cout<<endl; } } void multiplier(matrix* A,matrix* B,matrix* C){ C->m=A->m; C->n=B->n; C->L=0; int x,y,z; bool sert=false; for(int i=0;i<A->L;i++){ for(int j=0;j<B->L;j++){ if(A->Ma[i]->j==B->Ma[j]->i){//A的列号==B的行号 x=A->Ma[i]->i; y=B->Ma[j]->j; z=A->Ma[i]->data*B->Ma[j]->data; sert=false; for(int k=0;k<C->L;k++){ if(x==C->Ma[k]->i&&y==C->Ma[k]->j){ C->Ma[k]->data+=z; sert=true; break; } } if(!sert){ C->L++; C->Ma[C->L-1]=(node*)malloc(sizeof(node)); C->Ma[C->L-1]->i=x; C->Ma[C->L-1]->j=y; C->Ma[C->L-1]->data=z; } } } } } int main(){ start: matrix* A=(matrix*)malloc(sizeof(matrix)); matrix* B=(matrix*)malloc(sizeof(matrix)); matrix* C=(matrix*)malloc(sizeof(matrix)); cout<<"请输入A矩阵三元组长度,矩阵行数,矩阵列数:"<<endl; cin>>A->L>>A->m>>A->n; cout<<"请输入A矩阵:"<<endl; if(input(A)){ cout<<"出现错误,请重新输入!"<<endl; goto start; } output(A,"A"); cout<<"请输入B矩阵三元组长度,矩阵行数,矩阵列数:"<<endl; cin>>B->L>>B->m>>B->n; cout<<"请输入B矩阵:"<<endl; if(input(B)){ cout<<"出现错误,请重新输入!"<<endl; goto start; } output(B,"B"); multiplier(A,B,C); output(C,"C"); cout<<"是否继续进行稀疏矩阵乘法计算(y/n):"; char choice; choise: cin>>choice; if(choice=='y'||choice=='Y'){ goto start; }else if(choice=='n'||choice=='N'){ return 0; }else{ cout<<"输入错误,请重新输入:"; goto choise; } return 0; }
数据结构上机实验报告1——Fibonacci序列、划分子集问题
Fibonacci序列 问题分析 要正确实现程序的递归调用和返回，必须解决参数的传递和返回地址问题。具体地说，进行调用时，每递归一次都要给所有参变量重新分配储存空间，并要把前一次调用的实参和本次调用后的返回地址保留。 算法设计 算法描述如下： int Fib(int n){ int fib; if(n==0) fib=0; else if(n==1) fib=1; else fib=Fib(n-1)+Fib(n-2); return fib; } 数据结构设计 用栈去分配和管理储存空间，系统在每次执行调用过程的语句时需要开辟一个“工作记录”，用以保存调用前过程中所有参变量的值及调用后的返回地址，将此工作记录存于栈中，以便在返回时能在栈顶找到正确的信息。 调试过程 在每次调用函数的时候，将传入的参数进行输出，可以更直观地看到栈的调用过程。 以最开始Fib（2）的递归调用为例，程序先将Fib（5）、Fib（4）…Fib（1）储存到栈中，当n\==1时，将值返回上一个地址中，同理也将n\==0时的值返回，这样Fib（2）的值便有了，再返回到Fib（2）的上一级Fib（3）中。 输出结果 源代码 #include<bits/stdc++.h> using namespace std; int Fibonacci(int n){ int fib; if(n==0){ fib=0; }else if(n==1){ fib=1; }else if(n==2){ fib=2; }else{ fib=Fibonacci(n-1)+Fibonacci(n-2); } return fib; } int main(){ int n=0; cout<<"请输入n:"; start: cin>>n; cout<<"第n个Fibonacci数为"<<Fibonacci(n)<<endl; cout<<"是否继续计算(y/n):"; char choice; choice: cin>>choice; if(choice=='y'||choice=='Y'){ goto start; }else if(choice=='n'||choice=='N'){ return 0; }else{ cout<<"输入错误,请重新输入:"; goto choice; } return 0; } 划分子集问题 问题分析 问题要求我们将一个集合中划分成互不相交的子集，使任何子集上的元素无任何冲突，且划分的子集数较少。此类问题常用在日程安排上。 算法设计 冲突关系首先通过一个二维数组表示出来，有冲突关系则赋值1，无冲突则赋值0。通过循环筛选法对其划分，即从第一个元素开始，先将元素1单独拿出，逐个判断其他元素是否和拿出的所有元素有冲突关系，无冲突则拿出元素，并划为一组。这样循环一周，所有互相无冲突关系的已被划为一组，循环此操作，即可完成划分要求。 数据结构设计 通过一个循环队列来储存数据，每次循环一周，不断迭代数据，不需要开辟新的存储空间。 调试过程 输出结果 源代码 #include<bits/stdc++.h> using namespace std; int newr[9]; void DivideIntoGroup(int n,int R[][9],int cp[],int result[]) { int front,rear,group,pre,I,i; front=n-1; rear=n-1; for(i=0;i<n;i++) { newr[i]=0; cp[i]=i+1; } group=1; pre=0; do { front=(front+1)%n; I=cp[front]; if(I<pre) { group=group+1; result[I-1]=group; for(i=0;i<n;i++) { newr[i]=R[I-1][i]; } } else { if(newr[I-1]!=0) { rear=(rear+1)%n; cp[rear]=I; } else { result[I-1]=group; for(i=0;i<n;i++) { newr[i]+=R[I-1][i]; } } } pre=I; }while(rear!=front); } int main(){ int result[9],cp[9]; int R[9][9]= { {0,1,0,0,0,0,0,0,0}, {1,0,0,0,1,1,0,1,1}, {0,0,0,0,0,1,1,0,0}, {0,0,0,0,1,0,0,0,1}, {0,1,0,1,0,1,1,0,1}, {0,1,1,0,1,0,1,0,0}, {0,0,1,0,1,1,0,0,0}, {0,1,0,0,0,0,0,0,0}, {0,1,0,1,1,0,0,0,0}, }; DivideIntoGroup(9,R,cp,result); for(int i=0;i<9;i++) { cout<<i+1<<" "; } cout<<endl; for(int i=0;i<9;i++) { cout<<result[i]<<" "; } return 0; }