1、信息技術(shù)競(jìng)賽培訓(xùn)教程信息技術(shù)競(jìng)賽培訓(xùn)教程目錄 第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)（一）棧 （二）隊(duì)列 （三）鏈表 （四）迭代與遞推（五）遞歸（六）搜索與回溯（七）樹(shù)與二叉樹(shù)（八）排序算法（九）查找算法 （十）圖論基礎(chǔ)知識(shí) l l廣度優(yōu)先搜索l l廣度優(yōu)先搜索 第二部分算法和數(shù)據(jù)結(jié)構(gòu) （一）棧說(shuō)到學(xué)習(xí)和掌握數(shù)據(jù)結(jié)構(gòu)，很容易讓人想到的就是其最本的數(shù)據(jù)結(jié)構(gòu)模式棧、隊(duì)這一講，我們 就來(lái)談?wù)剹！薄！钡膽?yīng)用很廣泛，大家在 PASCAL程序設(shè)計(jì)中，常遇 的一種錯(cuò)誤就是 棧"超界，那么，棧”為何物呢 棧是只能在 莫一端插入和刪除的特殊線性表。用桶堆積物品，先堆進(jìn)來(lái)的壓在底下，隨后一件一件往 堆。取走時(shí)，只能從上面一

2、件一件取。堆和取都在頂部進(jìn)行，底部一般是不動(dòng)的。棧就是一種類似桶堆積物品的數(shù)據(jù)結(jié)構(gòu)，進(jìn)行刪除和 插入的一端稱棧頂，另一堆稱棧底。插入一般稱為進(jìn)棧（PUSH）,刪除則稱為退棧（POP）。棧也稱為后進(jìn)先生表（LIFO表）。一個(gè)棧可以用定長(zhǎng)為N的數(shù)組S來(lái)表示，用一個(gè)棧指 針TOP指向棧頂。若TOP=0,表示棧空，TOPN時(shí)棧滿。進(jìn)棧時(shí)TOP加1 o退棧時(shí)TOP減1 o當(dāng) TOP then exit; if si in * , / and symbolp in * , / then exit; can false; end; begin write String ; readlns; s s ; i

3、1; p 0; while i 9 ; t copys, j, i - j; valt, numberp, code; repeat if si then 右括號(hào)處理 begin while symbolp do pop; decp; numberp numberp 1; end else begin 根據(jù) 標(biāo)志函數(shù)值作運(yùn)算符入棧或由棧運(yùn)算處理 while can do pop;push; end; inci; until i lengths or si - 1; end; write Result ,number0; readln; end. 練習(xí)題 1、讀入一英文句子，單 詞之間用空格或逗

4、號(hào)隔開(kāi)，統(tǒng)計(jì)其中單詞個(gè)數(shù)，并輸由各個(gè) 字母由現(xiàn)的頻率。句子末尾不一定用”.結(jié)束 如果含有其他的字符，則只要求輸由錯(cuò)誤信息及錯(cuò)誤類型。含有大寫字母錯(cuò)誤類型error 1數(shù)字(0-9)錯(cuò)誤類型 error 2其他非法字符 錯(cuò)誤類型error 3如輸入It is 12輸 出 error 1 2 3 輸入 i am ,a student 輸由 4 2、 2、 編碼解 碼從鍵盤輸入一個(gè)英文句子，設(shè)計(jì)一個(gè)編碼、解碼程序。string編碼過(guò)程先鍵入一個(gè)正整數(shù) N1 0 and tb 0 do 當(dāng) 兩個(gè)表均不空時(shí) begin 比較兩表指針指向的項(xiàng)指數(shù)，輸由指 數(shù)小的項(xiàng)系數(shù)和指數(shù)，同時(shí)改變?cè)摫碇羔?if ata

5、.zhibtb.zhi then begin if ata.xi 0 then begin if btb.xi ata.xi 0 do 若有一表空，則輸由另一表的剩余項(xiàng) begin if ata.xi 0 dobegin if btb.xi nil and b nil do begin if a.zhi b.zhi then begin if a.xi 0 then begin if b.xi a.xi nil do begin if a.xi nil do begin if b.xi 0 and x0 and yw; 直至隊(duì)空為止 end; begin fillcharbz,sizeofbz

6、,true;num0; write input file ;readlnname; assignint,name;resetint;readlnint,m,n;for i1 to m dobegin readlnint,s;for j1 to n dobeginpici,jordsj-ord 0 ;if pici,j0then bzi,jfalse;end; end; closeint; for i1 to m do for j1 to n do if bzi,j then doingi,j; 在矩陣中尋找細(xì)胞 writeln NUMBER of cells ,num;readln; end.

7、（四）迭代與遞推本次我們想與大家共同探討一下迭代與遞推。在計(jì)算機(jī)數(shù)值程序設(shè)計(jì)中，迭代與遞推是兩個(gè)重要的基礎(chǔ)算法。一、迭代許多的實(shí)際問(wèn)題都能轉(zhuǎn)化為解方程Fx0的實(shí)數(shù)解的問(wèn)題。求根可以直接從方程由發(fā)，逐步縮小根的存在區(qū)間，把 根的近似值逐步精確到要以滿足具體實(shí)際問(wèn)題的需要為止， 該算法稱為迭代。迭代的一般原則可以用一個(gè)數(shù)學(xué)模型來(lái)描述，現(xiàn)要求由方程Fx0的解先設(shè)FxGx-x ,則方程Fx0可化為xGx ,這就 產(chǎn)生了一個(gè)迭代算法的數(shù)學(xué)模型Xn1G （X n）從奧一個(gè)數(shù)X0出發(fā),按此迭代模型，求由一個(gè)序列 X0, X1, X2, X3, Xn-2, X n-1 , Xn 當(dāng)X n Xn-1小于一個(gè)特定

8、值（誤差許可值）時(shí)，XXn-IXn,這時(shí)可認(rèn)定xGx o也就是說(shuō)，求生的X n已經(jīng)可以作為原方程 fx0根的近似 值了。設(shè)誤差許可值為 A,則迭代算法的 NS圖如圖1。圖1迭代算法NS框圖 迭代算 法的關(guān)鍵在于確定迭代函數(shù)Gx o確定Gx時(shí)需保證產(chǎn)生的迭代序列X n 是否能使兩個(gè)相鄰的數(shù)之間的差距越來(lái)越小（即兩數(shù)的差值越靠近誤差 值，我們稱這樣的序列為收斂序列），因?yàn)橹挥羞@樣才能使根的存在范圍越來(lái)越小，從而為根的取得創(chuàng)造條件。例1求2的算術(shù)平方根（不使用內(nèi)部函數(shù)）。分析使用迭代算法來(lái)解決這個(gè)問(wèn)題，使用迭代法可 以先設(shè)XSQRT2-1 ,則求2的算術(shù)平方根的近似值就可以轉(zhuǎn) 化為求XX21的正根。

9、列由等價(jià)方程 X1/X2 ,以1/X2為迭代函數(shù)，以 0為初 始近似值X 0,誤差值設(shè)定為0.0000001,則程序可寫成 program ex11_7; const a0.0000001; var x0,x1,Xreal; beginx00;x11/x02; while absx1-x0a do begin x0x1;x11/x02; end; xx11; 將 X1的值轉(zhuǎn)為 2的算術(shù)平方根 writeln sqrt2 ,x; end. 程序的輸生結(jié)果如下 SQRT21.4142135516E00開(kāi)始時(shí)，迭代函數(shù)的根的近似值設(shè)定在0,0.5之間，由于區(qū)間寬度大于給定誤差許可值，于 是再進(jìn)行迭代

10、運(yùn)算，產(chǎn)生下一個(gè)區(qū)間040.5;其寬度仍然大于誤差許可值，再產(chǎn)生下一個(gè)區(qū)間；如此反復(fù)，直到區(qū)間的寬度小于誤差給定值時(shí)，則表明在該區(qū)間中，任意選擇 一個(gè)數(shù)都可以滿足根的近似值要求了。為方便起見(jiàn)，取下該區(qū)間的邊界置作為近似值。這就是迭代算法的一般原則的體現(xiàn)了。二、.遞推 對(duì)于一個(gè)的序列來(lái)說(shuō)， 如果已知它的通項(xiàng)公 式（即表達(dá)位置與位置上的數(shù)據(jù)的關(guān)系的公式），那么，要求生數(shù)列中奧項(xiàng)之值是十分容易的。但是，在許多情況下，要得到數(shù)列的通項(xiàng)公式是很困難 的，甚至無(wú)法得到。然而，一個(gè)有規(guī)律的數(shù)列的相鄰位置上的數(shù)項(xiàng)之間通常 存在著一定的關(guān)系，我們可以借助已知的項(xiàng)，利用特定的關(guān) 系逐項(xiàng)推算由它的后繼項(xiàng)的值，如此反

11、復(fù)，直到找到所需 的那一項(xiàng)為止，這樣的方法稱為遞推算法。遞推算法的首要問(wèn)題是得到相鄰的數(shù)據(jù)項(xiàng)間的關(guān)系（即遞推關(guān)系）遞推算法避開(kāi)了求通項(xiàng)公項(xiàng)的麻煩，把一個(gè)復(fù)雜的問(wèn)題的求解，分解成了連續(xù)的若干步簡(jiǎn)單運(yùn)算。一般說(shuō)來(lái)，可以將遞推算法看成是一種特殊的迭代算法。例2著名的菲波納契Fibonacci數(shù)列，其第一項(xiàng)為0,第 二項(xiàng)為1,從第三項(xiàng)開(kāi)始，其每一項(xiàng)都是前兩項(xiàng)的和。編程求由該數(shù)列第 N項(xiàng)數(shù)據(jù)。分析按菲波納契數(shù)列的原則，數(shù)列為0 1 12 3 58 13 21 34 55無(wú)疑地，尋找其項(xiàng)數(shù)位置與項(xiàng)值的關(guān)系（即通項(xiàng)公式）是非常困難的。而根楣該數(shù)列的形成規(guī)則，其有一個(gè)的公式即bn = Un-1 + U n-2

12、襲明了相鄰的數(shù)據(jù)項(xiàng)之間的明顯關(guān)系。因此，可以其作為遞推公式，以已知項(xiàng) 0與1為起點(diǎn)， 逐項(xiàng)產(chǎn)生第3項(xiàng)、第4項(xiàng)、，直到取得需要的第 N項(xiàng)為止。在其遞推算法的語(yǔ)言實(shí)現(xiàn)上，可取J、K、P三個(gè)變量，分別表示前二項(xiàng)、前一項(xiàng)與當(dāng)前項(xiàng)，J、K分別取初值0與1。第一次通過(guò)遞推公式 PJK得到第三項(xiàng)，并進(jìn)行移位，即J 取K值、K取P值，為下次遞推作準(zhǔn)備；如此反復(fù)，經(jīng)過(guò) N-2次的遞推，P就是第N項(xiàng)的值（第1次產(chǎn)生的是3項(xiàng)的 值）。源程序如下 program ex11_8; var n,i,j,k,plongint; begin write N ;readlnn; i2;j0;k1; repeat inci;pj

13、k;jk;kp; until in;writeln F ,n,p; end,菲波納契數(shù)列的遞推明確地體現(xiàn)了遞推算法程序設(shè)計(jì)的一般原則，即遞推公式取得。例3數(shù)字三角形。如下所示為一個(gè)數(shù)字三角形。請(qǐng)編一個(gè)程序計(jì)算從頂?shù)降椎哪幍囊粭l路徑，使該路 徑所經(jīng)過(guò)的數(shù)字總和最大。只要求輸由總和。1、一步可沿左斜線向下或右斜線向下走；2、角形行數(shù)小于等于100;3、三角形中的數(shù)字為0,1, 99;測(cè)試數(shù)據(jù)通過(guò)鍵盤逐行輸入，如上例數(shù)據(jù)應(yīng)以如下所示格式 輸入 573 88 1 02 7 4 44 5 2 6 5 分析此題解法有多種，從遞推的思想由發(fā)，可以設(shè)想，當(dāng)從頂層 沿莫條路徑走到第I層向第I1層前進(jìn)時(shí)，我們的

14、選擇一定是 沿其下兩條可行路徑中最大數(shù)字的方向前進(jìn)，為此，我們可 以采用倒推的手法，設(shè) ai, j存放從i, j由發(fā)到達(dá)n層的最 大值，則 ai, jmaxai , jai1 , j, ai, jai1 , j1 , a1, 1即為所求的數(shù)字總和的最大值。源 程序如 下 program ex11_9; var n,j,iinteger; aarray1.100,1.,100 of integer; begin readn; for i1 to n do for j1 to i do readai,j; for in-1 downto 1 do for j1 to i do begin if a

15、i1,jai1,j1 then ai,j ai,jai1,j else ai,jai,jai1,j1; end; writelna1,1; end.（五） 遞歸 在（四）中，我們了解了迭代與遞推。與迭代、遞推相對(duì)應(yīng)的算法為遞歸，本趣談數(shù)據(jù)結(jié)構(gòu)， 我們就來(lái)談一談遞歸算法。遞歸算法作為計(jì)算機(jī)程序設(shè)計(jì)中的一種重要的算法，是 較難理解的算法之一。簡(jiǎn)單地說(shuō)，遞歸就是編寫這樣的一個(gè)特殊的過(guò)程，該過(guò) 程體中有一個(gè)語(yǔ)句用于調(diào)用過(guò)程自身（稱為遞歸調(diào)用）。遞歸過(guò)程由于實(shí)現(xiàn)了自我的嵌套執(zhí)行，使這種過(guò)程的執(zhí) 行變得復(fù)雜起來(lái)，其執(zhí)行的流程可以用圖1所示。圖1遞歸過(guò)程的執(zhí)行流程 從圖1可以看由，遞歸過(guò) 程的執(zhí)行總是一個(gè)過(guò)

16、程體未執(zhí)行完，就帶著本次執(zhí)行的結(jié)果又進(jìn)入另一輪過(guò)程體的執(zhí)行，如此反復(fù)，不斷深入，直 到莫次過(guò)程的執(zhí)行遇到終止遞歸調(diào)用的條件成立時(shí)，則不再 深入，而執(zhí)行本次的過(guò)程體余下的部分，然后又返回到上一 次調(diào)用的過(guò)程體中，執(zhí)行其余下的部分，如此反復(fù)，直到回到起始位置上，才最終結(jié)束整個(gè)遞歸過(guò)程的執(zhí)行，得到相 應(yīng)的執(zhí)行結(jié)果。遞歸過(guò)程的程序設(shè)計(jì)的核心就是參照這種執(zhí)行流程，設(shè) 計(jì)由一種適合 逐步深入，而后又逐步返回 的遞歸調(diào)用模型， 以解決實(shí)際問(wèn)題。利用遞歸調(diào)用程序設(shè)計(jì)技術(shù)可以解決很復(fù)雜但規(guī)律性 很強(qiáng)的問(wèn)題，并且可以使程序變得十分簡(jiǎn)短。例1利用遞歸調(diào)用手段編程計(jì)算No分析根楣數(shù)學(xué)知識(shí)，11,正整數(shù)N的階乘為 N*

17、N-1*N-2*2*1 , 該階乘序列可轉(zhuǎn)換為求 N*N-1 ,而N-1 以可轉(zhuǎn)換為 N-1*N-2 一 直至轉(zhuǎn)換為 2*1 ,而11。源程序如下 program ex11_10; var nbyte; textended; procedure findnbyte; begin if n1 then t1 else begin findn-1;tt*n; end; end; begin write N ;readlnn; findn; writeln N ,t10; end. 在過(guò)程find中，當(dāng)N1時(shí)，又調(diào)用過(guò)程 find,參數(shù)為N-1 -這種操作一直持續(xù)到N1為止。例如當(dāng)N5時(shí)，find5

18、的值變?yōu)?*find4 , 求find 4又 變?yōu)?*find3 一當(dāng)N 1時(shí)遞歸停止，逐步返回到第一次調(diào)用 的初始處，返回結(jié)果 5*4*3*2*1 ,即5。例2利用遞歸調(diào)用技術(shù)求菲波納契數(shù)列的第N項(xiàng)。分析我們已經(jīng)知道菲波納契數(shù)列的各數(shù)列的產(chǎn)生可用 下列公式表示U 1 = 0 U 2= 1 U n = U n-1 +U n-2（當(dāng)n2時(shí)） 因此當(dāng)N大于2時(shí)，求第N項(xiàng)值可轉(zhuǎn)化為求 第N-1項(xiàng)值與第N-2項(xiàng)值的和；而求第N-1項(xiàng)又可轉(zhuǎn)化為求N-2項(xiàng)值與N-3項(xiàng)的和，相應(yīng)地，求 N-2項(xiàng)值可轉(zhuǎn)化為求 N-3項(xiàng)值和N-4項(xiàng)值的和；如此反復(fù)，直至轉(zhuǎn)化為求第1項(xiàng)或第2項(xiàng)值，而第1項(xiàng)與第2項(xiàng)為已知值1和2。

19、if源程序 program ex11_11; var nbyte; aarray1.100 of longint; function fnbytelongint; var ilongint; begin an-10 then ian-1 else ifn-1; if an-20 then iian-2 else iifn-2; ani;fi; end; begin write N ;readlnn; fillchara,sizeofa,0; a11;a21; writeln F ,n, ,fn; end. 本 程序采用了函數(shù)遞歸，函數(shù) F的執(zhí)行比較復(fù)雜。函數(shù)F由于存在著兩次的遞歸調(diào)用，使遞歸調(diào)

20、用廣生執(zhí)行流程的 上叉樹(shù) 行式，大家可參照?qǐng)D2來(lái)理解這個(gè)執(zhí)行過(guò) 程。為方便起見(jiàn)，設(shè)定N5,圖中的數(shù)碼表示遞歸執(zhí)行的順序。圖2F函數(shù)的 上叉樹(shù) 執(zhí)行流程 遞歸調(diào)用技術(shù)的運(yùn)用， 是在犧牲計(jì)算機(jī)內(nèi)存空間和程序執(zhí)行速度的基礎(chǔ)上得到的。因?yàn)樵谶f歸調(diào)用的執(zhí)行過(guò)程中，系統(tǒng)必須花費(fèi)時(shí)間與空 間以棧的方式記下每次調(diào)用的返回位置地址及每一次過(guò)程 執(zhí)行的中間結(jié)果，以便當(dāng)遞歸調(diào)用終止條件成立時(shí)，能沿著逐步深入的路線逐步返回；取得這些數(shù)據(jù)，最終準(zhǔn)確地 回到初始調(diào)用處。比如，同是解決菲波納契數(shù)列問(wèn)題的程序，使用遞推就 比使用遞歸算法設(shè)計(jì)的程序執(zhí)行速度快了許多。當(dāng)一個(gè)問(wèn)題蘊(yùn)含著遞歸關(guān)系且結(jié)構(gòu)比較復(fù)雜時(shí)，采用 一般的算法，不僅給程序的設(shè)計(jì)帶來(lái)許多困難，而且也會(huì)給 設(shè)計(jì)生的程序帶來(lái)篇幅大、可讀性差的缺點(diǎn)，這時(shí)采用遞歸 調(diào)用技術(shù)來(lái)設(shè)計(jì)程序則會(huì)帶來(lái)相反的效果。例3相傳在古印度的布拉瑪婆羅門圣廟的僧侶在進(jìn)行一種被稱為漢諾塔的游戲，具裝置是一塊銅板，上面有三根桿（編號(hào)A、B、C）, A桿上自下而上、由大到小按順序串 上64個(gè)金盤（如圖3）。游戲的目標(biāo)是把【演示程序 DEM00_02,rar 1 A桿上的金盤全部移到C桿上，并仍原有順序疊好。條件是每次只能移動(dòng)一個(gè)盤，并且在每