高级数据结构

高级数据结构教材：《数据结构（C++描述）》（金远平编著，清华大学出版社）JYP1代价分摊（1.5.4）将孤立地分析一次算法调用得出的结论应用于一个ADT的相关操作序列会产生过于悲观的结果。例1.12整数容器Bag。classBag{public:Bag(intMaxSize=DefaultSize);//假设DefaultSize已定义intAdd(constintx);//将整数x加入容器中intDelete(constintk);//从容器中删除并打印k个整数private:inttop;//指示已用空间int*b;//用数组b存放整数intn;//容量};JYP2各操作的实现如下：Bag::Bag(intMaxSize=DefaultSize):n(MaxSize){b=newint[n];top=-1;}intBag::Add(constintx){if(top==n-1)return0;//返回0表示加入失败else{b[++top]=x;return1;}}JYP3intBag::Delete(constintk){if(top+1k)return0;//容器内元素不足k个，删除失败else{for(inti=0;ik;i++)coutb[top–i]“”;top=top-k;return1;}}先分析操作成功的情况：Add(x)的时间复杂性是O(1)；Delete(k)需要k个程序步，且k可能等于n，在最坏情况下其时间复杂性是O(n)；一个调用Add操作m1次，Delete操作m2次的序列的总代价则为O(m1+m2n)。JYP4前面是常规分析的结论。进一步观察：如果一开始容器为空，则删除的元素不可能多于加入的元素，即m2次Delete操作的总代价不可能大于m1次Add操作的总代价。因此，在最坏情况下，一个调用Add操作m1次，Delete操作m2次的序列的总代价为O(m1)。操作失败时，Add(x)和Delete(k)的时间复杂性都是O(1)。因此，在操作可能失败的情况下，一个调用Add操作m1次，Delete操作m2次的序列的总代价为O(m1+m2)。JYP5常规分析并没有错，只是其推导出的总代价上界远大于实际可得的上界。其原因是这种分析法没有注意到连续的最坏情况删除是不可能的。为了取得更准确的结果，还应该度量ADT数据结构的状态。对于每一个可能的状态S，赋予一个实数(S)。(S)称为S的势能，其选择应使得(S)越高，对处于S状态的数据结构成功进行高代价操作的可能越大。例如，将容器元素个数作为容器状态的势能就很合理，因为元素越多，对容器成功进行高代价操作的可能越大。JYP6考虑一个由m个对ADT操作的调用构成的序列，并设ti是第i次调用的实际代价，定义第i次调用的分摊代价ai为ai=ti+(Si)–(Si-1)Si-1是第i次调用开始前ADT数据结构的状态，Si是第i次调用结束后ADT数据结构的状态。设的选择使得(Sm)≥(S0)，则JYP7即，分摊代价的总和是实际代价总和的上界。例1.12将容器元素个数作为(S)。若操作序列始于空容器，则(Sm)≥(S0)总是成立。下表反映了容器(S)的典型变化情况。JYP8对于Add操作，ti=1，(Si)–(Si-1)=1，所以ai=2；对于Delete操作，ti=k，(Si)–(Si-1)=–k，所以ai=0。任何一个调用Add操作m1次，Delete操作m2次的序列的总代价为O(m12+m20)=O(m1)。JYP9可见，分摊分析法将偶尔出现的高价操作调用的代价分摊到邻近的其它调用上，故而得名。而且，当用分摊分析法得到的一个操作调用序列的代价总和比用常规分析法得到的代价总和小时，人们就得到了更接近实际代价的分析结果，或者说对算法时间复杂性的判断更准确了。JYP10两个字符串的最长公共子序列（2.4.3）一个字符串的子序列通过从字符串中删除零或多个任意位置的字符得到。两个字符串x和y的最长公共子序列记为lcs(x,y)。例如，x=abdebcbb，y=adacbcb，则lcs(x,y)是adcbb和adbcb，如下所示：JYP11问题的基本求解方法：用标记空串，则lcs(x,)=lcs(,y)=。lcs(xa,ya)=lcs(x,y)a，即xa和ya的最长公共子序列由x和y的最长公共子序列后接a构成。若xa和yb的最后一个字符不相等，则当lcs(xa,yb)不以a结尾时一定等于lcs(x,yb)，当lcs(xa,yb)不以b结尾时一定等于lcs(xa,y)。因此lcs(xa,yb)等于lcs(x,yb)与lcs(xa,y)中较长者。JYP12由此可得计算两个字符串最长公共子序列长度的递归算法lcs:intString::lcs(Stringy){//驱动器intn=Length(),m=y.Length();returnlcs(n,m,y.str);}intString::lcs(inti,intj,char*y){//递归核心if(i==0||j==0)return0;if(str[i-1]==y[j-1])return(lcs(i-1,j-1,y)+1);returnmax(lcs(i-1,j,y),lcs(i,j-1,y));}JYP13设x的长度为n，y的长度为m，在最坏情况下lcs的时间复杂性为w(n,m)。w(n,m)=因此，w(n,m)≥2w(n-1,m-1)≥…≥2min(n,m)c，即lcs的时间复杂性是指数型的。进一步可发现，lcs(i,0)=0（0≤i≤n），lcs(0,j)=0（0≤j≤m）。lcs(i,j)的计算依赖于lcs(i–1,j–1)、lcs(i–1,j)和lcs(i,j–1)，如下图所示：c（c为常数）n=0或m=0w(n,m-1)+w(n-1,m)否则JYP14根据以上拓扑关系，可以在不用递归的情况下计算lcs(i,j)。算法Lcs实现了上述优化策略，这种策略体现了动态规划的思想。算法Lcs的时间复杂性显然是O(nm)，这比其递归版有很大改进。JYP15intString::Lcs(Stringy){intn=Length(),m=y.Length();intlcs[MaxN][MaxM];//MaxN和MaxM是已定义的常数inti,j;for(i=0;i=n;i++)lcs[i][0]=0;//初始值for(j=0;j=m;j++)lcs[0][j]=0;//初始值for(i=1;i=n;i++)for(j=1;j=m;j++)if(str[i-1]==y.str[j-1])lcs[i][j]=lcs[i-1][j-1]+1;elselcs[i][j]=max(lcs[i-1][j],lcs[i][j-1]);returnlcs[n][m];}JYP16例如，x=abdebcbb，y=adacbcb，lcs(x,y)=adbcb，改进算法的计算如下所示：70122234556012223444501222334440112223333011222222201122222210111111110000000000012345678JYP17机场模拟（2.9）计算机模拟（simulation）：•用软件模仿另一个系统的行为。•将研究对象表示为数据结构，对象动作表示为对数据的操作，控制动作的规则转换为算法。•通过更改数据的值或改变算法设置，可以观察到计算机模拟的变化，从而使用户能够推导出关于实际系统行为的有用结论。•在计算机处理一个对象的动作期间，其它对象和动作需等待。•队列在计算机模拟中具有重要应用。JYP18简单机场模拟：•只有一个跑道。•在每个时间单元，可起飞或降落一架飞机，但不可同时起降。•飞机准备降落或起飞的时间是随机的，在任一时间单元，跑道可能处于空闲、降落或起飞状态，并且可能有一些飞机在等待降落或起飞。•飞机在地上等待的代价比在空中等待的小，只有在没有飞机等待降落的情况下才允许飞机起飞。•当出现队列满的情况时，则拒绝为新到达的飞机服务。JYP19需要两个队列landing和takeoff。飞机可描述为：structplane{intid;//编号inttm;//到达队列时间};飞机的动作为：enumaction{ARRIVE,DEPART};JYP20模拟运行:•时间单元:1—endtime，并产生关于机场行为的重要统计信息，如处理的飞机数量，平均等待时间，被拒绝服务飞机的数量等。•采用基于泊松分布的随机整数决定在每个时间单元有多少架新飞机需要降落或起飞。•假设在10个时间单元中到达的飞机数分别是：2，0，0，1，4，1，0，0，0，1，那么每个时间单元的平均到达数是0.9。JYP21•一个非负整数序列满足给定期望值v的泊松分布意味着，对于该序列的一段足够长的子序列，其中整数的平均值接近v。•在模拟中还需要建立新到达飞机的数据，处理被拒绝服务的飞机，起飞、降落飞机，处理机场空闲和总结模拟结果。下面是机场模拟类定义：JYP22classAirportSimulation{//机场模拟。一个时间单元=起飞或降落的时间public:AirportSimulation();//构造函数voidRunSimulation();//模拟运行private:Queueplanelanding(6);//等待降落飞机队列，假设用环//型队列，实际长度为5Queueplanetakeoff(6);//等待起飞飞机队列，同上doubleexpectarrive;//一个时间单元内期望到达降落飞机数doubleexpectdepart;//一个时间单元内期望到达起飞飞机数intcurtime;//当前时间intendtime;//模拟时间单元数intidletime;//跑道空闲时间单元数intlandwait;//降落飞机的总等待时间JYP23intnland;//降落的飞机数intnplanes;//处理的飞机数intnrefuse;//拒绝服务的飞机数intntakeoff;//起飞的飞机数voidRandomize();//设置随机数种子intPoissionRandom(double&expectvalue);//根据泊松分布和给定期望值生成随机非负整数plane*NewPlane(plane&p,actionkind);//建立新飞机的数据项voidRefuse(plane&p,actionkind);//拒绝服务voidLand(plane&p);//降落飞机voidFly(plane&p);//起飞飞机voidIdle();//处理空闲时间单元voidConclude();//总结模拟结果};JYP24构造函数初始化各变量，如下所示：AirportSimulation::AirportSimulation(){//构造函数Booleanok;cout“请输入模拟时间单元数：”;cinendtime;idletime=landwait=nland=nplanes=0;nrefuse=ntakeoff=takoffwait=0;//初值Randomize();//设置随机数种子do{cout“请输入一个时间单元内期望到达降落飞机数：”;cinexpectarrive;cout“请输入一个时间单元内期望到达起飞飞机数：”;cinexpectdepart;JYP25if(expectarrive0.0||expectdepart0.0){cout“这些数不能为负！请重新输入。”endl;ok=FALSE;}elseif(expectarrive+expectdepart1.0){cout“机场将饱和！请重新输入。”endl;ok=FALSE;}elseok=TRUE;}while(ok==FALSE);}JYP26RunSimulation()是模拟运行的主控程序：voidAirportSimu