1、數據結構的在程序設計中的應用長沙市一中 肖洲【關鍵字】 邏輯結構 存儲結構 算法優化【摘要】 數據結構作為程序設計的基礎，其對算法效率的影響必然是不可忽視的。本文就如何合理選擇數據結構來優化算法這一問題，對選擇數據結構的原則和方法進行了一些探討。首先對數據邏輯結構的重要性進行了分析，提出了選擇邏輯結構的兩個基本原則；接著又比較了順序和鏈式兩種存儲結構的優點和缺點，并討論了選擇數據存儲結構的方法；最后本文從選擇數據結構的的另一角度出發，進一步探討了如何將多種數據結構進行結合的方法。在討論方法的同時，本文還結合實際，選用了一些較具有代表性的信息學競賽試題舉例進行了分析【正文】一、引論“數據結構算法

2、程序”，這就說明程序設計的實質就是對確定的問題選擇一種合適的數據結構，加上設計一種好的算法。由此可見，數據結構在程序設計中有著十分重要的地位。數據結構是相互之間存在一種或多種特定關系的數據元素的集合。因為這其中的“關系”，指的是數據元素之間的邏輯關系，因此數據結構又稱為數據的邏輯結構。而相對于邏輯結構這個比較抽象的概念，我們將數據結構在計算機中的表示又稱為數據的存儲結構。建立問題的數學模型，進而設計問題的算法，直至編出程序并進行調試通過，這就是我們解決信息學問題的一般步驟。我們要建立問題的數學模型，必須首先找出問題中各對象之間的關系，也就是確定所使用的邏輯結構；同時，設計算法和程序實現的過程，

3、必須確定如何實現對各個對象的操作，而操作的方法是決定于數據所采用的存儲結構的。因此，數據邏輯結構和存儲結構的好壞，將直接影響到程序的效率。二、選擇合理的邏輯結構在程序設計中，邏輯結構的選用就是要分析題目中的數據元素之間的關系，并根據這些特定關系來選用合適的邏輯結構以實現對問題的數學描述，進一步解決問題。邏輯結構實際上是用數學的方法來描述問題中所涉及的操作對象及對象之間的關系，將操作對象抽象為數學元素，將對象之間的復雜關系用數學語言描述出來。根據數據元素之間關系的不同特性，通常有以下四種基本邏輯結構：集合、線性結構、樹形結構、圖狀（網狀）結構。這四種結構中，除了集合中的數據元素之間只有“同屬于一

4、個集合”的關系外，其它三種結構數據元素之間分別為“一對一”、“一對多”、“多對多”的關系。因此，在選擇邏輯結構之前，我們應首先把題目中的操作對象和對象之間的關系分析清楚，然后再根據這些關系的特點來合理的選用邏輯結構。尤其是在某些復雜的問題中，數據之間的關系相當復雜，且選用不同邏輯結構都可以解決這一問題，但選用不同邏輯結構實現的算法效率大不一樣。對于這一類問題，我們應采用怎樣的標準對邏輯結構進行選擇呢？下文將探討選擇合理邏輯結構應充分考慮的兩個因素。一、 充分利用“可直接使用”的信息。首先，我們這里所講的“信息”，指的是元素與元素之間的關系。對于待處理的信息，大致可分為“可直接使用”和“不可直接

5、使用”兩類。對于“可直接使用”的信息，我們使用時十分方便，只需直接拿來就可以了。而對于“不可直接使用”的這一類，我們也可以通過某些間接的方式，使之成為可以使用的信息，但其中轉化的過程顯然是比較浪費時間的。由此可見，我們所需要的是盡量多的“可直接使用”的信息。這樣的信息越多，算法的效率就會越高。對于不同的邏輯結構，其包含的信息是不同的，算法對信息的利用也會出現不同的復雜程度。因此，要使算法能夠充分利用“可直接使用”的信息，而避免算法在信息由“不可直接使用”向“可直接使用”的轉化過程中浪費過多的時間，我們必然需要采用一種合理的邏輯結構，使其包含更多“可直接使用”的信息。問題一 IOI99的隱藏的碼

6、字。問題描述問題中給出了一些碼字和一個文本，要求編程找出文本中包含這些碼字的所有項目，并將找出的項目組成一個最優的“答案”，使得答案中各項目所包含的碼字長度總和最大。每一個項目包括一個碼字，以及該碼字在文本中的一個覆蓋序列（如abcadc就是碼字abac的一個覆蓋序列），并且覆蓋序列的長度不超過1000。同時，“答案”要求其中每個項目的覆蓋序列互相沒有重疊。問題分析對于此題，一種較容易得出的基本算法是：對覆蓋序列在文本中的終止位置進行循環，再判斷包含了哪些碼字，找出所有項目，并最后使用動態規劃的方法將項目組成最優的“答案”。算法的其它方面我們暫且不做考慮，而先對問題所采用的邏輯結構進行選擇。如

7、果我們采用線性的邏輯結構（如循環隊列），那么我們在判斷是否包含某個碼字t時，所用的方法為：初始時用指針p指向終止位置，接著通過p的不斷前移，依次找出碼字t從尾到頭的各個字母。例如碼字為“ABDCAB”，而文本圖1-1，終止位置為最右邊的箭頭符號，每個箭頭代表依次找到的碼字的各個字母。指針p的移動方向 A B D C A BCDACBDCADCDBADCCBAD圖1-1由于題目規定碼字的覆蓋序列長度不超過1000，所以進行這樣的一次是否包含的判斷，其復雜度為O(1000)。由于碼字t中相鄰兩字母在文本中的位置，并非只有相鄰(如圖1-1中的D和C)這一種關系，中間還可能間隔了許多的字母(如圖1-1

8、中C和A就間隔了2個字母)，而線性結構中擁有的信息，僅僅只存在于相鄰的兩元素之間。通過這樣簡單的信息來尋找碼字的某一個字母，其效率顯然不高。如果我們建立一個有向圖，其中頂點i(即文本的第i位)用52條弧分別連接a.z,A.Z這52個字母在i位以前最后出現的位置（如圖1-2的連接方式），我們要尋找碼字中某個字母的前一個字母，就可以直接利用已連接的邊，而不需用枚舉的方法。我們也可以把問題看為：從有向圖的一個頂點出發，尋找一條長度為length(t)-1的路徑，并且路徑中經過的頂點，按照碼字t中的字母有序。CDACBDCADCDBADCCBAD圖1-2通過計算，用圖進行記錄在空間上完全可以承受(記錄

9、1000個點52條弧4字節的長整型=200k左右)。在時間上，由于可以充分利用第i位和第i+1位弧的連接方式變化不大這一點(如圖1-2所示，第i位和第i+1位只有一條弧的指向發生了變化，即第i+1位將其中一條弧指向了第i位)，所以要對圖中的弧進行記錄，只需對弧的指向進行整體賦值，并改變其中的某一條弧即可。因此，我們通過采用圖的邏輯結構，使得尋找字母的效率大大提高，其判斷的復雜度為O(length(t)，最壞為O(100)，比原來方法的判斷效率提高了10倍。（附程序codes.pas）對于這個例子，雖然用線性的數據結構也可以解決，但由于判斷的特殊性，每次需要的信息并不能從相鄰的元素中找到，而線性

10、結構中只有相鄰元素之間存在關系的這一點，就成為了一個很明顯的缺點。因此，問題一線性結構中的信息，就屬于“不可直接使用”的信息。相對而言，圖的結構就正好滿足了我們的需要，將所有可能產生關系的點都用弧連接起來，使我們可以利用弧的關系，高效地進行判斷尋找的過程。雖然圖的結構更加復雜，但卻將“不可直接使用”的信息，轉化成為了“可直接使用”的信息，算法效率的提高，自然在情理之中。二、 不記錄“無用”信息。從問題一中我們看到，由于圖結構的信息量大，所以其中的信息基本上都是“可用”的。但是，這并不表示我們就一定要使用圖的結構。在某些情況下，圖結構中的“可用”信息，是有些多余的。信息都“可用”自然是好事，但倘

11、若其中“無用”（不需要）的信息太多，就只會增加我們思考分析和處理問題時的復雜程度，反而不利于我們解決問題了。問題二 湖南省1997年組隊賽的乘船問題問題描述有N個人需要乘船，而每船最多只能載兩人，且必須同名或同姓。求最少需要多少條船。問題分析看到這道題，很多人都會想到圖的數據結構：將N個人看作無向圖的N個點，凡同名或同姓的人之間都連上邊。要滿足用船最少的條件，就是需要盡量多的兩人共乘一條船，表現在圖中就是要用最少的邊完成對所有頂點的覆蓋。這就正好對應了圖論的典型問題：求最小邊的覆蓋。所用的算法為“求任意圖最大匹配”的算法。使用“求任意圖最大匹配”的算法比較復雜(要用到擴展交錯樹，對花的收縮等等

12、)，效率也不是很高。因此，我們必須尋找一個更簡單高效的方法。首先，由于圖中任兩個連通分量都是相對獨立的，也就是說任一條匹配邊的兩頂點，都只屬于同一個連通分量。因此，我們可以對每個連通分量分別進行處理，而不會影響最終的結果。同時，我們還可以對需要船只s的下限進行估計：對于一個包含Pi個頂點的連通分量，其最小覆蓋邊數顯然為Pi/2。若圖中共有L個連通分量，則s=Pi/2(1=i=L)。 然后，我們通過多次嘗試，可得出一個猜想：實際需要的覆蓋邊數完全等于我們求出的下限Pi/2(1=i0)表示lcp,i-1的左兒子，顯然lcp,i與p是同姓的。假設存在某個點q，滿足qs且qT。由于s是有限集合，因而必

13、然存在某個lcp,k無左兒子。則我們可以令lcp,k+1=q，所以qT，與假設qT相矛盾。所以假設不成立，原命題得證。由引理2.1的證明方法，我們同理可證引理2.2。【引理2.2】若二叉樹T中包含了某個結點p，那么連通分量中所有與p同名的點一定都在T中。有了上面的兩個引理，我們就不難得出下面的定理了。【定理一】以連通分量中的任一點p作為根結點的二叉樹，必然能夠包含連通分量中的所有頂點。證明：由引理2.1和引理2.2，所有與p同姓或同名的點都一定在二叉樹中，即連通分量中所有與p有邊相連的點都在二叉樹中。由連通分量中任兩點間都存在路徑的特性，該連通分量中的所有點都在二叉樹中。在證明二叉樹中包含了連

14、通分量的所有頂點后，我們接著就需要證明我們的猜想，也就是下面的定理：【定理二】包含m個結點的二叉樹Tm，只需要船的數量為boatm=m/2(mN)。證明：(i) 當m=1,m=2,m=3時命題顯然成立。 圖2-2-1 圖2-2-2 圖2-2-3(ii) 假設當m3)時命題成立，那么當m=k時，我們首先從樹中找到一個層次最深的結點，并假設這個結點的父親為p。那么，此時有且只有以下三種情況（結點中帶有陰影的是p結點）：(1) 如圖2-2-1，p只有一個兒子。此時刪去p和p唯一的兒子，Tk就成為了Tk-2，則boatk=boatk-2+1=(k-2)/2+1=k/2。(2) 如圖2-2-2，p有兩個

15、兒子，并且p是其父親的左兒子。此時可刪去p和p的右兒子，并可將p的左兒子放到p的位置上。同樣地，Tk成為了Tk-2，boatk=boatk-2+1=k/2。(3) 如圖2-2-3，p有兩個兒子，并且p是其父親的右兒子。此時可刪去p和p的左兒子，并可將p的右兒子放到p的位置上。情況與(2)十分相似，易得此時得boatk=boatk-2+1=k/2。綜合(1)、(2)、(3)，當m=k時，boatk=k/2。最后，綜合(i)、(ii)，對于一切mN，boatm=m/2。由上述證明，我們將問題中數據的圖結構轉化為樹結構后，可以得出求一棵二叉樹的乘船方案的算法：proc try(father:inte

16、ger;var root:integer;var rest:byte);輸出root為樹根的子樹的乘船方案，father=0表示root是其父親的左兒子，father=1表示root是其父親的右兒子，rest表示輸出子樹的乘船方案后，是否還剩下一個根結點未乘船beginvisitroot:=true; 標記root已訪問找到一個與root同姓且未訪問的結點j; if jn+1 then try(0,j,lrest);找到一個與root同姓且未訪問的結點k; if kn+1 then try(1,k,rrest);if (lrest=1) xor (rrest=1) then begin 判斷r

17、oot是否只有一個兒子，情況一if lrest=1 then print(lrest,root) else print(rrest,root);rest:=0;endelse if (lrest=1) and (rrest=1) then begin 判斷root是否有兩個兒子if father=0 then beginprint(rrest,root);root:=j; 情況二endelse beginprint(lrest,root);root:=k; 情況三end;rest:=1;endelse rest:=1;end;這只是輸出一棵二叉樹的乘船方案的算法，要輸出所有人的乘船方案，我們還

18、需再加一層循環，用于尋找各棵二叉樹的根結點，但由于每個點都只會訪問一次，尋找其左右兒子各需進行一次循環，所以算法的時間復雜度為O(n2)。（附程序boat.pas）最后，我們對兩種結構得出不同時間復雜度算法的原因進行分析。其中最關鍵的一點就是因為二叉樹雖然結構相對較簡單，但已經包含了幾乎全部都“有用”的信息。由我們尋找乘船方案的算法可知，二叉樹中的所有邊不僅都發揮了作用，而且沒有重復的使用，可見信息的利用率也是相當之高的。既然采用樹結構已經足夠，圖結構中的一些信息就顯然就成為了“無用”的信息。這些多余的“無用”信息，使我們在分析問題時難于發現規律，也很難找到高效的算法進行解決。這正如迷宮中的墻

19、一樣，越多越難走。“無用”的信息，只會干擾問題的規律性，使我們更難找出解決問題的方法。小結我們對數據的邏輯結構進行選擇，是構造數學模型一大關鍵，而算法又是用來解決數學模型的。要使算法效率高，首先必須選好數據的邏輯結構。上面已經提出了選擇邏輯結構的兩個條件（思考方向），總之目的是提高信息的利用效果。利用“可直接使用”的信息，由于中間不需其它操作，利用的效率自然很高；不不記錄“無用”的信息，就會使我們更加專心地研究分析“有用”的信息，對信息的使用也必然會更加優化。總之，在解決問題的過程中，選擇合理的邏輯結構是相當重要的環節。三、 選擇合理的存儲結構數據的存儲結構，分為順序存儲結構和鏈式存儲結構。順

20、序存儲結構的特點是借助元素在存儲器中的相對位置來表示數據元素之間的邏輯關系；鏈式存儲結構則是借助指示元素存儲地址的指針表示數據元素之間的邏輯關系。因為兩種存儲結構的不同，導致這兩種存儲結構在具體使用時也分別存在著優點和缺點。這里有一個較簡單的例子：我們需要記錄一個nn的矩陣，矩陣中包含的非0元素為m個。此時，我們若采用順序存儲結構，就會使用一個nn的二維數組，將所有數據元素全部記錄下來；若采用鏈式存儲結構，則需要使用一個包含m個結點的鏈表，記錄所有非0的m個數據元素。由這樣兩種不同的記錄方式，我們可以通過對數據的不同操作來分析它們的優點和缺點。1 隨機訪問矩陣中任意元素。由于順序結構在物理位置

21、上是相鄰的，所以可以很容易地獲得任意元素的存儲地址，其復雜度為O(1)；對于鏈式結構，由于不具備物理位置相鄰的特點，所以首先必須對整個鏈表進行一次遍歷，尋找需進行訪問的元素的存儲地址，其復雜度為O(m)。此時使用順序結構顯然效率更高。2 對所有數據進行遍歷。兩種存儲結構對于這種操作的復雜度是顯而易見的，順序結構的復雜度為O(n2)，鏈式結構為O(m)。由于在一般情況下m要遠小于n2，所以此時鏈式結構的效率要高上許多。除上述兩種操作外，對于其它的操作，這兩種結構都不存在很明顯的優點和缺點，如對鏈表進行刪除或插入操作，在順序結構中可表示為改變相應位置的數據元素。既然兩種存儲結構對于不同的操作，其效

22、率存在較大的差異，那么我們在確定存儲結構時，必須仔細分析算法中操作的需要，合理地選擇一種能夠“揚長避短”的存儲結構。一、合理采用順序存儲結構。我們在平常做題時，大多都是使用順序存儲結構對數據進行存儲。究其原因，一方面是出于順序結構操作方便的考慮，另一方面是在程序實現的過程中，使用順序結構相對于鏈式結構更便于對程序進行調試和查找錯誤。因此，大多數人習慣上認為，能夠使用順序結構進行存儲的問題，最“好”采用順序存儲結構。其實，這個所謂的“好”只是一個相對的標準，是建立在以下兩個前提條件之下的：1 鏈式結構存儲的結點與順序結構存儲的結點數目相差不大。這種情況下，由于存儲的結點數目比較接近，使用鏈式結構

23、完全不能體現出記錄結點少的優點，并且可能會由于指針操作較慢而降低算法的效率。更有甚者，由于指針自身占用的空間較大，且結點數目較多，因而算法對空間的要求可能根本無法得到滿足。2 并非算法效率的瓶頸所在。由于不是算法最費時間的地方，這里是否進行改進，顯然是不會對整個算法構成太大影響的，若使用鏈式結構反而會顯得操作過于繁瑣。二、必要時采用鏈式存儲結構。上面我對使用順序存儲結構的條件進行了分析，最后就只剩下何時應該采用鏈式存儲結構的問題了。由于鏈式結構中指針操作確實較繁瑣，并且速度也較慢，調試也不方便，因而大家一般都不太愿意用鏈式的存儲結構。但是，這只是一般的觀點，當鏈式結構確實對算法有很大改進時，我

24、們還是不得不進行考慮的。問題三 IOI99的地下城市。問題描述已知一個城市的地圖，但未給出你的初始位置。你需要通過一系列的移動和探索，以確定初始時所在的位置。題目的限制是：1 不能移動到有墻的方格。2 只能探索當前所在位置四個方向上的相鄰方格。在這兩個限制條件下，要求我們的探索次數（不包括移動）盡可能的少。問題分析由于存儲結構要由算法的需要確定，因此我們首先來確定問題的算法。經過對問題的分析，我們得出解題的基本思想：先假設所有無墻的方格都可能是初始位置，再通過探索一步步地縮小初始位置的范圍，最終得到真正的初始位置。同時，為提高算法效率，我們還用到了分治的思想，使我們每一次探索都盡量多的縮小初始

25、位置的范圍(使程序盡量減少對運氣的依賴)。接著，我們來確定此題的存儲結構。由于這道題的地圖是一個二維的矩陣，所以一般來講，采用順序存儲結構理所當然。但是，順序存儲結構在這道題中暴露了很大的缺點。我們所進行的最多的操作，一是對初始位置的范圍進行篩選，二是判斷要選擇哪個位置進行探索。而這兩種操作，所需要用到的數據，只是龐大地圖中很少的一部分。如果采用順序存儲結構(如圖3-1中陰影部分表示已標記)，無論你需要用到多少數據，始終都要完全的遍歷整個地圖。 4 3 2 1 1 2 3 4 圖3-1 head(2,2)(2,3)(3,4)(4,1) 圖3-2然而，如果我們采用的是鏈式存儲結構(如圖3-2的鏈

26、表)，那么我們需要多少數據，就只會遍歷多少數據，這樣不僅充分發揮了鏈式存儲結構的優點，而且由于不需單獨對某一個數據進行提取，每次都是對所有數據進行判斷，從而避免了鏈式結構的最大缺點。我們使用鏈式存儲結構，雖然沒有降低問題的時間復雜度(鏈式存儲結構在最壞情況下的存儲量與順序存儲結構的存儲量幾乎相同)，但由于體現了前文所述選擇存儲結構時揚長避短的原則，因而算法的效率也大為提高。（程序對不同數據的運行時間見表3-3）測試數據編號使用順序存儲結構的程序使用鏈式存儲結構的程序10.06s0.02s21.73s0.07s31.14s0.06s43.86s0.14s532.84s0.21s6141.16s0

27、.23s70.91s0.12s86.92s0.29s96.10s0.23s1017.41s0.20s表3-3（附使用鏈式存儲結構的程序under.pas）我們選擇鏈式的存儲結構，雖然操作上可能稍復雜一些，但由于改進了算法的瓶頸，算法的效率自然也今非昔比。由此可見，必要時選擇鏈式結構這一方法，其效果是不容忽視的。小結合理選擇邏輯結構，由于牽涉建立數學模型的問題，可能大家都會比較注意。但是對存儲結構的選擇，由于不會對算法復雜度構成影響，所以比較容易忽視。那么，這種不能降低算法復雜度的方法是否需要重視呢？大家都知道，剪枝作為一種常用的優化算法的方法，被廣泛地使用，但剪枝同樣是無法改變算法的復雜度的。

28、因此，作用與剪枝相似的存儲結構的合理選擇，也是同樣很值得重視的。總之，我們在設計算法的過程中，必須充分考慮存儲結構所帶來的不同影響，選擇最合理的存儲結構。四、 多種數據結構相結合上文所探討的，都是如何對數據結構進行選擇，其中包含了邏輯結構的選擇和存儲結構的選擇，是一種具有較大普遍性的算法優化方法。對于多數的問題，我們都可以通過選擇一種合理的邏輯結構和存儲結構以達到優化算法的目的。但是，有些問題卻往往不如人愿，要對這類問題的數據結構進行選擇，常常會顧此失彼，有時甚至根本就不存在某一種合適的數據結構。此時，我們是無法選擇出某一種合適的數據結構的，以上的方法就有些不太適用了。為解決數據結構難以選擇的

29、問題，我們可以采用將多種數據結構進行結合的方法。通過多種數據結構相結合，達到取長補短的作用，使不同的數據結構在算法中發揮出各自的優勢。這只是我們將多種數據結構進行結合的總思想，具體如何進行結合，我們可以先看下面的例子。問題四 廣東省97年省賽的最小序列問題。問題描述給定一個NN（N=100）的正整數矩陣。需要在矩陣中尋找一條從起始位置到終止位置的路徑(可沿上下左右四個方向)，并且要求路徑中經過的所有數字，其相鄰數字之差的絕對值之和最小。問題分析這道題的基本算法很簡單，只要用Dijkstra算法求出從起始位置到終止位置的最短路徑即可。但這當中存在一個很大的問題：Neec表示首字母為c的碼字不在碼

30、字列表中 no:array1.100 of byte;noi-排序后列表中第i個碼字在原列表中的位置 ss,tt:arr1; nn:arr2; ssi,tti,nni分別記錄找到的第i個項目中的覆蓋序列的首位置， 尾位置和其對應碼字在排序后的碼字列表中的編號 f:text; b:char;procedure readcod;讀入碼字列表并對其進行排序var f:text; i,j,k,l:integer; st:string;begin assign(f,st11);reset(f); readln(f,n); for i:=1 to n do begin readln(f,ti);noi:=

31、i; end; fillchar(bb,sizeof(bb),1); fillchar(ee,sizeof(ee),0); 初始時,令所有bbceec,以后找到字母c后再改變bbc和eec的值 for i:=1 to n do begin k:=i; for j:=i+1 to n do 按尾字母進行排序,在尾字母相同時按碼字由長到短排序 if (tj,length(tj)length(tk) then k:=j; if ik then begin st:=ti;ti:=tk;tk:=st; l:=noi;noi:=nok;nok:=l; end; 下面的判斷為確定對應各尾字母的碼字在新列表中

32、的位置 if ti,length(ti)=b then inc(eeb) else begin b:=ti,length(ti);bbb:=i;eeb:=i; end; end; close(f);end;procedure find(st,ed:longint;e:char); 尋找項目的過程 ,已確定其終止位置為ed,初始位置不小于st， 其包含的碼字的尾字母為evar i,k,l:integer; j:longint; can:boolean;begin for k:=bbe to eee do begin j:=ed;i:=length(tk)-1; while (i0) and (j

33、=st) do begin j:=lastj and maxtk,i;dec(i); end; 依次找出碼字的各字母 if j=st then begin l:=m;can:=true; while (l0) and (ttl=j) do begin if (ssl=j) and (length(tnnl)=length(tk) then begin can:=false;break; end; dec(l); end; 對找出的項目進行擇優，若can=false表示新找到的項目不如以前的 if can then begin inc(m);ssm:=j;ttm:=ed;nnm:=k; end;

34、 end; end;end;procedure findanswer; 求最優“答案”var i,j,k:integer; f:text; len,next:arr1; leni表示在前i個項目(不必包含i)中得出的最優“答案”包含的碼字長度 leni=max(lenj)+項目i的碼字長度(ij0) and (ttj=ssi) do dec(j); if lenj+length(tnni)leni then begin 判斷選第i個項目是否更優 leni:=lenj+length(tnni);nexti:=j; end; end; assign(f,st2);rewrite(f); write

35、ln(f,lenm); 輸出“答案”的總和值 k:=m; 尋找“答案”中所包含的各個項目 while k0 do begin while lenk=lenk-1 do dec(k);等式成立時不必選項目k writeln(f,nonnk, ,ssk, ,ttk); k:=nextk; end; close(f);end;begin readcod; new(ss);new(tt);new(nn); assign(f,st12); settextbuf(f,buf); reset(f); fillchar(nearest,sizeof(nearest),0); for i:=0 to max d

36、o begin new(lasti);fillchar(lasti,sizeof(lasti),0); end; 初始化 while not seekeoln(f) do begin inc(now); lastnow and max:=nearest; read(f,b);nearestb:=now; 將最后一次出現字母b的位置更新為now if bbb=1000 then find(now-999,now,b) else find(1,now,b); 確定起始位置的下限max(now-999,1)，并對項目進行尋找 end; close(f); findanswer;end.程序2乘船問題

37、（采用二叉樹結構）：boat.pas本題輸入文件的格式為：第一行為總人數，以下每行為一個人的姓和名，中間用一個空格分開(姓和名分別為長度不超過5和10的字符串)。輸出文件每行給出了一艘船上坐船的人的姓名，最后一行為需要船只的總數。$A+,B-,D+,E+,F-,G-,I-,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+$M 65520,0,655360const Maxn=5000; 最多的人數type Fnamearr=array1.Maxn of string5; Gnamearr=array1.Maxn of string10;var Fname:Fnamearr; 記錄每個

38、人的姓 Gname:Gnamearr; 記錄每個人的名 visit:array1.Maxn of boolean; visiti記錄第i個人是否已訪問過 total,n:integer; total-需要船的數目，n-總人數 fo:text;procedure init; 讀入所有人的姓名var f:text; st,t:string; i,j:integer;begin new(Fname);new(Gname); write(Input file name:);readln(st);assign(f,st);reset(f); readln(f,n); for i:=1 to n do b

39、egin readln(f,t); j:=pos( ,t); Fnamei:=copy(t,1,j-1); delete(t,1,j); Gnamei:=t; end; close(f);end;procedure print(i,j:integer); 輸出i和j同坐一條船var t:integer;begin t:=17-length(Fnamei)-length(Gnamei); writeln(fo,Fnamei, ,Gnamei,:t,- ,Fnamej, ,Gnamej); inc(total);end;procedure try(father:integer;var root:integer;var rest:byte); 建立以root為根結點的子樹，并輸出在這棵子樹中的所有人的乘船方案 father表示root是其父親的哪個兒子，0表示左兒子，1表示右兒子 rest表示在輸出該子樹中所有人的乘船方案以后，是否有一個人獨坐一