数据结构讲义

数据结构讲义第1页，共67页，2023年，2月20日，星期六第2页，共67页，2023年，2月20日，星期六

5.1 数组的定义

5.2 数组的顺序表示和实现

5.3 矩阵的压缩存储

5.4 广义表的定义

5.5 广义表的存储结构

**5.6m元多项式的表示

**5.7广义表的递归算法

目录第五章数组和广义表第3页，共67页，2023年，2月20日，星期六5.1 数组的定义

数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数据元素本身也是一种线性表。数组的定义

几乎所有的程序设计语言都把数组类型设定为固有类型。数组也是我们最熟悉的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。第4页，共67页，2023年，2月20日，星期六以抽象数据类型的形式讨论数组的定义和实现，可以让我们加深对数组类型的理解。数组的抽象数据类型定义：ADTArray{数据对象:ji=0,...,bi-1,i=1,2,...,n;D={aj1j2...jn|n(>0)称为数组的维数,bi是数组第i维的长度,ji是数组元素的第i维下标,aj1j2...jn(-ElemSet}数据关系:R={R1,R2,...Rn}Ri={<aj1...ji...jn,aj1...ji+1...jn>|0<=jk<=bk-1,1<=k<=n且k<>i,0<=ji<=bi-2,aj1...ji...jn,aj1...ji+1…jn(-D,i=2,...n}第5页，共67页，2023年，2月20日，星期六基本操作:InitArray(&A,n,bound1,...,boundn)若维数和各维长度合法,则构造相应的数组A,并返回OK.DestroyArray(&A)操作结果:销毁数组A.Value(A,&e,index1,...,indexn)初始条件:A是n维数组,e为元素变量,随后是n个下标值.操作结果:若各下标不超界,则e赋值为所指定的A的元素值,并返回OK.Assign(&A,e,index1,...,indexn)初始条件:A是n维数组,e为元素变量,随后是n个下标值.操作结果:若下标不超界,则将e的值赋给所指定的A的元素,并返回OK.}ADTArray第6页，共67页，2023年，2月20日，星期六多维数组是一维数组的推广。例如，二维数组：a11a12

…a1nA1a21a22

…a2nA2

…

…

…

…am1am2

…amnAnAmn=见书P91页图5.1第7页，共67页，2023年，2月20日，星期六所以数组可以看成是由行向量组成的线性表，也可以看成是个列向量组成的线性表。在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，typedefelemtypearray2[m][n];等价于：typedefelemtypearray1[n];typedefarray1array2[m];同理，一个N维数组类型可以定义为其数据元素为N-1维数组类型的一维序组类型。数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。第8页，共67页，2023年，2月20日，星期六5.2 数组的顺序表示和实现由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。通常有两种顺序存储方式：⑴行优先顺序——将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn

在PASCAL、C语言中，数组就是按行优先顺序存储的。⑵列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线性序列为：a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm在FORTRAN语言中，数组就是按列优先顺序存储的。第9页，共67页，2023年，2月20日，星期六以上规则可以推广到多维数组的情况：优先顺序可规定为先排最右的下标，从右到左，最后排最左下标：列优先顺序与此相反，先排最左下标，从左向右，最后排最右下标。按上述两种方式顺序存储的序组，只要知道开始结点的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。例如，二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占用d个存储单元。元素aij的存储地址应是数组的基地址加上排在aij前面的元素所占用的单元数。因为aij位于第i行、第j列，前面i-1行一共有(i-1)×n个元素，第i行上aij前面又有j-1个元素，故它前面一共有(i-1)×n+j-1个元素，因此，aij的地址计算函数为：LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d同样，三维数组Aijk按“行优先顺序”存储，其地址计算函数为：LOC(aijk)=LOC(a111)+[(i-1)*n*p+(j-1)*p+(k-1)]*d第10页，共67页，2023年，2月20日，星期六将上述的式子推广到一般情况，可得到n维数组的数据元素存储位置的计算公式：

LOC(j1,j2,…,jn)=LOC(0,0,…,0)+(b2…bnj1+b3…bnj2+…+bnjn-1+jn)L=LOC(0,0,…,0)+=LOC(0,0,…,0)+

上式就称为n维数组的映象函数。容易看出，数组元素的存储位置是其下标的线性函数，一旦确定了数组的各维的长度,Ci就是常数。

第11页，共67页，2023年，2月20日，星期六数组的顺序存储表示和实现:#include<stdarg.h>#defineMAX_ARRAY_DIM8typedefstruct{ElemType*base;//数组元素基址，由InitArray分配intdim;//数组维数int*bounds;//数组维界基址，由InitArray分配int*constants;//数组映象函数常量基址，由InitArray分配}Array;StatusInitArray(Array&A,intdim,...);StatusDestroyArray(Array&A);StatusValue(ArrayA,ElemType&e,...);StatusAssign(Array&A,ElemTypee,...);第12页，共67页，2023年，2月20日，星期六基本操作的算法描述:StatusInitArray(Array&A,intdim,...){if(dim<1||dim>MAX_ARRAY_DIM)returnERROR;A.dim=dim;A.bounds=(int*)malloc(dim*sizeof(int));if(!A.bounds)exit(OVERFLOW);elemtotal=1;va_start(ap,dim);for(i=1;i<dim;++i){A.bounds[i]=va_arg(ap,int);if(A.bounds[i]<0)returnUNDERFLOW;}第13页，共67页，2023年，2月20日，星期六elemtotal*=A.bounds[i];va_end(ap);A.base=(ElemType*)malloc(elemtotal*sizeof(ElemType));if(!A.base)exit(OVERFLOW);A.constants=(int*)malloc(dim*sizeof(int));if(!A.constants)exit(OVERFLOW);A.constants[dim-1]=1;for(i=dim-2;i>=0;--i)A.constants[i]=A.bounds[i+1]*A.constants[i+1];returnOK;}第14页，共67页，2023年，2月20日，星期六StatusDestoyArray(Array&A){if(!A.base)returnERROR;free(A.base);A.base=NULL;if!(A.bounds)returnERROR;free(A.bounds);A.bounds=NULL;if!(A.constatns)returnERROR;free(A.constants);A.constants=NULL;returnOK;}第15页，共67页，2023年，2月20日，星期六StatusLocate(ArrayA,va_listap,int&off){off=0;for(i=0;i<A.dim;++i){ind=va_arg(ap,int);if(ind<0||ind>=A.bounds[i])returnOVERFLOW;off+=A.constants[i]*ind;}returnOK;}第16页，共67页，2023年，2月20日，星期六StatusValue(ArrayA,ElemType&e,...){va_start(ap,e);if((result=Locate(A,ap,off))<=0returnresult;e=*(A.base+off);returnOK;}第17页，共67页，2023年，2月20日，星期六StatusAssign(Array&A,ElemTypee,...){va_start(ap,e);if((result=Locate(A,ap,off))<=0)returnresult;*(A.base+off)=e;returnOK;}第18页，共67页，2023年，2月20日，星期六5.3 矩阵的压缩存储在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。第19页，共67页，2023年，2月20日，星期六特殊矩阵

所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。1、对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji0≦i,j≦n-1则称A为对称矩阵。如图5.1便是一个5阶对称矩阵。

对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示：第20页，共67页，2023年，2月20日，星期六15137a0050800a10a1118926a20a21a2330251………………..70613an-10an-11an-12

…an-1n-1

图5.1对称矩阵对于对称矩阵，我们可以为每一对对称元分配一个存储空间，则可将n2个元压缩存储到n(n+1)/2个元的空间中。因此，我们可以上图所指的次序将这些元素存放在一个向量sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵A中的元素，我们必须在aij和sa[k]之间找一个对应关系。

第21页，共67页，2023年，2月20日，星期六a00a10a11a20……an-1,0…..an-1,n-1k=0123n(n-1)/2n(n+1)/2-1123n1a002a10a113a20a21a22………………..nan-10an-11an-12

…an-1n-1

当i>=jk=当i<jaiji>=ji<j第22页，共67页，2023年，2月20日，星期六2、三角矩阵以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。a00a01

…a0n-1a00c…cca11

…a1n-1a10a11

…c

…..……………..cc…an-1n-1an-10an-11

…an-1n-1

(a)上三角矩阵(b)下三角矩阵

图5.2三角矩阵第23页，共67页，2023年，2月20日，星期六3.对角矩阵对角矩阵中，所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵，a00a01a10a11a12a21a22a23

….…..…. an-2n-3an-2n-2an-2n-1an-1n-2an-1n-1

图5.3对角矩阵

对这种矩阵我们亦可按某个原则（或以行为主，或以对角线的顺序）将其压缩存储到一维数组上。第24页，共67页，2023年，2月20日，星期六非零元素仅出现在主对角(aii,0≦i≦n-1上，紧邻主对角线上面的那条对角线上(aii+1,0≦i≦n-2)和紧邻主对角线下面的那条对角线上(ai+1i,0≦i≦n-2)。显然，当∣i-j∣>1时，元素aij=0。由此可知，一个k对角矩阵(k为奇数)A是满足下述条件的矩阵：若∣i-j∣>(k-1)/2，则元素aij=0。对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。

在三对角矩阵里附满足条件i=0，j=0、1，或i=n-1j=n-2、n-1或1<i<n-1,j=i-1、i、i+1的元素aij外，其余元素都是零。对这种矩阵，我们也可按行优序为主序来存储。除第0行和第n-1行是2个元素外，每行的非零元素都要是3个，因此，需存储的元素个数为3n-2。3(n-2)+2+2=3n-2第25页，共67页，2023年，2月20日，星期六an-1n-1an-1n-2……a21

a12a11a10a01

a00K=012345……3n-23n-1数组sa中的元素sa[k]与三对角带状矩阵中的元素aij存在一一对应关系，在aij之前有i行,共有3*i-1个非零元素，在第i行，有j-i+1个非零元素，这样，非零元素aij的地址为：

LOC(i,j)=LOC(0,0)+[3*i-1+(j-i+1)]*d=LOC(0,0)+(2i+j)*d上例中，a34对应着sa[10]。k=2*i+j=2*3+4=10a21对应着sa[5]k=2*2+1=5由此，我们称sa[0..3*n-2]是阶三对角带状矩阵A的压缩存储表示。第26页，共67页，2023年，2月20日，星期六上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。第27页，共67页，2023年，2月20日，星期六稀疏矩阵

什么是稀疏矩阵？简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即s≦m×n），则称A为稀疏矩阵。

精确点，设在的矩阵A中，有s个非零元素。令e=s/(m*n)，称e为矩阵的稀疏因子。通常认为e≦0.05时称之为稀疏矩阵。第28页，共67页，2023年，2月20日，星期六矩阵运算的种类很多，在下列抽象数据类型稀疏矩阵的定义中，只列举了几种常见的运算：ADTSparseMatrix{数据对象：D={aij|i=1,2,…,m;j=1,2,…,n;aij

ElemSet,m和n分别称为矩阵的行数和列数。}数据关系：R={Row,Col}Row={<aij,aij+1>|1<=i<=m,1<=j<=n-1}Col={<aij,ai+1j>|1<=i<=m-1,1<=j<=n}基本操作：CreateSMatrix(&M);操作结果：创建稀疏矩阵M。DestroySMatrix(&M);初始条件：稀疏矩阵M存在。操作结果：销毁稀疏矩阵M。第29页，共67页，2023年，2月20日，星期六PrintSMatrix(M);初始条件：稀疏矩阵M存在。操作结果：输出稀疏矩阵M。CopySMatrix(M,&T);初始条件：稀疏矩阵M存在。操作结果：由稀疏矩阵M复制得到T。AddSMatrix(M,N,&Q);初始条件：稀疏矩阵M与N的行数和列数对应相等。操作结果：求稀疏矩阵的和Q=M+N。SubtMatrix(M,N,&Q);初始条件：稀疏矩阵M与N的行数和列数对应相等。操作结果：求稀疏矩阵的差Q=M-N。MultSMatrix(M,N,&Q);初始条件：稀疏矩阵M的列数等于N的行数。操作结果：求稀疏矩阵的积Q=M*N。TransposeSMatrix(M,&T);初始条件：稀疏矩阵M存在。操作结果：求稀疏矩阵M的转置矩阵T。}ADTSparseMatrix第30页，共67页，2023年，2月20日，星期六在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。如何进行稀疏矩阵的压缩存储呢？按照压缩存储的概念，只存储稀疏矩阵的非零元。但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)。反之，用一个三元组(i,j,aij)唯一确定了矩阵A的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。第31页，共67页，2023年，2月20日，星期六例如，下列三元组表((1,2,12)(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))加上(6,7)这一对行、列值便可作为下列矩阵M的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法

1234567

0129000000-30015000000012000180-3000014090024000024000000000–70180000000140001500–7000000000000000图5.4稀疏矩阵M和TM=T=123456第32页，共67页，2023年，2月20日，星期六1.三元组顺序表

假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法——三元顺序表。#definemaxsize12500//假设非零元个数的最大值为12500typedefstruct{inti,j;//该非零元的行下标和列下标ElemTypee;}Triple;typedefstruct{tripledata[maxsize+1];//非零元三元组表intm,n,t;//矩阵的行数、行数和非零无个数}TSMatrix;第33页，共67页，2023年，2月20日，星期六设A为TSMatrix型的结构变量，图5.4中所示的稀疏矩阵的三元组的表示如下：ije1212data[1]139data[2]31-3data[3]3614data[4]4324data[5]5218data[6]6115data[7]64-7data[8]A.mu=6A.nu=7A.tu=8在此，data域中表示非零元的三元组是以行序为主序顺序排列的。第34页，共67页，2023年，2月20日，星期六下面以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。

一个m×n的矩阵A，它的转置B是一个n×m的矩阵，且a[i][j]=b[j][i]，0≦i≦m，0≦j≦n，即A的行是B的列，A的列是B的行。

将A转置为B，就是将A的三元组表a.data置换为表B的三元组表b.data，如果只是简单地交换a.data中i和j的内容，那么得到的b.data将是一个按列优先顺序存储的稀疏矩阵B，要得到按行优先顺序存储的b.data，就必须重新排列三元组的顺序。

由于A的列是B的行，因此，按a.data的列序转置，所得到的转置矩阵B的三元组表b.data必定是按行优先存放的。第35页，共67页，2023年，2月20日，星期六按这种方法设计的算法，其基本思想是：对A中的每一列col(0≦col≦n-1)，通过从头至尾扫描三元表a.data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放入b.data中，即可得到B的按行优先的压缩存储表示。ije13-3data[1]1615data[2]2112data[3]2518data[4]319data[5]3424data[6]46-7data[7]6314data[8]ije

1212data[1]139data[2]31-3data[3]3614data[4]4324data[5]5218data[6]6115data[7]64-7data[8]ABA.mu=6A.nu=7A.tu=8B.mu=7B.nu=6A.tu=8第36页，共67页，2023年，2月20日，星期六StatusTransposeSMatrix(TSMatrixA,TSMatrix&B){//采用三元组表存储表示，求稀疏矩阵A的转置矩阵B。B.mu=A.nu;B.nu=A.mu;B.tu=A.tu;if(B.tu){q=1;for(col=1;col<=A.nu;++col)for(p=1;p<=A.tu;++p)if(A.data[p].j==col){B.data[q].i=A.data[p].j;B.data[q].j=A.data[p].i;B.data[q].e=A.data[p].e;++q;}}returnOK;}P书99页算法5.1看演示!第37页，共67页，2023年，2月20日，星期六分析这个算法，主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(nu*tu)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为：for(col=0;col<=n-1;++col)for(row=0;row<=m;++row)t[col][row]=m[row][col];其时间复杂度为O(n*m)。当非零元素的个数tu和m*n同数量级时，算法transmatrix的时间复杂度为O(nu*n2)。三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算是法的难度。因此，此算法仅适用于tu<=m*n的情况。第38页，共67页，2023年，2月20日，星期六下面给出另外一种称之为快速转置的算法，其算法思想为：按照a.data中三元组的次序进行转置，并将转置后的三元组置入b中恰当的位置。如果能预先确定矩阵A中每一列（即B中每一行）的第一个非零元在B.data中应有的位置，那么在对a.data中的三元组依次作转置时，便可直接放到b.data中恰当的位置上去。为了确定这些位置，在转置前，应先求得A的每一列中非零元的个数（因为：矩阵A中每一列的第一个非零元素在数组B中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。），进而求得每一列的第一个非零元在b.data中应有的位置。为此，需要设置两个一维数组num[0..n]和cpot[0..n]num[0..n]：统计矩阵A中每列非零元素的个数.cpot[0..n]：由递推关系得出M中的每列第一个非零元素在B中的位置。第39页，共67页，2023年，2月20日，星期六算法通过cpot数组建立位置对应关系：cpot[1]=1cpot[col]=cpot[col-1]+num[col-1]2<=col<=a.nu例如：图5.4中的矩阵M和相应的三元组A可以求得num[col]和cpot[col]的值如下：col 1234567num[col] 2221010cpot[col] 1357889ije

1212data[1]139data[2]31-3data[3]3614data[4]4324data[5]5218data[6]6115data[7]64-7data[8]AA.mu=6A.nu=7A.tu=8见演示!第40页，共67页，2023年，2月20日，星期六快速转置算法如下：StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){//采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵B。T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;++col)O(nu)num[col]=0;for(t=1;t<=M.tu;++t)O(tu)++num[M.data[t].j];//求M中每一列含非零元个数cpot[1]=1;

第41页，共67页，2023年，2月20日，星期六//求第col列中第一个非零元在b.data中的序号for(col=2;col<=M.nu;++col)O(nu)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=M.tu;++p)O(tu){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];}//for}//if

O(nu+tu)如果tu=mu*muretrunOk;O(mu*mu)}//FastTransposeSMatrix第42页，共67页，2023年，2月20日，星期六三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需按行号存取某一行的非零元，则需从头开始进行查找。ije

1212data[1]139data[2]31-3data[3]3614data[4]4324data[5]5218data[6]6115data[7]64-7data[8]第43页，共67页，2023年，2月20日，星期六2.行逻辑链接的顺序表为了便于随机存取任意一行的非零元，则需知道每一行的第一个非零元在三元组表中的位置。为此，可将上节快速转置矩阵的算法中创建的，指示“行”信息的辅助数据cpot固定在稀疏矩阵的存储结构中。称这种“带行链接信息”的三元组表为行逻辑链接的顺序表。

我们就得到了稀疏矩阵的另一种顺序存储结构：带行链接的三元组表。其类型描述如下：#definemaxrow100typedefstruct{Tripledata[maxsize+1];//非零元三元组表intrpos[maxro+1];//各行第一个非零元的位置表intn,m,t;//矩阵的行数、列数和非零元个数}RLSMatrix;下面讨论两个稀疏矩阵相乘的例子，容易看出这种表示方法的优越性。第44页，共67页，2023年，2月20日，星期六两个矩阵相乘的经典算法也是大家所熟悉的。若设Q=M*N其中，M是m1*n1矩阵，N是m2*n2矩阵。当n1=m2时有：for(i=1;i<=m1;++i)for(j=1;j<=n2;++j){q[i][j]=0；for(k=1;k<=n1;++k)q[i][j]+=m[i][k]*n[k][j];}此算法的复杂度为O(m1*n1*n2)。第45页，共67页，2023年，2月20日，星期六当M和N是稀疏矩阵并用三元组表存储结构时，就不能套用上述算法。假设M和N分别为：