算法合集之《數(shù)據(jù)結(jié)構(gòu)的在程序設(shè)計(jì)中的應(yīng)用》

1、數(shù)據(jù)結(jié)構(gòu)的在程序設(shè)計(jì)中的應(yīng)用長(zhǎng)沙市一中 肖洲【關(guān)鍵字】 邏輯結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu) 算法優(yōu)化【摘要】 數(shù)據(jù)結(jié)構(gòu)作為程序設(shè)計(jì)的基礎(chǔ)，其對(duì)算法效率的影響必然是不可忽視的。本文就如何合理選擇數(shù)據(jù)結(jié)構(gòu)來(lái)優(yōu)化算法這一問(wèn)題，對(duì)選擇數(shù)據(jù)結(jié)構(gòu)的原則和方法進(jìn)行了一些探討。首先對(duì)數(shù)據(jù)邏輯結(jié)構(gòu)的重要性進(jìn)行了分析，提出了選擇邏輯結(jié)構(gòu)的兩個(gè)基本原則；接著又比較了順序和鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)和缺點(diǎn)，并討論了選擇數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的方法；最后本文從選擇數(shù)據(jù)結(jié)構(gòu)的的另一角度出發(fā)，進(jìn)一步探討了如何將多種數(shù)據(jù)結(jié)構(gòu)進(jìn)行結(jié)合的方法。在討論方法的同時(shí)，本文還結(jié)合實(shí)際，選用了一些較具有代表性的信息學(xué)競(jìng)賽試題舉例進(jìn)行了分析【正文】一、引論“數(shù)據(jù)結(jié)構(gòu)算法

2、程序”，這就說(shuō)明程序設(shè)計(jì)的實(shí)質(zhì)就是對(duì)確定的問(wèn)題選擇一種合適的數(shù)據(jù)結(jié)構(gòu)，加上設(shè)計(jì)一種好的算法。由此可見(jiàn)，數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中有著十分重要的地位。數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。因?yàn)檫@其中的“關(guān)系”，指的是數(shù)據(jù)元素之間的邏輯關(guān)系，因此數(shù)據(jù)結(jié)構(gòu)又稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。而相對(duì)于邏輯結(jié)構(gòu)這個(gè)比較抽象的概念，我們將數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示又稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。建立問(wèn)題的數(shù)學(xué)模型，進(jìn)而設(shè)計(jì)問(wèn)題的算法，直至編出程序并進(jìn)行調(diào)試通過(guò)，這就是我們解決信息學(xué)問(wèn)題的一般步驟。我們要建立問(wèn)題的數(shù)學(xué)模型，必須首先找出問(wèn)題中各對(duì)象之間的關(guān)系，也就是確定所使用的邏輯結(jié)構(gòu)；同時(shí)，設(shè)計(jì)算法和程序?qū)崿F(xiàn)的過(guò)程，

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

4、個(gè)集合”的關(guān)系外，其它三種結(jié)構(gòu)數(shù)據(jù)元素之間分別為“一對(duì)一”、“一對(duì)多”、“多對(duì)多”的關(guān)系。因此，在選擇邏輯結(jié)構(gòu)之前，我們應(yīng)首先把題目中的操作對(duì)象和對(duì)象之間的關(guān)系分析清楚，然后再根據(jù)這些關(guān)系的特點(diǎn)來(lái)合理的選用邏輯結(jié)構(gòu)。尤其是在某些復(fù)雜的問(wèn)題中，數(shù)據(jù)之間的關(guān)系相當(dāng)復(fù)雜，且選用不同邏輯結(jié)構(gòu)都可以解決這一問(wèn)題，但選用不同邏輯結(jié)構(gòu)實(shí)現(xiàn)的算法效率大不一樣。對(duì)于這一類問(wèn)題，我們應(yīng)采用怎樣的標(biāo)準(zhǔn)對(duì)邏輯結(jié)構(gòu)進(jìn)行選擇呢？下文將探討選擇合理邏輯結(jié)構(gòu)應(yīng)充分考慮的兩個(gè)因素。一、 充分利用“可直接使用”的信息。首先，我們這里所講的“信息”，指的是元素與元素之間的關(guān)系。對(duì)于待處理的信息，大致可分為“可直接使用”和“不可直接

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

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

7、果我們采用線性的邏輯結(jié)構(gòu)（如循環(huán)隊(duì)列），那么我們?cè)谂袛嗍欠癜硞€(gè)碼字t時(shí)，所用的方法為：初始時(shí)用指針p指向終止位置，接著通過(guò)p的不斷前移，依次找出碼字t從尾到頭的各個(gè)字母。例如碼字為“ABDCAB”，而文本圖1-1，終止位置為最右邊的箭頭符號(hào)，每個(gè)箭頭代表依次找到的碼字的各個(gè)字母。指針p的移動(dòng)方向 A B D C A BCDACBDCADCDBADCCBAD圖1-1由于題目規(guī)定碼字的覆蓋序列長(zhǎng)度不超過(guò)1000，所以進(jìn)行這樣的一次是否包含的判斷，其復(fù)雜度為O(1000)。由于碼字t中相鄰兩字母在文本中的位置，并非只有相鄰(如圖1-1中的D和C)這一種關(guān)系，中間還可能間隔了許多的字母(如圖1-1

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

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

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

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

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

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

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

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

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

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

18、需再加一層循環(huán)，用于尋找各棵二叉樹(shù)的根結(jié)點(diǎn)，但由于每個(gè)點(diǎn)都只會(huì)訪問(wèn)一次，尋找其左右兒子各需進(jìn)行一次循環(huán)，所以算法的時(shí)間復(fù)雜度為O(n2)。（附程序boat.pas）最后，我們對(duì)兩種結(jié)構(gòu)得出不同時(shí)間復(fù)雜度算法的原因進(jìn)行分析。其中最關(guān)鍵的一點(diǎn)就是因?yàn)槎鏄?shù)雖然結(jié)構(gòu)相對(duì)較簡(jiǎn)單，但已經(jīng)包含了幾乎全部都“有用”的信息。由我們尋找乘船方案的算法可知，二叉樹(shù)中的所有邊不僅都發(fā)揮了作用，而且沒(méi)有重復(fù)的使用，可見(jiàn)信息的利用率也是相當(dāng)之高的。既然采用樹(shù)結(jié)構(gòu)已經(jīng)足夠，圖結(jié)構(gòu)中的一些信息就顯然就成為了“無(wú)用”的信息。這些多余的“無(wú)用”信息，使我們?cè)诜治鰡?wèn)題時(shí)難于發(fā)現(xiàn)規(guī)律，也很難找到高效的算法進(jìn)行解決。這正如迷宮中的墻

19、一樣，越多越難走?！盁o(wú)用”的信息，只會(huì)干擾問(wèn)題的規(guī)律性，使我們更難找出解決問(wèn)題的方法。小結(jié)我們對(duì)數(shù)據(jù)的邏輯結(jié)構(gòu)進(jìn)行選擇，是構(gòu)造數(shù)學(xué)模型一大關(guān)鍵，而算法又是用來(lái)解決數(shù)學(xué)模型的。要使算法效率高，首先必須選好數(shù)據(jù)的邏輯結(jié)構(gòu)。上面已經(jīng)提出了選擇邏輯結(jié)構(gòu)的兩個(gè)條件（思考方向），總之目的是提高信息的利用效果。利用“可直接使用”的信息，由于中間不需其它操作，利用的效率自然很高；不不記錄“無(wú)用”的信息，就會(huì)使我們更加專心地研究分析“有用”的信息，對(duì)信息的使用也必然會(huì)更加優(yōu)化?？傊?，在解決問(wèn)題的過(guò)程中，選擇合理的邏輯結(jié)構(gòu)是相當(dāng)重要的環(huán)節(jié)。三、 選擇合理的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，分為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順

20、序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)則是借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。因?yàn)閮煞N存儲(chǔ)結(jié)構(gòu)的不同，導(dǎo)致這兩種存儲(chǔ)結(jié)構(gòu)在具體使用時(shí)也分別存在著優(yōu)點(diǎn)和缺點(diǎn)。這里有一個(gè)較簡(jiǎn)單的例子：我們需要記錄一個(gè)nn的矩陣，矩陣中包含的非0元素為m個(gè)。此時(shí)，我們?nèi)舨捎庙樞虼鎯?chǔ)結(jié)構(gòu)，就會(huì)使用一個(gè)nn的二維數(shù)組，將所有數(shù)據(jù)元素全部記錄下來(lái)；若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，則需要使用一個(gè)包含m個(gè)結(jié)點(diǎn)的鏈表，記錄所有非0的m個(gè)數(shù)據(jù)元素。由這樣兩種不同的記錄方式，我們可以通過(guò)對(duì)數(shù)據(jù)的不同操作來(lái)分析它們的優(yōu)點(diǎn)和缺點(diǎn)。1 隨機(jī)訪問(wèn)矩陣中任意元素。由于順序結(jié)構(gòu)在物理位置

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

22、率存在較大的差異，那么我們?cè)诖_定存儲(chǔ)結(jié)構(gòu)時(shí)，必須仔細(xì)分析算法中操作的需要，合理地選擇一種能夠“揚(yáng)長(zhǎng)避短”的存儲(chǔ)結(jié)構(gòu)。一、合理采用順序存儲(chǔ)結(jié)構(gòu)。我們?cè)谄匠Ｗ鲱}時(shí)，大多都是使用順序存儲(chǔ)結(jié)構(gòu)對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)。究其原因，一方面是出于順序結(jié)構(gòu)操作方便的考慮，另一方面是在程序?qū)崿F(xiàn)的過(guò)程中，使用順序結(jié)構(gòu)相對(duì)于鏈?zhǔn)浇Y(jié)構(gòu)更便于對(duì)程序進(jìn)行調(diào)試和查找錯(cuò)誤。因此，大多數(shù)人習(xí)慣上認(rèn)為，能夠使用順序結(jié)構(gòu)進(jìn)行存儲(chǔ)的問(wèn)題，最“好”采用順序存儲(chǔ)結(jié)構(gòu)。其實(shí)，這個(gè)所謂的“好”只是一個(gè)相對(duì)的標(biāo)準(zhǔn)，是建立在以下兩個(gè)前提條件之下的：1 鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)的結(jié)點(diǎn)與順序結(jié)構(gòu)存儲(chǔ)的結(jié)點(diǎn)數(shù)目相差不大。這種情況下，由于存儲(chǔ)的結(jié)點(diǎn)數(shù)目比較接近，使用鏈?zhǔn)浇Y(jié)構(gòu)

23、完全不能體現(xiàn)出記錄結(jié)點(diǎn)少的優(yōu)點(diǎn)，并且可能會(huì)由于指針操作較慢而降低算法的效率。更有甚者，由于指針自身占用的空間較大，且結(jié)點(diǎn)數(shù)目較多，因而算法對(duì)空間的要求可能根本無(wú)法得到滿足。2 并非算法效率的瓶頸所在。由于不是算法最費(fèi)時(shí)間的地方，這里是否進(jìn)行改進(jìn)，顯然是不會(huì)對(duì)整個(gè)算法構(gòu)成太大影響的，若使用鏈?zhǔn)浇Y(jié)構(gòu)反而會(huì)顯得操作過(guò)于繁瑣。二、必要時(shí)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。上面我對(duì)使用順序存儲(chǔ)結(jié)構(gòu)的條件進(jìn)行了分析，最后就只剩下何時(shí)應(yīng)該采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的問(wèn)題了。由于鏈?zhǔn)浇Y(jié)構(gòu)中指針操作確實(shí)較繁瑣，并且速度也較慢，調(diào)試也不方便，因而大家一般都不太愿意用鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)。但是，這只是一般的觀點(diǎn)，當(dāng)鏈?zhǔn)浇Y(jié)構(gòu)確實(shí)對(duì)算法有很大改進(jìn)時(shí)，我

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

25、位置的范圍(使程序盡量減少對(duì)運(yùn)氣的依賴)。接著，我們來(lái)確定此題的存儲(chǔ)結(jié)構(gòu)。由于這道題的地圖是一個(gè)二維的矩陣，所以一般來(lái)講，采用順序存儲(chǔ)結(jié)構(gòu)理所當(dāng)然。但是，順序存儲(chǔ)結(jié)構(gòu)在這道題中暴露了很大的缺點(diǎn)。我們所進(jìn)行的最多的操作，一是對(duì)初始位置的范圍進(jìn)行篩選，二是判斷要選擇哪個(gè)位置進(jìn)行探索。而這兩種操作，所需要用到的數(shù)據(jù)，只是龐大地圖中很少的一部分。如果采用順序存儲(chǔ)結(jié)構(gòu)(如圖3-1中陰影部分表示已標(biāo)記)，無(wú)論你需要用到多少數(shù)據(jù)，始終都要完全的遍歷整個(gè)地圖。 4 3 2 1 1 2 3 4 圖3-1 head(2,2)(2,3)(3,4)(4,1) 圖3-2然而，如果我們采用的是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(如圖3-2的鏈

26、表)，那么我們需要多少數(shù)據(jù)，就只會(huì)遍歷多少數(shù)據(jù)，這樣不僅充分發(fā)揮了鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)，而且由于不需單獨(dú)對(duì)某一個(gè)數(shù)據(jù)進(jìn)行提取，每次都是對(duì)所有數(shù)據(jù)進(jìn)行判斷，從而避免了鏈?zhǔn)浇Y(jié)構(gòu)的最大缺點(diǎn)。我們使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，雖然沒(méi)有降低問(wèn)題的時(shí)間復(fù)雜度(鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在最壞情況下的存儲(chǔ)量與順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)量幾乎相同)，但由于體現(xiàn)了前文所述選擇存儲(chǔ)結(jié)構(gòu)時(shí)揚(yáng)長(zhǎng)避短的原則，因而算法的效率也大為提高。（程序?qū)Σ煌瑪?shù)據(jù)的運(yùn)行時(shí)間見(jiàn)表3-3）測(cè)試數(shù)據(jù)編號(hào)使用順序存儲(chǔ)結(jié)構(gòu)的程序使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的程序10.06s0.02s21.73s0.07s31.14s0.06s43.86s0.14s532.84s0.21s6141.16s0

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

28、因此，作用與剪枝相似的存儲(chǔ)結(jié)構(gòu)的合理選擇，也是同樣很值得重視的?？傊?，我們?cè)谠O(shè)計(jì)算法的過(guò)程中，必須充分考慮存儲(chǔ)結(jié)構(gòu)所帶來(lái)的不同影響，選擇最合理的存儲(chǔ)結(jié)構(gòu)。四、 多種數(shù)據(jù)結(jié)構(gòu)相結(jié)合上文所探討的，都是如何對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行選擇，其中包含了邏輯結(jié)構(gòu)的選擇和存儲(chǔ)結(jié)構(gòu)的選擇，是一種具有較大普遍性的算法優(yōu)化方法。對(duì)于多數(shù)的問(wèn)題，我們都可以通過(guò)選擇一種合理的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)以達(dá)到優(yōu)化算法的目的。但是，有些問(wèn)題卻往往不如人愿，要對(duì)這類問(wèn)題的數(shù)據(jù)結(jié)構(gòu)進(jìn)行選擇，常常會(huì)顧此失彼，有時(shí)甚至根本就不存在某一種合適的數(shù)據(jù)結(jié)構(gòu)。此時(shí)，我們是無(wú)法選擇出某一種合適的數(shù)據(jù)結(jié)構(gòu)的，以上的方法就有些不太適用了。為解決數(shù)據(jù)結(jié)構(gòu)難以選擇的

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

30、字列表中 no:array1.100 of byte;noi-排序后列表中第i個(gè)碼字在原列表中的位置 ss,tt:arr1; nn:arr2; ssi,tti,nni分別記錄找到的第i個(gè)項(xiàng)目中的覆蓋序列的首位置， 尾位置和其對(duì)應(yīng)碼字在排序后的碼字列表中的編號(hào) f:text; b:char;procedure readcod;讀入碼字列表并對(duì)其進(jìn)行排序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); 初始時(shí),令所有bbceec,以后找到字母c后再改變bbc和eec的值 for i:=1 to n do begin k:=i; for j:=i+1 to n do 按尾字母進(jìn)行排序,在尾字母相同時(shí)按碼字由長(zhǎng)到短排序 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; 下面的判斷為確定對(duì)應(yīng)各尾字母的碼字在新列表中

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); 尋找項(xiàng)目的過(guò)程 ,已確定其終止位置為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; 對(duì)找出的項(xiàng)目進(jìn)行擇優(yōu)，若can=false表示新找到的項(xiàng)目不如以前的 if can then begin inc(m);ssm:=j;ttm:=ed;nnm:=k; end;

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

35、ln(f,lenm); 輸出“答案”的總和值 k:=m; 尋找“答案”中所包含的各個(gè)項(xiàng)目 while k0 do begin while lenk=lenk-1 do dec(k);等式成立時(shí)不必選項(xiàng)目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; 將最后一次出現(xiàn)字母b的位置更新為now if bbb=1000 then find(now-999,now,b) else find(1,now,b); 確定起始位置的下限max(now-999,1)，并對(duì)項(xiàng)目進(jìn)行尋找 end; close(f); findanswer;end.程序2乘船問(wèn)題

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

38、人的姓 Gname:Gnamearr; 記錄每個(gè)人的名 visit:array1.Maxn of boolean; visiti記錄第i個(gè)人是否已訪問(wèn)過(guò) total,n:integer; total-需要船的數(shù)目，n-總?cè)藬?shù) 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為根結(jié)點(diǎn)的子樹(shù)，并輸出在這棵子樹(shù)中的所有人的乘船方案 father表示root是其父親的哪個(gè)兒子，0表示左兒子，1表示右兒子 rest表示在輸出該子樹(shù)中所有人的乘船方案以后，是否有一個(gè)人獨(dú)坐一