数据结构-第5章数组和广义表

1、1第五章 数组和广义表在线性表L=(a0 a1,an-1)中，元素ai是无结构的（称为原子或单元素），即ai本身不再是一个数据结构。本章的数组和广义表是线性结构的推广。在这种结构中，元素本身可以又是一个数据结构。本章讨论多维数组的表示、矩阵压缩存储、广义表的表示等问题。5.1数组的定义及其操作5.1.1 数组的定义 在算法语言中(如FORTRAN、PASCAL、C、Java等)都有数组类型。前面接触到的是一维数组，本节以C语言为例讨论多维数组，如多维数组的描述、存储映象、地址计算等问题。 2数组描述设二维数组:其中:m、n为行列数,aij为第i行、第j列的元素,0im-1,0jn-1;元素个数

2、为mn。 二维数组可用形式化语言描述，即： A(2)=(D,R)其中：D=aij|aijdatatype,0im-1, 0jn-1; R=Row,Col 行关系：Row=|aij,aij+1D,0im-1,0jn-2 列关系：Col=|aij,ai+1jD,0im-2,0jn-1 a00 a01 a0j a0n-1.ai0 ai1 aij . ain-1.am-10 am-11 am-1j am-1n-1A(2) = Amn = 3数组描述关系集Row和Col表明：除数组A(2)周边元素外的其它任一个元素aij，有两个直接前驱ai-1j，aij-1,和两个直接后继ai+1j，aij+1 (周边

3、元素的前驱或后继可不足两个)。n维数组也可按上述方法类似定义。二维数组可如下描述: 多维数组是线性表的推广，而线性表是多维数组的特例。A0 Ai Am-1= (A0Ai.Am-1 )-线性表形式a00 a01 a0j a0n-1.ai0 ai1 aij . ain-1.am-10 am-11 am-1j am-1n-1A(2) = Amn = 45.1.1数组的抽象数据类型 在算法语言中，数组一旦生成，其元素的存储空间就固定下来，故数组的运算一般不包括插入和删除这样的操作。ADT Array D=aj1j2jn|aj1j2jndatatype，ji=0,bi-1其中i=1,2,n n(n0)为

4、数组维数，bi是第i维长度， ji是数组元素第i维下标。 R=R1,R2,Rn其中：Ri=|0jkbk-1，1kn且ki，0jibi-2，aj1jijn, aj1ji+1jnD，i=1,2,n P ArrayInit(&A,n,d1，d2,.dn)操作结果：若维数n和各维长度合法，则生成一个n维数组Ad1d2.dn（C语言中，1n8）。ArrayDestroy(&A)初始条件：数组A存在。操作结果：撤销数组A。ArrayGet(A,i1,.,in,&e)初始条件：数组A存在，edatatype。操作结果：若各下标合法，则将元素Ai1i2,.,in的值传给变量 e。5数组的抽象数据类型Array

5、Assign(&A,i1,.,in,e)初始条件：数组A存在，edatatype。操作结果：若各下标合法，则将变量 e的值传给数组元素Ai1i2,.,in。ADT Array； 5.2 数组的存储结构 由于计算机的存储空间是一维的（或线性的），所以存储数组时，要将多维数组中的元素按某种次序映象到一维存储空间，即解决“降维”问题。5.2.1 数组的静态存储方式1数组的静态存储映像 在PASCAL和C等语言中，是按低维下标优先变化（或按行优先）的方式，存储数组中的元素。如在C语言中，二维数组的映像如图5.1所示。 但在FORTRAN语言中，数组元素是按高维下标优先变化或按列优先方式，存储数组中的元

6、素。 6数组的存储映像 a00a0,n-1ai0ai,n-1am-1,n-1映像 （ 存储器）a00 a01 a0j a0n-1.ai0 ai1 aij . ain-1.am-10 am-11 am-1j am-1n-1 Amn = 图5.1思考：1.三维以上数组如何映像?2.“按列优先”如何映像?72.静态数组元素的地址计算以C语言为例。设数组元素的起始地址为b,每个元素占用L个单元（元素所占单元量由元素的类型而定），元素a的地址用Loc(a)表示。1）一维数组：即: Loc(a0)=b; Loc(a1)=b+L; Loc(ai)=b+iL;规律：任一元素ai的地址:a0a1 ai-1aia

7、n-1An=( a0, a1, ai , an-1) 起始地址b + ( ai前的元素个数i )L 起址 b: b+L: b+iL:L图5.28数组元素的地址计算2）二维数组：a00a0,n-1ai0aijam-1,n-1由图5.3知：Loc(a00) = b Loc(ai0) = b+( ai0前元素个数)L=b+(in)L Loc(aij) = b+( aij前元素个数)L= b+in+jL例5-1 设二维数组A78，起始地址b=1000，每个元素所占单元量L=3，则Loc(a5,6)=1000+(58+6)3 = 1138。 inj映像 起址 b: b+L: b+inL: b+in+jL

8、:图5.3a00 a01 a0j a0n-1.ai0 ai1 aij . ain-1.am-10 am-11 am-1j am-1n-1 Amn = 9数组元素的地址计算3）三维数组： 由图5.5可知：Loc(a000)=b 图5.5 Loc(ai00)=b+(inp)L Loc(aij0)=b+(inp +jp)L Loc(aijk)=b+(inp+jp+k)L aijk前的元素个数。a000ai00aij0aijk10数组元素的地址计算4）n 维数组 从以上的地址公式推导中得出这样一条规律： 数组中任一元素的地址= 起址b+ 该元素前的个数元素单元量L。故n维数组Au1u2.un中任一元素

9、ai1.in的地址为： Loc(ai1i2in)=b+(i1u2u3 un+i2u3u4 un+in-1un+in)L =b+( )L元素按“列优先”方式存储时，地址计算方法类似，不再赘述。有了数组元素的地址计算公式，给出相应参数后，能够很快求出任一元素的地址，然后按地址存取相应元素，故对数组的存取是随机存取（或按公式存取）。5.2.2数组的动态存储方式（略）115.2 矩阵的压缩存储信息的压缩存储是一项专业技术，在当今的多媒体应用中显得尤为重要。但本节只是讨论矩阵（或二维数组）中元素的压缩存储。在矩阵中，往往会出现许多值相同的元素或元素，为节省存储空间，可以采用某些技术对这类矩阵进行压缩存储

10、。压缩存储的原则是：对多个值相同的元素只存储其中之一，对元素甚至不分配存储空间。5.3.1特殊矩阵的压缩存储 特殊矩阵：值相同的元素或元素在矩阵中的分布遵循一定规律。1.对称矩阵： 满足aij = aji，(1i,jn) a11 a22 aii ann Ann= aijaji12特殊矩阵的压缩aij与aji对称相等，二者只需分配一个存储单元，即只存储包括主对角线的下三角(或上三角)元素。于是Ann所需单元数为n(n+1)/2，而不压缩存储需要n2个单元。当n很大时，几乎能压缩原存储空间的一半。具体做法：设置数组Sn(n+1)/2+1作为An.n的存储空间，且按行的次序存放Ann中包括主对角线的

11、下三角元素，如图5.5所示。a11a21a22aijann Sn(n+1)/2+1: 1 2 3 . k . n(n+1)/2图5.5其中aij存入Sk单元，下标（i,j）与k的关系为： i(i-1)/2+j 当ij 时； Si(i-1)/2+j 当ij 时； k= 即：aij= j(j-1)/2+i 当ij时。 Sj(j-1)/2+i 当ij)时，K=0. 对于下三角矩阵，类似于对称矩阵，即只存储包括主对角线的下三角元素。而当idata1 A-datatu 图5.817三元组表的转置然而，稀疏矩阵的压缩存储会给矩阵运算带来一些不便，算法要复杂些。这里的运算指求矩阵的转置，两矩阵相加和相乘等。

12、我们只讨论矩阵的转置的算法。未压缩前，求矩阵A的转置矩阵B，算法很简单： for(col=1;col= nu;col+) for (row=1;rowdata3.j=1,故将A-data3转置： (1，2，6)=B-data1，又A-data6.j=1，所以A-data6转置： (1，4，3)=B-data2，完成第一列的转换，依此类推。算法描述： void Transm(Tsmtype A, Tsmtype B) int p,q,col; B-mu=A-nu; B-nu=A-mu; B-tu=A-tu; if(A-tu!=0) q=1; /目标表的序号 for(col=1;colnu;col

13、+) for(p=1;ptu;p+) if(A-datap.j=col) B-dataq.i=A-datap.j;/行列互换 B-dataq.j=A-datap.i; B-dataq.v=A-datap.v; q+; 19三元组表的转置 ijv122154216238329413 p 123456 0 2 0 0 4 6 0 8 0 0 0 9 0 0 0 3 0 0 0 0 A45 = 1 2 3 4 5 colijv126 q 1234561432122393285140 6 0 3 2 0 9 0 0 8 0 0 0 0 0 0 4 0 0 0 B54 = （矩阵A 的三元组表） 图5.

14、10 （转置后的三元组表）算法的时间复杂度：O(tn)n=列数,t=非0元个数。改进算法的复杂度：O(t+n) （略）202.十字链表十字链表是以链表结构形式存储一个稀疏矩阵。矩阵中非0元设置成如下形式的节点： 其中i、j分别存放非0元的行列号，head/data或作为一非0元的值域（data）或作为头节点的链指针(head)；down为指向相同列下一个非0元节点的指针，right为指向相同行下一非0元节点的指针。节点类型描述：typedef struct node int i,j; union struct node *head; datatype data; vdata; struct n

15、ode *down,*right; nodetype,*tlink;ijhead/datadownright21十字链表111144222313445004400000000000000L例5-4 设稀疏矩阵 ：1 0 0 40 2 0 03 0 0 00 0 0 5 A44 = A的十字链表如图5.11：22建立十字链表算法思路：先构造空表，其中S取矩阵行列数的最大值，即S=max(m,n)。依次读入每个非0元(i,j,v)，生成一个非0元的节点，对该节点赋读入的值后，将其插入第i行链表和第j列链表的正确位置。算法描述：void Creattenlink(tlink L,int m, int

16、 n, int t) /L为头指针，m,n,t分别为行列号和非0元个数 tlink p,q,Hmaxsize; int i,j,k,s; datatype v; if(mn) s=m; else s=n; /确定头节点的个数 L=(tlink)malloc(sizeof(nodetype); /申请总的头节点 L-i=m;L-j=n; /置行列数 H0=L; for(i=1;ii=p-j=0; p-down=p-right=p; Hi=p; Hi-1-vdata.head=p; Hs-vdata.head=L; /构成循环 23建立十字链表 for(k=1;ki=i;p-j=j;p-vdata

17、.data=v; /赋值 q=Hi； /取第i行链表头节点指针 while(q-right!=Hi)&(q-right-jright; /找当前非0元节点在行链表中的位置 p-right=q-right; q-right=p; /当前非0元节点插入q节点之后 q=Hj； /取第j列链表头节点指针 while(q-down!=Hj)&(q-down-idown; /找当前非0元节点在列链表中的位置 p-down=q-down; q-down=p;/ 非0元节点节点插入q节点之后 245.4广义表的定义及其操作5.4.1 广义表的定义 广义表又称列表(lists),是线型表的推广。在线型表L=(a

18、0aian-1)中，ai是单元素或原子，即ai本身不再是一个DS，而广义表记为：LS = (d0d1didn1)其中di（0in-1）既可以是一个原子，又可以是另一个表（称为子表），即表中还可以套表。广义表LS的形式化描述为：LS=(D,R)其中： D= di |didatatype or diLS (递归定义)，i=0,1,.n-1,n0 R=|di, di+1D,0in-2式中n为表长（n=0 时为空表），若di为原子，则称di为LS的单元素，否则di称为LS的子表（满足递归定义)。对非空广义表定义两个函数：Gethead(LS)=d0； Gettail(LS)=(d1.dn-1)。即Ge

19、thead(LS)是LS的第一元素d0（当然d0可以为子表），而Gettail(LS)是LS中d1.dn-1的一个子表。对广义表的其它运算（如查找，插入和删除等）类似于线性表的运算（见5.4.2）。 25例5-5 广义表的例子约定：大写字母AZ为表名，小写字母 az为单元素。A=()或A()空表，表长=0，无表头，表尾；B=(a,b)或B(a,b)线性表特例,表长=2, Gethead(B)=a, Gettail(B)=(b)；C=(e,B)或C(e,B)表长=2，Gethead(C)=e, Gettail(C)=(B)=(a,b), 表C可以表示为：C(e,(a,b)；D=(A,B,C)或D

20、(A,B,C)表长=3，Gethead(D)=A=(), Gettail(D)=(B,C)=(a,b),(e,(a,b)；E=(a,E)表长=2，Gethead(E)=a, Gettail(E)=(E),整个表E为 (a,(a,(a, .)，它为一个特殊的广义表，称为递归表，或无限表。从例5-5可以看出，广义表有如下特点：（1）表可以嵌套表中元素可以是一个表，称为子表，而子表还可以有子表。如例5-5中表B和表C的结构如图5.13所示。 图5.13CeBababB26广义表的例子（2）表可以共享表可以是其它表的子表,或表中的元素可取自其他表。如例5-5中表D包含表A、B、C，或A、B、C为D的子

21、表,如图5.16所示。 （3）表可以递归表中元素可以是表本身。如例5-5中表E。 EaDABCabe图5.16另外，表中任一单元素可由Gethead(Ls)和Gettail(Ls)函数导出，如取表A=(a,(b,d,e)中单元素d的运算为： Gethead(Gettail(Gethead(Gettail(A) 275.5广义表的存储结构对于广义表LS=( d0 didn-1)，由于di可以是单元素或子表，故用顺序存储结构表示LS较为困难，一般采用链表存储，称为广义链表。5.5.1广义表的链式存储1单链表示法 元素di的节点形式：其中： 0 当di为单元素时； data 当atom=0时； at

22、om= data/link= 1 当di为子表时。 link 当atom=1时。 next意义同线性链表，指向di+1所在节点。 节点描述：typedef struct node int atom; union datatype data; struct node *link; dtype; struct node *next; Lsnode; atomdata/linknext28广义表的存储为操作方便，对每一广义表引入头节点，其形式同一般的表节点： 例5-5中广义表A、B、C、D、E的单链表如图5.15所示。 11AA=() 图5.150a0b1BB=(a，b)0e11CC=(e，B)1111DD=(A，B，C)0a11EE=(a，E)29广义表的存储2双链表示法元素di的节点形式：其中： 指向子表的指针 当di为子表时； link1= 当di为原子时。 表名 当di为子表时； data = link2：指向di+1所在的节点。 原子值 当di为原子时。例5-5中几个广义表的双链表结构如图5.16 ： datalink1l