高级数据结构.ppt

1、高级数据结构,教材：数据结构（C+描述）（金远平编著，清华大学出版社）,JYP,1,代价分摊（1.5.4）,将孤立地分析一次算法调用得出的结论应用于一个ADT的相关操作序列会产生过于悲观的结果。例1.12 整数容器Bag。class Bag public: Bag ( int MaxSize = DefaultSize ); / 假设DefaultSize已定义 int Add (const int x ); / 将整数x加入容器中 int Delete (const int k ); / 从容器中删除并打印k 个整数private: int top; / 指示已用空间 int *b; / 用

2、数组b存放整数 int n; / 容量;,JYP,2,各操作的实现如下：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; ,JYP,3,int Bag:Delete (const int k) if (top + 1 k ) return 0; /容器内元素不足k个，删除失败 else for (int i = 0; i

3、 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)。,JYP,4,前面是常规分析的结论。进一步观察：如果一开始容器为空，则删除的元素不可能多于加入的元素，即 m2 次Delete操作的总代价不可能大于m1 次Add操作的总代价。因此，在最坏情况下，一个调用Add操作 m1次，Delete操作m2次的序列的总代价为O

4、(m1)。 操作失败时，Add(x)和Delete(k) 的时间复杂性都是O(1)。因此，在操作可能失败的情况下，一个调用Add操作 m1次，Delete操作m2次的序列的总代价为O(m1+ m2)。,JYP,5,常规分析并没有错，只是其推导出的总代价上界远大于实际可得的上界。其原因是这种分析法没有注意到连续的最坏情况删除是不可能的。 为了取得更准确的结果，还应该度量ADT数据结构的状态。对于每一个可能的状态S，赋予一个实数(S)。(S)称为S的势能，其选择应使得(S)越高，对处于S状态的数据结构成功进行高代价操作的可能越大。 例如，将容器元素个数作为容器状态的势能就很合理，因为元素越多，对容

5、器成功进行高代价操作的可能越大。,JYP,6,考虑一个由m个对ADT操作的调用构成的序列，并设ti是第i次调用的实际代价，定义第i次调用的分摊代价ai为ai = ti + (Si) (Si-1) Si-1是第i次调用开始前ADT数据结构的状态，Si是第i次调用结束后ADT数据结构的状态。设的选择使得(Sm) (S0)，则,JYP,7,即，分摊代价的总和是实际代价总和的上界。 例1.12将容器元素个数作为(S)。若操作序列始于空容器，则(Sm) (S0)总是成立。下表反映了容器(S)的典型变化情况。,JYP,8,对于Add操作，ti=1，(Si)(Si-1)=1，所以ai=2；对于Delete操

6、作，ti=k，(Si)(Si-1)= k，所以ai=0。 任何一个调用Add操作 m1次，Delete操作m2次的序列的总代价为O(m12 + m20) = O(m1)。,JYP,9,可见，分摊分析法将偶尔出现的高价操作调用的代价分摊到邻近的其它调用上，故而得名。 而且，当用分摊分析法得到的一个操作调用序列的代价总和比用常规分析法得到的代价总和小时，人们就得到了更接近实际代价的分析结果，或者说对算法时间复杂性的判断更准确了。,JYP,10,两个字符串的最长公共子序列（2.4.3）,一个字符串的子序列通过从字符串中删除零或多个任意位置的字符得到。两个字符串x和y的最长公共子序列记为lcs(x,

7、y)。例如，x = abdebcbb，y = adacbcb，则lcs(x, y)是adcbb和adbcb，如下所示：,JYP,11,问题的基本求解方法： 用标记空串，则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)中较长者。,JYP,12

8、,由此可得计算两个字符串最长公共子序列长度的递归算法lcs: int 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

9、, y);,JYP,13,设x的长度为n，y的长度为m，在最坏情况下lcs的时间复杂性为w(n, m)。w(n, m) =,因此，w(n, m)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)否则,JYP,14,根据以上拓扑关系，可以在不用递归的情况下计算lcs(i, j)。算法Lcs实

10、现了上述优化策略，这种策略体现了动态规划的思想。算法Lcs的时间复杂性显然是O(nm)，这比其递归版有很大改进。,JYP,15,int 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 endti

11、me; idletime = landwait = nland = nplanes = 0; nrefuse = ntakeoff = takoffwait = 0; / 初值 Randomize( ); / 设置随机数种子 do cout expectarrive; cout expectdepart;,JYP,25,if (expectarrive 1.0) cout “机场将饱和！请重新输入。” endl; ok = FALSE; else ok = TRUE; while (ok = FALSE);,JYP,26,RunSimulation( )是模拟运行的主控程序：void Airp

12、ortSimulation:RunSimulation( ) 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

13、= PoissionRandom(expectdepart);,JYP,27,for (int i =1; i = pri; i+) /处理新到达准备起飞的飞机 p = *NewPlane(p, DEPART); if (takeoff.IsFull( ) Refuse(p, DEPART); else takeoff.Add(p); if (!landing.IsEmpty( ) / 降落飞机 p = *landing.Delete(p); Land(p); else if (!takeoff.IsEmpty( ) / 起飞飞机 p = *takeoff.Delete(p); Fly(p);

14、 else Idle( );/ 处理空闲时间单元 Conclude( );/ 总结模拟结果,JYP,28,用库函数srand和rand生成随机数，并用时钟设置随机种子，以增强随机性：void AirportSimulation:Randomize( ) srand(unsigned int) (time(NULL)%10000); 库函数time返回自格林威治时间1970年1月1日00:00:00 至今经历的秒数。这使得每次模拟运行随机数起点都不同。 rand按照均匀分布生成随机数，还需要转化为适合机场模拟的泊松分布随机数。下面直接给出根据泊松分布和给定期望值生成伪随机整数的算法（其数学推导略

15、） ：,JYP,29,int AirportSimulation:PoissionRandom(double,JYP,30,建立新飞机的数据项由函数NewPlane实现：plane* AirportSimulation:NewPlane(plane,JYP,31,处理被拒绝的飞机由函数Refuse实现:void AirportSimulation:Refuse(plane/ 被拒绝飞机总数加1,JYP,32,处理飞机降落由函数Land实现：void AirportSimulation:Land(plane/ 累加总降落等待时间,JYP,33,处理飞机起飞由函数Fly实现：void Airpor

16、tSimulation:Fly(plane/ 累加总起飞等待时间,JYP,34,处理机场空闲由函数Idle实现：void AirportSimulation:Idle( ) cout “跑道空闲。” endl; idletime+;/ 跑道空闲时间加1 总结模拟结果由函数Conclude实现：void AirportSimulation:Conclude( ) cout “总模拟时间单元数：” endtime endl; cout “总共处理的飞机数：” nplanes endl; cout “降落飞机总数：” nland endl; cout “起飞飞机总数：” ntakeoff endl;

17、,JYP,35,cout 0) cout 0) cout 0) cout “起飞平均等待时间：” (double) takeoffwait / ntakeoff endl;,JYP,36,可通过下列程序模拟运行：#include “common.h”#include “simdefs.h”/ 存放模拟类定义及相关函数实现void main( ) AirportSimulation s; s.RunSimulation( );,JYP,37,模拟过程产生的数据如下：请输入模拟时间单元数：30请输入一个时间单元内期望到达降落飞机数：0.47请输入一个时间单元内期望到达起飞飞机数：0.47时间单元1

18、：飞机1准备降落。 飞机1降落，该机等待时间：0。时间单元2：跑道空闲。时间单元3：飞机2准备降落。 飞机3准备降落。 飞机2降落，该机等待时间：0。时间单元4： 飞机3降落，该机等待时间：1。,JYP,38,时间单元5：飞机4准备降落。 飞机5准备降落。 飞机6准备起飞。 飞机7准备起飞。 飞机4降落，该机等待时间：0。时间单元6：飞机8准备起飞。 飞机5降落，该机等待时间：1。时间单元7：飞机9准备起飞。 飞机10准备起飞。 飞机6起飞，该机等待时间：2。时间单元8： 飞机7起飞，该机等待时间：3。时间单元9： 飞机8起飞，该机等待时间：3。,JYP,39,时间单元10：飞机11准备降落。

19、 飞机11降落，该机等待时间：0。时间单元11：飞机12准备起飞。 飞机9起飞，该机等待时间：4。时间单元12：飞机13准备降落。 飞机14准备降落。 飞机13降落，该机等待时间：0。时间单元13： 飞机14降落，该机等待时间：1。时间单元14： 飞机10起飞，该机等待时间：7。时间单元15： 飞机15准备降落。 飞机16准备起飞。 飞机17准备起飞。 飞机15降落，该机等待时间：0。,JYP,40,时间单元16：飞机18准备降落。 飞机19准备降落。 飞机20准备起飞。 飞机21准备起飞。 飞机18降落，该机等待时间：0。时间单元17： 飞机22准备降落。 飞机19降落，该机等待时间：1。时

20、间单元18： 飞机23准备起飞。 告诉飞机23等一会儿再试。 飞机22降落，该机等待时间：1。,JYP,41,时间单元19： 飞机24准备降落。 飞机25准备降落。 飞机26准备降落。 飞机27准备起飞。 告诉飞机27等一会儿再试。 飞机24降落，该机等待时间：0。时间单元20： 飞机28准备降落。 飞机29准备降落。 飞机30准备降落。 飞机31准备降落。 引导飞机31到其它机场降落。 飞机25降落，该机等待时间：1。,JYP,42,时间单元21：飞机32准备降落。 飞机33准备起飞。 告诉飞机33等一会儿再试。 飞机26降落，该机等待时间：2。时间单元22：飞机28降落，该机等待时间：2。

21、时间单元23：飞机29降落，该机等待时间：3。时间单元24：飞机34准备起飞。 告诉飞机34等一会儿再试。 飞机30降落，该机等待时间：4。,JYP,43,时间单元25：飞机35准备起飞。 告诉飞机35等一会儿再试。 飞机36准备起飞。 告诉飞机36等一会儿再试。 飞机32降落，该机等待时间：4。时间单元26：飞机37准备起飞。 告诉飞机37等一会儿再试。 飞机12起飞，该机等待时间：15。时间单元27：飞机16起飞，该机等待时间：12。时间单元28：飞机17起飞，该机等待时间：13。时间单元29：飞机20起飞，该机等待时间：13。,JYP,44,时间单元30：飞机38准备起飞。 飞机21起飞

22、，该机等待时间：14。总模拟时间单元数：30总共处理的飞机数：38降落飞机总数：19起飞飞机总数：10拒绝服务的飞机总数：8队列中剩余的准备降落飞机数：0 队列中剩余的准备起飞飞机数：1跑道空闲时间百分比：3.33降落平均等待时间：1.11起飞平均等待时间：8.60,JYP,45,二叉树计数(4.9),当n = 0或1时，只有一棵二叉树。 当n = 2，存在2棵不同（结构）的二叉树：,JYP,46,而当n = 3，则存在5棵不同的二叉树：,那么，具有n个结点的不同二叉树究竟有多少呢？,JYP,47,不失一般性，将树的n个结点编号为1到n。假设一棵二叉树的前序序列为1 2 3 4 5 6 7 8

23、 9且其中序序列为2 3 1 5 4 7 8 6 9，则通过这对序列可以唯一确定一棵二叉树。 为了构造相应的二叉树，可找出前序第一个结点，即1。于是，结点1是树根，中序序列中所有在1之前的结点（2 3）属于左子树，其余结点（5 4 7 8 6 9）属于右子树。,JYP,48,这一步构造如下所示：,JYP,49,接着，可根据前序序列2 3和中序序列2 3构造左子树。显然，结点2是树根。由于在中序序列中，结点2之前无结点，所以其左子树为空，结点3是其右子树，如下图所示：,JYP,50,如此继续，最终可唯一地构造下图所示的二叉树：,JYP,51,一般地，我们可以设计算法，根据二叉树的前序/中序序列对

24、构造该树。 可以证明，每一棵二叉树都有唯一的前序/中序序列对。 如果树中结点按前序编号，即树的前序序列为1, 2, , n，则由上讨论可知，不同的二叉树定义不同的中序序列。 因此，不同的二叉树个数等于从前序序列为1, 2, , n的二叉树可产生的不同的中序序列的个数。,JYP,52,设bn是具有n个结点的不同二叉树的个数。bn实际上是按以下方式形成的各种可能的二叉树个数之和：一个根和两个结点数分别为i和ni1的子树(0i n)，如下所示：,JYP,53,对于每一个i，存在bi bn-i-1棵不同的树，因此有,(4.3),为了用n表示bn，必须求解递归方程(4.3)。设,(4.4),JYP,54

25、,B(x)是二叉树个数的生成函数。由于,JYP,55,即 x B2(x) B(x) + 1 = 0,JYP,56,解此一元二次方程，并注意B(0) = b0 = 1（等式(4.3)），可得,利用二项式公式展开(1 4x)1/2得到,JYP,57,令n = m + 1，可得,(4.5),JYP,58,比较等式(4.4) 和(4.5)，并注意bn是B(x)中xn的系数，可得,JYP,59,JYP,60,最小最大堆 (5.2),5.2.1 双端优先队列与最小最大堆 双端优先队列是一种支持下列操作的数据结构：（1） 插入一个具有任意key值的元素（2） 删除key值最大的元素（3） 删除key值最小的

26、元素 当只需要支持两个删除操作之一时，可采用前一节的最小堆或最大堆。而最小最大堆可支持以上全部操作。,JYP,61,双端优先队列可定义为如下的抽象类：template class DEPQ public: virtual void Insert(const Element其中，假设Element含有一个key数据成员。,JYP,62,定义：最小最大堆是一棵完全二叉树，且其中每个元素有一个key数据成员。树的各层交替为最小层和最大层。根结点在最小层。设x是最小最大堆的任意结点。若x在最小（最大）层上，则x中的元素的key值在以x为根的子树的所有元素中是最小（最大）的。位于最小（最大）层的结点称为

27、最小（最大）结点。,JYP,63,下面是一个具有12个元素的最小最大堆，其中最大层的结点用粗体字表示：,JYP,64,最小最大堆定义为DEPQ的派生类，以确保实现DEPQ的三个操作。template class MinMaxHeap: public DEPQ public: MinMaxHeap (const int); / 构造函数 MinMaxHeap ( ); / 析构函数 void Insert (const Element/ 堆中可容纳元素的最大个数,JYP,65,/ 其它用于实现最小最大堆的私有数据成员 ;template / 构造函数定义MinMaxHeap:MinMaxHeap

28、 (const int sz = DefaultHeapSize) : MaxSize(sz), n(0) h = new ElementMaxSize+1; / h0 不用,JYP,66,5.2.2 插入操作,假设将key为5的元素插入图5.4的最小最大堆。插入后的堆有13个元素，其形状如下图：,JYP,67,最小最大堆的插入算法也需要沿从新结点j到根的路径比较key值。 比较结点j的key值5和j的双亲的key值10，由于存放key值10的结点位于最小层，且5 10，所以5一定小于所有从j到根的路径中位于最大层的结点的key值。 为了保持最小最大堆的性质，只需要检查从j到根的路径中的最小结

29、点即可。首先，将key为10的元素移到结点j。接着，将key为7的元素移到10的原来位置。最后，将key为5的元素插入根结点。,JYP,68,由此形成的最小最大堆如下图，圆周加粗的结点内容在插入过程修改过：,JYP,69,再假设将key为80的元素插入图5.4所示的最小最大堆。插入后的堆有13个元素，其形状也与前面相同。 由于存放key值10的结点位于最小层，且10 hp.key) / 沿着最大层检查 hn=hp; VerifyMax(p, x); else VerifyMin(n, x); / 沿着最小层检查 / switch结束 / Insert结束,JYP,73,函数level确定一个结

30、点是位于最小最大堆的最小层，还是位于最大层。根据引理4.2，当log2(j + 1)为偶数时，结点j位于最大层，否则位于最小层。 函数VerifyMax从最大结点i开始，沿着从结点i到最小最大堆的根的路径检查最大结点，查找插入元素x的正确结点。在查找过程中，key值小于x.key的元素被移到下一个最大层。,JYP,74,template void MinMaxHeap:VerifyMax (int i, const Element / 将x插入结点i,JYP,75,函数VerifyMin与VerifyMax类似，所不同的是，前者从最小结点i开始，沿着从结点i到根的路径检查最小结点，将元素x插入

31、正确位置。 分析：由于n个元素的最小最大堆有O(log n)层，成员函数Insert的时间复杂性是O(log n)。,JYP,76,5.2.3 删除最小元素操作,最小最大堆中删除最小元素在根结点中。删除图5.4的最小元素7之后的堆有11个元素，形状如下：,JYP,77,此时应将key值为12的元素从堆中删除后再重新插入，需要沿着从根到叶的路径检查相关结点。 一般而言，将元素x插入根结点为空的最小最大堆h中有两种情况需要考虑：（1） 根结点无子女，这时可将x插入根结点中。（2） 根结点至少有一个子女。这时堆中的最小元素（不算元素x）位于根结点的子女结点或孙子女结点（最多6个）之一。假设该结点的编

32、号为k，则还需要考虑下列可能性： (a) x.keyhk.key。由于h中不存在比x更小的元素，所以x可插入根。,JYP,78,(b) x.key hk.key且k是根的子女。由于k是最大结点，其后代的key值都不大于hk.key，因而也不大于x.key。所以可将元素hk移到根，并将元素x插入结点k。 (c) x.key hk.key且k是根的孙子女。这时也可将元素hk移到根。设p是k的双亲。若x.key hp.key，则将x 和hp交换。这时，问题转化为将x插入以k为根的子堆中，且hk已腾空。这与初始插入根结点为空的最小最大堆h的情形类似。,JYP,79,在本例中，x.key = 12，根结

33、点的子女结点或孙子女结点中的最小元素的key值为9。 设k为该结点编号，p是k的双亲。 由于12 9且k是根的孙子女，这属于情形2(c)。因此，将key值为9的元素（即hk）移到根结点。由于x.key = 12 70 = hp.key，所以不将x 和hp交换。 这时的情形如下一页所示。,JYP,80,现在，需要将x插入以k为根的子堆中。结点k的子女结点或孙子女结点中的最小元素的key值为20。由于12 20，这属于情形2(a)，因此可将x插入hk。,JYP,81,通过以上讨论，可得成员函数DeleteMin。template Element* MinMaxHeap: DeleteMin(Ele

34、ment/ 情况 2(a)，可将x 插入hi,JYP,82,else / 情况2(b) 或 (c) hi = hk; if (k hp.key) Element t = hp; hp = x; x = t; / if (k=2*i+1)结束 i = k; / if (x.key 1），最小元素在最小堆的根结点中，最大元素在最大堆的根结点中。若n = 1，则最小和最大元素相同，在最小堆的根结点中。,JYP,89,若i是最小堆中的结点，则其在最大堆中的对应结点是i + 2log2i -1。因此，双堆定义性质（4）中的j可如下确定：j = i + 2log2i -1;if (j n + 1) j /= 2; 注意，如果最小堆的所有叶结点都满足性质（4），则最小堆中其余结点也满足性质（4）。,JYP,90,双堆Deap的类定义如下：template class Deap: public DEPQ public: Deap (const int); Deap ( ); void Insert (const Element/ 可容纳的最大元素个数 / 其它私有数据成员,