第3章 稀疏矩阵和广义表

主要内容：稀疏矩阵广义表集合由具有相同属性的数据元素组合而成，数据之间没有任何前驱和后继关系。这两种数据结构是线性表的扩展：数据元素本身也是一个数据结构,第三章稀疏矩阵和广义表,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)表示，三元组按行号为主序排列，构成一个表示稀疏矩阵的三元组线性表。三元组线性表可用顺序或链接方式存储。,稀疏矩阵的抽象数据类型：ADTSpaseMatrixisData:用三元组线性表表示的稀疏矩阵，用类型名SMatrix表示Operation:voidInitMatrix(SMatrixendSpaseMatrix,二、稀疏矩阵的存储结构：稀疏矩阵有顺序和链接两种存储结构。存储内容为三元组线性表及其行数、列数、非零元个数。顺序存储用顺序结构存储三元组线性表，即数组的每个元素对应一个非零元的三元组。typedefstructintrow,col;/非零元素的行号、列号ElemTypeval;/元素值Triple;typedefstructintm,n,t;/矩阵的行、列数及非零元素个数TriplesmMaxTerms+1;/三元组线性表，从sm1开始SMatrix;,1,2,3,4,5,row,col,val,1,1,7,1,5,15,3,4,-1,4,1,-2,4,6,21,sm:,MaxTerms,m,n,t,4,6,5,非零元以行序为主序存储,(1,1,7),(1,5,15),(3,4,-1),(4,1,-2),(4,6,21),链接存储用链接结构存储三元组线性表（1）带行指针向量的链接存储每一行的非零元对应一个单链表(按列号次序)，用一维数组保存所有单链表的头指针。typedefstructNodeintrow,col;/非零元素的行号、列号ElemTypeval;/元素值structNode*next;TripleNode;typedefstructintm,n,t;/矩阵的行、列数及非零元素个数TripleNode*vectorMaxRows+1;/从vector1开始保存LMatrix;,(1,1,7),(1,5,15),(3,4,-1),(4,1,-2),(4,6,21),1234,vector,m,n,t,4,6,5,（2）十字链接存储既带行指针向量，又带列指针向量，每一个结点同时位于两个单链表中。typedefstructNodeintrow,col;/非零元素的行号、列号ElemTypeval;/元素值structNode*right,*down;/指向同一行,同一列的下一个结点CrossNode;typedefstructintm,n,t;/矩阵的行、列数及非零元素个数CrossNode*rvMaxRows+1;/行指针向量，从rv1开始CrossNode*cvMaxColumns+1;/列指针向量，从cv1开始CLMatrix;,7000150,000000,-2000021,000-100,A=,5,15,1,6,21,4,4,-1,3,cv,rv,(1,1,7),(1,5,15),(3,4,-1),(4,1,-2),(4,6,21),三、稀疏矩阵的运算1.初始化SMarix类型voidInitMatrix(SMatrix,M.m,M.n,M.t,0,0,0,(2)LMatrix类型voidInitMatrix(LMatrix,12.MaxRows,M.vector,M.m,M.n,M.t,0,0,0,2.输入SMarix类型voidInputMatrix(SMatrix,(2)LMatrix类型voidInputMatrix(LMatrix,12.MaxRows,M.vector,M.m,M.n,M.t,/插在单链表末尾if(q=NULL)M.vectorrow=p;elsewhile(q-next!=NULL)q=q-next;q-next=p;cinrowcolval;M.m=m;M.n=n;M.t=k;,3.输出SMarix类型voidOutputMatrix(SMatrixM)/按三元组线性表格式输出稀疏矩阵cout“(“;for(inti=1;iM.t;i+)cout“(“M.smi.row“,”;coutM.smi.col“,”;coutM.smi.val“)“,”;if(M.t!=0)/输出最后一项cout“(“M.smM.t.row“,”;coutM.smM.t.col“,”;coutM.smM.t.val“)“;cout“)”endl;,1,2,3,4,m.t,row,col,val,1,1,7,1,5,15,3,4,-1,4,1,-2,4,6,21,sm:,输出：(1,1,7),(1,5,15),(3,4,-1),(4,1,-2),(4,6,21),(2)LMatrix类型作业,4.转置运算以SMarix类型为例,1,2,3,4,5,row,col,val,1,1,7,1,5,15,3,4,-1,4,1,-2,4,6,21,sm:,1,2,3,4,5,1,1,7,1,4,-2,4,3,-1,5,1,15,6,4,21,700-2,0000,00-10,0000,A=,15000,00021,4*6,6*4,（1）普通转置法对sm数组进行n(列数)次扫描，每次转换成相应行SMatrixTranspose(SMatrixM)O(n*t)intk=1;SMatrixS;InitMatrix(S);S.m=M.n;S.n=M.m;S.t=M.t;if(t=0)returnS;for(intcol=1;col=M.n;col+)for(inti=1;i=M.t;i+)if(M.smi.col=col)S.smk.row=col;S.smk.col=M.smi.row;S.smk.val=M.smi.val;k+;returnS;,（2）快速转置法对sm数组进行2次扫描。第一次扫描计算出原矩阵中每一列非零元的个数（用num数组存放），由此计算出每一列的第一个非零元在转置矩阵数组中的位置（用pot数组存放）；第二次扫描则把每个三元组写到转置矩阵数组的相应位置上。计算公式：pot1=1potcol=potcol-1+numcol-1,1,2,3,4,5,row,col,val,1,1,7,1,5,15,3,4,-1,4,1,-2,4,6,21,1,1,7,1,4,-2,4,3,-1,5,1,15,6,4,21,1,2,3,4,5,row,col,val,i123456num200111pot133345,SMatrixFastTranspose(SMatrixM)O(n+t)intk,i,j,col;int*num,*pot;SMatrixS;/S存放转置矩阵InitMatrix(S);S.m=M.n;S.n=M.m;S.t=M.t;if(t=0)returnS;num=newintM.n+1;pot=newintM.n+1;for(col=1;col=M.n;col+)numcol=0;for(i=1;i=M.t;i+)numM.smi.col+;pot1=1;for(col=2;colnext=newptr;p=newptr;k+;/whilewhile(p1!=NULL)newptr=newTripleNode;*newptr=*p1;newptr-next=NULL;if(p=NULL)M.vectori=newptr;elsep-next=newptr;p=newptr;p1=p1-next;k+;/while,while(p2!=NULL)newptr=newTripleNode;*newptr=*p2;newptr-next=NULL;if(p=NULL)M.vectori=newptr;elsep-next=newptr;p=newptr;p2=p2-next;k+;/while/forM.t=k;returnM;O(M1.t+M2.t),3.5广义表一、广义表的定义：概念：广义表是线性表的推广。广义表是n(n=0)个数据元素a1,a2,，an构成的有限序列，数据元素可以是单个元素（称为单元素），也可以是广义表（称为子表或表元素）。是递归定义。广义表一般表示为:LS=(a1,a2,，an)n称为广义表的长度，n=0时称为空表,表示法：小写字母表示单元素，大写字母表示表元素A=()B=(d)C=(a,(b,c)D=(A,B,C)=(),(d),(a,(b,c)A()B(d)C(a,(b,c)D(A(),B(d),C(a,(b,c)表的深度指括号嵌套的最大次数。A和B的深度为1，C的深度为2，D的深度为3。,d,a,b,c,d,a,b,c,A,B,C,D,A,B,C,二、广义表的存储结构：一般采用链接结构。结点结构（两种类型结点）定义：typedefstructNodeinttag;/标志域，0代表单元素，1代表子表unionElemTypedata;/单元素：值structNode*sublist;/子表：指向子表的第一个结点;structNode*next;/指向后继结点GLNode;,A=NULL,0d,0a,1,0b,0c,B,C,1,1,1,0d,0a,1,0b,0c,D,不带表头附加结点的链接结构,A=()B=(d)C=(a,(b,c)D=(A,B,C)=(),(d),(a,(b,c),A,1,B,1,0a,1,0b,0c,C,1,0d,带表头附加结点的链接结构,A=()B=(d)C=(a,(b,c)D=(A,B,C)=(),(d),(a,(b,c),三、广义表的运算：,求广义表长度递归算法如下：（也可用非递归算法）intLenth(GLNode*GL)O(n)（n为结点数）if(GL!=NULL)return1+Length(GL-next);elsereturn0;,采用不带表头附加结点的链接结构,2.求广义表深度递归算法如下：(深度为所有子表中的最大深度加1)intDepth(GLNode*GL)O(n)（n为结点数）intdep,max=0;while(GL!=NULL)if(GL-tag=1)dep=Depth(GL-sublist);if(depmax)max=dep;GL=GL-next;returnmax+1;,建立广义表存储结构输入格式为：A=()#;B=(d)d;C=(a,(b,c)a,(b,c);D=(),(d),(a,(b,c)(#),(d),(a,(b,c);递归算法思路：扫描每一个输入的字符，根据不同类型作不同处理。若是空表（#），直接结束；若是单元素（字母），先建立新结点，再递归调用建立后续结点或结束；若是子表（(），先递归调用建立子表，再递归调用建立后续结点或结束。,voidCreate(GLNode*,cinch;/只可能读入,、)及;if(GL!=NULL)if(ch=,)Create(GL-next);/递归构造后继表elseif(ch