堆棧、隊(duì)列、樹(shù)形結(jié)構(gòu)長(zhǎng)沙市一中曹利國(guó)NOIp數(shù)據(jù)結(jié)構(gòu)棧352棧頂一種“后進(jìn)先出”的結(jié)構(gòu)加入一個(gè)數(shù)4取出棧頂元素再取出棧頂元素6棧352棧頂一種“后進(jìn)先出”的結(jié)構(gòu)加入一個(gè)數(shù)4取出棧頂元素再取出棧頂元素6分析構(gòu)造一個(gè)bracket棧，每次插入“（”，每遇到“）”時(shí)取出棧頂元素，如果此時(shí)碰到空棧則證明“）”多了，不合法。處理到串結(jié)束如果棧中還有元素也是不合法的，否則，是合法的。棧的應(yīng)用Procedurebracket;Flag:=false;Whilenoteofdoread(c);ifc=‘(‘thenpush(c)elseifnotgettopthenflag:=falseelsedeltop;endW;Ifgettopthenflag:=false;EndP;棧的應(yīng)用請(qǐng)思考如果上題中出現(xiàn)了()[]{}三種括號(hào)，包括嵌套（例：形如[{()}]也是合法的），又該如何處理？例題2：數(shù)制轉(zhuǎn)換將十進(jìn)制數(shù)轉(zhuǎn)換成其它進(jìn)制的數(shù)有一種簡(jiǎn)單的方法：例：十進(jìn)制轉(zhuǎn)換成八進(jìn)制：(66)10=(102)866/8=8余28/8=1余01/8=0余1結(jié)果為余數(shù)的逆序:102。先求得的余數(shù)在寫(xiě)出結(jié)果時(shí)最后寫(xiě)出，最后求出的余數(shù)最先寫(xiě)出，符合棧的先入后出性質(zhì)，故可用棧來(lái)實(shí)現(xiàn)數(shù)制轉(zhuǎn)換：例題三：最長(zhǎng)詞鏈一個(gè)詞是由至少1個(gè)，至多75個(gè)小寫(xiě)英文字母(a..z)組成。當(dāng)在一張由一個(gè)或多個(gè)詞組成的表中，每一個(gè)詞（除第一個(gè)外）都能由在其前一個(gè)詞的詞尾添加一個(gè)或多個(gè)字母而得到，則稱此表為一個(gè)鏈。例如：iinintinteger為一個(gè)含4個(gè)詞的詞鏈。分析這道題目，雖然測(cè)試數(shù)據(jù)大得驚人，但是難度卻并不大。主要的是要把握住表的特點(diǎn)：詞按字典順序由小到大的排列，因此表中的相鄰的兩個(gè)詞語(yǔ)之間的關(guān)系只有兩種——屬于同一詞鏈或不屬于同一詞鏈，若它們不屬于同一詞鏈，那么后一個(gè)單詞所在的詞鏈，除這一個(gè)單詞外的鏈（這個(gè)鏈可能為空）必定為它在表中的前一個(gè)單詞的詞鏈的前綴。算法框架constMaxLen=75;(單詞的最大長(zhǎng)度)typeTwork=objectTop，Max：Integer；（Top表示堆棧中元素的個(gè)數(shù)，Max表示最大詞鏈的長(zhǎng)度）；Word,Ans：array[1..MaxLen]ofString[MaxLen];（棧中每一層記錄的詞）procedureWork；end；procedureTwork.Work;1.Top←0；Max←0；2.Readln(St);讀入一個(gè)詞3.WhileSt<>’.’DoWhile(Top>0)and(Pos(Word[Top],St)<>1doTop←Top-1;｛查找堆棧中的詞判斷哪些詞語(yǔ)能夠繼續(xù)和目前的這個(gè)詞構(gòu)成詞鏈｝5.Top←Top+1;Word[Top]←St;6.IfTop>Maxthen7.beginMax←Top;Ans←Word;end;更新Max的值8.Readln(St);讀入一個(gè)詞9.輸出棧的應(yīng)用算術(shù)達(dá)式求值：輸入一個(gè)表達(dá)式，該表達(dá)式含有“+”、“-”、“*”、“/”、“（”、“）”和操作數(shù)，輸入以@結(jié)束。構(gòu)造兩個(gè)棧opnd和optr分別存放操作數(shù)和操作符構(gòu)造操作符的優(yōu)先關(guān)系表表達(dá)式：3×(5–2)+7@opndoptr3×(5–23+975–2=33×3=97+9=16結(jié)果便是16！16使用棧進(jìn)行算術(shù)表達(dá)式求值算法流程1、插入操作數(shù)或操作符2、如果是操作符，判斷與optr棧頂操作符的優(yōu)先關(guān)系，進(jìn)行運(yùn)算或保留，并刪除和加入相應(yīng)的操作數(shù)。3、事先在末尾加一個(gè)特殊符號(hào)（如“@”），并設(shè)定其優(yōu)先度最低，這樣，運(yùn)行到最后可使得opnd只剩一個(gè)數(shù)，即答案。隊(duì)列隊(duì)列是一種先進(jìn)先出(FIFO)的線性表隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)隊(duì)列必須構(gòu)造成循環(huán)隊(duì)列的形式,否則會(huì)出現(xiàn)“假溢出”

constmaxsize=隊(duì)列最大容量；

m=maxsize-1;typecyclcquetp=recordelem:array[0..m]ofelemtp;rear,front:0..m;end;基本操作插入（en_cycque）刪除（dl_cycque）隊(duì)列3265419隊(duì)列頭隊(duì)列尾算法框架Procedurework;Readln(n,m);//讀入Iniqueue;//初始化隊(duì)列P:=head;Fori:=1tondobeginforj:=1tom-1dop:=p^.next;out(p);//輸出

del(p);//刪除

endF;endP;q:=p^.pre;t:=p^.next;q^.next:=t;t^.pre:=q;dispose(p);p:=t;牙醫(yī)診所下面將描述牙科診所的一個(gè)實(shí)例:這兒有3位牙醫(yī),張醫(yī)生工作時(shí)間是[14,18]中的一個(gè)隨機(jī)整數(shù)(單位為分鐘),王醫(yī)生工作時(shí)間是[19,23]中的一個(gè)隨機(jī)整數(shù),李醫(yī)生工作時(shí)間是[20,24]中的一個(gè)隨機(jī)整數(shù),當(dāng)一個(gè)病人在某一時(shí)刻T1走進(jìn)診室,希望任一牙醫(yī)給他看病,預(yù)計(jì)時(shí)間為T(mén)2,T2為上面三個(gè)區(qū)間中的某一隨機(jī)數(shù),如果任一醫(yī)生空閑,則可以給這一病人看病,而且,一旦看完病,病人于T1+T2離開(kāi),病人在診所里花去的時(shí)間準(zhǔn)確的為T(mén)2,然而,可能沒(méi)有一位醫(yī)生是空閑的,他們都在為先到的病人看病.在這種情況下,每一位牙醫(yī)都有一個(gè)等候的隊(duì)列.病人首先走到等候隊(duì)列最短的隊(duì)列,排在最后面.一直到先等的人看完,于是該病人必須等到等候隊(duì)列的最前面之后,再過(guò)T2時(shí)間才離開(kāi)牙科診室.在這時(shí),他花在牙科診室的時(shí)間為T(mén)2加上排隊(duì)時(shí)間如果假設(shè)牙科診室可容納20個(gè)病人(包括正在看病的三個(gè)病人),病人每隔5-9分鐘

(取[5,9]中的一個(gè)隨機(jī)整數(shù)),一個(gè)接一個(gè)進(jìn)入牙科診室,但當(dāng)診室滿額時(shí)(新來(lái)的)病人便離去,試編寫(xiě)一個(gè)程序仿真這個(gè)系統(tǒng)(牙科診室的病人情況),打印一組信息(病人的標(biāo)識(shí)符ID,始末時(shí)間,對(duì)應(yīng)醫(yī)生),仿真結(jié)束時(shí),應(yīng)打印平均等待時(shí)間(從請(qǐng)求到開(kāi)始看病的時(shí)間).二叉樹(shù)二叉樹(shù)就是最多只有兩個(gè)子節(jié)點(diǎn)的樹(shù)所有葉節(jié)點(diǎn)深度相同的二叉樹(shù)為滿二叉樹(shù)深度為k且有n個(gè)節(jié)點(diǎn)的二叉樹(shù)，當(dāng)其每一個(gè)節(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)從1至n的節(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱之為完全二叉樹(shù)多叉樹(shù)轉(zhuǎn)二叉樹(shù)用二叉樹(shù)表示一棵樹(shù)要比多叉樹(shù)簡(jiǎn)單些，而且多叉樹(shù)都可以轉(zhuǎn)換成唯一的二叉樹(shù)。對(duì)于多叉樹(shù)中的每個(gè)節(jié)點(diǎn)，可以用兩個(gè)指針?lè)謩e指向它的第一個(gè)子節(jié)點(diǎn)和下一個(gè)相鄰節(jié)點(diǎn)。多叉轉(zhuǎn)二叉的例子在下圖中，每個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)為它原來(lái)的第一個(gè)子節(jié)點(diǎn)，右子節(jié)點(diǎn)為它的第一個(gè)兄弟節(jié)點(diǎn)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 哈夫曼樹(shù)哈夫曼樹(shù)又稱最優(yōu)二叉樹(shù)，是一種帶權(quán)路徑長(zhǎng)度最短的二叉樹(shù)。所謂樹(shù)的帶權(quán)路徑長(zhǎng)度，就是樹(shù)中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長(zhǎng)度（若根結(jié)點(diǎn)為0層，葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度為葉結(jié)點(diǎn)的層數(shù)）。樹(shù)的帶權(quán)路徑長(zhǎng)度記為WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N個(gè)權(quán)值Wi(i=1,2,...n)構(gòu)成一棵有N個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，相應(yīng)的葉結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)i(i=1,2,...n)。可以證明哈夫曼樹(shù)的WPL是最小的。哈夫曼樹(shù)然而怎樣構(gòu)造一棵哈夫曼樹(shù)呢？最具有一般規(guī)律的構(gòu)造方法就是哈夫曼算法。一般的數(shù)據(jù)結(jié)構(gòu)的書(shū)中都可以找到其描述：一、對(duì)給定的n個(gè)權(quán)值{W1,W2,W3,...,Wi,...,Wn}構(gòu)成n棵二叉樹(shù)的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉樹(shù)Ti中只有一個(gè)權(quán)值為Wi的根結(jié)點(diǎn)，它的左右子樹(shù)均為空。（為方便在計(jì)算機(jī)上實(shí)現(xiàn)算法，一般還要求以Ti的權(quán)值Wi的升序排列。）二、在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作為新構(gòu)造的二叉樹(shù)的左右子樹(shù)，新二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左右子樹(shù)的根結(jié)點(diǎn)的權(quán)值之和。三、從F中刪除這兩棵樹(shù)，并把這棵新的二叉樹(shù)同樣以升序排列加入到集合F中。四、重復(fù)二和三兩步，直到集合F中只有一棵二叉樹(shù)為止。構(gòu)造二叉哈夫曼樹(shù)選取值最小的兩個(gè)根節(jié)點(diǎn)a和b。創(chuàng)建一個(gè)新節(jié)點(diǎn)，其權(quán)值就是a、b的權(quán)值之和，左右子樹(shù)分別為a、b這兩個(gè)節(jié)點(diǎn)。重復(fù)1步驟，直至只有一個(gè)根節(jié)點(diǎn)（即所有節(jié)點(diǎn)都在同一棵樹(shù)中）。1249108371915344910819哈夫曼樹(shù)應(yīng)用題目闡述：

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

AＡ

D

BE

CＤ

Ｂ

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

于是構(gòu)成Ｎ叉樹(shù)如下：為虛結(jié)點(diǎn)

ＦＥ

ＤＣ

ＢＡ

ＷＰＬ＝１＊６＋１＊５＋２＊４＋２＊３＋３＊２＋３＊１＋３＊０＝３３對(duì)應(yīng)編碼為：Ａ：２２１Ｂ：２２０Ｃ：２１Ｄ：２０Ｅ：１Ｆ：０由此可知，對(duì)于N叉二叉樹(shù)我們也可以類似處理。哈夫曼樹(shù)應(yīng)用堆堆是一種特殊的二叉樹(shù)它滿足{V(左孩子)<V(根)>V(右孩子)}或{V(左孩子)>V(根)<V(右孩子)}堆我們?nèi)绾谓ǘ涯?如果需要O(N)去添加一個(gè)元素，這就沒(méi)有意義了，所以，我們要用O(log2(N))把一個(gè)元素加進(jìn)去。這樣，我們就可以在O(NlogN)的時(shí)間內(nèi)建好堆。堆(以小根堆為例)3建堆開(kāi)始……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é)點(diǎn)71273728833868一、取出二、調(diào)整算法描述（堆排序）proceduresort;build;fori:=1tondowriteln(a[1]);delete(1);endp;類似于push,不過(guò)push是把小元素向上換，delete是把最小的刪掉后，把最后一個(gè)元素放上來(lái)，這樣就變成了把一個(gè)大元素向下放的過(guò)程，具體方法請(qǐng)自己思考。堆排序算法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īng)用果子合并在一個(gè)果園里，多多已經(jīng)將所有的果子打了下來(lái)，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。

每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和?？梢钥闯?，所有的果子經(jīng)過(guò)n-1次合并之后，就只剩下一堆了。多多在合并果子時(shí)總共消耗的體力等于每次合并所耗體力之和。

因?yàn)檫€要花大力氣把這些果子搬回家，所以多多在合并果子時(shí)要盡可能地節(jié)省體力。假定每個(gè)果子重量都為1，并且已知果子的種類數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計(jì)出合并的次序方案，使多多耗費(fèi)的體力最少，并輸出這個(gè)最小的體力耗費(fèi)值。

例如有3種果子，數(shù)目依次為1，2，9?？梢韵葘?、2堆合并，新堆數(shù)目為3，耗費(fèi)體力為3。接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為12，耗費(fèi)體力為12。所以多多總共耗費(fèi)體力=3+12=15?？梢宰C明15為最小的體力耗費(fèi)值。

堆的應(yīng)用【輸入文件】

輸入文件fruit.in包括兩行，第一行是一個(gè)整數(shù)n(1<＝n<=10000)，表示果子的種類數(shù)。第二行包含n個(gè)整數(shù)，用空格分隔，第i個(gè)整數(shù)ai(1<＝ai<=20000)是第i種果子的數(shù)目。

【輸出文件】

輸出文件fruit.out包括一行，這一行只包含一個(gè)整數(shù)，也就是最小的體力耗費(fèi)值。輸入數(shù)據(jù)保證這個(gè)值小于2^31。

堆的應(yīng)用很明顯，這道題是一道貪心的題目，可以證明，每次取最小的兩堆合并會(huì)使得最后的體力值最小。那么，這道題的問(wèn)題就在于怎么找最小的兩堆果子了。注意到，每次合并完果子會(huì)刪掉兩堆，并添加一堆新的，如果采用線性表，時(shí)間復(fù)雜度將高達(dá)O（N^2），對(duì)于N<=20000是不夠的。所以，我們考慮用小根堆優(yōu)化。堆的應(yīng)用算法：建立空堆每讀入一個(gè)數(shù)插入堆中每次取兩個(gè)堆頂元素合并，并插入合并后的數(shù)，總共合并n-1次。堆的應(yīng)用具體實(shí)現(xiàn)參考堆排代碼用堆優(yōu)化dijstra算法例題：最小序列問(wèn)題。給定一個(gè)N×N（N<=100）的正整數(shù)矩陣。需要在矩陣中尋找一條從起始位置到終止位置的路徑(可沿上下左右四個(gè)方向)，并且要求路徑中經(jīng)過(guò)的所有數(shù)字，其相鄰數(shù)字之差的絕對(duì)值之和最小。例題分析這道題的基本算法很簡(jiǎn)單，只要用Dijkstra算法求出從起始位置到終止位置的最短路徑即可。但這當(dāng)中存在一個(gè)很大的問(wèn)題：N<=100。這就是說(shuō)圖中點(diǎn)的數(shù)目可能多達(dá)10000個(gè)。此時(shí)復(fù)雜度為O(n2)的Dijkstra算法就顯得有些力不從心了。例題分析我們繼續(xù)對(duì)算法進(jìn)行分析。由于Dijstra算法通常采用的是線性的數(shù)組結(jié)構(gòu)，所以當(dāng)我們每次尋找下一條最短路徑時(shí)，有兩步需要進(jìn)行：（1）找出一個(gè)不在最短路徑起點(diǎn)集合內(nèi)，并且到終點(diǎn)距離最短的頂點(diǎn)i。這一步的復(fù)雜度顯然為O(n)。（2）修改從與i相鄰的頂點(diǎn)到終點(diǎn)的路徑長(zhǎng)度。由于最多只有4個(gè)點(diǎn)(四個(gè)方向)與i相鄰，所以這一步的復(fù)雜度為O(1)即常數(shù)例題分析這兩步中，雖然第二步最多只改變了到4個(gè)點(diǎn)的路徑長(zhǎng)度，但是第一步卻還是需要枚舉所有的數(shù)組元素，這顯然很浪費(fèi)時(shí)間。出于對(duì)第一步進(jìn)行改進(jìn)的考慮，我們可以想到樹(shù)結(jié)構(gòu)中二叉堆的結(jié)構(gòu)。堆結(jié)構(gòu)的優(yōu)點(diǎn)是：根結(jié)點(diǎn)就是最優(yōu)的結(jié)點(diǎn)，并且改變堆中某個(gè)結(jié)點(diǎn)的值以后，只需O(log2n)的復(fù)雜度就可以完成堆化的過(guò)程(可分為從二叉樹(shù)中自下而上和自上而下兩種堆化方法，并且復(fù)雜度都一樣)，使堆的結(jié)構(gòu)發(fā)生改變后，通過(guò)堆化仍然能夠保留堆的性質(zhì)。如果我們采用二叉堆的結(jié)構(gòu)存儲(chǔ)距離，第一步就只需將根結(jié)點(diǎn)取出，并且用堆中的另一結(jié)點(diǎn)代替后進(jìn)行一次自上而下的堆化。因而第一步的復(fù)雜度可降為O(log2n)。但是，此時(shí)的堆結(jié)構(gòu)在進(jìn)行第二步時(shí)暴露了很大的缺點(diǎn)：無(wú)法預(yù)知i點(diǎn)的相鄰點(diǎn)在堆中的位置。如果我們用對(duì)堆進(jìn)行遍歷來(lái)尋找i的相鄰點(diǎn)，第二步的復(fù)雜度又成為了O(n)。例題分析我們從這兩種數(shù)據(jù)結(jié)構(gòu)中不難發(fā)現(xiàn)這樣規(guī)律：采用線性結(jié)構(gòu)的數(shù)組，易于進(jìn)行第二步；采用樹(shù)結(jié)構(gòu)的二叉堆，做第一步時(shí)效果比較理想。那么，我們是否可以將這兩種數(shù)據(jù)結(jié)構(gòu)進(jìn)行結(jié)合，取長(zhǎng)補(bǔ)短呢？我們可以采用映射的方法，將線性結(jié)構(gòu)中的元素與堆中間的結(jié)點(diǎn)一一對(duì)應(yīng)起來(lái)，若線性的數(shù)組中的元素發(fā)生變化，堆中相應(yīng)的結(jié)點(diǎn)也接著變化，堆中的結(jié)點(diǎn)發(fā)生變化，數(shù)組中相應(yīng)的元素也跟著變化。將兩種結(jié)構(gòu)進(jìn)行結(jié)合后，無(wú)論是第一步還是第二步，我們都不需對(duì)所有元素進(jìn)行遍歷，只需進(jìn)行常數(shù)次復(fù)雜度為O(log2n)的堆化操作。這樣，整個(gè)時(shí)間復(fù)雜度就成為了O(nlog2n)，算法效率無(wú)疑得到了很大提高。二叉搜索樹(shù)二叉查找樹(shù)（BinarySearchTree），或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：

若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；

若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；

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

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

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

2）只有一個(gè)兒子。那么把父節(jié)點(diǎn)的相應(yīng)兒子指針指向兒子的獨(dú)生子，刪除兒子節(jié)點(diǎn)也OK了。

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

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

（1）令a1為二叉樹(shù)的根；

（2）若a2<a1，則令a2為a1的左子樹(shù)的根結(jié)點(diǎn)，否則，令a2為a1的右子樹(shù)的根結(jié)點(diǎn)；

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

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

Everyoneroundyoucanhearyouwhenyousperk

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

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

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

[輸入格式]

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

[輸出格式]

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

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

輸入 輸出

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

[輸入格式]

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

computer.txthistory.txtWANGLINWANGQINGWANGLINZHANGPIN

LIHONG

LINLINGZHAOPENGZHAOPINGWANGFANWANGFANZHAOPENGZHAOPINLIUQING

WANGLINZHAOPENG

輸入

輸出

math.txt

WANGLINcomputer.txt

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

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

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

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

第一列第二列第三列第四列……初始時(shí)1234……M231

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

432……C424號(hào)戰(zhàn)艦與2號(hào)戰(zhàn)艦之間僅布置了一艘戰(zhàn)艦，編號(hào)為3，輸出1例2銀河英雄傳說(shuō)(NOI2002)這一題需要增加兩個(gè)域，一個(gè)表示該元素所在集合中元素的總個(gè)數(shù)，用count表示；另一個(gè)是在該集合中，這個(gè)元素之前有多少個(gè)元素，用before表示。初始的時(shí)候father[i]:=i;count[i]:=1;before[i]:=0;例2銀河英雄傳說(shuō)(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銀河英雄傳說(shuō)(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銀河英雄傳說(shuō)(NOI2002)詢問(wèn)操作Procedureask(x,y:longint);beginifgetfather(x)<>getfather(y)thenwriteln(-1)elsewriteln(abs(before[x]-before[y])-1);end;這一題中在量與量的處理中加入了一些附加的信息，但只要你理清了并查集的基本思路，本題也就通過(guò)上面三個(gè)簡(jiǎn)單的過(guò)程解決了。例3食物鏈(NOI2001)動(dòng)物王國(guó)中有三類動(dòng)物A,B,C，這三類動(dòng)物的食物鏈構(gòu)成了有趣的環(huán)形。A吃B，B吃C，C吃A?，F(xiàn)有N個(gè)動(dòng)物，以1－N編號(hào)。每個(gè)動(dòng)物都是A,B,C中的一種，但是我們并不知道它到底是哪一種。有人用兩種說(shuō)法對(duì)這N個(gè)動(dòng)物所構(gòu)成的食物鏈關(guān)系進(jìn)行描述：第一種說(shuō)法是“1XY”，表示X和Y是同類。第二種說(shuō)法是“2XY”，表示X吃Y。例3食物鏈(NOI2001)此人對(duì)N個(gè)動(dòng)物，用上述兩種說(shuō)法，一句接一句地說(shuō)出K句話，這K句話有的是真的，有的是假的。當(dāng)一句話滿足下列三條之一時(shí)，這句話就是假話，否則就是真話。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)輸入文件第一行是兩個(gè)整數(shù)N和K，以一個(gè)空格分隔。以下K行每行是三個(gè)正整

D，X，Y，兩數(shù)之間用一個(gè)空格隔開(kāi)，其中D表示說(shuō)法的種類。若D=1，則表示X和Y是同類。若