课程设计--稀疏矩阵应用

数学与计算机学院课程设计说明书课程名称:数据结构课程设计课程代码:8404181题目:稀疏矩阵应用年级/专业/班:学生姓名:学号:开始时间:2011年06月13日完成时间:2011年06月21日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总分（100）指导教师签名：年月日稀疏矩阵应用目录1引言.....................................................11.1问题的提出...............................................11.2国内外研究的现状..........................................11.3任务与分析...............................................12程序的主要功能.............................................12.1三元组的转置..............................................12.2三元组的加法..............................................12.3三元组的减法..............................................12.4三元组的乘法..............................................22.5十字链表的转置............................................22.6十字链表的加法............................................22.7十字链表的减法............................................22.8十字链表的乘法............................................23程序运行平台................................................34总体设计...................................................35程序类的说明................................................46模块分析...................................................5稀疏矩阵应用6.1三元组的转置.............................................56.2三元组减法...............................................66.3三元组的减法..............................................96.4三元组的乘法.............................................126.5十字链表的转置..........................................146.6十字链表的加法..........................................156.7十字链表的减法...........................................186.8十字链表的乘法...........................................227系统测试..................................................257.1三元组的转置.............................................257.2三元组的加法............................................267.3三元组的减法............................................267.4三元组的乘法............................................277.5十字链表的转置..........................................277.6十字链表的加法...........................................287.7十字链表的减法..........................................287.8十字链表的乘法..........................................297.9总结....................................................298结论......................................................29参考文献....................................................29稀疏矩阵应用摘要随着计算机的普及，一句话引出题目…（小四楷体_GB2312），分析了三元组和十字链表的存储和各种运算的实现，利用C语言编程实现了稀疏矩阵的运算系统，该系统具有三元组十字链表存储下的稀疏矩阵转置、加法、减法、乘法的功能。关键词：稀疏矩阵;计算机;运算器-1-稀疏矩阵应用1引言1.1问题的提出矩阵是很多科学与工程计算问题中研究的数学对象。因此，我们感兴趣的不是矩阵本身，而是如何存储矩阵的元，从而使矩阵的各种运算能有效地进行。通常，用高级语言编制程序时，都是用二维数组来存储矩阵元，有的程序设计语言中还提供了各种矩阵运算，用户使用时很方便。然而，在数值分析中，经常出现一些阶数很高的矩阵，同时在矩阵中有许多值相同的元素或者是零元素，有时为了节省存储空间，可以对这类矩阵进行压缩存储。所谓压缩存储，就是指：为多个值相同的元只分配一个存储空间；对零元不分配空间。1.2国内外研究的现状目前已经可以用于人脸识别、子空间方法预处理技术稀疏近似逆按模最小特征值修正矩阵广义极小残余方法等方面。1.3任务与分析（1）给出算法并编程实现；（2）任给实例并演示求解结果；（3）给出时间复杂度分析；（4）结合所完成题目，分析总结各算法所使用的算法设计技术，以及相应技术的基本思想。2程序的主要功能2.1三元组的转置将一个按三元组存储的稀疏矩阵进行转置。2.2三元组的加法将两个按三元组存储的稀疏矩阵进行相加并得出结果。2.3三元组的减法将两个按三元组存储的稀疏矩阵进行相减并得出结果。-2-稀疏矩阵应用2.4三元组的乘法将两个按三元组存储的稀疏矩阵进行相乘并得出结果。2.5十字链表的转置将一个按十字链表存储的稀疏矩阵进行转置。2.6十字链表的加法将两个按十字链表存储的稀疏矩阵进行相加并得出结果。2.7十字链表的减法将两个按十字链表存储的稀疏矩阵进行相加并得出结果。2.8十字链表的乘法将两个按十字链表存储的稀疏矩阵进行相加并得出结果。-3-稀疏矩阵应用3程序运行平台VC++6.0。编译，链接，执行。4总体设计图4.1系统总体框架图主函数三元组创建三元组转置三元组加法三元组减法十字链表创建十字链表转置十字链表加法十字链表减法十字链表乘法-4-稀疏矩阵应用5程序类的说明OLNode结构声明typedefstructOLNode{inti,j;inte;structOLNode*right,*down;}OLNode,*OLink;Crosslist结构的声明typedefstruct{intmu,nu,tu;OLink*rhead,*chead;}CrossList;Triple结构的声明typedefstruct{inti,j;inte;}Triple;TSMatrix结构的声明typedefstruct{Tripledata[maxsize];intrpos[maxsize+1];intnu,mu,tu;}TSMatrix;-5-稀疏矩阵应用6模块分析6.1三元组的转置将一个按三元组存储的稀疏矩阵进行转置（非快速转置）。voidTransposeSMatrix(TSMatrixM,TSMatrix&T)//三元组的转置{T.nu=M.mu;T.mu=M.nu;T.tu=M.tu;intq=1;for(intcol=1;col=M.nu;col++)for(intp=1;p=M.tu;p++)if(M.data[p].j==col){T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;q++;}}intCompare(inta1,intb1,inta2,intb2){-6-稀疏矩阵应用if(a1a2)return1;elseif(a1a2)return-1;elseif(b1b2)return1;if(b1b2)return-1;elsereturn0;}6.2三元组减法用户再输入一个稀疏矩阵，系统将两个矩阵进行加运算并得出结果。voidAddTMatix(TSMatrixM,TSMatrixT,TSMatrix&S)//三元组相加{S.mu=M.muT.mu?M.mu:T.mu;S.nu=M.nuT.nu?M.nu:T.nu;S.tu=0;intce;intq=1;intmcount=1,tcount=1;while(mcount=M.tu&&tcount=T.tu){switch(Compare(M.data[mcount].i,M.data[mcount].j,T.data[tcount].i,T.data-7-稀疏矩阵应用[tcount].j)){case-1:S.data[q].e=M.data[mcount].e;S.data[q].i=M.data[mcount].i;S.data[q].j=M.data[mcount].j;q++;mcount++;break;case1:S.data[q].e=T.data[tcount].e;S.data[q].i=T.data[tcount].i;S.data[q].j=T.data[tcount].j;q++;tcount++;break;case0:ce=M.data[mcount].e+T.data[tcount].e;if(ce){S.data[q].e=ce;S.data[q].i=M.data[mcount].i;-8-稀疏矩阵应用S.data[q].j=M.data[mcount].j;q++;mcount++;tcount++;}else{mcount++;tcount++;}break;}}while(mcount=M.tu){S.data[q].e=M.data[mcount].e;S.data[q].i=M.data[mcount].i;S.data[q].j=M.data[mcount].j;q++;mcount++;}while(tcount=M.tu)-9-稀疏矩阵应用{S.data[q].e=T.data[tcount].e;S.data[q].i=T.data[tcount].i;S.data[q].j=T.data[tcount].j;q++;tcount++;}S.tu=q-1;}…6.3三元组的减法用户再输入一个稀疏矩阵，系统将两个矩阵进行加运、减算并得出结果。voidjianTMatix(TSMatrixM,TSMatrixT,TSMatrix&S)//三元组相减{S.mu=M.muT.mu?M.mu:T.mu;S.nu=M.nuT.