稀疏矩阵相乘课程设计报告马良

学号：0121310870534课程设计题目稀疏矩阵相乘学院计算机科学与技术专业计算机科学与技术卓越工程师班级计算机zy1301姓名马良指导教师杨克俭2014年12月25日武汉理工大学《数据结构》课程设计说明书1目录课程设计任务书.......................................................................................................21．问题描述.............................................................................................................31.1问题描述......................................................................................................31.2基本要求......................................................................................................31.3测试数据......................................................................................................32.实现分析...............................................................................................................33．程序设计.............................................................................................................43.1存储结构设计..............................................................................................43.1.1三元组表示稀疏矩阵........................................................................43.1.2十字链表表示稀疏矩阵....................................................................43.2主要算法设计..............................................................................................53.2.1程序主要函数原型及功能................................................................53.2.2各函数的实现....................................................................................63.2.3程序流程图.....................................................................................114.调试报告.............................................................................................................124.1调试中的问题............................................................................................124.2设计分析....................................................................................................125.程序运行结果...................................................................................................126.经验和体会.........................................................................................................137.源程序.................................................................................................................14参考文献：.......................................................................................................22本科生课程设计成绩评定表.................................................................................23武汉理工大学《数据结构》课程设计说明书2课程设计任务书学生姓名：马良专业班级：计算机zy1301班指导教师：杨克俭工作单位：计算机科学系题目:稀疏矩阵相乘初始条件：稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。（1）以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵（2）实现两个矩阵相乘的运算。（3）稀疏矩阵采用十字链表表示，而运算结果的矩阵则以通常的阵列形式列出。（4）测试用例见严蔚敏《数据结构习题集(C语言版)》p136。要求完成的主要任务:（包括课内实践工作量及其技术要求，以及说明书撰写等具体要求）课内实践报告按学校规定格式用A4纸打印（书写），并应包含如下内容：1.问题描述简述题目要解决的问题是什么。2.设计存储结构设计、主要算法设计（用类C/C++语言或用框图描述）、测试用例设计；3.调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4.经验和体会（包括对算法改进的设想）5.附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出。说明：1.设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。2.凡拷贝往年任务书或课内实践充数者，成绩一律无效，以0分记。时间安排：1．第16周完成，验收时间为12月26日（星期五）下午2．验收地点：实验中心3．验收内容：可执行程序与源代码、课内实践报告书。指导教师签名：2014年11月4日系主任（或责任教师）签名：年月日武汉理工大学《数据结构》课程设计说明书3课程设计报告书1．问题描述1.1问题描述稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。1.2基本要求以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相乘的运算。稀疏矩阵采用十字链表表示，而运算结果的矩阵则以通常的阵列形式列出。1.3测试数据测试用例：严蔚敏《数据结构习题集(C语言版)》p136。4-30013000-600008042080000100*010=0100000701000000002.实现分析（1）根据题目要求，稀疏矩阵采用三元组法顺序输入，十字链表表示。只存储稀疏矩阵中极少的非零元素。（2）各元素按照在原来矩阵中的位置行优先进行存放。（3）在稀疏矩阵十字链表的表示中，每一行都是一个带附加头结点的循环行链表，每一列都是一个带附加头结点的循环列链表。（4）逐个寻找两个矩阵中非零元的位置，第一个矩阵从第一行开始，第二个矩阵从第一列开始，逐渐相乘相加，得到第三个矩阵。武汉理工大学《数据结构》课程设计说明书4（5）如果矩阵中非零元素个数比矩阵元素个数多，返回错误信息，程序结束。（6）若输入成功，输出三个矩阵。3．程序设计3.1存储结构设计3.1.1三元组表示稀疏矩阵只存储在矩阵中极少数的非零元素，用row,col,value来唯一确定一个矩阵元素。在三元组数组中，各矩阵元素按在原矩阵中的位置，以行优先的顺序依次存放，另外还要存储原矩阵的行数、列数和非零元素个数structTrituple{//三元组类Tritupleintrow,col;//非零元素的行号、列号floatvalue;//非零元素的值Trituple&operator=(Trituple&x){row=x.row;col=x.col;value=x.value;}};3.1.2十字链表表示稀疏矩阵在稀疏矩阵十字链表的表示中，每一行都是一个带附加头结点的循环行链表，每一列都是一个带附加头结点的循环列链表。所有的结点都是结点类Node的对象。Node类有一个head域，用来区分该结点是附加头结点还是非零元素结点。每个附加头结点有三个域：d、r、next。第i个行链表和第i个列链表是一个附加头结点，r域存放第i行第一个结点的地址，d域存放第i列第一个结点的地址，next域链接到第i+1个附加头结点。每个非零元素结点有6个域：head，row，col，d，value。r是行链表指针，d是列链表指针。structTrituple{//三元组类Tritupleintrow,col;//非零元素的行号、列号floatvalue;//非零元素的值};classNode;classSparseMatrix武汉理工大学《数据结构》课程设计说明书5{//稀疏矩阵的类定义friendostream&operator(ostream&,SparseMatrix&);//友元函数：输出流操作符重载friendistream&operator(istream&,SparseMatrix&);//友元函数：输入流操作符重载public:SparseMatrix();//构造函数SparseMatrix(inta,intb);//重载构造函数SparseMatrix(SparseMatrix&T);//复制构造函数~SparseMatrix(){makeEmpty();}//析构函数voidInit(inta,intb);//矩阵初始化函数voidmakeEmpty();//清空矩阵voidInsert(inta,intb,floatc);//插入矩阵元素Node*Locate(inti);//定位附加头结点SparseMatrixCheng(SparseMatrixb);//两个矩阵相乘SparseMatrix&operator=(SparseMatrix&T);//重载赋值运算符private:intRow,Col,Terms,t;//矩阵的总行数，总列数，非零元素个数和普通变量；Node*headNode;//稀疏矩阵的总表头};classNode{//矩阵结点类的定义friendclassSparseMatrix;public:Node():head(true){r=d=this;}//建立附加头结点Node(Trituple*t)//建立非零元素结点{triple.col=t-col;triple.row=