《第4章数组和广义表ppt课件.ppt》由会员分享，可在线阅读，更多相关《第4章数组和广义表ppt课件.ppt（55页珍藏版）》请在三一办公上搜索。
1、数组的逻辑结构,一个二维数组的类型定义如下：,其中c,d设为1，数组可表示为：,A:arrayc.md.n of ElemType,它可以看成是由m个行向量或n个列向量组成的线性表。即，二维数组可以看成是一种推广的线性表，这种线性表的每一个数据元素本身也是一个线性表。,类似地，一个三维数组可以看成是数据元素为二维数组的线性表一个n维数组可视为其数据元素为n-1维数组的线性表。,数组的顺序存储分配,a1,a2,a3,an-1,an,Loc(ai)=Loc(a1)+(i-1)k,A1:n=(a1,a2,a3,an),若已知每个元素占k 个存储单元，并且知道第一个元素的存储地址Loc(a1),则,a
2、11 a12 a13 a1n a21 a22 a23 a2nA1:m 1:n=am1 am2 am3 amn,a11,.,a1n,a21,.,a2n,a31,.,aij,.,amn,a11 a12 a13 a1n a21 a22 a23 a2nA1:m 1:n=am1 am2 am3 amn,a11 a12 a13 a1n a21 a22 a23 a2n a31 a32 a33 a3nA1:m 1:n=aij am1 am2 am3 amn,i-1 行,Loc(aij)=Loc(a11)+(i1)nk+(j1)k,=Loc(a11)+(i1)n+(j1)k,a11,.,am1,a12,.,am
3、2,a13,.,aij,.,amn,a11 a12 a13 a1n a21 a22 a23 a2nA1:m1:n=am1 am2 am3 amn,a11 a12 a13 a1n a21 a22 a23 a2n a31 a32 a33 a3nA1:m 1:n=aij am1 am2 am3 amn,j-1 列,Loc(aij)=Loc(a11)+(j1)mk+(i1)k,=Loc(a11)+(j1)m+(i1)k,9,数组A0506的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则A55的地址是（）。.1175.1180.1205.1210,A,已知二维数组Amn采用
4、行序为主的方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A00),则Aij的地址是。,LOC(A00)+(i*n+j)*k,a11 a12 a13 a1n a21 a22 a23 a2n m=am1 am2 am3 amn,A 1:m 1:n,矩阵的压缩存储,a11 a12 a13 a1n a21 a22 a23 a2n a31 a32 a33 a3nA1:n 1:n=an1 an2 an3 ann,传统做法：定义一个二维数组 A 1:n,1:n,a11,a21,a22,.,aij,.,ann,1 2 3.n*(n+1)/2,a11 a12 a13 a1n a21 a22
5、 a23 a2n a31 a32 a33 a3nA1:n 1:n=an1 an2 an3 ann,V,只存储下三角元素时寻址公式为：loc(Aij)=loc(A11)+i(i-1)/2+j-1*k,传统做法：定义一个二维数组 B 1:n 1:n,0元素,0元素,例.三对角矩阵的压缩存储,b11 b12 b21 b22 b23 b32 b33 b34 bn-1n bnn-1 bnn,0元素,B1:n 1:n=,b11 b12 b21 b22 b23 b32 b33 b34 bn-1n bnn-1 bn n,B1:n 1:n=,对角线数组中某元素寻址公式为：loc(Aij)=loc(A11)+2(
6、i-1)+j-1*k,传统做法：定义一个二维数组 A 1:6 1:6,一个较大的矩阵中，零元素的个数相对于整 个矩阵元素的总个数所占比例较大时，可以称该 矩阵为一个稀疏矩阵。,稀疏矩阵,三元组：(i,j,value),例如：（1,1,15）表示第1行、第1列、值为15的元素。,（1,4,22）表示第1行、第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 分别表示稀疏矩阵的总
7、的行数、总的列数与非零元素的总个数。,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 0 0 0,M 1:61:6,6,6,8,1,1,15,1,4,22,1,6,-15,2,2,11,3,4,-6,2,3,3,5,1,91,6,3,28,A=,A 1:9 1:3,三元组：(i j value),M=,15 0 0 0 91 0 0 11 0 0 0 0 0 3 0 0 0 28 22 0-6 0 0 0 0 0 0 0 0 0-15 0 0 0 0 0,N=,表示稀疏矩阵M的三列的二维数组,
8、1 2 3A0 6 6 8A1 1 1 15A2 1 4 22A3 1 6-15A4 2 2 11A5 2 3 3A6 3 4-6A7 5 1 91A8 6 3 28,1 2 3B0 6 6 8B1 1 1 15B2 1 5 91B3 2 2 11B4 3 2 3B5 3 6 28B6 4 1 22B7 4 3-6B8 6 1-15,表示稀疏矩阵N的三列的二维数组,A=,B=,1)转置过程按照B数组中元素的最终排列顺序进行,由于矩阵M的列经过转置后变为N的行,所以可以按照M的列序来转置。为了按顺序找到M中的每一列的所有非0元素,对数组A从第一行起将每行的第二列扫描n遍,每遍扫描分别找到矩阵N的
9、从第一行到第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);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 3A0 6 6 8A1 1 1 15A2 1 4 22A3 1 6-15A4 2 2 11A5 2 3 3A6 3 4-6A7 5 1 91A8 6 3 28,2)B数组中元素的生成不是顺序的而是跳跃式的,即转换按数组A
10、中行的顺序进行，但转换后的元素在B中不是连续存放，而是将它放入它在B中最终应占据的位置。,设：Num1.n:存放矩阵m中各列非0元素的个数;Pot1.n:存放矩阵m中各列第一个非0元素在数组B中应占 的位置。,M=,j 1 2 3 4 5 6 Numj 2 1 2 2 0 1 Potj 1 3 4 6 8 8,void 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+)numAi,2=numAi,2+1;,pot1=1;,for(j
11、=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 3A0 6 6 8A1 1 1 15A2 1 4 22A3 1 6-15A4 2 2 11A5 2 3 3A6 3 4-6A7 5 1 91A8 6 3 28,0 21 0-2 00 4,由于两个稀疏矩阵的积并不一定仍是稀疏矩阵，故结果矩阵c=s*r仍需采用通常的矩形结构的二维数组存储方式。,m*n,B=,Procedure matrix-multiplication(A,B,C);Begin(
12、m,n,t1):=(A0,1,A0,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
13、:=ai,2;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中找到所有相应的元素(k,j,Rkj),为了便于在B中寻找R中第k行的第一个非0元素，和前面类似，需设置两个数组Num1:n和Pot1:n，其中numk表示R中第k行非0元素的个数；potk
14、表示R中第k行第一个非0元素在B中的位置。,下面我们就给出矩阵乘法的算法：,void matrx-multiplication(A,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+
15、)numBi1=numBi1+1;,pot1=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,即:,为便于理解上述算法，说明如下：因为Potk表示了R的第k行中第一个非零元素在B中的位置（行数），故potk+1-1就表示了第k行中最后一个非零元素在B中的行数。为了正确表示出中的第n行中的最后一个非零元素在B中的位置，故在数组pot中增加了一个元素 potn+1，且令potn+1=potn+numn,此算法存储量的占用为：O
16、(3*(t1+t2)+2*n+m*p)对于时间的复杂性,若认为矩阵R每行中均为p个非零元素,则开销为O(t1*p),故当t1m*n时,该算法比经典算法要快些,在最坏情况下,即t1=O(m*n)时,时间开销变成O(m*n*p),与经典算法相当,但其存储开销也将上升很快,所以,此算法也只适用于稀疏矩阵。如果算法得到的结果矩阵C仍是稀疏矩阵,并且它将继续参加运算,则可再把它变成三列的二维数组压缩存储形式。,算法分析：执行时间为:O（t1*p）其最坏情况下为O(m*n*p)空间为：O(3*t1+t2)+2n+m*p,用十字链表表示稀疏矩阵,在链表中，稀疏矩阵的每个非零元素对应一个含有五个域的 结点，它
17、们分别是 row:行域表示非零元素所在行 col:列域表示非零元素所在列 val:值域表示非零元素值 down:向下域,用以链接同一列中下一个非0元素 right:向右域,用以链接同一行中下一个非0元素 结点结构如下图所示。,在十字链表中将稀疏矩阵每一行的非零元素通过right域链接成一个带有表头结点的行循环链表，将每一列的非零元素通过down域链接成一个带有表头结点的列循环链表。,因此，每个非零元素即是第i行循环链表中的一个结点又是第j列循环链表中的一个结点。由于整个稀疏矩阵是由十字交叉的链结构来表示的，故称其为十字链表。如对下面的稀疏矩阵A可由如下图所示的十字链表来表示。,在表示有t个非零
18、元素的mn的矩阵的十字链表中，共有t+max（m，n）+1个结点，每个结点大约需要占用23个存储单元。因此，只在矩阵非零元素个数t比矩阵的阶mn小的多的条件下，十字链表的存储开销才小于矩形结构的二维数组的开销mn。以上给出了稀疏矩阵的一种新的存储思想，但如何将一个已知的稀疏矩阵以十字链表表示出来,还是一个需要解决的问题。下面我们就来讨论在内存中建立十字链表的具体算法。首先输入三元组（m，n，t）它们是要存储矩阵的行数,列数及非零元素个数,紧接着输入t个形如（i，j，aij）的三元组,它们分别代表了t个非零元素行、列值及元素值，其输入次序是按矩阵中以行为主顺序输入的。如此，对于前面图中所示的含有
19、5个非零元素的稀疏矩阵A。其输入的数据依次为：5,4,5;1,1,3;1,4,7;2,3,-1;3,1,2;5,4,8,算法中还需引入一辅助工作数组：hdn：p1：p（p=max（m，n)及指针变量last。其中hdni是指向十字链表中第i行（也是第i列）行（列）链表的表头结点的指针,last是指向当前所建的行链表的最右（后）面的那个结点。这样，建立十字链表的算法Mread（A）执行的大致过程是：i)按前述规定建立p个表头结点（不包括HA）。ii)建立每个行循环链表，在此过程中第i个链表示的表头结点的val域先用来跟踪第i列的列链表当前最下（后）面的那个结点，其作用相当于建立行链表时的指针la
20、st。iii)建立表头结点HA，并将全体p+1个表头结点链成循环链表。算法具体描述如下：,PROCEDURE Mread(A)；BEGIN read(m，n，t)；p：=max(m，n)；FOR i=1 TO p DO newl(x);hdni:=x;x.row:=x.col:=0;x.right:=x.val:=x;crow:=1;last:=hdn1;FOR i:=1 TO t DO read(rrow,cool,val);IF rrowcrow THEN last.right:=hdncrow;crow:=rrow;last:=hdncrow newl(x);x.row:=rrow;,x
21、.col:=ccol;x.val:=val;last.right:=x;last:=x;(hdncool.Val).down:=x;hdnccol.val:=x IF t0 THEN last.right:=hdnrrow;FOR i:=1 TO p DO hdni.val).down:=hdni;newl(A);A.row:=m;A.col:=n;HA:=A;FOR i:=1 TO p-1 DO hdni.val:=hdni+1;IF p=0 THEN HA.val:=HA;ELSE hdnp.val:=ha;ha.val:=hdn1 END;,void Mread(A)scanf(“%d,
22、%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=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=
23、1;ival)-down=hdni;A=new orthogonalNode;A-row=m;A-col=n;HA=A;for(i=1;ival=hdni+1;if(p=0)HA-val=HA;Else hdnp-val=HA;HA-val=hdn1;,容易看出上述算法的时间复杂性为O(p+t)=O(m+n+t)，如果用矩形结构的二维数组存储矩阵时,则所需时间为O(m*n)。因此，当非零元素个数t比m*n小得多时用Mread算法存储稀疏矩阵比用经典方法要快。,当将B加到A上去时，对A矩阵的十字链表来说，或者是改变结点的Val域值（aij+bij 0）,或者是不变（当bij=0时）或,者是插入一
24、个新结点（当aij=0时），还可能是删除一个结点（当aij+bij=0时）。整个运算可从矩阵的第一行开始，一行一行的进行，一直到m行。对任何一行都从表头结点出发找到各自的第一个结点开始进行比较，为了便于插入和删除结点，需设以下4组指针：(1)ha，hb 分别表示矩阵A和B的十字链表的头指针；(2)Ca，Cb 分别指向A和B的行链表的表头结点的指针；(3)Pa，Pb 分别指向A和B的同一行上的两个结点，这两 个指针将指向各非零元素；(4)qa指示Pa所指结点的行的前趋结点，为删除插入服务。hlj指示A矩阵中每一列的指针，初值指向每一列的列 链表的表头结点，以便在某行j列上插入或删除 某一结点时，
25、让hlj指向这一列的上一个结点。,(1)由Ca，Cb确定Pa，Pb，分别指向A和B链表中第一行第一个非零元素。pa=Ca-right；p=Cb-right；若B中该行中无非零元素（即Pb-Col=0）则令Ca，Cb指针下移，指向下一行（即Ca=Ca-val；Cb=Cb-val）。,下面将矩阵B加到矩阵A上去的运算过程大致描述如下：刚开始由ha，hb确定Ca，Cb：Ca=ha-val;Cb=hb-val;,(2)否则，比较这两个结点进行相加，这时可能有上述所说的三种情况：若Pa-colcol,且pa-col0（不是表头结点）则令pa指向本行的下一个结点即:qa=pa;pa=pa-right；并重
26、新加以比较。,若pa-colpb-col 或pa-col=0(A在该行无非零元素，B 相应行有非零元素)则将B中相应结点插入A中，设新结点为P：qa-right=p；p-right=pa;修改A中的列指针，首先需找到同一列中上一个结点，然后令hlj指向该结点。于是A的列表指针改为：P-down=hlj-down;hlj-down=P;Pb=Pb-right;,若pa-col=pb-col,则pa-val=pa-val+pb-val；若pa-val!=0，则qa=Pa;Pa=Pa-right;Pb=Pb-right(为下一次比较做准备)若pa-val=0，则删除A中该结点：,Qa-right=P
27、a-right;hlj-down=Pa-down;然后Pa=qa-right;Pb=Pb-right;(为下一次比较做准备),(3)重复步骤(2)，直到B的同一行中没有非零元素为止(即Pb.Col=0到表头结点了)，然后转向下一行。以此类推直到m行都进行完为止。此时Ca，Cb分别又指向十字链表的头结点，即Ca-row!=0;Cb-row!=0(因为Cb-row0表示是行链表的表头结点)上述算法的整个运算过程在于对A和B的十字链表逐行扫描，其循环次数主要取决于A和B矩阵中非零元素的个数ta和tb,因此此算法的时间复杂度为O（ta+tb）。,这一节的最后，我们来看看如何把用十字链表表示的稀疏矩阵的
28、所有结点还给可利用空间栈。这里假设可用空间栈是通过right域链接起来的单链表，表头指针为av，其归还算法并不复杂，直接用类C语言描述如下：,void Merase(ha);/将以ha为表头指针的十字链表的全部结点归还给av栈next=ha-val;/记下第一行行链表表头结点 ha-right=av;av=ha;while(nextha)t=next-right;next-right=av;av=t;next=next-val;,广义表,若ai 为不可再分割的原子元素，则称ai 为原子元素；若ai 为一个子表，则称ai 为表元素。用小写字母表示原子元素，用大写字母表示表元素。,表的深度是指表中
29、所包含的括号的层数。,A=();长度为0的空表。B=();是以空表作为唯一元素的表，长度为1。C=(a,b);有两个元素a,b长度为2。D=(a,(b,c);含有一个原子元素和一广义表，长度为2。E=(x,D,y);长度为3的广义表。F=(a,F);长度为2的递归的广义表。,广义表的例子：,a,b,a,b,c,x,y,a,b,c,a,C,D,E,D,F,表元素,原子元素,3.列表可以是一个递归的表，即列表可以是本身的一个子表。,2.列表可以为其他表所共享。,1.列表的元素可以是子表,而子表的元素还可以是子表,。,求下列广义表的运算结果：1.Head(p,w,h)2.tail(b,k,p,h)3
30、.Head(a,b),(c,d)4.tail(a,b),(c,d)5.tail(Head(a,b),(c,d),广义表一般采用链式存储结构，链结点的构造可以为,A=(),B=(),B,C=(a,b),D=(a,(b,c),C,D,E=(x,D,y),E,F=(a,F),F,A=NULL,多元多项式的广义表表示,P(x,y,z)=x10y3z2+2x8y3z2+3x8y2z2+x4y4z+6x2y4z+2yz,=(x10+2x8)y3+3x8y2)z2+(x4+6x2)y4+2y)z,P(z)=Az2+Bz,A(x,y)=(x10+2x8)y3+3x8y2,B(x,y)=(x4+6x2)y4+2y,A(y)=Cy3+Dy2,B(y)=Ey4+Fy,C(x)=x10+2x8,D(x)=3x8,E(x)=x4+6x2,F(x)=2x0,若链结点的构造设计为,其中,coef 表示多项式的某一项的系数,或指向其系数子表 exp 表示多项式的某一项的指数 link 为链接多项式中同一层各链结点的指针,相当于data域,该多项式的广义表的表示形式为：,
