《《稀疏矩阵和广义表》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《稀疏矩阵和广义表》PPT课件.ppt（41页珍藏版）》请在三一文库上搜索。
1、3.4稀疏矩阵 3.5广义表,集合、稀疏矩阵和广义表,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) ),2稀疏矩阵的三元组线性表表示 稀疏矩阵若用二维数组存储太浪费空间。 一般只考虑存储非零元素，每个非零元素可由行、列、值三元组(i, j, aij)表示，三元组按行号为主序、列号为辅序进行排列，构成一个表示稀疏矩阵的三元组线性表。 三元组线性表可用顺序或链接方式存储。,3稀疏矩阵
2、的抽象数据类型 ADT SparseMatrix is Data: 用三元组线性表表示的稀疏矩阵， 用类型名SMatrix表示 Operation: void InitMatrix(SMatrix end SparseMatrix,3.4.2 稀疏矩阵的存储结构： 稀疏矩阵有顺序和链接两种存储结构。存储内容为三元组线性表及其行数、列数、非零元个数。 顺序存储 用顺序结构存储三元组线性表，即数组的每个元素对应一个非零元的三元组。 struct Triple int row, col; /非零元素的行号、列号 ElemType val; /元素值 ; struct SMatrix int m, n
3、, t; /矩阵的行、列数及非零元素个数 Triple smMaxTerms+1; /三元组线性表，从sm1开始 ;,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）带行指针向量的链接存储 每一行的非零元对应一个单链表(按列号次序)，用一维数组保存所有单链表的头指针。 struct TripleNode int
4、row, col; /非零元素的行号、列号 ElemType val; /元素值 TripleNode *next; ; struct LMatrix int m, n, t; /矩阵的行、列数及非零元素个数 TripleNode *vectorMaxRows+1; /从vector1开始保存 ;,( (1,1,7), (1,5,15), (3,4,-1), (4,1,-2), (4,6,21) ),1 2 3 4,vector,m,n,t,4,6,5,带行指针向量的链接存储结构,（2）十字链接存储 既带行指针向量，又带列指针向量，每一个结点同时位于两个单链表中。 struct CrossNo
5、de int row, col; /非零元素的行号、列号 ElemType val; /元素值 CrossNode *right, *down; /指向同一行,同一列的下一个结点 ; struct CLMatrix int m, n, t; /矩阵的行、列数及非零元素个数 CrossNode *rvMaxRows+1; /行指针向量，从rv1开始 CrossNode *cvMaxColumns+1; /列指针向量，从cv1开始 ;,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,6,21,4,4,-1,3,cv,r
6、v, , ,( (1,1,7), (1,5,15), (3,4,-1), (4,1,-2), (4,6,21) ),*3.4.3 稀疏矩阵的运算 1.初始化 SMarix类型 void InitMatrix(SMatrix ,M.m,M.n,M.t,0,0,0,(2)LMatrix类型 void InitMatrix(LMatrix ,1 2 . . . MaxRows,M.vector,M.m,M.n,M.t,0,0,0,2. 输入 SMarix类型 void InputMatrix( SMatrix ,(2)LMatrix类型 void InputMatrix( LMatrix ,1 2
7、. . . MaxRows,M.vector,M.m,M.n,M.t,/插在单链表末尾 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 ,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,
8、-2), (4,6,21) ),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,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,（1）普通转置法 对sm数组进行n(列数)次扫描，每次转换成相应行 SMatrix Transpose( SMatrix M) O(n*t) int k=1; SMatrix S; InitMat
9、rix(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; ,（2）快速转置法 对sm数组进行2次扫描。第一次扫描计算出原矩阵中每一列非零元的个数（用num数组存放），由此计算出每一列的第一个非零元在转置矩阵数组中的位置（用pot数组存放） ；第二次扫描则把每
10、个三元组写到转置矩阵数组的相应位置上。 计算公式： 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,SMatrix FastTranspose( SMatrix M) O(n+t) int k, i, j, col; int *num, *pot; SMatrix
11、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;,for (i=1; i=M.t; i+) j= M.smi.col; k= potj; S.smk.row
12、=M.smi.col; S.smk.col=M.smi.row; S.smk.val=M.smi.val; potj+; delete num; delete pot; return S; ,5.加法运算 采用LMatrix类型，计算 M=M1+M2 (M1与M2需大小相同） 两矩阵相加的前提条件是：两矩阵的大小相同，即行数和列数分别相等。,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
13、; if ( (M1.t=0) ,while ( (p1!=NULL) ,/以下插入newptr到第i行链尾，并后移p指针 newptr-next=NULL; if (p=NULL ) M.vectori=newptr; else p-next=newptr; p=newptr; k+; /while while (p1!=NULL) newptr=new TripleNode; *newptr=*p1; newptr-next=NULL; if (p=NULL ) M.vectori=newptr; else p-next=newptr; p=newptr; p1=p1-next; k+;
14、/while,while (p2!=NULL) newptr=new TripleNode; *newptr=*p2; newptr-next=NULL; if (p=NULL ) M.vectori=newptr; else p-next=newptr; p=newptr; p2=p2-next; k+; /while /for M.t=k; return M; O(M1.t+M2.t),3.5 广义表（generalized list） 3.5.1广义表的定义 广义表是线性表的推广。广义表是 n(n=0) 个数据元素a1, a2, ， an 构成的有限序列，数据元素可以是单个元素（称为单元
15、素），也可以是广义表（称为子表或表元素）。广义表是一种递归的数据结构。 广义表一般表示为: 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,3.5.2广义表
16、的存储结构： 一般采用链接结构。 结点结构（两种类型结点）定义： struct GLNode int tag; /标志域，0代表单元素，1代表子表 union ElemType data; /单元素：值 struct Node *sublist; /子表：指向子表的第一个结点 ; GLNode *next; /指向后继结点 ;,A=NULL,0 d ,0 a,1 ,0 b,0 c ,B,C,1 ,1,1 ,0 d ,0 a,1 ,0 b,0 c ,D,不带表头附加结点的链接结构,A=( ) B=(d) C=(a, (b,c) D=(A,B,C)=( (), (d), (a,(b,c) ),A,
17、1 ,B,1 ,0 a,1 ,0 b,0 c ,C,1 ,0 d ,带表头附加结点的链接结构,A=( ) B=(d) C=(a, (b,c) D=(A,B,C)=( (), (d), (a,(b,c) ),3.5.3广义表的运算,求广义表长度 递归算法如下：（也可用非递归算法） int Length(GLNode *GL) O(n) （n为结点数） if (GL!=NULL) return 1 + Length(GL-next); else return 0; ,采用不带表头附加结点的链接结构,2. 求广义表深度 递归算法如下：(深度为所有子表中的最大深度加1) int Depth(GLNod
18、e *GL) O(n) （n为结点数） int dep, max=0; while (GL!=NULL) if (GL-tag=1) dep=Depth(GL-sublist); if (depmax) max=dep; GL=GL-next; return max+1; ,建立广义表存储结构 输入格式为： A=( ) #; B=(d) d; C=(a, (b,c) a,(b,c); D=( (), (d), (a,(b,c) ) (#), (d), (a,(b,c); 递归算法思路： 扫描每一个输入的字符，根据不同类型作不同处理。若是空表（#），直接结束；若是单元素（字母），先建立新结点，再
19、递归调用建立后续结点或结束；若是子表（(），先递归调用建立子表，再递归调用建立后续结点或结束。,void Create(GLNode * ,cinch; / 只可能读入 , 、 ) 及 ; if (GL!=NULL) if (ch=,) Create(GL-next); /递归构造后继表 else if ( (ch=) | (ch=;) ) GL-next=NULL; ,4. 输出广义表 递归算法思路： MPrint: 输出广义表最外层的一对括号，调用Print 输出广义表其余内容。 Print: 先输出第一个元素（若是非空子表，则递归调用输出），再递归调用输出后继表。 void MPrint(GLNode *GL) O(n)（n为结点数） /输出广义表最外层的一对括号，其余内容调用Print输出 cout(; if (GL=NULL) cout#; else Print(GL); cout); ,void Print(GLNode *GL) O(n)（n为结点数） if (GL-tag=1) /子表结点 coutsublist=NULL) coutsublist); /递归输出子表 coutdata; /单元素结点 if (GL-next!=NULL) coutnext); /递归输出后继表 ,3.5.4简单程序举例,