day5基本數(shù)據(jù)結(jié)構(gòu)-曹利國-noip培訓(xùn)

長沙市一中曹利國NOIp數(shù)據(jù)結(jié)構(gòu)1.棧(Stack)及其應(yīng)用1。1棧的概念只允許在一端插入和刪除的表允許插入和刪除的一端稱為棧頂

(top)，另一端稱為棧底(bottom)特點后進先出(LIFO)進棧例如

出棧例如棧的根本操作1、初始化2、進棧PUSH3、出棧POP4、取棧頂元素GetTop5、判棧是否非空1。2棧的應(yīng)用NOIP2005試題：《等價表達式》問題描述明明進了中學(xué)之后，學(xué)到了代數(shù)表達式。有一天，他碰到一個很麻煩的選擇題。這個題目的題干中首先給出了一個代數(shù)表達式，然后列出了假設(shè)干選項，每個選項也是一個代數(shù)表達式，題目的要求是判斷選項中哪些代數(shù)表達式是和題干中的表達式等價的。這個題目手算很麻煩，因為明明對計算機編程很感興趣，所以他想是不是可以用計算機來解決這個問題。假設(shè)你是明明，能完成這個任務(wù)嗎？這個選擇題中的每個表達式都滿足下面的性質(zhì)：表達式只可能包含一個變量‘a(chǎn)’。表達式中出現(xiàn)的數(shù)都是正整數(shù)，而且都小于10000。表達式中可以包括四種運算‘+’〔加〕，‘-’〔減〕，‘*’〔乘〕，‘^’〔乘冪〕，以及小括號‘(’，‘)’。小括號的優(yōu)先級最高，其次是‘^’，然后是‘*’，最后是‘+’和‘-’?！?’和‘-’的優(yōu)先級是相同的。相同優(yōu)先級的運算從左到右進行?！沧⒁猓哼\算符‘+’，‘-’，‘*’，‘^’以及小括號‘(’，‘)’都是英文字符〕冪指數(shù)只可能是1到10之間的正整數(shù)〔包括1和10〕。表達式內(nèi)部，頭部或者尾部都可能有一些多余的空格。下面是一些合理的表達式的例子：((a^1)^2)^3，a*a+a-a，((a+a))，9999+(a-a)*a，1+(a-1)^3，1^10^9……輸入文件輸入文件equal.in的第一行給出的是題干中的表達式。第二行是一個整數(shù)n〔2<=n<=26〕，表示選項的個數(shù)。后面n行，每行包括一個選項中的表達式。這n個選項的標(biāo)號分別是A，B，C，D……輸入中的表達式的長度都不超過50個字符，而且保證選項中總有表達式和題干中的表達式是等價的。輸出文件輸出文件equal.out包括一行，這一行包括一系列選項的標(biāo)號，表示哪些選項是和題干中的表達式等價的。選項的標(biāo)號按照字母順序排列，而且之間沒有空格。樣例輸入(a+1)^23(a-1)^2+4*aa+1+aa^2+2*a*1+1^2+10-10+a-a樣例輸出AC關(guān)鍵：如何判斷表達式等價？方法1：展開表達式直接比對，顯然不可取。方法2：求表達式的值，比對表達式的值。但對于個體值有可能出現(xiàn)等價的表達式其值相等。引入隨機化思想，隨機產(chǎn)生幾個a的值，當(dāng)對每個隨機產(chǎn)生的a值表達式值都相等時視為表達式等價。問題轉(zhuǎn)換：如何求表達式的值。利用棧實現(xiàn)表達式計算。對表達式運算符定義運算優(yōu)先級。算法描述：設(shè)立運算符棧和操作數(shù)棧，逐詞讀入表達式，并處理：1、假設(shè)讀入為操作數(shù)，那么入棧；2、假設(shè)讀入為運算符，那么與棧頂運算符相比較：〔1〕假設(shè)棧頂運算符優(yōu)先級高于或等讀入運算符，反復(fù)執(zhí)行以下操作，直到棧頂運算符優(yōu)先級不高于讀入運算符：彈出運算符，彈出兩個操作數(shù)，計算并將結(jié)果入操作數(shù)棧；〔2〕假設(shè)棧頂運算符優(yōu)先級低于讀入運算符，那么將讀入運算符入棧；3、假設(shè)遇到結(jié)束運算符，那么計算結(jié)束。4、檢查棧狀態(tài)，得到計算結(jié)果。程序表達：閱讀equal.pas表達式：3×(5–2)+7@opndoptr3×(5–23+975–2=33×3=97+9=16結(jié)果便是16！16使用棧進行算術(shù)表達式求值2.1隊列(

Queue)的概念定義隊列是只允許在一端刪除，在另一端插入的順序表允許刪除的一端叫做隊頭(front)，允許插入的一端叫做隊尾(rear)。特性先進先出(FIFO,FirstInFirstOut)2.隊(Queue)及其應(yīng)用隊列的根本操作1、構(gòu)造一個隊列2、進隊操作-----將新元素插入隊尾3、出隊操作------隊列頭元素出隊4、取隊列頭元素5、判定隊列是否為空隊列的存儲結(jié)構(gòu)順序存儲------循環(huán)隊列鏈?zhǔn)酱鎯?-----鏈隊思考:為什么要構(gòu)造循環(huán)隊列?

進隊時隊尾指針rear=rear+1，將新元素按rear指示位置參加。出隊時隊頭指針front=front+1，再將下標(biāo)為front的元素取出。思考：上圖中，元素再進隊，將如何？出現(xiàn)“假上溢”現(xiàn)象

解決方法:將存儲數(shù)據(jù)元素的一維數(shù)組看成是頭尾相接的循環(huán)結(jié)構(gòu)即循環(huán)隊列循環(huán)隊列的進隊和出隊隊頭指針:front=(front+1)%maxSize;隊尾指針:rear=(rear+1)%maxSize;隊列初始化：front=rear=0;循環(huán)隊列的隊空隊滿問題為了方便起見，約定：初始化建空隊時，令front=rear=0,

當(dāng)隊空時：front==rear

當(dāng)隊滿時：front==rear亦成立

因此，只憑等式front=rear

無法判斷隊空還是隊滿。

有三種方法處理上述問題：

①浪費一個單元。當(dāng)使用MaxSize-1個單元時即認為是隊滿,此時

(rear+1)%MaxSize==front②設(shè)置一個布爾變量flag。當(dāng)flag==flase時為空，當(dāng)flag==true時為滿。③使用一個計數(shù)器記錄隊列中元素的個數(shù)。如num，當(dāng)num==0時隊空，當(dāng)num==MaxSize時隊滿。隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)問題1、集合刪數(shù)問題描述：一個集合有如下元素：1是集合元素；假設(shè)P是集合的元素，那么2*P+1，4*P+5也是集合的元素，取出此集合中最小的K個元素，按從小到大的順序組合成一個多位數(shù)，現(xiàn)要求從中刪除M個數(shù)位上的數(shù)字，使得剩下的數(shù)字最大，編程輸出刪除前和刪除后的多位數(shù)字。注：不存在所有數(shù)被刪除的情況`輸入格式：輸入的僅一行，K，M的值，K，M均小于等于30000。輸出格式：輸出為兩行，第一行為刪除前的數(shù)字，第二行為刪除后的數(shù)字。樣例輸入：54樣例輸出：137915952.2隊列的應(yīng)用問題簡述

問題由兩個子問題組成：1、構(gòu)造一個多位數(shù)：1是集合元素；假設(shè)P是集合的元素，那么2*P+1，4*P+5也是集合的元素，取出此集合中最小的K個元素，按從小到大的順序組合成一個多位數(shù)2、從多位數(shù)中刪除M個數(shù)位上的數(shù)字，使得剩下的數(shù)字最大

1、分析集合元素特點：假設(shè)P是集合的元素，那么2*P+1，4*P+5也是集合的元素，即生成集合元素的函數(shù)是單調(diào)遞增的。將2*P+1與4*P+5產(chǎn)生的元素分成兩個集合，每次取兩集合中最小的一個元素，顯然只需比較兩集合中當(dāng)前未被取走的第一個元素。引入指針概念：設(shè)TOP1指向2*P+1當(dāng)前未被取走的第一個元素，TOP2指向4*P+5當(dāng)前未被取走的第一個元素。關(guān)鍵詞：隊比較TOP1，TOP2指向的元素，取最小的一個，將取走元素隊列的指針指向下一個元素。例：生成5元素的集合數(shù)。1379152*P+1：3715194*P+5：9173341a:=1; b:=1; p[1]:=1; Fori:=2tondo begin x:=p[a]*2+1; y:=p[b]*4+5; ifx<=ythenbegin ifx=ytheninc(b); p[i]:=x; inc(a); end else begin p[i]:=y; inc(b); end; end;2、分析〔1〕貪心：高位越大越好;〔2〕因為數(shù)據(jù)很大,邊取數(shù)字邊處理，處理原那么是當(dāng)前數(shù)留下，還是取代前面數(shù)留下。如：13751967留下2位數(shù)137519697

〔3〕當(dāng)前數(shù)能否作為剩余序列的最高位？能，那么刪除前面比自己小的數(shù)。當(dāng)前數(shù)是否取代前面留下的數(shù)的條件為：①當(dāng)當(dāng)前數(shù)大于前面數(shù)時;②總體保存位數(shù)〔末刪除數(shù)個數(shù)+末讀入數(shù)個數(shù)〕大等于需留下的位數(shù)時；刪除前面保存的數(shù)設(shè)原數(shù)長度N，刪除D位數(shù)D:=N-D;{留下數(shù)位數(shù)}Stack[0]:=Chr(58);{字符9}Top:=1;Fori:=1toNdoBegin 取出第i位數(shù)字C While(C>Stack[Top-1])And(Top+N-i>D)doDec(Top);{如果當(dāng)前位數(shù)字大于前面數(shù)字且已保存數(shù)位個數(shù)與剩余數(shù)個數(shù)和大于需留下數(shù)位的個數(shù)，那么刪除前面的數(shù)字} Stack[Top]:=C; Inc(Top)End;Fori:=1toDdoWrite(Stack[i])算法偽代碼：問題2:合并果子(NOIP2004提高組)【問題描述】在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和?？梢钥闯?，所有的果子經(jīng)過n-1次合并之后，就只剩下一堆了。多多在合并果子時總共消耗的體力等于每次合并所耗體力之和。因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節(jié)省體力。假定每個果子重量都為1，并且果子的種類數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計出合并的次序方案，使多多消耗的體力最少，并輸出這個最小的體力消耗值。例如有3種果子，數(shù)目依次為1，2，9。可以先將1、2堆合并，新堆數(shù)目為3，消耗體力為3。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為12，消耗體力為12。所以多多總共消耗體力=3+12=15?？梢宰C明15為最小的體力消耗值?！据斎敫袷健枯斎氚▋尚校谝恍惺且粋€整數(shù)n(1<＝n<=10000)，表示果子的種類數(shù)。第二行包含n個整數(shù)，用空格分隔，第i個整數(shù)ai(1<＝ai<=20000)是第i種果子的數(shù)目?！据敵龈袷健枯敵霭ㄒ恍校@一行只包含一個整數(shù)，也就是最小的體力消耗值。輸入數(shù)據(jù)保證這個值小于2^31。【輸入樣例】3129【輸出樣例】15分析：很明顯，這道題是一道貪心的題目，可以證明，每次取最小的兩堆合并會使得最后的體力值最小。那么，這道題的問題就在于怎么找最小的兩堆果子了。樸素方法：排序，合并，插入。

我們注意到，每次合并完果子會刪掉兩堆，并添加一堆新的，如果采用線性表，時間復(fù)雜度將高達O〔N^2〕，對于N<=20000是不夠的。所以，我們考慮使用最小堆優(yōu)化。算法：建立空堆；讀入數(shù)據(jù)，建立最小堆；每次取兩個堆頂元素合并，并插入合并后的數(shù)，總共合并n-1次。FRUIT.PAS方法2：隊列樸素方法問題是時間浪費在每次的排序中，能否根據(jù)此題特點進行改進呢？構(gòu)造兩個隊列old和new，old用來存儲原有的果子堆數(shù)，new用來存儲每次合并得到的新果子堆數(shù)，每次合并后累加消耗的體力即可。要想得到最小的體力消耗值，那么old要按增序排列，而NEW也是增序排列，很明顯每次合并時候是在old和new的首部，取兩個最小值，合并之后插入到new尾部。此種方法的好處是只需對old進行一次排序，之后就不再需要排序，而是直接在old和new的首部取值就好了。

由于old的元素是從a[]中復(fù)制過來的，所以我們可以對其進行插入排序，這樣排序的時間復(fù)雜度是O(N*logN)；但如果我們注意觀察的話，可以發(fā)現(xiàn)輸入數(shù)據(jù)1<＝ai<=20000，我們完全可以使用計數(shù)排序，以空間換時間，使得時間復(fù)雜度降低到O(N)?！瞗ruit1.pas〕問題3WINDOWS選自PKU2823問題描述：給你一個長度為N的數(shù)組，一個長為K的滑動的窗體從最左移至最右端，你只能見到窗口的K個數(shù)，每次窗體向右移動一位，如下表：你的任務(wù)是找出窗口在各位置時的maxvalue,minvalue.輸入格式：第1行n,k,第2行為長度為n的數(shù)組輸出格式：2行，第1行每個位置的minvalue,第2行每個位置的maxvalue樣例：window.in8313-1-35367window.out-1-3-3-333335567數(shù)據(jù)范圍：20%：n<=500;50%:n<=100000;100%:n<=1000000;分析：方法1：樸素算法枚舉WINDOWS左端位置，求得每個區(qū)間長度為K的數(shù)中的最大值和最小值。效率為O(n*k)。顯然，在n次的k次中有許多的重復(fù)工作。分析數(shù)據(jù)：以求區(qū)間最小值為例。[13-1]-35367q:{-1},最小值為-11[3-1-3]5367q:{-3}新參加數(shù)小于-1,顯然-1無用了，最小數(shù)為-313[-1-35]367q:{-3，5}新參加數(shù)大于-3，保存，最小數(shù)為-313-1[-353]67q:{-3，3}新參加數(shù)小于5,顯然5無用了，最小數(shù)為-313-1-3[536]7q:{3，6}新參加數(shù)大于3，保存，但-3已移出區(qū)間，刪除，最小數(shù)為313-1-35[367]q:{3，6，7}新參加數(shù)大于6，保存，最小數(shù)為3

總結(jié)操作過程：把q序列看成一個隊列，每次從尾部參加一個新的數(shù)，如果它比隊尾還小，那么隊尾的這個數(shù)不可能成為之后任何一個區(qū)間的最小值，刪除隊尾元素后入隊，如果它比隊尾元素大，入隊。同時，當(dāng)隊頭留在隊中的次數(shù)超過k時隊頭數(shù)據(jù)出隊，因為它不在下一個區(qū)間內(nèi)了。這樣，區(qū)間的最小值總是當(dāng)前隊列的隊頭。依此類推，即可得解。q序列為單調(diào)隊列。它首先是一個隊列，每一個時刻，隊列元素值是單調(diào)的，同時支持入隊和出隊，但是出隊有從隊頭出和隊尾出兩種。方法2：單調(diào)隊列，每個數(shù)都進隊、出隊一次，算法效率為O(N)。

procedurework; {設(shè)原始數(shù)據(jù)存入q[i]中}Vari,top,tail:longint;

begin top:=1;tail:=1; queue[top]:=1;//隊頭指向q[i]中第一個數(shù)

fori:=2tokdo//前k個數(shù)的初始隊列

begin while(top<=tail)and(q[queue[tail]]>=q[i])dodec(tail);//隊尾元素大于當(dāng)前元素，出隊

inc(tail); //當(dāng)前元素入隊

queue[tail]:=i; end;

單調(diào)隊列程序框架〔以最小值為例〕min[1]:=q[queue[top]];//第1窗口最小值

fori:=2ton-k+1do//窗口左端位置

beginifqueue[top]<itheninc(top);//如果隊頭指向位置滑出窗口左端，隊頭出隊

while(top<=tail)and(q[queue[tail]]>=q[i+k-1])dodec(tail); );//隊尾元素大于當(dāng)前窗口右端元素，出隊

inc(tail); queue[tail]:=i+k-1;//當(dāng)前窗口右端元素入隊

min[i]:=q[queue[top]];//取當(dāng)前窗口最小值

end; end;

最長詞鏈一個詞是由至少1個，至多75個小寫英文字母(a..z)組成。當(dāng)在一張由一個或多個詞組成的表中，每一個詞〔除第一個外〕都能由在其前一個詞的詞尾添加一個或多個字母而得到，那么稱此表為一個鏈。例如：iinintinteger為一個含4個詞的詞鏈。而表inputinteger不是詞鏈。注意：所有含有一個詞的表都是鏈。給定一個詞按字典順序由小到大排列的表，找出表中的最長詞鏈。表的大小最大到達2M。

分析這道題目，雖然測試數(shù)據(jù)大得驚人，但是難度卻并不大。主要的是要把握住表的特點：詞按字典順序由小到大的排列，因此表中的相鄰的兩個詞語之間的關(guān)系只有兩種——屬于同一詞鏈或不屬于同一詞鏈，假設(shè)它們不屬于同一詞鏈，那么后一個單詞所在的詞鏈，除這一個單詞外的鏈〔這個鏈可能為空〕必定為它在表中的前一個單詞的詞鏈的前綴。舉例：i,in,int,integer,inter在上面這個例子當(dāng)中，最后一個單詞inter所組成的詞鏈為i→in→int→inter,在這個鏈中，除inter的外的鏈為i→in→int。而它的前一個單詞integer組成的詞鏈為i→in→int→integer。其中i→in→int就是i→in→int→integer中的前綴。因此，可以利用堆棧這種數(shù)據(jù)結(jié)構(gòu)來解決這一問題。算法框架constMaxLen=75;(單詞的最大長度)typeTwork=objectTop，Max：Integer；〔Top表示堆棧中元素的個數(shù)，Max表示最大詞鏈的長度〕；Word,Ans：array[1..MaxLen]ofString[MaxLen];〔棧中每一層記錄的詞〕procedureWork；end；procedureTwork.Work;1.Top←0；Max←0；2.Readln(St);讀入一個詞3.WhileSt<>’.’DoWhile(Top>0)and(Pos(Word[Top],St)<>1doTop←Top-1;｛查找堆棧中的詞判斷哪些詞語能夠繼續(xù)和目前的這個詞構(gòu)成詞鏈｝5.Top←Top+1;Word[Top]←St;6.IfTop>Maxthen7.beginMax←Top;Ans←Word;end;更新Max的值8.Readln(St);讀入一個詞9.輸出二叉樹二叉樹就是最多只有兩個子節(jié)點的樹所有葉節(jié)點深度相同的二叉樹為滿二叉樹深度為k且有n個節(jié)點的二叉樹，當(dāng)其每一個節(jié)點都與深度為k的滿二叉樹中編號從1至n的節(jié)點一一對應(yīng)時，稱之為完全二叉樹多叉樹轉(zhuǎn)二叉樹用二叉樹表示一棵樹要比多叉樹簡單些，而且多叉樹都可以轉(zhuǎn)換成唯一的二叉樹。對于多叉樹中的每個節(jié)點，可以用兩個指針分別指向它的第一個子節(jié)點和下一個相鄰節(jié)點。多叉轉(zhuǎn)二叉的例子在以下圖中，每個節(jié)點的左子節(jié)點為它原來的第一個子節(jié)點，右子節(jié)點為它的第一個兄弟節(jié)點7 4 8 1 4 9 3 1 6 5 2 7 4 8 1 4 9 3 1 6 5 2 7 4 8 1 4 9 3 1 6 5 2 幾類特殊的樹形結(jié)構(gòu)二叉和N叉哈夫曼樹堆二叉搜索〔排序〕樹并查集哈夫曼樹哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長度最短的二叉樹。所謂樹的帶權(quán)路徑長度，就是樹中所有的葉結(jié)點的權(quán)值乘上其到根結(jié)點的路徑長度〔假設(shè)根結(jié)點為0層，葉結(jié)點到根結(jié)點的路徑長度為葉結(jié)點的層數(shù)〕。樹的帶權(quán)路徑長度記為WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N個權(quán)值Wi(i=1,2,...n)構(gòu)成一棵有N個葉結(jié)點的二叉樹，相應(yīng)的葉結(jié)點的路徑長度為Li(i=1,2,...n)。可以證明哈夫曼樹的WPL是最小的。哈夫曼樹然而怎樣構(gòu)造一棵哈夫曼樹呢？最具有一般規(guī)律的構(gòu)造方法就是哈夫曼算法。一般的數(shù)據(jù)結(jié)構(gòu)的書中都可以找到其描述：一、對給定的n個權(quán)值{W1,W2,W3,...,Wi,...,Wn}構(gòu)成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉樹Ti中只有一個權(quán)值為Wi的根結(jié)點，它的左右子樹均為空?！矠榉奖阍谟嬎銠C上實現(xiàn)算法，一般還要求以Ti的權(quán)值Wi的升序排列?！扯?、在F中選取兩棵根結(jié)點權(quán)值最小的樹作為新構(gòu)造的二叉樹的左右子樹，新二叉樹的根結(jié)點的權(quán)值為其左右子樹的根結(jié)點的權(quán)值之和。三、從F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列參加到集合F中。四、重復(fù)二和三兩步，直到集合F中只有一棵二叉樹為止。構(gòu)造二叉哈夫曼樹選取值最小的兩個根節(jié)點a和b。創(chuàng)立一個新節(jié)點，其權(quán)值就是a、b的權(quán)值之和，左右子樹分別為a、b這兩個節(jié)點。重復(fù)1步驟，直至只有一個根節(jié)點〔即所有節(jié)點都在同一棵樹中〕。1249108371915344910819哈夫曼樹應(yīng)用題目闡述：

以Ｎ進制編碼方式對一個英文字串中的字符進行編碼，每個不同的字符其編碼不同．使得由新的編碼替代原串后總碼長最小，且輸入０，１，２，．．．，Ｎ－１構(gòu)成的數(shù)字串后，依照該編碼方式可以正確的對譯出唯一的英文原串．如：Ｎ＝３英文原串為ＡＢＢＣＢＡＤＤＡＣＥ其對應(yīng)的一種編碼方式為Ａ：００Ｂ：０１Ｃ：０２０Ｄ：０２１Ｅ：０２２原串對譯后的編碼為０００１０１０２００１０００２１０２１０００２００２２其碼長為２７假設(shè)輸入編碼串０１０２００２２００那么對應(yīng)的英文原串為ＢＣＥＡ假設(shè)英文原串中的字符存放于字符集Ｓ中，‖Ｓ‖＝Ｘ，每個字符在字串中出現(xiàn)的概率為Ｗ［ｉ］，Ｌ［ｉ］為字符ｉ的編碼長．依題意得，對Ｓ集合中的不同字符進行Ｎ進制編碼后要求１〕新字串的碼長最短ＷＰＬ＝∑Ｗ［ｉ］＊Ｌ［ｉ］ 〔ｉ∈１．．Ｘ〕使得在ＷＰＬ是所有編碼方式中的最小值２〕編碼無二義性任意一字符編碼都不為其它字符編碼的前綴此題以哈夫曼樹來解答是非常適宜的．Ｎ為此哈夫曼樹的分叉數(shù)，Ｓ字符集里的元素即為此Ｎ叉哈夫曼樹的葉子，概率Ｗ［ｉ］即為葉子結(jié)點的權(quán)重，從根結(jié)點到各葉子結(jié)點的路徑長即為該葉子結(jié)點的編碼長Ｌ［ｉ］．由哈夫曼樹的思想可以知道哈夫曼樹的建立是一步到位的貪心法，即權(quán)重越大的結(jié)點越靠近該樹的根，這樣，出現(xiàn)頻率越大的字符其編碼就越短．哈夫曼樹應(yīng)用但具體應(yīng)該怎樣建立起此Ｎ叉哈夫曼樹呢？2叉哈夫曼樹已經(jīng)講過，我們來看3叉。Ｎ＝３時又是怎樣一種情況呢？設(shè)Ｓ＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ｝Ｗ＝［７，４，２，５，３｝那么按權(quán)重排序可得Ｓ＝｛Ａ，Ｄ，Ｂ，Ｅ，Ｃ｝Ｗ＝［７，５，４，３，２］哈夫曼樹應(yīng)用那么此哈夫曼樹的樹形應(yīng)為怎樣呢？是以下的左圖，還是右圖，或是兩者均不是

AＡ

D

BE

CＤ

Ｂ

ＥＣ哈夫曼樹應(yīng)用顯然，要帶權(quán)路徑長ＷＰＬ最短，那么，此樹的高度就應(yīng)盡可能的小，由此可知將此樹建成飽滿Ｎ叉樹是最合理的，于是我們盡量使樹每一層都為Ｎ個分枝．這樣，我們得到了初步算法。哈夫曼樹應(yīng)用類似2叉哈夫曼樹，我們把每次取2個改成每次取3個，對于Ｓ＝｛Ａ，Ｄ，Ｂ，Ｅ，Ｃ｝Ｗ＝［７，５，４，３，２］我們進行如下操作：哈夫曼樹應(yīng)用哈夫曼樹應(yīng)用75432921finish75432921哈夫曼樹應(yīng)用ADBEC以０．．Ｎ－１依次標(biāo)記每個根結(jié)點的Ｎ個分枝，那么可以得到每個字符相對應(yīng)的編碼：Ａ:0Ｂ:20Ｃ:22Ｄ:1Ｅ:21思考：我們發(fā)現(xiàn)對于這種情況恰巧每層均為Ｎ個分枝，但事實上并非所有的Ｎ叉哈夫曼樹都可得到每層Ｎ個分枝．例于當(dāng)Ｎ＝３，‖Ｓ‖＝６時就不可能構(gòu)成一棵每層都為三個分枝的三叉樹．如何來處理這種情況呢？哈夫曼樹應(yīng)用最簡單的處理方式就是添加假設(shè)干出現(xiàn)概率為０的空字符填補在Ｎ叉樹的最下一層，這些權(quán)為０的虛結(jié)點并無實際意義但卻非常方全便于這棵Ｎ叉樹的建立．空字符的添加個數(shù)ａｄｄ的計算如下：Ｙ＝‖Ｓ‖ｍｏｄ〔ｎ－１〕ａｄｄ＝０〔Ｙ＝１〕ａｄｄ＝１〔Ｙ＝０〕ａｄｄ＝Ｎ－Ｙ〔Ｙ＞１〕虛結(jié)點的參加使得權(quán)重最小的Ｎ－ａｄｄ個字符構(gòu)成了距根結(jié)點最遠的分枝，使其它字符構(gòu)成的Ｎ叉樹保持了飽滿的Ｎ叉結(jié)構(gòu)．哈夫曼樹應(yīng)用例：Ｎ＝３Ｓ＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ｝Ｗ＝［１，２，３，４，５，６｝哈夫曼樹應(yīng)用那么ｙ：＝６ｍｏｄ〔３－１〕＝０->ａｄｄ＝１

于是構(gòu)成Ｎ叉樹如下：

為虛結(jié)點

ＦＥ

ＤＣ

ＢＡ

ＷＰＬ＝１＊６＋１＊５＋２＊４＋２＊３＋３＊２＋３＊１＋３＊０＝３３對應(yīng)編碼為：Ａ：２２１Ｂ：２２０Ｃ：２１Ｄ：２０Ｅ：１Ｆ：０由此可知，對于N叉二叉樹我們也可以類似處理。哈夫曼樹應(yīng)用堆堆是一種特殊的二叉樹它滿足{V(左孩子)<V(根)>V(右孩子)}或{V(左孩子)>V(根)<V(右孩子)}堆我們?nèi)绾谓ǘ涯?如果需要O(N)去添加一個元素，這就沒有意義了，所以，我們要用O(log2(N))把一個元素加進去。這樣，我們就可以在O(NlogN)的時間內(nèi)建好堆。堆(以小根堆為例)3建堆開始……65752313877152163613建堆完畢……算法描述〔建堆〕procedurebuild;fori:=1tondoread(x);push(x);endf;endp;begininc(num);a[num]:=x;j:=x;i:=num;whilea[idiv2]>a[i]doswap(i,idiv2);i:=idiv2;endw;end;堆——選擇與維出堆頂節(jié)點71273728833868一、取出二、調(diào)整算法描述〔堆排序〕proceduresort;build;fori:=1tondowriteln(a[1]);delete(1);endp;類似于push,不過push是把小元素向上換，delete是把最小的刪掉后，把最后一個元素放上來，這樣就變成了把一個大元素向下放的過程，具體方法請自己思考。堆排序算法PROCshift(varr:listtype;k,m:integer);i:=k.j:=2*I;x:=r[k].key;finish:=falset:=r[k];while(j<=m)andnotfinishdo[if(j<m)andr[j].key>r[j+1].key)thenj:=j+1;Ifx<=r[j].keythenfinish:=trueElse[r[i]:=r[j];i:=j;j:=2*I]]r[i]:=tendPPROCheapsort(varr:listtype);Fori:=[n/2]downto1shift(r,I,n);Fori:=ndownto2do[r[1]與r[i]交換;shift(r,1,i-1)]endP用堆優(yōu)化dijstra算法例題：最小序列問題。給定一個N×N〔N<=100〕的正整數(shù)矩陣。需要在矩陣中尋找一條從起始位置到終止位置的路徑(可沿上下左右四個方向)，并且要求路徑中經(jīng)過的所有數(shù)字，其相鄰數(shù)字之差的絕對值之和最小。例題分析這道題的根本算法很簡單，只要用Dijkstra算法求出從起始位置到終止位置的最短路徑即可。但這當(dāng)中存在一個很大的問題：N<=100。這就是說圖中點的數(shù)目可能多達10000個。此時復(fù)雜度為O(n2)的Dijkstra算法就顯得有些力不從心了。例題分析我們繼續(xù)對算法進行分析。由于Dijstra算法通常采用的是線性的數(shù)組結(jié)構(gòu)，所以當(dāng)我們每次尋找下一條最短路徑時，有兩步需要進行：〔1〕找出一個不在最短路徑起點集合內(nèi)，并且到終點距離最短的頂點i。這一步的復(fù)雜度顯然為O(n)。〔2〕修改從與i相鄰的頂點到終點的路徑長度。由于最多只有4個點(四個方向)與i相鄰，所以這一步的復(fù)雜度為O(1)即常數(shù)例題分析這兩步中，雖然第二步最多只改變了到4個點的路徑長度，但是第一步卻還是需要枚舉所有的數(shù)組元素，這顯然很浪費時間。出于對第一步進行改進的考慮，我們可以想到樹結(jié)構(gòu)中二叉堆的結(jié)構(gòu)。堆結(jié)構(gòu)的優(yōu)點是：根結(jié)點就是最優(yōu)的結(jié)點，并且改變堆中某個結(jié)點的值以后，只需O(log2n)的復(fù)雜度就可以完成堆化的過程(可分為從二叉樹中自下而上和自上而下兩種堆化方法，并且復(fù)雜度都一樣)，使堆的結(jié)構(gòu)發(fā)生改變后，通過堆化仍然能夠保存堆的性質(zhì)。如果我們采用二叉堆的結(jié)構(gòu)存儲距離，第一步就只需將根結(jié)點取出，并且用堆中的另一結(jié)點代替后進行一次自上而下的堆化。因而第一步的復(fù)雜度可降為O(log2n)。但是，此時的堆結(jié)構(gòu)在進行第二步時暴露了很大的缺點：無法預(yù)知i點的相鄰點在堆中的位置。如果我們用對堆進行遍歷來尋找i的相鄰點，第二步的復(fù)雜度又成為了O(n)。例題分析我們從這兩種數(shù)據(jù)結(jié)構(gòu)中不難發(fā)現(xiàn)這樣規(guī)律：采用線性結(jié)構(gòu)的數(shù)組，易于進行第二步；采用樹結(jié)構(gòu)的二叉堆，做第一步時效果比較理想。那么，我們是否可以將這兩種數(shù)據(jù)結(jié)構(gòu)進行結(jié)合，取長補短呢？我們可以采用映射的方法，將線性結(jié)構(gòu)中的元素與堆中間的結(jié)點一一對應(yīng)起來，假設(shè)線性的數(shù)組中的元素發(fā)生變化，堆中相應(yīng)的結(jié)點也接著變化，堆中的結(jié)點發(fā)生變化，數(shù)組中相應(yīng)的元素也跟著變化。將兩種結(jié)構(gòu)進行結(jié)合后，無論是第一步還是第二步，我們都不需對所有元素進行遍歷，只需進行常數(shù)次復(fù)雜度為O(log2n)的堆化操作。這樣，整個時間復(fù)雜度就成為了O(nlog2n)，算法效率無疑得到了很大提高。二叉搜索樹二叉查找樹〔BinarySearchTree〕，或者是一棵空樹，或者是具有以下性質(zhì)的二叉樹：

假設(shè)它的左子樹不空，那么左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；

假設(shè)它的右子樹不空，那么右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；

它的左、右子樹也分別為二叉排序樹。

二叉搜索樹根本操作1、查找元素2、構(gòu)造3、刪除二叉排序樹用于動態(tài)查找12623381825195297查找7找到了!查找相信大家都想得到。根據(jù)性質(zhì)只要每次查找時，符合那么退出，否那么就在左孩子〔查找值小于當(dāng)前值〕或右孩子〔查找值大于當(dāng)前值〕中繼續(xù)查找。二叉搜索樹在二叉搜索樹上插入一個新元素，首先應(yīng)搜索新元素的插入位置。搜索插入位置要求在從根結(jié)點往下搜索的過程中，要記錄下當(dāng)前元素的雙親結(jié)點，并以指針q指示。如果在搜索中遇到相同關(guān)鍵字值的元素，那么說明有重復(fù)元素，那么顯示“Duplicate”信息。搜索到達空子樹時結(jié)束，表示二叉搜索樹中不包含待插入的新元素x，此時，指針q指向新元素插入后的雙親結(jié)點。二叉搜索樹的插入算法構(gòu)造一個新結(jié)點用以存放新元素x，設(shè)新結(jié)點由指針r指示。如果原二叉搜索樹是空樹，那么新結(jié)點*r成為新二叉搜索樹的根；否那么新結(jié)點*r將成為結(jié)點*q的孩子。如果新元素x的關(guān)鍵字值小于q結(jié)點的關(guān)鍵字值，那么*r將成為*q的左孩子，否那么成為其右孩子。二叉搜索樹的插入二叉搜索樹的插入運算(X.Key=43)(a)p=Bt->Root;(b)q=p;p=p->Rchild;(c)q=p;p=p->Rchild;(d)r=NewNode2(x);q->Rchild=r圖8－3二叉搜索樹的構(gòu)造過程

(a)空樹；(b)插入28；(c)插入21；(d)插入25；(e)插入36；(f)插入33；(g)插入43在二叉搜索樹上刪除一個結(jié)點也很方便。首先應(yīng)搜索被刪除的元素。搜索刪除元素的方法與插入元素的做法類似，要求在從根結(jié)點往下搜索的過程中，記錄下當(dāng)前元素的雙親結(jié)點，并用指針q指示。如果不存在該元素，那么顯示“Noelementwithkey”信息。如果存在待刪除的結(jié)點，設(shè)其由指針p指示，那么刪除結(jié)點*p的操作可分下面三種情況討論。二叉搜索樹的刪除1〕沒有兒子，即為葉節(jié)點。直接把父節(jié)點的對應(yīng)兒子指針設(shè)為NULL，刪除兒子節(jié)點就OK了。

2〕只有一個兒子。那么把父節(jié)點的相應(yīng)兒子指針指向兒子的獨生子，刪除兒子節(jié)點也OK了。

二叉搜索樹的刪除二叉搜索樹的刪除3〕有兩個兒子。這是最麻煩的情況，因為刪除節(jié)點之后，還要保證滿足搜索二叉樹的結(jié)構(gòu)。其實也比較容易，我們可以選擇左兒子中的最大元素或者右兒子中的最小元素放到待刪除節(jié)點的位置，就可以保證結(jié)構(gòu)的不變。當(dāng)然，要記得調(diào)整子樹，畢竟又出現(xiàn)了節(jié)點刪除。這里選擇左兒子的最大元素，將它放到待刪節(jié)點的位置。左兒子的最大元素其實很好找，只要順著左兒子不斷的去搜索右子樹就可以了，直到找到一個沒有右子樹的節(jié)點。那就是最大的了。103158111583172Delete(5)Delete(2)Delete(15)12二叉搜索樹的刪除二叉搜索樹注意：二叉搜索樹操作的時間復(fù)雜度最好情況下〔如無序數(shù)據(jù)〕是O(NlogN)，但是如果是有序的，時間復(fù)雜度有可能到達N^2，為了解決這個問題，人們提出了不同的平衡方法。如Splay，AVL。二叉搜索樹的應(yīng)用試將一段英文中出現(xiàn)的單詞按詞典的順序打印出來，同時應(yīng)注明每個單詞在該段文章中出現(xiàn)的次數(shù)。例題分析將一段英文中的單詞按詞典順序打印的過程，就是由一個無序序列構(gòu)造有序序列的過程，這個過程可以通過構(gòu)造二叉排序樹實現(xiàn)。

設(shè)A={a1,a2,a3,...,an}為一組元素的集合，那么按以下規(guī)那么生成的二叉樹就是一棵二叉排序樹：

〔1〕令a1為二叉樹的根；

〔2〕假設(shè)a2<a1，那么令a2為a1的左子樹的根結(jié)點，否那么，令a2為a1的右子樹的根結(jié)點；

〔3〕a3,a4,...,an遞歸重復(fù)步驟２。

例題分析假設(shè)輸入英文段落為：

Everyoneroundyoucanhearyouwhenyousperk

按算法構(gòu)造的二叉排序樹如圖示。

二叉搜索樹的應(yīng)用例題：尋找同名的學(xué)生。

某大學(xué)有三個系，每個系的學(xué)生名字單獨放在一個文本文件中，每個系的學(xué)生人數(shù)不超過1000人。請編一程序，在這所大學(xué)中尋找這樣的名字，用該名字的人數(shù)恰為M(M>0)。注意：同一個系或系與系之間都有可能出現(xiàn)同名現(xiàn)象。

[輸入格式]

從鍵盤依次讀入三個文本文件的文件名和M的值(每項占一行)。在每個文本文件中，一個學(xué)生的名字占一行(左邊無空格)，姓名由3至10個大寫英文字母組成，中間無空格。

[輸出格式]

在屏幕上輸出符合條件的名字，假設(shè)有多個名字符合條件，須按字典順序列出，每個名字占一行(左邊無空格)。

[輸入輸出舉例]假設(shè)有三個文件如下：math.txtcomputer.txthistory.txtWANGLINWANGQINGWANGLINZHANGPINLIHONGLINLINGZHAOPENGZHAOPINGWANGFANWANGFANZHAOPENGZHAOPINLIUQINGWANGLINZHAOPENG

輸入 輸出math.txtWANGLINcomputer.txtZHAOPENGhistory.txt3二叉搜索樹的應(yīng)用例題：尋找同名的學(xué)生。

[輸入格式]

從鍵盤依次讀入三個文本文件的文件名和M的值(每項占一行)。在每個文本文件中，一個學(xué)生的名字占一行(左邊無空格)，姓名由3至10個大寫英文字母組成，中間無空格。[輸出格式]在屏幕上輸出符合條件的名字，假設(shè)有多個名字符合條件，須按字典順序列出，每個名字占一行(左邊無空格)[輸入輸出舉例]假設(shè)有三個文件如下：math.txtcomputer.txthistory.txtWANGLINWANGQINGWANGLINZHANGPINLIHONGLINLINGZHAOPENGZHAOPINGWANGFANWANGFANZHAOPENGZHAOPINLIUQINGWANGLINZHAOPENG

輸入 輸出math.txtWANGLINcomputer.txtZHAOPENGhistory.txt3例題分析這是一道比較簡單的查找和統(tǒng)計問題。最容易想到的就使用一個數(shù)組每一個出現(xiàn)的名字及出現(xiàn)的次數(shù)記錄下來。這樣每增加一個節(jié)點，就要將當(dāng)前節(jié)點與前面所有產(chǎn)生的節(jié)點進行比較。這樣最壞的情況下時間復(fù)雜度將到達3000*3000=9*10^6。我們還會想到另一種方法，就使用單鏈表將名字從小大的連接起來。這樣，每新添一個節(jié)點，即從表頭查找起，假設(shè)找到相同的那么紀(jì)錄下來，否那么插入適當(dāng)?shù)奈恢谩＿@樣，時間復(fù)雜度會相應(yīng)的有所降低。對于查找，我們就不得不想到二叉排序樹，如果對此題構(gòu)造一棵二叉排序樹，對于每一個節(jié)點，左孩子存放比父節(jié)點字串值小的字串，右孩子存放比父節(jié)點字串值大的字串，，這樣平均時間復(fù)雜度將降到O〔logn〕。

并查集DisjointSets并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合的合并問題。并查集的主要操作有1－合并兩個不相交集合2－判斷兩個元素是否屬于同一個集合3－路徑壓縮元素的合并圖示13245合并1和2合并1和3合并5和4合并5和3判斷元素是否屬于同一集合用father[i]表示元素i的父親結(jié)點，如剛剛那個圖所示12354faher[1]=1faher[2]=1faher[3]=1faher[4]=5faher[5]=3判斷元素是否屬于同一集合由此用某個元素所在樹的根結(jié)點表示該元素所在的集合判斷兩個元素時候?qū)儆谕粋€集合的時候，只需要判斷他們所在樹的根結(jié)點是否一樣即可也就是說，當(dāng)我們合并兩個集合的時候，只需要在兩個根結(jié)點之間連邊即可并查集的操作判斷兩個節(jié)點是否在同一個集合中合并兩個集合并查集操作的關(guān)鍵——維護并查集1235648710判斷5與10是否在同一個集合中第一步：上溯11第二步：上調(diào)41087合并11和10所在的集合第一步：上溯第二步：合并第三步：上調(diào)路徑壓縮上述的做法是指就是將元素的父親結(jié)點指來指去的在指，當(dāng)這課樹是鏈的時候，可見判斷兩個元素是否屬于同一集合需要O(N)的時間，于是路徑壓縮產(chǎn)生了作用路徑壓縮實際上是在找完根結(jié)點之后，在遞歸回來的時候順便把路徑上元素的父親指針都指向根結(jié)點路徑壓縮示意圖13245由此我們得到了一個復(fù)雜度只是O(1)的算法程序清單functiongetfather(v:integer):integer;beginif(father[v]=0)thengetfather:=velsebeginfather[v]:=getfather(father[v]);getfather:=father[v];end;end;程序清單functionjudge(x,y:integer):boolean;varfx,fy:integer;beginfx:=getfaher(x);fy:=gefather(y);Iffx=fythenjudge:=exit(true)elsejudge:=false;father[fx]:=fy;{合并兩個集合}end;例1親戚假設(shè)某個家族人員過于龐大，要判斷兩個是否是親戚，確實還很不容易，現(xiàn)在給出某個親戚關(guān)系圖，求任意給出的兩個人是否具有親戚關(guān)系。規(guī)定：x和y是親戚，y和z是親戚，那么x和z也是親戚。如果x,y是親戚，那么x的親戚都是y的親戚，y的親戚也都是x的親戚。例1親戚數(shù)據(jù)輸入：第一行：三個整數(shù)n,m,p，〔n<=5000,m<=5000,p<=5000〕，分別表示有n個人，m個親戚關(guān)系，詢問p對親戚關(guān)系。以下m行：每行兩個數(shù)Mi，Mj，1<=Mi，Mj<=N，表示Ai和Bi具有親戚關(guān)系。接下來p行：每行兩個數(shù)Pi，Pj，詢問Pi和Pj是否具有親戚關(guān)系。數(shù)據(jù)輸出：P行，每行一個’Yes’或’No’。表示第i個詢問的答案為“具有”或“不具有”親戚關(guān)系。例1親戚樣例：input.txt6531215345213142356output.txtYesYesNo例1親戚這個題目是最根底的并查集問題運用根本的并查集工具就可以解決了例2銀河英雄傳說(NOI2002)公元五八○一年，地球居民遷移至金牛座α第二行星，在那里發(fā)表銀河聯(lián)邦創(chuàng)立宣言，同年改元為宇宙歷元年，并開始向銀河系深處拓展。宇宙歷七九九年，銀河系的兩大軍事集團在巴米利恩星域爆發(fā)戰(zhàn)爭。泰山壓頂集團派宇宙艦隊司令萊因哈特率領(lǐng)十萬余艘戰(zhàn)艦出征，氣吞山河集團點名將楊威利組織麾下三萬艘戰(zhàn)艦迎敵。例2銀河英雄傳說(NOI2002)楊威利擅長排兵布陣，巧妙運用各種戰(zhàn)術(shù)屢次以少勝多，難免恣生驕氣。在這次決戰(zhàn)中，他將巴米利恩星域戰(zhàn)場劃分成30000列，每列依次編號為1,2,…,30000。之后，他把自己的戰(zhàn)艦也依次編號為1,2,…,30000，讓第i號戰(zhàn)艦處于第i列(i=1,2,…,30000)，形成“一字長蛇陣”，誘敵深入。這是初始陣形。當(dāng)進犯之?dāng)车竭_時，楊威利會屢次發(fā)布合并指令，將大局部戰(zhàn)艦集中在某幾列上，實施密集攻擊。合并指令為Mij，含義為讓第i號戰(zhàn)艦所在的整個戰(zhàn)艦隊列，作為一個整體〔頭在前尾在后〕接至第j號戰(zhàn)艦所在的戰(zhàn)艦隊列的尾部。顯然戰(zhàn)艦隊列是由處于同一列的一個或多個戰(zhàn)艦組成的。合并指令的執(zhí)行結(jié)果會使隊列增大。例2銀河英雄傳說(NOI2002)然而，老謀深算的萊因哈特早已在戰(zhàn)略上取得了主動。在交戰(zhàn)中，他可以通過龐大的情報網(wǎng)絡(luò)隨時監(jiān)聽楊威利的艦隊調(diào)動指令。在楊威利發(fā)布指令調(diào)動艦隊的同時，萊因哈特為了及時了解當(dāng)前楊威利的戰(zhàn)艦分布情況，也會發(fā)出一些詢問指令：Cij。該指令意思是，詢問電腦，楊威利的第i號戰(zhàn)艦與第j號戰(zhàn)艦當(dāng)前是否在同一列中，如果在同一列中，那么它們之間布置有多少戰(zhàn)艦。作為一個資深的高級程序設(shè)計員，你被要求編寫程序分析楊威利的指令，以及答復(fù)萊因哈特的詢問。最終的決戰(zhàn)已經(jīng)展開，銀河的歷史又翻過了一頁……例2銀河英雄傳說(NOI2002)輸入文件galaxy.in的第一行有一個整數(shù)T〔1<=T<=500,000〕，表示總共有T條指令。以下有T行，每行有一條指令。指令有兩種格式：1.

Mij：i和j是兩個整數(shù)〔1<=i,j<=30000〕，表示指令涉及的戰(zhàn)艦編號。該指令是萊因哈特竊聽到的楊威利發(fā)布的艦隊調(diào)動指令，并且保證第i號戰(zhàn)艦與第j號戰(zhàn)艦不在同一列。2.

Cij：i和j是兩個整數(shù)〔1<=i,j<=30000〕，表示指令涉及的戰(zhàn)艦編號。該指令是萊因哈特發(fā)布的詢問指令。例2銀河英雄傳說(NOI2002)輸出文件為galaxy.out。你的程序應(yīng)當(dāng)依次對輸入的每一條指令進行分析和處理：如果是楊威利發(fā)布的艦隊調(diào)動指令，那么表示艦隊排列發(fā)生了變化，你的程序要注意到這一點，但是不要輸出任何信息；如果是萊因哈特發(fā)布的詢問指令，你的程序要輸出一行，僅包含一個整數(shù)，表示在同一列上，第i號戰(zhàn)艦與第j號戰(zhàn)艦之間布置的戰(zhàn)艦數(shù)目。如果第i號戰(zhàn)艦與第j號戰(zhàn)艦當(dāng)前不在同一列上，那么輸出-1。例2銀河英雄傳說(NOI2002)樣例輸入4M23C12M24C42樣例輸出-11例2銀河英雄傳說(NOI2002)

第一列第二列第三列第四列……初始時1234……M231

324……C121號戰(zhàn)艦與2號戰(zhàn)艦不在同一列，因此輸出-1M241

432……C424號戰(zhàn)艦與2號戰(zhàn)艦之間僅布置了一艘戰(zhàn)艦，編號為3，輸出1例2銀河英雄傳說(NOI2002)這一題需要增加兩個域，一個表示該元素所在集合中元素的總個數(shù)，用count表示；另一個是在該集合中，這個元素之前有多少個元素，用before表示。初始的時候father[i]:=i;count[i]:=1;before[i]:=0;例2銀河英雄傳說(NOI2002)路徑壓縮Functiongetfather(v:longint):longint;varf:longint;beginiffather[v]=vthengetfather:=velsebeginf:=getfather(father[v]);before[v]:=before[father[v]]+before[v];{這里是關(guān)鍵}father[v]:=f;getfather:=father[v];end;end;例2銀河英雄傳說(NOI2002)歸并操作Proceduremerge(x,y:longint);vari,j:longint;begini:=getfather(x);j:=getfather(y);father[i]:=j;before[i]:=before[i]+count[j];count[j]:=count[j]+count[i];{做相應(yīng)的修改}end;例2銀河英雄傳說(NOI2002)詢問操作Procedureask(x,y:longint);beginifgetfather(x)<>getfather(y)thenwriteln(-1)elsewriteln(abs(before[x]-before[y])-1);end;這一題中在量與量的處理中參加了一些附加的信息，但只要你理清了并查集的根本思路，此題也就通過上面三個簡單的過程解決了。例3食物鏈(NOI2001)動物王國中有三類動物A,B,C，這三類動物的食物鏈構(gòu)成了有趣的環(huán)形。A吃B，B吃C，C吃A?，F(xiàn)有N個動物，以1－N編號。每個動物都是A,B,C中的一種，但是我們并不知道它到底是哪一種。有人用兩種說法對這N個動物所構(gòu)成的食物鏈關(guān)系進行描述：第一種說法是“1XY”，表示X和Y是同類。第二種說法是“2XY”，表示X吃Y。例3食物鏈(NOI2001)此人對N個動物，用上述兩種說法，一句接一句地說出K句話，這K句話有的是真的，有的是假的。當(dāng)一句話滿足以下三條之一時，這句話就是假話，否那么就是真話。1－當(dāng)前的話與前面的某些真的話沖突，就是假話；2－當(dāng)前的話中X或Y比N大，就是假話；3－當(dāng)前的話表示X吃X，就是假話。你的任務(wù)是根據(jù)給定的N〔1<=N<=50,000〕和K句話〔0<=K<=100,000〕，輸出假話的總數(shù)。例3食物鏈(NOI2001)輸入文件第一行是兩個整數(shù)N和K，以一個空格分隔。以下K行每行是三個正整

D，X，Y，兩數(shù)之間用一個空格隔開，其中D表示說法的種類。假設(shè)D=1，那么表示X和Y是同類。假設(shè)D=2，那么表示X吃Y。輸出文件只有一個整數(shù)，表示假話的數(shù)目。例3食物鏈(NOI2001)輸入文件對7句話的分析100711011假話212真話223真話233假話113假話231真話155真話例3食物鏈(NOI2001)很顯然，對假話條件2、3的處理十分簡單，只要在讀入數(shù)據(jù)時作兩個條件判斷即可解決，題目的主要任務(wù)在于處理條件1。從外表上看，條件１的處理似乎也沒有什么難度：一個動物無非就是A,B,C三類，而A,B,C之間的食物鏈關(guān)系是一對一單向環(huán)形的，也就是說如果動物X所屬種類和X、Y之間的食物鏈關(guān)系，就一定可以確定出動物Y的種類，同時某個動物具體屬于哪一類并不影響此題的結(jié)果，而只要求它與其他動物關(guān)系的相對位置正確即可。例3食物鏈(NOI2001)于是，我們不妨開3個數(shù)組A,B,C，分別記錄著三種類的成員，首先假設(shè)第一句有效話中的動物X為A類，將其放入數(shù)組A，倘假設(shè)Y與X同類，那么把Y也放入A；假設(shè)Y被X吃，那么將Y放入B，如此反復(fù)操作所有的有效話，就可以確定每個動物的種類，并容易統(tǒng)計出假話的個數(shù)。例3食物鏈(NOI2001)問題似乎已經(jīng)圓滿地解決了，但是，稍稍認真思考就會發(fā)現(xiàn)，上面的這個算法存在著重大的錯誤，是十分片面的。對于一個未知屬性的生物我們都采取的是定義為A類型，這樣子顯然是錯的。可見，這個算法只能當(dāng)每一句話都可直接與此前的食物鏈建立明確關(guān)系的時候才能使用。例3食物鏈(NOI2001)明確了上面這個關(guān)系，我們就不難從剛剛的算法擴展出另一種算法：對于目前關(guān)系未知的動物X，我們?yōu)樗麻_辟一條食物鏈A2,B2,C2，顯然，在這個新的組中，動物X所在的種類也是隨意的，于是假設(shè)它在A2組，這樣，所有與X的關(guān)系就可用與算法1同樣的方式參加這個組中，而這個組與原先的組A1,B1,C1的關(guān)系是不確定的。如此反復(fù)，我們也可以得到組3、組4、組5……，一旦有一句話牽涉到某兩個組的成員之間的食物鏈關(guān)系，我們就依據(jù)一定的換算規(guī)那么將這兩個組合并起來，以保證關(guān)系網(wǎng)的完整性。例3食物鏈(NOI2001)通過上面的分析，并查集在此題中的運用已經(jīng)呼之欲出。一個集合有三類的元素，合并集合的時候，需要對三類元素進行合并。Parity(ceoi99)有一個01序列,長度<=1000000000,現(xiàn)在有n條信息,每條信息的形式是－abeven/odd。表示第a位到第b位元素之間的元素總和是偶數(shù)/奇數(shù)。你的任務(wù)是對于這些給定的信息，輸出第一個不正確的信息所在位置-1。信息的數(shù)目不超過5000。如果信息全部正確，即可以找到一個滿足要求的01序列，那么輸出n。Parity(ceoi99)輸入文件第一行一個整數(shù)m表示01序列的長度，第二行一個整數(shù)n表示信息的數(shù)目。接下來是n條信息樣例輸入10512even34odd56even16even710odd樣例輸出3{因為第4個信息是不正確的，所以輸出3，表示從1到3條信息都是正確的}Parity(ceoi99)從整個01序列肯定是無法入手的，因為它的長度高達109。從范圍比較小的n入手。也就是說我們需要對信息進行一些特殊的處理。abeven/odd，那么將元素b指向a-1，邊的權(quán)值是even/odd。下面我們由樣例來說明一下這個處理方法。Parity(ceoi99)042612even34odd56even16even0100???Parity(ceoi99)顯然在第4條信息參加的時候，6到0已經(jīng)有值存在，即(0+1+0)mod2=1，這時添入6到0為0顯然是不對。實現(xiàn)的時候不用開1-109的數(shù)組，因為出現(xiàn)的不同元素最多有104而已，因此，開一個列表存儲元素即可。算法的大致框架就是對于讀入的信息不斷地用上述方法處理，由區(qū)間的遞推性質(zhì)可以得出矛盾與否。上述算法的實現(xiàn)就用到了并查集。DisjointSets小結(jié)先從問題的簡單做法入手，構(gòu)造出原始模型。如果原始模型是對于集合之間合并處理問題，那么就可以使用并查集使得程序變得高效。并查集的路徑壓縮只有在元素之間的特性存在遞推關(guān)系時才可以使用。圖型結(jié)構(gòu)圖的概念圖〔graph〕是圖型結(jié)構(gòu)的簡稱。它是一種復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)。圖在各個領(lǐng)域都著廣泛的應(yīng)用。圖的二元組定義為：G=〔V,E〕其中V是非空的頂點集合，即V={vi|1<=i<=n,n>=1,vi∈elemtype，n為頂點數(shù)}圖的根本術(shù)語1、端點和鄰接點在一個無向圖中，假設(shè)存在—條邊〔vi，vj〕，那么稱vi,vj為此邊的兩個端點，并稱它們互為鄰接點〔adjacent〕，即vi是vj的一個鄰接點，vj也是vi的一個鄰接點。在一個有向圖中，假設(shè)存在一條邊<vi,vj>，那么稱此邊是頂點vi的一條出邊〔outedge〕，頂點vj的一條入邊〔inedge〕；稱Vi為此邊的起始端點，簡稱起點或始點，vj為此邊的終止端點，簡稱終點；稱vi和vj互為鄰接點，并稱vj是vi的出邊鄰接點，vi是vj的入邊鄰接點。2、頂點的度、入度、出度無向圖頂點v的度〔degree〕定義為以該頂點為一個端點的邊的數(shù)目，簡單地說，就是該頂點的邊的數(shù)目，記為D〔v〕。有向圖中頂點v的度有入度和出度之分，入度〔indegree〕是該頂點的入邊的數(shù)目，記為ID〔v〕；出度〔outdegree〕是該頂點的出邊的數(shù)目，記為OD〔v〕頂點v的度等于它的入度和出度之和，即D〔v〕=ID〔v〕+OD〔v〕。3、完全圖、稠密圖、稀疏圖假設(shè)無向圖中的每兩個頂點之間都存在著一條邊，有向圖中的每兩個頂點之間都存在著方向相反的兩條邊，那么稱此圖為完全圖。顯然，假設(shè)完全圖是無向的，那么圖中包含有n〔n-1〕/2條邊,假設(shè)完全圖是有向的，那么圖中包含有n〔n-1〕條邊。當(dāng)一個圖接近完全圖時，那么可稱為稠密圖，相反地，當(dāng)一個圖有較少的邊數(shù)〔即e<<n〔n–1〕〕時，那么可稱為稀疏圖。4、子圖設(shè)有兩個圖G=〔V,E〕和G’＝〔V’,E’〕,假設(shè)V’是V的子集，且E’是E的子集，那么成G’是G的子圖。5、路徑和回路在一個圖G中，從頂點v到頂點v’的一條路徑〔path〕是一個頂點序列vi0,vi1,vi2,vim,其中v=vi0,v’=vim,假設(shè)此圖是無向圖，那么〔vij-1,vij〕∈E〔G〕，〔1≤j≤m〕；假設(shè)此圖是有向圖，那么<vij-1,vij>∈E〔G〕，〔1≤j≤m〕。路徑長度是指該路徑上經(jīng)過的邊的數(shù)目。假設(shè)一條路徑上除了前后端點可以相同外，所有頂點均不同，那么稱此路徑為簡單路徑。假設(shè)一條路徑上的前后兩端點相同，那么被稱為回路或環(huán)〔cycle〕，前后兩端點相同的簡單路徑被稱為簡單回路或簡單環(huán)。6、連通和連通分量在無向圖G中，假設(shè)從頂點vi到頂點vj有路徑，那么稱vi和vj是連通的。假設(shè)圖G中任意兩個頂點都連通，那么稱G為連通圖，否那么稱為非連通圖。無向圖G的極大連通子圖稱為G的連通分量。顯然，任何連通圖的連通分量只有一個，即本身，而非連通圖有多個連通分量。7、強連通圖和強連通分量在有向圖G中，假設(shè)從頂點vi到頂點vj有路徑，那么稱從vi到vj是連通的。假設(shè)圖G中的任意兩個頂點vi和vj都連通，即從vi到vj和從vj到vi都存在路徑，那么稱G是強連通圖。有向圖G的極大強連通子圖稱為G的強連通分量。顯然，強連通圖只有一個強連通分量，即本身，非強連通圖有多個強連通分量。8、權(quán)和網(wǎng)在一個圖中．每條邊可以標(biāo)上具有某種含義的數(shù)值，此數(shù)值稱為該邊的權(quán)〔weight〕。例如，對于一個反映城市交通線路的圖，邊上的權(quán)可表示該條線路的長度或等級；對于一個反映電子線路的圖，邊上的權(quán)可表示兩端點間的電阻、電流或電壓；對于一個反映零件裝配的圖，邊上的權(quán)可表示一個端點需要裝配另一個端點的零件的數(shù)量；對于一個反映工程進度的圖，邊上的權(quán)可表示從前一子工程到后一子工程所需要的天數(shù)。邊上帶有權(quán)的圖稱作帶權(quán)圖，也常稱作網(wǎng)〔network〕。

圖的存儲結(jié)構(gòu)

1、鄰接矩陣鄰接矩陣〔adjacencymatrix〕是表示頂點之間相鄰關(guān)系的矩陣。設(shè)G＝〔V，E〕是具有n個頂點的圖，頂點序號依次為1、2、···、n，那么G的鄰接矩陣是具有如下定義的n階方陣。2、鄰接表鄰接表〔adjacencylist〕是對圖中的每個頂點建立一個鄰接關(guān)系的單鏈表，并把它們的表頭指針用向量存儲的一種圖的表示方法。為頂點vi建立的鄰接關(guān)系的單鏈表又稱作vi的鄰接表。vi鄰接表中的每個結(jié)點用來存儲以該頂點為端點或起點的一條邊的信息，因而被稱為邊結(jié)點。vi鄰接表中的結(jié)點數(shù)，對于無向圖來說，等于vi的邊數(shù)，鄰接點數(shù)或度數(shù)；對于有向圖來說，等于vi的出邊數(shù)、出邊鄰接點數(shù)或出度數(shù)。

圖的遍歷

1、深度優(yōu)先遍歷深度優(yōu)先搜索〔depthfirstsearch〕遍歷類似樹的先根遍歷，它是一個遞歸過程，可表達為：首先訪問一個頂點vi〔開始為初始點〕，并將其標(biāo)記為已訪問過，然后從vi的一個未被訪問的鄰接點〔無向圖〕或出邊鄰接點〔有向圖〕出發(fā)進行深度優(yōu)先搜索遍歷，當(dāng)vi的所有鄰接點均被訪問過時，那么退回到上一個頂點vk，從vk的另一個未被訪問過的鄰接點出發(fā)進行深度優(yōu)先搜索遍歷。2、廣度優(yōu)先搜索遍歷廣度優(yōu)先搜索〔breadth—firstsearch〕遍歷類似樹的按層遍歷，其過程為：首先訪問初始點vi,并將其標(biāo)記為已訪問過，接著訪問vi的所有未被訪問過的鄰接點vi1,vi2,···,vit并均標(biāo)記