稀疏矩阵和广义表课件

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,3.4稀疏矩阵,3.5广义表,集合、稀疏矩阵和广义表,3.4稀疏矩阵 集合、稀疏矩阵和广义表,3.4 稀疏矩阵,3.4.1 稀疏矩阵的定义,1稀疏矩阵,：,非零元素个数远远少于零元素个数的矩阵,三元组线性表表示：,(1,4,22),(1,7,15),(2,2,11),(2,6,17),(3,4,-6),(4,6,39),(5,1,91),(6,3,28),3.4 稀疏矩阵 三元组线性表表示：,2稀疏矩阵的三元组线性表表示,稀疏矩阵若用二维数组存储太浪费空间。,一般只考虑存储非零元素，每个非零元素可由行,、,列,、,值三元组(i,j,a,ij,),表示，三元组按行号为主序、列号为辅序进行排列，构成一个表示稀疏矩阵的,三元组线性表。,三元组线性表可用顺序或链接方式存储。,2稀疏矩阵的三元组线性表表示,3,稀疏矩阵的抽象数据类型,ADT SparseMatrix is,Data:,用,三元组线性表表示的稀疏矩阵，,用类型名,SMatrix,表示,Operation:,void InitMatrix(SMatrix,SMatrix Transpose(SMatrix ,SMatrix Add(SMatrix,SMatrix Multiply(SMatrix ,void InputMatrix(SMatrix,void OutputMatrix(SMatrix,end SparseMatrix,3稀疏矩阵的抽象数据类型,3.4.2,稀疏矩阵的存储结构：,稀疏矩阵,有顺序和链接两种,存储结构。存储内容为,三元组线性表及其行数,、,列数,、,非零元个数。,顺序存储,用顺序结构存储三元组线性表，即,数组的每个元素对应一个非零元的三元组。,struct,Triple,int row,col;,/,非零元素的行号、列号,ElemType val;,/,元素值,;,struct,SMatrix,int m,n,t;,/,矩阵的行、列数及非零元素个数,Triple smMaxTerms+1;,/,三元组线性表，从sm1开始,;,3.4.2 稀疏矩阵的存储结构：,7 0 0 0 15 0,0 0 0 0 0 0,-2 0 0 0 0 21,0 0 0 -1 0 0,A=,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),7 0 0,链接存储,用链接结构存储三元组线性表,（1）带行指针向量的链接存储,每一行的非,零元,对应一个单链表(按列号次序)，用一维数组保存所有单链表的头指针,。,struct TripleNode,int row,col;,/,非零元素的行号、列号,ElemType val;,/,元素值,TripleNode,*next;,;,struct,LMatrix,int m,n,t;,/,矩阵的行、列数及非零元素个数,TripleNode*vectorMaxRows+1;,/,从vector1开始保存,;,链接存储,7 0 0 0 15 0,0 0 0 0 0 0,-2 0 0 0 0 21,0 0 0 -1 0 0,A=,(1,1,7),(1,5,15),(3,4,-1),(4,1,-2),(4,6,21),1,2,3,4,1 1 7,1 5 15 ,3 4 -1 ,4 1 -2,4 6 21 ,vector,m,n,t,4,6,5,带行指针向量的链接存储结构,7 0 0,（2）十字链接存储,既带,行指针向量，又带列指针向量，,每一个结点同时位于两个单链表中,。,struct CrossNode,int row,col;,/,非零元素的行号、列号,ElemType val;,/,元素值,CrossNode,*right,*down;,/,指向同一行,同一列的下一个结点,;,struct CLMatrix,int m,n,t;,/,矩阵的行、列数及非零元素个数,CrossNode*rvMaxRows+1;,/,行指针向量，从rv1开始,CrossNode*cvMaxColumns+1;,/,列指针向量，从cv1开始,;,（2）十字链接存储,7 0 0 0 15 0,0 0 0 0 0 0,-2 0 0 0 0 21,0 0 0 -1 0 0,A=,5,15,1,1,-2,4,6,21,4,1,7,1,4,-1,3,col,val,right,down,row,cv,rv,(1,1,7),(1,5,15),(3,4,-1),(4,1,-2),(4,6,21),7 0 0,*3.4.3,稀疏矩阵的运算,1.,初始化,SMarix,类型,void InitMatrix(SMatrix&M),M.m=0;M.n=0;M.t=0;,1,2,3,4,5,row,col,val,M.sm:,MaxTerms,M.m,M.n,M.t,0,0,0,*3.4.3 稀疏矩阵的运算12345rowcolval,(2)LMatrix,类型,void InitMatrix(LMatrix&M),M.m=0;M.n=0;M.t=0;,for(int i=1;irowcolval;,while(row!=0),k+;,M.smk.row=row;,M.smk.col=col;,M.smk.val=val;,cinrowcolval;,M.m=m;M.n=n;M.t=k;,1,2,3,4,5,row,col,val,M.sm:,MaxTerms,M.m,M.n,M.t,2.输入 12345rowcolval M.sm:,(2)LMatrix,类型,void InputMatrix(LMatrix&M,int m,int n),/,以行序为主序次序每行输入一个三元组，最后以“0 0 0”结束,TripleNode *p,*q;,int row,col,val,k=0;,cinrowcolval;,while(row!=0),k+;,p=new,TripleNode;,p-row=row;,p-col=col;,p-val=val;,p-next=NULL;,q=M.,vectorrow;,1,2,.,.,.,MaxRows,.,.,.,M.vector,M.m,M.n,M.t,(2)LMatrix类型 1.M,/,插在单链表末尾,if(q=NULL),M.,vectorrow=p;,else ,while(q-next!=NULL)q=q-next;,q-next=p;,cinrowcolval;,M.m=m;M.n=n;M.t=k;,/插在单链表末尾,3.,输出,SMarix,类型,void OutputMatrix(SMatrix&M),/,按三元组线性表格式输出稀疏矩阵,cout“(“;,for(int i=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;,3.输出,7 0 0 0 15 0,0 0 0 0 0 0,-2 0 0 0 0 21,0 0 0 -1 0 0,A=,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),7 0 0,4.,转置运算,以,SMarix,类型为例,7 0 0 0 15 0,0 0 0 0 0 0,-2 0 0 0 0 21,0 0 0 -1 0 0,A=,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,7 0 0 -2,0 0 0 0,0 0 -1 0,0 0 0 0,A=,15 0 0 0,0 0 0 21,4*6,6*4,4.转置运算 7,（1）普通转置法,对sm数组进行n(列数)次扫描，每次转换成相应行,SMatrix Transpose(SMatrix M),O(n*t),int k=1;,SMatrix S,;,InitMatrix(S);,S.m=M.n;S.n=M.m;S.t=M.t;,if(t=0)return S;,for(int col=1;col=M.n;col+),for(int i=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+;,return S;,（1）普通转置法,（2）快速转置法,对sm数组进行2次扫描。第一次扫描计算出原矩阵中每一列非零元的个数（用num数组存放），由此计算出每一列的第一个非零元在转置矩阵数组中的位置（用pot数组存放）；第二次扫描则把每个三元组写到转置矩阵数组的相应位置上。,计算公式：,pot1=1 potcol=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,i,1 2 3 4 5 6,num 2 0 0 1 1 1,pot,1 3 3 3 4 5,（2）快速转置法12345rowcolval1 171,SMatrix FastTranspose(SMatrix M),O(n+t),int k,i,j,col;,int*num,*pot;,SMatrix S,;,/S,存放转置矩阵,InitMatrix(S);,S.m=M.n;S.n=M.m;S.t=M.t;,if(t=0)return S;,num=new intM.n+1;,pot=new intM.n+1;,for(col=1;col=M.n;col+),numcol=0;,for(i=1;i=M.t;i+),num M.smi.col+;,pot1=1;,for(col=2;col=M.n;col+),potcol=potcol-1+numcol-1;,SMatrix FastTranspose(SM,for(i=1;i=M.t;i+),j=M.smi.col;,k=potj;,S.smk.row=M.smi.col;,S.smk.col=M.smi.row;,S.smk.val=M.smi.val;,potj+;,delete num;,delete pot;,return S;,for(i=1;i=M.t;,5.,加法运算,采用LMatrix类型，计算 M=M1+M2,(M1,与M2需大小相同）,两矩阵相加的前提条件是：两矩阵的大小相同，即行数和列数分别相等。,5.加法运算,LMatrix Add(LMatrix M1,LMatrix M2),int k=0;,/,统计非零元个数,Triple*p1,*p2,*p,*newptr;,LMatrix M;,InitMatrix(M);,M.m=M1.m;M.n=M1.n;,if(M1.t=0)&(M2.t=0),return M;,for(int i=1;icol col),*newptr=*p1;p1=p1-next;,else if(p1-col p2-col),*newptr=*p2;p2=p2-next