考研-数据结构

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

本质上为非线性结构5.1数组和线性表的关系以及数组的运算5.2数组的顺序存储结构5.3特殊矩阵和稀疏矩阵的压缩存储5.4广义表的定义和表示方法5.5广义表的存储结构5.6广义表的递归算法5.7例题解析数据结构---第五章数组和广义表25.1数组和线性表的关系以及数组的运算[数组和线性表的关系]

任何数组A都可以看作一个线性表

A=(a1,a2,…,aj,…an)

n维数组时，表中每一个元素是一个(n-1)维数组[数组的特点]数组中各元素都具有统一的类型可以认为，d维数组的非边界元素具有d个直接前趋和d个直接后继数组维数确定后，数据元素个数和元素之间的关系不再发生改变，适合于顺序存储每组有定义的下标都存在一个与其相对应的值[在数组上的基本操作]给定一组下标，取得相应的数据元素值读取给定一组下标，修改相应的数据元素值修改数据结构---第五章数组和广义表35.2数组的顺序存储结构[一维数组]b基地址c个单元a[1]a[2]a[i]loc(a[i])=b+(i-1)c=b-c+i*c=C0+C1*iC1=cC0=b-C1VARa:ARRAY[1..n]OFelemtp；数据结构---第五章数组和广义表4[二维数组]

a11a12a13...a1na21a22a23...a2n

::::am1am2am3...amna=mna[1,1]a[1,n]a[2,1]a[i,j]a[m,n]ba1loc(a[i,j])=b+[(i-1)*n+(j-1)]*c=C0+C1*i+C2*jC2=cC1=n*C2C0=b-C1-C2注：Pascal、C语言以行序为主序

Fortran语言以列序为主序VARa:ARRAY[1..m,1..n]OFelemtp;数据结构---第五章数组和广义表5[d维数组]loc(a[i1,i2,...,id])=C0+C1*i1+C2*i2+...+Cd*id

Cd=c;Ct-1=Ct*nt(1<td)C0=b-C1-C2-...-Cdb=loc(a[1,1,...,1])VARa:ARRAY[1..n1,1..n2,...,1..nd]OFelemtp;数据结构---第五章数组和广义表65.3特殊矩阵和稀疏矩阵的压缩存储

数组下标(i,j)存储地址5.3.1对称矩阵[特点]

在nn的矩阵a中，满足如下性质：aij=aji(1i,jn)[存储方法]

只存储下(或者上)三角(包括主对角线)的数据元素。共占用n(n+1)/2个元素空间。k=i(i-1)/2+j当ijj(j-1)/2+i当i<ja11a21a22a31aij(aji)annk1234n(n+1)/2saaji确定aij数据结构---第五章数组和广义表75.3.2三角矩阵[特点]

对角线以下(或者以上)的数据元素(不包括对角线)全部为常数c。[存储方法]

重复元素c共享一个元素存储空间，共占用n(n+1)/2+1个元素空间:sa[1..n(n+1)/2+1]

上三角矩阵下三角矩阵

k=(i-1)(2n-i+2)/2+j-i+1ijk=i(i-1)/2+jijn(n+1)/2+1i>j

n(n+1)/2+1i<jCC上三角矩阵下三角矩阵数据结构---第五章数组和广义表85.3.3带状矩阵（对角矩阵）[特点]

在nn的方阵中，非零元素集中在主对角线及其两侧共L(奇数)条对角线的带状区域内—L对角矩阵。[存储方法]以对角线的顺序存储

823000

420300

577680096915006142000283五对角矩阵

338520612827943476185962s[-2..2;1..6]-2-1012123456i1=i-jj1=j|i-j|(L-1)/2k1n*Lsak=(i1+2)*n+j1=(i-j+2)*n+j|i-j|(L-1)/2数据结构---第五章数组和广义表9只存储带状区内的元素除首行和末行，按每行L个元素，共(n-2)L+(L+1)个元素。sa[1..(n-1)L+1]

k=(i-1)L+1+(j-i)|i-j|(L-1)/2

823000

420300

577680096915006142000283823420357768969156142283sak1234567891011121314151617181920212223242526数据结构---第五章数组和广义表105.3.4稀疏矩阵[特点]

大多数元素为零。[常用存储方法]

只记录每一非零元素(i,j,aij)

节省空间，但丧失随机存取功能顺序存储：三元组表链式存储：十字(正交)链表

1500220-15011

3000000-600000000

9100000002800066数据结构---第五章数组和广义表115.3.4.1三元组表[类型定义]

CONSTu={矩阵中非零元素最大个数};TYPEtuple3p=RECORDi,j:integer;v:elemtp;END;

sparmattp=RECORDm,n,t:integer;

{m:行数;n:列数;t:非零元素数目}data:ARRAY[1..u]OFtuple3tp;END;ijv1115142216651916328数据结构---第五章数组和广义表12三元组表的结点次序一般按矩阵的行优先顺序排列矩阵转置算法示例说明在某些时候利用必要的辅助空间可以提高算法的时间效率其它的顺序存储压缩方法

带辅助行向量的二元组表示法

伪地址法

jv1154226-15222334-6191328

14677812345612345678addrv1154226-158229316-62591332812345678addr=(i-1)*n+j数据结构---第五章数组和广义表135.3.4.2十字（正交）链表[特点]

在行、列两个方向上，将非零元素链接在一起。克服三元组表在矩阵的非零元素位置或个数经常变动时的使用不便。[类型定义]TYPElink=^matnode;feature=(headnode,element);matnode=RECORDrow,col:integer;right,down:link;CASEfeatureOFheadnode:(next:link);element:(val:elemtp)END;rowcolval/nextdownright数据结构---第五章数组和广义表14结点总数：非零元素个数+max{行数，列数}+1数据结构---第五章数组和广义表15稀疏矩阵的链式存储还可以采用带行指针向量的单链表表示法行指针向量123456

115422

6-15^jvnext数据结构---第五章数组和广义表165.4广义表（列表）的定义和表示方法[概念]

广义表是由零个或多个原子或者子表组成的有限序列。可以记作：LS=(d1,d2,…,dn

)

原子：逻辑上不能再分解的元素。

子表：作为广义表中元素的广义表。[与线性表的关系]

广义表中的元素全部为原子时即为线性表。线性表是广义表的特例，广义表是线性表的推广。数据结构---第五章数组和广义表17[广义表的表示方法和相关术语]

表长表深表头表尾

A=()01--B=(a,A)=(a,())22a(())C=((a,b),c,d)32(a,b)(c,d)D=(a,D)=(a,(a,(a,…)))2a(D)表的长度：表中的元素（第一层）个数。表的深度：表中元素的最深嵌套层数。表头：表中的第一个元素。表尾：除第一个元素外，剩余元素构成的广义表。数据结构---第五章数组和广义表18[广义表的图形表达方法]

A=(a,b)abAB=(A,c)BD=(a,D)aDL=(A,B)LABabcAabc表原子数据结构---第五章数组和广义表19[规定所有表都有名字时广义表的表示方法]例A(a,b)B(A(a,b),c)L(A(a,b),B(A(a,b),c))D(a,D(a,D(…)))[广义表结构的分类]

纯表：与树型结构对应的广义表。再入表：允许结点共享的广义表。递归表：允许递归的广义表。递归表再入表纯表线性表数据结构---第五章数组和广义表205.5广义表的存储结构5.5.1方法１—头尾链表形式

[类型定义]

TYPEnodeptr=^nodetype;nodetype=RECORDtag:0..1;CASEtagOF0:(data:atomtp);1:(hp,tp:nodeptr)END;

lists1=nodeptr;tag=1hptp表结点tag=0data原子结点hp:指示表头的指针tp:指示表尾的指针数据结构---第五章数组和广义表21[示例]A=()A-NILBC11^^0a111^0c0d11^0a0b11^D0aB=(a,A)C=((a,b),c,d)D=(a,D)(A)(D)(a,b)(c,d)(d)(b)数据结构---第五章数组和广义表225.5.2方法2—扩展的线性链表形式

[类型定义]

TYPEpoint=^node;node=RECORDtag:0..1;tp:point;CASEtagOF0:(data:atomtp);1:(hp:point)END;

lists2=point;tag=1hptp表结点tag=0datatp原子结点hp:指向表头的指针tp:指向同一层的下一个结点数据结构---第五章数组和广义表23[示例]A1^^1^0aA=()1^^BB=(a,A)C=((a,b),c,d)C1^10c0d^0a0b^1^DD=(a,D)0a1^aDaA(a,b)cdab数据结构---第五章数组和广义表245.6广义表的递归算法[广义表的特点]

定义是递归的。[广义表上操作的实现]

多采用递归算法操作对象——非递归表且无共享子表把广义表分解为表头和表尾

当以头尾链表形式存储时宜把广义表看成是n个并列的子表组成的表当以扩展线性链表形式存储时宜

数据结构---第五章数组和广义表255.7例题解析判断题1.数组可以看成线性表，因此为线性表定义的基本操作也都适合于数组。2.三元组和散列是稀疏矩阵常用的两种存储方式。3.若采用三元组存储稀疏矩阵，只要将每个元素的行号和列号互换，就完成了对该矩阵的转置。4.特殊矩阵压缩存储后丧失随机存取功能。5.稀疏矩阵压缩存储后丧失随机存取功能。6.一个广义表的表尾总是一个广义表。7.一个广义表的深度与其表尾的深度一致。8.空表的表头仍是空表。9.（北邮2002）二维以上的数组其实是一种特殊的广义表。数据结构---第五章数组和广义表26填空题1.（北邮2001）用一维数组B以列优先存放带状矩阵A中的非零元素A[i，j]（1in，i-2ji+2），B中的第8个元素是A中第1行、第3列的元素。

五对角矩阵2.设广义表L=((),())，则head[L]是()；tail[L]是(())。…………………………数据结构---第五章数组和广义表27求解题1.已知三维数组A[1..6,0..7,-1..4]，每个元素占用4个字节，存储器按字节编址。已知A的起始存储位置是1024，计算

1）数组A占用的存储空间大小

2）按低下标优先存储时，A[3,5,2]的第一个字节的地址类似行优先

3）按高下标优先存储时，A[3,5,2]的第一个字节的地址类似列优先[解]1）[(6-1+1)(7-0+1)(4-(-1)+1)]4=[686]4=1152字节2）1024+[(3-1)86+(5-0)6+(2-(-1))]4=15403）1024+[(3-1)+(5-0)6+(2-(-1))86]4=1728数据结构---第五章数组和广义表282.设有nn的上三角矩阵A，其上三角的元素逐行存于数组B[1..m]中（m充分大），使得B[k]=aij，且k=f(i)+g(j)+C。试推导出函数f、g和C（要求f和g中不含常数项）。[解]

k=[n+(n-(i-2))](i-1)/2前i-1行的总元素数+(j-i+1)第i行上到j列为止的元素数=-i2+i(n+1/2)+j-n

即f(i)=-i2+i(n+1/2)g(j)=jC=-n数据结构---第五章数组和广义表293.设mn阶稀疏矩阵A有t个非零元素，其三元组表表示为LTMA[1:(t+1),1:3]，试问：非零元素的个数达到什么程度时用LTMA表示A才有意义？[解答]A矩阵本身直接存储占用空间为mn，三元组表占用空间为3(t+1),

则应有3(t+1)mn，因此tmn/3-1时，用LTMA表示A才有意义。4.利用广义表的head和tail操作将元素e从以下广义表中分离出来：L=((((a),b)),(((),d),(e,f)))

并求L的长度和深度[解答]e=head[head[tail[head[tail[L]]]]]

L的长度是2，深度是4。数据结构---第五章数组和广义表305.给出稀疏矩阵如图，画出

1）三元组表示法

2）伪地址表示法

3）带行指针向量的单链表表示法

4）十字链表示法6.已知广义表A=……，画出其两种存储结构。数据结构---第五章数组和广义表31算法题1.有二维数组A[1..m,1..n]，其元素为整型，每行每列均按从小到大有序，试给出一算法确定值为x的元素的行、列号，且要求总的比较次数不多于m+n次。设x为输入参数，它一定存在于A中。PROCsearch(A:ARRAY[1..m,1..n]OFinteger;x:integer);i:=1;j:=n;WHILEA[i,j]xDOIFA[i,j]>xTHENj:=j-1ELSEi:=i+1;write(i,j)ENDP;{search}1n1m数据结构---第五章数组和广义表322.假设稀疏矩阵Amk和Bkn采用三元组表示，设计一个算法求C=A*B，要求C也采用三元组表示。PROCmadd(A,B:sparmattp;VARC:sparmattp);p=1;FORi:=1TOA.mDO[FORj:=1TOB.nDO[c:=0;FORs:=1TOA.nDOc:=c+value(A,i,s)*value(B,s,j);]IFc0THEN[C.data[p].i:=i;C.data[p].j:=j;C.data[p].v:=c;p:=p+1];]C.m=A.m;C.n=B.n;C.t:=p-1ENDP;{madd}数据结构---第五章数组和广义表33FUNCvalue(C:sparmattp;i,j:integer);p:=1;WHILE(p<=C.tANDNOT(C.data[p].i=iANDC.data[p].j=j))DOp:=p+1;IF(p<=C.t)THENRETURN(C.data[p].v)ELSERETURN(0)ENDF;{value}数据结构---第五章数组和广义表343.若广义表以头尾链表形式存储，求广义表的深度。方法1：广义表由n个元素组成LS=（a1，a2，…，an）

1当LS为空表

depth(LS)=0当LS为单原子

1+

max{depth(ai)}n1

FUNCdepth(ls:list1):integer;IFls=nilTHENRETURN(1);IFls^.tag=0THENRETURN(0);max:=0;pp:=ls;WHILEppnilDO[dep:=depth(pp^.hp);IFdep>maxTHENmax:=dep;pp:=pp^.tp;]RETURN(max+1);ENDF;{depth}数据结构---第五章数组和广义表35方法2：分析表头和表尾

1当LS为空表

depth(LS)=0当LS为单原子

max{depth(head(LS)+1,depth(tail(LS))}其它情况

FUNCdepth(ls:list1):integer;IFls=NILTHENRETURN(1);{空表}

IFls.tag=0THENRETURN(0);{单原子}

dep1:=depth(ls.hp)+1;dep2:=depth(ls.tp);IFdep1>dep2THENRETURN(dep1)ELSERETURN(dep2)ENDF;{depth}数据结构---第五章数组和广义表364.若广义表以扩展线性链表形式存储，求广义表的深度。广义表由n个元素组成LS=（a1，a2，…，an）

1当LS为空表

depth(LS)=0