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

內容簡介

Delphi開發人員Julian Bucknall從實用角度為廣大程序員提供了有關使用算法和數據結構的一個詳盡的介紹。Bucknall先從算法性能的討論開始，涵蓋了諸如數組、鏈表和二叉樹等內容。這本書強調了查找算法（如順序和二分查找），另外也重點介紹了排序算法（包括冒泡排序、插入排序、希爾排序、快速排序和堆排序），此外還提供了有關的優化技術。不僅如此，作者還介紹了散列和散列表、優先隊列、狀態機和正則表達式以及諸如哈夫曼和LZ77等數據壓縮技術。

隨附光盤中有作者所開發的一個相當成功的自由軟件庫EZDSL，另外還有可運行于各版本Delphi上和Kylix上的源代碼，此外還提供了TurboPower Software公司的可執行程序。

前言

你可能剛剛在書店里拿起這本書，也可能已經買回家正在翻閱，現在你所需要了解的大概不外乎以下幾個問題……

為什么,要寫一本關于Delphi算法的書呢

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

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

對于Delphi，我很自得地認為它在目前應用開發所用的諸多語言和環境中可謂獨樹一幟。首先，類似于Visual Basic，Delphi也是一種可以快速開發16位或32位Windows應用的環境，而使用Kylix則可以實現Linux應用的快速開發。僅需輕點鼠標，組件即可落于窗體之上。有些組件隨后需要雙擊，再鍵入些許代碼，這樣組件之間就可以建立錯綜復雜而又緊密的關系。如果再加上事件處理程序，就有可能得到一個看上去很不錯的半成品了。

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

Delphi程序員將其本身劃歸為兩大陣營：應用程序員和系統程序員。不過有時你也會發現有的程序員二者兼備。這兩個陣營之間的聯系就在于無論哪一類程序員都必須同算法世界打交道，同時對于算法也必須做到有一定了解。如果你有一定的編程經驗，可能會遇到需要編寫二分查找(折半查找)代碼的情況。當然，在此之前，你可能需要實現某種排序使數據按照一定的順序排列，從而正常地完成二分查找。最后，你還可能開始使用某種性能評測工具(Profiler)，也許會發現TStringList中存在的瓶頸，并希望了解哪一種數據結構能夠更有效地完成這一任務。

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

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

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

下面來看為什么要用Delphi?其原因有二：Object Pascal語言和操作系統。Delphi的語言中有許多構造在其他語言中均沒有，利用構造將使高效的算法和數據結構可以更容易也更自然地得以封裝。例如屬性即屬此類，再如若出現不可預知的錯誤時，相應的異常也屬構造。盡管在Delphi中不用這些Delphi專用的語言構造也完全可以編寫出標準算法，但我認為，如此一來我們將無法感受到這種語言的效率和魅力所在。在本書中，我們將特意大量使用Delphi中的ObjectPascal語言，在此我沒有考慮拿到此書的Java程序員在轉換代碼時可能存在的困難。既然封面上標明Delphi，那么我們就一心一意地使用Delphi吧。

其次要考慮的是，傳統意義上對算法的認識均體現在通用性上，至少從CPU和操作系統的角度來看需要如此。這些算法當然可以針對W~mdows環境得到優化，也可以面向Linux進行改進。對于我們所用的各種類型的Pentium處理器、各種不同的內存緩存器、OS中不同的虛存子系統等等，算法還可以做到更為高效。這本書將特別關注于在效率上所獲得的收益。不過，我們不至于什么代碼都拿匯編語言來編寫，盡管它對于當前處理器的管道式體系結構來說應該是最優化的，但有些地方我還是必須明確其使用要有一定限制!

因此，無論怎樣，廣大Delphi群體確實需要一本算法方面的書，而且迫切需要它完全針對于特定的語言、操作系統和處理器，而本書正是應此需而生。它不是由面向其他語言的其他書翻譯得來的。不僅這本書本身是從頭編寫的，而且此書的作者可謂每日均與Delphi“并肩作戰”，他以編寫軟件庫為生，對于開發商業運行例程、類和工具的復雜性可算是輕車熟路。

我需要了解什么呢

這本書并不是要教你學習Delphi編程。你需要首先了解Delphi程序設計的基礎知識，例如創建新的工程、如何編寫代碼、完成編譯和調試等等。在此提醒一句：這本書里不會談到控件。你必須對于類、過程和方法引用、無類型指針、強大的TList以及封裝為Delphi的TStream系列的流相當熟悉。此外，還需要對諸如封裝、繼承、多態和委托等面向對象的概念有足夠的理解。最后，應該不會對Delphi中的對象模型感到陌生或害怕!

前面已經提到，這本書中所描述的許多概念都相當簡單。學習編程的新手會從本書中學到有關標準算法和數據結構的一些基本內容。實際上，分析源代碼可以幫助這些初級程序員掌握到高級程序員的許多技巧和方法。而更高級的結構則留待你在特別需要的時候再來學習。

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

需要何種版本的Delphi呢

準備好了嗎?請不要感到奇怪，這個問題的答案是所有版本。除了在第2章討論動態數組時需要使用Delphi4及以上版本和Kylix，另外第12章中部分內容和偶而零星處對版本有要求以外，這里的代碼可以在任何版本的Delphi中進行編譯和運行。除了前面我提到的少量特定于版本的代碼之外，本書中的所有其他代碼都曾在各種版本的Delphi和Kylix中測試通過。

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

目錄

第1章 什么是算法

1．1 什么是算法

1．2 算法和平臺

1．3 調試與測試

1．4 小結

第2章 數組

2．1 數組

2．2 Delphi中的數組類型

2．3 TList類和指針數組

2．4 磁盤數組

2．5 小結

第3章 鏈表、棧和隊列

3．1 單鏈表

3．2 雙向鏈表

3．3 鏈表的優缺點

3．4 棧

3．5 隊列

3．6 小結

第4章 查找

4．1 比較例程

4．2 順序查找

4．3 二分查找

4．4 小結

第5章 排序

5．1 排序算法

5．2 排序基礎知識

5．3 小結

第6章 隨機算法

6．1 隨機數生成

6．2 其他隨機數分布

6. 3 跳表

6．4 小結

第7章 散列和散列表

7．1 散列函數

7．2 利用線性探測方法實現沖突解決

7．3 其他開放定址機制

7．4 利用鏈式方法解決沖突

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

7．6 磁盤上的散列表

7．7 小結

第8章二叉樹

8．1 創建一個二叉樹

8．2 叉樹的插入和刪除

8．3 二叉樹的遍歷

8．4 二叉樹的類實現

8．5 二叉查找樹

8．6 伸展樹

8．7 紅黑樹

8．8 小結

第9章 優先隊列和堆排序

9．1 優先隊列

9. 2 堆

9．3 堆排序

9．4 擴展優先隊列

9．5 小結

第10章 狀態機和正則表達式

10．1 狀態機

10．2 正則表達式

10．3 小結

第11章 數據壓縮

11．1 數據表示

11．2 數據壓縮

11．3 位流

11．4 最小冗余壓縮

11．5 字典壓縮

11．6 小結

第12章 高級主題

12．1 讀者-寫者算法

12．2 生產者-消費者算法

12．3 查找兩文件的差別

12．4 小結

后記

參考文獻

021_《Delphi算法與數據結構》