Delphi算法与数据结构(附光盘) (2008 年度畅销榜NO.511 )

本书从实用性的角度出发，以Delphi程序设计语言为载体，详细介绍了算法和数据结构。其中涵盖了诸如数组、链表和二叉树等内容，并着重介绍了查找算法、排序算法以及相关的优化技术。另外本书还对散列、散列表、优先队列、状态机和正则表达式以及诸如哈夫曼和LZ77等数据压缩技术进行了描述。本书适用于Delphi程序员以及数据库开发人员。 \r\n

前言\r\n致谢\r\n第1章 什么是算法\r\n第2章 数组\r\n第3章 链表、栈和队列\r\n第4章 查找\r\n第5章 排序\r\n第6章 随机算法\r\n第7章 散列和散列表\r\n第8章 二叉树\r\n第9章 优先队列和堆排序\r\n第10章 状态机和正则表达式\r\n第11章 数据压缩\r\n第12章 高级主题\r\n后记\r\n参考文献\r\n

你可能刚刚在书店里拿起这本书, 也可能已经买回家正在翻阅, 现在你所需要了解的大概不外乎以下几个问题…… 为什么,要写一本关于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. 尽管有些代码清单要基于特定版本, 不过均已明确指出. 我将看到哪些内容, 它们将如何安排 这本书分为12章, 并包括一个参考文献部分. 第1章中列出了一些基本的规则. 首先从性能的讨论开始, 我们将了解到算法效率的度量, 在此将先介绍大O符号的含义, 再对算法的实际运行时间进行分析, 最后将说明如何利用Profiler进行度量. 我们将讨论针对当前处理器和操作系统的(特别是内存缓存. 页面和虚存等等)相应的数据表示效率问题. 在此之后, 这一章还将谈到测试与调试, 这些内容在许多书中都被遗漏了, 但是实际上它们对于所有程序员而言都是相当重要的. 第2章所涵盖的内容为数组. 我们将学习对于数组的标准语言支持, 这也包括对动态数组的支持, 还会讨论到TList类：另外将创建一个封装了一个记录数组的类. 另一个需要强调的数组为串, 所以我们在此也将对它加以介绍. 第3章会介绍链表, 这包括单链表和双向链表. 通过利用单链表和数组来实现栈和队列, 我们还将学习到如何创建栈和队列. 第4章讨论了查找算法, 特别是顺序查找和二分查找算法. 我们还将看到如何利用二分查找在一个有序数组或链表中插入项. 第5章要介绍排序算法. 我们将学习诸多类型的排序方法, 包括：冒泡排序. 摇动排序. 选择排序. 希尔排序. 快速排序和归并排序等. 最后还将对数组和链表进行排序. 第6章将讨论有关随机数的算法. 我们将看到一个PRNG(pseudorandom number generator, 伪随机数生成器), 还将介绍一种称为跳转表的卓越的有序数据结构, 在此使用了一个PRNG从而实现结构的平衡. 第7章所考虑的是散列及散列表, 在此涉及到为什么使用散列表, 以及其优缺点等问题. 这里将介绍一些标准散列算法. 在散列表中存在着一个问题即冲突, 因此我们还将了解如何利用各种类型的试探法和链式方法加以解决. 第8章将介绍二叉树, 这是应用相当广泛的一种重要的数据结构. 我们将了解到如何建立和维护一棵二叉树, 以及如何遍历树中的节点. 在此还将引入不平衡树, 这是通过有序地插入数据而创建的. 后面还将提供两个平衡算法：伸展树和红黑树. 第9章所解决的是优先队列, 并由此介绍了堆结构. 我们将考虑一些重要的堆操作, 包括上冒和下滴, 还会了解到利用堆结构可以为我们提供一种方便的排序算法：堆排序. 第10章提供了有关状态机的信息, 并说明了如何利用状态机解决一类特定的问题. 在举出有限确定状态机的几个示例之后, 这一章接下来研究了正则表达式, 并介绍了如何对其进行解析并编译为有限非确定状态机, 最后还将把状态机应用于接受和拒绝串的情况. 第11章将提到一些数据压缩技术. 在此会介绍Shannon-Fano. 哈夫曼编码. 伸展树压缩和LZ77等算法. 第12章将涉及到一些高级技术, 如果你对搜索算法和结构感兴趣, 那么这将很合你的胃口. 当然, 它们对于满足程序设计需求而言也大有裨益. 最后本书还包括了一个参考文献部分, 在此列出了有关的参考文献, 由此可以帮助你找到本书所描述算法的更多信息, 在这些参考文献中不仅包括其他的算法书籍, 还包括一些学术论文和文章.