021_《Delphi算法与数据结构》

• 原书名： 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算法与数据结构》