高级数据结构.ppt
《高级数据结构.ppt》由会员分享,可在线阅读,更多相关《高级数据结构.ppt(378页珍藏版)》请在三一文库上搜索。
1、JYP,1,高级数据结构,教材: 数据结构(C+描述)(金远平编著,清华大学出版社) 讲课教师: 金远平,软件学院 ,JYP,2,代价分摊(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
2、 top; / 指示已用空间 int *b; / 用数组b存放整数 int n; / 容量 ;,JYP,3,各操作的实现如下: 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,4,int Bag:Delete (const int k) if (top + 1 k ) return 0; /容器内元素不足k个
3、,删除失败 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)。,JYP,5,前面是常规分析的结论。进一步观察:如果一开始容器为空,则删除的元素不可能多于加入的元素,即 m2 次Delete操作的总代价不可能大于m1 次Add操作的总代价。因此,在最坏情况下,一个调用Ad
4、d操作 m1次,Delete操作m2次的序列的总代价为O(m1)。 操作失败时,Add(x)和Delete(k) 的时间复杂性都是O(1)。因此,在操作可能失败的情况下,一个调用Add操作 m1次,Delete操作m2次的序列的总代价为O(m1+ m2)。,JYP,6,常规分析并没有错,只是其推导出的总代价上界远大于实际可得的上界。其原因是这种分析法没有注意到连续的最坏情况删除是不可能的。 为了取得更准确的结果,还应该度量ADT数据结构的状态。对于每一个可能的状态S,赋予一个实数(S)。(S)称为S的势能,其选择应使得(S)越高,对处于S状态的数据结构成功进行高代价操作的可能越大。 例如,将容
5、器元素个数作为容器状态的势能就很合理,因为元素越多,对容器成功进行高代价操作的可能越大。,JYP,7,考虑一个由m个对ADT操作的调用构成的序列,并设ti是第i次调用的实际代价,定义第i次调用的分摊代价ai为 ai = ti + (Si) (Si-1) Si-1是第i次调用开始前ADT数据结构的状态,Si是第i次调用结束后ADT数据结构的状态。设的选择使得(Sm) (S0),则,JYP,8,即,分摊代价的总和是实际代价总和的上界。 例1.12将容器元素个数作为(S)。若操作序列始于空容器,则(Sm) (S0)总是成立。下表反映了容器(S)的典型变化情况。,JYP,9,对于Add操作,ti=1,
6、(Si)(Si-1)=1,所以ai=2;对于Delete操作,ti=k,(Si)(Si-1)= k,所以ai=0。 任何一个调用Add操作 m1次,Delete操作m2次的序列的总代价为O(m12 + m20) = O(m1)。,JYP,10,可见,分摊分析法将偶尔出现的高价操作调用的代价分摊到邻近的其它调用上,故而得名。 而且,当用分摊分析法得到的一个操作调用序列的代价总和比用常规分析法得到的代价总和小时,人们就得到了更接近实际代价的分析结果,或者说对算法时间复杂性的判断更准确了。,JYP,11,两个字符串的最长公共子序列(2.4.3),一个字符串的子序列通过从字符串中删除零或多个任意位置的
7、字符得到。 两个字符串x和y的最长公共子序列记为lcs(x, y)。 例如,x = abdebcbb,y = adacbcb,则lcs(x, y)是adcbb和adbcb,如下所示:,JYP,12,问题的基本求解方法: 用标记空串,则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)等于 lc
8、s(x, yb)与 lcs(xa, y)中较长者。,JYP,13,由此可得计算两个字符串最长公共子序列长度的递归算法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 m
9、ax( lcs( i-1, j, y), lcs( i, j-1, y); ,JYP,14,设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 = 0 w(n, m-1) + w(n-1, m) 否则,JYP,15,根
10、据以上拓扑关系,可以在不用递归的情况下计算lcs(i, j)。算法Lcs实现了上述优化策略,这种策略体现了动态规划的思想。算法Lcs的时间复杂性显然是O(nm),这比其递归版有很大改进。,JYP,16,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 (
11、i = 1; i = n; i+) for ( j = 1; j = m; j+) if ( stri-1 =y.strj-1 ) lcsij = lcsi-1j-1 + 1; else lcsij = max(lcsi-1j, lcsij-1); return lcsnm; ,JYP,17,例如,x = abdebcbb,y = adacbcb,lcs(x, y) = adbcb,改进算法的计算如下所示:,JYP,18,机场模拟(2.9),计算机模拟(simulation): 用软件模仿另一个系统的行为。 将研究对象表示为数据结构,对象动作表示为对数据的操作,控制动作的规则转换为算法。 通过
12、更改数据的值或改变算法设置,可以观察到计算机模拟的变化,从而使用户能够推导出关于实际系统行为的有用结论。 在计算机处理一个对象的动作期间,其它对象和动作需等待。 队列在计算机模拟中具有重要应用。,JYP,19,简单机场模拟: 只有一个跑道。 在每个时间单元,可起飞或降落一架飞机,但不可同时起降。 飞机准备降落或起飞的时间是随机的,在任一时间单元,跑道可能处于空闲、降落或起飞状态,并且可能有一些飞机在等待降落或起飞。 飞机在地上等待的代价比在空中等待的小,只有在没有飞机等待降落的情况下才允许飞机起飞。 当出现队列满的情况时,则拒绝为新到达的飞机服务。,JYP,20,需要两个队列landing和t
13、akeoff。 飞机可描述为: struct plane int id; / 编号 int tm; / 到达队列时间 ; 飞机的动作为: enum action ARRIVE, DEPART ;,JYP,21,模拟运行: 时间单元:1 endtime,并产生关于机场行为的重要统计信息,如处理的飞机数量,平均等待时间,被拒绝服务飞机的数量等。 采用基于泊松分布的随机整数决定在每个时间单元有多少架新飞机需要降落或起飞。 假设在10个时间单元中到达的飞机数分别是:2,0,0,1,4,1,0,0,0,1,那么每个时间单元的平均到达数是0.9。,JYP,22,一个非负整数序列满足给定期望值v的泊松分布意
14、味着,对于该序列的一段足够长的子序列,其中整数的平均值接近v。 在模拟中还需要建立新到达飞机的数据,处理被拒绝服务的飞机,起飞、降落飞机,处理机场空闲和总结模拟结果。 下面是机场模拟类定义:,JYP,23,class AirportSimulation / 机场模拟。一个时间单元 = 起飞或降落的时间 public: AirportSimulation( ); / 构造函数 void RunSimulation( ); / 模拟运行 private: Queue landing(6); / 等待降落飞机队列,假设用环 / 型队列,实际长度为5 Queue takeoff(6); / 等待起飞飞
15、机队列,同上 double expectarrive; /一个时间单元内期望到达降落飞机数 double expectdepart; /一个时间单元内期望到达起飞飞机数 int curtime; / 当前时间 int endtime; / 模拟时间单元数 int idletime ; / 跑道空闲时间单元数 int landwait ; / 降落飞机的总等待时间,JYP,24,int nland ; / 降落的飞机数 int nplanes; / 处理的飞机数 int nrefuse; / 拒绝服务的飞机数 int ntakeoff; / 起飞的飞机数 void Randomize( ); /
16、 设置随机数种子 int PoissionRandom(double,JYP,25,构造函数初始化各变量,如下所示: AirportSimulation:AirportSimulation( ) / 构造函数 Boolean ok; cout endtime; idletime = landwait = nland = nplanes = 0; nrefuse = ntakeoff = takoffwait = 0; / 初值 Randomize( ); / 设置随机数种子 do cout expectarrive; cout expectdepart;,JYP,26,if (expectar
17、rive 1.0) cout “机场将饱和!请重新输入。” endl; ok = FALSE; else ok = TRUE; while (ok = FALSE); ,JYP,27,RunSimulation( )是模拟运行的主控程序: void AirportSimulation:RunSimulation( ) int pri; / 伪随机整数 plane p; for (curtime = 1; curtime = endtime; curtime+) cout “时间单元” curtime “:” ; pri = PoissionRandom(expectarrive); for (
18、int i =1; i = pri; i+) /处理新到达准备降落的飞机 p = *NewPlane(p, ARRIVE); if (landing.IsFull( ) Refuse(p, ARRIVE); else landing.Add(p); pri = PoissionRandom(expectdepart);,JYP,28,for (int i =1; i = pri; i+) /处理新到达准备起飞的飞机 p = *NewPlane(p, DEPART); if (takeoff.IsFull( ) Refuse(p, DEPART); else takeoff.Add(p); if
19、 (!landing.IsEmpty( ) / 降落飞机 p = *landing.Delete(p); Land(p); else if (!takeoff.IsEmpty( ) / 起飞飞机 p = *takeoff.Delete(p); Fly(p); else Idle( ); / 处理空闲时间单元 Conclude( ); / 总结模拟结果 ,JYP,29,用库函数srand和rand生成随机数,并用时钟设置随机种子,以增强随机性: void AirportSimulation:Randomize( ) srand(unsigned int) (time(NULL)%10000);
20、库函数time返回自格林威治时间1970年1月1日00:00:00 至今经历的秒数。这使得每次模拟运行随机数起点都不同。 rand按照均匀分布生成随机数,还需要转化为适合机场模拟的泊松分布随机数。下面直接给出根据泊松分布和给定期望值生成伪随机整数的算法(其数学推导略) :,JYP,30,int AirportSimulation:PoissionRandom(double ,JYP,31,建立新飞机的数据项由函数NewPlane实现: plane* AirportSimulation:NewPlane(plane ,JYP,32,处理被拒绝的飞机由函数Refuse实现: void Airpor
21、tSimulation:Refuse(plane / 被拒绝飞机总数加1 ,JYP,33,处理飞机降落由函数Land实现: void AirportSimulation:Land(plane / 累加总降落等待时间 ,JYP,34,处理飞机起飞由函数Fly实现: void AirportSimulation:Fly(plane / 累加总起飞等待时间 ,JYP,35,处理机场空闲由函数Idle实现: void AirportSimulation:Idle( ) cout “跑道空闲。” endl; idletime+; / 跑道空闲时间加1 总结模拟结果由函数Conclude实现: void
22、AirportSimulation:Conclude( ) cout “总模拟时间单元数:” endtime endl; cout “总共处理的飞机数:” nplanes endl; cout “降落飞机总数:” nland endl; cout “起飞飞机总数:” ntakeoff endl;,JYP,36,cout 0) cout 0) cout 0) cout “起飞平均等待时间:” (double) takeoffwait / ntakeoff endl; ,JYP,37,可通过下列程序模拟运行: #include “common.h” #include “simdefs.h” / 存
23、放模拟类定义及相关函数实现 void main( ) AirportSimulation s; s.RunSimulation( ); ,JYP,38,模拟过程产生的数据如下: 请输入模拟时间单元数:30 请输入一个时间单元内期望到达降落飞机数:0.47 请输入一个时间单元内期望到达起飞飞机数:0.47 时间单元1:飞机1准备降落。 飞机1降落,该机等待时间:0。 时间单元2:跑道空闲。 时间单元3:飞机2准备降落。 飞机3准备降落。 飞机2降落,该机等待时间:0。 时间单元4: 飞机3降落,该机等待时间:1。,JYP,39,时间单元5:飞机4准备降落。 飞机5准备降落。 飞机6准备起飞。 飞
24、机7准备起飞。 飞机4降落,该机等待时间:0。 时间单元6:飞机8准备起飞。 飞机5降落,该机等待时间:1。 时间单元7:飞机9准备起飞。 飞机10准备起飞。 飞机6起飞,该机等待时间:2。 时间单元8: 飞机7起飞,该机等待时间:3。 时间单元9: 飞机8起飞,该机等待时间:3。,JYP,40,时间单元10:飞机11准备降落。 飞机11降落,该机等待时间:0。 时间单元11:飞机12准备起飞。 飞机9起飞,该机等待时间:4。 时间单元12:飞机13准备降落。 飞机14准备降落。 飞机13降落,该机等待时间:0。 时间单元13: 飞机14降落,该机等待时间:1。 时间单元14: 飞机10起飞,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 高级 数据结构
链接地址:https://www.31doc.com/p-3165748.html