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

1、高級數(shù)據(jù)結(jié)構(gòu),教材：《數(shù)據(jù)結(jié)構(gòu)（C++描述）》（金遠(yuǎn)平編著，清華大學(xué)出版社）,JYP,1,代價分?jǐn)偅?.5.4）,將孤立地分析一次算法調(diào)用得出的結(jié)論應(yīng)用于一個ADT的相關(guān)操作序列會產(chǎn)生過于悲觀的結(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 個整數(shù)private: int top; // 指示已用空間 int *b; // 用數(shù)組b存放整數(shù) int n; // 容量};,JYP,2,各操作的實現(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個，刪除失敗 else { for (int i = 0; i < k; i++) cout << b[top – i] << “ ” ; top = top - k; return 1; }} 先分析操作成功的情況：Add(x)的時間復(fù)雜性是O(1)；

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

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

7、賦予一個實數(shù)?(S)。?(S)稱為S的勢能，其選擇應(yīng)使得?(S)越高，對處于S狀態(tài)的數(shù)據(jù)結(jié)構(gòu)成功進(jìn)行高代價操作的可能越大。 例如，將容器元素個數(shù)作為容器狀態(tài)的勢能就很合理，因為元素越多，對容器成功進(jìn)行高代價操作的可能越大。,JYP,6,考慮一個由m個對ADT操作的調(diào)用構(gòu)成的序列，并設(shè)ti是第i次調(diào)用的實際代價，定義第i次調(diào)用的分?jǐn)偞鷥rai為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的總和是實際代價總和的上界。 例1.12將容器元素個數(shù)作為?(S)。若操作序列始于空容器，則?(Sm) ≥ ?(S0)總是成立。下表反映了容器?(S)的典型變化情況。,JYP,8,對于Add操作，ti=1，?(Si)–?(Si-1)=1，所以ai=2；對于Delete操作，ti=

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

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

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

12、: int String::lcs ( String y ) {// 驅(qū)動器 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的長度為n，y的長度為m，在最壞情況下lcs的時間復(fù)雜性為w(n, m)。w(n, m) =,因此，w(n, m)≥2 w(n-1, m-1)≥…≥2min(n, m)?c，即lcs的時間復(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)的計算依賴于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)系，可以在不用遞歸的情況下計算lcs(i, j)。算法Lcs實現(xiàn)了上述優(yōu)化策略，這種策略體現(xiàn)了動態(tài)

15、規(guī)劃的思想。算法Lcs的時間復(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)算法的計算如下所示：,JYP,17,機(jī)場模擬（2.9）,計算機(jī)模擬（simulation）：用軟件模仿另一個系統(tǒng)的行為。將研究對象表示為數(shù)據(jù)結(jié)構(gòu)，對象動作表示為對數(shù)據(jù)的操作，控制

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

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

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

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

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

23、 // 模擬時間單元數(shù) int idletime ; // 跑道空閑時間單元數(shù) int landwait ; // 降落飛機(jī)的總等待時間,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ù)項 void Refuse(plane& p, action kind); // 拒絕服務(wù) void Land(p

25、lane& p); // 降落飛機(jī) void Fly(plane& p); // 起飛飛機(jī) void Idle( ); // 處理空閑時間單元 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ī)場將飽和！請重新輸入?！?lt;< endl; ok = FALSE; } else ok = TRUE; } while (ok == FALSE);},JYP,26,RunSimulation( )是模擬運行

28、的主控程序：void AirportSimulation::RunSimulation( ) { int pri; // 偽隨機(jī)整數(shù) plane p; for (curtime = 1; curtime <= endtime; curtime++) { cout << “時間單元” << 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( );// 處理空閑時間單元 } Conclude( );// 總結(jié)模擬結(jié)果},JYP,28,用庫函數(shù)srand和rand生成隨機(jī)數(shù)，并用時鐘設(shè)置隨機(jī)種子，以增強(qiáng)隨機(jī)性：void AirportSimulation::Randomize( ) { srand((unsigned int) (time(NULL)%10000));}

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

34、t n = 0;// 循環(huán)計數(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ù)項由函數(shù)NewPlane實現(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實現(xiàn):void AirportSimulation::Refuse(plane& p, action kind) { switch (kind) { case ARRIVE: cout << “引導(dǎo)飛機(jī)” &

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

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

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

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

42、Idle( ) { cout << “跑道空閑?！?<< endl; idletime++;// 跑道空閑時間加1} 總結(jié)模擬結(jié)果由函數(shù)Conclude實現(xiàn)：void AirportSimulation::Conclude( ) { cout << “總模擬時間單元數(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、均等待時間：” << (double) takeoffwait / ntakeoff << endl;},JYP,36,可通過下列程序模擬運行：#include “common.h”#include “simdefs.h”// 存放模擬類定義及相關(guān)函數(shù)實現(xiàn)void main( ) { AirportSimulation s; s.RunSimulation( );

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

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

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

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

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

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

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

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

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

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

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

56、和n–i–1的子樹(0≤i < n)，如下所示：,JYP,53,對于每一個i，存在bi bn-i-1棵不同的樹，因此有,(4.3),為了用n表示bn，必須求解遞歸方程(4.3)。設(shè),(4.4),JYP,54,B(x)是二叉樹個數(shù)的生成函數(shù)。由于,JYP,55,即 x B2(x) – B(x) + 1 = 0,JYP,56,解此一元二次方程，并注意B(0) = b0 = 1（等式(4.3)），可得,利用二項式公式展開(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)先隊列與最小最大堆 雙端優(yōu)先隊列是一種支持下列操作的數(shù)據(jù)結(jié)構(gòu)：（1） 插入一個具有任意key值的元素（2） 刪除key值最大的元素（3） 刪除key值最小的元素 當(dāng)只需要支持兩個刪除

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

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

60、大堆，其中最大層的結(jié)點用粗體字表示：,JYP,64,最小最大堆定義為DEPQ的派生類，以確保實現(xiàn)DEPQ的三個操作。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)前元素個數(shù) int MaxSize;// 堆中可容納元素的最大個數(shù),JYP,65,// 其它用于實現(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個元素，其形狀如下圖：,JYP,67,最小最大堆的插入算法也需要沿從新結(jié)點j到根的路徑比較key值。

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

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

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

66、+; int p = n/2; // p是新結(jié)點的雙親 if (!p) {h[1] = x; return;} // 插入初始時為空的堆 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確定一個結(jié)點是位于最小最大堆的最小層，還是位于最大層。根據(jù)引理4.2，當(dāng)?log2(j + 1)?為偶數(shù)時，結(jié)點j位于最大層，否則位于最小層。 函數(shù)VerifyMax從最大結(jié)點i開始，沿著從結(jié)點i到最小最大堆的根的路徑檢查最大結(jié)點，查找插入元素x的正確結(jié)點。在查找過程中，key值小于x.key的元素被移

69、到下一個最大層。,JYP,74,template void MinMaxHeap::VerifyMax (int i, const Element&x ) { // 沿著從最大結(jié)點i // 到根結(jié)點的路徑檢查最大結(jié)點，將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é)點i},JYP,75,函數(shù)VerifyMin與VerifyMax類似，所不同的是，前者從最小結(jié)點i開始，沿著從結(jié)點i到根的路徑檢查最小結(jié)點，將元素x插入正確位置。 分析：由于n個元素的最小最大堆有O(log n)層，成員函數(shù)Insert的時間復(fù)雜性是O(log n)。,J