资源描述：
《第3章 稀疏矩阵和广义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、主要内容：稀疏矩阵广义表集合由具有相同属性的数据元素组合而成，数据之间没有任何前驱和后继关系。这两种数据结构是线性表的扩展：数据元素本身也是一个数据结构第三章稀疏矩阵和广义表3.4稀疏矩阵一、稀疏矩阵的定义：概念：非零元素个数远远少于零元素个数的矩阵三元组线性表：((1,4,22),(1,7,15),(2,2,11),(2,6,17),(3,4,-6),(4,6,39),(5,1,91),(6,3,28))稀疏矩阵的三元组线性表表示:稀疏矩阵若用二维数组存储太浪费空间。一般只考虑存储非零元素，每个非零元素可由行、列、值三元组(i,j,aij)表示，三元组按行
2、号为主序排列，构成一个表示稀疏矩阵的三元组线性表。三元组线性表可用顺序或链接方式存储。稀疏矩阵的抽象数据类型：ADTSpaseMatrixisData:用三元组线性表表示的稀疏矩阵，用类型名SMatrix表示Operation:voidInitMatrix(SMatrix&M);SMatrixTranspose(SMatrixM);SMatrixAdd(SMatrixM1,SMatrixM2);SMatrixMultiply(SMatrixM1,SMatrixM2);voidInputMatrix(SMatrix&M,intm,intn);voidOutpu
3、tMatrix(SMatrixM);endSpaseMatrix二、稀疏矩阵的存储结构：稀疏矩阵有顺序和链接两种存储结构。存储内容为三元组线性表及其行数、列数、非零元个数。顺序存储用顺序结构存储三元组线性表，即数组的每个元素对应一个非零元的三元组。typedefstruct{introw,col;//非零元素的行号、列号ElemTypeval;//元素值}Triple;typedefstruct{intm,n,t;//矩阵的行、列数及非零元素个数Triplesm[MaxTerms+1];//三元组线性表，从sm[1]开始}SMatrix;7000150000
4、000-2000021000-100A=12345rowcolval117151534-141-24621…sm:MaxTermsmnt465非零元以行序为主序存储((1,1,7),(1,5,15),(3,4,-1),(4,1,-2),(4,6,21))链接存储用链接结构存储三元组线性表（1）带行指针向量的链接存储每一行的非零元对应一个单链表(按列号次序)，用一维数组保存所有单链表的头指针。typedefstructNode{introw,col;//非零元素的行号、列号ElemTypeval;//元素值structNode*next;}TripleNode
5、;typedefstruct{intm,n,t;//矩阵的行、列数及非零元素个数TripleNode*vector[MaxRows+1];//从vector[1]开始保存}LMatrix;7000150000000-2000021000-100A=((1,1,7),(1,5,15),(3,4,-1),(4,1,-2),(4,6,21))12341171515^34-1^41-24621^^vectormnt465（2）十字链接存储既带行指针向量，又带列指针向量，每一个结点同时位于两个单链表中。typedefstructNode{introw,col;//非零
6、元素的行号、列号ElemTypeval;//元素值structNode*right,*down;//指向同一行,同一列的下一个结点}CrossNode;typedefstruct{intm,n,t;//矩阵的行、列数及非零元素个数CrossNode*rv[MaxRows+1];//行指针向量，从rv[1]开始CrossNode*cv[MaxColumns+1];//列指针向量，从cv[1]开始}CLMatrix;7000150000000-2000021000-100A=515^^11-2^4621∧∧41714-1∧∧3colvalrightdownrow
7、cvrv^^^^∧∧((1,1,7),(1,5,15),(3,4,-1),(4,1,-2),(4,6,21))三、稀疏矩阵的运算1.初始化SMarix类型voidInitMatrix(SMatrix&M){M.m=0;M.n=0;M.t=0;}12345rowcolval…M.sm:MaxTermsM.mM.nM.t000(2)LMatrix类型voidInitMatrix(LMatrix&M){M.m=0;M.n=0;M.t=0;for(inti=1;i<=MaxRows;i++)M.vector[i]=NULL;}12...MaxRows^^...^M.
8、vectorM.mM.nM.t0002.输入SMar
