• 原書(shū)名： The Tomes of Delphi Algorithms and Data Structures
• 原出版社： Wordware Publishing
• 作者： [美]Julian Bucknall
• 譯者： 林琪 朱濤江
• 叢書(shū)名： Delphi技術(shù)系列
• 出版社：中國(guó)電力出版社
• ISBN：7508314832
• 上架時(shí)間：2003-8-14
• 出版日期：2003 年8月
• 開(kāi)本：16開(kāi)
• 頁(yè)碼：420
• 版次：1-1

內(nèi)容簡(jiǎn)介

Delphi開(kāi)發(fā)人員Julian Bucknall從實(shí)用角度為廣大程序員提供了有關(guān)使用算法和數(shù)據(jù)結(jié)構(gòu)的一個(gè)詳盡的介紹。Bucknall先從算法性能的討論開(kāi)始，涵蓋了諸如數(shù)組、鏈表和二叉樹(shù)等內(nèi)容。這本書(shū)強(qiáng)調(diào)了查找算法（如順序和二分查找），另外也重點(diǎn)介紹了排序算法（包括冒泡排序、插入排序、希爾排序、快速排序和堆排序），此外還提供了有關(guān)的優(yōu)化技術(shù)。不僅如此，作者還介紹了散列和散列表、優(yōu)先隊(duì)列、狀態(tài)機(jī)和正則表達(dá)式以及諸如哈夫曼和LZ77等數(shù)據(jù)壓縮技術(shù)。

隨附光盤(pán)中有作者所開(kāi)發(fā)的一個(gè)相當(dāng)成功的自由軟件庫(kù)EZDSL，另外還有可運(yùn)行于各版本Delphi上和Kylix上的源代碼，此外還提供了TurboPower Software公司的可執(zhí)行程序。

前言

你可能剛剛在書(shū)店里拿起這本書(shū)，也可能已經(jīng)買(mǎi)回家正在翻閱，現(xiàn)在你所需要了解的大概不外乎以下幾個(gè)問(wèn)題……

為什么,要寫(xiě)一本關(guān)于Delphi算法的書(shū)呢

盡管書(shū)店里有關(guān)算法的書(shū)可謂林林總總，但是通常僅涉獵標(biāo)準(zhǔn)計(jì)算機(jī)科學(xué)課程范圍之內(nèi)，而很少能夠從實(shí)用的角度來(lái)研究算法。這些書(shū)中的代碼只是描述了所討論的算法，并沒(méi)有對(duì)相關(guān)技術(shù)在實(shí)際生活中的具體應(yīng)用給予更多考慮。從專業(yè)程序員的角度來(lái)看，其中許多書(shū)都只是大學(xué)院校相應(yīng)課程所用的課本，一些很有意思的內(nèi)容卻往往留給讀者自行練習(xí)，很少有答案，甚至根本沒(méi)有。

當(dāng)然，大部分此類書(shū)并不使用Delphi、Kylix或Pascal。有一些采用偽代碼描述，有些采用C，有些則采用C++，還有一些采用特定(dujour)語(yǔ)言；不過(guò)在最著名也是最常參考的算法書(shū)中則使用了一種根本不存在的匯編語(yǔ)言(如《The Art of Computer Programming》中所用的MIX匯編語(yǔ)言[11，12，13]——請(qǐng)參見(jiàn)“參考文獻(xiàn)”部分)。這些書(shū)在其標(biāo)題中也確實(shí)聲稱可“應(yīng)用”于C、C++乃至Java。這有什么問(wèn)題嗎?畢竟，算法終歸是算法；對(duì)于算法采用何種方式描述應(yīng)該不成問(wèn)題，這樣理解難道不對(duì)嗎?為什么還要費(fèi)勁去購(gòu)買(mǎi)和閱讀一本基于Delphi的算法書(shū)呢?

對(duì)于Delphi，我很自得地認(rèn)為它在目前應(yīng)用開(kāi)發(fā)所用的諸多語(yǔ)言和環(huán)境中可謂獨(dú)樹(shù)一幟。首先，類似于Visual Basic，Delphi也是一種可以快速開(kāi)發(fā)16位或32位Windows應(yīng)用的環(huán)境，而使用Kylix則可以實(shí)現(xiàn)Linux應(yīng)用的快速開(kāi)發(fā)。僅需輕點(diǎn)鼠標(biāo)，組件即可落于窗體之上。有些組件隨后需要雙擊，再鍵入些許代碼，這樣組件之間就可以建立錯(cuò)綜復(fù)雜而又緊密的關(guān)系。如果再加上事件處理程序，就有可能得到一個(gè)看上去很不錯(cuò)的半成品了。

其次，像C++一樣，Delphi也比較接近于底層，可以很容易地訪問(wèn)不同的操作系統(tǒng)API。有些情況下，Borland公司會(huì)開(kāi)發(fā)出訪問(wèn)API的單元，并連同Delphi本身一起銷(xiāo)售：另外一些情況下，程序員會(huì)仔細(xì)分析C的頭文件，從而嘗試將其轉(zhuǎn)換為Delphi的形式(可參見(jiàn)http：／／www,delphi-jedi,org的Jedi項(xiàng)目)。無(wú)論如何，Delphi都可以充分利用其優(yōu)勢(shì)妥善地完成任務(wù)并實(shí)現(xiàn)OS子系統(tǒng)的管理。

Delphi程序員將其本身劃歸為兩大陣營(yíng)：應(yīng)用程序員和系統(tǒng)程序員。不過(guò)有時(shí)你也會(huì)發(fā)現(xiàn)有的程序員二者兼?zhèn)?。這兩個(gè)陣營(yíng)之間的聯(lián)系就在于無(wú)論哪一類程序員都必須同算法世界打交道，同時(shí)對(duì)于算法也必須做到有一定了解。如果你有一定的編程經(jīng)驗(yàn)，可能會(huì)遇到需要編寫(xiě)二分查找(折半查找)代碼的情況。當(dāng)然，在此之前，你可能需要實(shí)現(xiàn)某種排序使數(shù)據(jù)按照一定的順序排列，從而正常地完成二分查找。最后，你還可能開(kāi)始使用某種性能評(píng)測(cè)工具(Profiler)，也許會(huì)發(fā)現(xiàn)TStringList中存在的瓶頸，并希望了解哪一種數(shù)據(jù)結(jié)構(gòu)能夠更有效地完成這一任務(wù)。

作為程序員，算法即是我們工作的全部。初學(xué)者總是很害怕規(guī)范的算法，我的意思是說(shuō)，在習(xí)慣于此之前，甚至這個(gè)詞(algorithm)本身好像都很難拼寫(xiě)。不過(guò)可以這樣來(lái)考慮：程序可定義為一種從用戶獲取信息的算法，并為其產(chǎn)生某種輸出。

歷經(jīng)計(jì)算機(jī)科學(xué)家們的努力，標(biāo)準(zhǔn)算法得到了充分的發(fā)展和完善，這才使諸如你我之輩在編程時(shí)可以“享用”到這些算法。掌握基本算法不僅可以使你的編程技藝得到充分發(fā)揮，并且還可以使你不為選用的語(yǔ)言所左右。例如，如果你了解散列表，這包括其優(yōu)缺點(diǎn)、用途以及如此使用的原因等等，另外還得到了可以立即投入使用的一種具體實(shí)現(xiàn)，那么對(duì)于你目前所開(kāi)發(fā)的子系統(tǒng)或應(yīng)用而言，你對(duì)它的設(shè)計(jì)將有一個(gè)全新的認(rèn)識(shí)，而且會(huì)發(fā)現(xiàn)某些地方利用散列表應(yīng)該更為有利。如果對(duì)于排序你不感覺(jué)發(fā)怵，而且知道它是如何工作的，此外對(duì)于何時(shí)使用選擇排序而不是快速排序也了如指掌，那么你很可能會(huì)在應(yīng)用中自行編寫(xiě)相關(guān)的排序代碼，而不會(huì)借助于某個(gè)標(biāo)準(zhǔn)的Delphi控件來(lái)滿足要求(例如，我就記得曾聽(tīng)說(shuō)過(guò)一個(gè)“聳人聽(tīng)聞”的故事：有人曾使用一個(gè)隱藏的TListBox控件，并在其中加入了一大堆的串，然后將控件的Sorted屬性置為true，力圖用這種方法來(lái)使這些串做到有序)。

也許你會(huì)說(shuō)：“好吧，寫(xiě)算法固然不錯(cuò)，但為什么非要用Delphi或Kylix呢?”順便說(shuō)一句，在此先來(lái)做一個(gè)約定；否則我將不得不寫(xiě)上大量的“Delphi或Kylix”。后面我在提到“Delphi”時(shí)，實(shí)際上指的就是“Delphi或Kylix”。畢竟，Kylix的早期版本即被認(rèn)為是面向Linux的“Delphi”。因此在這本書(shū)中，“Delphi'’就是指面向Windows的Delphi以及面向Linux的Kylix。

下面來(lái)看為什么要用Delphi?其原因有二：Object Pascal語(yǔ)言和操作系統(tǒng)。Delphi的語(yǔ)言中有許多構(gòu)造在其他語(yǔ)言中均沒(méi)有，利用構(gòu)造將使高效的算法和數(shù)據(jù)結(jié)構(gòu)可以更容易也更自然地得以封裝。例如屬性即屬此類，再如若出現(xiàn)不可預(yù)知的錯(cuò)誤時(shí)，相應(yīng)的異常也屬構(gòu)造。盡管在Delphi中不用這些Delphi專用的語(yǔ)言構(gòu)造也完全可以編寫(xiě)出標(biāo)準(zhǔn)算法，但我認(rèn)為，如此一來(lái)我們將無(wú)法感受到這種語(yǔ)言的效率和魅力所在。在本書(shū)中，我們將特意大量使用Delphi中的ObjectPascal語(yǔ)言，在此我沒(méi)有考慮拿到此書(shū)的Java程序員在轉(zhuǎn)換代碼時(shí)可能存在的困難。既然封面上標(biāo)明Delphi，那么我們就一心一意地使用Delphi吧。

其次要考慮的是，傳統(tǒng)意義上對(duì)算法的認(rèn)識(shí)均體現(xiàn)在通用性上，至少?gòu)腃PU和操作系統(tǒng)的角度來(lái)看需要如此。這些算法當(dāng)然可以針對(duì)W~mdows環(huán)境得到優(yōu)化，也可以面向Linux進(jìn)行改進(jìn)。對(duì)于我們所用的各種類型的Pentium處理器、各種不同的內(nèi)存緩存器、OS中不同的虛存子系統(tǒng)等等，算法還可以做到更為高效。這本書(shū)將特別關(guān)注于在效率上所獲得的收益。不過(guò)，我們不至于什么代碼都拿匯編語(yǔ)言來(lái)編寫(xiě)，盡管它對(duì)于當(dāng)前處理器的管道式體系結(jié)構(gòu)來(lái)說(shuō)應(yīng)該是最優(yōu)化的，但有些地方我還是必須明確其使用要有一定限制!

因此，無(wú)論怎樣，廣大Delphi群體確實(shí)需要一本算法方面的書(shū)，而且迫切需要它完全針對(duì)于特定的語(yǔ)言、操作系統(tǒng)和處理器，而本書(shū)正是應(yīng)此需而生。它不是由面向其他語(yǔ)言的其他書(shū)翻譯得來(lái)的。不僅這本書(shū)本身是從頭編寫(xiě)的，而且此書(shū)的作者可謂每日均與Delphi“并肩作戰(zhàn)”，他以編寫(xiě)軟件庫(kù)為生，對(duì)于開(kāi)發(fā)商業(yè)運(yùn)行例程、類和工具的復(fù)雜性可算是輕車(chē)熟路。

我需要了解什么呢

這本書(shū)并不是要教你學(xué)習(xí)Delphi編程。你需要首先了解Delphi程序設(shè)計(jì)的基礎(chǔ)知識(shí)，例如創(chuàng)建新的工程、如何編寫(xiě)代碼、完成編譯和調(diào)試等等。在此提醒一句：這本書(shū)里不會(huì)談到控件。你必須對(duì)于類、過(guò)程和方法引用、無(wú)類型指針、強(qiáng)大的TList以及封裝為Delphi的TStream系列的流相當(dāng)熟悉。此外，還需要對(duì)諸如封裝、繼承、多態(tài)和委托等面向?qū)ο蟮母拍钣凶銐虻睦斫?。最后，?yīng)該不會(huì)對(duì)Delphi中的對(duì)象模型感到陌生或害怕!

前面已經(jīng)提到，這本書(shū)中所描述的許多概念都相當(dāng)簡(jiǎn)單。學(xué)習(xí)編程的新手會(huì)從本書(shū)中學(xué)到有關(guān)標(biāo)準(zhǔn)算法和數(shù)據(jù)結(jié)構(gòu)的一些基本內(nèi)容。實(shí)際上，分析源代碼可以幫助這些初級(jí)程序員掌握到高級(jí)程序員的許多技巧和方法。而更高級(jí)的結(jié)構(gòu)則留待你在特別需要的時(shí)候再來(lái)學(xué)習(xí)。

因此本書(shū)基本上要求你有一定的Delphi編寫(xiě)經(jīng)驗(yàn)。在編程時(shí)，你有時(shí)可能會(huì)發(fā)現(xiàn)TList及相關(guān)的一組類型不足以滿足需要，而希望有其他類型的數(shù)據(jù)結(jié)構(gòu)，但是又不太清楚哪些數(shù)據(jù)結(jié)構(gòu)可用，或者是即使找到了某種結(jié)構(gòu)又不知如何使用。有的情況下，你可能需要一個(gè)簡(jiǎn)單排序例程，但所找到的參考書(shū)采用的編碼語(yǔ)言卻為C++，而說(shuō)實(shí)話你寧可從頭編起也不想由此C++代碼進(jìn)行轉(zhuǎn)換。還有些情況，你可能還希望看到一本算法書(shū)，其中將把性能和效率與算法本身的描述提到同一個(gè)高度。那么，這本書(shū)正是你所需要的。

需要何種版本的Delphi呢

準(zhǔn)備好了嗎?請(qǐng)不要感到奇怪，這個(gè)問(wèn)題的答案是所有版本。除了在第2章討論動(dòng)態(tài)數(shù)組時(shí)需要使用Delphi4及以上版本和Kylix，另外第12章中部分內(nèi)容和偶而零星處對(duì)版本有要求以外，這里的代碼可以在任何版本的Delphi中進(jìn)行編譯和運(yùn)行。除了前面我提到的少量特定于版本的代碼之外，本書(shū)中的所有其他代碼都曾在各種版本的Delphi和Kylix中測(cè)試通過(guò)。

因此你可以認(rèn)為這本書(shū)里所印的所有代碼均適用于各種版本的Delphi。盡管有些代碼清單要基于特定版本，不過(guò)均已明確指出。

目錄

第1章 什么是算法

1．1 什么是算法

1．2 算法和平臺(tái)

1．3 調(diào)試與測(cè)試

1．4 小結(jié)

第2章 數(shù)組

2．1 數(shù)組

2．2 Delphi中的數(shù)組類型

2．3 TList類和指針數(shù)組

2．4 磁盤(pán)數(shù)組

2．5 小結(jié)

第3章 鏈表、棧和隊(duì)列

3．1 單鏈表

3．2 雙向鏈表

3．3 鏈表的優(yōu)缺點(diǎn)

3．4 棧

3．5 隊(duì)列

3．6 小結(jié)

第4章 查找

4．1 比較例程

4．2 順序查找

4．3 二分查找

4．4 小結(jié)

第5章 排序

5．1 排序算法

5．2 排序基礎(chǔ)知識(shí)

5．3 小結(jié)

第6章 隨機(jī)算法

6．1 隨機(jī)數(shù)生成

6．2 其他隨機(jī)數(shù)分布

6. 3 跳表

6．4 小結(jié)

第7章 散列和散列表

7．1 散列函數(shù)

7．2 利用線性探測(cè)方法實(shí)現(xiàn)沖突解決

7．3 其他開(kāi)放定址機(jī)制

7．4 利用鏈?zhǔn)椒椒ń鉀Q沖突

7．5 利用桶式方法解決沖突

7．6 磁盤(pán)上的散列表

7．7 小結(jié)

第8章二叉樹(shù)

8．1 創(chuàng)建一個(gè)二叉樹(shù)

8．2 叉樹(shù)的插入和刪除

8．3 二叉樹(shù)的遍歷

8．4 二叉樹(shù)的類實(shí)現(xiàn)

8．5 二叉查找樹(shù)

8．6 伸展樹(shù)

8．7 紅黑樹(shù)

8．8 小結(jié)

第9章 優(yōu)先隊(duì)列和堆排序

9．1 優(yōu)先隊(duì)列

9. 2 堆

9．3 堆排序

9．4 擴(kuò)展優(yōu)先隊(duì)列

9．5 小結(jié)

第10章 狀態(tài)機(jī)和正則表達(dá)式

10．1 狀態(tài)機(jī)

10．2 正則表達(dá)式

10．3 小結(jié)

第11章 數(shù)據(jù)壓縮

11．1 數(shù)據(jù)表示

11．2 數(shù)據(jù)壓縮

11．3 位流

11．4 最小冗余壓縮

11．5 字典壓縮

11．6 小結(jié)

第12章 高級(jí)主題

12．1 讀者-寫(xiě)者算法

12．2 生產(chǎn)者-消費(fèi)者算法

12．3 查找兩文件的差別

12．4 小結(jié)

后記

參考文獻(xiàn)

021_《Delphi算法與數(shù)據(jù)結(jié)構(gòu)》