《数据结构第5章数组和广义表》由会员分享，可在线阅读，更多相关《数据结构第5章数组和广义表（33页珍藏版）》请在金锄头文库上搜索。
1、第五章 数组和广义表在线性表L=(a0 a1,an-1)中，元素ai是无结构的（称为 原子或单元素），即ai本身不再是一个数据结构。本章的数组 和广义表是线性结构的推广。在这种结构中，元素本身可以 又是一个数据结构。本章讨论多维数组的表示、矩阵压缩存 储、广义表的表示等问题。 5.1数组的定义及其操作 5.1.1 数组的定义 在算法语言中(如FORTRAN、PASCAL、C、Java等)都 有数组类型。前面接触到的是一维数组，本节以C语言为例讨 论多维数组，如多维数组的描述、存储映象、地址计算等问 题。1数组描述设二维数组:其中:m、n为行列数,aij为第i行、第j列的元素,0im-1,0jn
2、-1;元素个数 为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-1a00 a01 a0j a0n-1.ai0 ai1 aij . ain-1.am-10 am-11 am-1j am-1n-1A(2) = Amn = 2数组描述关系集Row和Col表明：除数组A(2)周边元素外的其它任一个元素aij ，有两个直接前驱ai-1j，aij-1,和两个直接后继ai+1j，aij
3、+1 (周边元素的前驱 或后继可不足两个)。n维数组也可按上述方法类似定义。 二维数组可如下描述: 多维数组是线性表的推广，而线性表是多维数组的特例。A0Ai 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 = 35.1.1数组的抽象数据类型在算法语言中，数组一旦生成，其元素的存储空间就固定下来，故数组 的运算一般不包括插入和删除这样的操作。 ADT Array D=aj1j2jn|aj1j2jndatatype，ji=0,bi-1其中i=1,2,
4、n n(n0)为数组维数，bi是第i维长度， ji是数组元素第i维下标。R=R1,R2,Rn 其中：Ri=|0jkbk-1，1kn且ki，0jibi-2， aj1jijn, aj1ji+1jnD，i=1,2,nPArrayInit(Loc(a1)=b+L;Loc(ai)=b+iL;规律：任一元素ai的地址:a0a1 ai-1aian-1An=( a0, a1, ai , an-1)起始地址b + ( ai前的元素个数i )L 起址 b:b+L:b+iL:L图5.27数组元素的地址计算2）二维数组：a00a0,n-1ai0aijam-1,n-1由图5.3知：Loc(a00) = bLoc(ai0
5、) = b+( ai0前元素个数)L=b+(in)LLoc(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:图5.3a00 a01 a0j a0n-1.ai0 ai1 aij . ain-1.am-10 am-11 am-1j am-1n-1Amn = 8数组元素的地址计算3）三维数组：由图5.5可知：Loc(a000)=b 图5.5Loc(ai00)=b+(inp)LLoc(aij0
6、)=b+(inp +jp)LLoc(aijk)=b+(inp+jp+k)Laijk前的元素个数。a000ai00 aij0aijk9数组元素的地址计算4）n 维数组从以上的地址公式推导中得出这样一条规律：数组中任一元素的地址= 起址b+ 该元素前的个数元素单元量L。 故n维数组Au1u2un中任一元素ai1in的地址为：Loc(ai1i2in)=b+(i1u2u3 un+i2u3u4 un+in-1un+in)L=b+( )L元素按“列优先”方式存储时，地址计算方法类似，不再赘述。 有了数组元素的地址计算公式，给出相应参数后，能够很快求出任 一元素的地址，然后按地址存取相应元素，故对数组的存取
7、是随机存取（ 或按公式存取）。 5.2.2数组的动态存储方式（略）105.2 矩阵的压缩存储信息的压缩存储是一项专业技术，在当今的多媒体应用中显得尤为 重要。但本节只是讨论矩阵（或二维数组）中元素的压缩存储。 在矩阵中，往往会出现许多值相同的元素或元素，为节省存储空 间，可以采用某些技术对这类矩阵进行压缩存储。压缩存储的原则是：对 多个值相同的元素只存储其中之一，对元素甚至不分配存储空间。 5.3.1特殊矩阵的压缩存储特殊矩阵：值相同的元素或元素在矩阵中的分布遵循一定规律。 1.对称矩阵：满足aij = aji，(1i,jn) a11 a22 aiiannAnn= aijaji11特殊矩阵的压
8、缩aij与aji对称相等，二者只需分配一个存储单元，即只存储包括主对角 线的下三角(或上三角)元素。于是Ann所需单元数为n(n+1)/2，而不压缩 存储需要n2个单元。当n很大时，几乎能压缩原存储空间的一半。 具体做法：设置数组Sn(n+1)/2+1作为An.n的存储空间，且按行的次 序存放Ann中包括主对角线的下三角元素，如图5.5所示。a11a21a22aijannSn(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
9、+i 当ij)时，K=0. 对于下三角矩阵，类似于对称矩阵，即只存储包括主对 角线的下三角元素。而当idata1 A-datatu 图5.816三元组表的转置然而，稀疏矩阵的压缩存储会给矩阵运算带来一些不便，算法要复 杂些。这里的运算指求矩阵的转置，两矩阵相加和相乘等。我们只讨论矩 阵的转置的算法。未压缩前，求矩阵A的转置矩阵B，算法很简单：for(col=1;coldata3.j=1,故将A-data3转置 ：(1，2，6)=B-data1，又A-data6.j=1，所以A-data6转置：(1，4，3)=B-data2，完成第一列的转换，依此类推。 算法描述：void Transm(Tsm
10、type 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+)for(p=1;ptn;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+; 18三元组表的转置ijv 122 154 216 238 329 413p 1234560 2 0 0 46 0 8 0 00 9 0 0 03 0 0 0 0A45 = 1
11、2 3 4 5colijv 126q 123456143 212 239 328 5140 6 0 3 2 0 9 0 0 8 0 0 0 0 0 0 4 0 0 0B54 = （矩阵A 的三元组表）图5.10 （转置后的三元组表）算法的时间复杂度：O(tn)n=列数,t=非0元个数。改进算法的复杂度：O(t+n) （略）192.十字链表十字链表是以链表结构形式存储一个稀疏矩阵。矩阵中非0元设置成 如下形式的节点：其中i、j分别存放非0元的行列号，head/data或作为一非0元的值域（ data）或作为头节点的链指针(head)；down为指向相同列下一个非0元节 点的指针，right为指向
12、相同行下一非0元节点的指针。 节点类型描述： typedef struct node int i,j;union struct node *head;datatype data;vdata;struct node *down,*right; nodetype,*tlink;ijhead/datadownright20十字链表1 111 442 223 134 450 04 40 00 00 00 00 00 00 0L例5-4 设稀疏矩阵 ：1 0 0 4 0 2 0 0 3 0 0 0 0 0 0 5A44 = A的十字链表如图5.11：21建立十字链表算法思路：先构造空表，其中S取矩阵行列
13、数的最大值，即S=max(m,n)。依 次读入每个非0元(i,j,v)，生成一个非0元的节点，对该节点赋读入的值后 ，将其插入第i行链表和第j列链表的正确位置。 算法描述： void Creattenlink(tlink L,int m, int 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;fo
14、r(i=1;ii=p-j=0; p-down=p-right=p; Hi=p;Hi-1-vdata.head=p;Hs-vdata.head=L; /构成循环 22建立十字链表for(k=1;ki=i;p-j=j;p-vdata.data=v; /赋值q=Hi； /取第i行链表头节点指针while(q-right!=Hi) /找当前非0元节点在行链表中的位置p-right=q-right; q-right=p; /当前非0元节点插入q节点之后q=Hj； /取第j列链表头节点指针while(q-down!=Hj) /找当前非0元节点在列链表中的位置p-down=q-down; q-down=p;/ 非
