稀疏矩阵基本操作和转置.doc

北京理工大学珠海学院数据结构实验报告题目：稀疏矩阵基本操作的实现和快速转置所在学院： 计算机科学与技术学院 专业班级： 学 号： 学生姓名： _ 目录1前 言12概要设计22.1 数据结构设计22.2 算法设计22.2.1 创建稀疏矩阵的算法22.2.2 求稀疏矩阵的和的算法32.2.3 销毁稀疏矩阵的算法32.2.4 快速求稀疏矩阵的转置矩阵的算法32.3 ADT描述42.4 功能模块分析53详细设计53.1 数据存储结构设计53.2主要算法流程图（或算法伪代码）64软件测试85心得体会9参考文献9附 录91前 言“数据结构”是计算机专业一门重要的专业技术基础课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法；介绍了常用的多种查找和排序技术，并进行性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础，数据结构课程是计算机专业的一门核心的关键性课程。数据结构课程是计算机科学与技术专业、软件工程专业等相关专业的一门专业基础课，学好数据结构课程，将为后续的专业课程，如数据库系统、操作系统、编译原理等，打下良好的知识基础，而且还为软件开发和程序设计提供了必要的技能训练。是一门理论性和实践性都很强的一门课程。它涉及在计算机中如何有效地表示数据，如何合理地组织数据和处理数据，还涉及初步的算法设计和算法性能分析。C与C+语言程序设计和离散数学的基础都将影响到本课程的学习效果，同时数据结构也是一门自学起来比较困难的一门课程。所以学生在以学习过程中，应当在认真听取老师课堂讲解的基础上，充分运用辅导资料、网络教学资源、多媒体课件等进行深入学习理解和掌握，并利用实习机会进行上机操作，理解和巩固算法2概要设计2.1 数据结构设计 本程序对三元组的实现采用的是通过建立一个存放数据元素及下标的数组来存放对应的元素，再定义矩阵的行数，列数，非零元数来实现数组的压缩存储。struct Triple int i,j; ElemType e; ; typedef struct Triple dataMAX_SIZE+1; int mu,nu,tu; TSMatrix;2.2 算法设计2.2.1 创建稀疏矩阵的算法（1）算法思想分析 输入矩阵的M.mu行数，M.nu列数，M.tu非零元个数。然后保存非零元对应的下标i,j，和数据元素，创建3元表。（2）要点描述 if(T.iM.mu|T.jM.nu)，要判断所输入元素是否越界，若越界while循环返回重新输入。（3）时间和空间复杂度分析 时间复杂度O（tu*k）2.2.2 求稀疏矩阵的和的算法（1）算法思想分析 判断栈顶是否为空，若为空，用realloc重新分配内存空间，若不为空增加栈顶元素。（2）要点描述 每增加一个元素之后，栈顶要top+而不是top+1，因为栈顶是指的是即将存放元素的位置，所以加完元素后，栈顶也要加1。（3）时间和空间复杂度分析 时间复杂度O（n）2.2.3 销毁稀疏矩阵的算法（1）算法思想分析 M.mu=M.nu=M.tu=0; 把行数，列数，非零元设为零即可。（2）要点描述（3）时间和空间复杂度分析 时间复杂度o(1)2.2.4 快速求稀疏矩阵的转置矩阵的算法（1）算法思想分析 通过numcol表示矩阵M中第col列中非零元的个数，和cpotcol表示首非零元的位置，通过for循环进行控制数组的行列互换，来进行转置。（2）要点描述 在求numcol和cpotcol，numcol实际是一个记数的，每次遇到一个该列的非零元则对应+ numcol，来记住每列的非零元的个数。而cpotcol则通过cpotcol-1也就是前一行的非零元位置加numcol对应的非零元个数而求得。（3）时间和空间复杂度分析 时间复杂度O（n）2.3 ADT描述ADT List数据对象：D=ai|i=1,2m;j=1,2,n数据关系：R=Row,Col Row=| 1=i=m,1=j=n-1Col=| 1=i=m-1,1=j=n基本操作：CreateSMatrix(&M);操作结果：创建稀疏矩阵M。DestroyMatrix(&M); 初始条件：稀疏矩阵M已存在。操作结果：销毁稀疏矩阵M。CopySMatrix(TSMatrix M,TSMatrix &T)初始条件：稀疏矩阵M已存在。操作结果：复制稀疏矩阵M复制得到TAddSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q) 初始条件：稀疏矩阵M的行数和列数对应相等。 操作结果：求稀疏矩阵的和Q=M+N。ubtSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)初始条件：稀疏矩阵M的行数和列数对应相等。操作结果：求稀疏矩阵的差Q=M-N。MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)初始条件：稀疏矩阵M的行数和N列数相等。操作结果：求稀疏矩阵的乘积Q=M*N。TransposeSMatrix(TSMatrix M,TSMatrix &T)初始条件：稀疏矩阵M已存在操作结果：求稀疏矩阵M的转置矩阵T2.4 功能模块分析CreateSMatrix (&M)创建稀疏矩阵M。DestroyMatrix(&M);销毁稀疏矩阵M。CopySMatrix(TSMatrix M,TSMatrix &T)复制稀疏矩阵M复制得到TAddSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q) 求稀疏矩阵的和Q=M+N。ubtSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)求稀疏矩阵的差Q=M-N。MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q)：求稀疏矩阵的乘积Q=M*N。TransposeSMatrix(TSMatrix M,TSMatrix &T)快速求稀疏矩阵M的转置矩阵T3详细设计3.1 数据存储结构设计 在数值分析中经常出现一些阶数很高的矩阵，同时在矩阵中有许多值相同的元素或者是零元素。有时为了节省存储空间，可以对这类矩阵进行压缩存储。按照压缩矩阵的存储概念，只存储稀疏矩阵的非零元。因此，除了存储非零元的值之外，还必须同时记下他所在行和列的位置(i,j)。反之，一个三元组(i,j,aij)唯一确定了矩阵A的一个非零元。由此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。3.2主要算法流程图（或算法伪代码）4软件测试5心得体会通过这次数据结构课程设计课，让我更进一步的对矩阵压缩存储的理解。为多个值相同的元只分配一个存储空间；对零元不分配空间。而对于更毫无规律可循的稀疏矩阵，我们不可能把他所有的元素都存起来，这样会造成极大的资源浪费。所以我们就通过定义三元组来保存，然后对稀疏矩阵进行一系列的，如矩阵相加相减等操作。首先然我深受体会的是，你必须对矩阵的相加相乘等矩阵的性质要清楚，然后才能设计相应的算法。连矩阵是怎样运算的都不知道，就根本不用完成压缩存储等相应操作了。而这次设计课中，比如矩阵的相加，转置，相乘是比较难的，相减则是通过相加来完成的。如Q=M-N，则是Q=M+(-N)。而相乘，转置则是通过对行序的逐个判断，来进行相关的操作的。其中一些思想对于我来说都是比较难理解的。而且本程序是采用C+写的，虽然仿照源代码，但是还是遇到 了小小问题的。除了完成矩阵相应功能有一定的难度外，在写测试函数时，也想到万一2矩阵不能相加或相乘的情况，虽然比较简单，但对于程序员来说，这是严谨性的必须。但本函数都是些在一个.CPP中的，可读性也比较低，还需要改进。反正在这次课程设计中，我发现看懂程序其实还是远远不够的，要想得出才是重要的。参考文献 清华大学出版社 严蔚敏 吴伟民数据结构 (c语言版本)附 录#include #include #include #include typedef int Status;typedef int ElemType;#define DIMMAX 5#define ERROR 0#define OK 1#define MAX_SIZE 1000 struct Triple /三元组 int i,j; ElemType e; ; typedef struct Triple dataMAX_SIZE+1; int mu,nu,tu; TSMatrix; int comp(int c1,int c2); Status CreateSMatrix(TSMatrix &M) /创建稀疏矩阵 int i; Triple T; Status k; cout请输入矩阵的行数,列数,非零元素个数：M.muM.nuM.tu; if(M.tuMAX_SIZE) return ERROR; M.data0.i=0; for(i=1;i=M.tu;i+) do cout请按行序顺序输入第i个非零元素所在的行(1M.mu),列(1M.nu),元素值：T.iT.jT.e; k=0; if(T.iM.mu|T.jM.nu) k=1; cout输入错误，请重新输入endl; if(T.iM.datai-1.i|T.i=M.datai-1.i&T.j=M.datai-1.j) k=1; cout输入错误，请重新输入endl; while(k); M.datai=T; return OK; void PrintSMatrix(TSMatrix M) /打印矩阵M int i,j,k=1; Triple *p=M.data+1; for(i=1;i=M.mu;i+) for(j=1;j=M.nu;j+) if(ki=i&p-j=j) coute ; k+; else cout0 ; coutendl; void DestroySMatrix(TSMatrix &M) / 销毁稀疏矩阵M M.mu=M.nu=M.tu=0; void CopySMatrix(TSMatrix M,TSMatrix &T) / 复制稀疏矩阵M复制得到T T=M; Status AddSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q) / 求2个稀疏矩阵的和Q=M+N int m=1,n=1,q=0; if(M.mu!=N.mu|M.nu!=N.nu) return ERROR; Q.mu=M.mu; Q.nu=M.nu; while(m=M.tu&n=N.tu) switch(comp(M.datam.i,N.datan.i) case -1:Q.data+q=M.datam+; /M的行小 break; case 0:switch(comp(M.datam.j,N.datan.j) /M的列小 case -1:Q.data+q=M.datam+; break; case 0: /相加 Q.data+q=M.datam+; Q.dataq.e+=N.datan+.e; if(Q.dataq.e=0) q-; break; case 1:Q.data+q=N.datan+; /N的列小 break; case 1:Q.data+q=N.datan+; /N的行小 while(m=M.tu) Q.data+q=M.datam+; while(nMAX_SIZE) return ERROR; Q.tu=q; return OK; Status SubtSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q) / 求稀疏矩阵的差Q=M-N int i; if(M.mu!=N.mu|M.nu!=N.nu) return ERROR; for(i=1;i=N.tu;+i) / 矩阵 M-N =M+(-N) 所以把矩阵N所有元素乘于-1，然后在AddSMatrix。 N.datai.e*=-1; AddSMatrix(M,N,Q); return OK; void TransposeSMatrix(TSMatrix M,TSMatrix &T) / 求稀疏矩阵M的转置矩阵T。 int p,col,q=1; T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if(T.tu) 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; Status MultSMatrix(TSMatrix M,TSMatrix N,TSMatrix &Q) / 求稀疏矩阵的乘积Q=MN int i,j,q,p; ElemType Qs; TSMatrix T; if(M.nu!=N.mu) return ERROR; Q.mu=M.mu; Q.nu=N.nu; Q.tu=0; TransposeSMatrix(N,T); for(i=1;i=Q.mu;i+) q=1; for(j=1;j=T.mu;j+) Qs=0; p=1; while(M.datap.ii) p+; while(T.dataq.ij) q+; while(p=M.tu&qMAX_SIZE) return ERROR; Q.dataQ.tu.i=i; Q.dataQ.tu.j=j; Q.dataQ.tu.e=Qs; return OK; void FastTransposeSMatrix(TSMatrix M,TSMatrix &T) / 快速求稀疏矩阵M的转置矩阵T int p,q,col,*num,*cpot; num=(int*)malloc(M.nu+1)*sizeof(int); cpot=(int*)malloc(M.nu+1)*sizeof(int); 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(p=1;p=M.tu;+p) +numM.datap.j; cpot1=1; 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; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +cpotcol; free(num); free(cpot); int comp(int c1,int c2) /判断2数大小 if(c1c2) ret