高級(jí)數(shù)據(jù)結(jié)構(gòu)

1、高級(jí)數(shù)據(jù)結(jié)構(gòu),教材：《數(shù)據(jù)結(jié)構(gòu)（C++描述）》（金遠(yuǎn)平編著，清華大學(xué)出版社）,JYP,1,代價(jià)分?jǐn)偅?.5.4）,將孤立地分析一次算法調(diào)用得出的結(jié)論應(yīng)用于一個(gè)ADT的相關(guān)操作序列會(huì)產(chǎn)生過(guò)于悲觀的結(jié)果。例1.12 整數(shù)容器Bag。class Bag { public: Bag ( int MaxSize = DefaultSize ); // 假設(shè)DefaultSize已定義 int Add (const int

2、 x ); // 將整數(shù)x加入容器中 int Delete (const int k ); // 從容器中刪除并打印k 個(gè)整數(shù)private: int top; // 指示已用空間 int *b; // 用數(shù)組b存放整數(shù) int n; // 容量};,JYP,2,各操作的實(shí)現(xiàn)如下：Bag::Bag ( int MaxSize = DefaultSize ):n(Ma

3、xSize) { b = new int[n]; 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) {

4、 if (top + 1 < k ) return 0; //容器內(nèi)元素不足k個(gè)，刪除失敗 else { for (int i = 0; i < k; i++) cout << b[top – i] << “ ” ; top = top - k; return 1; }} 先分析操作成功的情況：Add(x)的時(shí)間復(fù)雜性是O(1)；

5、Delete(k)需要k個(gè)程序步，且k可能等于n，在最壞情況下其時(shí)間復(fù)雜性是O(n)；一個(gè)調(diào)用Add操作 m1次，Delete操作m2次的序列的總代價(jià)則為O(m1+ m2n)。,JYP,4,前面是常規(guī)分析的結(jié)論。進(jìn)一步觀察：如果一開始容器為空，則刪除的元素不可能多于加入的元素，即 m2 次Delete操作的總代價(jià)不可能大于m1 次Add操作的總代價(jià)。因此，在最壞情況下，一個(gè)調(diào)用Add操作 m1次，Delete操作m2次的序列的總代價(jià)為O

6、(m1)。 操作失敗時(shí)，Add(x)和Delete(k) 的時(shí)間復(fù)雜性都是O(1)。因此，在操作可能失敗的情況下，一個(gè)調(diào)用Add操作 m1次，Delete操作m2次的序列的總代價(jià)為O(m1+ m2)。,JYP,5,常規(guī)分析并沒(méi)有錯(cuò)，只是其推導(dǎo)出的總代價(jià)上界遠(yuǎn)大于實(shí)際可得的上界。其原因是這種分析法沒(méi)有注意到連續(xù)的最壞情況刪除是不可能的。 為了取得更準(zhǔn)確的結(jié)果，還應(yīng)該度量ADT數(shù)據(jù)結(jié)構(gòu)的狀態(tài)。對(duì)于每一個(gè)可能的狀態(tài)S，

7、賦予一個(gè)實(shí)數(shù)?(S)。?(S)稱為S的勢(shì)能，其選擇應(yīng)使得?(S)越高，對(duì)處于S狀態(tài)的數(shù)據(jù)結(jié)構(gòu)成功進(jìn)行高代價(jià)操作的可能越大。 例如，將容器元素個(gè)數(shù)作為容器狀態(tài)的勢(shì)能就很合理，因?yàn)樵卦蕉?，?duì)容器成功進(jìn)行高代價(jià)操作的可能越大。,JYP,6,考慮一個(gè)由m個(gè)對(duì)ADT操作的調(diào)用構(gòu)成的序列，并設(shè)ti是第i次調(diào)用的實(shí)際代價(jià)，定義第i次調(diào)用的分?jǐn)偞鷥r(jià)ai為ai = ti + ?(Si) – ?(Si-1) Si-1是第i次

8、調(diào)用開始前ADT數(shù)據(jù)結(jié)構(gòu)的狀態(tài)，Si是第i次調(diào)用結(jié)束后ADT數(shù)據(jù)結(jié)構(gòu)的狀態(tài)。設(shè)?的選擇使得?(Sm) ≥ ?(S0)，則,JYP,7,即，分?jǐn)偞鷥r(jià)的總和是實(shí)際代價(jià)總和的上界。 例1.12將容器元素個(gè)數(shù)作為?(S)。若操作序列始于空容器，則?(Sm) ≥ ?(S0)總是成立。下表反映了容器?(S)的典型變化情況。,JYP,8,對(duì)于Add操作，ti=1，?(Si)–?(Si-1)=1，所以ai=2；對(duì)于Delete操作，ti=

9、k，?(Si)–?(Si-1)= –k，所以ai=0。 任何一個(gè)調(diào)用Add操作 m1次，Delete操作m2次的序列的總代價(jià)為O(m1?2 + m2?0) = O(m1)。,JYP,9,可見，分?jǐn)偡治龇▽⑴紶柍霈F(xiàn)的高價(jià)操作調(diào)用的代價(jià)分?jǐn)偟洁徑钠渌{(diào)用上，故而得名。 而且，當(dāng)用分?jǐn)偡治龇ǖ玫降囊粋€(gè)操作調(diào)用序列的代價(jià)總和比用常規(guī)分析法得到的代價(jià)總和小時(shí)，人們就得到了更接近實(shí)際代價(jià)的分析結(jié)果，或者說(shuō)對(duì)算法時(shí)間復(fù)雜性的判斷

10、更準(zhǔn)確了。,JYP,10,兩個(gè)字符串的最長(zhǎng)公共子序列（2.4.3）,一個(gè)字符串的子序列通過(guò)從字符串中刪除零或多個(gè)任意位置的字符得到。兩個(gè)字符串x和y的最長(zhǎng)公共子序列記為lcs(x, y)。例如，x = abdebcbb，y = adacbcb，則lcs(x, y)是adcbb和adbcb，如下所示：,JYP,11,問(wèn)題的基本求解方法： 用?標(biāo)記空串，則lcs(x, ?)= lcs(?, y) = ?。 lcs(xa

11、, ya) = lcs(x, y)a，即xa和ya的最長(zhǎng)公共子序列由x和y的最長(zhǎng)公共子序列后接a構(gòu)成。 若xa和yb的最后一個(gè)字符不相等，則當(dāng)lcs(xa, yb)不以a結(jié)尾時(shí)一定等于lcs(x, yb)，當(dāng)lcs(xa, yb)不以b結(jié)尾時(shí)一定等于lcs(xa, y)。因此lcs(xa, yb)等于 lcs(x, yb)與 lcs(xa, y)中較長(zhǎng)者。,JYP,12,由此可得計(jì)算兩個(gè)字符串最長(zhǎng)公共子序列長(zhǎng)度的遞歸算法lcs

12、: int String::lcs ( String y ) {// 驅(qū)動(dòng)器 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 ( str

13、[i-1] ==y[j-1] ) return ( lcs( i-1, j-1, y) + 1); return max( lcs( i-1, j, y), lcs( i, j-1, y));},JYP,13,設(shè)x的長(zhǎng)度為n，y的長(zhǎng)度為m，在最壞情況下lcs的時(shí)間復(fù)雜性為w(n, m)。w(n, m) =,因此，w(n, m)≥2 w(n-1, m-1)≥…≥2min(n, m)?c，即lcs的時(shí)間復(fù)雜性是指數(shù)型的。

14、 進(jìn)一步可發(fā)現(xiàn)，lcs(i, 0)=0（0≤i≤n），lcs(0, j) =0（0≤j≤m）。lcs(i, j)的計(jì)算依賴于lcs(i–1, j–1)、lcs(i–1, j)和lcs(i, j–1)，如下圖所示：,c （c為常數(shù)）n = 0或m = 0w(n, m-1) + w(n-1, m)否則,,JYP,14,根據(jù)以上拓?fù)潢P(guān)系，可以在不用遞歸的情況下計(jì)算lcs(i, j)。算法Lcs實(shí)現(xiàn)了上述優(yōu)化策略，這種策略體現(xiàn)了動(dòng)態(tài)

15、規(guī)劃的思想。算法Lcs的時(shí)間復(fù)雜性顯然是O(n?m)，這比其遞歸版有很大改進(jìn)。,JYP,15,int String::Lcs ( String y ) { int n = Length( ), m = y.Length( ); int lcs[MaxN][MaxM]; // MaxN和MaxM 是已定義的常數(shù) int i, j; for ( i = 0; i <= n; i++) lcs[i][

16、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;

17、 else lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]); return lcs[n][m];},JYP,16,例如，x = abdebcbb，y = adacbcb，lcs(x, y) = adbcb，改進(jìn)算法的計(jì)算如下所示：,JYP,17,機(jī)場(chǎng)模擬（2.9）,計(jì)算機(jī)模擬（simulation）：用軟件模仿另一個(gè)系統(tǒng)的行為。將研究對(duì)象表示為數(shù)據(jù)結(jié)構(gòu)，對(duì)象動(dòng)作表示為對(duì)數(shù)據(jù)的操作，控制

18、動(dòng)作的規(guī)則轉(zhuǎn)換為算法。通過(guò)更改數(shù)據(jù)的值或改變算法設(shè)置，可以觀察到計(jì)算機(jī)模擬的變化，從而使用戶能夠推導(dǎo)出關(guān)于實(shí)際系統(tǒng)行為的有用結(jié)論。在計(jì)算機(jī)處理一個(gè)對(duì)象的動(dòng)作期間，其它對(duì)象和動(dòng)作需等待。隊(duì)列在計(jì)算機(jī)模擬中具有重要應(yīng)用。,JYP,18,簡(jiǎn)單機(jī)場(chǎng)模擬：只有一個(gè)跑道。在每個(gè)時(shí)間單元，可起飛或降落一架飛機(jī)，但不可同時(shí)起降。飛機(jī)準(zhǔn)備降落或起飛的時(shí)間是隨機(jī)的，在任一時(shí)間單元，跑道可能處于空閑、降落或起飛狀態(tài)，并且可能有一些飛機(jī)在等待降落或

19、起飛。飛機(jī)在地上等待的代價(jià)比在空中等待的小，只有在沒(méi)有飛機(jī)等待降落的情況下才允許飛機(jī)起飛。當(dāng)出現(xiàn)隊(duì)列滿的情況時(shí)，則拒絕為新到達(dá)的飛機(jī)服務(wù)。,JYP,19,需要兩個(gè)隊(duì)列l(wèi)anding和takeoff。飛機(jī)可描述為：struct plane { int id;// 編號(hào) int tm;// 到達(dá)隊(duì)列時(shí)間};飛機(jī)的動(dòng)作為：enum action { ARRIVE, DEPART };,JYP,20,模擬運(yùn)行: 時(shí)間

20、單元:1 — endtime，并產(chǎn)生關(guān)于機(jī)場(chǎng)行為的重要統(tǒng)計(jì)信息，如處理的飛機(jī)數(shù)量，平均等待時(shí)間，被拒絕服務(wù)飛機(jī)的數(shù)量等。 采用基于泊松分布的隨機(jī)整數(shù)決定在每個(gè)時(shí)間單元有多少架新飛機(jī)需要降落或起飛。 假設(shè)在10個(gè)時(shí)間單元中到達(dá)的飛機(jī)數(shù)分別是：2，0，0，1，4，1，0，0，0，1，那么每個(gè)時(shí)間單元的平均到達(dá)數(shù)是0.9。,JYP,21,一個(gè)非負(fù)整數(shù)序列滿足給定期望值v的泊松分布意味著，對(duì)于該序列的一段足夠長(zhǎng)的子序列，其中整數(shù)的平均值接近

21、v。 在模擬中還需要建立新到達(dá)飛機(jī)的數(shù)據(jù)，處理被拒絕服務(wù)的飛機(jī)，起飛、降落飛機(jī)，處理機(jī)場(chǎng)空閑和總結(jié)模擬結(jié)果。 下面是機(jī)場(chǎng)模擬類定義：,JYP,22,class AirportSimulation {// 機(jī)場(chǎng)模擬。一個(gè)時(shí)間單元 = 起飛或降落的時(shí)間public: AirportSimulation( );// 構(gòu)造函數(shù) void RunSimulation( );// 模擬運(yùn)行private:

22、 Queue landing(6);// 等待降落飛機(jī)隊(duì)列，假設(shè)用環(huán)// 型隊(duì)列，實(shí)際長(zhǎng)度為5 Queue takeoff(6);// 等待起飛飛機(jī)隊(duì)列，同上 double expectarrive; //一個(gè)時(shí)間單元內(nèi)期望到達(dá)降落飛機(jī)數(shù) double expectdepart; //一個(gè)時(shí)間單元內(nèi)期望到達(dá)起飛飛機(jī)數(shù) int curtime;// 當(dāng)前時(shí)間 int endtime;

23、 // 模擬時(shí)間單元數(shù) int idletime ; // 跑道空閑時(shí)間單元數(shù) int landwait ; // 降落飛機(jī)的總等待時(shí)間,JYP,23,int nland ; // 降落的飛機(jī)數(shù) int nplanes; // 處理的飛機(jī)數(shù) int nrefuse; // 拒絕服務(wù)的飛機(jī)數(shù) int ntakeoff; // 起飛的飛機(jī)數(shù) void Randomize( );

24、// 設(shè)置隨機(jī)數(shù)種子 int PoissionRandom(double& expectvalue); // 根據(jù)泊松分布和給定期望值生成隨機(jī)非負(fù)整數(shù) plane* NewPlane(plane& p, action kind); // 建立新飛機(jī)的數(shù)據(jù)項(xiàng) void Refuse(plane& p, action kind); // 拒絕服務(wù) void Land(p

25、lane& p); // 降落飛機(jī) void Fly(plane& p); // 起飛飛機(jī) void Idle( ); // 處理空閑時(shí)間單元 void Conclude( ); // 總結(jié)模擬結(jié)果};,JYP,24,構(gòu)造函數(shù)初始化各變量，如下所示：AirportSimulation::AirportSimulation( ) {// 構(gòu)造函數(shù) Boolean ok

26、; cout > endtime; idletime = landwait = nland = nplanes = 0; nrefuse = ntakeoff = takoffwait = 0; // 初值 Randomize( ); // 設(shè)置隨機(jī)數(shù)種子 do { cout > expectarrive; cout > expectdepart;,JYP,

27、25,if (expectarrive 1.0) { cout << “機(jī)場(chǎng)將飽和！請(qǐng)重新輸入?！?lt;< endl; ok = FALSE; } else ok = TRUE; } while (ok == FALSE);},JYP,26,RunSimulation( )是模擬運(yùn)行

28、的主控程序：void AirportSimulation::RunSimulation( ) { int pri; // 偽隨機(jī)整數(shù) plane p; for (curtime = 1; curtime <= endtime; curtime++) { cout << “時(shí)間單元” << curtime << “：” ; pri = Po

29、issionRandom(expectarrive); for (int i =1; i <= pri; i++) { //處理新到達(dá)準(zhǔn)備降落的飛機(jī) p = *NewPlane(p, ARRIVE); if (landing.IsFull( )) Refuse(p, ARRIVE); else landing.Add(p); }

30、 pri = PoissionRandom(expectdepart);,JYP,27,for (int i =1; i <= pri; i++) { //處理新到達(dá)準(zhǔn)備起飛的飛機(jī) p = *NewPlane(p, DEPART); if (takeoff.IsFull( )) Refuse(p, DEPART); else takeoff.Add(p);

31、 } if (!landing.IsEmpty( )) { // 降落飛機(jī) p = *landing.Delete(p); Land(p); } else if (!takeoff.IsEmpty( )) {// 起飛飛機(jī) p = *takeoff.Delete(p); Fly(p);

32、 } else Idle( );// 處理空閑時(shí)間單元 } Conclude( );// 總結(jié)模擬結(jié)果},JYP,28,用庫(kù)函數(shù)srand和rand生成隨機(jī)數(shù)，并用時(shí)鐘設(shè)置隨機(jī)種子，以增強(qiáng)隨機(jī)性：void AirportSimulation::Randomize( ) { srand((unsigned int) (time(NULL)%10000));}

33、 庫(kù)函數(shù)time返回自格林威治時(shí)間1970年1月1日00:00:00 至今經(jīng)歷的秒數(shù)。這使得每次模擬運(yùn)行隨機(jī)數(shù)起點(diǎn)都不同。 rand按照均勻分布生成隨機(jī)數(shù)，還需要轉(zhuǎn)化為適合機(jī)場(chǎng)模擬的泊松分布隨機(jī)數(shù)。下面直接給出根據(jù)泊松分布和給定期望值生成偽隨機(jī)整數(shù)的算法（其數(shù)學(xué)推導(dǎo)略） ：,JYP,29,int AirportSimulation::PoissionRandom(double& expectvalue) { in

34、t n = 0;// 循環(huán)計(jì)數(shù) double limit; // e-v, 其中，v是期望值 double x; // 偽隨機(jī)數(shù) limit = exp(-expectvalue); x = rand( ) / (double) INT_MAX; // rand( )生成0到INT_MAX之間的整數(shù), x在0和1之間 while (x > limit) { n++;

35、 x *= rand( ) / (double) INT_MAX; } return n;},JYP,30,建立新飛機(jī)的數(shù)據(jù)項(xiàng)由函數(shù)NewPlane實(shí)現(xiàn)：plane* AirportSimulation::NewPlane(plane& p, action kind) { nplanes++;// 飛機(jī)總數(shù)加1 p.id = nplanes; p.tm = curtime;

36、switch (kind) { case ARRIVE: cout << “飛機(jī)” << nplanes << “準(zhǔn)備降落。” << endl; break; case DEPART: cout << “飛機(jī)” << nplanes << “準(zhǔn)備起飛。” <

37、;< endl; break; } return &p;},JYP,31,處理被拒絕的飛機(jī)由函數(shù)Refuse實(shí)現(xiàn):void AirportSimulation::Refuse(plane& p, action kind) { switch (kind) { case ARRIVE: cout << “引導(dǎo)飛機(jī)” &

38、lt;< p.id << “到其它機(jī)場(chǎng)降落。” << endl; break; case DEPART: cout << “告訴飛機(jī)” << p.id << “等一會(huì)兒再試?！?<< endl;

39、 break; } nrefuse++;// 被拒絕飛機(jī)總數(shù)加1},JYP,32,處理飛機(jī)降落由函數(shù)Land實(shí)現(xiàn)：void AirportSimulation::Land(plane& p) { int wait; wait = curtime – p.tm; cout << “飛機(jī)” << p.id << “降落，該機(jī)等待時(shí)間：”

40、 << wait << “?！?lt;< endl; nland++;// 降落飛機(jī)總數(shù)加1 landwait += wait;// 累加總降落等待時(shí)間},JYP,33,處理飛機(jī)起飛由函數(shù)Fly實(shí)現(xiàn)：void AirportSimulation::Fly(plane& p) { int wait = curtime – p.tm; cout &

41、lt;< “飛機(jī)” << p.id << “起飛，該機(jī)等待時(shí)間：” << wait << “?！?lt;< endl; ntakeoff++;// 起飛飛機(jī)總數(shù)加1 takeoffwait += wait;// 累加總起飛等待時(shí)間},JYP,34,處理機(jī)場(chǎng)空閑由函數(shù)Idle實(shí)現(xiàn)：void AirportSimulation::

42、Idle( ) { cout << “跑道空閑。” << endl; idletime++;// 跑道空閑時(shí)間加1} 總結(jié)模擬結(jié)果由函數(shù)Conclude實(shí)現(xiàn)：void AirportSimulation::Conclude( ) { cout << “總模擬時(shí)間單元數(shù)：” << endtime << endl; cout <

43、< “總共處理的飛機(jī)數(shù)：” << nplanes << endl; cout << “降落飛機(jī)總數(shù)：” << nland << endl; cout << “起飛飛機(jī)總數(shù)：” << ntakeoff << endl;,JYP,35,cout 0) cout 0) cout 0) cout << “起飛平

44、均等待時(shí)間：” << (double) takeoffwait / ntakeoff << endl;},JYP,36,可通過(guò)下列程序模擬運(yùn)行：#include “common.h”#include “simdefs.h”// 存放模擬類定義及相關(guān)函數(shù)實(shí)現(xiàn)void main( ) { AirportSimulation s; s.RunSimulation( );

45、},JYP,37,模擬過(guò)程產(chǎn)生的數(shù)據(jù)如下：請(qǐng)輸入模擬時(shí)間單元數(shù)：30請(qǐng)輸入一個(gè)時(shí)間單元內(nèi)期望到達(dá)降落飛機(jī)數(shù)：0.47請(qǐng)輸入一個(gè)時(shí)間單元內(nèi)期望到達(dá)起飛飛機(jī)數(shù)：0.47時(shí)間單元1：飛機(jī)1準(zhǔn)備降落。 飛機(jī)1降落，該機(jī)等待時(shí)間：0。時(shí)間單元2：跑道空閑。時(shí)間單元3：飛機(jī)2準(zhǔn)備降落。 飛機(jī)3準(zhǔn)備降落。 飛機(jī)2降落，該機(jī)等待時(shí)間：0。時(shí)間單元4： 飛機(jī)3降落，該機(jī)等待時(shí)間：1。,JYP,38,時(shí)間單元5：飛機(jī)

46、4準(zhǔn)備降落。 飛機(jī)5準(zhǔn)備降落。 飛機(jī)6準(zhǔn)備起飛。 飛機(jī)7準(zhǔn)備起飛。 飛機(jī)4降落，該機(jī)等待時(shí)間：0。時(shí)間單元6：飛機(jī)8準(zhǔn)備起飛。 飛機(jī)5降落，該機(jī)等待時(shí)間：1。時(shí)間單元7：飛機(jī)9準(zhǔn)備起飛。 飛機(jī)10準(zhǔn)備起飛。 飛機(jī)6起飛，該機(jī)等待時(shí)間：2。時(shí)間單元8： 飛機(jī)7起飛，該機(jī)等待時(shí)間：3。時(shí)間單元9： 飛機(jī)8起飛，該機(jī)等待時(shí)間：3。,JYP,39,時(shí)間單元10：飛機(jī)11準(zhǔn)備降落。

47、 飛機(jī)11降落，該機(jī)等待時(shí)間：0。時(shí)間單元11：飛機(jī)12準(zhǔn)備起飛。 飛機(jī)9起飛，該機(jī)等待時(shí)間：4。時(shí)間單元12：飛機(jī)13準(zhǔn)備降落。 飛機(jī)14準(zhǔn)備降落。 飛機(jī)13降落，該機(jī)等待時(shí)間：0。時(shí)間單元13： 飛機(jī)14降落，該機(jī)等待時(shí)間：1。時(shí)間單元14： 飛機(jī)10起飛，該機(jī)等待時(shí)間：7。時(shí)間單元15： 飛機(jī)15準(zhǔn)備降落。 飛機(jī)16準(zhǔn)備起飛。 飛機(jī)17準(zhǔn)備起飛。

48、 飛機(jī)15降落，該機(jī)等待時(shí)間：0。,JYP,40,時(shí)間單元16：飛機(jī)18準(zhǔn)備降落。 飛機(jī)19準(zhǔn)備降落。 飛機(jī)20準(zhǔn)備起飛。 飛機(jī)21準(zhǔn)備起飛。 飛機(jī)18降落，該機(jī)等待時(shí)間：0。時(shí)間單元17： 飛機(jī)22準(zhǔn)備降落。 飛機(jī)19降落，該機(jī)等待時(shí)間：1。時(shí)間單元18： 飛機(jī)23準(zhǔn)備起飛。 告訴飛機(jī)23等一會(huì)兒再試。 飛機(jī)22降落，該機(jī)等待時(shí)間：

49、1。,JYP,41,時(shí)間單元19： 飛機(jī)24準(zhǔn)備降落。 飛機(jī)25準(zhǔn)備降落。 飛機(jī)26準(zhǔn)備降落。 飛機(jī)27準(zhǔn)備起飛。 告訴飛機(jī)27等一會(huì)兒再試。 飛機(jī)24降落，該機(jī)等待時(shí)間：0。時(shí)間單元20： 飛機(jī)28準(zhǔn)備降落。 飛機(jī)29準(zhǔn)備降落。 飛機(jī)30準(zhǔn)備降落。 飛機(jī)31準(zhǔn)備降落。 引導(dǎo)飛機(jī)31到其它機(jī)場(chǎng)降落。

50、 飛機(jī)25降落，該機(jī)等待時(shí)間：1。,JYP,42,時(shí)間單元21：飛機(jī)32準(zhǔn)備降落。 飛機(jī)33準(zhǔn)備起飛。 告訴飛機(jī)33等一會(huì)兒再試。 飛機(jī)26降落，該機(jī)等待時(shí)間：2。時(shí)間單元22：飛機(jī)28降落，該機(jī)等待時(shí)間：2。時(shí)間單元23：飛機(jī)29降落，該機(jī)等待時(shí)間：3。時(shí)間單元24：飛機(jī)34準(zhǔn)備起飛。 告訴飛機(jī)34等一會(huì)兒再試。 飛機(jī)30降落，該機(jī)等待時(shí)間：4。,JYP,43,時(shí)間單元

51、25：飛機(jī)35準(zhǔn)備起飛。 告訴飛機(jī)35等一會(huì)兒再試。 飛機(jī)36準(zhǔn)備起飛。 告訴飛機(jī)36等一會(huì)兒再試。 飛機(jī)32降落，該機(jī)等待時(shí)間：4。時(shí)間單元26：飛機(jī)37準(zhǔn)備起飛。 告訴飛機(jī)37等一會(huì)兒再試。 飛機(jī)12起飛，該機(jī)等待時(shí)間：15。時(shí)間單元27：飛機(jī)16起飛，該機(jī)等待時(shí)間：12。時(shí)間單元28：飛機(jī)17起飛，該機(jī)等待時(shí)間：13。時(shí)間單元29：飛機(jī)20起飛，該機(jī)等待時(shí)間

52、：13。,JYP,44,時(shí)間單元30：飛機(jī)38準(zhǔn)備起飛。 飛機(jī)21起飛，該機(jī)等待時(shí)間：14。總模擬時(shí)間單元數(shù)：30總共處理的飛機(jī)數(shù)：38降落飛機(jī)總數(shù)：19起飛飛機(jī)總數(shù)：10拒絕服務(wù)的飛機(jī)總數(shù)：8隊(duì)列中剩余的準(zhǔn)備降落飛機(jī)數(shù)：0 隊(duì)列中剩余的準(zhǔn)備起飛飛機(jī)數(shù)：1跑道空閑時(shí)間百分比：3.33降落平均等待時(shí)間：1.11起飛平均等待時(shí)間：8.60,JYP,45,二叉樹計(jì)數(shù)(4.9),當(dāng)n = 0或1時(shí)，只有一棵二叉樹

53、。 當(dāng)n = 2，存在2棵不同（結(jié)構(gòu)）的二叉樹：,JYP,46,而當(dāng)n = 3，則存在5棵不同的二叉樹：,那么，具有n個(gè)結(jié)點(diǎn)的不同二叉樹究竟有多少呢？,JYP,47,不失一般性，將樹的n個(gè)結(jié)點(diǎn)編號(hào)為1到n。假設(shè)一棵二叉樹的前序序列為1 2 3 4 5 6 7 8 9且其中序序列為2 3 1 5 4 7 8 6 9，則通過(guò)這對(duì)序列可以唯一確定一棵二叉樹。 為了構(gòu)造相應(yīng)的二叉樹，可找出前序第一個(gè)結(jié)點(diǎn)，即1。于是，結(jié)點(diǎn)1是

54、樹根，中序序列中所有在1之前的結(jié)點(diǎn)（2 3）屬于左子樹，其余結(jié)點(diǎn)（5 4 7 8 6 9）屬于右子樹。,JYP,48,這一步構(gòu)造如下所示：,JYP,49,接著，可根據(jù)前序序列2 3和中序序列2 3構(gòu)造左子樹。顯然，結(jié)點(diǎn)2是樹根。由于在中序序列中，結(jié)點(diǎn)2之前無(wú)結(jié)點(diǎn)，所以其左子樹為空，結(jié)點(diǎn)3是其右子樹，如下圖所示：,JYP,50,如此繼續(xù)，最終可唯一地構(gòu)造下圖所示的二叉樹：,JYP,51,一般地，我們可以設(shè)計(jì)算法，根據(jù)二叉樹的前序/中序序列

55、對(duì)構(gòu)造該樹。 可以證明，每一棵二叉樹都有唯一的前序/中序序列對(duì)。 如果樹中結(jié)點(diǎn)按前序編號(hào)，即樹的前序序列為1, 2, …, n，則由上討論可知，不同的二叉樹定義不同的中序序列。 因此，不同的二叉樹個(gè)數(shù)等于從前序序列為1, 2, …, n的二叉樹可產(chǎn)生的不同的中序序列的個(gè)數(shù)。,JYP,52,設(shè)bn是具有n個(gè)結(jié)點(diǎn)的不同二叉樹的個(gè)數(shù)。bn實(shí)際上是按以下方式形成的各種可能的二叉樹個(gè)數(shù)之和：一個(gè)根和兩個(gè)結(jié)點(diǎn)數(shù)分別為i

56、和n–i–1的子樹(0≤i < n)，如下所示：,JYP,53,對(duì)于每一個(gè)i，存在bi bn-i-1棵不同的樹，因此有,(4.3),為了用n表示bn，必須求解遞歸方程(4.3)。設(shè),(4.4),JYP,54,B(x)是二叉樹個(gè)數(shù)的生成函數(shù)。由于,JYP,55,即 x B2(x) – B(x) + 1 = 0,JYP,56,解此一元二次方程，并注意B(0) = b0 = 1（等式(4.3)），可得,利用二項(xiàng)式公式展開(1 –

57、 4x)1/2得到,JYP,57,令n = m + 1，可得,(4.5),JYP,58,比較等式(4.4) 和(4.5)，并注意bn是B(x)中xn的系數(shù)，可得,JYP,59,JYP,60,最小最大堆 (5.2),5.2.1 雙端優(yōu)先隊(duì)列與最小最大堆 雙端優(yōu)先隊(duì)列是一種支持下列操作的數(shù)據(jù)結(jié)構(gòu)：（1） 插入一個(gè)具有任意key值的元素（2） 刪除key值最大的元素（3） 刪除key值最小的元素 當(dāng)只需要支持兩個(gè)刪除

58、操作之一時(shí)，可采用前一節(jié)的最小堆或最大堆。而最小最大堆可支持以上全部操作。,JYP,61,雙端優(yōu)先隊(duì)列可定義為如下的抽象類：template class DEPQ {public: virtual void Insert(const Element&) = 0; virtual Element* DeleteMax(Element&) = 0; virtual Element* DeleteMin

59、(Element&) = 0;};其中，假設(shè)Element含有一個(gè)key數(shù)據(jù)成員。,JYP,62,定義：最小最大堆是一棵完全二叉樹，且其中每個(gè)元素有一個(gè)key數(shù)據(jù)成員。樹的各層交替為最小層和最大層。根結(jié)點(diǎn)在最小層。設(shè)x是最小最大堆的任意結(jié)點(diǎn)。若x在最?。ㄗ畲螅由?，則x中的元素的key值在以x為根的子樹的所有元素中是最?。ㄗ畲螅┑?。位于最小（最大）層的結(jié)點(diǎn)稱為最?。ㄗ畲螅┙Y(jié)點(diǎn)。,JYP,63,下面是一個(gè)具有12個(gè)元素的最小最

60、大堆，其中最大層的結(jié)點(diǎn)用粗體字表示：,JYP,64,最小最大堆定義為DEPQ的派生類，以確保實(shí)現(xiàn)DEPQ的三個(gè)操作。template class MinMaxHeap: public DEPQ {public: MinMaxHeap (const int); // 構(gòu)造函數(shù) ~MinMaxHeap ( ); // 析構(gòu)函數(shù) void Insert (const Element&);

61、 Element* DeleteMax(Element& x ); Element* DeleteMin(Element& x );private: Element *h; int n; // 最小最大堆的當(dāng)前元素個(gè)數(shù) int MaxSize;// 堆中可容納元素的最大個(gè)數(shù),JYP,65,// 其它用于實(shí)現(xiàn)最小最大堆的私有數(shù)據(jù)成員 …};template // 構(gòu)造函數(shù)定義M

62、inMaxHeap::MinMaxHeap (const int sz = DefaultHeapSize) : MaxSize(sz), n(0) {h = new Element[MaxSize+1]; // h[0] 不用},JYP,66,5.2.2 插入操作,假設(shè)將key為5的元素插入圖5.4的最小最大堆。插入后的堆有13個(gè)元素，其形狀如下圖：,JYP,67,最小最大堆的插入算法也需要沿從新結(jié)點(diǎn)j到根的路徑比較key值。

63、 比較結(jié)點(diǎn)j的key值5和j的雙親的key值10，由于存放key值10的結(jié)點(diǎn)位于最小層，且5 < 10，所以5一定小于所有從j到根的路徑中位于最大層的結(jié)點(diǎn)的key值。 為了保持最小最大堆的性質(zhì)，只需要檢查從j到根的路徑中的最小結(jié)點(diǎn)即可。首先，將key為10的元素移到結(jié)點(diǎn)j。接著，將key為7的元素移到10的原來(lái)位置。最后，將key為5的元素插入根結(jié)點(diǎn)。,JYP,68,由此形成的最小最大堆如下圖，圓周加粗的結(jié)點(diǎn)內(nèi)容

64、在插入過(guò)程修改過(guò)：,JYP,69,再假設(shè)將key為80的元素插入圖5.4所示的最小最大堆。插入后的堆有13個(gè)元素，其形狀也與前面相同。 由于存放key值10的結(jié)點(diǎn)位于最小層，且10 < 80，所以80一定大于所有從j到根的路徑中位于最小層的結(jié)點(diǎn)的key值。 為了保持最小最大堆的性質(zhì)，只需要檢查從j到根的路徑中的最大結(jié)點(diǎn)即可。圖5.4中只有一個(gè)這樣的結(jié)點(diǎn)，其元素的key值為40，將該元素移到結(jié)點(diǎn)j，并將key為8

65、0的新元素插入key為40的元素原來(lái)的結(jié)點(diǎn)。,JYP,70,由此形成的最小最大堆如下圖：,JYP,71,成員函數(shù)Insert實(shí)現(xiàn)了上述過(guò)程，其中又用到私有成員函數(shù)VerifyMax，VerifyMin 和level。template void MinMaxHeap::Insert(const Element&x ) { if (n == MaxSize ) { MinMaxFull( ); return;} n+

66、+; int p = n/2; // p是新結(jié)點(diǎn)的雙親 if (!p) {h[1] = x; return;} // 插入初始時(shí)為空的堆 switch (level(p)) { case MIN: if (x.key < h[p].key) { // 沿著最小層檢查 h[n]=h[p]; VerifyMin(p, x);

67、 },JYP,72,else VerifyMax(n, x); // 沿著最大層檢查 break; case MAX: if (x.key > h[p].key) { // 沿著最大層檢查 h[n]=h[p]; VerifyMax(p, x); } else VerifyMin(n, x

68、); // 沿著最小層檢查 } // switch結(jié)束} // Insert結(jié)束,JYP,73,函數(shù)level確定一個(gè)結(jié)點(diǎn)是位于最小最大堆的最小層，還是位于最大層。根據(jù)引理4.2，當(dāng)?log2(j + 1)?為偶數(shù)時(shí)，結(jié)點(diǎn)j位于最大層，否則位于最小層。 函數(shù)VerifyMax從最大結(jié)點(diǎn)i開始，沿著從結(jié)點(diǎn)i到最小最大堆的根的路徑檢查最大結(jié)點(diǎn)，查找插入元素x的正確結(jié)點(diǎn)。在查找過(guò)程中，key值小于x.key的元素被移

69、到下一個(gè)最大層。,JYP,74,template void MinMaxHeap::VerifyMax (int i, const Element&x ) { // 沿著從最大結(jié)點(diǎn)i // 到根結(jié)點(diǎn)的路徑檢查最大結(jié)點(diǎn)，將x插入正確位置 for (int gp = i/4; gp && (x.key > h[gp].key); gp /=4) { // gp是 i的祖父

70、 h[i] = h[gp];// 將h[gp]移到h[i] i = gp; } h[i] = x; // 將x插入結(jié)點(diǎn)i},JYP,75,函數(shù)VerifyMin與VerifyMax類似，所不同的是，前者從最小結(jié)點(diǎn)i開始，沿著從結(jié)點(diǎn)i到根的路徑檢查最小結(jié)點(diǎn)，將元素x插入正確位置。 分析：由于n個(gè)元素的最小最大堆有O(log n)層，成員函數(shù)Insert的時(shí)間復(fù)雜性是O(log n)。,J