本站已废弃并迁移，服务器过期后不续费，请转至新博客 https://guzhengsvt.cn - 数据结构
type: channel
link: https://www.guzhengsvt.top/index.php/tag/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/
items: 数据结构实机实验报告8——关键路径
items: 数据结构实机实验报告7——Kruskal算法与最小生成树问题，Dijkstra算法与带权图最短路径问题
items: 数据结构实机实验报告6——前序、后续将二叉树线索化，图的邻接矩阵和邻接表的存储
items: 数据结构实机实验报告5——哈夫曼树的编码和译码，排序二叉树的构建和节点删除
items: 数据结构实机实验报告4——二叉树的构建（完全二叉树BFS结果）、存储（顺序存储与链式存储）、遍历（BFS与DFS）
items: 数据结构实机实验报告3——KMP算法用于字符串搜索
items: 数据结构实机实验报告2——稀疏矩阵乘法
items: 数据结构上机实验报告1——Fibonacci序列、划分子集问题

数据结构实机实验报告8——关键路径
type: item
date: 2023-12-13T19:14:00+08:00
description: 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，并且每个活动的最早开始时间和最晚开始时间都正确计算。这表明我们的算法和数据结构…

数据结构实机实验报告7——Kruskal算法与最小生成树问题，Dijkstra算法与带权图最短路径问题
type: item
date: 2023-12-12T23:46:00+08:00
description: 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 st…

数据结构实机实验报告6——前序、后续将二叉树线索化，图的邻接矩阵和邻接表的存储
type: item
date: 2023-12-12T23:43:00+08:00
description: 前序、后续将二叉树线索化 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) { // 如…

数据结构实机实验报告5——哈夫曼树的编码和译码，排序二叉树的构建和节点删除
type: item
date: 2023-12-12T23:36:00+08:00
description: 实现哈夫曼树的编码和译码 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')…

数据结构实机实验报告4——二叉树的构建（完全二叉树BFS结果）、存储（顺序存储与链式存储）、遍历（BFS与DFS）
type: item
date: 2023-12-12T23:30:00+08:00
description: 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];…

数据结构实机实验报告3——KMP算法用于字符串搜索
type: item
date: 2023-12-12T23:20:00+08:00
description: 实验目的： 本实验旨在分析和测试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——稀疏矩阵乘法
type: item
date: 2023-12-12T23:16:00+08:00
description: 问题分析 本实验的主要目标是开发一个稀疏矩阵乘法算法，该算法能够将两个稀疏矩阵 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…

数据结构上机实验报告1——Fibonacci序列、划分子集问题
type: item
date: 2023-12-12T23:06:00+08:00
description: 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,…