资源简介 (共52张PPT)第五章 数组和广义表5.1 数组的定义5.2 数组的顺序表示和实现5.3 矩阵的压缩存储5.3.1 特殊矩阵5.3.2 稀疏矩阵5.4 广义表的定义5.5 广义表的存储结构数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数所元素本身也是一种线性表。5.1 数组的定义数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：a11 a12 … a1na21 a22 … a2n… … … …am1 am2 … amnAmn=可以看成是由个行向量组成的向量，也可以看成是个列向量组成的向量。在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，typedef elemtype array2[m][n];等价于：typedef elemtype array1[n];typedef array1 array2[m];同理，一个维数组类型可以定义为其数据元素为维数组类型的一维序组类型。数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。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语言中，数组就是按列优先顺序存储的。以上规则可以推广到多维数组的情况：优先顺序可规定为先排最右的下标，从右到左，最后排最左下标：列优先顺序与此相反，先排最左下标，从左向右，最后排最右下标。按上述两种方式顺序存储的序组，只要知道开始结点的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。例如，二维数组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上述讨论均是假设数组各维的下界是不是1，更一般的二维数组是A[c1..d1,c2..d2]，这里c1,c2不一定是1。aij前一共有i-c1行，二维数组一共有d2-c2+1列，故这i-c1行共有(i-c1)*(d2-c2+1)个元素，第i行上aij前一共有j-c2个元素，因此，aij的地址计算函数为：LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+j-c2)]*d例如，在C语言中，数组各维下标的下界是0，因此在C语言中，二维数组的地址计算公式为：LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d5.3 矩阵的压缩存储在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间， 我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。5.3.1特殊矩阵所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。1、对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji 0≦i,j≦n-1则称A为对称矩阵。如图5.1便是一个5阶对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示：1 5 1 3 7 a005 0 8 0 0 a10 a 111 8 9 2 6 a20 a21 a233 0 2 5 1 ………………..7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 …a n-1 n-1图 5.1 对称矩阵在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为：(i+1)=n(n+1)/2因此，我们可以按图中箭头所指的次序将这些元素存放在一个向量sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵A中的元素，我们必须在aij和sa[k]之间找一个对应关系。若i≧j，则ai j在下三角形中。 ai j之前的i行（从第0行到第i-1行）一共有1+2+…+i=i(i+1)/2个元素，在第i行上， ai j之前恰有j个元素（即ai0,ai1,ai2,…,aij-1），因此有：k=i*(i+1)/2+j 0≦k若ik=j*(j+1)/2+i 0≦ k令 I=max(i,j)， J=min(i,j)，则k和 i, j的对应关系可统一为：k=I*(I+1)/2+J 0≦ k因此，aij的地址可用下列式计算：LOC(aij)=LOC(sa[k])=LOC(sa[0])+k*d=LOC(sa[0]+[I*(I+1)/2+J]*d有了上述的下标交换关系，对于任意给定一组下标(i，j)，均可在sa[k]中找到矩阵元素aij，反之，对所有的k=0,1,2,…n(n-1)/2-1，都能确定sa[k]中的元素在矩阵中的位置(i,j)。由此，称sa[n(n+1)/2]为阶对称矩阵A的压缩存储，见下图：k=0 1 2 3 n(n-1)/2 n(n-1)/2-1例如a21和a12均存储在 sa[4]中，这是因为k=I*(I+1)/2+J=2*(2+1)/2+1=4a00 a10 a11 a20 …… an-1 0 …… an-1,n-12、三角矩阵以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。a00 a01 … a 0 n-1 a00 c … cc a11 … a 1 n-1 a10 a11 … c………………….. ……………..c c … a n-1 n-1 an-1 0 an-1 1 … an-1 n-1(a)上三角矩阵 (b)下三角矩阵图5.2 三角矩阵三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa[0..n(n+1)/2]中，其中c存放在向量的最后一个分量中，上三角矩阵中，主对角线之上的第p行(0≦p(n-p)=i(2n-i+1)/2个元素，在第i行上，aij前恰好有j-i个元素：aij,aij+1,…aij-1。因此，sa[k]和aij的对应关系是：i(2n-i+1)/2+j-i 当i≦jn(n+1)/2 当i>jk=下三角矩阵的存储和对称矩阵类似，sa[k]和aij对应关系是：i(i+1)/2+j i≧jn(n+1)/2 i>j3、对角矩阵对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵，a00 a01a10 a11 a12a21 a22 a23…. ….. …. 图5.3 对角矩阵an-2 n-3 an-2 n-2 an-2 n-1an-1 n-2 an-1 n-1k=非零元素仅出现在主对角(aii,0≦i≦n-1上，紧邻主对角线上面的那条对角线上(aii+1,0≦i≦n-2)和紧邻主对角线下面的那条对角线上(ai+1 i,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对这种矩阵，我们也可按行优序为主序来存储。除第0行和第n-1行是2个元素外，每行的非零元素都要是3个，因此，需存储的元素个数为3n-2。a00 a01 a10 a11 a12 a21 … … a n-1 n-2 a n-1 n-1K=0 1 2 3 4 5 … … 3n-2 3n-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的压缩存储表示。上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。5.3.2 稀疏矩阵什么是稀疏矩阵？简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即s≦m×n），则称A为稀疏矩阵。精确点，设在的矩阵A中，有s个非零元素。令 e=s/(m*n)，称e为矩阵的稀疏因子。通常认为e≦0.05时称之为稀疏矩阵。在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)。反之，一个三元组(i,j,aij)唯一确定了矩阵A的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。例如，下列三元组表((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的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。0 12 9 0 0 0 0 0 0 -3 0 0 150 0 0 0 0 0 0 12 0 0 0 18 0-3 0 0 0 0 14 0 9 0 0 24 0 00 0 24 0 0 0 0 0 0 0 0 0 –70 18 0 0 0 0 0 0 0 14 0 0 015 0 0 –7 0 0 0 0 0 0 0 0 00 0 0 0 0 0图5.4 稀疏矩阵M和TM=T=一、三元组顺序表假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法——三元顺序表。#define maxsize 10000typedef int datatype;typedef struct{int i,j;datatype v;}triple;typedef struct{triple data[maxsize];int m,n,t;}tripletable;设A为tripletable型的结构变量，图5.4中所示的稀疏矩阵的三元组的表示如下：i j v1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7下面以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。一个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必定是按行优先存放的。按这种方法设计的算法，其基本思想是：对A中的每一列 col(0≦col≦n-1)，通过从头至尾扫描三元表a.data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放入b.data中，即可得到B的按行优先的压缩存储表示。i j v1 3 -31 6 152 1 122 5 183 1 93 4 244 6 -76 3 14Void transmatrix(tripletable a,tripletable b){int p q col;b.m=a.n;b.n=a.m;b.t=a.t;if(b.t<=0)printf(“A=0\n”);q=0;for(col=1;col<=a.n;col++)for(p=0;p<=a.t;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].v=a.data[p].v;q++;}}分析这个算法，主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(n*t)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为：for(col=0;col<=n-1;++col)for(row=0;row<=m;++row)t[col][row]=m[row][col];其时间复杂度为O(n*m)。当非零元素的个数t和m*n同数量级时，算法transmatrix的时间复杂度为O(n*n2)。三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算是法的难度。因此，此算法仅适用于t<=m*n的情况。下面给出另外一种称之为快速转置的算法，其算法思想为：对A扫描一次，按A第二列提供的列号一次确定位置装入B的一个三元组。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。为了预先确定矩阵M中的每一列的第一个非零元素在数组B中应有的位置，需要先求得矩阵M中的每一列中非零元素的个数。因为：矩阵M中第一列的第一个非零元素在数组B中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。为此，需要设置两个一维数组num[0..n]和cpot[0..n]num[0..n]：统计M中每列非零元素的个数，num[col]的值可以由A的第二列求得。cpot[0..n]：由递推关系得出M中的每列第一个非零元素在B中的位置。算法通过cpot数组建立位置对应关系：cpot[1]=1cpot[col]=cpot[col-1]+num[col-1]2<=cpl<=a.n例如：图5.4中的矩阵M和相应的三元组A可以求得num[col]和 cpot[col]的值如下：col 1 2 3 4 5 6 7num[col] 2 2 2 1 0 1 0cpot[col] 1 3 5 7 8 8 91 2 vq …A i j v第一列元素个数第二列元素个数第三列元素个数numcpotq=cpot[col]2 1 vpp快速转置算法如下：void fasttranstri(tritupletable b,tritupletable a){int p,q,col,k;int num[0..a.n],copt[0..a.n];b.m=a.n; b.n=a.m; b.t=a.t;if(b.t<=0)printf(“a=0”\n);for(col=1;col<=a.u;++col)num[col]=0;for(k=1;k<=a.t;++k)++num[a.data[k].j];cpot[0]=1;for(col=2;col<=a.t;++col)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=a.t;++p){col=a.data[p].j; q=cpot[col];b.data[q].i=a.data[p].j; b.data[q].j=a.data[p].i;b.data[q].v=a.data[p].v; ++cpot[col];}}}二、带行表的三元组有时为了方便某些矩阵运算，我们在按行优先存储的三元组中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。当将行表作为三元组表的一个新增属性加以描述时，我们就得到了稀疏矩阵的另一种顺序存储结构：带行表的三元组表。其类型描述如下：#define maxrow 100typedef struct{triple data[maxsize];int rpos[maxrow];int n,m,t;}rtripletable下面讨论两个稀疏矩阵相乘的例子，容易看出这种表示方法的优越性。两个矩阵相乘的经典算法也是大家所熟悉的。若设 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]=0for(k=1;k<=n1;++k)q[i][j]+=m[i][k]*n[k][j];}此算法的复杂度为O(m1*n1*n2)。当M和N是稀疏矩阵并用三元组表存储结构时，就不能套用上述算法。假设M和N分别为：0 0 50 -1 0 02 0 0 0M=0 21 0-2 40 0N=则Q=M*N为：0 6-1 00 4Q=它们的三元组、和分别为：i j v i j v i j v1 1 3 1 2 2 1 2 61 4 5 2 1 1 2 1 -13 2 -1 3 1 -2 3 2 43 1 2 3 2 4 q.datam.data n.data稀疏矩阵相乘的基本思想是：对于M中每个元素M，找到N 中所有满足条件的元素，求得和的乘积，而从式得知，乘积矩阵Q中每个元素的值是个累加和，这个乘积只是中的一部分。为了便于操作，应对每个元素设一累加和的变量，其初值为零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。void multsmatrix( rtripletable a,rtripletable b,rtripletable c){if(a.n!=b.m){printf(“error\n”); exit(0);}c.m=a.m; c.n=b.n; c.t=0;if(a.t*b.t!=0){for(arow=1;arow<=a.m;++arow){ctemp[arow]=0;c.rpos[arow]=c.t+1;for(p=a.rops[arow];pbrow=a.data[p].j;if(browelse t=b.t+1;for(q=b.rpos[brow]; qccol=n.data[q].j;ctemp[ccol]+=a.data[p].v*b.data[q].v;}}for(ccol=1;ccol<=c.n;++ccol)if(ctemp[ccol]){if(++c.t>maxsize)exit(0);c.data[c.t]={arow,ccol,ctemp[ccol]};}}}}5.4 广义表的定义广义表（Lists，又称列表）是线性表的推广。在第2章中，我们把线性表定义为n>=0个元素a1,a2,a3,…,an的有限序列。线性表的元素仅限于原子项，原子是作为结构上不可分割的成分，它可以是一个数或一个结构，若放松对表元素的这种限制，容许它们具有其自身结构，这样就产生了广义表的概念。广义表是n(n>=0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。通常记作LS=（a1,a2,a3,…,an)。LS是广义表的名字，n为它的长度。若ai是广义表，则称它为LS的子表。通常用圆括号将广义表括起来，用逗号分隔其中的元素。为了区别原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。若广义表LS（n>=1)非空，则a1是LS的表头，其余元素组成的表(a1,a2,…an)称为LS的表尾。显然广义表是递归定义的，这是因为在定义广义表时又用到了广义表的概念。广义表的例子如下：（1）A=（）——A是一个空表，其长度为零。（2）B=（e）——表B只有一个原子e，B的长度为1。（3）C=（a,(b,c,d))——表C的长度为2，两个元素分别为原子a和子表(b,c,d)。（4）D=（A，B，C）——表D的长度为3，三个元素都是广义表。显然，将子表的值代入后，则有D=(( ),(e),(a,(b,c,d)))。（5）E=（E）——这是一个递归的表，它的长度为2，E相当于一个无限的广义表E=(a,(a,(a,(a,…)))).从上述定义和例子可推出广义表的三个重要结论：（1）广义表的元素可以是子表，而子表的元素还可以是子表，。由此，广义表是一个多层次的结构，可以用图形象地表示。P108（2）广义表可为其它表所共享。例如在上述例（4）中，广义表A，B，C为D的子表，则在D中可以不必列出子表的值，而是通过子表的名称来引用。（3）广义表的递归性。综上所述，广义表不仅是线性表的推广，也是树的推广。由表头、表尾的定义可知：任何一个非空广义表其表头可能是广义表，也可能是广义表，而其表尾必定是广义表。gethead(B)=e gettail(B)=( )gethead(D)=A gettail(D)=(B,C)由于（B，C）为非空广义表，则可继续分解得到：gethead(B,C)=B gettail(B,C)=(C)注意广义表（ ）和( ( ) )不同。前者是长度为0的空表，对其不能做求表头的和表尾的运算；而后者是长度为1的非空表（只不过该表中唯一的一个元素是空表）。对其可进行分解，得到表头和表尾均为空表（ ）。5.5 广义表的存储结构由于广义表(a1,a2,a3,…an)中的数据元素可以具有不同的结构，（或是原子，或是广义表），因此，难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个结点表示。由于广义表中有两种数据元素，原子或广义表，因此，需要两种结构的结点：一种是表结点，一种是原子结点。 下面介绍两种广义表的链式存储结构。1、表结点由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；而原子域只需两个域：标志域和值域。表结点 原子结点tag=1 hp tptag=0 atom其类型定义如下：typedef enum{ATOM,LIST}elemtag;typedeg struct glnode{elemtag tag;union{atomtype atom;struct {struct glnode *hp,*tp;}ptr;};} *glist;例见书P109。2、表结点由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；原子结点的三个域为：标志域、值域和指示表尾的指针域。tag=1hptptag=0 atom tp表结点 原子结点其类型定义如下：typedef enum{atom,list}elemtag;Typedef struct glnode{elemtag tag;union{atomtype atom;struct glnode *hp;};struct glnode *tp;} *glist;例见书P110(共24张PPT)第一章 绪 论计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示信息的处理而信息的表示和组又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。1.1什么是数据结构众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下几个例子。例1、电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1，b1)(a2，b2)…(an，bn)其中ai，bi(i=1，2…n) 分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。数据的结构，直接影响算法的选择和效率。上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)， 1≤i≤n数据结构还要提供每种结构类型所定义的各种运算的算法。例2、图书馆的书目检索系统自动化问题例3、教师资料档案管理系统例4、多叉路口交通灯的管理问题通过以上几例可以直接地认为：数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。1.2 基本概念和术语数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。数据结构主要指逻辑结构和物理结构数据之间的相互关系称为逻辑结构。通常分为四类基本结构：一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构 结构中的数据元素之间存在一对一的关系。三、树型结构 结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。数据结构的形式定义为：数据结构是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。例 复数的数据结构定义如下：Complex=(C，R)其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部。R={P}，P是定义在集合上的一种关系{〈C1，C2〉}。数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。数据对象可以是有限的，也可以是无限的。 数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。抽象数据类型：一个数学模型以及定义在该模型上的一组操作。 抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。 用三元组描述如下： （Ｄ，Ｓ，Ｐ）数据结构在计算机中有两种不同的表示方法：顺序表示和非顺序表示由此得出两种不同的存储结构：顺序存储结构和链式存储结构顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个存放地址的指针（ ），用此指针来表示数据元素之间的逻辑关系。数据类型：在一种程序设计语言中，变量所具有的数据种类。例1、 在FORTRAN语言中，变量的数据类型有整型、实型、和复数型例2、在C语言中数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义数据对象：某种数据类型元素的集合。例3、整数的数据对象是{…-3，-2，-1，0，1，2，3，…}英文字符类型的数据对象是{A，B，C，D，E，F，…}1.3 抽象数据类型的表示和实现抽象数据类型通常是指由用户定义，用以表示应用问题的数据类型，抽象数据类型由基本的数据类型组成，并包括一组相关的服务（或称操作）。抽象数据类型有些类似于pascal语言中的记录(record)类型和c语言中的构造(struct)类型，但它增加了相关的服务。在计算机中使用二进制定点数和浮点数实现数据的存储和运算，而在汇编中给出数据的自然表示，到了高级语言，给出了更高一级的数据抽象，出现了整形、实型、字符型、双精度行。待到抽象数据类型出现时，可以进一步定义出更高级的数据抽象。如各种表、队列、图、甚至窗口、管理器等。抽象数据类型的特征是使用和实现分离，实行封装和信息隐蔽。下面我们给出自然数(natural number)的抽象数据类型定义：ADT naturalnumber isObjects:Function:Zero():naturalnumberIszero(x):booleanAdd(x,y):nuturalnumberEqual(x,y):booleanSuccessor(x):naturalnumberSubtract(x,y):naturalnumberEnd naturalnumber1.4 算法和算法分析算法：是对特定问题求解步骤的一种描述算法是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下五个特性：（1）有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。（2）确定性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。（3）可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。4）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。5）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。1.4.2 算法设计的要求评价一个好的算法有以下几个标准:(1) 正确性(Correctness ) 算法应满足具体问题的需求。(2)可读性(Readability) 算法应该好读。以有利于阅读者对程序的理解。(3)健状性(Robustness) 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。(4)效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。1.4.3 算法效率的度量对一个算法要作出全面的分析可分成两用人才个阶段进行，即事先分析和事后测试事先分析 求出该算法的一个时间界限函数事后测试 收集此算法的执行时间和实际占用空间的统计资料。定义：如果存在两个正常数c和n0，对于所有的n≧n0，有︱f(n) ︳≦c｜g(n) ︳则记作 f(n)=O(g(n)) 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作T(n)=O(f(n))称作算法的渐近时间复杂度。例１、for(I=1，I<=n;++I)for(j=1;j<=n;++j){c[I][j]=0;for(k=1;k<=n;++k)c[I][j]+=a[I][k]*b[k][j];}由于是一个三重循环，每个循环从1到n，则总次数为: n×n×n=n3 时间复杂度为T(n)=O(n3)频度：是指该语句重复执行的次数例２ {++x;s=0;}将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1)如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。例３、for(I=1;I<=n;++I){++x;s+=x;}语句频度为：2n 其时间复杂度为：O(n)即时间复杂度为线性阶。例４、for(I=1;I<=n;++I) for(j=1;j<=n;++j){++x;s+=x;}语句频度为：2n2 其时间复杂度为：O(n2)即时间复杂度为平方阶。定理：若A(n)=a m n m +a m-1 n m-1 +…+a1n+a0是一个m次多项式，则A(n)=O(n m) 证略。例５for(i=2;i<=n;++I)for(j=2;j<=i-1;++j){++x;a[i，j]=x;}语句频度为：1+2+3+…+n-2=(1+n-2) ×(n-2)/2=(n-1)(n-2)/2=n2-3n+2∴时间复杂度为O(n2)即此算法的时间复杂度为平方阶.一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。以下六种计算算法时间的多项式是最常用的。其关系为：O(1)指数时间的关系为：O(2n)当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如：Void bubble-sort(int a[]，int n)for(I=n-1;change=TURE;I>1 && change;--I){change=false;for(j=0;jif (a[j]>a[j+1]) {a[j] ←→a[j+1];change=TURE}}最好情况：0次最坏情况：1+2+3+…+n-1=n(n-1)/2平均时间复杂度为:O(n2)1.4.4 算法的存储空间需求空间复杂度:算法所需存储空间的度量，记作:S(n)=O(f(n))其中n为问题的规模(或大小)程序所用的存储空间包括两个部分：固定部分可变部分1、固定部分：这部分空间的大小与输入输出的个数多少、数值大小无关。主要包括存放程序指令代码的空间，常数、简单变量、定长成分（如数组元素、结构成分、对象的数据成员等）变量所占的空间等。这部分属于静态空间，只要作简单的统计就可估算。2、可变部分：这部分空间主要包括其尺寸与实例特征有关的成分变量所占空间、引用变量所占空间、以及递归栈所用的空间，还有算法运行时动态命令使用的空间。(共34张PPT)第七章 图7.1 抽象数据类型图的定义ADT Graph {数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R＝{VR}VR＝{| v,w∈V且P(v,w)，表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息 }名词和术语有向图、 无向图、 网、 子图弧头、 弧尾、 边完全图、 稀疏图、 稠密图邻接点、 度、 入度、 出度路径、 路径长度、 回路简单路径、 简单回路连通图、 连通分量、强连通图、 强连通分量生成树、 生成森林、 最小生成树基本操作P：结构的建立和销毁:CreateGraph(&G,V,VR); // 按V和VR的定义构造图G。DestroyGraph(&G); // 销毁图G。对顶点的访问操作:LocateVex(G, u); // 若G中存在顶点u，则返回该顶点// 在图中位置；否则返回其它信息。GetVex(G, v); // 返回v的值。PutVex(&G, v, value); // 对v赋值value。对邻接点的操作:FirstAdjVex(G, v); // 返回v的第一个邻接点。若该顶点//在G中没有邻接点，则返回“空”。NextAdjVex(G, v, w); //返回v的（相对于w的）下一个// 邻接点。若w是v的最后一个邻// 接点，则返回“空”。插入或删除顶点InsertVex(&G, v); // 在图G中增添新顶点v。DeleteVex(&G, v); // 删除G中顶点v及其相关的弧。插入和删除弧InsertArc(&G, v, w); // 在G中增添弧，若G是无// 向的，则还增添对称弧。DeleteArc(&G, v, w); //在G中删除弧，若G是无// 向的，则还删除对称弧。遍历DFSTraverse(G, v, Visit()); // 从顶点v起深度优先遍历图// G，并对每个顶点调用函数// Visit一次且仅一次。BFSTraverse(G, v, Visit()); // 从顶点v起广度优先遍历图// G，并对每个顶点调用函数// Visit一次且仅一次。7.2 图的存储表示图的数组(邻接矩阵)存储表示#define INFINITY INT_MAX // 最大值∞#define MAX_VERTEX_NUM 20 // 最大顶点个数typedef enum {DG, DN, AG, AN} GraphKind;//{有向图,有向网,无向图,无向网}typedef struct ArcCell {VRType adj; // VRType是顶点关系类型。// 对无权图，用1或0表示相邻否；// 对带权图，则为权值类型。InfoType *info; // 该弧相关信息的指针}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct {VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量AdjMatrix arcs; // 邻接矩阵int vexnum, arcnum; // 图的当前顶点数和弧(边)数GraphKind kind; // 图的种类标志}MGraph;图的邻接表存储表示#define MAX_VERTEX_NUM 20typedef struct ArcNode {int adjvex; // 该弧所指向的顶点的位置struct ArcNode *nextarc; // 指向下一条弧的指针InfoType *info; // 该弧相关信息的指针} ArcNode;typedef struct VNode {VertexType data; // 顶点信息ArcNode *firstarc; // 指向第一条依附该顶点的弧} VNode, AdjList[MAX_VERTEX_NUM];typedef struct {AdjList vertices;int vexnum, arcnum; // 图的当前顶点数和弧数int kind; // 图的种类标志} ALGraph;有向图的十字链表存储表示#define MAX_VERTEX_NUM 20typedef struct ArcBox {int tailvex, headvex; // 该弧的尾和头顶点的位置struct ArcBox *hlink, *tlink;// 分别指向下一个弧头相同和弧尾相同的弧的指针域InfoType *info; // 该弧相关信息的指针} ArcBox;typedef struct VexNode {VertexType data;ArcBox *firstin, *firstout; // 分别指向该顶点第一条入弧和出弧} VexNode;typedef struct {VexNode xlist[MAX_VERTEX_NUM]; // 表头向量int vexnum, arcnum; // 有向图的当前顶点数和弧数} OLGraph; 无向图的邻接多重表存储表示#define MAX_VERTEX_NUM 20typedef emnu {unvisited, visited} VisitIf;typedef struct Ebox {VisitIf mark; // 访问标记int ivex, jvex; // 该边依附的两个顶点的位置struct EBox *ilink, *jlink; // 分别指向依附这两个顶点的下一条边InfoType *info; // 该边信息指针} EBox;typedef struct VexBox {VertexType data;EBox *firstedge; // 指向第一条依附该顶点的边} VexBox;typedef struct {VexBox adjmulist[MAX_VERTEX_NUM];int vexnum, edgenum; // 无向图的当前顶点数和边数} AMLGraph;7.3 图的遍历从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。一、深度优先搜索从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。//--- 下列算法使用的全局变量 ---Boolean visited[MAX]; // 访问标志数组Status (* VisitFunc)(int v); // 函数变量void DFSTraverse(Graph G, Status (*Visit)(int v)) {// 对图G作深度优先遍历。VisitFunc = Visit;for (v=0; vvisited[v] = FALSE; // 访问标志数组初始化for (v=0; vif (!visited[v]) DFS(G, v); // 对尚未访问的顶点调用DFS}void DFS(Graph G, int v) {// 从第v个顶点出发递归地深度优先遍历图G。visited[v] = TRUE; VisitFunc(v);// 访问第v个顶点for ( w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G, v, w) )if (!visited[w]) DFS(G, w);// 对v的尚未访问的邻接顶点w递归调用DFS}二、广度优先搜索从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。void BFSTraverse(Graph G, Status (*Visit)(int v)) {// 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。for (v=0; vInitQueue(Q); // 置空的辅助队列Qfor ( v=0; vif ( !visited[v]) { // v尚未访问EnQueue(Q, v); // v入队列while (!QueueEmpty(Q)) {DeQueue(Q, u); // 队头元素出队并置为uvisited[u] = TRUE; Visit(u); // 访问ufor ( w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G, u, w) )if ( ! visited[w]) EnQueue(Q, w);// u的尚未访问的邻接顶点w入队列Q7.4 最小生成树问题：假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建n-1条线路，如何在最节省经费的前提下建立这个通讯网？该问题等价于：构造网的一棵最小生成树，即：在e条带权的边中选取n-1条（不构成回路），使“权值之和”为最小。算法一：（普里姆算法）可取图中任意一个顶点v作为生成树的根，之后若要往生成树上添加顶点w，则在顶点v和顶点w之间必定存在一条边，并且该边的权值在所有连通顶点v和w之间的边中取值最小。一般情况下，假设n个顶点分成两个集合：U（包含已落在生成树上的结点）和V-U（尚未落在生成树上的顶点），则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。记录从顶点集U到V－U的代价最小的边的辅助数组：struct {VertexType adjvex;VRType lowcost;} closedge[MAX_VERTEX_NUM];k = LocateVex ( G, u ); // 顶点u为构造生成树的起始点for ( j=0; jif (j!=k) closedge[j] = { u, G.arcs[k][j].adj };closedge[k].lowcost = 0; // 初始，U＝{u}for (i=0; ik = minimum(closedge); // 求出T的下一个结点(k)printf(closedge[k].adjvex, G.vexs[k]); // 输出生成树的边closedge[k].lowcost = 0; // 第k顶点并入U集for (j=0; jif (G.arcs[k][j].adj < closedge[j].lowcost)closedge[j] = { G.vexs[k], G.arcs[k][j].adj };// 新顶点并入U后重新选择最小边} 算法二：（克鲁斯卡尔算法）为使生成树上边的权值之和最小，显然，其中每一条边的权值应该尽可能地小。克鲁斯卡尔算法的做法就是：先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。算法:构造非连通图 ST=( V,{ } );k = i = 0;while (k++i;从边集 E 中选取第i条权值最小的边(u,v);若(u,v)加入ST后不使ST中产生回路，则 输出边(u,v); 且 k++;} 一般来讲，由于普里姆算法的时间复杂度为O(n2)，则适于稠密图；而克鲁斯卡尔算法需对e条边按权值进行排序，其时间复杂度为O(eloge)，则适于稀疏图。7.5 重（双）连通图和关节点问题：若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。图的双连通性对于表示通讯或运输的图来说，有着重要的意义。若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为关节点。显然，没有关节点的连通图为双连通图。关节点的特征：假设从某个顶点V0出发对连通图进行深度优先搜索遍历，则可得到一棵深度优先生成树，树上包含图的所有顶点。· 若生成树的根结点，有两个或两个以上的分支，则此顶点(生成树的根)必为关节点;· 对生成树上的任意一个“顶点”，若其某棵子树的根或子树中的其它“顶点”没有和其祖先相通的回边，则该“顶点”必为关节点。如何判别？1) 设V0为深度优先遍历的出发点p = G.vertices[0].firstarc; v = p->adjvex;DFSArticul(G, v);// 从第v顶点出发深度优先搜索if (count < G.vexnum) {// 生成树的根有至少两棵子树printf (0, G.vertices[0].data);// 根是关节点}2) 对生成树上的顶点定义一个函数:low(v) = Min{visited[v], low[w], visited[k] }对顶点v，若(在生成树上)存在一个子树根w,low[w] ≥ visited[v]则顶点v为关节点visited[v0] = min = ++count; // count计顶点访问次序for (p=G.vertices[v0].firstarc; p; p=p->nextarc) {w = p->adjvex; // w为v0的邻接顶点if (visited[w] == 0) { // w未曾被访问DFSArticul(G, w); // 返回前求得low[w]if (low[w] < min) min = low[w];if (low[w]>=visited[v0]) printf(v0, G.vertices[v0].data);} // 输出关节点elseif (visited[w] < min) min = visited[w];// w是回边上的顶点}low[v0] = min; 7.6 两点之间的最短路径问题求从某个源点到其余各点的最短路径迪杰斯特拉推出了一个按路径长度递增的次序求从源点到其余各点最短路径的算法。假设图中所示为从源点到其余各点之间的最短路径，则在这些路径中，必然存在一条长度最短者※ 在这条路径上，必定只含一条(权值最小)弧，由此，只要在所有从源点出发的弧中查找权值最小者;长度次短的路径可能有两种情况:它可能是从源点直接到该点的路径;也可能是，从源点到a, 再从a到该点其余依次类推。假设 Dist[k] 表示 当前所求得的从源点到k的最 短路径显然，Dist[k] = <源点到顶点k的弧上的权值>或者 = <源点到其它顶点的路径长度>+ <其它顶点到顶点k弧上的权值>二、每一对顶点之间的最短路径从vi到vj的最短路径是以下各种可能路径中的长度最小者:若存在，则存在路径{vi,vj}// 路径中不含其它顶点若,存在，则存在路径{vi,v1,vj}// 路径中所含顶点序号不大于1若{vi,…,v2}, {v2,…,vj}存在，则存在一条路径{vi, …, v2, …vj}// 路径中所含顶点序号不大于2…依次类推，则vi至vj的最短路径应是上述这些路径中，路径长度最小者。7.7 拓扑排序· 问题:假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。如何检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。· 何谓“拓扑排序”？对有向图进行如下操作:按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。· 如何进行拓扑排序？一、从有向图中选取一个没有前驱的顶点，并输出之;二、从有向图中删去此顶点以及所有以它为尾的弧;重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。没有前驱 -- 入度为零删除顶点及以它为尾的弧-- 弧头顶点的入度减1· 算法:取入度为零的顶点v;while (v<>0) {printf(v); ++m;w:=FirstAdj(v);while (w<>0) {inDegree[w]--;w:=nextAdj(v,w);}取下一个入度为零的顶点v;}if m 7.8 关键路径· 问题:假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间，问:哪些子工程项是“关键工程”？即:将影响整个工程完成期限的子工程项。整个工程完成的时间为:从有向图的源点到汇点的最长路径。“关键活动”指的是: 该弧上的权值增加 将使有向图上的最长路径的长度增加。· 如何求关键活动？ “事件(顶点)” 的 最早发生时间 ve(j)ve(j) = 从源点到顶点j的最长路径长度;“事件(顶点)” 的 最迟发生时间 vl(k)vl(k) = 从顶点k到汇点的最短路径长度;假设第i条弧为则 第i项活动“活动(弧)”的 最早开始时间 ee(i)ee(i) = ve(j);“活动(弧)”的 最迟开始时间 el(i)el(i) = vl(k) – dut();事件发生时间的计算公式:ve(源点) = 0;ve(k) = Max{ve(j) + dut()}vl(汇点) = ve(汇点);vl(j) = Min{vl(k) – dut()}· 算法的实现要点:显然，求ve的顺序应该是按拓扑有序的次序;而 求vl的顺序应该是按拓扑逆序的次序;因为 拓扑逆序序列即为拓扑有序序列的逆序列，因此 应该在拓扑排序的过程中，用一个“栈”记下拓扑有序序列。学习要点 1. 熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。 2. 熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索的两种形式（递归和非递归）和广度优先搜索的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略。 3. 应用图的遍历算法求解各种简单路径问题。 4. 理解教科书中讨论的各种图的算法。(共55张PPT)第二章 线性表2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现2.3.1 线性链表2.3.3 双向链表2.4 一元多项式的表示及相加2.3.2 循环链表2.1 线性表的逻辑结构线性表(Linear List) ：由n(n≧)个数据元素(结点)a1，a2， …an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n>0)记作：(a1，a2，…an)这里的数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。例1、26个英文字母组成的字母表（A，B，C、…、Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）例3、学生健康情况登记表如下：姓 名 学 号 性 别 年龄 健康情况王小林 790631 男 18 健康陈 红 790632 女 20 一般刘建平 790633 男 21 健康张立立 790634 男 17 神经衰弱…….. …….. ……. ……. …….例4、一副扑克的点数（2，3，4，…，J，Q，K，A）从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1；其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋a i-1和一个直接后继a i+1。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。抽象数据类型的定义为：P19算法2.1例2-1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。void union(List &La，List Lb) {La-len=listlength(La);Lb-len=listlength(Lb);for(I=1;I<=lb-len;I++) {getelem(lb，I，e);if(!locateelem(la，e，equal))listinsert(la，++la-en，e)}}例2-2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。此问题的算法如下：void mergelist(list la，list lb，list &lc)initlist(lc);I=j=1;k=0;la-len=listlength(la);lb-len=listlength(lb);while((I<=la-len)&&(j<=lb-len)){getelem(la，I，ai);getelem(lb，j，bj);if(ai<=bj){listinsert(lc，++k，ai);++I;}else{listinsert(lc，++k，bj);++j;}}while(I<=la-len){getelem((la，I++，ai);listinsert(lc，++k，ai);}while(j<=lb-len){getelem((lb，j++，bj);listinsert(lc，++k，bi);}}2.2 线性表的顺序存储结构2.2.1 线性表把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第I+1个数据元素的存储位置LOC( a i+1)和第i个数据元素的存储位置LOC(a I )之间满足下列关系：LOC(a i+1)=LOC(a i)+l线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(I-1)*l由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。# define ListSize 100typedef int DataType;typedef struc{DataType data[ListSize];int length;} Sqlist;2.2.2 顺序表上实现的基本操作在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是l.data[I-1]。以下主要讨论线性表的插入和删除两种运算。1、插入线性表的插入运算是指在表的第I(1≦i≦n+1个位置上，插入一个新结点x，使长度为n的线性表(a1，…a i-1，ai，…，an)变成长度为n+1的线性表(a1，…a i-1，x，ai，…，an)算法2.3Void InsertList(Sqlist*L，DataType x，int I){int j;if(I<1 || I>l.length+1)printf(“Position error”);return ERRORif(l.length>=ListSize)printf(“overflow”);exit(overflow);for(j=l.length-1;j>=I-1;j--)l.data[j+1]=l.data[j];l.data[I-1]=x;l.length++;}现在分析算法的复杂度。这里的问题规模是表的长度，设它的值为。该算法的时间主要化费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。当时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）；当=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，其时间复杂度为O（n）。由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度在长度为n的线性表中第i个位置上插入一个结点，令Eis(n)表示移动结点的期望值（即移动的平均次数），则在第i个位置上插入一个结点的移动次数为n-I+1。故Eis(n)= pi(n-I+1)不失一般性，假设在表中任何位置(1≦i≦n+1)上插入结点的机会是均等的，则p1=p2=p3=…=p n+1=1/(n+1)因此，在等概率插入的情况下，Eis(n)= (n-I+1)/(n+1)=n/2也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长 n较大时，算法的效率相当低。虽然Eis(n)中n的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为O(n)。2、删除线性表的删除运算是指将表的第i(1≦i≦n)结点删除，使长度为n的线性表： (a1，…a i-1，ai，a i+1…，an)变成长度为n-1的线性表(a1，…a i-1，a i+1，…，an) BBBBB ‘[Void deleteList(Sqlist*L，int I){int j;if(I<1 || I>l.length)printf(“Position error”);return ERRORfor(j=i;j<=l.length-1;j++)l.data[j-1]=l.data[j];l.length--;}该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。若I=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点；若I=1，则前移语句将循环执行n-1次，需移动表中除开始结点外的所有结点。这两种情况下算法的时间复杂度分别为O(1)和O(n)。删除算法的平均性能分析与插入算法相似。在长度为n的线性表中删除一个结点，令Ede(n)表示所需移动结点的平均次数，删除表中第i个结点的移动次数为n-i，故Ede(n)= pi(n-I)式中，pi表示删除表中第i个结点的概率。在等概率的假设下，p1=p2=p3=…=pn=1/n由此可得：Ede(n)= (n-I)/n=(n-1)/2即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是O(n)。2.3 线性表的链式表示和实现线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使得插入和删除操作会移动大量的结点.为避免大量结点的移动，我们介绍线性表的另一种存储方式，链式存储结构，简称为链表(Linked List)。2.3.1 线性链表链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构：data link其中：data域是数据域，用来存放结点的值。next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。由于上述链表的每一个结只有一个链域，故将这种链表称为单链表（Single Linked)。显然，单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。同时，由于终端结点无后继，故终端结点的指针域为空，即null（图示中也可用^表示)。例1、线性表:(bat，cat，eat，fat，hat，jat，lat，mat)的单链表示意图如下：……110……130135……160头指针 head 165170……200205…………… ……hat 200……. ……cat 135eat 170…. ……mat Nullbat 130fat 110…… ……jat 205lat 160…… ……165headbatcateatmat ^…单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。例如：若头指针名是head，则把链表称为表head。用C语言描述的单链表如下：Typedef char datatype;Typedef struct node{datatype data;struct node *next;}listnode;typedef listnode *linklist;listnode *p;linklist head;注意区分指针变量和结点变量这两个不同的概念。P为动态变量，它是通过标准函数生成的，即p=(listnode*)malloc(sizeof(listnode));函数malloc分配了一个类型为listnode的结点变量的空间，并将其首地址放入指针变量p中。一旦p所指的结点变量不再需要了，又可通过标准函数 free(p)释放所指的结点变量空间。指针变量P和（其值为结点地址）和结点变量*P之间的关系。一、建立单链表假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符‘\n’为输入结束标记。动态地建立单链表的常用方法有如下两种：1、头插法建表该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。具体算法如下：linklist createlistf(void){char ch;linklist head;listnode *p;head=null;ch=getchar( );while (ch!=‵\n′{p=(listnode*)malloc(sizeof(listnode));p–>data=ch;p–>next=head;head=p;ch=getchar( );}return (head);}listlink createlist(int n){ int data;linklist head;listnode *phead=null;for(i=n;i>0;--i){p=(listnode*)malloc(sizeof(listnode));scanf((〝%d〞，&p–>data);p–>next=head;head=p;}return(head);}2、尾插法建表头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。例：linklist creater( ){char ch;linklist head;listnode *p，*r; //(， *head;)head=NULL;r=NULL;while((ch=getchar( )!=‵\n′){p=(listnode *)malloc(sizeof(listnode));p–>data=ch;if(head=NULL)head=p;elser–>next=p;r=p;}if (r!=NULL)r–>next=NULL;return(head);}说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，而其余结点的位置是在其前趋结点的指针域中。算法中的第一个if语句就是用来对第一个位置上的插入操作做特殊处理。算法中的第二个if语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表head是空表，尾指针r亦为空，结点*r不存在；否则链表head非空，最后一个尾结点*r是终端结点，应将其指针域置空。如果我们在链表的开始结点之前附加一个结点，并称它为头结点，那么会带来以下两个优点：a、由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处理；b、无论链表是否为空，其头指针是指向头结点 在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。其算法如下：linklist createlistr1( ){char ch;linklist head=(linklist)malloc(sizeof(listnode));listnode *p，*rr=head;while ((ch=getchar( )) !=‵\n′{p=(listnode*)malloc(sizeof(listnode));p–>data=ch;p–>next=p;r=p;}r–>next=NULL;return(head);}上述算法里动态申请新结点空间时未加错误处理，可作下列处理：p=(listnode*)malloc(sizeof(listnode))if(p==NULL)error(〝No space for node can be obtained〞);return ERROR;以上算法的时间复杂度均为O(n)。二、查找运算1、按序号查找在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第0 个结点，其算法如下：Listnode * getnode(linklist head ， int i){int j;listnode * p;p=head;j=0;while(p–>next && jp=p–>next;j++;}if (I==j)return p;elsereturn NULL;}2、按值查找按值查找是在链表中，查找是否有结点值等于给定值key的结点，若有的话，则返回首次找到的其值为key的结点的存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值key作比较。其算法如下：Listnode * locatenode(linklist head，int key){listnode * p=head–>next;while( p && p–>data!=key)p=p–>next;return p;}该算法的执行时间亦与输入实例中的的取值key有关，其平均时间复杂度的分析类似于按序号查找，也为O(n)。三、插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，我们必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*p，并令结点*p的指针域指向新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化，插入过程如：具体算法如下：void insertnode(linklist head，datetype x，int i){listnode * p，*q;p=getnode(head，i-1);if(p==NULL)error(〝position error〞);q=(listnode *)malloc(sizeof(listnode));q–>data=x;q–>next=p–next;p–>next=q;}设链表的长度为n，合法的插入位置是1≦i≦n+1。注意当i=1时，getnode找到的是头结点，当 i=n+1时，getnode找到的是结点an。因此，用i-1做实参调用getnode时可完成插入位置的合法性检查。算法的时间主要耗费在查找操作getnode上，故时间复杂度亦为O(n)。四、删除运算删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点a a i-1的指针域next中，所以我们必须首先找到a i-1的存储位置p。然后令p–>next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，将其归还给“存储池”。此过程为：具体算法如下：void deletelist(linklist head， int i){listnode * p， *r;p=getnode(head，i-1);if(p= =NULL || p–>next= =NULL)return ERROR;r=p–>next;p–>next=r–>next;free( r ) ;}设单链表的长度为n，则删去第i个结点仅当1≦i≦n时是合法的。注意，当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当*p存在（即p!=NULL）且*p不是终端结点（即p–>next!=NULL）时，才能确定被删结点存在。显然此算法的时间复杂度也是O(n)。从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。2.3.2 循环链表循环链表时一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：a1an….head⑴ 非空表⑵ 空表在用头指针表示的单链表中，找开始结点a1的时间是O(1)，然而要找到终端结点an，则需从头指针开始遍历整个链表，其时间是O(n)在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便.如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是(rear–>next) —>next和rear，显然，查找时间都是O(1)。因此，实际中多采用尾指针表示单循环链表。由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p—>next是否为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等。例、在链表上实现将两个线性表(a1，a2，a3，…an)和(b1，b2，b3，…bn)链接成一个线性表的运算。linklist connect(linklist heada，linklist headb){linklist p=heada—>next;heada—>next=(headb—next)—>nextfree(headb—>next);headb—>next=p;return(headb);}2.3.3双链表双向链表(Double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为：typedef struct dlistnode{datatype data;struc dlistnode *prior，*next;}dlistnode;typedef dlistnode * dlinklist;dlinklist head;和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向链表。设指针p指向某一结点，则双向链表结构的对称性可用下式描述：(p—>prior)—>next=p=(p—>next)—>prior即结点*p的存储位置既存放在其前趋结点*(p—>prior)的直接后继指针域中，也存放 在它的后继结点*(p—>next)的直接前趋指针域中。双向链表的前插操作算法如下：void dinsertbefor(dlistnode *p，datatype x){dlistnode *q=malloc(sizeof(dlistnode));q—>data=x;q—>prior=p—>prior;q—>next=p;p—>prior—>next=q;p—>prior=q;}void ddeletenode(dlistnode *p){p–>prior–>next=p–>next;p–>next–>prior=p–>prior;free(p);}注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算是法的时间复杂度均为O(1)。(共34张PPT)第六章 树和二叉树6.1 树的定义和基本概念6.2 二叉树6.2.1 树的定义和基本术语6.2.2 二叉树的性质6.2.3 二叉树的存储结构6.3 遍历二叉树6.3.1 遍历二叉树6.3.2 线索二叉树6.4 树和森林6.4.1 树的存储结构6.4.2 森林与二叉树的转换树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。6.1 树的定义和基本术语定义：树(Tree)是n(n>=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：（1）有且仅有一个特定的称为根(Root)的结点；(2)其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。6.2 二叉树二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树 相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。6.2.1 二叉树的定义定义：二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。二查树不是树的特殊情况，它们是两个概念。二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。图6.8列出二差树的5种基本形态，图6.8(C) 和图6.8（d）是不同的两棵二叉树。(a)空二叉树AABABACB(b)根和空的左右子树(c)根和左子树(d)根和右子树(e)根和左右子树图6.8 二叉树的5种形式6.2.2 二叉树的性质二叉树具有下列重要性质：性质1： 在二叉树的第i层上至多有2i-1个结点(i>=1)。采用归纳法证明此性质。当i=1时，只有一个根结点，2i-1=20 =1,命题成立。现在假定多所有的j，1<=j由于二叉树每个结点的度最大为2，故在第i层上最大结点数为第i－1层上最大结点数的二倍，即2×2i-2＝2i-1。命题得到证明。性质2：深度为k的二叉树至多有2k－1个结点（k>=1).深度为k的二叉树的最大的结点时为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数，： EkI=1（第i层上的最大结点数）= EkI=12i-1=2k –1性质3： 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有：N＝n0＋n1＋n2 (6-1)再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数，则有：N＝B＋1。由于这些分支都是由度为1和2的结点射出的，所有有：B＝n1+2*n2N＝B＋1＝n1＋2×n2＋1 （6－2)由式（6－1）和（6－2）得到：n0+n1+n2=n1+2*n2+1n0＝n2＋1下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树。一棵深度为k且由2k-1个结点的二叉树称为满二叉树。图6.9就是一棵满二叉树，对结点进行了顺序编号。如果深度为k、由n个结点的二叉树中个结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，2453671图6.9 满二叉树12345612345712367(a)完全二叉树(b)非完全二叉树( c)非完全二叉树图6.10 完全二叉树则称这样的二叉树为完全二叉树，图6..10（b）、c）是2棵非完全二叉树。满二叉树是完全二叉树的特例。完全二叉树的特点是：（1)所有的叶结点都出现在第k层或k－1层。（2）错任一结点，如果其右子树的最大层次为1，则其左子树的最大层次为1或l＋1。性质4：具有n个结点的完全二叉树的深度为[log2n]＋1。符号【x】表示不大于x的最大整数。假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-1－12k-1<=n<2k取对数得到：k－1性质5： 如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第【log2n】+1层，每层从左到右),则对任一结点i（1<=i<=n),有：（1）如果i＝1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲是结点【i/2】。（2）如果2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。（3）如果2i＋1>n，则结点i无右孩子；否则，其右孩子是结点2i＋1。[I/2]iI+12i2i+12(I+1)2i+3I+12(I+1)2i+3i2i2i+1图6.11 完全二叉树中结点I和i+1(a)I和i+1结点在同一层(b)I和i+1结点不在同一层如图6.11所示为完全二叉树上结点及其左右好在结点之间的关系。在此过程中，可以从（2）和（3）推出（1），所以先证明（2）和（3）。对于i＝1，由完全二叉树的定义，其左孩子是结点2，若2>n，即不存在结点2，此是，结点i无孩子。结点i的由孩子也只能是结点3，若结点3不存在，即3>n，此时结点i无右孩子。对于i>1，可分为两种情况：（1）设第j（1<=j<=[log2n])层的第一个结点的编号为i，由二叉树的性质2和定义知i＝2j-1结点i的左孩子必定为的j＋1层的第一个结点，其编号为2j＝2×2j-1＝2i。如果2i>n，则无左孩子：其右孩子必定为第j＋1层的第二个结点，编号为2i＋1。若2i+1>n，则无右孩子。（2）假设第j（1<=j<=[log2n])层上的某个结点编号为i（2e(j-1)<=i<=2ej-1),且2i＋1当i＝1时，就是根，因此无双亲，当i>1时，如果i为左孩子，即2×（i/2)=i,则i/2是i的双亲；如果i为右孩子，i＝2p+1,i的双亲应为p，p＝（i－1）/2=[i/2]. 证毕。6.2.3 二叉树的存储结构1.顺序存储结构它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法： #define max-tree-size 100Typedef telemtype sqbitree[max-tree-size];Sqbitree bt从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为H且只有H个结点的右单支树确需要2h-1个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！A B C D E F G H I J K L1 2 3 4 5 6 7 8 9 10 11 12完全二叉树abcdefghijklABCDEFG 表示该处没有元素存在仅仅为了好理解A B C D E F G一般二叉树顺序存储结构的算法：Status CreateBiTree(BiTree *T) {scanf(&ch);if(ch= =") T=NULL;else{if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))exit(OVERFLOW);T–>data=ch;CreateBiTree(T–>lchild);CreateBiTree(T–>rchildd);}return OK;}（2）二叉链表法存储二叉树经常用二叉链表法A^ BC ^D^ E^ F ^^ G ^^ H ^lchild Data rchild二叉树的二叉链表存储表示Typedef struct BiTNode {TelemType data;struct BiTNode *lchild,*rchild;} BiTNode,*BiTree;有时也可用数组的下标来模拟指针,即开辟三个一维数组Data ,lchild,rchild 分别存储结点的元素及其左,右指针域;6.3 遍历二叉树和线索二叉树6.3.1遍历二叉树在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。bca(根结点)(右子树)(左子树)由二叉树的递归定义，二叉树的三个基本组成单元是：根结点、左子树和右子树。假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为：DLR——先（根）序遍历，LDR——中（根）序遍历，LRD——后（根）序遍历。1、先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。2、中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。3、后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。例如图（1）所示的二叉树表达式(a+b*(c-d)-e/f)若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为：-+a*b-cd/ef按中序遍历,其中序序列为：a+b*c-d-e/f按后序遍历,其后序序列为：abcd-*+ef/-人喜欢中缀形式的算术表达式,对于计算机,使用后缀易于求值 图 （1）－＋*a/b-dcfeTREENODE *creat_tree(){TREENODE *t;char c;c=getchar();if(c= =‘#’) return(NULL);else{t=(TREENODE *)malloc(sizeof(TREENODE))t – >data=c;t –>lchild=create_tree();t –>rchild=create –tree(); }return(t);}中序遍历算法:#include#include#define NULL 0Typedef struct node{char data;struct node *lchild,*rchild;}TREENODE;TREENODE *root;TREENODE *creat_tree();Void inorder(TREENODE *);Void inorder(TREENODE *p){if(p!=NULL){ inorder(p–>lchild);printf(“%c”,p–>data)inorder(p–>rchild);}}（3）三叉链表其它见书P127lchild data parent rchild线索二叉树：当以二叉链表作为存储结构时,只能找到结点的左右孩子的信息,而不能在结点的任一序列的前驱与后继信息,这种信息只有在遍历的动态过程中才能得到,为了能保存所需的信息,可增加标志域;其中:0 lchild 域指示结点的左孩子ltag={ 1 lchild 域指示结点的前驱0 rchild 域指示结点的右孩子rtag={ 1 rchild 域指示结点的后驱以这种结构构成的二叉链表作为二叉树的存储结构,叫做线索链表,其中指向结点前驱与后继的指针叫做线索.加上线索的二叉树称之为线索二叉树lchild ltag data rtag rchild二叉树的二叉线索存储表示:Typedef enum{Link,Thread}PointerTag;Link= =0:指针,Thread= =1:线索Typedef struct BiThrNode{TelemType data;struct BiTreeNode *lchild,*rchild; PointerTag LTag, Rtag;}BiTreeNode,*BiThrTree;.模仿线性表的存储结构,在二叉树的线索链表上也添加一个头结点,令其lchild域的指针指向二叉树的根结点,其rchild域的指针指向中序遍历时访问的最后一个结点;同时,令二叉树中序序列中的第一个结点lchild域 指针的和最后一个结点rchild域的指针均指向头结点;就像为二叉树建立了一个双向线索链表,就好比人在一个圆圈上走路,有可能存在好走的可能性Status InorderTraverse_Thr(BiThrTree T,status(*visit)(TElemType)){//T指向头结点,头结点的lchild左链指向根结点//中序遍历二叉线索树的非递归算法,对每个数据元素调用//函数VisitP=T–>lchild;while(p!=T){while(p –>LTag = =Link) p=p –>lchild;if(!visit(p –>data)) return error;while(p –>RTag = =Thread&&p –>rchild!=T) {p=p –>rchild; Visit(p –>data);}p= p–>rchild;}return OK;}//InorderTraverse_ThrP134 : Status InorderThreading(BiThrTree &Thrt,BiThrTree T){if(!(Thrt =(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);Thrt –>LTag =Link; Thrt –>RTag =Thread;Thrt –>rchild=Thrt;if(!T) Thrt –>lchild=Thrt;else{Thrt –>lchild=T; pre=Thrt;InThrTreading(T);pre –>rchild=Thrt; pre –> RTag =Thread;Thrt –>rchild=pre;}return OK;}//InorderThreadingVoid InThreading(BiThrTree p) {if(p){InThreading(p –>lchild);if(!p –>lchild) {p –> LRag =Thread; p –>lchild=pre;}if(!pre –>rchild){pre –>rchild){pre –>RRag =Thread;pre –>rchild=p;}pre=p;InThreading(p –>rchild);}}在线索树上插入一棵左子树(Ins_lchild)和删除一棵左子(Del_lchild)(共33张PPT)第四章 串4.1 串类型的定义4.2 串的表示和实现4.2.1 定长顺序存储表示4.2.2 堆分配存储表示4.2.3 串的块链存储表示4.1 串类型的定义一、串和基本概念串(String)是零个或多个字符组成的有限序列。一般记作S=“a1a2a3…an”，其中S 是串名，双引号括起来的字符序列是串值；ai(1≦i≦n)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串(Empty String)，它不包含任何字符。通常将仅由一个或多个空格组成的串称为空白串(Blank String)注意：空串和空白串的不同，例如“ ”和“”分别表示长度为1的空白串和长度为0的空串。串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如，设A和B分别为A=“This is a string” B=“is”则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的序号（或位置）为3特别地，空串是任意串的子串，任意串是其自身的子串。通常在程序中使用的串可分为两种：串变量和串常量。串常量和整常数、实常数一样，在程序中只能被引用但不能不能改变其值，即只能读不能写。通常串常量是由直接量来表示的，例如语句Error(“overflow”)中“overflow”是直接量。但有的语言允许对串常量命名，以使程序易读、易写。如C++中，可定义const char path[]=“dir/bin/appl”;这里path是一个串常量，对它只能读不能写。串变量和其它类型的变量一样，其取值是可以改变的。二、串的抽象数据定义Const int maxlen=128；Class string{Public:String(const string&ob);String(const char*init);String()-string(){delete[]ch;}Int length()const{return curlen}String&coperator(){int pos,int len};Int operator ==(const string&ob) const{return strcmp(ch,ob.ch)==0}Int operator!=(const string&ob)const {return strcmp(ch,ob.ch)!=0}Int operator!()const{return curlen==0;}String &operator=(const string&ob);String &operator +=(const string&ob);Char &operator [](int I);Int find (string pat)const;Private ;Int curlen;Char *ch;}三、串的基本操作对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。下面仅介绍几种在C语言中常用的串运算，其它的串操作见的文件。定义下列几个变量：char s1[20]=“dirtreeformat”,s2[20]=“file.mem”;char s3[30],*p;int result;求串长(length)int strlen(char s); //求串的长度例如：printf(“%d”,strlen(s1)); 输出13（2）串复制(copy)char *strcpy(char to,char from);该函数将串from复制到串to中，并且返回一个指向串to的开始处的指针。例如：strcpy(s3,s1); //s3=“dirtreeformat”(3)联接(concatenation)char strcat(char to,char from)该函数将串from复制到串to的末尾，并且返回一个指向串to的开始处的指针。例如：strcat(s3,”/”)strcat(s3,s2); //s3=“dirtreeformat/file.mem”(4)串比较（compare)int strcmp(chars1,char s2);该函数比较串s1和串s2的大小，当返回值小于0，等于0或大于0时分别表示s1s2例如：result=strcmp(“baker”,”Baker”) result>0result=strcmp(“12”,”12”); result=0result=strcmp(“Joe”,”Joseph”); result<0（5）字符定位(index)char strchr(char s,char c);该函数是找c在字符串中第一次出现的位置，若找到则返回该位置，否则返回NULL。例如：p=strchr(s2,”.”); p 指向“file”之后的位置if(p) strcpy(p,”.cpp”); s2=“file.cpp”上述串的操作是最基本的，其中后四个还有变种形式：strncpy，strncat，strncmp，strnchr。串的其余操作可由这些基本操作组合而成。例1、求子串求子串的过程即为复制字符序列的过程，将串S中的第pos个字符开始长度为len的字符复制到串T中。void substr(string sub,string s,int pos,int len){if(pos<0 || pos>strlen(s)-1 || len<0)error(“parameter error”)strncpy(sub,&s[pos],len);}例2、串的定位index(s,t,pos)在主串中取从第i个字符起、长度和串T相等的子串和T比较，若相等，则求得函数值为i，否则值增1直至S中不存在和串T相等的子串为止。int index(string s,string t,int pos){if(pos>0){n=strlen(s); m=strlen(t); i=pos;while(isubstr(sub,s,i,m);if(strcmp(sub,t)!=0)++i;else return(i);}}return(0);}4.2 串的表现和实现因为串是特殊的线性表，故其存储结构与线性表的存储结构类似。只不过由于组成串的结点是单个字符。串有三种机内表示方法，下面分别介绍。4.2.1定长顺序存储表示定长顺序存储表示,也称为静态存储分配的顺应表。它是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出：#define maxstrlen 256typedef char sstring[maxstrlen];sstring s; //s是一个可容纳255个字符的顺序串。一般可使用一个不会出现在串中的特殊字符在串值的尾部来表示串的结束。例如，C语言中以字符‵\0′表示串值的终结，这就是为什么在上述定义中，串空间最大值maxstrlen为256，但最多只能存放255个字符的原因，因为必须留一个字节来存放‵\0′字符。若不设终结符，可用一个整数来表示串的长度，那么该长度减1的位置就是串值的最后一个字符的位置。此时顺序串的类型定义和顺序表类似：typedef struct{char ch[maxstrlen];int length;}sstring; //其优点是涉及到串长操作时速度快。4.2.2堆分配存储表示这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表。在C语言中，利用和等动态存储管理函数，来根据实际需要动态分配和释放字符数组空间。这样定义的顺序串类型也有两种形式。typedef char *string; //c中的串库相当于此类型定义typedef struct{char *ch;int length;}hsring;status sinsert(hstring s,int pos,hstring t){if(pos<1 || pos>s.length+1)return error;if(t.length){if(!(s.ch=(char*)realloc(s.ch,(s.length+t.length)*sizeof(char)))exit(overflow);for(i=s.length-1;i>pos-1;--i)s.ch[I+t.length]=s.ch[i];s.ch[pos-1..pos+t.length2]=t.ch[0..t.length-1];s.length+=t.length;}return ok;}int strlen(hstring s){return s.length;}status clearstring(hstring s){if(s.ch){free(s.ch);s.ch=NULL;}s.length=0;}status strassign(hstring t,char *chars){//生成一个其值等于串常量chars的串tif(t.ch) free(t.ch);for(i=0,(c=chars;c;++i),++c);if(!i) {t.ch=null; t.length=0;}else{if(!(t.ch=(char *)malloc(I*sizeof(char))))exit(overflow);t.ch[0..i-1]=chars[0..i-1];t.length=i;}}int strcmp(hstring s,hstring t){for(i=0;iif(s.ch[i]!=t.ch[i]return(s.ch[i]-t.ch[i]);return s.length-t.length;}status concat(hstring t,hstring s1,hstring s2){if(!(t.ch)=(char*)malloc(s1.length+s2.length)*sizeof(char)))exit(overflow);t.ch[0..s1.length-1]=s1.ch[0..s1.length-1];t.length=s1.length+s2.length;t.ch[s1.length..t.length-1]=s2.ch[0..s2.length-1];}Status substr(hstring sub,hstring s,int pos,int len){if(pos<1 || pos>s.length || len<0 ||len>s.length-pos+1)return error;if(sub.ch) free(sub.ch);if(!len){sub.ch=null;sub.length=0;}else{sub.ch=(char *)malloc(len*sizeof(char));sub.ch[0..len-1]=s[pos-1..pos+len-2];s.length=len;}}4.2.3 串的链式存储结构顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。typedef struct node{char data;struct node *next;}lstring;一个链串由头指针唯一确定。这种结构便于进行插入和删除运算，但存储空间利用率太低。为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于 1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。对于结点大小不为1的链串，其类型定为义只需对上述的结点类型做简单的修改即可。#define nodesize 80typedef struct node{char data[nodesize];struct node *next;}lstring;4.3 串的模式匹配算法子串定位运算又称为模式匹配(Pattern Matching)或串匹配(String Matching)，此运算的应用在非常广泛。例如，在文本编辑程序中，我们经常要查找某一特定单词在文本中出现的位置。显然，解此问题的有效算法能极大地提高文本编辑程序的响应性能。在串匹配中，一般将主串称为目标串，子串称之为模式串。设S为目标串，T为模式串，且不妨设：S=“s0s1s2…sn-1” T=“t0t1…tm-1”串的匹配实际上是对于合法的位置0≦i≦n-m依次将目标串中的子串s[i..i+m-1]和模式串t[0..m-1]进行比较，若s[i..i+m-1]=t[0..m-1]，则称从位置i开始的匹配成功，亦称模式t在目标s中出现；若s[i..i+m-1] ≠t[0..m-1]，，则称从位置i开始的匹配失败。上述的位置i又称为位移，当s[i..i+m-1]=t[0..m-1]时，i称为有效位移；当s[i..i+m-1] ≠t[0..m-1]时，i称为无效位移。这样，串匹配问题可简化为是找出某给定模式T在一给定目标T中首次出现的有效位移。串匹配的算法很多，这里我们只讨论一种最简单的称为朴素的串匹配算法。其基本思想是用一个循环来依次检查n-m+1个合法的位移i(0≦i≦n-m)是否为有效位移，其算法段为：for(i=0;i<=n-m;i++){if(S[i..i+m-1]=T[0..m-1]return i;下面以第二种定长的顺序串类型作为存储结构，给出具体的串匹配算法。int index(sstring s,sstring t,int pos){int i,j,k;int m=s.length;int n=t.length;for(i=0;i<=n-m;i++){j=0;k=i;while(jk++;j++;}if(j==m)return i;}return –1;}显然，该算法在最坏情况下的时间复杂度为O((n-m)m)。链串上的子串定位算法用结点大小为1的单链表做串的存储结构时，实现朴素的匹配算法很简单。只是现在的位移是结点地址而非整数，且单链表中没有存储长度信息。若匹配成功，则返回有效位移所指的结点地址，否则返回空指针。具体算法如下：lstring *lindex(lstring s,lstring t){lstring *shift,*q,*p;shift=S;q=shift;p=t;while(q && p){if(q->data==p->data){q=q->next;p=p->next;}else{shift=shift->next;q=shift;p=t;}}if(p==null)return shift;elsereturn null;}(共83张PPT)概述插入排序交换排序选择排序归并排序基数排序外排序第九章 排序什么是排序(Sorting)？简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来。排序是计算机中经常遇到的操作。排序的几个基本概念数据表(Data List) 待排序的数据对象的有限集合。关键码(Key) 作为排序依据的数据对象中的属性域。主关键码 不同的数据对象若关键码互不相同，则这种关键码称为主关键码。排序的确切定义 使一组任意排列的对象变成一组按关键码线性有序的对象。排序的几个基本概念排序算法的稳定性 判断标准：关键码相同的数据对象在排序过程中是否保持前后次序不变。如 2, 2*,1，排序后若为1, 2*, 2 则该排序方法是不稳定的。内排序与外排序 区分标准：排序过程是否全部在内存进行。排序的时间开销 它是衡量算法好坏的最重要的标志。通常用算法执行中的数据比较次数和数据移动次数来衡量静态排序中的数据表的类定义const int DefaultSize = 100;Template class datalist;Templateclass Element{friend calss datalist;private:Type key;field otherdata;} ;public:Type getKey( ) { return key;}void setKey(const Type x) {key=x;}Element&operator=(Element&x){key=x->key;otherdata=x->otherdata;}Type operator == (Type &x){return key==x->key;}Type operator <= (Type &x) {return key<=x->key; }Type operator >= (Type &x) {return key>=x->key; }Type operator < (Type &x) {return keykey; }templateclass datalist{private:Element*Vector;int MaxSize,CurrentSize;int Partition(const int low,const int high)public;datalist (int MaxSz = DefaultSize):MaxSize( MaxSz) { };void Swap(Element &x, Element &y){Element temp=x;x=y;y=temp;}void Sort();}9.2 插入排序(Insert Sorting)基本原理，每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象适当位置上，直到对象全部插入为止。三种常见的插入排序分类原理，根据往已经排好序的有序数据表中寻找插入位置的方法的不同而区分。直接插入排序(Insert Sort)折半插入排序(Binary Insert Sort)链表插入排序希尔排序(Shell Sort)直接插入排序(Insert Sort)基本思想：当插入第i个对象时，前面的V[0],V[1],…,V[i-1]已经排好序，此时，用v[i]的关键码与V[i-1], V[i-2],…的关键码顺序进行比较，找到插入位置即将V[i]插入，原来位置上对象向后顺移。直接插入排序举例i (0) (1) (2) (3) (4) (5) temp[21] 25 49 25* 16 08 251 [21 25] 49 25* 16 08 492 [21 25 49] 25* 16 08 25*3 [21 25 25* 49] 16 08 164 [16 21 25 25* 49] 08 085 [08 16 21 25 25* 49]直接插入排序程序Templatevoid dataList::sort{Elementtemp;int j;for(int i=1;itemp=Vector[i];j=i;for(int j=i;j>0;j--)if (tempelse break;Vector[j]=temp;}}直接插入排序的时间复杂度考虑关键码的比较次数和对象移动次数， 最好情况时两者分别为n-1与2(n-1)，最坏情况时两者分别为KCN=1+2+...+n-1 = n(n-1)/2RMN= (1+2)+(2+2)+...+(n-1+2)= (n+4)(n-1)/2直接插入排序的稳定性直接插入排序是一种稳定的排序方法。原理：关键码相同的两个对象，在整个排序过程中，不会通过比较而相互交换。折半插入排序(Binary Insert Sort)基本思想：当插入第i个对象时，前面的V[0],V[1],…,V[i-1]已经排好序，此时，用折半查找法寻找V[i]的插入位置移。折半插入排序程序template void datalist ::sort(){int left, right; Element temp;for (int i=1;ileft=0;right=i-1;temp=Vector[i];while (left < =right) {int middle=(left+right)/2;if (temp right=middle-1;else left=middle+1;for (int k=i-1;k>=left; k--)Vector[k+1]=Vector[k];Vector[left] = temp;}折半插入排序的时间复杂度考虑关键码的比较次数和对象移动次数1. KCN 约为 n log 2 n，且与对象序列的初始排列无关当n较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况时要差。2. RMN与直接插入排序相同。折半插入排序的稳定性折半插入排序是一种稳定的排序方法。原理：关键码相同的两个对象，在整个排序过程中，不会通过比较而相互交换。链表插入排序基本思想：用链表来表示已排序的数据对象，当插入V[i]时，依次在链表中检查，找到V[i]应插入的位置，并修改相应的链接指针。如此重复，直到V[n]也插入到链表中排好序为止。链表插入排序的数据结构template class staticlinklist{templateclass Element{private:Type key; int link;public:Type getKey() {return key;}void setKey(const Type x) {key=x;}int getLink(){return link;}void setLink(const int ptr){link=ptr;}}链表插入排序的数据结构templateclass staticlinklist{private:Element * Vector;int MaxSize, CurrentSize;public:staticlinklist(int MaxSz=DefaultSize):MaxSize(MaxSize),CurrentSize(0){};}链表插入排序示例i index (0) (1) (2) (3) (4) (5) (6)key MaxNum 21 25 49 25* 16 8link 1 0 0 0 0 0 02 link 1 2 0 0 0 0 03 link 1 2 3 0 0 0 04 link 1 2 4 0 3 0 05 link 5 2 4 0 3 1 06 link 6 2 4 0 3 1 5链表插入排序的算法template int staticlinklist :: Sort(){Vector[0].key=MaxNum;Vector[0].link=1;Vector[1].link=0;for(int i=2; i<=CurrentSize; i++){int current =Vector[0].link; int pre = 0;while (Vector[current].key <=Vector[i].key){ pre=i; current=Vector[current].link;}Vector[i].link=current;Vector[pre].link=i;}}链表插入排序的时间复杂度考虑关键码的比较次数和对象移动次数1. KCN 最小为n-1，最大为 n (n-1)/22. 对象移动次数为0 。链表插入排序方法是稳定的。希尔排序1959年由D.L. Shell提出，又称缩小增量排序(Diminishing-increment sort) 。基本思想：在插入排序中，只比较相邻的结点，一次比较最多把结点移动一个位置。如果对位置间隔较大距离的结点进行比较，使得结点在比较以后能够一次跨过较大的距离，这样就可以提高排序的速度。希尔排序的基本过程设待排序的对象序列有n个对象，首先取一个整数gap希尔排序示例i (0) (1) (2) (3) (4) (5) gap21 25 49 25* 16 081 21 - - 25* 325 - - 1649 - - 0821 16 08 25* 25 492 21 - 08 - 25 216 - 25* - 4908 16 21 25* 25 493 08 16 21 25* 25 49 108 16 21 25* 25 49希尔排序的算法template void datalist ::sort(){Elementtemp;int gap=CurrentSize/2,i,j;while(gap!=0)for (int i=gap; i< CurrentSize;i++){temp = Vector[i];for (j=i;j>=gap;j-=gap)if (tempelse break;Vector[j] = temp;}gap=gap/2;}希尔排序中gap的取法Shell最初的方案是 gap= n/2, gap=gap/2，直到gap=1.Knuth的方案是gap = gap/3+1其它方案有，都取奇数为好；或gap互质为好等等。希尔排序的时间复杂度对希尔排序的复杂度的分析很困难，在特定情况下可以准确地估算关键码的比较和对象移动次数，但是考虑到与增量之间的依赖关系，并要给出完整的数学分析，目前还做不到。Knuth的统计结论是，平均比较次数和对象平均移动次数在n1.25 与1.6n1.25之间。希尔排序的稳定性希尔排序是一种不稳定的排序方法。如序列 3 2 2* 59.3 交换排序基本原理，两两比较待排序的对象的关键码，如果发生逆序，则交换之，直到全部对象都排好序为止。两种常见的交换排序起泡排序(Bubble Sort)快速排序(Quick Sort)起泡排序的基本过程假设待排序的n个对象的序列为V[0],V[1],..., V[n-1]，起始时排序范围是从V[0]到V[n-1]在当前的排序范围之内，自右至左对相邻的两个结点依次进行比较，让值较大的结点往下移(下沉)，让值较小的结点往上移(上冒)。每趟起泡都能保证值最小的结点上移至最左边，下一遍的排序范围为从下一结点到V[n-1]。在整个排序过程中，最多执行(n-1)遍。但执行的遍数可能少于(n-1)，这是因为在执行某一遍的各次比较没有出现结点交换时，就不用进行下一遍的比较。起泡排序示例i (0) (1) (2) (3) (4) (5)21 25 49 25* 16 081 08 21 25 49 25* 162 08 16 21 25 49 25*3 08 16 21 25 25* 494 08 16 21 25 25* 49起泡排序的算法Templatevoid datalist::sort(){int pass=1;int exchange=1;while (passexchange=0;for (int j=CurrentSize-1;j>=pass;j--)if (Vector[j-1]>Vector[j]){swap(Vector[j-1],vector[j])exchange=1;}pass++;}}起泡排序的时间复杂度考虑关键码的比较次数和对象移动次数1. KCN 为 n * (n-1) /22. RMN 为 3/2 * n* (n-1) 。起泡排序方法是稳定的。快速排序的基本过程快速排序法是一种所需比较次数较少，目前在内部排序中速度较快的方法。其思想是取待排序的结点序列中某个结点的值作为控制值，采用某种方法把这个结点放到适当的位置，使得这个位置的左边的所有结点的值都小于等于这个控制值，而这个位置的右边的所有结点的值都大于等于这个控制值。然后分别对这两个子序列重复实施上述方法.快速排序示例i (0) (1) (2) (3) (4) (5) pivot（基准)21 25 49 25* 16 08 211 08 16 21 25* 25 49 08(左),25*(右)2 08 16 21 25* 25 49 25(右)3 08 16 21 25* 25 494 08 16 21 25* 25 49快速排序的递归算法template void QuickSort(const int left, const int right) {if (leftint pivotpos = Partition (left, right);if (leftif (pivotpos+1>right) QuickSort(list,pivotpos+1,right);}快速排序的递归算法template int Partition(const int low, const int high){int pivotpos = low;Element pivot = Vector[low];for (int i=low+1; i<=high; i++)if(Vector[i]pivotpos++;if (pivotpos!i)Swap(Vector[pivotpos], Vector[i]);}Swap(Vector[low], Vector[pivotpos]);return pivotpos;}快速排序的时间复杂度考虑关键码的比较次数和对象移动次数1. 平均计算时间为O(n*log2n) ，实验表明，快速排序是我们所讨论过的内排序中，平均计算时间最快。2. 最坏情况总的关键码比较次数为 n* (n-1) /2，例如，对一个已经排序的序列进行快速排序。快速排序是不稳定的排序方法。如序列2, 3, 3*, 19.4 选择排序基本原理，将待排序的结点分为已排序(初始为空)和为未排序两组，依次将未排序的结点中值最小的结点插入已排序的组中。三种常见的选择排序直接选择排序锦标赛排序堆排序直接选择排序的基本过程在一组对象V[i]到V[n-1]中选择具有最小关键码的对象若它不是这组对象中的第一个对象，则将它与这组对象中的第一个对象对调。删除具有最小关键码的对象，在剩下的对象中重复第(1)、(2)步，直到剩余对象只有一个为止。直接选择排序示例i (0) (1) (2) (3) (4) (5) k[21 25 49 25* 16 08] 50 08 [25 49 25* 16 21] 41 08 16 [49 25* 25 21] 52 08 16 21 [25* 25 49] 33 08 16 21 25* [25 49] 44 08 16 21 25* 25 [49]直接选择排序的算法template void datalist :: sort() { for(int i=0;iint k=i;for (int j=i+1; jif (Vector[j]if (k!=i) Swap(Vector[i], Vector[k]);}}直接选择排序的时间复杂度考虑关键码的比较次数和对象移动次数1. KCN与对象的初始排列无关，总为 n* (n-1) /22. RMN与对象的初始排列有关，最少为0，最大为3(n-1) 。如：n-1,0,1,2,..., n-2直接选择排序是不稳定的排序方法。锦标赛排序的基本过程在一组对象V[i]到V[n-1]中选择具有最小关键码的对象若它不是这组对象中的第一个对象，则将它与这组对象中的第一个对象对调。删除具有最小关键码的对象，在剩下的对象中重复第(1)、(2)步，直到剩余对象只有一个为止。锦标赛排序示例i (0) (1) (2) (3) (4) (5) (6)21 25 49 25* 16 08 63 21 25* 08 6321 080821 25 49 25* 16 08 63 21 25* 16 6321 1616锦标赛排序的算法template class DataNode{public:Type data; int index; int active;}template void TournamentSort(Type a[ ], int n){DataNode *tree;DataNode item;int bottonRowSize = PowerOfTwo(n);int TreeSize = 2* bottomRowSize –1;int loadindex = bottomRowSize –1;tree = new DataNode [TreeSize];int j=0;for (int i= loadindex; itree[i].index = i;if (jelse tree[i].active = 0;}i = loadindex;while(i){j=i;while(j<2*i) {if (!tree[j+1].active || tree[j].data < tree[j+1].data)tree[(j-1)/2] = tree[j];else tree[(j-1)/2] = tree[j+1];j+=2;} i=(i-1)/2;}for (i=0; ia[i] = tree[0].data;tree[tree[0].index].active = 0;UpdateTree(tree,tree[0].index);}a[n-1] = tree[0].data;}template void UpdateTree(DataNode *tree, int i) {if ( i %2 == 0) tree[(i-1)/2] = tree[i-1];else tree[(i-1)/2] = tree[i+1];i=(i-1)/2;while (i) {if ( i % 2 == 0) j= i-1;else j=i+1;if (! tree[i].active || ! tree[j].active)if ( tree[i].active) tree[(i-1)/2] = tree[i];else tree[(i-1)/2] = tree[j];elseif ( tree[i].data < tree[j].data)tree[(i-1)/2] = tree[i];else tree[(i-1)/2] = tree[j];i = (i-1)/2;}}锦标赛排序的时间复杂度考虑关键码的比较次数和对象移动次数1. 比较次数为 O(log2n)2. 对象的移动次数不超过比较次数。所以总的时间复杂度为O(n log2n)锦标赛排序是稳定的排序方法。堆排序利用第6章介绍的堆及其运算，可以方便地实现选择排序的思路。堆排序分为两个步骤：根据初始输入，形成初始堆。通过一系列的对象交换和重新调整进行排序。堆的定义完全二叉树的数组表示Ki K2i+1 &&Ki K2i+2Ki K2i+1 &&Ki K2i+2堆排序示例i (0) (1) (2) (3) (4) (5)21 25 49 25* 16 08初始堆为：2125 4925* 16 08调整后的最大堆为：4925 2125* 16 08堆排序示例（续）交换0号与5号元素后为：0825 2125* 16 49调整后的堆为：2525* 2108 16最大堆的向下调整算法template void MaxHeap::FilterDown (const int i,const int EndOfHeap ){int current = i; int child = 2*i+1;Type temp = heap[i];while ( child <= EndOfHeap ) {if ( child+1 < EndOfHeap &&heap[child]if ( temp>= heap[child]) break;else {heap[current] = heap[child];current = child; child = 2 * child +1;}} heap[current] = temp;}堆排序的算法template void datalist ::sort() {for (int i=(CurrentSize –1)/2; i>=0; i--)FilterDown(i, CurrentSize-1);for (int i=(CurrentSize –1); i>=1; i--) {Swap( heap[0], heap[i]);FilterDown(0,i-1);}堆排序的时间复杂度堆排序的时间复杂性为O(n log2n)空间复杂性为 O(1)堆排序是不稳定的排序方法。9.5 归并排序基本原理，通过对两个或两个以上的有序结点序列的合并来实现排序。如果是对两个已经排好序的序列的合并来实现排序，称为“两路归并”(2-way merging) 。两路归并的基本思想设有两个有序表A和B，对象个数分别为al和bl，变量i和j分别是两表的当前指针。设表C是归并后的新有序表，变量k是它的当前指针。i和j对A和B遍历时，依次将关键码小的对象放到C中，当A或B遍历结束时，将另一个表的剩余部分照抄到新表中。两路归并的示例initList08 21 25 25* 49 62 72 93 16 37 54归并后为mergedList08 16 21 25 25* 37 49 54 62 72 93两路归并的算法template void merge(datalist &mergedList,const int left, const int mid, const int right) {int i=left; j=mid+1; k=left;while(i<=m && j<=n)if (Vector[i]{mergedList.Vector[k]=Vector[i];i++;k++;}else{mergedList.Vector[k]=Vector[j];j++;k++;} if (I<=mid) for(int n1=k,n2=I;n2<=mid;n1++;n2++) mergedList.vector[n1]=vector[n2]; }两种常见的归并排序迭代的归并排序算法递归的表归并排序迭代的归并排序假设初始的对象序列有n个对象，我们首先把它看成是n个长度为1的有序子序列，先做两两归并，得到n/2个长度为2的归并项（如果n为奇数，则最后一个有序子序列的长度为1）；再做两两归并，……，如此重复，最后得到一个长度为n的有序序列。归并排序的过程算法template void MergePass(datalist &mergedList, const int len) {int i=0;while(i+2*len <= CurrentSize-1) {merge(mergedList,i, i+len-1, i+2*len-1);i+=2*len; } if (I+len<=CurrentSize-1) else for(int j=i;j<=CurrentSize-1;j++) mergedlist.Vector[j]=Vector[j];迭代的归并排序的时间复杂度MergeSort调用 log2n 次，总的时间复杂度为O(n log2n)空间开销为需要一个与原待排序对象数组同样大小的辅助数组。迭代的归并排序是稳定的排序方法。递归的表归并排序首先把整个待排序序列划分为两个长度大致相等的部分，分别称为左子表和右子表。对这些子表分别递归地进行排序，然后再把排好序的两个子表进行归并。递归的表归并的示例存储表示的选择在归并时，若采用基于数组的两路归并算法，由于需要进行数组元素的传递，影响了归并的效率。若对排序的对象采用静态链表的存储表示，则可以得到一种有效的归并排序算法。静态链表的数据结构同链表插入排序中的数据结构template class staticlinklist{private:struct Element{Type key;field otherdata;int link;public:Type getKey() {return key;}void setKey(const Type x) {key=x;}void operator = (Element &item){ this = item; }void Swap(Element &x,Element &y){Element temp=x; x=y; y=temp;}}public:staticlinklist(int MaxSz=DefaultSize):MaxSize(MaxSize){};void MakEmpty(){Vector[0].link=0; CurrentSize=0;}private:Element * Vector;int MaxSize, CurrentSize;}静态链表的数据结构初始时，置所有的Vector[i].link = 0，即每个链表结点都是一个独立的单链表。函数ListMerge()将两个有序单链表归并为一个单链表的算法。链表的归并算法template int staticlinklist::ListMerge (const int start1, const int start2) {int k=0, i=start1, j=start2;while(i!=0 && j!=0)if (Vector[i].key <= Vector[j].key){ Vector[k].link=i;k=i;i=Vector[i].link;}else {Vector[k].key=j; k=j;j= Vector[j].link;}if (i==0)Vector[k].link=j;else list.Vector[k].link=i;return list.Vector[0].link;}template int staticlinklist ::sort(int left, int right) {if ( left >= right ) return left;int middle = (left + right) / 2;return ListMerge (sort(left,middle), sort(middle+1,right));}链表的归并排序的时间复杂度递归深度为O(log2n)，总的时间复杂度为O(n log2n)对象的移动次数为0链表的归并排序是稳定的排序方法。9.6 基数排序基本原理，采用“分配”和“收集”的办法，用对多关键码进行排序的思想实现对单关键码进行排序的方法。下面先介绍多关键码排序多关键码排序方法示例如对扑克牌的排序每张扑克牌有两个“关键码”：花色和面值它们之间有次序的优先。对以上排序，可以先对花色排序，或先对面值排序。多关键码有序的概念考虑对象序列{V0,V1,..., Vn-1}，每个对象Vi含d个关键码(Ki1,Ki2,..., Kid)。若对序列中的任意两个对象Vi和Vj都有(Ki1,Ki2,..., Kid) < (Kj1,Kj2,..., Kjd)则称序列对关键码(Ki1,Ki2,..., Kid)有序，且K1称为最高位关键码，Kd称为最低位关键码。多关键码排序原理：根据组成关键码的各位的值进行排序。实现基数排序的两种方法：1 最高位优先(MSD)排序：从关键码的高位到低位2 最低位优先(LSD)排序：从关键码的低位到高位MSD方法通常是一个递归的过程。多关键码排序（续）LSD和MSD方法也可应用于对一个关键码进行的排序。此时可将单关键码Ki看成是一个子关键码组：(Ki1,Ki2,..., Kid)如对关键码取值范围为0到999的一组对象，可看成是(K1,K2,K3)的组合。MSD方法按K1,K2,K3的顺序对所有对象排序；LSD方法按K3 ,K2 , K1的顺序对所有对象排序。链式的基数排序基数排序是一种典型的LSD排序方法，它利用“分配”和“收集”两种运算对单关键码进行排序。此时可将单关键码K看成是一个子关键码组：(Ki1,Ki2,..., Kid)排序过程：设关键码共有d位，让j= d, d-1,...,1, 依次执行d次“分配”与“收集”。(共41张PPT)第十章 索引与散列静态索引结构动态索引结构散列10.1 静态索引结构10.1.1 线形索引索引表：由一组关键码和对象地址组成的索引项构成。线形索引：在一个线形表中存放对象的索引项。一个索引项对应数据表中一个对象的索引结构叫做稠密索引。数据表对象在外存中按加入的顺序存放而不是按关键码有序存放的索引结构。称为索引非顺序结构。如果对象在外存中有序存放,可以采用子表索引.子表索引要求做到分块有序。即后一个子表中所有的关键码均大于前一个子表中所有对象的关键码。图10.2所示的结构是索引顺序结构。它由索引表和子表构成。索引时首先在索引表中搜索给定值K，然后根据ID[i-1].max_key索引顺序搜索成功的平均搜索长度为： ASLIndexSeq=ASLIndex+ASLSublist 设把长度为n的表分成均等的b个子表，每个子表有S个对象，则b=n/s.又设表中每个对象的搜索概率相等。子表为1/b，子表内各对象为1/s，则顺序搜索的平均搜索长度为： ASLIndexSeq=(b+1)/2+(s+1)/2=(b+s)/2+1 子表内折半搜索成功平均搜索程度为： ASLIndexSeq=log2(b+1)-1+(s+1)/2=log(1+n/s)+s/2 可见，索引搜索的平均搜索长度与表的长度n和子表 内对象的个数S有关。10.1.2 倒排表 主关键码建立的索引为主搜索。非主关键码建立的索引叫次索引。次索引由次关键码、链表长度和链表本身组成。倒排表是次索引的一种实现。在倒排表中所有次关键码的链都保存在次索引中。倒排表一般的搜索步骤是：首先通过次索引找到主索引的主关键码，再通过主关键码找到相应的对象。10.1.3 m路静态搜索树当数据对象数目特别大，索引表本身也很大，在内存中放不下，可以建立索引的索引，称为二级索引。如果二级索引内存中也放不下，可以建立多级索引，这种多级索引结构形成一种m叉树。每一个分支结点表示一个索引块，最多有m个索引块，每个索引块分别给出各子树结点最大关键码和结点地址树的叶结点中各索引项给出在数据表中存放的对象的关键码和存放地址。这种m叉树用来作为多级索引，就是m路搜索树.10.2 动态索引结构动态的m路搜索树的定义为：一个空树或满足以下条件 (1)根结点最多有m棵子树，并具有如下的结构： n,P0,(K1,P1),(K2,P2),…,(Kn,Pn) 其中，Pi是指向子树的指针，0≤i≤n≤m;Ki是关键码(2)Ki(4)在子树Pn中所有的关键码都大于Kn,而子树P0中的所有关键码都小于K1. (5)子树Pi也是m路搜索树，0≤i≤n.m路搜索树的C++描述： templateclass Mtree{ protected: Mnoderoot; int m; public: Triple&search(const Type&); AVL树是2路搜索树。已知m路搜索树的度为m和它的高度为h，则树的最大结点数为：Triple resule getnode(root); mnode*p=root,*p=NULL; while (p!=NULL){ int I=0;p->key[(p->n)+1]=MAXKEY; while(p->key[I+1]key[I+1]==x){ result.r=p;result.I=I+1;result.tag=0; return result; } q=p;p=p->ptr[I];getnode(p); } result.r=p;result.I=I+1;result.tag=1;return result;}对于给定的关键码数n，如果搜索树是平衡的，可以使m路搜索树的性能接近最佳.10.2.2 B树 一棵m阶B树是一棵平衡的m路搜索树，它或者是空树，或满足下列条件。 (1)根结点至少有两个子女 (2)除根结点以外的所有结点(不包括失败结点)至少有m/2个子女。 (3)所有的失败结点都位于同一层。B树的类声明和B树结点类的声明如下： templateclass Btree;public Mtree{ public: int insert(const Type&x); int remove(const Type &x); }; templateclass Mnode; private; int n; Mnode*parent; Type key[m+1]; Mnode*ptr[m+1]; }; struct Triple{ Mnode*r; int I;int tag; };B树的搜索过程是一个在结点内搜索和循某一条路径向下一层搜索交替进行的过程。因此，B树的搜索时间与B树的阶层m和B树的高度h直接有关。B树的高度h与关键码个数N的关系为： h≤logm/2((N+1)/2)+110.2.3 B树的插入 B树是从空树起，逐个插入关键码而生成的。但在插入关键码时，如果结点中关键码的个数超过m-1，则结点要发生“分裂” .否则直接插入. 实现结点“分裂”的原则是: 设结点P已经有m-1个关键码,当再插入一个关键码后结点中的状态为 (m,P0,K1,P1,K2,P2,…,Km,Pm),其中Ki结点p:(m/2-1,P0,K1,P1,…,Km/2-1,Pm/2-1) 结点q:(m-m/2,Pm/2,Km/2+1,Pm/2+1,…,Km,Pm) 位于中间的关键码Km/2与指向新结点q的指针形成一个二元组(Km/2,q)插入到这两个结点的双亲结点中.10.2.4 B树的删除 删除非叶结点的关键码.将被删关键码Ki删除,并从Pi所指示的子树中的最小关键码x代替Ki,然后将x所在的叶结点中将x删除. 在叶结点上删除有四种情况: (1)若被删关键码所在的叶结点同时又是根结点,且该结点中关键码的个数n≥2,可直接删除. (2)若被删关键码所在的叶结点不是根结点,且该结点中关键码的个数n≥m/2,可直接删除.(3)被删关键码所在叶结点删除前关键码有n=m/2-1,若这是与该结点相邻的右兄弟(或左兄弟)结点的关键码个数n≥m/2,则可按以下的步骤调整左、右兄弟和双亲结点。 a. 将双亲结点中刚刚大于(或小于)被删关键码Ki下移到被删关键码所在的结点中。 b. 将右兄弟(或左兄弟)结点中最小(或最大)关键码上移到双亲结点Ki位置。 c. 将右兄弟(或左兄弟)结点中最左(或最右)子树指针平移到被删关键码所在结点最后(或最前)子树指针位置。 d. 将右兄弟(或左兄弟)结点中，将被移走的关键码和指针位置用剩余的关键码和指针填补、调整，再将结点中的关键码个数减一。(4)被删关键码所在的叶结点关键码的个数为n=m/2-1,若这时右兄弟(或左兄弟)结点的关键码个数n=m/2-1,则必须按以下步骤合并这两个结点。 a. 将双亲结点p中相应关键码下移到选定保留的结点中，若要合并p中的子树指针Pi和Pi+1所指的结点，且保留Pi所指的结点，则把p中的关键码Ki+1下移到Pi所指的结点中。 b. 把p中子树指针Pi+1所指结点中的全部指针和关键码都照搬到Pi所指结点的后面。删去P i+1所指的结点。 c. 在双亲结点p中用后面剩余的关键码和指针填补关键码Ki+1和指针Pi+1。 d. 修改双亲结点p和选定保留结点的关键码个数.10.2.5 B+数 B+树的定义如下：(1)树中每个结点最多有m棵树 (2)根结点(非叶结点)至少有2棵树,除根结点外，其他的非叶结点至少有m/2棵子树，有n棵子树的非叶结点有n-1个关键码。 (3)所有的叶结点都处于同一层次上，包含了全部关键码及指向相应数据对象存放地址的指针，且叶结点本身按关键码从小到大顺序链接。 (4)每个叶结点中子树棵数可以多于m，可以少于m，视关键码字节及对象地址指针字节数而定。若设结点可容纳最大关键码数为m1，则指向对象地址指针也有m1个，因此，结点中的子树棵数应满足n∈[m1/2,m1]. (5)所有的非叶结点可以看成是索引部分。结点格式同b树在图10.15中所有非叶结点中子树的棵数n∈[2,4],其所有的关键码都出现在叶结点中。上层结点中的关键码都是其右子树上最小关键码的副本。 B+树有两个指针，一个指向树的根结点，一个指向关键码最小的结点。因此，可以对B+树进行两种搜索，一种是从根结点开始，另一种是循叶结点自己拉起的链表顺序搜索。 在B+树上搜索在非叶结点上找到给定值，搜索并不停止，一直要找到叶结点上的给定值，搜索才结束。因此，每次搜索都从根结点走到叶结点。在B+树中删除叶结点中的最小关键码，并不需要删除上层结点中的副本。因为其上层的副本只起引导搜索的“分界关键码”的作用。10.3 散列(Hashing) 10.3.1 词典的抽象数据类型 在计算机科学中，词典也当作一种抽象数据类型。在讨论词典抽象数据类型时，把词典定义为<名字-属性>对的集合。通常用文件或表格来表示实际的对象集合，用文件中的记录或表格中的表项来表示单个对象。<名字-属性>被存于记录(或表项)中，通过表项的关键码来标识该表项。表项的存放位置及其关键码之间的对应关系可以用一个二元组表示： (关键码key,表项位置指针) 这个二元组构成了搜索某一指定表项的索引项。可以使用多种方式搜索索引项。但是使用散列结构是一种搜索效率很高的词典的组织方法。 10.3.2 散列表与散列方法 散列方法在表项的存储位置与它的关键码之间建立一个确定的对应函数关系Hash(),使每个关键码与结构中的唯一存储位置相对应： Address=Hash(Rec.key)散列方法：在存放表项时，通过相同函数计算存储位置，并按此位置存放，这种方法称为散列方法。 散列函数：在散列方法中使用的函数。 散列表：按上述方法构造出来的表称为散列表。 通常关键码集合比散列表地址集合大的多，因此有可能经过散列函数的计算，把不同的关键码映射到同一个散列地址上。称这些散列地址相同的不同关键码为同义词。 对于散列方法需要讨论两个问题 (1)对于给定的一个关键码集合，选择一个计算简单且地址分布比较均匀的散列函数，避免或尽量减少冲突。 (2)拟订解决冲突的方案。 10.3.3散列函数 构造散列函数应注意以下几个问题： (1)散列函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址，其值域必须在1～m-1之间。 (2)散列函数计算出来的地址应能均匀分布在整个地址空间中。 (3)散列函数应是简单的。1.直接定址法 此类方法取关键码的某个线形函数值作为散列地址： Hash(key)=a*key+b {其中a,b为常数} 这类散列函数是一对一的映射，一般不会产生冲突。但是，它要求散列地址空间的大小与关键码集合的大小相同，这种要求一般很难实现。 2.数字分析法 设有n个d位数，每一位可能有r种不同的符号。这r种不同的符号在各位上出现的频率不一定相同。可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址。计算各位数字中符号分布均匀度其中， 表示第I个符号在第k位上出现的次数，n/r表示各种符号在n个数中均匀出现的期望值。计算 值越小，表明在该位各种符号分布的越均匀。3.除留余数法 设散列表中允许的地址数为m，取一个不大于m，但最接近或等于m的质数p，或选取一个不含有小于20的质因子的合数作为除数。这样的散列函数为： hash(key)=key%p p≤m 其中，“%”是整数除法取余的运算，要求这时的质数p不是接近2的幂。4.平方取中法 先计算构成关键码的表示符的内码的平方，然后按照散列表的大小取中间的若干位作为散列地址。在平方取中法中，一般取散列地址为2的某次幂。5.折叠法 有两种方法： (1)移位法----把各部分的最后一位对齐相加。 (2)分界法----各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相加的结果当作散列地址。10.3.4 处理冲突的闭散列方法 若设散列表有m个地址，将其改为m个桶。其桶号与散列地址一一对应。每个桶可存放s个表项。如果对不同的关键码用散列函数计算得到同一个散列地址，就产生了冲突，它们可以放到桶内的不同位置，只有当桶内所s个表项都放满后才会产生冲突。处理冲突的一种常用的方法就是闭散列，也叫开地址法。所有的桶都直接放在散列表数组中。因此，每一个桶只有一个表项。如果在存放表项时发现，该位置已被别的表项占据，则在整个表中查找新的位置，如果表未被装满，则在允许的范围内必定有新的位置。查找的主要方法有3种。 1.线形探测法 方法为：一旦发生冲突，在表中顺序向后寻找“下一个”空桶Hi的递推公式为:Hi=(Hi-1+1)%m i=1,2,….,m-1或 Hi=(H0+I)%m I=1,2,….,m-1实例:已知关键码Burke,Ekers,Broad,Blum,Attlee,Alton,Hecht, Ederly 散列函数为:Hash(x)=ord(x)-ord(‘a’) 可得:Hash(Burke)=1,Hash(Ekers)=4,Hash(Broad)=1, Hash(Blum)=1,Hash(Attlee)=0,Hash(Alton)=0, Hash(Hecht)=7, Hash(Ederly)=4 0 1 2 3 4 5 6 72.二次探查法 线形探查法容易产生“堆积”的问题,即不同探查序列的关键码占据可利用的空桶,使得为寻找某一关键码需要经历土同的探查序列的元素,导致搜索时间增加. 使用二次探查法,在表中寻找“下一个”空桶的公式为: Hi=(H0+i2)%m,Hi=(H0-i2)%m,I=1,2,3,…,(m-1)/2 式中H0=hash(x)是通过某一个散列函数hash()对表项的关键码x进行计算得到的桶号,它是一个非负整数.m是表的大小,它应是Attle Burk Broa Blum Eker Alto Eder Hech一个值为4k+3的质数,其中k是一个整数. 实例:若设表的长度为Tablesize=31,根据线形探查结果利用二次探查法所得到的结果为: 0 1 2 3 4 5 6 7Blum Burk Broa Eker Ederl Hech21 22 23 24 25 26 27 30Alton Attle设散列表的桶数为m,待查表项的关键码为x,第一次通过散列函数计算出来的桶号为H0=hash(x).当发生冲突时,第i-1次和第i次次计算出来的“下一个”桶号为:将上述两式相加可以得到:从上述式子可以知道,只要知道上一次桶号Hi-1就可以知道下一个桶号Hi.3.双散列法 使用散列方法时,需要使用两个散列函数.第一个散列函数Hash()按表项的关键码key 计算表项所在的桶号.一旦发生冲突,利用第二个散列函数ReHash()计算该表项“下一个”桶的移位量.10.3.5 处理冲突的开散列方法----链地址法 链地址法处理冲突的方法是,将通过散列函数计算出来地址相同的关键码通过链表链接起来,各链表表头结点组成一个向量.向量的元素个数与桶数一致表头.(共44张PPT)第三章 栈和队列3.1 栈3.1.1 抽象数据类型栈的定义3.1.2 栈的表示和实现3.2 栈的应用举例3.2.1 数制转换3.2.2 括号匹配的检验3.2.4 行编辑程序3.2.5 迷宫求解3.2.5 表达式求值3.1.1 栈3.1.1 栈的定义及基本运算栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。3.1.2 顺序栈由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top。例、一叠书或一叠盘子。栈的抽象数据类型的定义如下：a na n-1a2a1……栈顶栈底top7 6 5 4 3 2 1-1来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。顺序栈的类型定义如下：# define StackSize 100typedef char datatype;typedef struct {datatype data[stacksize];int top;}seqstack;设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即s–>data[0]是栈底元素，那么栈顶指针s–>top是正向增加的，即进栈时需将s–>top加1，退栈时需将s–>top 减1。因此，s–>top<0表示空栈， s–>top =stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。3、判断栈满int stackfull(seqstack *s){return(s–>top==stacksize-1);}4、进栈void push(seqstack *s，datatype x){if (stackfull(s))error(“stack overflow”);s–>data[++s–>top]=x;}1、置空栈void initstack(seqstack *s){s–>top=-1;}2、判断栈空int stackempty(seqstack *s){return(s–>top==-1);}5、退栈datatype pop(seqstack *s){if(stackempty(s))error(“stack underflow”);x=s–>data[top];s–>top--;return(x)//return(s–>data[s–>top--]);}6、取栈顶元素Datatype stacktop(seqstack *s){if(stackempty(s)error(“stack is enpty”);return s–>data[s–>top];}3.1.3 链栈栈的链式存储结构称为链栈，它是运算是受限的单链表，插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。链栈的类型说明如下：typedef struct stacknode{datatype datastruct stacknode *next}stacknode;Void initstack(seqstack *p){p–>top=null;}int stackempty(linkstack *p){return p–>top==null;}Void push(linkstack *p,datatype x){stacknode *q q=(stacknode*)malloc(sizeof(stacknode));q–>data=x;q–>next=p–>top;p–>top=p;}Datatype pop( linkstack *p){datatype x;stacknode *q=p–>top;if(stackempty(p)error(“stack underflow.”);x=q–>data;p–>top=q–>next;free(q);return x;}datatype stack top(linkstack *p){if(stackempty(p))error(“stack is empty.”);return p–>top–>data;}3.2 栈的应用举例由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。3.2.1 数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(n div d)*d+n mod d( 其中:div为整除运算,mod为求余运算)例如 (1348)10=(2504)8，其运算过程如下：n n div 8 n mod 81348 168 4168 21 021 2 52 0 2void conversion( ) {initstack(s);scanf (“%”,n);while(n){push(s,n%8);n=n/8;}while(! Stackempty(s)){pop(s,e);printf(“%d”,e);}}3.2.2 括号匹配的检验假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例：（（）（） （（）））3.2.3 行编辑程序在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。行编辑程序算法如下:void lineedit( ){initstack(s);ch=gether( );while(ch!=eof){while(ch!=eof && ch!=‘\n’){switch(ch){case ‘#’ : pop(s,c);case ‘@’ : clearstack(s);default : push(s,ch);}ch=getchar( );}clearstack(s);if(ch!=eof)ch=gethar( );}destroystack(s);}3.2.4 迷宫求解入口出口3.4 队列3.4.1 抽象数据类型队列的定义队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。 例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。 当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an ，也就是说队列的修改是依先进先出的原则进行的。下图是队列的示意图： a1 a2 … an 出队入队队头队尾队列的抽象数据定义见书Ｐ593.4.2 循环队列－队列的顺序表示和实现 队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置，它们的初始值地队列初始化时均应置为０。入队时将新元素插入所指的位置，然后将加１。出队时，删去所指的元素，然后将加１并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。 ０ １ ２ ３ 0 1 2 3 Frontreara b cFront rear(a)队列初始为空 （b）A,B,C入队 ０ １ ２ ３ ０ １ ２ ３b cfront rear frontrear（c) a出队 (d) b,c出队，队为空和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在“假上溢”现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（Circular Queue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为：if(I+1==QueueSize)i=0;elsei++;利用模运算可简化为： i=(i+1)%QueueSize显然，因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。如图所示：由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。解决此问题的方法至少有三种：其一是另设一个布尔变量以匹别队列的空和满；其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；其三是使用一个计数器记录队列中元素的总数（实际上是队列长度）。下面我们用第三种方法实现循环队列上的六种基本操作，为此先给出循环队列的类型定义。#define QueueSize 100typedef char DataType;typedef Struct{int front;int rear;int count;datatype data[queuesize]}cirqueue;（1）置空队void initqueue(cirqueue *q){q–>front=q–>rear=0;q–>count=0;}（2）判断队空int queueempty(cirqueue *q) {return q–>count==0;}（3）判断队满int queuefull(cirqueue *q){return q–>count==queuesize;}（4）入队void enqueue(cirqueue *q,datatype x){if(queuefull(q))error(“queue overflow”);q–>count++;q–data[q–rear]=x;q–rear=(q–rear+1)%queuesize;}（5）出队datatype dequeue(cirqueue *q){datatype temp;if(queueempty(q))error(“queue underflow”);temp=q–>data[q–>front];q–>count--;q–front=(q–>front+1)%queuesize;return temp;}（6）取头指针datatype queuefront(cirqueue *q){if(queueempty(q))error(“queue is empty.”);return q–>data[q–>front];}3.4.3 链队列队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由一个头指针唯一确定。和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型LinkQueue定义为一个结构类型：typedef struct queuenode{datatype data;struct queuenode *next;}queuenode;typedef struct{queuenode *front;queuenode *rear;}linkqueue;下面给出链队列上实现的基本运算：void initqueue(linkqueue *q){q–>front=q–>rear=null;}int queueempty(linkqueue *q){return q–>front==null &&q–>rear==null;}void enqueue(linkqueue *q,datatype x){queuenode *pp=(queuenode * )malloc(sizeof(queuenode));p–>data=x;p–next=null;if(queueempty(q))q–>front=q–>rear=p;else{q–>rear–>next=p;q–rear=p;}}Datatype dequeue(linkqueue *q){datatype x;queuenode *pif(queueempty(q))error(“queue underflow”);p=q–>front;x=p–>data;q–>front=p–>next;if(q–>rear==p)q–rear=null;free(p);return x;}datatype queuefront(linkqueue *q){if(queueempty(q))error(“queue is empty.”);return q–>front–>data;}注意：在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。习题1、设将整数以万计、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问题：（1）若入栈次序为push(1)，pop()，push(2，push(3)，pop()，pop( )，push(4)，pop( )，则出栈的数字序列为什么？（2）能否得到出栈序列车员423和平共处五项原则432？并说明为什么不能得到或如何得到。（3）请分析1、2、3、4的24种排列中，哪些序列可以通过相应的入出栈得到。2、链栈中为何不设头指针？3、循环队列的优点是什么？如何判断它的空和满？4、设长度为n的链队列用单循环链表表示，若只设头指针，则怎样进行入队和出队操作；若只设尾指针呢？5、利用栈的基本操作，写一个返回栈s中结点个数的算法int stacksize(seqstack s)，并说明s为何不用作为指针参数？6、利用栈的基本操作，写一个将栈中所有结点均删除算法，并说明S为何要作为指针参数？7、用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试设计置空队、判队空、判队满、出队、入队及取队头元素等六个基本操作。8、假设循环队列只设rear和quelen来分别指示队尾元素的位置和队中元素的个数，试给出判断此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头指针。9、指出下列程序段的功能是什么？(1) void demo1(seqstack *s){int I;arr[64];n=0;while (!stackempty(s)) arr[n++]=pos(s);for(I=0;}(2) void demo2(seqstack *s,int m){seqstack t; int i;initstack(t);while(! Stackempty(s))if(I=pop(s)!=m) push(t,I);While(! Stackempty(t)) {i=pop(t);push(s,I);}}(共12张PPT)四皇后问题递归应用四皇后问题图像演示1 2 3 4调用的过程Try(1)四皇后问题图像演示1 2 3 4调用的过程Try(1)Try(2)四皇后问题图像演示1 2 3 4调用的过程Try(1)Try(2)Try(3) 失败四皇后问题图像演示1 2 3 4调用的过程Try(1)Try(2)四皇后问题图像演示1 2 3 4调用的过程Try(1)Try(2)Try(3)四皇后问题图像演示1 2 3 4调用的过程Try(1)Try(2)Try(3)Try(4)四皇后问题图像演示1 2 3 4调用的过程Try(1)Try(2)Try(3)四皇后问题图像演示1 2 3 4调用的过程Try(1)四皇后问题图像演示1 2 3 4调用的过程Try(1)Try(2)四皇后问题图像演示1 2 3 4调用的过程Try(1)Try(2)Try(3)四皇后问题图像演示1 2 3 4调用的过程Try(1)Try(2)Try(4)找到一组解！！Try(3)(共9张PPT)栈和队列图象演示空栈PUSH 1PUSH 3PUSH 5PUSH 7POPPOPPOP135531栈队列headtail空队列1队列headtail空队列PUSH 11队列head空队列PUSH 1PUSH 33tail1队列head空队列PUSH 1PUSH 33PUSH 5 队满tail5队列空队列PUSH 1PUSH 33PUSH 5 队满tail5POPhead1队列空队列PUSH 1PUSH 33PUSH 5 队满tail5POPhead1POP队列空队列PUSH 1PUSH 33PUSH 5 队满tail5POPhead1POPPOP 展开更多...... 收起↑ 资源列表 四皇后问题.ppt 栈和队列.ppt 第一章绪论.ppt 第七章 图.ppt 第三章栈和队列.ppt 第九章排序.ppt 第二章线性表.ppt 第五章数组和广义表.ppt 第六章树和二叉树.ppt 第十章 索引与散列.ppt 第四章串.ppt
资源列表