VC編程教程 第三章 算法與數(shù)據(jù)結(jié)構(gòu).ppt

1、第三章 算法與數(shù)據(jù)結(jié)構(gòu),程序?yàn)槭裁茨芙忸}？就是它能把輸入的數(shù)據(jù)，經(jīng)過表達(dá)式計(jì)算、賦值、置換轉(zhuǎn)移等一系列計(jì)算步驟，最后得到輸出。編制程序就是要設(shè)計(jì)數(shù)據(jù)(輸入的、輸出的、中間的)，然后針對這些數(shù)據(jù)一一安排計(jì)算步驟，即所謂計(jì)算法。所以，很早就有人說，程序計(jì)算的本質(zhì)是： 程序 = 算法 + 數(shù)據(jù)結(jié)構(gòu) 算法和數(shù)據(jù)結(jié)構(gòu)討論的是抽象的計(jì)算邏輯，與具體的表示法無關(guān)，可以用圖形、偽代碼和匯編語言、高級程序設(shè)計(jì)語言表達(dá)它們，一般討論中采用近似于高級語言的偽代碼(不能上機(jī)運(yùn)行，可以方便地轉(zhuǎn)成編程語言代碼)表達(dá)。 本章討論編程最重要的兩個(gè)基礎(chǔ)，即算法與數(shù)據(jù)結(jié)構(gòu)。,3.1 算 法,算法是什么？就字面而言是計(jì)算解題的辦法

2、，是解題策略具體化為計(jì)算機(jī)的動作。即計(jì)算機(jī)在什么情況下應(yīng)該怎么做的一系列步驟，實(shí)施了這些步驟問題得到解決。例如，輾轉(zhuǎn)相除法是求兩個(gè)整數(shù)的最大公約數(shù)的數(shù)學(xué)算法。它的解題策略是：以小數(shù)除大數(shù)，得余數(shù)，如果余數(shù)不為零，則小數(shù)成被除數(shù)，余數(shù)成除數(shù)，除后得新余數(shù)。若余數(shù)為零，則此除數(shù)即為最大公約數(shù)，否則繼續(xù)輾轉(zhuǎn)除。不妨先拿兩個(gè)正整數(shù)試一試： 544和119。544/119的余數(shù)是68，119/68的余數(shù)是51，68/51的余數(shù)是17，51/17的余數(shù)是0。所以544和119的最大公約數(shù)是17。 如何寫出計(jì)算機(jī)算法呢？計(jì)算機(jī)怎么進(jìn)行輾轉(zhuǎn)相除呢？顯然只能用計(jì)算機(jī)容許的動作，寫出的算法才是可行的。,計(jì)算機(jī)容許

3、的動作是： 為變量賦值(包括初值)； 計(jì)算表達(dá)式(在變量上做四則或邏輯運(yùn)算)； 計(jì)算過程的選擇、循環(huán)、轉(zhuǎn)移控制； 調(diào)用函數(shù)/子程序。 再看如何寫出計(jì)算機(jī)的輾轉(zhuǎn)相除法。 令變量x為被除數(shù)，y為除數(shù)，z為余數(shù)。計(jì)算機(jī)中有求余函數(shù)mod，則： z = x mod y 然后xy, yz就換過來了，x依然是被除數(shù)，y是除數(shù)。于是寫出GCD(Greatest Common Divisor最大公約數(shù))算法： 1設(shè)定x, y, z 2輸入x, y 3if yx then zy; yx; xz fi 4while y0 do Azy Byx mod y; Cxz od 5輸出z，即最大公約數(shù),其中，ifthen

4、fi、while dood是分支和循環(huán)控制，fi和od是編程語言Endif和Endwhile的簡寫。是賦值符號。其中的序號按1，2，3和A，B，C字母數(shù)字相間表示嵌套，第5步這一行最后的表示算法結(jié)束。這種表示法是算法文獻(xiàn)上學(xué)者們約定的表示法。,3.1.1 算法的表示,從GCD算法的例子看到它的表達(dá)比較自由，不過是自然語言加上編程語言的基本特征(控制結(jié)構(gòu)、賦值、調(diào)用)而已。很自然地，讀者就會問到“算法描述語言和編程語言有什么關(guān)系？”。事實(shí)上，早期的編程語言ALGOL就叫算法語言。后來發(fā)現(xiàn)，用編程語言描述算法往往使人們陷于表示的細(xì)節(jié)，因?yàn)榫幊陶Z言的形式化(即正規(guī)性)過于嚴(yán)格，而在設(shè)計(jì)程序的早期，人

5、們關(guān)心的是程序邏輯能否解題，而不是立即上機(jī)運(yùn)行。于是先用偽代碼寫設(shè)計(jì)，再用編程語言編碼實(shí)現(xiàn)這個(gè)設(shè)計(jì)(編碼)。 算法描述的是程序的計(jì)算邏輯，編程語言表達(dá)的是程序本體(源代碼)。更形象地說，一個(gè)是靈魂，一個(gè)是包含有靈魂的肉體。設(shè)計(jì)過程也是人們對這個(gè)問題更深入了解的過程，反復(fù)修改是必然的，何不先設(shè)計(jì)、修改好了一次翻譯(編碼)成功呢？于是“先設(shè)計(jì)，后編碼！”是早期軟件行業(yè)不成文的行規(guī)。直到現(xiàn)在，軟件開發(fā)依然強(qiáng)調(diào)設(shè)計(jì)和編程是兩個(gè)不同階段。只是由于開發(fā)工具的完善，偽代碼越來越近似于最后實(shí)現(xiàn)的編程語言。甚至有些簡單編程直接用編程語言，如VB、VC在窗口上進(jìn)行。偽代碼始終沒有統(tǒng)一的標(biāo)準(zhǔn)。,類C、類Pascal

6、、類VB之類的偽代碼，也不盡相同，但程序員必須記住“用偽代碼寫算法，編程語言寫程序”還是應(yīng)該遵循的！ 本書約定的算法描述語言是VC語言的變體，稱為類VC語言。 這里還需要說一說流程圖(Flow Chart)。因?yàn)樗跉v史上有過巨大的影響，在20世紀(jì)5070年代結(jié)構(gòu)化編程語言尚未風(fēng)行時(shí)，流程圖一直是表達(dá)算法的設(shè)計(jì)工具。美國國家標(biāo)準(zhǔn)協(xié)會(ANSI)還把它定為標(biāo)準(zhǔn)。為了幫助讀者閱讀歷史的軟件文檔，這里做一點(diǎn)簡單說明。,圖3.1 常用流程圖符號,如圖3.1所示，其中： 帶圓弧的框是起止框，表示算法的起始、終止?？騼?nèi)填寫文字。 圓圈一般是連接框，連接多個(gè)流向箭頭。大圈中寫文字標(biāo)號，無文字時(shí)是句號大小的圈

7、。 平行四邊形的輸入輸出框表示輸入數(shù)據(jù)和輸出計(jì)算結(jié)果。框內(nèi)應(yīng)填寫需要輸入或輸出的量。有的標(biāo)準(zhǔn)將輸出畫成打印紙形狀。 菱形的判斷框根據(jù)條件判斷執(zhí)行的走向?？騼?nèi)應(yīng)填上條件。 矩形的處理框表示執(zhí)行計(jì)算表達(dá)式和賦值操作?？騼?nèi)用文字或符號表明具體實(shí)現(xiàn)的操作。 雙立邊矩形框是調(diào)用/引用框。框內(nèi)寫函數(shù)/過程名。 注釋框表示對操作或數(shù)據(jù)做必要的說明, 框內(nèi)用文字說明注釋信息。 流向線表示算法中控制的流向，向下向右可不畫箭頭，其他方向必畫。 畫流程圖時(shí)，主流程必須在一條垂直的軸線上，特別是起止框要對齊，切勿因有多次分支而將主流程畫成臺階形或橫寬大于縱長。,3.1.2 算法的定義,仍回到上述GCD算法的例子，以它

8、來說明E.Knuth對算法作的定義： 一個(gè)算法，就是一個(gè)有窮規(guī)則的集合，規(guī)則規(guī)定了解決某類問題的運(yùn)算序列。它是有窮的、確定的、能行的，并有0到多個(gè)輸入和1到多個(gè)輸出。,現(xiàn)解釋如下： 運(yùn)算序列體現(xiàn)了解題規(guī)則 GCD算法例子中運(yùn)算是廣義的，就是計(jì)算機(jī)可執(zhí)行的操作，不單指計(jì)算值。用標(biāo)號表示操作步驟的次序，體現(xiàn)了輾轉(zhuǎn)相除的規(guī)則。其中的賦值、循環(huán)、條件分支、求余也都是規(guī)則。整個(gè)的操作步驟就是一個(gè)算法過程。 0到多個(gè)輸入，1到多個(gè)輸出 沒有輸入/輸出的計(jì)算是沒有意義的。這里只需解釋0個(gè)輸入不是無輸入，而是變量已有初值或缺省值，算法執(zhí)行時(shí)不另要求輸入，這是極為常見的。例如，公司的正式文件每頁都要打上公司的商

9、標(biāo)，其缺省位置是左上角，每次調(diào)用，打印程序無需輸入坐標(biāo)參數(shù)。 有窮的 指算法實(shí)施的規(guī)則是有窮的，也就是執(zhí)行了有限個(gè)步驟即結(jié)束，無限步驟即不終止就不能稱之為算法，只能是稱為算法模型的計(jì)算方法。數(shù)學(xué)中有些計(jì)算方法在界定收斂條件之前是不終止的。 確定的 指算法的每一步驟都有確切的定義和解釋。所以算法描述語言力求形式化，無二義性解釋。編程語言當(dāng)然是形式語言，但如前所述太煩瑣，多采用偽代碼。 能行的 指算法中的每一步驟均能準(zhǔn)確實(shí)施，也指可以證明整個(gè)算法實(shí)施后可以得到預(yù)期的解。,3.1.3 算法與建模,從以上討論可以得出，每個(gè)程序都包含了算法，設(shè)計(jì)程序首先作算法設(shè)計(jì)，就是把解題策略具體化。那么解題策略由何

10、而來？這就需要建立計(jì)算模型，前述的“輾轉(zhuǎn)相除”求最大公約數(shù)，既是模型(兩個(gè)整數(shù)輾轉(zhuǎn)相除)又是解題策略。不妨再舉個(gè)例子：,例3.1 求整數(shù)1.N之和 這是數(shù)學(xué)家高斯小時(shí)候回答教師“求1.100之和是多少？”的做法：數(shù)據(jù)模型是整數(shù)1.100數(shù)組，求和模型如圖所示：,把(1，99)，(2，98)，(3，97)，成對先加，共49個(gè)100，再加上50和100，換成數(shù)學(xué)表示 N*(N/21)+N/2+N = N*(N+1)/2 是求和模型的數(shù)學(xué)描述，也稱數(shù)學(xué)模型。代入數(shù)字： 按照這個(gè)公式寫出算法的偽代碼是極簡單的： void sum1( ) cin n s = n*(n+1)/2 cout s 這個(gè)題目也

11、可以直接按公式模擬人們做累加偽代碼如下，： void sum2( ) cin n i = 1;s = 0 dowhile (in) s = s+i i= i+1 loop cout s,算法Sum1和Sum2顯然不同，一個(gè)只做加法，一個(gè)有加、乘、除法(運(yùn)算速度不一樣)；一個(gè)用三個(gè)變量一個(gè)只用兩個(gè)(存儲單元耗用不同)。對于復(fù)雜的計(jì)算，它們的差別就非常巨大了。算法分析就是專門研究算法時(shí)空效率的。它們的不同在于所取計(jì)算模型不同，一個(gè)是總結(jié)出的數(shù)學(xué)模型，一個(gè)是模擬自然數(shù)序列增長的過程模型。當(dāng)然最常見的稍微復(fù)雜一點(diǎn)算法多采用結(jié)構(gòu)模型。請看下例：,例3.2 產(chǎn)品的最短完工期 一個(gè)工廠制造某產(chǎn)品其備料加工直

12、至包裝的各階段所需工期如下圖：,圖3.2 最短工期計(jì)算圖,產(chǎn)品是兩種部件不同的組合，因而要有不同的試車方案。當(dāng)接收到合同選定的產(chǎn)品組合后，計(jì)算最短的完工期。 圖3.2就是解此問題的模型，也就是沿起始結(jié)點(diǎn)P到終止結(jié)點(diǎn)B找一條最長的路徑(要涉及R1，R2試車數(shù)量)。 有了模型就可以在它上面思考算法。請注意，同一模型可以有多個(gè)不同的改進(jìn)算法。后文的數(shù)據(jù)結(jié)構(gòu)就是研究有哪些典型的結(jié)構(gòu)關(guān)系及其算法。,建立什么模型才易設(shè)計(jì)算法呢？這要取決于問題的性質(zhì)和分析人員的水平。常見有以下三種模型： 數(shù)學(xué)模型 最易寫算法的模型，且準(zhǔn)確、簡單不易出錯(cuò)。來各種數(shù)學(xué)類型都有成熟的計(jì)算方法。可惜并不是所有問題都能找出數(shù)學(xué)公式建

13、立數(shù)學(xué)模型。 過程模擬模型 這是處理日常業(yè)務(wù)問題算法的常用模型。例如民航售票系統(tǒng)，可畫出一個(gè)用例圖模擬售票業(yè)務(wù)活動：,圖3.3描述了每個(gè)參與角色(旅客、售票員、會計(jì)系統(tǒng)、銷售座位登記程序、打印機(jī))的各項(xiàng)活動過程。每個(gè)活動都可以作為一任務(wù)寫算法。如查詢要根據(jù)客戶要求的日期、座艙等級、到達(dá)時(shí)間、折扣情況為用戶提供多種方案，以便決策?；顒釉骄唧w，任務(wù)越明確，算法越好寫。多個(gè)任務(wù)也可以寫成一個(gè)算法。 這種模型簡單易行，當(dāng)今流行的UML語言即以此種模型為基礎(chǔ)提供了八種不同角度的視圖，以便作面向?qū)ο蟪绦蛟O(shè)計(jì)(后文還要介紹)。,圖3.3 民航售票用例圖,結(jié)構(gòu)模型 已如前述，每個(gè)結(jié)點(diǎn)可以是一種處理動作，每一個(gè)

14、邊是輸出/輸出。反過來，每個(gè)結(jié)點(diǎn)也可以是數(shù)據(jù)的狀態(tài)，每個(gè)邊是一種處理的動作。結(jié)構(gòu)模型雖沒有數(shù)學(xué)模型簡單、清晰、深刻，但比過程模擬模型要明確得多，是設(shè)計(jì)算法時(shí)常用的。,3.1.4 算法的優(yōu)劣,算法雖與計(jì)算模型密切相關(guān)，但模型只是設(shè)計(jì)算法的根據(jù)。算法設(shè)計(jì)畢竟是編排計(jì)算機(jī)的動作過程，解是過程的結(jié)果。同樣模型，同樣結(jié)果可以有不同的算法過程，其差別表現(xiàn)在運(yùn)算次數(shù)，占用存儲多少。請看下例： 例3.3 荷蘭國旗問題 有三種顏色(紅，白，藍(lán))的石子混合排成一條長龍，試設(shè)計(jì)一算法將其分色(紅、白、藍(lán))排列。 稍加分析就知道它是個(gè)分類問題。怎么表示？以三種字符R、W、B代表三種顏色的石子，把它們放在一個(gè)數(shù)組之中。

15、這個(gè)問題就成了在字符數(shù)組中分類(解題模型)，數(shù)據(jù)結(jié)構(gòu)是數(shù)組，如下圖所示：,首先想到的算法是DNF1： 1輸入A(1.N) 2找一個(gè)同大的數(shù)組B放分類完的字符；下標(biāo)指示Q = 1 3查三遍P = 1.N A若A(P) = R|W|B /這個(gè)算法查找比較3N次，假定三色個(gè)數(shù)平均 (1) B(Q) = A(P) /移動元素N次 (2) Q = Q+1 B. P = P+1 /占內(nèi)存2N+3單元，(A，B，P，Q，N) 4輸出B,這個(gè)算法簡單不易出錯(cuò)，只是內(nèi)存占得太多，能不能就地變換？于是就想到第二個(gè)算法：,Q指針按“R”、“W”、“B”三種色，逐個(gè)增加，“R”不完不向前走。P指針逐個(gè)詢問。每找到一個(gè)

16、要換的字符做以下交換。請注意，以下算法用偽代碼： Swap(A(P),A(Q) Z = A(P) A(P) = A(Q) A(Q) = Z DNF2的算法是： DNF2(ByRef A:Char, N:Integer) Char C(2) = (R,W) Q = 1 for（i=1; i2; i+）P = Q /算法查找比較5/3N次,最多交換2N/3次，4N/3個(gè)元素 Do While ( PN ) /占內(nèi)存N+5個(gè)單元(A，C，Z，P，Q) If ( A(P) = C(i) ) Swap(A(P)，A(Q) ; Q = Q+1；P = P1 P = P+1 其中P = P1是剛換來的字符還

17、要再查是什么色的。請注意，算法過程的輸入輸出通過引用過程參數(shù)(ByRef)帶來帶去。,這個(gè)算法比DNF1改進(jìn)多了，但Dijkstra提出了更好的算法： 多設(shè)一個(gè)指針，每當(dāng)查找到一個(gè)字符，詢問不是R，緊接著問是否B。兩頭都可交換，當(dāng)P = NP時(shí)即可停止，如下圖所示：,寫出偽代碼算法是： DNF3(ByRef A: Char, N:Integer) Int P, Q, NP = N+1: P = 1; Q = 1 Do While (PNP) If (A(P)W) If A(P) = B do NP = NP1 while (A(NP1) = B) Swap(A(NP1),A(P) NP = N

18、P1 Else Swap(A(P),A(Q) Q = Q+1 /本算法查找2N/3，比較N次 /至多交換N個(gè)元素，N/2次 Else /占用N+4個(gè)單元，(A，P，Q，Z，NP) P = P+1 這個(gè)例子說明計(jì)算模型、數(shù)據(jù)結(jié)構(gòu)、算法既相關(guān)又獨(dú)立。模型是算法的思路，數(shù)據(jù)結(jié)構(gòu)是算法作用的對象，算法有其自身的好壞(時(shí)、空效率),3.1.5 常用算法,算法設(shè)計(jì)要先弄清問題，建立計(jì)算模型；設(shè)計(jì)實(shí)現(xiàn)這種模型的數(shù)據(jù)(結(jié)構(gòu))；再設(shè)計(jì)使數(shù)據(jù)變化達(dá)到要求的動作步驟；證明或驗(yàn)證算法正確；再查看有無更好的改進(jìn)。DNF的例子，說明一個(gè)好的算法常常是深思熟慮多次改進(jìn)的結(jié)果。 對于初學(xué)者先解決有無，再解決好壞。為此，本小節(jié)

19、提供一些常用算法(模型)，既可以解決一些問題，又是組合更復(fù)雜算法的思路。 枚舉法 枚舉亦稱窮舉，是最笨但最可靠的辦法，計(jì)算機(jī)無知覺，它根據(jù)你給的條件，無一遺漏地做一遍總可以找到解。生活中這種辦法也不少見。如公安局根據(jù)少量特征把全市符合該特征的人查一遍以搜捕重要逃犯。工作量巨大，近乎蠻干，但是它是沒有其他辦法時(shí)的最好辦法。計(jì)算機(jī)因?yàn)樗俣瓤?，可以“以快補(bǔ)拙”，所以常用這種方法。,枚舉法作為一種具體的算法，還可以解決常規(guī)方法不易解決的問題。例如，百元買百雞這個(gè)古老的問題： 例3.4 公雞每只五元，母雞每只三元，小雞三只一元，問百元買百雞有幾種買法？ 可以寫出代數(shù)方程式： x+y+z100 5x+3y

20、+z/3100 再也找不出方程了，那么兩方程怎么解三個(gè)未知數(shù)？ 這類問題只好用枚舉法。因?yàn)楣u最多20只，母雞最多33只，一一枚舉其組合。若余下的只數(shù)能與錢數(shù)匹配，就是一個(gè)解。全部枚舉可以找出所有的解。算法如下： BuyChicks() Int x, y, z: for（i=1; i20; i+） x=I; for（j=1; i33; i+） y = j; z = 100 xy; If (5x+3y+(z/3) = 100) Print x, y, z 枚舉法的程序一般簡單，但有時(shí)運(yùn)算量大。如果能找到明知枚舉無結(jié)果的限定規(guī)則，縮小枚舉范圍，這種方法還是很有效的。,迭代法 在科學(xué)計(jì)算領(lǐng)域，人們時(shí)

21、常會遇到求解方程f(x) = 0或微分方程的數(shù)值解等計(jì)算問題?？墒侨藗儏s很難或無法用像一元二次方程的求根公式那樣的解析解法(又稱直接求解法)。例如，一般的一元五次或更高次方程、幾乎所有的超越方程，它們的解都無法用解析方法表達(dá)出來。為此，人們只能用數(shù)值方法(也稱數(shù)值計(jì)算方法)求出問題的近似解，若近似解的誤差可以估計(jì)和控制，且迭代的次數(shù)也為人們可以接受，它就是一種數(shù)值近似求解的好方法。它既可以用來求解代數(shù)方程，又可以用來求解微分方程，使一個(gè)復(fù)雜問題的求解過程轉(zhuǎn)化為相對簡單的迭代算式的重復(fù)執(zhí)行過程。下面以方程求根f(x) = 0為例說明迭代法的基本思想。,首先把求解方程變換成為迭代算式xg(x)，然

22、后從事先估計(jì)的一個(gè)根的初始近似值x0出發(fā)，用迭代算式xk+1 = g(xk)求出另一個(gè)近似值x1，再由x1確定x2,最終構(gòu)造出一個(gè)迭代序列x0, x1，x2, xn ,來逐次逼近方程f(x) = 0的根。例如：求方程x3x10在x1.5附近的一個(gè)根。 首先將方程改寫成：(1) 用給定的初始值x01.5代入(1)式的右端，得到 x11.35721 用x1作為近似值代入(1)式的右端，又得到 x21.33086 重復(fù)同樣步驟，可以逐次求得更精確的值。這一過程即為迭代過程。顯然，迭代過程就是通過老值求出新值，用新值替代老值的過程。對于一個(gè)收斂的迭代過程，有時(shí)也要經(jīng)過千百次迭代才可以得到準(zhǔn)確解，但實(shí)際

23、計(jì)算時(shí)，只能作有限次迭代，因此，要精選迭代算式，研究算式的收斂性及收斂速度。例如上式若選xx31作為迭代算式就是不收斂的。,如果一時(shí)找不出收斂的算式，也可以用迭代算法： 例3.5 求方程x5+4x412x3+6x2x+1 = 0在0,1區(qū)間的一個(gè)解。 初步驗(yàn)證f(0) = 1, f(1) = 1。函數(shù)值變號有一個(gè)解。先寫計(jì)算函數(shù)f的算法 Func f(x: Double) : Double f = x5+4x412.0 x3+6x2x+1 EndFunc,再寫求根算法的偽代碼： Root(A, B, Ebs : Double) /每次取區(qū)間中值m = (a+b)/2。 F1 = F(A); F

24、M = FA /若f(a)f(m)0它們同號，則將區(qū)間縮小為m,b； Do /若f(a)f(m)0 )A = M Else B = M While (Abs(FM)Eps) /以下是縮小區(qū)間的迭代 Print x =, M 終止循環(huán)的條件：兩次得到的近似值之差的絕對值小于預(yù)先給定的誤差值。,遞歸法 數(shù)學(xué)上有許多函數(shù)是用函數(shù)本身定義的，例如階乘函數(shù)： fact(n) = n! = n(n1)(n2)1 = n*fact(n1) 用其自身定義非常自然。程序中能不能寫一個(gè)過程自己調(diào)用自己呢？早期編程語言(Basic , FORTRAN)不行，現(xiàn)在都可以了。過程調(diào)用自己比調(diào)用別的過程還要方便(少寫過程

25、)。因?yàn)檫f歸算法往往是對問題更本質(zhì)的描述，在計(jì)算技術(shù)中它占有重要地位。 寫遞歸算法的程序極其簡單，看上去幾乎和遞歸的數(shù)學(xué)公式一樣，只是注意“遞歸出口”自己調(diào)用自己何時(shí)才了？再看階乘函數(shù) 寫成偽代碼是： Func fact(n : Integer)/這是定義的接口 If （n = 0 or n = 1 ）fact=1/出口條件 Else fact = nfact(n1)/是遞歸調(diào)用，n不斷減少 EndFunc 遞歸算法一般要先問是否滿足出口。遞歸函數(shù)放在Else部分。 可以設(shè)想它的執(zhí)行情況，從n(n1)一直連乘到1，而不是相反。,在非數(shù)值計(jì)算中用遞歸建立計(jì)算模型寫算法也很簡單，舉河內(nèi)塔為例。 例

26、3.6 19世紀(jì)歐洲人到東方，看到Bramah神廟里有個(gè)和尚整天把三根柱子上的金盤倒來倒去。原來他是想把一個(gè)柱子上64個(gè)從下至上逐個(gè)縮小的金盤從一個(gè)柱子移到另一個(gè)柱子，規(guī)定每次移一個(gè)，而且小盤永遠(yuǎn)在大盤上。據(jù)說，全部移完之后就是世界末日，梵天再世。但是無論他倒了多少天總沒有什么進(jìn)展。這個(gè)裝置引起歐洲人極大興趣，后來傳到歐洲作為饋贈的玩物，叫河內(nèi)塔。河內(nèi)塔移動規(guī)則簡單，但移動次數(shù)實(shí)在驚人。64個(gè)盤子其移動的次數(shù)是 次，比以秒計(jì)的地球年齡1.891017都大。當(dāng)然，計(jì)算機(jī)移動一次不會要一秒鐘，那么，編一個(gè)程序讓機(jī)器作也許能多做幾個(gè)。 為找到這個(gè)問題的算法，先畫出圖，試走幾個(gè)盤。,大家很快就可以想到

27、： 要使n個(gè)盤從1柱移到2柱，得先把n1個(gè)盤移到3柱，那么第n個(gè)盤(最大盤)就可以從1柱移到2柱。至于如何把n1個(gè)盤從1柱移動到3柱暫時(shí)不管。第n盤移完之后，按同樣方式再將n1個(gè)盤從3柱移到2柱。于是n個(gè)盤從1柱移到2柱的任務(wù)就完成了。草擬算法是： MoveTower(N,1,2) Call MoveTower (N1,1,3) Call MoveDisk (1,2) Call MoveTower (N1,3,2),其中過程MoveTower的參數(shù)依次表示要把幾個(gè)盤子、從起始柱搬到目的柱；過程MoveDisk的參數(shù)表示把一個(gè)盤子從起始柱移到目的柱。移動N個(gè)盤的任務(wù)變成兩個(gè)移動N1個(gè)盤的任務(wù)，加

28、上一個(gè)有效的移盤動作，看來這個(gè)問題似乎沒解決，移動N個(gè)和N1個(gè)差不多，到底如何移動還是不知道。其實(shí)這個(gè)問題已經(jīng)解決了。把MoveTower (N1,1,3)這個(gè)新任務(wù)如法炮制，把2柱當(dāng)成過渡柱，也可以變?yōu)閮蓚€(gè)子任務(wù)加一個(gè)MoveDisk (1,3)的動作。如此做下去，每次移動盤子的任務(wù)減1，直到0個(gè)盤子時(shí)就沒有任務(wù)了，剩下的全部是動作。遞歸算法的內(nèi)容就這三步，遞歸程序能自動地做到0個(gè)任務(wù)為止?？梢阅萌齻€(gè)盤子檢驗(yàn)一下這個(gè)遞歸算法。 可以看到，當(dāng)任務(wù)為0時(shí)，剩下的全是動作，從上往下數(shù)是： 12，13，23，12，31，32，12 和實(shí)際復(fù)核的完全一樣。,在寫算法時(shí)，只要把柱名改成變量，就可以自動改

29、變其值，再加上遞歸終止條件，可以得到： MoveTower (N，F(xiàn)rom，To，Using : Integer) If (N = 0) Print From, To Else Call MoveTower (N1，F(xiàn)rom，Using，To) Call MoveDisk (From，To) Call MoveTower (N1，Using，To，F(xiàn)rom) 這是一個(gè)典型的遞歸算法自己調(diào)用自己。它從遞歸給定參數(shù)出發(fā)(如例中N個(gè))遞歸到達(dá)邊界(N = 0)。,遞推法 所謂遞推法，它的數(shù)學(xué)公式也是遞歸的。只是在實(shí)現(xiàn)計(jì)算時(shí)迭代方向相反。從給定邊界出發(fā)逐步迭代到達(dá)指定計(jì)算參數(shù)。它不需反復(fù)調(diào)用自己(節(jié)省

30、了很多調(diào)用參數(shù)匹配開銷)。效率較高。還是以解階乘函數(shù)為例，其遞推過程是： f(0)0! 1 f(1)1! 1f(0) 1 f(2)2! 2f(1) 2 f(3)3! 3f(2)6 f(n)n! n(n1)! nf(n1),寫出偽代碼算法是： Func fact1(N : Integer) : Integer If (N = 0 or N = 1) fact1 = 1 Else = 1 Do fact1 = fact1I ;I = I+1 /此處是變量引用，而不是函數(shù)調(diào)用 hile ( ) EndFunc 再看一個(gè)Fibonacci數(shù)列的例子： Fib(1) = 1 Fib(2) = 1 Fib

31、(n) = Fib(n1) + Fib(n2) 寫個(gè)遞歸算法的偽代碼把以上公式抄進(jìn)去就可以了，寫遞推算法偽代碼只要記住，從邊界開始，都用變量： Func Fib (N: Integer): Integer F1 = 1 If( N = 1 ) Return F2 = 1 If （N = 2 ) Return I = 3 Do Fib = F1+F2 F1 = F2 F2 = Fib I = I+1 While （IN ） EndFunc 不難看出，遞推法就是把迭代法用于遞歸公式，迭代方向正好和遞歸算法過程相反。,分治法 在算法優(yōu)劣一節(jié)中談到算法分析，它是研究算法的運(yùn)算次數(shù)(相對速度)和占用空間

32、的。研究表明，運(yùn)算對象的多少(大小)是一個(gè)重要指標(biāo)，算法的復(fù)雜性(運(yùn)算次數(shù))隨大小(n)的增長呈線性增長、指數(shù)增長、階乘增長，它們的關(guān)系可表示為： f0(n) = O(n) /計(jì)算次數(shù)正比于n f2(n) = O(2n)/計(jì)算次數(shù)正比于2n f3(n) = O(n!) /計(jì)算次數(shù)正比于n! 這就得到一個(gè)啟示：把一個(gè)大的計(jì)算分成兩個(gè)小的計(jì)算其計(jì)算量可以很快地降下來。 n = 2(n/2) /6 = 23 n22(n/2)2 /62 = 36232 = 18 n!2(n/2)! /6! = 72023! = 12 這就是分治法的思想基礎(chǔ)。因?yàn)槌Ｒ姷木仃囘\(yùn)算、排序、查找算法，線性復(fù)雜度不大，只要分小

33、就是有益的。 Knuth的快速排序算法(Quicksort)就是這種分治思想的連續(xù)運(yùn)用。,例3.7 設(shè)有N個(gè)元素的數(shù)組，請按遞增(遞減)次序排序。 隨便取出一個(gè)元素A(P)和數(shù)組其他元素比較，凡大于它的放在右邊，小于它的放在左邊。A(P)的位置確定后，留下左右兩個(gè)待排序的子數(shù)組。接著按同樣的方法二分，遞歸直到一個(gè)元素。,寫成偽代碼算法是： QuickSort(A, Min, Max) P = Min Top = Min+1 Bot = Max Do Do Top = Top+1While (A(Top)A(P) Do Bot = Bot1 While (A(Bot)A(P) Swap(A(To

34、p),A(Bot) While （TopBOT ） Swap(A(P),A(Top) /A(P)找到恰當(dāng)位置 Call QuickSort(A, Min, Top1) /小于A(P)的子數(shù)組 Call QuickSort(A, Top + 1,Max) /大于A(P)的子數(shù)組 可以證明其平均比較次數(shù)為O(N log2N)，小于一般排序的O(N2)。這個(gè)算法還可以改進(jìn)，如果分出的子數(shù)組碰巧已排好序，另一個(gè)尚需排，如何讓已排好的子數(shù)組跳出運(yùn)算。 把一個(gè)大的處理對象分割為小對象，如果仍用原方法處理小對象就是遞歸。如果分出的各部分用不同的算法處理就是分治，分治在人工智能、查找、檢索的算法設(shè)計(jì)中是經(jīng)常見

35、到的。,回溯法 算法過程如同下棋，每一步都會對結(jié)果狀態(tài)有所影響，每一步都正確結(jié)果自然正確。算法設(shè)計(jì)就是設(shè)計(jì)出能得出正確結(jié)果的全過程。為此規(guī)定每一步的約束。有時(shí)一下子規(guī)定不了必然正確的全過程，只能根據(jù)當(dāng)時(shí)當(dāng)?shù)厍闆r決策，試著來，發(fā)現(xiàn)不對可以反悔(如同悔棋)。這就是回溯的思想，回溯法寫成算法是極其有用的。,回溯法的算法是： Backtracking(ByRef succ : Boolean) 1確定起始狀態(tài)值走第一步 /本例是c(4,4) = 1 2確定下一步還有幾種可能 /本例是8，其他位置是2，3，4，6，8 3選一可能，走下一步，記住可能和本步特征(I,J,N) 4做完新一步應(yīng)做的事 /本例是

36、c(I,J) = N, N = N+1 5While 目標(biāo)未達(dá)到 Do A確定下一步有幾種可能 BWhile 沒有可能and 還有上一步 do 1) 回退上一步 2) 查有無下一可能 CIf 上一步?jīng)]有了 Return(succ = False) D選一可能走一步，記住可能和本步特征 E做完新一步應(yīng)做的事 6Return(succ = True) 讀者可按這個(gè)框架寫出騎士周游的算法。,3.2 數(shù) 據(jù) 結(jié) 構(gòu),上一節(jié)談到算法必須有輸入/輸出，也就是算法必須有操作對象它才能有的放矢。有些算法的操作對象很簡單，幾個(gè)變量就可以了，例如方程求根。有一些則不然，操作的對象是一組相互有關(guān)的數(shù)據(jù)，脫離了數(shù)據(jù)的

37、關(guān)聯(lián)性算法就無從施展。例如，上節(jié)的快速分類、騎士周游、荷蘭國旗問題就是一維數(shù)組和二維矩陣上展開的，前面也談到計(jì)算的結(jié)構(gòu)模型，所謂結(jié)構(gòu)就是許多元素和它們的聯(lián)系在拓?fù)淇臻g形成有界的整體。這些元素如果是數(shù)據(jù)，即為數(shù)據(jù)結(jié)構(gòu)，如果是操作就是過程的結(jié)構(gòu)模型(流程圖、數(shù)據(jù)流圖、活動圖、用例圖都是這種結(jié)構(gòu)的圖示)。本節(jié)討論數(shù)據(jù)結(jié)構(gòu)，即數(shù)據(jù)元素及其相互結(jié)構(gòu)關(guān)系。,3.2.1 數(shù)據(jù)的結(jié)構(gòu)關(guān)系,單個(gè)的數(shù)據(jù)(變量)雖然能解決不少問題，但經(jīng)常遇到要計(jì)算的問題其數(shù)據(jù)往往是關(guān)聯(lián)的。甚至不關(guān)聯(lián)就失去處理的價(jià)值。先分析幾個(gè)例子： (1) 名字串ZhangSan 這八個(gè)字符串在一起表示“張三”，少一個(gè)多一個(gè)或次序顛倒都不是張三，

38、計(jì)算機(jī)在處理它時(shí)，一起存，一起取，除非張三改名。每個(gè)字符數(shù)據(jù)和其他數(shù)據(jù)是鄰接的關(guān)系。,(2) 火車行車時(shí)刻表 這是一個(gè)二維表單，將車次、時(shí)間和站名放在一起就可以回答很多問題：“早上78點(diǎn)到武漢可在北京乘T37次、T77次”，“從北京站到武漢站最快要12小時(shí)”就不單是“T37次北京18：53開”一條信息了，把這個(gè)表輸入到計(jì)算機(jī)，連查找的功夫都可以省。 計(jì)算機(jī)之所以“聰明”是因?yàn)樗鼤槎S矩陣。,(3) 分配工作圖3.4 申請職位關(guān)系圖 有五個(gè)不同專業(yè)的人申請五個(gè)不同職位，每人填兩個(gè)志愿，申請情況如圖3.4所示： 人名A、B、C、D、E，職位a、b、c、d、e都是長串的字符串?dāng)?shù)據(jù)的簡寫。申請志愿的

39、聯(lián)線把它們連成一個(gè)圖。圖就是數(shù)據(jù)結(jié)構(gòu)，是寫分派工作算法的解題模型。分配的結(jié)果是每人都滿足了志愿，而每個(gè)職位都有人干。,圖3.4 申請職位關(guān)系圖,這個(gè)例子小到一眼就看到結(jié)果。但如果申請人是1275人，職類87，職位44，志愿13，不用計(jì)算機(jī)算就太費(fèi)事了。編個(gè)程序先按基本條件刪去一部分人，然后按每個(gè)職類計(jì)劃的職位和申請的人數(shù)分配，打出一張錄用表。 描述這個(gè)圖不外乎數(shù)據(jù)集合 D = A,B,C,D,E, a,b,c,d,e 和它們的關(guān)系集合 R = , 表示前后兩數(shù)據(jù)有關(guān)系，且次序不能倒，如次序可逆用(,)。 數(shù)據(jù)及其關(guān)系構(gòu)成數(shù)據(jù)結(jié)構(gòu) 由以上例子看出數(shù)據(jù)結(jié)構(gòu)只由兩種集合構(gòu)成： DS = (D，R)

40、數(shù)據(jù)集合D，可以是單個(gè)數(shù)據(jù)集合，也可以是不同類型子集組成的大集合，甚至可以是數(shù)據(jù)結(jié)構(gòu)。第一個(gè)例子的字符串本身是字符的數(shù)據(jù)結(jié)構(gòu)，字符串集合也是數(shù)據(jù)集合。 關(guān)系集合R指數(shù)據(jù)間的結(jié)構(gòu)關(guān)系。這里的數(shù)據(jù)間關(guān)系很抽象的，兩數(shù)據(jù)只是有關(guān)不問具體是什么關(guān)系，例如單值函數(shù)關(guān)系，用集合表示法枚舉每個(gè)關(guān)系：,函數(shù)關(guān)系sin是 用集合論關(guān)系的形式符號表達(dá)方式是很基本的。常用于證明某種數(shù)據(jù)結(jié)構(gòu)的某些性質(zhì)。數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的結(jié)構(gòu)關(guān)系。請看下例： DS1 = (D1,R1) D1 = a,b,c,d,e R1 = (a,b),(b,c),(c,d),(d,e),(e,a),(a,c),(a,d),(b,e),(c,e)

41、,畫成圖形如圖3.5(a)所示，DS1是一個(gè)無向圖。 若 DS2 = (D1,R2) D1 = a,b,c,d,e R2=, 畫成圖形如圖3.5(b)所示，DS2是一個(gè)有向圖。,圖3.5 無向圖和有向圖,若 DS3 = (D3,R3) D3 = a1,a2,ak R3 = |1ik1 這個(gè)關(guān)系R3說明任何兩遞增下標(biāo)的數(shù)據(jù)元素都有相鄰關(guān)系，畫出圖形如圖3.6所示，是一個(gè)數(shù)組。,圖3.6 數(shù)組數(shù)據(jù)結(jié)構(gòu),若 DS4 = (D4,R4) D4 = a,b,c,d,e,f R4 = , 它們的結(jié)構(gòu)關(guān)系如圖3.7所示，是一種樹型數(shù)據(jù)結(jié)構(gòu)。,圖3.7 樹的數(shù)據(jù)結(jié)構(gòu),3.2.2 數(shù)據(jù)結(jié)構(gòu)的研究方法,從上節(jié)的例

42、子可以看出，數(shù)據(jù)結(jié)構(gòu)的基本概念是非常簡單的：數(shù)據(jù)元素及其關(guān)系。由于關(guān)系不同可以形成不同的結(jié)構(gòu)，它們的計(jì)算特性也各不相同。如果能找出其中最基本的幾種，熟知這幾種的計(jì)算特性，那么，以數(shù)據(jù)結(jié)構(gòu)模擬客觀世界的數(shù)據(jù)，依托它寫算法就十分方便了。如上所述，數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素，也可以擴(kuò)充成數(shù)據(jù)結(jié)構(gòu)(圓圈擴(kuò)充成為一個(gè)圖或表或樹)。這樣，極其復(fù)雜的結(jié)構(gòu)也能表達(dá)，其計(jì)算特性不外乎疊加。所以，熟知基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)是極為重要的。,按一般文獻(xiàn)的介紹，數(shù)據(jù)結(jié)構(gòu)分四大類： 表 元素是線性關(guān)系(連接) 圖 元素間是非線性關(guān)系(連接) 樹 元素間是非線性關(guān)系，連接不得有回路 文件 記錄的序列,研究方法 研究每種數(shù)據(jù)結(jié)構(gòu)可以實(shí)施什

43、么算法，這些結(jié)構(gòu)都能映象到機(jī)器的存儲中，實(shí)施的算法才有意義。 這四類最基本的數(shù)據(jù)結(jié)構(gòu)最重要的是表類，因?yàn)樗苯訉?yīng)為機(jī)器對數(shù)據(jù)的操作，找出首地址拉出一長串?dāng)?shù)據(jù)，或按首地址位移多少地址即可找到某元素(索引)。如果不是存放在一起，每個(gè)元素跟下一個(gè)元素的地址(指針)也是線性表。因?yàn)橛酶呒壵Z言編程寫算法，不能涉及具體地址只說線性表和線性鏈表。至于其他的數(shù)據(jù)結(jié)構(gòu)機(jī)器是不能直接操作的，都得化為簡單表來處理。即使是稍微復(fù)雜一點(diǎn)的表，如二維矩陣，則每個(gè)元素也是按一維數(shù)組的數(shù)組元素來處理，所以在討論每種數(shù)據(jù)結(jié)構(gòu)時(shí)： 首先研究它的邏輯結(jié)構(gòu)有什么運(yùn)算性質(zhì) 用什么表示法表示這種邏輯結(jié)構(gòu)(表或鏈表或復(fù)合) 再按表示法和

44、性質(zhì)寫出求解問題的算法 下文中都是按這個(gè)辦法處理的，此處不再舉例。,邏輯結(jié)構(gòu)和物理結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)是十分抽象的，學(xué)會了基本結(jié)構(gòu)：表、圖、樹、文件，就可以用它們的復(fù)合模型刻畫事物的本質(zhì)。這樣就形成了邏輯結(jié)構(gòu)，它是客觀世界數(shù)據(jù)關(guān)系的真實(shí)反映。但計(jì)算機(jī)只能處理最簡單的結(jié)構(gòu)，這就形成了邏輯結(jié)構(gòu)和物理(實(shí)現(xiàn))結(jié)構(gòu)的分離。正如艾菲爾鐵塔、長江大橋的拱頂是不同的邏輯結(jié)構(gòu)，滿足不同的用途，它們的物理結(jié)構(gòu)都是各型鋼鐵焊接(或鉚接)的結(jié)構(gòu)。討論問題或程序感興趣的是邏輯結(jié)構(gòu)，而程序的實(shí)現(xiàn)非物理結(jié)構(gòu)不行。 這里還要說明邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是相對的，直接討論矩陣的元素寫兩個(gè)下標(biāo)A(i,j)非常直觀，但機(jī)器自動把它轉(zhuǎn)為一維下

45、標(biāo)A(n)后才能實(shí)現(xiàn)計(jì)算。前者在邏輯結(jié)構(gòu)上說話，后者在物理結(jié)構(gòu)上實(shí)現(xiàn)。一旦能自動實(shí)現(xiàn)，就認(rèn)為它是“物理的”了。在討論圖的表示法時(shí)，二維數(shù)組是實(shí)現(xiàn)圖的物理數(shù)據(jù)結(jié)構(gòu)，也就是不再說二維到一維的實(shí)現(xiàn)了。,數(shù)據(jù)結(jié)構(gòu)的圖形表示 上小節(jié)給出圖、有向圖、數(shù)組、樹的圖形表示法，以及對應(yīng)的基本的集合論定義。在實(shí)用中不去證明數(shù)據(jù)結(jié)構(gòu)的某種性質(zhì)，而是直接使用“定義好”了的結(jié)構(gòu)，觀察它的宏觀性質(zhì)寫算法，不再寫出基本的形式定義，除非要做理論證明工作。無論是邏輯的還是物理的都可以用圖形表示。用一個(gè)框表示數(shù)據(jù)實(shí)體，圓形方形均可。無箭頭連線表示雙向關(guān)系，有箭頭連線表示單向關(guān)系。當(dāng)只有線性關(guān)系且不分離時(shí)，可以不畫連線。圖3.6即

46、為實(shí)例。 以下分別討論這四類數(shù)據(jù)結(jié)構(gòu),3.2.3 線性表,線性表的邏輯結(jié)構(gòu)是n個(gè)數(shù)據(jù)元素的有限序列: (a1, a2 ,a3,an) 表中元素的個(gè)數(shù)n定義了線性表的長度(n0)，n = 0的表稱為空表。 線性表的結(jié)構(gòu)特征是：數(shù)據(jù)元素呈線性關(guān)系。線性表隱含是有序的，它必存在惟一的“第一個(gè)”數(shù)據(jù)元素和“最后一個(gè)”數(shù)據(jù)元素； 除第一個(gè)元素外，每個(gè)元素都有一個(gè)且只有一個(gè)前驅(qū)元素； 除最后一個(gè)元素外，每個(gè)元素都有且只有一個(gè)后繼元素。在同一個(gè)線性表中所有數(shù)據(jù)元素ai必須是相同的數(shù)據(jù)結(jié)構(gòu)，它可以是同類型的數(shù)，同一類符號或同樣復(fù)雜的結(jié)構(gòu)。,圖3.8 線性表的示意圖 線性表的邏輯圖如圖3.8所示： 線性表也可以

47、用機(jī)器能直接接受的符號串表示法，用括號括著的元素名或值。例如可以按問題需要建立以下線性表： 表1：(李研，劉豐，陳宏英) 表2：(李研,98,99,100,297,99.0), (劉豐,97,96,94,287,95.7)， (陳宏英,94,96,99,289,96.3) 表1是名字表。表2的數(shù)據(jù)元素是(姓名，語文成績，數(shù)學(xué)成績，英語成績，總分，平均分)具體的值。雖然不是同一類型數(shù)據(jù)，但所有元素均是同一種形式。它是由簡單表組成的線性表。,圖3.8 線性表的示意圖,線性表的基本運(yùn)算主要有： 創(chuàng)建一個(gè)新表，包括無表元素的空表 在兩個(gè)確定的元素之間插入一個(gè)新的元素 刪除線性表中某個(gè)元素 按某種要求查

48、找線性表中的一個(gè)元素，按需要更新表元素 計(jì)算表長(元素個(gè)數(shù)) 重排表元素，即排序 合并兩個(gè)表 第1種操作在高級語言中只要聲明，編譯程序就可以替你完成。其余的要先決定表的表示法，再寫算法。,順序表和一維數(shù)組 沒有特殊說明，表是隱含順序存放的。如果要插入或刪除一個(gè)元素，那么在這個(gè)元素以后的元素存儲位置都要改動。為了顯式地操作存放順序，則定義了數(shù)組。數(shù)組是以一維下標(biāo)索引的順序表。數(shù)組一旦聲明其長度不可改變，中間也不許刪除或插入。這就找到了一個(gè)不變的舞臺，讓順序表在其上演繹變動。 下面是順序表插入和刪除的算法。線性表的查找見3.3節(jié)。其余操作讀者可以參考這幾個(gè)算法寫出。,插入 在線性表(a1, a2,

49、，ai，ai+1，an)的第i個(gè)位置插入元素x，使之成為(a1, a2,，ai，x，ai+1，an)，其算法描述如下： Insert(ByRef A:Type,n,i,x)/一維數(shù)組A(1n)第i個(gè)元素之前插入一個(gè)新元素x If(in+1) ERROR(“位置不存在！”) /插入的位置不合法 Else for（j=n; ni; j-） A(j+1) = A(j) /元素后移 A(i) = x /進(jìn)行插入 n = n+1 /線性表的長度加1 從上述算法可見，當(dāng)i = n+1，語句A(j+1) = A(j)將不執(zhí)行，因?yàn)榇藭r(shí)循環(huán)變量的終值大于初值，即不需要移動元素而直接將x插入到A(n+1)的位置

50、上去即可。反之，當(dāng)i = 1時(shí)，語句A(j+1) = A(j)將執(zhí)行n次，即需將線性表中原已存在的n個(gè)元素均后移一個(gè)元素的位置才能進(jìn)行插入。所以，若順序表中元素個(gè)數(shù)為n，在往每個(gè)位置插入的概率相等的情況下，插入一個(gè)元素的平均移動元素個(gè)數(shù)為n/2。,刪除 一般情況下，在表長為n的線性表(a1, a2 ,，ai1,ai，ai+1，an)中刪除第i個(gè)數(shù)據(jù)元素，還需將第i+1個(gè)至第n個(gè)元素向前推動一個(gè)位置，即(a1, a2 ,，ai1,ai+1，an)，其算法描述如下： Delete (ByRef A, n,i) /一維數(shù)組A(1:n)中的第i個(gè)元素處刪除該元素x If (in) ERROR (位置不

51、存在！) /刪除的位置不合法 Else for（j = i; in1; i+）A(j) = A(j+1) /元素前移 n = n1 /表長減1 和插入的情況類似，當(dāng)i = n時(shí)，語句A(j) = A(j+1)將不執(zhí)行，因?yàn)檠h(huán)變量的初值大于終值，即不要移動元素；但當(dāng)i = 1時(shí)，語句A(j) = A(j+1)將執(zhí)行n1次，此時(shí)需將線性表中除第一個(gè)元素之外的所有元素均向前移動一個(gè)位置。所以，在等概率的情況下，刪除順序表中一個(gè)元素平均需要移動的元素個(gè)數(shù)為(n1)/2。,鏈表 以數(shù)組實(shí)現(xiàn)順序表，插入或刪除元素時(shí)，都不可避免地要作元素的移動，每進(jìn)行一次插入或刪除，都要移動近乎一半的元素。又由于數(shù)組是定

52、長的連續(xù)存儲單元，對于長度可變的線性表，只好按其可能達(dá)到的最大長度預(yù)先分配空間。這可能由于估計(jì)不足造成一部分空間太長而得不到充分利用，也可能因空間過短而造成溢出。鏈表恰能有效地克服這些缺點(diǎn)。鏈表一般有單鏈表、雙向鏈表和循環(huán)鏈表等。,(1) 單鏈表 單鏈表就是鏈?zhǔn)酱鎯Φ木€性表，其元素除信息域外還含有一個(gè)指針域，用來指出其后繼元素的位置。元素的結(jié)構(gòu)如圖3.9所示。單鏈表的最后一個(gè)結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)，它的指針域?yàn)榭?記為NIL或)。另外還需要設(shè)置一個(gè)頭指針head，指向單鏈表的第一個(gè)結(jié)點(diǎn)。,圖3.9 單鏈表中的結(jié)點(diǎn)結(jié)構(gòu),例如，上述表1： (李研，劉豐，陳宏英) 的單鏈表實(shí)現(xiàn)如圖3.10所示。 鏈表的一

53、個(gè)重要特點(diǎn)是插入、刪除運(yùn)算靈活方便，不需移動元素，只要改變元素中指針域的值即可。圖3.11(a)、(b)分別示出了從單鏈表中，插入一個(gè)新元素和刪除一個(gè)元素的鏈接。虛線表示變化后的指針。,圖3.10 單鏈表邏輯圖,圖3.11 單鏈表的插入和刪除,鏈表插入元素的算法如下： InsertLink (list, Q : pointer, /每個(gè)結(jié)點(diǎn)有兩個(gè)域如圖3.9 Item : Integer) Call GetNode(P) /申請一個(gè)結(jié)點(diǎn)返回指向該結(jié)點(diǎn)的指針P PInfo = item If (list = Nil ) list = P; listNext = Nil /如原鏈表為空 Else

54、PNext = QNext /在Q所指結(jié)點(diǎn)之后插入item QNext = P 其他算法讀者可以自行寫出，值得一提的是鏈表有一個(gè)操作是所有指針逆反，可以很快得到反向排序的表。 鏈表是十分有用的數(shù)據(jù)結(jié)構(gòu)。它有助于快速方便地使用信息。例如，機(jī)器中按順序錄入了10個(gè)人的信息，人員還在不斷增減要保證打印的文件總是按某種原則排序(如年齡、級別、工資等級、性別等)，為了不致大量重排和移動所有數(shù)據(jù)，用鏈表排序最方便，信息只按先后次序存入且次序不變，按鏈表排序后打印，即可滿足要求。排序的工作量是很小的。,(2) 循環(huán)鏈表 循環(huán)鏈表是結(jié)構(gòu)形式和單鏈表稍有不同的一種鏈表，如圖3.12所示，其差別僅在于鏈表中最后一

55、個(gè)結(jié)點(diǎn)的指針域不為“NIL”，而是指向頭一個(gè)結(jié)點(diǎn)，整個(gè)鏈表成為一個(gè)由鏈指針相鏈結(jié)的環(huán)，故稱之為循環(huán)鏈表。其插入、刪除算法和單鏈表沒有多大區(qū)別。 循環(huán)鏈表應(yīng)用也是極其廣泛的。例如，要10分鐘內(nèi)公布一次股票漲落行情，則把所有股票號接成一個(gè)循環(huán)鏈表。有一批錄入員負(fù)責(zé)行情變化錄入，每人只管負(fù)責(zé)幾個(gè)號的漲落行情錄入，報(bào)表程序按鏈表依次處理各股票10分鐘之內(nèi)的變化。,圖3.12 循環(huán)鏈表示意圖,(3) 雙向鏈表 在實(shí)際應(yīng)用中，鏈表結(jié)點(diǎn)可根據(jù)需要來設(shè)定。對于線性表來說，除了設(shè)有指向后繼結(jié)點(diǎn)的指針外，還可設(shè)一個(gè)指向前驅(qū)結(jié)點(diǎn)的指針。習(xí)慣稱這種含有兩個(gè)指針域的結(jié)點(diǎn)構(gòu)成的鏈表為雙向鏈表。其結(jié)構(gòu)如圖3.13所示。 由

56、于每個(gè)結(jié)點(diǎn)中都設(shè)有兩個(gè)指針，則不僅可直接得到后繼結(jié)點(diǎn)的信息，也容易得到前驅(qū)結(jié)點(diǎn)的信息。這對某些需要逆向查找的算法特別有用，還可以增大表的安全性。但在作插入、刪除運(yùn)算時(shí)，需要同時(shí)修改兩個(gè)方向上的指針。一般情況下稱結(jié)點(diǎn)含有多個(gè)指針域的鏈表為多重鏈表，雙向鏈表是多重鏈表的一種。,圖3.13 雙向鏈表圖例,棧 除了前面講的線性表外，棧(stack)是一種特殊的線性表，對它的操作只能是“后進(jìn)先出”(LIFO)，也是使用最為廣泛的數(shù)據(jù)結(jié)構(gòu)之一。因?yàn)樗倪\(yùn)算次序受到嚴(yán)格的限定，故又稱限定性數(shù)據(jù)結(jié)構(gòu)。,圖3.14 棧的邏輯結(jié)構(gòu),(1) 棧的結(jié)構(gòu)特點(diǎn)圖3.14 棧的邏輯結(jié)構(gòu) 在日常生活中，很多事務(wù)是按照“后到達(dá)

57、的比先到達(dá)的優(yōu)先”的順序處理的。例如，穿衣服的順序是先襯衫，后制服，最后是大衣。脫衣服的順序必須反過來，最先脫的是最后穿上的大衣。若想在襯衫和制服之間加一件毛衣時(shí)，必須先脫下大衣和制服，才能穿上毛衣。又如，玩具手槍的子彈壓入子彈夾時(shí)，總是要將子彈一粒粒按順序壓入，而射擊時(shí)卻是最后壓入的一粒先打出來，而最先壓入的最后一個(gè)被射出。棧的結(jié)構(gòu)特點(diǎn)正是這些事物的抽象。 棧是限定僅在表尾進(jìn)行插入和刪除運(yùn)算的線性表，表尾稱為棧頂(top)，表頭稱為棧底(bottom)。表中無元素時(shí)稱為空棧。如圖3.14所示的棧中，元素按a1, a2 ,a3,an的順序進(jìn)棧，a1稱為棧底元素。新元素進(jìn)棧要置于an之上，刪除或

58、退棧必須先對an進(jìn)行操作。棧體的物理存儲可以用順序表結(jié)構(gòu)，也可用鏈表。,(2) 棧的運(yùn)算 通常對棧進(jìn)行的運(yùn)算有：設(shè)置一個(gè)空棧、判定某個(gè)棧是否為空棧、進(jìn)棧、退棧以及讀取棧頂元素等。下面分別給出以順序表實(shí)現(xiàn)的棧和進(jìn)棧、退棧的算法： 進(jìn)棧 PushStack (ByRef stack，m，top，x) /在棧Stack(1:m)的棧頂top之上插入元素x If ( top = m) ERROR (“棧滿！”) Else top = top+1 /棧頂上移 stack(top) = x /將x放入棧頂 退棧 Func PopStack (ByRef stack，top，y)：Bool /當(dāng)?？諘r(shí)返回FALSE， If (top = 0) Return(False) /反之退出棧頂元素賦給變量y并返回TRUE Else y = stack(top) /將棧頂元素賦給變量y top = top1 /棧頂下移圖3.15 鏈棧存儲結(jié)構(gòu) Return(True) EndFunc,當(dāng)棧的最大容量事先不能估計(jì)時(shí)，也可采用鏈表作存儲結(jié)構(gòu)，簡稱鏈棧。如圖3.15所示。圖中top為棧頂指針，指示