第4章数组和广义表ppt课件.ppt

《第4章数组和广义表ppt课件.ppt》由会员分享，可在线阅读，更多相关《第4章数组和广义表ppt课件.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章第四章 数组和广义表数组和广义表数组的逻辑结构数组的逻辑结构一个二维数组的类型定义如下：一个二维数组的类型定义如下： 其中其中c,dc,d设为设为1 1，数组可表示为：，数组可表示为：A:arrayc.md.n of ElemTypeA=a11 a12 a1na21 a22 a2n am1 am2 amn 它可以看成是由它可以看成是由m m个行向量或个行向量或n n个列向量组成的线性表。即，二个列向量组成的线性表。即，二维数组可以看成是一种推广的线维数组可以看成是一种推广的线性表，这种线性表的每一个数据性表，这种线性表的每一个数据元素本身也是一个线性表。元素本身也是一个线性表。类似地，类

2、似地， 一个三维数组可以看成是数据元素为二维数组的线性表一个三维数组可以看成是数据元素为二维数组的线性表一个一个n维数组可视为其数据元素为维数组可视为其数据元素为n-1维数组的线性表。维数组的线性表。数组的顺序存储分配数组的顺序存储分配a1a2a3an-1anLoc(ai) = Loc(a1) + (i-1) kA1:n = ( a1, a2, a3, , an ) 若已知每个元素占若已知每个元素占k 个存储单元，并且知道第个存储单元，并且知道第一个元素的存储地址一个元素的存储地址Loc(a1), 则则一一. .一维数组一维数组A1:nA1:n a11 a12 a13 a1n a21 a22

3、a23 a2nA1:m 1:n = am1 am2 am3 amn 行序为主序分配方式行序为主序分配方式 列序为主序分配方式列序为主序分配方式二二. .二维数组二维数组A1:mA1:m1:n1:n a11 . . .a1na21. . .a2na31. . .aij. . .amn第第1行行第第2行行 a11 a12 a13 a1n a21 a22 a23 a2nA1:m 1:n = am1 am2 am3 amn 1. 行序为主序分配方式行序为主序分配方式 a11 a12 a13 a1n a21 a22 a23 a2n a31 a32 a33 a3nA1:m 1:n = aij am1 am

4、2 am3 amni-1 行行 若已知每个元素占若已知每个元素占k个存储单元，并且知道第一个存储单元，并且知道第一个元素的存储地址个元素的存储地址 LOC(a11), 则则 Loc(aij) = Loc(a11) + (i 1) n k + (j 1) k = Loc(a11) + (i 1) n+(j 1) ka11 . . .am1a12. . .am2a13. . .aij. . .amn第第1列列第第2列列 a11 a12 a13 a1n a21 a22 a23 a2nA1:m1:n= am1 am2 am3 amn 2. 列序为主序分配方式列序为主序分配方式 a11 a12 a13

5、a1n a21 a22 a23 a2n a31 a32 a33 a3nA1:m 1:n = aij am1 am2 am3 amnj-1 列列 若已知每个元素占若已知每个元素占k个存储单元，并且知道第一个存储单元，并且知道第一个元素的存储地址个元素的存储地址 LOC(a11), 则则 Loc(aij) = Loc(a11) + (j 1) m k + (i 1) k = Loc(a11) + (j 1) m+(i 1) k9 数组数组A0A0505066的每个元素占的每个元素占5 5个字节，将个字节，将其按列优先次序存储在起始地址为其按列优先次序存储在起始地址为10001000的内存的内存单元

6、中，则单元中，则A55A55的地址是（的地址是（ ）。）。 课堂练习课堂练习A 已知二维数组已知二维数组AmnAmn采用行序为主的方式存储，采用行序为主的方式存储，每个元素占每个元素占k k个存储单元，并且第一个元素的存个存储单元，并且第一个元素的存储地址是储地址是LOC(A00),LOC(A00),则则AijAij的地址的地址是是 。LOC(A00)+(i*n+j)*k a11 a12 a13 a1n a21 a22 a23 a2n m = am1 am2 am3 amn A 1:m 1:n 所谓所谓压缩存储压缩存储是指为多个值相同的元素是指为多个值相同的元素, 或者或者位置分布有规律的那些

7、元素分配尽可能少的存储空位置分布有规律的那些元素分配尽可能少的存储空间，而对间，而对0元素一般情况下不分配存储空间。元素一般情况下不分配存储空间。传统做法传统做法矩阵的压缩存储矩阵的压缩存储 a11 a12 a13 a1n a21 a22 a23 a2n a31 a32 a33 a3nA1:n 1:n = an1 an2 an3 ann传统做法：传统做法： 定义一个二维数组定义一个二维数组 A 1:n, 1:n 一一. . 对称矩阵的压缩存储对称矩阵的压缩存储 一个一个n 阶矩阵阶矩阵A的元素满足性质的元素满足性质 aij = aji 1i, jn则称则称矩阵矩阵A为为n 阶对称矩阵。阶对称矩

8、阵。a11a21a22. .aij. .ann 1 2 3 1 2 3 . . n n* *(n+1)/2 (n+1)/2 a11 a12 a13 a1n a21 a22 a23 a2n a31 a32 a33 a3nA1:n 1:n = an1 an2 an3 annV只存储下三角元素时寻址公式为： loc(Aij)=loc (A11)+i(i-1)/2 +j-1*k传统做法：定义一个二维数组传统做法：定义一个二维数组 B 1:n 1:n 0元素元素0元素元素二二. . 对角矩阵的压缩存储对角矩阵的压缩存储 若一个矩阵中，值非若一个矩阵中，值非0的元素对称地集中在主对的元素对称地集中在主对角

9、线两旁的一个带状区域中角线两旁的一个带状区域中(该区域之外的元素都为该区域之外的元素都为0元素元素)，称这样的矩阵为对角矩阵。，称这样的矩阵为对角矩阵。例例. . 三对角矩阵的压缩存储三对角矩阵的压缩存储 b11 b12 b21 b22 b23 b32 b33 b34 bn-1n bnn-1 bnn0元素元素0元素元素非零元素的个数为非零元素的个数为3 3（n-2n-2）+4+4B1:n 1:n =b11b12b21 bij . . b22. . 1 2 3 4 . . 3n-2 bnn b11 b12 b21 b22 b23 b32 b33 b34 bn-1n bnn-1 bn n0元素元素

10、0元素元素B1:n 1:n =对角线数组中某元素寻址公式为： loc(Aij)=loc (A11)+ 2(i-1)+j-1*k传统做法：定义一个二维数组传统做法：定义一个二维数组 A 1:6 1:6 一一. 什么是稀疏矩阵什么是稀疏矩阵? 一个较大的矩阵中，零元素的个数相对于整一个较大的矩阵中，零元素的个数相对于整 个矩阵元素的总个数所占比例较大时，可以称该个矩阵元素的总个数所占比例较大时，可以称该 矩阵为一个稀疏矩阵。矩阵为一个稀疏矩阵。 M = 15 0 0 22 0 -15 0 11 3 0 0 0 0 0 0 -6 0 0 0 0 0 0 0 0 91 0 0 0 0 0 0 0 28

11、 0 0 0稀疏矩阵稀疏矩阵三元组三元组： ( i, j, value )例如例如 ： （1,1,15）表示第）表示第1行、第行、第1列、值为列、值为15的元素。的元素。（1,4,22）表示第）表示第1行、第行、第4 4列、值为列、值为22的元素。的元素。（1,6,-15）表示第）表示第1行、第行、第6列、值为列、值为-15的元素。的元素。 15 0 0 22 0 -15 0 11 3 0 0 0 0 0 0 -6 0 0 0 0 0 0 0 0 91 0 0 0 0 0 0 0 28 0 0 0二二. 稀疏矩阵的三元组表示稀疏矩阵的三元组表示( m, n, t ) 其中，其中，m, n, t

12、 分别表示稀疏矩阵的总的行数、分别表示稀疏矩阵的总的行数、总的列数与非零元素的总个数。总的列数与非零元素的总个数。 若一个若一个m n阶稀疏矩阵具有阶稀疏矩阵具有t个非零元素，则个非零元素，则用用t+1个三元组来存储个三元组来存储, ,其中第一个三元组分别用来其中第一个三元组分别用来给出稀疏矩阵的总行数给出稀疏矩阵的总行数m、总列数、总列数n 以及非零元素以及非零元素的总个数的总个数t ；第二个三元组到第；第二个三元组到第 t+1 个三元组按行个三元组按行序为主序的方式依次存储序为主序的方式依次存储t 个非零元素。个非零元素。 M= 15 0 0 22 0 -15 0 11 3 0 0 0 0

13、 0 0 -6 0 0 0 0 0 0 0 0 91 0 0 0 0 0 0 0 28 0 0 0 M 1:61:6 6681115142216-15221134-623351916328 A=A 1:9 1:3 三元组三元组： ( i j value )15 0 0 22 0 -1515 0 0 22 0 -15 0 11 3 0 0 0 0 11 3 0 0 0 0 0 0 -6 0 0 0 0 0 -6 0 0 0 0 0 0 0 0 0 0 0 0 0 091 0 0 0 0 091 0 0 0 0 0 0 0 28 0 0 00 0 28 0 0 0M= 15 0 0 0 91 01

14、5 0 0 0 91 0 0 11 0 0 0 0 0 11 0 0 0 0 0 3 0 0 0 28 0 3 0 0 0 28 22 0 -6 0 0 0 22 0 -6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0-15 0 0 0 0 0-15 0 0 0 0 0N=表示稀疏矩阵表示稀疏矩阵M的三列的二维数组的三列的二维数组 1 2 31 2 3A0 6 6 8A0 6 6 8A1 1 1 15A1 1 1 15A2 1 4 22A2 1 4 22A3 1 6 -15A3 1 6 -15A4 2 2 11A4 2 2 11A5 2 3 3A5 2 3 3A6 3 4 -6A

15、6 3 4 -6A7 5 1 91A7 5 1 91A8 6 3 28A8 6 3 28 1 2 31 2 3B0 6 6 8B0 6 6 8B1 1 1 15B1 1 1 15B2 1 5 91B2 1 5 91B3 2 2 11B3 2 2 11B4 3 2 3B4 3 2 3B5 3 6 28B5 3 6 28B6 4 1 22B6 4 1 22B7 4 3 -6B7 4 3 -6B8 6 1 -15B8 6 1 -15表示稀疏矩阵表示稀疏矩阵N的三列的二维数组的三列的二维数组A=B=三三. 矩阵的转置矩阵的转置1)1)转置过程按照转置过程按照B B数组中元素的最终排列顺序进行数组中元素

16、的最终排列顺序进行 由于矩阵由于矩阵M的列经过转置后变为的列经过转置后变为N的行的行,所以可以按照所以可以按照M的列序来转置。为了按顺序的列序来转置。为了按顺序找到找到M中的每一列的所有非中的每一列的所有非0元素元素,对数组对数组A从从第一行起将每行的第二列扫描第一行起将每行的第二列扫描n遍遍,每遍扫描每遍扫描分别找到矩阵分别找到矩阵N的从第一行到第的从第一行到第n行的各行所行的各行所有非有非0元素元素,并产生并产生B数组相应的行。数组相应的行。算法算法 void transmat(A,B); (m,n,t)=(A0,1,A0,2,A0,3); (B0,1, B0,2,B0,3)=(n,m,t

17、); if(t!=0) q=1; for(col=1;col=n;col+) for(p=1;p=t;p+) if(Ap2=col) Bq1=Ap2; Bq2=Ap1; Bq3=Ap3; q+; 1 2 31 2 3A0 6 6 8A0 6 6 8A1 1 1 15A1 1 1 15A2 1 4 22A2 1 4 22A3 1 6 -15A3 1 6 -15A4 2 2 11A4 2 2 11A5 2 3 3A5 2 3 3A6 3 4 -6A6 3 4 -6A7 5 1 91A7 5 1 91A8 6 3 28A8 6 3 282)B2)B数组中元素的生成不是顺序的而是跳跃式的数组中元素的生

18、成不是顺序的而是跳跃式的 即转换按数组即转换按数组A A中行的顺序进行，但转换后的元素在中行的顺序进行，但转换后的元素在B B中中不是连续存放，而是将它放入它在不是连续存放，而是将它放入它在B B中最终应占据的位置。中最终应占据的位置。设：设：Num1.n:存放矩阵存放矩阵m中各列非中各列非0元素的个数元素的个数; Pot1.n:存放矩阵存放矩阵m中各列第一个非中各列第一个非0元素在数组元素在数组B中应占中应占 的位置。的位置。pot1=1pot1=1potj=potj-1+numj-1 (2jn)potj=potj-1+numj-1 (2jn)15 0 0 22 0 -1515 0 0 22

19、 0 -15 0 11 3 0 0 0 0 11 3 0 0 0 0 0 0 -6 0 0 0 0 0 -6 0 0 0 0 0 0 0 0 0 0 0 0 0 091 0 0 0 0 091 0 0 0 0 0 0 0 28 0 0 0 0 0 28 0 0 0M= j 1 2 3 4 5 6 Numj 2 1 2 2 0 1 Potj 1 3 4 6 8 8void fasttranspo(A,B) (m,n,t)=(A01,A02,A03); (B01,B02,B03)=(n,m,t); if (t!=0) for (j=1;j=n;j+) numj=0; for (i=1;i=t;i+

20、) numAi,2=numAi,2+1; pot1=1; for (j=2;j=n;j+) potj=potj-1+numj-1; for (i=1;i=t;i+) k=Ai2; Bpotk1=Ai2; Bpotk2=Ai1; Bpotk3=Ai3; potk= potk+1; 1 2 3 1 2 3A0 6 6 8A0 6 6 8A1 1 1 15A1 1 1 15A2 1 4 22A2 1 4 22A3 1 6 -15A3 1 6 -15A4 2 2 11A4 2 2 11A5 2 3 3A5 2 3 3A6 3 4 -6A6 3 4 -6A7 5 1 91A7 5 1 91A8 6 3

21、28A8 6 3 28四四. 矩阵的相乘矩阵的相乘3 0 0 50 -1 0 02 0 0 0S=0 21 0-2 00 43 4 41 1 31 4 52 2 -13 1 2A=B=4 2 41 2 22 1 13 1 -24 2 4 由于两个稀疏矩阵的积并不一定仍是稀疏矩阵，故结果由于两个稀疏矩阵的积并不一定仍是稀疏矩阵，故结果矩阵矩阵c=sc=s* *r r仍需采用通常的矩形结构的二维数组存储方式。仍需采用通常的矩形结构的二维数组存储方式。m*nR=R=n*pB=Procedure matrix-multiplication(A,B,C);Begin (m,n,t1):=(A0,1,A0

22、,2,A0,3); if n=B0,1 then (p,t2):=(B0,2,B0,3) else Write(Incompatible matrix);exit; if t1*t2=0 then exit; 乘积为乘积为0矩阵矩阵 for i:=1 to m do for j:=1 to p do Ci,j:=0; for i:=1 to n do numi:=0; for i:=1 to t2 do numBi,1:=numBi,1+1; pot1:=1; for i:=2 to n+1 do poti:=poti-1+numi-1; for i:=1 to t1 do k:=ai,2;

23、for j:=potk to potk+1-1 do CAi,1,Bj,2:=CAi,1,Bj,2+Ai,3*Bj,3;End; 在经典算法中，不管元素是否为在经典算法中，不管元素是否为0都需要相乘，但实际上都需要相乘，但实际上只有只有Si,k和和Rk,j均不为均不为0时，乘积才不为时，乘积才不为0。因此，需在。因此，需在A、B中找出相应的各对元素中找出相应的各对元素(即数组即数组A中第二列的值与数组中第二列的值与数组B中第中第一列的值相等的元素一列的值相等的元素)相乘即可。相乘即可。 为了得到非为了得到非0的乘积，对的乘积，对A中每一行的元素中每一行的元素(i,k,Sik)，需要，需要在在B

24、中找到所有相应的元素中找到所有相应的元素(k,j,Rkj),为了便于在为了便于在B中寻找中寻找R中第中第k行的第一个非行的第一个非0元素，和前面类似，需设置两个数组元素，和前面类似，需设置两个数组Num1:n和和Pot1:n，其中，其中numk表示表示R中第中第k行非行非0元素的个数；元素的个数；potk表示表示R中第中第k行第一个非行第一个非0元素在元素在B中的位置。中的位置。pot1=1pot1=1potj=potj-1+numj-1 (2jn)potj=potj-1+numj-1 (2jn)下面我们就给出矩阵乘法的算法矩阵乘法的算法：void matrx-multiplication(A

25、,B,C) (m,n,t1)=(A01,A02,A03); if (n=B01) (p,t2)=(B02,B03); else printf(“%s”,”incompatible matrices”); exit(1);/矩阵不相容，不必做，退出矩阵不相容，不必做，退出 if (t1*t2=0) exit(1);/矩阵为零矩阵，不必做，退出矩阵为零矩阵，不必做，退出for (i=1;i=m;i+) for (j=1;j=p;j+) Cij=0;/结果矩阵初始化结果矩阵初始化for (i=1;i=n;i+) numi=0; for (i=1;i=t2;i+) numBi1= numBi1+1;p

26、ot1=1; for (i=2;i=n+1;i+) poti=poti-1+numi-1;for (i=1;i=t1;i+) k=ai2; for (j=potk;j=potk+1-1;j+) CAi1Bj2=CAi1Bj2+Ai3*Bj3 即即:0 26-1 00 4C=为便于理解上述算法，说明如下：为便于理解上述算法，说明如下： 因为因为PotkPotk表示了表示了R R的第的第k k行中第一个非零元素在行中第一个非零元素在B B中的位置（行数），故中的位置（行数），故potk+1-1potk+1-1就表示了第就表示了第k k行中行中最后一个非零元素在最后一个非零元素在B B中的行数。为了

27、正确表示出中的行数。为了正确表示出中的第中的第n n行中的最后一个非零元素在行中的最后一个非零元素在B B中的位置，故在中的位置，故在数组数组potpot中增加了一个元素中增加了一个元素 potn+1potn+1，且令，且令potn+1=potn+numnpotn+1=potn+numn 此算法存储量的占用为：此算法存储量的占用为： O(3O(3* *(t(t1 1+t+t2 2)+2)+2* *n+mn+m* *p)p) 对于时间的复杂性对于时间的复杂性, ,若认为矩阵若认为矩阵R R每行中均为每行中均为p p个非零元素个非零元素, ,则开销为则开销为O(t1O(t1* *p),p),故当故

28、当t1mt1crow IF rrowcrow THEN last.right:=hdncrow; THEN last.right:=hdncrow; crow:=rrow; crow:=rrow; last:=hdncrow last:=hdncrow newl(x); x.row:=rrow; newl(x); x.row:=rrow; x.col:=ccol; x.col:=ccol; x.val:=val; x.val:=val; last.right:=x; last:=x; last.right:=x; last:=x; (hdncool.Val).down:=x; (hdncool

29、.Val).down:=x; hdnccol.val:=x hdnccol.val:=x IF t0 THEN last.right:=hdnrrow; IF t0 THEN last.right:=hdnrrow; FOR i:=1 TO p DO FOR i:=1 TO p DO hdni.val).down:=hdni; hdni.val).down:=hdni; newl(A);A.row:=m;A.col:=n; HA:=A; newl(A);A.row:=m;A.col:=n; HA:=A; FOR i:=1 TO p-1 DO FOR i:=1 TO p-1 DO hdni.va

30、l:=hdni+1; hdni.val:=hdni+1; IF p=0 THEN HA.val:=HA; IF p=0 THEN HA.val:=HA; ELSE hdnp.val:=ha; ELSE hdnp.val:=ha; ha.val:=hdn1 ha.val:=hdn1 END; END;void Mread(A) scanf(“%d,%d,%d”,m,n,t); p=max(m,n); for (i=1;irow=x-col=0; x-right=x-val=x; crow=1;last=hdn1; for (i=1;icrow ) last-right=hdncrow; crow

31、=rrow;last=hdncrow; x=new orthogonalNode; x-row=rrow; x-col=ccol; x-val=val; last-right=x; last=x; (hdncool-val)-down=x;/建立列链建立列链 hdncool-val=x;/追踪当前列链表的最下面一个结点追踪当前列链表的最下面一个结点 if (t!=0) last-right=hdnrrow; for (i=1;ival)-down=hdni; A=new orthogonalNode; A-row=m; A-col=n;HA=A; for (i=1;ival=hdni+1; i

32、f (p=0) HA-val=HA; Else hdnp-val=HA;HA-val=hdn1; 容易看出上述算法的时间复杂性为容易看出上述算法的时间复杂性为O(p+t)=O(m+n+t)O(p+t)=O(m+n+t)，如，如果用矩形结构的二维数组存储矩阵时果用矩形结构的二维数组存储矩阵时, ,则所需时间为则所需时间为O(mO(m* *n)n)。因此，当非零元素个数因此，当非零元素个数t t比比m m* *n n小得多时用小得多时用MreadMread算法存储稀疏算法存储稀疏矩阵比用经典方法要快。矩阵比用经典方法要快。Aij=( (i) ) aij+bij( (ii) ) aij ( (bij

33、 =0) )( (iii) ) bij ( (aij =0) ) 紧接着需要讨论的问题是，在这种存储结构中，如何实现紧接着需要讨论的问题是，在这种存储结构中，如何实现矩阵的运算。最简单的运算是两个矩阵的运算。最简单的运算是两个m m* *n n矩阵相加。设矩阵相加。设A A，B B是两个是两个用十字链表存储的稀疏矩阵，我们讨论用十字链表存储的稀疏矩阵，我们讨论A:=A+BA:=A+B的运算，为区别的运算，为区别和式和式A A与被加数与被加数A A写为写为A=A+BA=A+B，相加后不外乎这三种情况：，相加后不外乎这三种情况： 当将当将B B加到加到A A上去时，对上去时，对A A矩阵的十字链表

34、来说，或者是改矩阵的十字链表来说，或者是改变结点的变结点的ValVal域值（域值（aij+bij 0）, ,或者是不变（当或者是不变（当bij = 0时）或时）或者是插入一个新结点（当者是插入一个新结点（当aij=0时），还可能是删除一个结点时），还可能是删除一个结点（当（当aij+bij=0时）。时）。 整个运算可从矩阵的第一行开始，一行一行的进行，一直整个运算可从矩阵的第一行开始，一行一行的进行，一直到到m行。对任何一行都从表头结点出发找到各自的第一个结点行。对任何一行都从表头结点出发找到各自的第一个结点开始进行比较，为了便于插入和删除结点，需设以下开始进行比较，为了便于插入和删除结点，需

35、设以下4组指针：组指针： (1)(1) ha，hb 分别表示矩阵分别表示矩阵A和和B的十字链表的头指针；的十字链表的头指针； (2)(2) Ca，Cb 分别指向分别指向A和和B的行链表的表头结点的指针；的行链表的表头结点的指针； (3)(3) Pa，Pb 分别指向分别指向A和和B的同一行上的两个结点，这两的同一行上的两个结点，这两 个指针将指向各非零元素；个指针将指向各非零元素； (4)(4) qa指示指示Pa所指结点的行的前趋结点，为删除插入服务。所指结点的行的前趋结点，为删除插入服务。 hlj指示指示A矩阵中每一列的指针，初值指向每一列的列矩阵中每一列的指针，初值指向每一列的列 链表的表头

36、结点，以便在某行链表的表头结点，以便在某行j列上插入或删除列上插入或删除 某一结点时，让某一结点时，让hlj指向这一列的上一个结点。指向这一列的上一个结点。 (1)(1)由由CaCa，CbCb确定确定PaPa，PbPb，分别指向，分别指向A A和和B B链表中第一行第链表中第一行第一个非零元素。一个非零元素。pa=Ca-right pa=Ca-right ；p=Cb-right p=Cb-right ；若；若B B中该行中该行中无非零元素（即中无非零元素（即Pb-Col=0Pb-Col=0） 则令则令CaCa，CbCb指针下移，指向指针下移，指向下一行（即下一行（即Ca=Ca-valCa=Ca

37、-val；Cb=Cb-valCb=Cb-val）。）。下面将矩阵下面将矩阵B B加到矩阵加到矩阵A A上去的运算过程大致描述如下：上去的运算过程大致描述如下： 刚开始由刚开始由haha，hbhb确定确定CaCa，CbCb： Ca=ha-val; Cb=hb-val;Ca=ha-val; Cb=hb-val; (2)(2)否则，比较这两个结点进行相加，这时可能有上述所说否则，比较这两个结点进行相加，这时可能有上述所说的三种情况：的三种情况： 若若Pa-colcol,Pa-colcol,且且pa-col0pa-col0（不是表头结点）（不是表头结点） 则令则令papa指向本行的下一个结点即指向本行

38、的下一个结点即: : qa=pa; pa=pa-right qa=pa; pa=pa-right；并重新加以比较。；并重新加以比较。若若pa-colpb-col pa-colpb-col 或或pa-col=0(Apa-col=0(A在该行无非零元素，在该行无非零元素，B B 相应行有非零元素相应行有非零元素) ) 则将则将B B中相应结点插入中相应结点插入A A中，设新结点为中，设新结点为P P： qa-right=pqa-right=p； p-right=pa;p-right=pa; 修改修改A A中的列指针，首先需找到同一列中上一个结点，然中的列指针，首先需找到同一列中上一个结点，然后令后

39、令hljhlj指向该结点。于是指向该结点。于是A A的列表指针改为：的列表指针改为：P-down=hlj-down;hlj-down=P;Pb=Pb-right;P-down=hlj-down;hlj-down=P;Pb=Pb-right;若若pa-col=pb-col,pa-col=pb-col,则则pa-val=pa-val+pb-valpa-val=pa-val+pb-val； 若若pa-val!=0pa-val!=0，则，则qa=Pa;Pa=Pa-right;Pb=Pb-rightqa=Pa;Pa=Pa-right;Pb=Pb-right ( (为下一次比较做准备为下一次比较做准备)

40、) 若若pa-val=0pa-val=0，则删除，则删除A A中该结点：中该结点：Qa-right =Pa-right; hlj-down=Pa-down;Qa-right =Pa-right; hlj-down=Pa-down;然后然后Pa=qa-right; Pb=Pb-right;(Pa=qa-right; Pb=Pb-right;(为下一次比较做准备为下一次比较做准备) ) (3)(3)重复步骤重复步骤(2)(2)，直到，直到B B的同一行中没有非零元素为止的同一行中没有非零元素为止( (即即Pb.Col=0Pb.Col=0到表头结点了到表头结点了) )，然后转向下一行。以此类推直到，

41、然后转向下一行。以此类推直到m m行行都进行完为止。此时都进行完为止。此时CaCa，CbCb分别又指向十字链表的头结点，即分别又指向十字链表的头结点，即Ca-row!=0; Cb-row!=0(Ca-row!=0; Cb-row!=0(因为因为Cb-row0Cb-row0表示是行链表的表表示是行链表的表头结点头结点) ) 上述算法的整个运算过程在于对上述算法的整个运算过程在于对A A和和B B的十字链表逐行扫描，的十字链表逐行扫描，其循环次数主要取决于其循环次数主要取决于A A和和B B矩阵中非零元素的个数矩阵中非零元素的个数tata和和tb, tb, 因因此此算法的时间复杂度为此此算法的时间

42、复杂度为O O（ta+tbta+tb）。）。 这一节的最后，我们来看看如何把用十字链表表示的稀这一节的最后，我们来看看如何把用十字链表表示的稀疏矩阵的所有结点还给可利用空间栈。这里假设可用空间栈疏矩阵的所有结点还给可利用空间栈。这里假设可用空间栈是通过是通过rightright域链接起来的单链表，表头指针为域链接起来的单链表，表头指针为avav，其归还，其归还算法并不复杂，直接用类算法并不复杂，直接用类C C语言描述如下：语言描述如下：void Merase(ha);/将以将以ha为表头指针的十字链表的全部结点归还给为表头指针的十字链表的全部结点归还给av栈栈next=ha-val; /记下第

43、一行行链表表头结点记下第一行行链表表头结点 ha-right=av; av=ha; while(nextha) t=next-right; next-right=av; av=t; next=next-val; 广义表广义表 若若ai 为不可再分割的原子元素，为不可再分割的原子元素， 则称则称ai 为为原子元素原子元素；若若ai 为一个子表，则称为一个子表，则称ai 为为表元素表元素。 用小写字母表示原子用小写字母表示原子元素，用大写字母表示表元素。元素，用大写字母表示表元素。一一. . 广义表的基本概念广义表的基本概念广义表是一个长度广义表是一个长度n0 的有限序列。记作的有限序列。记作LS

44、 = ( a1, a2, , an-1, an )其中，其中，LSLS为广义表的名字为广义表的名字, , a ai i为表中元素；为表中元素； a ai i 可以是可以是原子元素，也可以是一个子表。原子元素，也可以是一个子表。n n 为表的长为表的长 度，长度，长度为度为0 0 的表称为空表。当广义表非空时，称第一个元素的表称为空表。当广义表非空时，称第一个元素a a1 1为广义表的表头为广义表的表头(Head)(Head)，称其余元素组成的表，称其余元素组成的表(a(a2 2, , , a, an-1n-1, a, an n) )是广义表的表尾（是广义表的表尾（Tail)Tail)。 表的深

45、度是指表中所包含的括号的层数。表的深度是指表中所包含的括号的层数。A=( ); ; 长度为长度为0的空表。的空表。B=( ); 是以空表作为唯一元素的表，长度为是以空表作为唯一元素的表，长度为1。C=(a,b);有两个元素有两个元素a,b长度为长度为2。D=(a, (b,c) ; ; 含有一个原子元素和一广义表，长度为含有一个原子元素和一广义表，长度为2。E=(x, D, y) ; ; 长度为长度为3的广义表。的广义表。F=(a, F); 长度为长度为2的递归的广义表。的递归的广义表。 广义表的例子：广义表的例子：ababcxyabcaCDEDF表元素表元素原子元素原子元素 3.3.列表可以是

46、一个递归的表，即列表可以是一个递归的表，即列表可以是本身的一个子表。列表可以是本身的一个子表。 2.2.列表可以为其他表所共享。列表可以为其他表所共享。 1.1.列表的元素可以是子表列表的元素可以是子表, ,而子表而子表的元素还可以是子表的元素还可以是子表, ,。结论结论求下列广义表的运算结果：求下列广义表的运算结果：1.Head(p,w,h)1.Head(p,w,h)2.tail(b,k,p,h)2.tail(b,k,p,h)3.Head(a,b),(c,d)3.Head(a,b),(c,d)4.tail(a,b),(c,d)4.tail(a,b),(c,d)5.tail(Head(a,b)

47、,(c,d)5.tail(Head(a,b),(c,d)课堂练习课堂练习二二. . 广义表的链接表示法广义表的链接表示法tagdatalink其中，其中，tag为标志位为标志位, 令令 1 表示本结点为表结点表示本结点为表结点 0 表示本结点为原子结点表示本结点为原子结点当当tag=0时时, data域存放相应原子元素的信息域存放相应原子元素的信息；当当tag=1时，时，data域存放子表第一个元素对应的链结点的地址；域存放子表第一个元素对应的链结点的地址； link域存放本元素同一层的下一个元素所在链接点的地址，域存放本元素同一层的下一个元素所在链接点的地址， 当本元素为所在层的最后一个元素

48、时，当本元素为所在层的最后一个元素时，link域为域为Null。flag=广义表一般采用链式存储结构，链结点的构造可以为广义表一般采用链式存储结构，链结点的构造可以为A=( )B=( )1BC=(a,b)0a0bD=(a, (b,c)C0aD0b0c1E=(x, D, y)0 xE10yF=(a, F)0aF1A=NULL多元多项式的广义表表示多元多项式的广义表表示P(x,y,z) = x10y3z2+2x8y3z2+3x8y2z2+x4y4z+6x2y4z+2yz = (x10+2x8)y3+3x8y2)z2+(x4+6x2)y4+2y)zP(z) = Az2+BzA(x,y) = (x10

49、+2x8)y3+3x8y2B(x,y) = (x4+6x2)y4+2yA(y) = Cy3+Dy2B(y) = Ey4+FyC(x) = x10+2x8D(x) = 3x8E(x) = x4+6x2F(x) = 2x0coef exp link若链结点的构造设计为若链结点的构造设计为其中其中, ,coef 表示多项式的某一项的系数表示多项式的某一项的系数, ,或指向其系数子表或指向其系数子表 exp 表示多项式的某一项的指数表示多项式的某一项的指数 link 为链接多项式中同一层各链结点的指针为链接多项式中同一层各链结点的指针相当于相当于data域域P(x,y,z) = x10y3z2+2x8y3z2+3x8y2z2+x4y4z+6x2y4z+2yz = (x10+2x8)y3+3x8y2)z2+(x4+6x2)y4+2y)z该多项式的广义表的表示形式为：该多项式的广义表的表示形式为：Pz21y32 y4x3 8 1 6 2 1 4x1 102 8 xx2 0