数据结构C语言版-稀疏矩阵三元组的基本操作(共33页).doc

《数据结构C语言版-稀疏矩阵三元组的基本操作(共33页).doc》由会员分享，可在线阅读，更多相关《数据结构C语言版-稀疏矩阵三元组的基本操作(共33页).doc（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上数据结构课程设计实验报告内容名称：稀疏矩阵的基本操作 成员1： -陈东 成员2： -蔡丹 班级： 09数31 教师： 李晓翠 江苏师范大学数学科学学院目录1. 序言.31.1数据结构背景.31.2课程设计目的.31.3 课程名称31.4设计要求.31.5设计说明.32课程任务设计说明书.53. 需求分析.6 3.1题目名称.6 3.2题目内容.6 3.3题目分析.64概要设计.7 4.1稀疏矩阵存储结构.7 4.2.稀疏矩阵的基本操作.7 4.3各模块设计要求.8 4.4总体功能流程图.9 4.4.1存储结构流程图.9 4.4.2稀疏矩阵基本操作流程图.105详细设计

2、11 5.1设计原理.115.2基本函数实现流程图136主要函数代码.217调试与操作说明277.1操作说明277.2调试结果. .287.3结果分析318.设计体会329.参考文献3210.分工说明.331.序言1.1数据结构背景数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁。该课程的先行课程是计算机基础、程序设计语言、离散数学等，后续课程有操作系统、编译原理、数据库原理、软件工程等。 通过本门课程的学习，我们应该能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力，而且该课程的研究方法对我们学生在校和

3、离校后的学习和工作，也有着重要的意义。数据结构是计算机科学与技术专业的一门核心专业基础课程，在该专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。基于此原因，我们开设了数据结构课程设计。针对数据结构课程的特点，着眼于培养我们的实践能力。实习课程是为了加强编程能力的培养，鼓励学生使用新兴的编程语言。相信通过数据结构课程实践，无论是理

4、论知识，还是实践动手能力，同学们都会有不同程度上的提高。1.2课程设计的目的巩固和深刻理解“数据结构（C语言版）”课程所讲解的C语言作为数据结构的算法的描述，掌握对数据的存储结构和算法进行描述时，尽量考虑C语言的特色。培养学生独立工作和创新思维的能力，取得设计与调试的实践经验。提高和加强计算机应用及软件开发能力。通过课程设计题目的练习，强化学生对所学知识的掌握及对问题分析和任务定义的理解，对每到题目作出了相应的逻辑分析和数据结构的选择，通过对任务的分析，为操作对象定义相应的数据结构，以过程化程序设计的思想方法为原则划分各个模块，定义数据的抽象数据类型。分模块对题目进行设计，强化学生对C语言的掌

5、握和对数据结构的选择及掌握。通过程序的编译掌握对程序的调试方法及思想，并且让学生学会使用一些编程技巧。促使学生养成良好的编程习惯， 以及让学生对书本上的知识进行了实践。算法与数据结构这门课是计算机科学中一门综合性的专业基础课1.2课程名称：数据结构1.3设计要求学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构，存储结构及其相应的算法，算法要求用C语言完成。学生独立思考解决问题为主，教师指导为辅，结合上机操作，完成指定的任务，撰写课程设计报告。要求源代码有足够的注释，能达到题目要求，并使人能看得懂你的代码。1.5设计说明此课程设计着重在于让我们理解如何利用C语言来实

6、现稀疏矩阵的一些具体操作，里面代码完全采用C语言描述，包括了稀疏矩阵的建立，稀疏矩阵的输出，两个稀疏矩阵的相加，以及如何求出相应矩阵的转置矩阵。由于在我们课本中除了学习了稀疏矩阵的建立，相加，转置外，我们还接触了稀疏矩阵的销毁，稀疏矩阵的复制，稀疏矩阵的相减，稀疏矩阵的相乘，为了将有关稀疏矩阵的几个基本操作全部实现一遍，我们在完成原有题目的要求下，拓展了下题目内容，将稀疏矩阵的销毁，稀疏矩阵的复制，稀疏矩阵的相减，稀疏矩阵的相乘补充进去，这样我们更觉得此次课程设计的完整性。而且，为了使读者更容易理解代码含义，程序的源代码基本与书本同步，思想方法也基本与书本介绍的吻合！2课程设计任务书姓名学号-

7、陈东 -蔡丹班 级09信计课程名称数据结构程序设计课程性质专业必修设计时间 2012年 5月17日 2012 年 5 月 24日设计名称稀疏矩阵的操作设计要求稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加, 销毁，复制，相减，相乘，以及矩阵的一般转置和快速转置功能。设计思路与设计过程首先将课本上的所有关于稀疏矩阵方面的概念看一遍，知道一些关于稀疏矩阵的具体操作的C语言代码。由于书上部分代码已给出，只需理解个代码所执行的各自功能，然后将

8、所有代码组合起来，便可以达到题目所需的要求。具体可分为一下几个步骤：1.创建稀疏矩阵：int CreateSMatrix(TSMatrix *M)2.输出稀疏矩阵：void PrintSMatrix(TSMatrix M)3.两个矩阵相加：int AddSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q)4.矩阵一般转置：int TransposeSMatrix(TSMatrix M,TSMatrix *T)5.矩阵快速转置：int FastTransposeSMatrix(TSMatrix M,TSMatrix *T)6.稀疏矩阵的销毁：void Destro

9、ySMatrix(TSMatrix *M)7.稀疏矩阵的复制：int CopySMatrix(TSMatrix M,TSMatrix *T)8.两个稀疏矩阵的相减：int SubtSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q)9.两个稀疏矩阵的相乘：int MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q计划与进度打算三天把课本的关于稀疏矩阵的知识点搞清楚，明白各代码所执行的具体功能，按照题目要求，整合出相应的C代码，剩余三天整理并写好相应的文档。时间很充分，总体进度还好。任课教师意 见3需求分析3.1题目名称：稀

10、疏矩阵的操作3.2题目内容：1.稀疏矩阵采用三元组表示；2.求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C；3.求出A的转置矩阵D，输出D；题目拓展：4.稀疏矩阵的销毁5.稀疏矩阵的快速转置6.求两个具有相同行列数的稀疏矩阵A和B的相减矩阵C，并输出C；7.求两个具有相同行列数的稀疏矩阵A和B的相乘矩阵C，并输出C；3.3题目分析： 通常，用高级语言编制程序时，都是用二维数组来存储矩阵元。有的程序设计语言中还提供了各种矩阵运算，用户使用时都很方便。然而，在数值分析中经常出现一些阶数很高的矩阵，同时在矩阵中有许多值相同的元素或者零元素。有的为了节省存储空间，可以对这类矩阵进行压缩存储

11、。所谓压缩存储是指：为多个值相同的元只分配一个存储空间；对零元不分配空间。我们可以运用压缩存储的方式来实现稀疏矩阵的几个基本操作。4.概要设计4.1稀疏矩阵存储结构 #define MAXSIZE 12500 /假设非零元个数的最大值为12500 typedef struct int i ，j； /该非零元的行下标和列下标 ElemeType e； Triple;Typedef struct Triple dataMAXSIZE+1；/非零元三元组表，data0未用 int mu ，nu，tu；/矩阵的行数，列数和非零元个数TSMatrix；4.2.稀疏矩阵的基本操作CreateSMatrix

12、(&M);操作结果：创建稀疏矩阵M。DestroySMatrix(&M)；初始条件：稀疏矩阵M存在；操作结果：销毁稀疏矩阵M。PrintSMatrix( M)初始条件：稀疏矩阵M存在。操作结果：输出稀疏矩阵M。CopySMatrix(TSMatrix M,TSMatrix *T)初始条件：稀疏矩阵M存在操作结果：由稀疏矩阵M复制得到T。AddSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q)初始条件：稀疏矩阵M与N的行数和列数对应相等。操作结果：求稀疏矩阵的和Q=M+N.SubtSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q

13、)初始条件：稀疏矩阵M与N的行数和列数对应相等。操作结果：求稀疏矩阵的和Q=M-N.MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q)初始条件：稀疏矩阵M与N的行数和列数对应相等。操作结果：求稀疏矩阵的和Q=M*N.TransposeSMatrix(TSMatrix M,TSMatrix *T)初始条件：稀疏矩阵M存在操作结果：由稀疏矩阵M的转置矩阵T4.3.各模块设计要求1.初始函数建立稀疏矩阵及初始化稀疏矩阵 本模块要求设计函数在三元组顺序表中建立稀疏矩阵并初始化。首先要定义三元组表结构体类型，在输入出现错误时，能够对错误进行判别处理，初始化稀疏矩

14、阵都为空值，特别需要注意在三元组表存储稀疏矩阵的时候，要对变量进行动态的地址分配2.转置函数进行稀疏矩阵的转置 本模块要求设计函数进行稀疏矩阵的转置并输出转置后的结果，由于对稀疏矩阵的转置只对一个矩阵进行操作，所以实现起来难度并不是很大，函数也比较容易编写。在编写函数时，首先定义一个相应的结构体变量用于存放转置后的矩阵，最后把此矩阵输出。3.和运算函数进行两个稀疏矩阵相加运算 本模块要求设计加法对两个矩阵进行运算，并输出最终运算后的稀疏矩阵，在进行运算前，要对两个矩阵进行检查，看是不是相同类型的矩阵，因为两个矩阵相加要求两个矩阵一定是同一类型的矩阵，定义相应的矩阵类型用于存放两个矩阵相加的结果

15、矩阵，这个结果矩阵的行数列数要综合多方面来确定。4.积运算函数进行两个稀疏矩阵的乘法运算 本模块要求设计乘法对两个矩阵进行运算，并输出最终运算后的稀疏矩阵，在进行运算前，要对两个矩阵进行检查，如果A矩阵的行（列）和B矩阵列（行）数值相等，则能完成相应的乘法运算，定义相应的矩阵类型用于存放两个稀疏矩阵相乘之后的结果矩阵，并且调用输出函数完成乘积的输出5输出函数完成矩阵的输出 本模块要求完成对稀疏矩阵的输出功能，实现起来比较简单，完成矩阵的转置输出，矩阵的加法，减法，乘法运算输出相应的和，差，积，都要调用输出函数。4.4总体功能流程图4.4.1存储结构流程图：矩阵a非零数值data1非零数值dat

16、a2行数m列数n头h行列值行列值mnDatamaxrowcolvrowcolv4.4.2稀疏矩阵基本操作流程图： 开始构造一个稀疏矩阵A由矩阵A复制矩阵得到B求矩阵A的转置销毁矩阵B矩阵A+B=C矩阵A-B=C矩阵A*B=C结束5详细设计5.1设计原理1.三元组顺序表：假设以顺序存储结构来表示三元组表，则可得稀疏矩阵的一种压缩存储方式我们称之为三元组顺序表。因此，data域中表示非零的三元组是以行序为主序顺序排列的。按照压缩存储的概念，只存储稀疏矩阵的非零元。因此，除了存储非零元的值外，还必须同时记下它所在行和列的位置（i，j）。反之，一个三元组（i，j，aij）唯一确定了矩阵A的一个非零元。

17、由此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。例如，下列三元组表：（1,2,1），（1,3,9），（3,1,3），（3,6,14），（4,3,4），（5,2,8），（6,1,5），（6,4,7），于是稀疏矩阵A可以描述为： 0 1 9 0 0 0 0 0 0 0 0 0 0 0A= 3 0 0 0 0 4 0 0 0 4 0 0 0 0 0 8 0 0 0 0 0 5 0 0 7 0 0 02.矩阵转置：转置运算是一种简单的矩阵运算。对于一个m*n的矩阵M，它的转置矩阵T是一个n*m的矩阵，且T(i,j)=M(j,i)。显然，一个稀疏矩阵的转置仍为稀疏矩阵：要想实现矩阵之间的转置，只

18、要做到：(1)将矩阵的行列值相互交换；(2)将每个三元组中的i和j相互调换；(3)重排三元组之间的次序便可实现矩阵的转置。前二条内容是容易做到的，关键是如何实现第三条，我们有2种方法，在这我们使用以下方法实现：我们按照矩阵M的列序来进行转置，为了找到M的每一列中所有的非零元素，需要对其三元组表a.data从第一行起整个扫描一遍，由于a.data是以M的行序为主序来存放每个非零元的，由此得到的恰是b.data应用的顺序。ijvijv 1 2 1 1 3 31 3 9 1 6 5 3 1 3 2 1 2 3 6 4 2 5 8 4 3 4 3 1 9 5 2 8 3 4 24 6 1 5 4 6

19、7 6 4 7 6 3 4a.data b.data3 .两个稀疏矩阵相加：比较满足条件（行数及列数都相同的2个矩阵）的两个稀疏矩阵中不为0的元素的行数及列数（即i与j），将i与j都相等的前后两个元素e相加，保持i，j不变存储在新的三元组中，不等的则分别储存在此新三元组中。最后得到的这个新三元组表就是两个矩阵的和矩阵的三元组表。例如： 3 0 0 5 0 2 1 0 M= 0 1 0 0 ， N= 0 0 2 0 2 0 0 0 -2 0 0 1 那么 则Q=M+N为3 2 1 5 Q= 0 -1 2 0 0 0 0 1 则它们三元组M.data，N.data，Q.data分别为i j ei

20、j ei j e 1 1 3 1 2 2 1 1 3 1 4 5 1 2 1 1 2 2 2 2 -1 2 3 2 1 3 1 3 1 2 3 1 -2 1 4 5 3 4 1 2 2 -1 2 3 2 4 4 1 M.data N.data Q.data4.两个稀疏矩阵相减：知道两个稀疏矩阵相加原理后，要想实现两个稀疏矩阵相减就很容易了，只需将要减的那个稀疏矩阵所有元素乘以-1后，看成两个稀疏矩阵的相加，然后再利用两个稀疏矩阵相加的方法，就能实现两个稀疏矩阵的相减了。5.快速转置：矩阵A中三元组的存放顺序是先行后列，对同一行来说，必定先遇到列号小的元素，这样只需扫描一遍A.data 。所以需

21、引入两个向量来实现 ：numn+1和position n+1，numcol表示矩阵A中第col列的非零元素的个数(为了方便均从1单元用起)，position col初始值表示矩阵A中的第col列的第一个非零元素在B.data中的位置。于是position的初始值为：position 1=1;position col= position col-1+numcol-1; 2coln 依次扫描A.data，当扫描到一个col列元素时，直接将其存放在B.data的position col位置上，position col加1，position col中始终是下一个col列元素在B.data中的位置。6两

22、个稀疏矩阵的相乘：两个矩阵相乘的金典算法也是大家所熟悉的。若设Q=M*N其中，M是m1*n1矩阵，N是m2*n2矩阵。当n1=m2时有：for(i=1,i=m1;+i)for(j=1;j=n2;+j)Qij=0;for(k=1;k=n1;+k)Qij+=Mik*Nkj;此算法的时间复杂度是O(m1*n1*n2)。当M和N是稀疏矩阵并用三元组表示存储结构时，就不能套用上述算法。假设M和N分别为 3 0 0 5 0 2 M= 0 1 0 0 ， N= 1 0 2 0 0 0 -2 4 0 0则Q=M*N为0 6Q= -1 0 0 4它们的三元组M.data,N.data分别为：i j ei j e

23、i j e1 1 31 2 21 2 6 1 4 52 1 12 1 -12 2 -13 1 -23 2 43 1 23 2 4 M.data N.data Q.data那么如何从M和N求得Q呢？（1） 乘积矩阵Q中元素 1=i=m1,1=j=n2; (5-6)在经典算法中，不论M（i，k）和N（k，j）的值是否为零，都要进行一次乘法运算，而实际上，这两者有一个值为零时，其乘积也为零。因此，在对稀疏矩阵进行运算时，应免去这种无效操作，换句话说，为求Q的值，只需在M.dtat和N.data中找到相应的各对元素（即M.data中的j值和N.data中的i值相等的各对元素）相乘即可。例如，M.dat

24、a11表示的矩阵元（1,1,3）只要和N.data1表示的矩阵元（1,2,2）相乘；而M.data2表示的矩阵元（1,4,5）则不需要和N中任何元素相乘，因为N.data中没有i为4的元素。由此可见，为了得到非零的乘积，只要对M.data1. .M.tu中的每个元素（i，k，M（i，k）（1=i=m1,1=k=n1）,找到N.data中所有相应的元素（k，j，N（k，j）(1=k=m2,1=jdata00481101212332124306.Max-12.稀疏矩阵输入基本流程图 运行程序输入稀疏矩阵行数m，列数n，非零元数个数v分别输入非零元数e所在的行i列j的位置1=i=m&1=j=n返回重

25、新输入YesNo在第i行,j列生成元素e输入非零元数个数是否等于vNoYes继续输入输出所构造的稀疏矩阵结束3.稀疏矩阵相加，相减基本流程图开始输入一个i行，j列的稀疏矩阵A调用稀疏矩阵输出函数输出稀疏矩阵A输入一个m行，n列的稀疏矩阵Bi=m&=nYesNo调用稀疏矩阵相加函 数调用稀疏矩阵想减函 数得到矩阵C1=A+B得到矩阵C2=A-B输出矩阵C1和C2结束4.稀疏矩阵乘基本流程图开始输入一个i行，j列的稀疏矩阵A调用稀疏矩阵输出函数输出稀疏矩阵A输入一个m行，n列的稀疏矩阵Bj=mYesNo调用稀疏矩阵相乘函 数得到稀疏矩阵C=A*B结束输出稀疏矩阵C5.各函数之间的实现流程图开始调用

26、稀疏矩阵转置函数调用稀疏矩阵复制函数得到矩阵B正确的构造出一个稀疏矩阵A调用稀疏矩阵的销毁函数销毁矩阵B得到0行0列0个元素稀疏矩阵得到由A复制得到的矩阵B调用稀疏矩阵创建函 数正确构造出一个稀疏矩阵B调用稀疏矩阵相乘函 数调用稀疏矩阵相减函 数调用稀疏矩阵相加函 数得到A的转置矩阵A得到稀疏矩阵C3=A*B得到稀疏矩阵C2=A-B得到稀疏矩阵C1=A+B函数调用完毕结束6.主要函数代码根据5.1的设计原理，我们可以得到以下主要函数的基本代码：1.稀疏矩阵的创建int CreateSMatrix(TSMatrix *M)int i,m,n;ElemType e;int k;printf(请输入

27、矩阵的行数,列数,非零元素个数：（逗号）n);scanf(%d,%d,%d,&(*M).mu,&(*M).nu,&(*M).tu);(*M).data0.i=0;/ 为以下比较顺序做准备 for(i = 1; i = (*M).tu; i+)doprintf(请按行序顺序输入第%d个非零元素所在的行(1%d),列(1%d),元素值：(逗号)n, i,(*M).mu,(*M).nu);scanf(%d,%d,%d,&m,&n,&e);k=0;/ 行或列超出范围 if(m (*M).mu | n (*M).nu) k=1;if(m (*M).datai-1.i | m = (*M).datai-1

28、.i& n = (*M).datai-1.j) / 行或列的顺序有错 k=1;while(k);(*M).datai.i = m;/行下标(*M).datai.j = n;/列下标(*M).datai.e = e;/该下标所对应的值return 1;2稀疏矩阵的销毁void DestroySMatrix(TSMatrix *M) (*M).mu=0;(*M).nu=0;(*M).tu=0;3稀疏矩阵的输出void PrintSMatrix(TSMatrix M)int i;printf(n所得A矩阵为:%d行%d列%d个非零元素。n,M.mu,M.nu,M.tu);printf(%4s%4s%

29、8sn, 行, 列, 元素值);for(i=1;i=M.tu;i+)printf(%4d%4d%8dn,M.datai.i,M.datai.j,M.datai.e);4稀疏矩阵的相加int AddSMatrix(TSMatrix M,TSMatrix N,TSMatrix *Q) Triple *Mp,*Me,*Np,*Ne,*Qh,*Qe;if(M.mu!=N.mu)return 0;if(M.nu!=N.nu)return 0;(*Q).mu=M.mu;(*Q).nu=M.nu;Mp=&M.data1;/ Mp的初值指向矩阵M的非零元素首地址 Np=&N.data1;/ Np的初值指向矩阵

30、N的非零元素首地址 Me=&M.dataM.tu;/ Me指向矩阵M的非零元素尾地址 Ne=&N.dataN.tu;/ Ne指向矩阵N的非零元素尾地址 Qh=Qe=(*Q).data;/ Qh、Qe的初值指向矩阵Q的非零元素首地址的前一地址 while(Mp = Me & Np i,Np-i)case 1: *Qe=*Mp;Mp+;break;case 0: / M、N矩阵当前非零元素的行相等,继续比较列switch(comp(Mp-j,Np-j) case 1: *Qe=*Mp;Mp+;break;case 0: *Qe=*Mp;Qe-e+=Np-e;if(!Qe-e) / 元素值为0，不存

31、入压缩矩阵 Qe-;Mp+;Np+;break;case -1: *Qe=*Np;Np+;break;case -1: *Qe=*Np;Np+;if(MpMe) / 矩阵M的元素全部处理完毕 while(NpNe) / 矩阵N的元素全部处理完毕 while(Mp=Me)Qe+;*Qe=*Mp;Mp+;(*Q).tu=Qe-Qh; / 矩阵Q的非零元素个数 return 1;5稀疏矩阵的一般转置int TransposeSMatrix(TSMatrix M,TSMatrix *T)int p,q,col;(*T).mu=M.nu;(*T).nu=M.mu;(*T).tu=M.tu;if(*T).

32、tu)q=1;for(col=1;col=M.nu;+col)/先将列转换成行for(p=1;p=M.tu;+p)/再将行转换成列if(M.datap.j=col)(*T).dataq.i=M.datap.j;(*T).dataq.j=M.datap.i;(*T).dataq.e=M.datap.e;+q;return 1;6.稀疏矩阵的快速转置int FastTransposeSMatrix(TSMatrix M,TSMatrix *T) int p,q,t,col,*num,*cpot;num=(int *)malloc(M.nu+1)*sizeof(int);/ 生成数组（0不用） cp

33、ot=(int *)malloc(M.nu+1)*sizeof(int);/ 生成数组（0不用） (*T).mu=M.nu;(*T).nu=M.mu;(*T).tu=M.tu;if(*T).tu)for(col=1;col=M.nu;+col)numcol=0; / 设初值 for(t=1;t=M.tu;+t) / 求M中每一列含非零元素个数 +numM.datat.j;cpot1=1;/ 求第col列中第一个非零元在(*T).data中的序号for(col=2;col=M.nu;+col) cpotcol=cpotcol-1+numcol-1;for(p=1;p=M.tu;+p)col=M.datap.j;q=cpotcol;(*T).dataq.i=M.datap.j;