1、高级数据结构高级数据结构 教材：教材：数据结构（数据结构（C+描述）描述）（金远平编著，清华大（金远平编著，清华大学出版社）学出版社）讲课教师：讲课教师：金远平，软件学院金远平，软件学院 1JYP代价分摊（代价分摊（1.5.4）将孤立地分析一次算法调用得出的结论应用于一将孤立地分析一次算法调用得出的结论应用于一个个ADT的相关操作序列会产生过于悲观的结果。的相关操作序列会产生过于悲观的结果。例例1.12 整数容器整数容器Bag。class Bag public:Bag(int MaxSize=DefaultSize);/假设DefaultSize已定义 int Add(const int x)
2、/将整数x加入容器中 int Delete(const int k);/从容器中删除并打印k 个整数private:int top;/指示已用空间 int*b;/用数组b存放整数 int n;/容量;2JYP各操作的实现如下：各操作的实现如下：Bag:Bag(int MaxSize=DefaultSize):n(MaxSize)b=new intn;top=-1;int Bag:Add(const int x)if(top=n-1)return 0;/返回0表示加入失败 else b+top=x;return 1;3JYPint Bag:Delete(const int k)if(top+1
3、 k)return 0;/容器内元素不足容器内元素不足k k个，删除失个，删除失败败 else for(int i=0;i k;i+)cout btop i “”;top=top-k;return 1;先分析操作成功的情况：先分析操作成功的情况：Add(x)的时间复杂性的时间复杂性是是O(1)；Delete(k)需要需要k个程序步，且个程序步，且k可能等于可能等于n，在最坏情况下其时间复杂性是在最坏情况下其时间复杂性是O(n)；一个调用；一个调用Add操作操作 m1次，次，Delete操作操作m2次的序列的总代价则为次的序列的总代价则为O(m1+m2n)。4JYP 前面是常规分析的结论。进一步
4、观察：如果一开前面是常规分析的结论。进一步观察：如果一开始容器为空，则删除的元素不可能多于加入的元素，始容器为空，则删除的元素不可能多于加入的元素，即即 m2 次次Delete操作的总代价不可能大于操作的总代价不可能大于m1 次次Add操作的总代价。因此，在最坏情况下，一个调用操作的总代价。因此，在最坏情况下，一个调用Add操作操作 m1次，次，Delete操作操作m2次的序列的总代价为次的序列的总代价为O(m1)。操作失败时，操作失败时，Add(x)和和Delete(k)的时间复杂性的时间复杂性都是都是O(1)。因此，在操作可能失败的情况下，一个。因此，在操作可能失败的情况下，一个调用调用A
5、dd操作操作 m1次，次，Delete操作操作m2次的序列的总代次的序列的总代价为价为O(m1+m2)。5JYP 常规分析并没有错，只是其推导出的总代价上常规分析并没有错，只是其推导出的总代价上界远大于实际可得的上界。其原因是这种分析法没界远大于实际可得的上界。其原因是这种分析法没有注意到连续的最坏情况删除是不可能的。有注意到连续的最坏情况删除是不可能的。为了取得更准确的结果，还应该度量为了取得更准确的结果，还应该度量ADT数据数据结构的状态。对于每一个可能的状态结构的状态。对于每一个可能的状态S，赋予一个实，赋予一个实数数(S)。(S)称为称为S的的势能势能，其选择应使得，其选择应使得(S)
6、越高，越高，对处于对处于S状态的数据结构成功进行高代价操作的可能状态的数据结构成功进行高代价操作的可能越大。越大。例如，将容器元素个数作为容器状态的势能就例如，将容器元素个数作为容器状态的势能就很合理，因为元素越多，对容器成功进行高代价操很合理，因为元素越多，对容器成功进行高代价操作的可能越大。作的可能越大。6JYP 考虑一个由考虑一个由m个对个对ADT操作的调用构成的序列，操作的调用构成的序列，并设并设ti是第是第i次调用的次调用的实际代价实际代价，定义第，定义第i次调用的次调用的分分摊代价摊代价ai为为ai=ti+(Si)(Si-1)Si-1是第是第i次调用开始前次调用开始前ADT数据结构
7、的状态，数据结构的状态，Si是第是第i次调用结束后次调用结束后ADT数据结构的状态。设数据结构的状态。设 的选的选择使得择使得(Sm)(S0)，则，则7JYP即，分摊代价的总和是实际代价总和的上界。即，分摊代价的总和是实际代价总和的上界。例例1.12将容器元素个数作为将容器元素个数作为(S)。若操作序列始。若操作序列始于空容器，则于空容器，则(Sm)(S0)总是成立。下表反映了总是成立。下表反映了容器容器(S)的典型变化情况。的典型变化情况。8JYP 对对于于Add操操作作，ti=1，(Si)(Si-1)=1，所所以以ai=2；对对于于Delete操操作作，ti=k，(Si)(Si-1)=k，
8、所以，所以ai=0。任任何何一一个个调调用用Add操操作作 m1次次，Delete操操作作m2次次的的序列的总代价为序列的总代价为O(m1 2+m2 0)=O(m1)。9JYP 可可见见，分分摊摊分分析析法法将将偶偶尔尔出出现现的的高高价价操操作作调调用用的的代价代价分摊分摊到邻近的其它调用上，故而得名。到邻近的其它调用上，故而得名。而而且且，当当用用分分摊摊分分析析法法得得到到的的一一个个操操作作调调用用序序列列的的代代价价总总和和比比用用常常规规分分析析法法得得到到的的代代价价总总和和小小时时，人人们们就就得得到到了了更更接接近近实实际际代代价价的的分分析析结结果果，或或者者说说对算法时间
9、复杂性的判断对算法时间复杂性的判断更准确更准确了。了。10JYP两个字符串的最长公共子序列（两个字符串的最长公共子序列（2.4.3）一个字符串的子序列通过从字符串中删除零或多一个字符串的子序列通过从字符串中删除零或多个任意位置的字符得到。个任意位置的字符得到。两个字符串两个字符串x和和y的的最长公共子序列最长公共子序列记为记为lcs(x,y)。例如，例如，x=abdebcbb，y=adacbcb，则，则lcs(x,y)是是adcbb和和adbcb，如下所示：，如下所示：11JYP问题的基本求解方法问题的基本求解方法：用用 标记空串，则标记空串，则lcs(x,)=lcs(,y)=。lcs(xa,
10、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)中较长者。中较长者。12JYP 由此可得计算两个字符串最长公共子序列长度的由此可得计算两个字符串最长公共子序列长度的递归算法递归算法lcs:in
11、t String:lcs(String y)/驱动器 int n=Length(),m=y.Length();return lcs(n,m,y.str);int String:lcs(int i,int j,char*y)/递归核心 if(i=0|j=0)return 0;if(stri-1=yj-1)return(lcs(i-1,j-1,y)+1);return max(lcs(i-1,j,y),lcs(i,j-1,y);13JYP 设设x的长度为的长度为n，y的长度为的长度为m，在最坏情况下，在最坏情况下lcs的时间复杂性为的时间复杂性为w(n,m)。w(n,m)=因此，因此，w(n,m)
12、2 w(n-1,m-1)2min(n,m)c，即，即lcs的时间复杂性是指数型的。的时间复杂性是指数型的。进一步可发现，进一步可发现，lcs(i,0)=0（0in），），lcs(0,j)=0（0jm）。）。lcs(i,j)的计算依赖于的计算依赖于lcs(i1,j1)、lcs(i1,j)和和lcs(i,j1)，如下图所示：，如下图所示：c（c为常数）为常数）n=0或或m=0w(n,m-1)+w(n-1,m)否则否则14JYP 根据以上拓扑关系，可以在不用递归的情况下计根据以上拓扑关系，可以在不用递归的情况下计算算lcs(i,j)。算法。算法Lcs实现了上述优化策略，这种策略实现了上述优化策略，这
13、种策略体现了动态规划的思想。算法体现了动态规划的思想。算法Lcs的时间复杂性显然的时间复杂性显然是是O(n m)，这比其递归版有很大改进。，这比其递归版有很大改进。15JYPint String:Lcs(String y)int n=Length(),m=y.Length();int lcsMaxNMaxM;/MaxN和MaxM 是已定义的常数 int i,j;for(i=0;i=n;i+)lcsi0=0;/初始值 for(j=0;j=m;j+)lcs0j=0;/初始值 for(i=1;i=n;i+)for(j=1;j=m;j+)if(stri-1=y.strj-1)lcsij=lcsi-1j
14、1+1;else lcsij=max(lcsi-1j,lcsij-1);return lcsnm;16JYP 例如，例如，x=abdebcbb，y=adacbcb，lcs(x,y)=adbcb，改，改进算法的计算如下所示：进算法的计算如下所示：7012223455601222344450122233444011222333301122222220112222221011111111000000000001234567817JYP机场模拟（机场模拟（2.9）计算机模拟（计算机模拟（simulation）：）：用软件模仿另一个系统的行为。用软件模仿另一个系统的行为。将研究对象表示为数据结构，对象
15、动作表示为对将研究对象表示为数据结构，对象动作表示为对数据的操作，控制动作的规则转换为算法。数据的操作，控制动作的规则转换为算法。通过更改数据的值或改变算法设置，可以观察到通过更改数据的值或改变算法设置，可以观察到计算机模拟的变化，从而使用户能够推导出关于计算机模拟的变化，从而使用户能够推导出关于实际系统行为的有用结论。实际系统行为的有用结论。在计算机处理一个对象的动作期间，其它对象和在计算机处理一个对象的动作期间，其它对象和动作需等待。动作需等待。队列在计算机模拟中具有重要应用。队列在计算机模拟中具有重要应用。18JYP简单机场模拟：简单机场模拟：只有一个跑道。只有一个跑道。在每个时间单元，
16、可起飞或降落一架飞机，但不在每个时间单元，可起飞或降落一架飞机，但不可同时起降。可同时起降。飞机准备降落或起飞的时间是随机的，在任一时飞机准备降落或起飞的时间是随机的，在任一时间单元，跑道可能处于空闲、降落或起飞状态，间单元，跑道可能处于空闲、降落或起飞状态，并且可能有一些飞机在等待降落或起飞。并且可能有一些飞机在等待降落或起飞。飞机在地上等待的代价比在空中等待的小，只有飞机在地上等待的代价比在空中等待的小，只有在没有飞机等待降落的情况下才允许飞机起飞。在没有飞机等待降落的情况下才允许飞机起飞。当出现队列满的情况时，则拒绝为新到达的飞机当出现队列满的情况时，则拒绝为新到达的飞机服务。服务。19
17、JYP需要两个队列需要两个队列landing和和takeoff。飞机可描述为：飞机可描述为：struct plane int id;/编号 int tm;/到达队列时间;飞机的动作为：飞机的动作为：enum action ARRIVE,DEPART;20JYP模拟运行模拟运行:时间单元时间单元:1 endtime，并产生关于机场行为的，并产生关于机场行为的重要统计信息，如处理的飞机数量，平均等待时重要统计信息，如处理的飞机数量，平均等待时间，被拒绝服务飞机的数量等。间，被拒绝服务飞机的数量等。采用基于泊松分布的随机整数决定在每个时间单采用基于泊松分布的随机整数决定在每个时间单元有多少架新飞机需
18、要降落或起飞。元有多少架新飞机需要降落或起飞。假设在假设在10个时间单元中到达的飞机数分别是：个时间单元中到达的飞机数分别是：2，0，0，1，4，1，0，0，0，1，那么每个时间单元，那么每个时间单元的平均到达数是的平均到达数是0.9。21JYP 一个非负整数序列满足给定期望值一个非负整数序列满足给定期望值v v的泊松分布的泊松分布意味着，对于该序列的一段足够长的子序列，其意味着，对于该序列的一段足够长的子序列，其中整数的平均值接近中整数的平均值接近v v。在模拟中还需要建立新到达飞机的数据，处理被在模拟中还需要建立新到达飞机的数据，处理被拒绝服务的飞机，起飞、降落飞机，处理机场空拒绝服务的飞
19、机，起飞、降落飞机，处理机场空闲和总结模拟结果。闲和总结模拟结果。下面是机场模拟类定义：下面是机场模拟类定义：22JYPclass AirportSimulation/机场模拟。一个时间单元=起飞或降落的时间public:AirportSimulation();/构造函数 void RunSimulation();/模拟运行private:Queue landing(6);/等待降落飞机队列，假设用环/型队列，实际长度为5 Queue takeoff(6);/等待起飞飞机队列，同上 double expectarrive;/一个时间单元内期望到达降落飞机数 double expectdepar
20、t;/一个时间单元内期望到达起飞飞机数 int curtime;/当前时间 int endtime;/模拟时间单元数 int idletime;/跑道空闲时间单元数 int landwait;/降落飞机的总等待时间23JYP int nland;/降落的飞机数 int nplanes;/处理的飞机数 int nrefuse;/拒绝服务的飞机数 int ntakeoff;/起飞的飞机数 void Randomize();/设置随机数种子 int PoissionRandom(double&expectvalue);/根据泊松分布和给定期望值生成随机非负整数 plane*NewPlane(plan
21、e&p,action kind);/建立新飞机的数据项 void Refuse(plane&p,action kind);/拒绝服务 void Land(plane&p);/降落飞机 void Fly(plane&p);/起飞飞机 void Idle();/处理空闲时间单元 void Conclude();/总结模拟结果;24JYP 构造函数初始化各变量，如下所示：构造函数初始化各变量，如下所示：AirportSimulation:AirportSimulation()/构造函数 Boolean ok;cout endtime;idletime=landwait=nland=nplanes=0
22、nrefuse=ntakeoff=takoffwait=0;/初值 Randomize();/设置随机数种子 do cout expectarrive;cout expectdepart;25JYP if(expectarrive 0.0|expectdepart 0.0)cout “这些数不能为负！请重新输入。”1.0)cout “机场将饱和！请重新输入。”endl;ok=FALSE;else ok=TRUE;while(ok=FALSE);26JYP RunSimulation()是模拟运行的主控程序：是模拟运行的主控程序：void AirportSimulation:RunSimula
23、tion()int pri;/伪随机整数 plane p;for(curtime=1;curtime=endtime;curtime+)cout “时间单元”curtime “：”;pri=PoissionRandom(expectarrive);for(int i=1;i=pri;i+)/处理新到达准备降落的飞机 p=*NewPlane(p,ARRIVE);if(landing.IsFull()Refuse(p,ARRIVE);else landing.Add(p);pri=PoissionRandom(expectdepart);27JYP for(int i=1;i limit)n+;x
24、rand()/(double)INT_MAX;return n;30JYP 建立新飞机的数据项由函数建立新飞机的数据项由函数NewPlane实现：实现：plane*AirportSimulation:NewPlane(plane&p,action kind)nplanes+;/飞机总数加1 p.id=nplanes;p.tm=curtime;switch(kind)case ARRIVE:cout “飞机”nplanes “准备降落。”endl;break;case DEPART:cout “飞机”nplanes “准备起飞。”endl;break;return&p;31JYP 处理被拒绝
25、的飞机由函数处理被拒绝的飞机由函数Refuse实现实现:void AirportSimulation:Refuse(plane&p,action kind)switch(kind)case ARRIVE:cout “引导飞机”p.id “到其它机场降落。”endl;break;case DEPART:cout “告诉飞机”p.id “等一会儿再试。”endl;break;nrefuse+;/被拒绝飞机总数加132JYP 处理飞机降落由函数处理飞机降落由函数Land实现：实现：void AirportSimulation:Land(plane&p)int wait;wait=curtime p.
26、tm;cout “飞机”p.id “降落，该机等待时间：”wait “。”endl;nland+;/降落飞机总数加1 landwait+=wait;/累加总降落等待时间33JYP 处理飞机起飞由函数处理飞机起飞由函数Fly实现：实现：void AirportSimulation:Fly(plane&p)int wait=curtime p.tm;cout “飞机”p.id “起飞，该机等待时间：”wait “。”endl;ntakeoff+;/起飞飞机总数加1 takeoffwait+=wait;/累加总起飞等待时间34JYP 处理机场空闲由函数处理机场空闲由函数Idle实现：实现：void
27、AirportSimulation:Idle()cout “跑道空闲。”endl;idletime+;/跑道空闲时间加1 总结模拟结果由函数总结模拟结果由函数Conclude实现：实现：void AirportSimulation:Conclude()cout “总模拟时间单元数：”endtime endl;cout “总共处理的飞机数：”nplanes endl;cout “降落飞机总数：”nland endl;cout “起飞飞机总数：”ntakeoff endl;35JYP cout “拒绝服务的飞机总数：”nrefuse endl;cout “队列中剩余的准备降落飞机数：”landin
28、g.Size()endl;/假设队列成员函数Size()返回队列中元素个数 cout “队列中剩余的准备起飞飞机数：”takeoff.Size()0)cout “跑道空闲时间百分比：”(double)idletime/endtime)*100.0 0)cout “降落平均等待时间：”(double)landwait/nland 0)cout “起飞平均等待时间：”(double)takeoffwait/ntakeoff endl;36JYP可通过下列程序模拟运行：可通过下列程序模拟运行：#include“common.h”#include“simdefs.h”/存放模拟类定义及相关函数实现vo
29、id main()AirportSimulation s;s.RunSimulation();37JYP模拟过程产生的数据如下：模拟过程产生的数据如下：请输入模拟时间单元数：请输入模拟时间单元数：30请输入一个时间单元内期望到达降落飞机数：请输入一个时间单元内期望到达降落飞机数：0.47请输入一个时间单元内期望到达起飞飞机数：请输入一个时间单元内期望到达起飞飞机数：0.47时间单元时间单元1：飞机：飞机1准备降落。准备降落。飞机飞机1降落，该机等待时间：降落，该机等待时间：0。时间单元时间单元2：跑道空闲。：跑道空闲。时间单元时间单元3：飞机：飞机2准备降落。准备降落。飞机飞机3准备降落。准备
30、降落。飞机飞机2降落，该机等待时间：降落，该机等待时间：0。时间单元时间单元4：飞机飞机3降落，该机等待时间：降落，该机等待时间：1。38JYP时间单元时间单元5：飞机：飞机4准备降落。准备降落。飞机飞机5准备降落。准备降落。飞机飞机6准备起飞。准备起飞。飞机飞机7准备起飞。准备起飞。飞机飞机4降落，该机等待时间：降落，该机等待时间：0。时间单元时间单元6：飞机：飞机8准备起飞。准备起飞。飞机飞机5降落，该机等待时间：降落，该机等待时间：1。时间单元时间单元7：飞机：飞机9准备起飞。准备起飞。飞机飞机10准备起飞。准备起飞。飞机飞机6起飞，该机等待时间：起飞，该机等待时间：2。时间单元时间单元
31、8：飞机飞机7起飞，该机等待时间：起飞，该机等待时间：3。时间单元时间单元9：飞机飞机8起飞，该机等待时间：起飞，该机等待时间：3。39JYP时间单元时间单元10：飞机：飞机11准备降落。准备降落。飞机飞机11降落，该机等待时间：降落，该机等待时间：0。时间单元时间单元11：飞机：飞机12准备起飞。准备起飞。飞机飞机9起飞，该机等待时间：起飞，该机等待时间：4。时间单元时间单元12：飞机：飞机13准备降落。准备降落。飞机飞机14准备降落。准备降落。飞机飞机13降落，该机等待时间：降落，该机等待时间：0。时间单元时间单元13：飞机飞机14降落，该机等待时间：降落，该机等待时间：1。时间单元时间单
32、元14：飞机飞机10起飞，该机等待时间：起飞，该机等待时间：7。时间单元时间单元15：飞机飞机15准备降落。准备降落。飞机飞机16准备起飞。准备起飞。飞机飞机17准备起飞。准备起飞。飞机飞机15降落，该机等待时间：降落，该机等待时间：0。40JYP时间单元时间单元16：飞机：飞机18准备降落。准备降落。飞机飞机19准备降落。准备降落。飞机飞机20准备起飞。准备起飞。飞机飞机21准备起飞。准备起飞。飞机飞机18降落，该机等待时间：降落，该机等待时间：0。时间单元时间单元17：飞机飞机22准备降落。准备降落。飞机飞机19降落，该机等待时间：降落，该机等待时间：1。时间单元时间单元18：飞机飞机23
33、准备起飞。准备起飞。告诉飞机告诉飞机23等一会儿再试。等一会儿再试。飞机飞机22降落，该机等待时间：降落，该机等待时间：1。41JYP时间单元时间单元19：飞机飞机24准备降落。准备降落。飞机飞机25准备降落。准备降落。飞机飞机26准备降落。准备降落。飞机飞机27准备起飞。准备起飞。告诉飞机告诉飞机27等一会儿再试。等一会儿再试。飞机飞机24降落，该机等待时间：降落，该机等待时间：0。时间单元时间单元20：飞机飞机28准备降落。准备降落。飞机飞机29准备降落。准备降落。飞机飞机30准备降落。准备降落。飞机飞机31准备降落。准备降落。引导飞机引导飞机31到其它机场降落。到其它机场降落。飞机飞机2
34、5降落，该机等待时间：降落，该机等待时间：1。42JYP时间单元时间单元21：飞机：飞机32准备降落。准备降落。飞机飞机33准备起飞。准备起飞。告诉飞机告诉飞机33等一会儿再试。等一会儿再试。飞机飞机26降落，该机等待时间：降落，该机等待时间：2。时间单元时间单元22：飞机：飞机28降落，该机等待时间：降落，该机等待时间：2。时间单元时间单元23：飞机：飞机29降落，该机等待时间：降落，该机等待时间：3。时间单元时间单元24：飞机：飞机34准备起飞。准备起飞。告诉飞机告诉飞机34等一会儿再试。等一会儿再试。飞机飞机30降落，该机等待时间：降落，该机等待时间：4。43JYP时间单元时间单元25：
35、飞机：飞机35准备起飞。准备起飞。告诉飞机告诉飞机35等一会儿再试。等一会儿再试。飞机飞机36准备起飞。准备起飞。告诉飞机告诉飞机36等一会儿再试。等一会儿再试。飞机飞机32降落，该机等待时间：降落，该机等待时间：4。时间单元时间单元26：飞机：飞机37准备起飞。准备起飞。告诉飞机告诉飞机37等一会儿再试。等一会儿再试。飞机飞机12起飞，该机等待时间：起飞，该机等待时间：15。时间单元时间单元27：飞机：飞机16起飞，该机等待时间：起飞，该机等待时间：12。时间单元时间单元28：飞机：飞机17起飞，该机等待时间：起飞，该机等待时间：13。时间单元时间单元29：飞机：飞机20起飞，该机等待时间：
36、起飞，该机等待时间：13。44JYP时间单元时间单元30：飞机：飞机38准备起飞。准备起飞。飞机飞机21起飞，该机等待时间：起飞，该机等待时间：14。总模拟时间单元数：总模拟时间单元数：30总共处理的飞机数：总共处理的飞机数：38降落飞机总数：降落飞机总数：19起飞飞机总数：起飞飞机总数：10拒绝服务的飞机总数：拒绝服务的飞机总数：8队列中剩余的准备降落飞机数：队列中剩余的准备降落飞机数：0 队列中剩余的准备起飞飞机数：队列中剩余的准备起飞飞机数：1跑道空闲时间百分比：跑道空闲时间百分比：3.33降落平均等待时间：降落平均等待时间：1.11起飞平均等待时间：起飞平均等待时间：8.6045JYP
37、二叉树计数二叉树计数(4.9)当当n=0或或1时，只有一棵二叉树。时，只有一棵二叉树。当当n=2，存在，存在2棵不同（结构）的二叉树：棵不同（结构）的二叉树：46JYP 而当而当n=3，则存在，则存在5棵不同的二叉树：棵不同的二叉树：那么，具有那么，具有n个结点的不同二叉树究竟有多少呢？个结点的不同二叉树究竟有多少呢？47JYP 不不失失一一般般性性，将将树树的的n个个结结点点编编号号为为1到到n。假假设设一一棵棵二二叉叉树树的的前前序序序序列列为为1 2 3 4 5 6 7 8 9且且其其中中序序序序列列为为2 3 1 5 4 7 8 6 9，则则通通过过这这对对序序列列可可以以唯唯一一确确
38、定定一棵二叉树。一棵二叉树。为为了了构构造造相相应应的的二二叉叉树树，可可找找出出前前序序第第一一个个结结点点，即即1。于于是是，结结点点1是是树树根根，中中序序序序列列中中所所有有在在1之之前前的的结结点点（2 3）属属于于左左子子树树，其其余余结结点点（5 4 7 8 6 9）属于右子树。属于右子树。48JYP 这一步构造如下所示：这一步构造如下所示：49JYP 接接着着，可可根根据据前前序序序序列列2 3和和中中序序序序列列2 3构构造造左左子子树树。显显然然，结结点点2是是树树根根。由由于于在在中中序序序序列列中中，结结点点2之之前前无无结结点点，所所以以其其左左子子树树为为空空，结结
39、点点3是是其其右右子子树，如下图所示：树，如下图所示：50JYP 如此继续，最终可唯一地构造下图所示的二叉树：如此继续，最终可唯一地构造下图所示的二叉树：51JYP 一一般般地地，我我们们可可以以设设计计算算法法，根根据据二二叉叉树树的的前前序序/中序序列对构造该树。中序序列对构造该树。可可以以证证明明，每每一一棵棵二二叉叉树树都都有有唯唯一一的的前前序序/中中序序序序列对。列对。如如果果树树中中结结点点按按前前序序编编号号，即即树树的的前前序序序序列列为为1,2,n，则则由由上上讨讨论论可可知知，不不同同的的二二叉叉树树定定义义不不同同的中序序列。的中序序列。因因此此，不不同同的的二二叉叉树
40、树个个数数等等于于从从前前序序序序列列为为1,2,n的二叉树可产生的不同的中序序列的个数。的二叉树可产生的不同的中序序列的个数。52JYP 设设bn是是具具有有n个个结结点点的的不不同同二二叉叉树树的的个个数数。bn实实际际上上是是按按以以下下方方式式形形成成的的各各种种可可能能的的二二叉叉树树个个数数之之和和：一一个个根根和和两两个个结结点点数数分分别别为为i和和ni1的的子子树树(0i n)，如下所示：，如下所示：53JYP 对于每一个对于每一个i，存在，存在bi bn-i-1棵不同的树，因此有棵不同的树，因此有(4.3)为了用为了用n表示表示bn，必须求解递归方程，必须求解递归方程(4.
41、3)。设。设(4.4)54JYP B(x)是二叉树个数的生成函数。由于是二叉树个数的生成函数。由于 55JYP即即 x B2(x)B(x)+1=056JYP 解解此此一一元元二二次次方方程程，并并注注意意B(0)=b0=1（等等式式(4.3)），可得），可得 利用二项式公式展开利用二项式公式展开(1 4x)1/2得到得到57JYP 令令n=m+1，可得，可得(4.5)58JYP 比比较较等等式式(4.4)和和(4.5)，并并注注意意bn是是B(x)中中xn的的系数，可得系数，可得59JYP60JYP最小最大堆最小最大堆(5.2)5.2.1 双端优先队列与最小最大堆双端优先队列与最小最大堆 双端
42、优先队列双端优先队列是一种支持下列操作的数据结构：是一种支持下列操作的数据结构：（1）插入一个具有任意插入一个具有任意key值的元素值的元素（2）删除删除key值最大的元素值最大的元素（3）删除删除key值最小的元素值最小的元素 当只需要支持两个删除操作之一时，可采用前一当只需要支持两个删除操作之一时，可采用前一节的最小堆或最大堆。而节的最小堆或最大堆。而最小最大堆最小最大堆可支持以上全可支持以上全部操作。部操作。61JYP 双端优先队列可定义为如下的抽象类：双端优先队列可定义为如下的抽象类：template class DEPQ public:virtual void Insert(cons
43、t Element&)=0;virtual Element*DeleteMax(Element&)=0;virtual Element*DeleteMin(Element&)=0;其中，假设其中，假设Element含有一个含有一个key数据成员。数据成员。62JYP 定义：最小最大堆定义：最小最大堆是一棵完全二叉树，且其中每是一棵完全二叉树，且其中每个元素有一个个元素有一个key数据成员。树的各层交替为最小层数据成员。树的各层交替为最小层和最大层。根结点在最小层。设和最大层。根结点在最小层。设x是最小最大堆的任是最小最大堆的任意结点。若意结点。若x在最小（最大）层上，则在最小（最大）层上，则x
44、中的元素的中的元素的key值在以值在以x为根的子树的所有元素中是最小（最大）为根的子树的所有元素中是最小（最大）的。位于最小（最大）层的结点称为的。位于最小（最大）层的结点称为最小（最大）最小（最大）结点结点。63JYP 下面是一个具有下面是一个具有12个元素的最小最大堆，其中最个元素的最小最大堆，其中最大层的结点用粗体字表示：大层的结点用粗体字表示：64JYP 最小最大堆定义为最小最大堆定义为DEPQ的派生类，以确保实现的派生类，以确保实现DEPQ的三个操作。的三个操作。template class MinMaxHeap:public DEPQ public:MinMaxHeap(const
45、 int);/构造函数 MinMaxHeap();/析构函数 void Insert(const Element&);Element*DeleteMax(Element&x);Element*DeleteMin(Element&x);private:Element*h;int n;/最小最大堆的当前元素个数 int MaxSize;/堆中可容纳元素的最大个数65JYP /其它用于实现最小最大堆的私有数据成员 ;template/构造函数定义MinMaxHeap:MinMaxHeap(const int sz=DefaultHeapSize):MaxSize(sz),n(0)h=new Elem
46、entMaxSize+1;/h0 不用66JYP5.2.2 插入操作插入操作 假假设设将将key为为5的的元元素素插插入入图图5.4的的最最小小最最大大堆堆。插插入后的堆有入后的堆有13个元素，其形状如下图：个元素，其形状如下图：67JYP 最小最大堆的插入算法也需要沿从新结点最小最大堆的插入算法也需要沿从新结点j到根到根的路径比较的路径比较key值。值。比较结点比较结点j的的key值值5和和j的双亲的的双亲的key值值10，由于存，由于存放放key值值10的结点位于最小层，且的结点位于最小层，且5 10，所以，所以5一定一定小于所有从小于所有从j到根的路径中位于最大层的结点的到根的路径中位于
47、最大层的结点的key值。值。为了保持最小最大堆的性质，只需要检查从为了保持最小最大堆的性质，只需要检查从j到到根的路径中的最小结点即可。首先，将根的路径中的最小结点即可。首先，将key为为10的元的元素移到结点素移到结点j。接着，将。接着，将key为为7的元素移到的元素移到10的原来的原来位置。最后，将位置。最后，将key为为5的元素插入根结点。的元素插入根结点。68JYP 由此形成的最小最大堆如下图，圆周加粗的结点由此形成的最小最大堆如下图，圆周加粗的结点内容在插入过程修改过：内容在插入过程修改过：69JYP 再假设将再假设将key为为80的元素插入图的元素插入图5.4所示的最小最所示的最小
48、最大堆。插入后的堆有大堆。插入后的堆有13个元素，其形状也与前面相个元素，其形状也与前面相同。同。由于存放由于存放key值值10的结点位于最小层，且的结点位于最小层，且10 80，所以，所以80一定大于所有从一定大于所有从j到根的路径中位于最小层到根的路径中位于最小层的结点的的结点的key值。值。为了保持最小最大堆的性质，只需要检查从为了保持最小最大堆的性质，只需要检查从j到到根的路径中的最大结点即可。图根的路径中的最大结点即可。图5.4中只有一个这样中只有一个这样的结点，其元素的的结点，其元素的key值为值为40，将该元素移到结点，将该元素移到结点j，并将，并将key为为80的新元素插入的新
49、元素插入key为为40的元素原来的的元素原来的结点。结点。70JYP 由此形成的最小最大堆如下图：由此形成的最小最大堆如下图：71JYP 成员函数成员函数Insert实现了上述过程，其中又用到私实现了上述过程，其中又用到私有成员函数有成员函数VerifyMax，VerifyMin 和和level。template void MinMaxHeap:Insert(const Element&x)if(n=MaxSize)MinMaxFull();return;n+;int p=n/2;/p是新结点的双亲 if(!p)h1=x;return;/插入初始时为空的堆 switch(level(p)cas
50、e MIN:if(x.key hp.key)/沿着最大层检查 hn=hp;VerifyMax(p,x);else VerifyMin(n,x);/沿着最小层检查 /switch结束/Insert结束 73JYP 函数函数level确定一个结点是位于最小最大堆的最小确定一个结点是位于最小最大堆的最小层，还是位于最大层。根据引理层，还是位于最大层。根据引理4.2，当，当 log2(j+1)为偶数时，结点为偶数时，结点j位于最大层，否则位于最小层。位于最大层，否则位于最小层。函数函数VerifyMax从最大结点从最大结点i开始，沿着从结点开始，沿着从结点i到到最小最大堆的根的路径检查最大结点，查找插
免费区 
