数据结构实验6.2：稀疏矩阵的基本运算-EW帮帮网

文章目录

一，实验目的
二，问题描述
三，基本要求
四、算法分析
五，实验操作
六，示例代码
七，运行效果

一，实验目的

深入理解数组的存储结构与操作原理，熟练掌握矩阵的基本运算规则，包括矩阵的加法、乘法等，能够运用数组准确表示矩阵并实现相关运算，提升对数据结构中基础内容的应用能力。
全面掌握稀疏矩阵的三元组表示方法，清晰理解其存储原理，包括非零元素的行、列和值如何在三元组中记录，能够灵活运用该表示方法对稀疏矩阵进行高效存储与操作。
熟练掌握基于稀疏矩阵三元组表示的各种运算，如矩阵的转置、加法、乘法等，通过实际编程实现这些运算，深入体会稀疏矩阵在节省存储空间和提高运算效率方面的优势，增强对复杂数据结构运算的编程实现能力。

二，问题描述

设有两个6×6稀疏矩阵A、B如下：

编程实现稀疏矩阵的下列运算：

向稀疏矩阵三元组插入一个新元素；
求两个稀疏矩阵相加：C = A + B；
求两个稀疏矩阵相乘：C = A × B；
求稀疏矩阵A的转置矩阵AT。

三，基本要求

设计稀疏矩阵三元组表示法的存储结构；
设计基于三元组的稀疏矩阵的插入、创建及输出算法；
设计基于三元组表示的稀疏矩阵的相加、相乘及求转置的算法；
设计求解稀疏矩阵各种运算问题的完整程序，设计测试数据，上机调试、测试，保存和打印测试结果，对结果进行分析；
掌握本实验中的各种算法。改写主函数，改用菜单控制方式完成本实验。

四、算法分析

（一）稀疏矩阵三元组表示法存储结构

采用结构体来定义三元组存储结构，结构体包含行索引、列索引和元素值三个成员，同时为了方便记录矩阵的行数、列数和非零元素个数，可再设计一个结构体来管理三元组数组。例如：

typedef struct {
   
    int row;
    int col;
    int value;
} Triple;

typedef struct {
   
    Triple data[MAXSIZE];
    int rows;
    int cols;
    int num;
} SparseMatrix;

这种结构可以高效地存储稀疏矩阵，只记录非零元素的相关信息，大大节省存储空间。

（二）插入算法

遍历三元组数组，根据新元素的行索引和列索引确定插入位置。如果存在相同位置的元素，则更新其值；否则，将后续元素后移，插入新元素，并更新矩阵的非零元素个数。时间复杂度为 $O (n)$ ，其中 $n$ 是三元组数组中元素的个数，因为在最坏情况下需要遍历整个数组来确定插入位置。

（三）创建算法

从输入获取矩阵的行数、列数和非零元素个数，然后依次输入每个非零元素的行索引、列索引和值，按照插入算法的逻辑将元素插入到三元组数组中。时间复杂度取决于输入非零元素的个数，若有 $m$ 个非零元素，则时间复杂度为 $O (m)$ 。

（四）输出算法

遍历三元组数组，按照矩阵的格式输出非零元素，对于非非零元素位置输出0。时间复杂度为 $O (n)$ ，其中 $n$ 是三元组数组中元素的个数。

（五）相加算法

同时遍历两个稀疏矩阵的三元组数组，根据行索引和列索引判断元素是否对应。若对应，则将元素值相加，若结果不为0则存入结果矩阵的三元组数组；若不对应，则将较小索引对应的元素直接存入结果矩阵。时间复杂度为 $O (m + n)$ ，其中 $m$ 和 $n$ 分别是两个稀疏矩阵三元组数组中元素的个数。

（六）相乘算法

对于矩阵A的每一个非零元素，遍历矩阵B中相同列索引（即A元素的列索引等于B元素的行索引）的非零元素，将它们的值相乘并累加到结果矩阵对应位置。时间复杂度较高，为 $\times n \times p)$ ，其中 $m$ 、 $n$ 、 $p$ 分别是矩阵A、B三元组数组中元素的个数以及结果矩阵可能的非零元素个数。