12讲第五章数组广义表

第五章数组和广义表本章内容与要点本章内容数组的类型定义和表示方法；稀疏矩阵的压缩存储方法及矩阵运算的实现；广义表定义的递归性及广义表的链式存储结构。本章要点了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法；领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法；掌握广义表的结构特点及链式存储表示方法；掌握数组和广义表可看成是一种特殊的线性表，其特殊性在于，表中的数据元素本身也是一种线性表。5.1数组的定义数组数组是数据元素为结构类型的一种特殊的线性表。数组的每一个元素的结构都是相同的；数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界；数组通常分为一维数组、二维数组、三维数组…和n维数组。数组一旦被定义，它的维数和维界就不再改变。除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。

二维数组的定义二维数组既可以看成是由行向量组成的向量；也可以看成是列向量组成的向量；C语言中二维数组的定义定义为分量类型为一维数组类型的一维数组类型

typedefelemtypearray2[m][n];

等价于：

typedefelemtypearray1[n];typedefarray1array2[m];Amn=a11a12

…a1na21a22

…a2n

…

…

…

…am1am2

…amn5.2数组的顺序表示和实现数组的顺序存储方式行优先顺序将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面；以二维数组为例，按行优先顺序存储的线性序列为：a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn

PASCAL、C语言中，数组就是按行优先顺序存储的。列优先顺序将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，数组的m*n个元素按列优先顺序存储的线性序列为：a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm在FORTRAN语言中，数组就是按列优先顺序存储的。数组的顺序存储方式（续）多维数组行优先顺序规定为先排最右的下标，从右到左，最后排最左下标：列优先顺序规定为先排最左下标，从左向右，最后排最右下标。数组的顺序存储特点只要已知开始结点的存放地址（即基地址）、数组维数、每维的上、下界，和每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数；数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。数组的顺序表示和实现（续）求数组A[c1..d1,c2..d2,……,cn..dn]每个给定下标的数据元素的存储地址：LOC(j1,j2,…,jn)=

Loc(c1,c2,…,cn)+[(d2-c2+1)…(dn-cn+1)(j1-c1)+(d3-c3+1)…(dn-cn+1)(j2-c2)+...+(dn-cn+1)(jn-1-cn-1)+(jn-cn)]*l=Loc(c1,c2,…,cn)+[∑(ji-ci)(∏(dk-ck+1)+(jn-cn)]*li=1k=i+1n-1nLOC(j1,j2,…,jn)=

Loc(c1,c2,…,cn)+∑αi(ji-ci)i=1n其中αi

=l∏(dk-ck+1)1≤i≤nnk=i+15.3矩阵压缩存储特殊矩阵非零元素或零元素的分布有一定规律的矩阵，可以把矩阵压缩存储在一个一维数数组中。如下三角矩阵有映射k=i(i-1)/2+j(i≥j),Aij=Bk(i≥j)，Aij=0(i≤j)An×nBm，即B[k]=A[i,j]，需求出下标映射函数k=f(i,j)。上三角矩阵0对角矩阵000下三角矩阵ajiaij对称矩阵a11a21a22a31．．．an,1．．．annk=0123n(n-1)/2n(n+1)/2-1稀疏矩阵稀疏矩阵非零元素很少，分布没有规律；设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即s≦m×n），则称A为稀疏矩阵；令e=s/(m*n)，称e为矩阵的稀疏因子。通常认为e≦0.05时称之为稀疏矩阵；在压缩存储时需要同时存储非零元素的下标和值；可用三元组存储（行号，列号，值）。0120000100030000500000000020006ijv1212211253345522566A三元组顺序表（续）稀疏矩阵的定义稀疏矩阵还可用带行索引的二元组表、十字链表等表示。#defineMAXSIZE12500typedefstruct{ inti,j; ElemTypee;}Triple;typedefstruct{ Tripledata[MAXSIZE+1]; intmu,nu,tu;}TSMatrix;矩阵的操作求矩阵的转置ijv1212211253345522566ijv1212112252435523656A’求矩阵的转置一个m×n的矩阵M，它的转置T是一个n×m的矩阵，且a[i][j]=b[j][i]，0≤i≤m，0≤j≤n，即M的行是T的列，M的列是T的行；算法思想对M中的每一列col(1≤col≤n)，从头至尾扫描三元表a.data；找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放入b.data中；即可得到T的按行优先的压缩存储表示。求矩阵转置的算法Voidtransmatrix(TSMatrixM,TSMatrix&T){ T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu) {q=1;for(col=1;col<=M.nu;col++)for(p=1;p<=M.tu;p++) if(M.data[p].j==col) {T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;q++;}}}算法的时间复杂度

O(nu*tu)快速转置算法思路对M扫描一次，预先确定矩阵M中每一列的第一个非零元在T中的位置；对M进行第二次扫描，由位置关系装入三元组。算法实现附设num和cpot两个向量：num[col]:表示矩阵M中第col列中非零元的个数；cpot[col]:指示M中第col列的第一个非零元在b.data中的恰当位置；cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1] 2≤col≤a.nu

因三元组表是按行优先排序的，故先确定转置后矩阵各行的元素个数，预留出位置再进行转置。快速转置的算法实现voidfasttranstri(TSMatrixM,TSMatrix&T){ T.mu=M.nu;T.nu=M.mu;T.tu=M.tu; if(T.tu) { for(col=1;col<=M.nu;++col)num[col]=0; for(t=1;t<=M.tu;++t)++num[M.data[t].j]; cpot[1]=1; for(col=2;col<=M.nu;++col) cpot[col]=cpot[col-1]+num[col-1]; for(p=1;p<=M.tu;++p) { col=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++cpot[col];}}}算法的时间复杂度

O(mu*nu)5.4广义表的定义广义表又称列表，其每一个元素的结构都可能是不同的；是n(n≥0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表；通常记作LS=(a1,a2,a3,…,an)LS是广义表的名字，n为它的长度。若ai是广义表，则称它为LS的子表。第一个元素a1称为表LS的表头（head），由余下元素组成的表(a2,a3,...,an)称为LS的表尾（tail）。广义表中括号的重数称为广义表的深度。广义表的定义（续）广义表举例表长表深表头表尾A=()01--B=(a,A)=(a,())22a(())C=((a,b),c,d)32(a,b)(c,d)D=(a,D)=(a,(a,(a,…)))2

a(D)广义表的图形表达方法

A=(a,b)abAB=(A,c)BD=(a,D)aDL=(A,B)LABabcAabc表原子5.5广义表的存储结构头尾链表存储结构typedefenum{ATOM,LIST}ElemTag;typedefstructGLNode{ ElemTagtag; union{ AtomTypeatom; struct{ structGLNode*hp; /*表头指针*/ structGLNode*tp; /*表尾指针*/ }ptr; };}*GList;tag=1hptp表结点tag=0data原子结点广义表的头尾链表存储结构示例A=()A-NIL11^^0a111^0c0d11^0a0b11^D0aB=(a,A)C=((a,b),c,d)D=(a,D)(A)(D)(a,b)(c,d)(d)(b)BC广义表的存储结构（续）扩展线性链表存储结构typedefenum{ATOM,LIST}ElemTag;typedefstructGLNode{ ElemTagtag; union{ AtomTagatom; structGLNode*hp; /*表头指针*/ }; structGLNode*tp; /*同一层的下一个结点*/}*GList;tag=0datatp原子结点tag=1hptp表结点广义表的扩展线性链表存储示例A1^^1^0aA=()1^^BB=(a,A)C=((a,b),c,d)C1^10c0d^0a0b^1^DD=(a,D)0a1^aDaA(a,b)cdab5.6m元多项式的表示将m元多项式先分解成主变元的多项式可将其看作一元多项式每个系数则是m-1元多项式；利用此法可将m-1元多项式进一步分解，直至每个系数为常数。作业求下列广义表运算的结果：

1、HEAD[((a,b),(c,d))]2、TAIL[((a,b),(c,d))]3、HEAD[TAIL[((a,b),(c,d))]] 4、TAIL[HEAD[((a,b),(c,d))]]5、HEAD[TAIL[HEAD[((a,b),(c,d))]]] 6、TAIL[HEAD[TAIL[((a,b),(c,d))]]]作业利用HEAD和TAIL运算将下列广义表中的原子c取出来：

1、L1=(a,b,c,d)2、L2=((a,b),(c