算法+數(shù)據(jù)結(jié)構(gòu)=程序

1、算法+數(shù)據(jù)結(jié)構(gòu)=程序-評(píng)數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用-C+語(yǔ)言描述記得Pascal之父、結(jié)構(gòu)化程序設(shè)計(jì)的先驅(qū)Niklaus Wirth最著名的一本書(shū)，書(shū)名叫作算 法+數(shù)據(jù)結(jié)構(gòu)=程序，算法與數(shù)據(jù)結(jié)構(gòu)之于程序設(shè)計(jì)的重要性不言自明。那么，什么是 算法？什么是數(shù)據(jù)結(jié)構(gòu)？什么又是程序呢？我們先從闡明大家最為熟悉的”程序”的概念入手。程序是計(jì)算機(jī)指令的某種組合，控制 計(jì)算機(jī)的工作流程，完成一定的邏輯功能，以實(shí)現(xiàn)某種任務(wù)；再來(lái)看什么是算法，算法是程 序的邏輯抽象，是解決某類(lèi)客觀(guān)問(wèn)題的數(shù)學(xué)過(guò)程；最后我們來(lái)看一看數(shù)據(jù)結(jié)構(gòu)又是什么呢？ 在這里，數(shù)據(jù)結(jié)構(gòu)具有兩個(gè)層面上的涵義-邏輯結(jié)構(gòu)和物理結(jié)構(gòu)：客觀(guān)事物自身所具有的結(jié) 構(gòu)特

2、點(diǎn)，我們將其稱(chēng)之為邏輯結(jié)構(gòu)。如家族譜系是一個(gè)天然的樹(shù)型邏輯結(jié)構(gòu)。而邏輯結(jié)構(gòu)在 計(jì)算機(jī)中的具體實(shí)現(xiàn)則稱(chēng)之為物理結(jié)構(gòu)。如樹(shù)型邏輯結(jié)構(gòu)是用指針表示還是使用數(shù)組實(shí)現(xiàn)。仔細(xì)體會(huì)一下，就會(huì)發(fā)現(xiàn)算法與數(shù)據(jù)結(jié)構(gòu)間的緊密性。用一個(gè)較為貼切的例子來(lái)形容， 若把數(shù)據(jù)結(jié)構(gòu)喻為建筑工程中的建筑設(shè)計(jì)圖，那么算法就是工程中的施工流程圖。數(shù)據(jù)結(jié)構(gòu) 與算法呈相互依托的關(guān)系，恰當(dāng)?shù)拇_立了問(wèn)題的結(jié)構(gòu)，問(wèn)題的解決才能根據(jù)確立的層次結(jié)構(gòu) 選擇合適的解決方法。因此任何講解數(shù)據(jù)結(jié)構(gòu)的書(shū)都不可能撇開(kāi)算法，單單介紹數(shù)據(jù)結(jié)構(gòu)， 反之亦然。下面，我們就來(lái)看看IEEE 97Booth教育獎(jiǎng)獲得者Sartaj Sahni是如何處理數(shù)據(jù)結(jié) 構(gòu)、算法和程

3、序他們?nèi)咧g的關(guān)系的吧！一般來(lái)說(shuō)，計(jì)算機(jī)專(zhuān)業(yè)著作有兩種基本寫(xiě)作方式：一種是教材，一種是百科全書(shū)。本書(shū) 是按照大學(xué)教材的結(jié)構(gòu)來(lái)寫(xiě)的，然而令人驚訝的是本書(shū)的內(nèi)容是如此的豐富，以至于同樣可 以將它看作是一本關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法的大全。顯然，這本書(shū)并不適合初學(xué)，將它作為數(shù)據(jù) 結(jié)構(gòu)進(jìn)階學(xué)習(xí)的第二本書(shū)是恰當(dāng)?shù)?。這本書(shū)最為顯著的特點(diǎn)是特別注重應(yīng)用，我們很快就會(huì) 看到這一點(diǎn)。首先，我們來(lái)看一看數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用-C+語(yǔ)言描述這本書(shū)的組織結(jié)構(gòu)。書(shū) 由三個(gè)部分組成：預(yù)備知識(shí)、數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)。第一部分預(yù)備知識(shí)回顧了具備面向?qū)ο筇匦缘腃+語(yǔ)言的重要特征。因?yàn)椴皇窃诮榻B C+語(yǔ)言，這里的回顧和前提引入直接切入到了

4、 C+中許多重要而又易被忽略以至于顯得較 為模糊的概念。參數(shù)傳遞、函數(shù)返回、模板、遞歸還有操作符重載等等，如若在以前學(xué)習(xí) C+時(shí)，對(duì)其理解不是十分深入的話(huà)，你是否清楚在什么樣的情形下函數(shù)返回引用更為合適 呢？隨后探討程序時(shí)空復(fù)雜性的分析、測(cè)量與漸進(jìn)符號(hào)（0、Q、。），為后面的算法 分析內(nèi)容建立基礎(chǔ)。較為特別的是，作者提早在第一部分就講述了程序設(shè)計(jì)中的一些基本設(shè) 計(jì)方法：簡(jiǎn)單的排序與搜索算法、多項(xiàng)式求值和矩陣運(yùn)算。這樣做是要冒風(fēng)險(xiǎn)的（對(duì)基礎(chǔ)差 一些的讀者來(lái)說(shuō)就會(huì)覺(jué)得難度較大），不過(guò)作者深厚的寫(xiě)作功力使其顯得自然而又恰如其分。第二部分?jǐn)?shù)據(jù)結(jié)構(gòu) 是本書(shū)的主體，闡述線(xiàn)性表、數(shù)組、矩陣、堆棧、隊(duì)列、跳躍

5、表、 散列、二叉樹(shù)、優(yōu)先隊(duì)列、競(jìng)賽樹(shù)、搜索樹(shù)還有圖。與一般的數(shù)據(jù)結(jié)構(gòu)書(shū)不同，這里采用了 四種不同的數(shù)據(jù)描述方法：公式化描述、鏈接描述、間接尋址和模擬指針。隨著學(xué)習(xí)的深入， 你很快就可以發(fā)現(xiàn)相同的邏輯結(jié)構(gòu)，其物理結(jié)構(gòu)的實(shí)現(xiàn)竟是如此的不同。而不同的物理結(jié)構(gòu) 又各自存在著自己的優(yōu)缺點(diǎn)，這是由不同的物理結(jié)構(gòu)的自身特點(diǎn)所決定的。例如：使用數(shù)組 實(shí)現(xiàn)的線(xiàn)性表可直接存取元素，然而元素插入與刪除的效率卻特別低；而若線(xiàn)性表采用鏈表 描述，則正好與順序表的優(yōu)缺點(diǎn)相反。若欲博采眾長(zhǎng)，就必須設(shè)計(jì)或是選擇更為復(fù)雜的數(shù)據(jù) 結(jié)構(gòu)，這又為算法設(shè)計(jì)帶來(lái)了更多的麻煩。而且，整體結(jié)構(gòu)和具體實(shí)現(xiàn)會(huì)顯得不是那么清晰 與自然，甚至?xí)兊?/p>

6、非常的難于理解。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的訣要就在于掌握基本的數(shù)據(jù)結(jié)構(gòu)，在解決現(xiàn)實(shí)問(wèn)題時(shí)選擇合適的結(jié)構(gòu)或 設(shè)計(jì)更為恰當(dāng)?shù)哪Ｐ?，然后根?jù)確立的結(jié)構(gòu)特性編寫(xiě)出算法。我們前面提到的關(guān)于本書(shū)最為獨(dú)特的地方就在于它特別強(qiáng)調(diào)應(yīng)用。這一特色，就表現(xiàn)在 這第二部分中。書(shū)中給出了大量來(lái)自不同領(lǐng)域的應(yīng)用：布線(xiàn)路由、元件折疊、電路板排列、 LZW壓縮編碼、迷宮問(wèn)題、工廠(chǎng)仿真、貨箱裝船、LPT調(diào)度、貨郎擔(dān)問(wèn)題這些具體問(wèn)題 的實(shí)現(xiàn)不僅使學(xué)習(xí)充滿(mǎn)了樂(lè)趣，而且所選擇出來(lái)的典型實(shí)例對(duì)于我們解決現(xiàn)實(shí)問(wèn)題具有很強(qiáng) 的指導(dǎo)作用。同時(shí)，這些經(jīng)典實(shí)例的實(shí)現(xiàn)能夠大幅度提高我們閱讀和編寫(xiě)復(fù)雜的大型程序的 能力。我們的程序設(shè)計(jì)能力和算法思維能力的提高，

7、正是建立在對(duì)基本數(shù)據(jù)結(jié)構(gòu)和算法原理 的理解以及閱讀中、大型程序源代碼的基礎(chǔ)上的。本書(shū)的第三部分側(cè)重于計(jì)算機(jī)算法的分析與實(shí)現(xiàn)。書(shū)中提供了五種基本的算法設(shè)計(jì)方 法：貪婪算法、分而治之算法、動(dòng)態(tài)規(guī)劃、回溯和分支定界。由于這里已經(jīng)是書(shū)末，讀者的 基礎(chǔ)知識(shí)已經(jīng)相當(dāng)?shù)某鋵?shí)，故而本部分也是本書(shū)最難的地方。算法的定義采用了正式的數(shù)學(xué) 定義，有算法引論或組合數(shù)學(xué)基礎(chǔ)的讀者會(huì)更容易理解一些。正如文前所述，這里更強(qiáng)調(diào)的是問(wèn)題的解決過(guò)程，合適的算法將可能會(huì)使解決問(wèn)題的復(fù) 雜度降低幾個(gè)數(shù)量級(jí)。如順序搜索與折半搜索、冒泡排序與快速排序性能上的差異足以決定 解決問(wèn)題的可能性。在這里，作者同樣強(qiáng)調(diào)如何選擇合適的算法設(shè)計(jì)方法，

8、建立起針對(duì)特定 的實(shí)際應(yīng)用的解決方法。找偽幣、找零錢(qián)、分金塊、迷宮老鼠、棋盤(pán)覆蓋等豐富而生動(dòng)的事 例中蘊(yùn)含著深刻的算法思想，同樣的問(wèn)題利用不同的算法設(shè)計(jì)方法通過(guò)不同途徑得到解。正 如前面所述，算法的確定依賴(lài)于數(shù)據(jù)結(jié)構(gòu)的選擇，數(shù)據(jù)結(jié)構(gòu)的選擇制約于算法設(shè)計(jì)的復(fù)雜程 度-算法+數(shù)據(jù)結(jié)構(gòu)=程序。數(shù)據(jù)結(jié)構(gòu)與算法方面的好書(shū)很多，我在這里沒(méi)有作一一介紹，而是著重推薦了一些經(jīng)典 著作：計(jì)算機(jī)編程藝術(shù)The Art of Computer Programming（Volume I - III）第1卷 基本算法、 第2卷半數(shù)值算法、第3卷排序與查找）國(guó)防工業(yè)出版社數(shù)據(jù)結(jié)構(gòu)的開(kāi)拓者D.E.Knuth 高德納編著的計(jì)

9、算機(jī)科學(xué)發(fā)展史上的不朽之作。第1卷基本算法介紹計(jì)算機(jī)程序設(shè)計(jì)的基 本算法，包括基本的編程概念和技術(shù)以及信息結(jié)構(gòu)-機(jī)內(nèi)信息的表示、數(shù)據(jù)元及其處理的結(jié) 構(gòu)關(guān)系；第2卷半數(shù)值算法介紹隨機(jī)數(shù)和算術(shù)，提供了計(jì)算機(jī)編程和數(shù)值分析之間的豐富 接口；第3卷排序與查找介紹排序和查找的最權(quán)威的經(jīng)典技術(shù)，擴(kuò)充了第1卷的數(shù)據(jù)結(jié)構(gòu)， 以處理大小型數(shù)據(jù)庫(kù)及內(nèi)外部存儲(chǔ)。本書(shū)偏重分析技術(shù)，采用匯編語(yǔ)言描述算法，是一本本 學(xué)科最經(jīng)典最權(quán)威的百科全書(shū)，適合于從事數(shù)據(jù)結(jié)構(gòu)與算法研究的專(zhuān)家閱讀。算法+數(shù)據(jù)結(jié)構(gòu)=程序科學(xué)出版社Pascal之父Niklaus Wirth著一本簡(jiǎn)潔、清 晰具有深刻內(nèi)涵的小冊(cè)子。介紹了許多巧妙的程序設(shè)計(jì)技術(shù)，書(shū)中還完成了一個(gè)簡(jiǎn)單的程序 設(shè)計(jì)語(yǔ)言的實(shí)現(xiàn)，真不愧為世界級(jí)的編譯器設(shè)計(jì)專(zhuān)家。這本書(shū)的難度也很大，將它作為數(shù)據(jù) 結(jié)構(gòu)高級(jí)讀物更好一些。數(shù)據(jù)結(jié)構(gòu)與算法美A.V.阿霍，美J.E.霍普克羅夫特著看看作者名字就知道這本書(shū) 的水平