第3章2稀疏矩阵和广义表

1、 1稀疏矩阵稀疏矩阵：非零元素个数远远少于零元素个数的矩阵非零元素个数远远少于零元素个数的矩阵 0000280000000091039000000006000017000110150022000A76 三元组线性表表示：三元组线性表表示：( (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 2稀疏矩阵的三元组线性表表示稀疏矩阵的三元组线性表表示 稀疏矩阵若用二维数组存储太浪费空间。稀疏矩阵若用二维数组存储太浪费空间。 一般只考虑存储非零元素，每个非零元素一般只考虑存储非零元素，每个非零元素可由

2、行可由行、列列、值三元组值三元组(i, j, a(i, j, aijij) )表示，三元表示，三元组按行号为主序、列号为辅序进行排列，构成组按行号为主序、列号为辅序进行排列，构成一个表示稀疏矩阵的一个表示稀疏矩阵的三元组线性表。三元组线性表。 三元组线性表可用顺序或链接方式存储。三元组线性表可用顺序或链接方式存储。 3 3稀疏矩阵的抽象数据类型稀疏矩阵的抽象数据类型ADT SparseMatrix is Data: 用用三元组线性表表示的稀疏矩阵，三元组线性表表示的稀疏矩阵， 用类型名用类型名SMatrix表示表示 Operation: void InitMatrix(SMatrix &

3、;M); SMatrix Transpose(SMatrix &M); SMatrix Add(SMatrix &M1, SMatrix &M2); SMatrix Multiply(SMatrix &M1, SMatrix &M2); void InputMatrix(SMatrix &M, int m, int n); void OutputMatrix(SMatrix &M);end SparseMatrix有顺序和链接两种有顺序和链接两种三元组线性表及其行数三元组线性表及其行数、列数列数、非零元个数。非零元个数。1. 顺序存储顺序

4、存储 用顺序结构存储三元组线性表，即用顺序结构存储三元组线性表，即数组的每个元素数组的每个元素对应一个非零元的三元组。对应一个非零元的三元组。 7 0 0 0 15 0 0 0 0 0 0 0 -2 0 0 0 0 21 0 0 0 -1 0 0A=12345rowcolval1 171 51534 -141 -246 21sm:MaxTermsmnt465非零元以行序为主序存储非零元以行序为主序存储( (1,1,7), (1,5,15), (3,4,-1), (4,1,-2), (4,6,21) )2. 链接存储链接存储 用链接结构存储三元组线性表用链接结构存储三元组线性表（1）带行指针向量

5、的链接存储）带行指针向量的链接存储 每一行的非每一行的非零元零元对应一个单链表对应一个单链表( (按列号次序按列号次序) )，用一维数组保存所有单链表的头指针用一维数组保存所有单链表的头指针。 7 0 0 0 15 0 0 0 0 0 0 0 -2 0 0 0 0 21 0 0 0 -1 0 0A=( (1,1,7), (1,5,15), (3,4,-1), (4,1,-2), (4,6,21) )12341 1 71 5 15 3 4 -1 4 1 -2 4 6 21 vectormnt465带行指针向量的链接存储结构（2）十字链接存储）十字链接存储 既带既带行指针向量，又带列指针向量，行指

6、针向量，又带列指针向量，每一个结点每一个结点同时位于两个单链表中同时位于两个单链表中。 7 0 0 0 15 0 0 0 0 0 0 0 -2 0 0 0 0 21 0 0 0 -1 0 0A=515 11-2 4621 41714-1 3col val right down row cvrv ( (1,1,7), (1,5,15), (3,4,-1), (4,1,-2), (4,6,21) )12345rowcolval M.sm:MaxTermsM.mM.nM.t000 1 2 . . .MaxRows.M.vectorM.mM.nM.t00012345rowcolval M.sm:Max

7、TermsM.mM.nM.t 1 2 . . .MaxRows.M.vectorM.mM.nM.t 7 0 0 0 15 0 0 0 0 0 0 0 -2 0 0 0 0 21 0 0 0 -1 0 0A=1234m.trowcolval1 171 51534 -141 -246 21sm:输出：输出：( (1,1,7), (1,5,15), (3,4,-1), (4,1,-2), (4,6,21) ) 7 0 0 0 15 0 0 0 0 0 0 0 -2 0 0 0 0 21 0 0 0 -1 0 0A=12345rowcolval1 171 51534 -141 -246 21sm:12

8、3451 171 4-243 -151 1564 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*66*4 12345rowcolval1 171 51534 -141 -246 211 171 4-243 -151 1564 2112345rowcolval i /S存放转置矩阵存放转置矩阵for (i=1; i=M.t; i+) num M.smi.col +; LMatrix Add(LMatrix M1, LMatrix M2) int k=0; /统计非零元个数统计非零元个数 Triple *p1, *p2, *

9、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; else if ( p1-val + p2-val = 0 ) p1=p1-next; p2=p2-next; continue; else *newptr=*p1; newptr-val+=p2-va

10、l; p1=p1-next; p2=p2-next; /以下插入以下插入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;

11、 k+; /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) 广义表广义表是线性表的推广。是线性表的推广。广义表广义表是是 n(n=0) n(n=0) 个数据元素个数据元素a a1 1, a, a2 2, , ， a an n 构成的有限序列，数构成的有限序列

12、，数据元素可以是单个元素（称为据元素可以是单个元素（称为单元素单元素），也可以是），也可以是广义表（称为广义表（称为子表子表或或表元素表元素）。）。广义表广义表是一种递归是一种递归的数据结构。的数据结构。 广义表广义表一般表示为一般表示为: : LS = ( a1, a2, ， an ) n n 称为称为广义表的广义表的长度长度，n=0 n=0 时称为时称为空表空表 表示法：表示法： 小写字母表示单元素，大写字母表示表元素小写字母表示单元素，大写字母表示表元素 A=( ) B=(d) C=(a, (b,c) D=(A,B,C)=( (), (d), (a,(b,c) ) A( ) B( d )

13、 C( a, (b,c) ) D( A(), B(d), C(a,(b,c) ) 表的表的深度深度指括号嵌套的最大次数。指括号嵌套的最大次数。 A A和和B B的深度为的深度为1 1，C C的深度为的深度为2 2，D D的深度为的深度为3 3。dabcdabcA BCD A BC A=NULL0 d 0 a 1 0 b 0 c BC1 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) )A1 B1 0 a 1 0 b 0 c C1 0 d 带

14、表头附加结点的链接结构带表头附加结点的链接结构A=( ) B=(d)C=(a, (b,c) D=(A,B,C)=( (), (d), (a,(b,c) ) 递归算法如下：递归算法如下：（也可用非递归算法）也可用非递归算法） int Length(GLNode *GL) O(n) （n为结点为结点数）数） if (GL!=NULL) return 1 + Length(GL-next); else return 0; 采用不带表头附加结点的链接结构采用不带表头附加结点的链接结构 递归算法如下递归算法如下：(深度为所有子表中的最大深度加深度为所有子表中的最大深度加1) int Depth(GLNo

15、de *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); 扫描每一个输入的字符，根据不同类型作不同扫描每一个输入的字符，根据不同类型作不同处理。若是空表（处理。若是空表（#），直接结束；若是单元素（字），直

16、接结束；若是单元素（字母），先建立新结点，再递归调用建立后续结点或母），先建立新结点，再递归调用建立后续结点或结束；若是子表（结束；若是子表（(），先递归调用建立子表，再），先递归调用建立子表，再递归调用建立后续结点或结束。递归调用建立后续结点或结束。void Create(GLNode *&GL) O(n)（n为读入的字符数）为读入的字符数） char ch; cinch / 只可能读入只可能读入 # 、 ( 及字母及字母 if (ch=#) GL=NULL; /建立空表建立空表 else if ( ch=( ) /递归构造子表递归构造子表 GL=new GLNode; GL-tag

17、=1; Create(GL-sublist); else /建立单元素结点建立单元素结点 GL=new GLNode; GL-tag=0; GL-data=ch; cinch; / 只可能读入只可能读入 , 、 ) 及及 ; if (GL!=NULL) if (ch=,) Create(GL-next); /递归构造后继表递归构造后继表 else if ( (ch=) | (ch=;) ) GL-next=NULL; MPrint: 输出广义表最外层的一对括号，调用输出广义表最外层的一对括号，调用Print 输出广义表其余内容。输出广义表其余内容。 Print: 先输出第一个元素（若是非空子表，则先输出第一个元素（若是非空子表，则递归调用输出），再递归调用输出后继表。递归调用输出），再递归调用输出后继表。 void MPrint(GLNode *G