稀疏矩阵的操作.doc

(完整word)稀疏矩阵的操作稀疏矩阵的操作数据结构课程设计报告专 业： 计算机科学与技术 班 级： 姓 名： 学 号： 指导教师: 完成日期：2013-1-9目录1课程设计题目与要求31。1课程设计的目的:31.2课程设计的题目：31.3题目要求:32 总体设计42。1程序结构与整体示意图42.2各子模块功能介绍43详细设计53.1引入常量53。2存储结构53。3程序流程图64运行结果：95课程设计总结126参考书目121课程设计题目与要求1。1课程设计的目的:1掌握多维数组的逻辑结构和存储结构。2掌握稀疏矩阵的压缩存储及基本操作。1。2课程设计的题目: 稀疏矩阵的操作1。3题目要求：（1） 稀疏矩阵采用三元组表示，求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C。（2） 求出A的转置矩阵D，输出D（用两种方法实现，原始算法和改进的算法）.（3） 求两个稀疏矩阵A和B的相乘矩阵E，并输出E.2 总体设计2.1程序结构与整体示意图函数的声明void InitMatrix1(SMatrix M)；/顺序存储结构 对稀疏矩阵的初始化void InitMatrix2（LMatrix& M）；/链式存储结构 对稀疏矩阵的初始化void InputMatrix1(SMatrix M，int m,int n)；/顺序存储结构 输入函数void InputMatrix2（LMatrix M,int m,int n）;/链式存储结构 输入函数void OutputMatrix1(SMatrix& M);/顺序存储结构 输出函数void OutputMatrix2(LMatrix& M);/链式存储结构 输出函数SMatrix Transpose（SMatrix& M)；/顺序存储结构 普通转置SMatrix FastTranspose(SMatrix M);/顺序存储结构 快速转置LMatrix Add（LMatrix M1,LMatrix& M2）;/链式存储结构 加法void menu()；/ 菜单函数2。2各子模块功能介绍1. 稀疏矩阵的存储结构的建立以结构体为基础建立存储结构，分为顺序存储和链式存储的方式.采用三元组法，对系数矩阵中非零的元素进行存储，存储行号、列号以及元素的值（value)并记录下行，列及非零元素个数.2. 稀疏矩阵的初始化函数将矩阵的行、列以及非零元素的个数初始化零，保持程序的稳定性。3. 稀疏矩阵的录入函数将非零的元素值的行、列以及值录入创建的矩阵中。4. 稀疏矩阵的输出函数将进行操作后的稀疏矩阵输出。5. 稀疏矩阵的转置、快速转置以及加法函数函数对稀疏矩阵进行一系列的操作。6. 菜单函数对操作进行说明。3详细设计3.1引入常量define MaxTerms 10#define MaxRows 10定义矩阵最大为10行10列3.2存储结构通过使用结构体来存储相关信息:struct Triple/定义三元组 顺序存储int row,col;/行号和列号ElemType val;/元素值;struct SMatrix /定义稀疏矩阵的结构 顺序存储int m，n,t；/行,列及非零元素个数Triple smMaxTerms+1;；struct TripleNode/三元组结点 链式存储结构int row，col；ElemType val；TripleNode next;struct LMatrix/定义稀疏矩阵的结构 链式存储结构int m，n,t；TripleNode* vectorMaxRows+1；3.3程序流程图输入函数 NY普通转置NNYY稀疏矩阵的加法4运行结果:主界面顺序存储建立稀疏矩阵稀疏矩阵的普通转置稀疏矩阵的快速转置三元组建立稀疏矩阵链式存储稀疏矩阵的加法5课程设计总结在此课程设计中，实际对稀疏矩阵的操作。由于稀疏矩阵中存在大量的0值，对于程序来说，要把大量的0值存储起来再一个个的进行运算是非常浪费空间和时间的，为此,我们优化存储方式,通过三元组定义元素的行、列以及元素值来确定元素的基本属性。为0的则不进行定义。根据系数矩阵的定义,矩阵中有至少十分之九的元素值为0,通过三元组的存储， 我们至少节约了十分之九的存储的存储,在进行转置操作的操作中，可以近似的认为以直接访问的方式来访问元素的各个属性，即行、列以及元素的值.这样有大大减少了程序的运行时间.在传统的普通二维矩阵中操作，必须通过双重甚至三重的for循环进行复制和操作，例如再赋值过程中，要通过双重的for进行赋值，时间复杂度为o（n2），而在进行转置是，时间复杂度为 o（n3），这种时间花费太大，而通过三元组，则大大减少时间。 数据结构是计算机专业必学的学习的课程，通过对数据结构的学习,我学到了对数据进行组织好操作的基本方法。一个好的程序员不仅仅熟悉各种语言,更重要的是学会各种算法并在存储的层次中对数据进行操作，通过好的结构,来缩短程序运行的时间复杂度，提高程序的运行效率。数据结构这门课程我感觉只是学了一点点而已,以后一定要加强对这门课程的深入学习，设计好的算法。6参考书目1. 谭浩强. C+程序设计。北京：清华大学出版社，2008.2. 数据结构(C语言版) 人民邮电出版社，2011源代码include iostream#define MaxTerms 10define MaxRows 10using namespace std；typedef int ElemType;struct Triple/定义三元组 顺序存储int row,col；/行号和列号ElemType val；/元素值；struct SMatrix /定义稀疏矩阵的结构 顺序存储int m,n，t;/行，列及非零元素个数Triple smMaxTerms+1;；struct TripleNode/三元组结点 链式存储结构int row,col；ElemType val;TripleNode* next；;struct LMatrix/定义稀疏矩阵的结构 链式存储结构int m，n，t；TripleNode* vectorMaxRows+1；/以上是对顺序和链式存储结构定义/函数的声明void InitMatrix1（SMatrix& M);/顺序存储结构 对稀疏矩阵的初始化void InitMatrix2（LMatrix M）;/链式存储结构 对稀疏矩阵的初始化void InputMatrix1（SMatrix M,int m，int n)；/顺序存储结构 输入函数void InputMatrix2(LMatrix M，int m,int n);/链式存储结构 输入函数void OutputMatrix1（SMatrix& M）；/顺序存储结构 输出函数void OutputMatrix2(LMatrix M）;/链式存储结构 输出函数SMatrix Transpose(SMatrix& M）;/顺序存储结构 普通转置SMatrix FastTranspose(SMatrix& M）；/顺序存储结构 快速转置LMatrix Add（LMatrix& M1,LMatrix& M2）；/链式存储结构 加法void menu（);/ 菜单函数int main（)SMatrix S1; /顺序结构声明S1LMatrix L1，L2；/链式存储结构声明L1L2LMatrix L;/用来存储L1 L2的和int c,m=1;while（m=1)menu(）;cout请输入你需要的操作endl;cinc；switch（c)case 1：InitMatrix1(S1）;InputMatrix1(S1,10，10）；OutputMatrix1（S1);break;case 2：OutputMatrix1（Transpose(S1）；break；case 3: OutputMatrix1(FastTranspose(S1)）；break;case 4:InitMatrix2(L1);InputMatrix2(L1,10，10）;OutputMatrix2（L1);break;case 5：InitMatrix2(L2)；cout”输入要相加的矩阵”endl；InputMatrix2(L2,10，10)；OutputMatrix2(L2);L=Add(L1,L2)；OutputMatrix2（L）;break;case 6：cout”再见endl；exit（1);return 0;void InitMatrix1（SMatrix M)/顺序存储结构 对稀疏矩阵的初始化为0M.m=0; M.n=0； M。t=0；void InitMatrix2(LMatrix M)/链式存储结构 对稀疏矩阵的初始化为0int i;M。m=0；M。n=0；M。t=0；for（i=1;i=MaxRows;i+)M。vectori=NULL;void InputMatrix1(SMatrix M，int m,int n)/顺序存储结构 输入函数M.m=m;M。n=n;int row，col,val；/row和col用来分别存储元素的行号和列号，val用来存储元素值，t为非零元素个数int k=0;coutrowcolval;while(row！=0col!=0&val！=0)k+；M.smk.row=row;M。smk。col=col;M.smk.val=val；cinrowcolval;M。t=k;void InputMatrix2（LMatrix M,int m，int n）/链式存储结构 输入函数M。m=m;M。n=n;int row，col，val;int k=0;cout”输入链式三元组中的行、列和对应值，以0 0 0为结束标志”colval;while（row!=0&col！=0&val!=0）k+;TripleNode *p;TripleNode *newptr;newptr=new TripleNode；/建立新结点newptr-row=row；newptrcol=col；newptr-val=val;newptrnext=NULL;p=M.vectorrow；if（p=NULL)M.vectorrow=newptr； elsewhile(pnext!=NULL）p=pnext；p-next=newptr；cinrowcolval;M。t=k；void OutputMatrix1（SMatrix M)/顺序存储结构 输出函数int i=1；cout”矩阵为”endl；for(i=1；i=M.t;i+）coutM。smi。row ”;coutM。smi.col” ”;coutM。smi。val” ;coutendl;void OutputMatrix2(LMatrix& M)/链式存储结构 输出函数int i；TripleNode p;cout矩阵为rowcol ”val；coutendl；coutendl;SMatrix Transpose(SMatrix& M)/普通转置SMatrix S；InitMatrix1（S）;int m，n，t；m=M.m; n=M。n; t=M。t；/用m,n，t分别暂存M的行数、列数和非零元素的个数S。m=n; S.n=m; S.t=t;/分别置S的行数域、列数域和非零元素的个数域为n,m和tif(t=0）/若是零矩阵则转换完毕返回return S；int k=1;/用k指示S.sm数组中待存元素的下标for（int col=1;col=n； col+)for（int i=1；i=t；i+)if(M.smi。col=col）S.smk.row=col;S.smk。col=M.smi.row;S.smk.val=M。smi。val；k+;return S;/返回转置矩阵SSMatrix FastTranspose（SMatrix M）/快速转置，不必考虑大量的0元素SMatrix S；InitMatrix1(S);int m，n，t;m=M。m; n=M。n； t=M.t；/用m,n，t分别暂存M的行数、列数和非零元素的个数S.m=n； S.n=m； S。t=t；/分别置S的行数域、列数域和非零元素的个数域为n，m和tif(t=0)/若是零矩阵则转换完毕返回return S;int* num=new intn+1；/为num向量动态分配存储空间int pot=new intn+1；/为pot向量动态分配存储空间int col,i;for(col=1；col=n;col+)/对num向量进行初始化，置每个分量为0numcol=0；for（i=1;i=t;i+)/第1遍扫描数组M。sm，统计出每一列非零元素的个数int j=M。smi.col;numj+;pot1=1;for（col=2;col=n;col+)/计算每一列的第1个非零元素在S。sm中存储位置potcol=potcol1+numcol-1;for(i=1；i=t；i+)/对M.sm进行第2遍扫描，把每个元素行、列值互换写入到S.sm的确定位置int j=M.smi。col；int k=potj；S。smk。row=j；S。smk。col=M.smi。row;S.smk。val=M。smi.val；potj+；delete num;/删除动态分配的数组delete pot;return S;LMatrix Add（LMatrix M1,LMatrix M2）/矩阵加法LMatrix M;/暂存运算结果，以便返回InitMatrix2（M)；if(（M1.n!=M2。n)(M1。n!=M2.n)）cout两个矩阵规格不同”endl；exit（1);M.m=M1。m； M.n=M1.n；/把其中一个加数矩阵的尺寸赋给结果矩阵if（(M1.t=0） & (M2.t=0）return M;/进行两矩阵相加产生和矩阵int k=0；/用k统计结果矩阵中结点的个数for（int i=1；i=M.m；i+）/循环的次数相当于矩阵的行数TripleNode p1,p2，*p;p1=M1.vectori；/p1指向M1矩阵中第i行单链表的待相加的结点p2=M2.vectori;/p2指向M2矩阵中第i行单链表的待相加的结点p=M。vectori;/p指向M矩阵中第i行单链表的待相加的结点while(（p1！=NULL) & （p2！=NULL）)TripleNode newptr=new TripleNode；if(p1colcol）/赋值新结点，p1指针后移newptr=*p1;p1=p1-next;else if(p1-colp2-col）/赋值新结点,p2指针后移*newptr=p2；p2=p2next;else/对具有相同列号的结点进行处理if(p1val+p2-val=0)/不建立新结点和链接p1=p1next；p2=p2next；/p1和p2指针后移continue;else /新结点值为两结点值之和，p1和p2指针后移newptr=*p1；newptr-val+=p2val;p1=p1next;p2=p2next；newptrnext=NULL；/将新结点的指针域置空/把新结点链接到结果矩阵的第i行单链表的表尾if(p=NULL)M.vectori=newptr;elsepnext=newptr；p=newptr；k+;while（p1!=NULL）TripleNode* newptr=new TripleNode；*newptr=*p1；newptr-next=NULL;if(p=NULL）M.vectori=newptr;elsep-next=newptr；p=newptr;p1=p1-next;k+;/若p2不为空，则把剩余结点复制链接到结果矩阵中while（p2！=NULL)TripleNode newptr=new TripleNode;*newptr=*p2；newptr-next=NULL；if（p=NULL）M.vectori=newptr；elsepnext=newptr;p=newptr；p2=p2next;k+;M.t=k;/置和矩阵中结点数cout相加后得矩阵”endl；return M;/返回和矩阵void menu()/ 菜单函数 cout 稀疏矩阵运算 endl;cout” *”endl；cout * 1。用三元组（顺序存储)建立矩阵 *”endl;cout * 2.矩阵普通转置 ”endl；cout” * 3。矩阵快速转置 *”endl；/cout” 4。矩阵乘法 *”endl；cout * 4。用三元组(链接存储）建立矩阵 ”endl;cout” * 5.矩阵加法 *endl;cout * 6.退出 *”endl；cout” *”endl;