稀疏矩阵数据结构实验报告

《稀疏矩阵数据结构实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1•需求分析12.概要设计22.1链表对稀疏矩阵进行定义22.3程序一共有五个功能23.i羊细设计33.1稀疏矩阵存储算法分析33.2稀疏矩阵各运算算法分析34•调试分析84.1调试过程中的问题及解决方法84.2算法的时间复杂度和空间复杂84.3经验和体会85•用户使用说明96.次I］试纟吉果106.1程序主界面106.2其他函数操作界面显示1016参考文献15致谢1.需求分析矩阵在日常生活中应用广泛，尤其是有些特殊矩阵的运算。但是在实际应用中有一种矩阵，在mXn的矩阵中有t个非零元素，且t远小于mXn,我们这样的

2、矩阵被称为稀疏矩阵。由于这类矩阵中通常零元素是没有规律的，为了能够找到相应的元素，仅存储非零元素的值是不行的，还要存储其所在的行和列等信息。本程序主要的任务是创建稀疏矩阵，并且利用C++算法程序实现相应的运算（转置，加法，减法，乘法）（1）输入的形式以及范围：键盘输入符合要求的稀疏矩阵。（2）输出形式：最终运算结果以矩阵的形式输出。（3）程序功能实现：输入矩阵通过程序运算出相应的转置矩阵以及两个符合要求的矩阵的加减乘除法的运算。（4）测试数据：如果输入正确，程序会显示最后的运算结果；否则错误时则会返回上层。2・概要

3、设计要存储稀疏矩阵并且进行运算，那么就要了解稀疏矩阵的存储结构，这里采用链表的形式存储稀疏矩阵并进行运算。2.1链表对稀疏矩阵进行定义typedefstructOLNode{//定义链表元素inti,j；inte;structOLNode*next;//该非零元所在行表和列表的后继元素JOLNode^OLink;typedefstruct{//定义链表对彖结构体OLink*head;intmu,nu,tu;}CrossList;//头指针//行数，列数，和非零元素个数2.3程序一共有五个功能1.用CreateSMa

4、trix_OL(M)函数来实现稀疏矩阵的存储，用OutPutSMatrix_OL(M)函数实现稀疏矩阵的输出。2.使用TransposeSMatrix()函数实现稀疏矩阵的转置操作。3.使用AddSMatrix(数实现稀疏矩阵的加法运算。4.使用SubSMatrix(数实现稀疏矩阵的减法运算。5.使用MultSMatrix()函数实现稀疏矩阵的乘法运算。在TransposeSMatrix(),AddSMatrix(),SubSMatrix(),MultSMatrix()各函数中乂调用到矩阵的存入和输岀函数。图2-1

5、程序主要函数关系2.详细设计3.1稀疏矩阵存储算法分析链表存储稀疏矩阵的基本思想是：创建一个数据域还有一个指针域，数据域用来存储该非零元素的行、列、数值；指针域next指向下一结点。如图3-1所行列值Next图3-1链表的结点结构把稀疏矩阵的三元素(行数、列数、非零元素个数)放在头结点中，头结点的next指向第一个结点。数据结点中数据域存储行值、列值、数值，指针指向下一个结点，这样把一个个的结点连接起来。在此以稀疏矩阵如图3-2:000-1000为例，画出十字链表存储的结构图0head图3-2十字链表312fMIL

6、L3.2稀疏矩阵各运算算法分析根据整个程序的功能分析，该稀疏矩阵程序需要实现以下运算功能:(1)稀疏矩阵的转置(2)稀疏矩阵的乘法(3)稀疏矩阵的加法(4)稀疏矩阵的减法根据整个函数的具体分析，从屮可以剖析出程序具有以下函数表3-1程序中的函数列表相应函数相应功能CreateSMatrixOL(CrossList&M)用链表的方式存储稀疏矩阵OutPutSMatrixOL(CrossListT)读収用链表存储的稀疏矩阵TransposeSMatrix()转置矩阵MultSMatrix()稀疏矩阵的乘法AddSMat

7、rix()稀疏矩阵的加法SubSMatrix()稀疏矩阵的减法3.2.1TransposeSMatrix()函数该函数是对输入的稀疏矩阵进行转置，设原矩阵为M是一个mXn稀疏矩阵，那么其转置矩阵N就是一个nXm的稀疏矩阵。只要把稀疏矩阵M的行、列转化为T的列、行。调用CreateSMatrix_OL(CrossList&M)函数读取要转置的矩阵M,定义转置后的矩阵N。复制矩阵M的头结点，设当前指针为P,逐个读取存储矩阵M的链表信息，对读取的数据域中对行值和列值进行交换操作，并把操作后的结点连接到存储矩阵N的链表中，

8、直到链表读取结束。调用OutPutSMat「ix_OL(CrossListT)函数读取转置后的矩阵N。3.3.2MultSMatrix()函数该函数是实现两个稀疏矩阵的乘法。调用CreateSMatrix_OL(CrossList&M)函数读取要进行运算的两个矩阵M,N,定义结果矩阵Q。判断M的行数值是否等于N的列数值，若相等则进行运算，若不相等则返回上一函