本书是《数据结构基础》的 C 语言版。用C 语言讲授数据结构，原因不止一

个。首先，或者说至关重要的原因是，C 语言适用于各种机型，就是说，无论个

人计算机（如 PC 机和 Mac 机），或者基于 Unix 的系统，C 语言均为主流

开发语言。其次，C 语言本身也在不断进化，时至今日， C 编译器功能愈发强

大、C 编程开发环境越来越广泛，我们理应为数据结构的初学者贡献一个 C 语

言版本的数据结构教材。还有，在计算机科学的教学体系中，C 语言的地位也相

当重要，举例来说，在程序设计课程里讲授的许多重要概念，诸如虚拟存储、文

件系统、自动语法生成、词法分析、网络编程等等，都是由 C 语言实现的。因

此，当前通行的教学理念是，尽早介绍 C 语言，这样可以为学生预备足够的时

间磨练 C 语言的编程技能，从而可以保证，学生在学习各种重要概念之前，就

做好了必要准备。

本书所有 C 语言程序都符合 ANSI C 标准。ANSI C 标准的制订始于 1983 年，

目的是增强早期的 C 语言功能，为此 ANSI 标准增加了一些新的语言特征，例

如，函数首部引入了类型信息，这样不但令程序更易读，还使程序更加可靠。

本书保留了第 1 版以及其它程序设计语言版本的特色，依然包括算法与计算时

间复杂度的详细讨论。而且，本书的章节组织与文体风格也尽量与第 1 版保持

一致。然而，我们并未墨守陈规，本书也有一些改进之处。举例来说，指针与动

态存储分配这两部分内容是 C 语言最常用的概念和技术，现在提前到了第一章；

另外，程序中的出错信息现在统一写到stderr 设备；还有，系统功能调用

结束之后，例如，在调用 malloc之后，现在都要检查返回状态，判断是

否成功返回。为了避免程序过于繁琐而不易理解，书中特别定义了若干宏语句，

以便程序简短而且易读，例如，宏语句MALLOC在调用malloc 的同时

还要判断返回结果是否正确。如果程序正常结束则调用exit(EXIT_SUCCESS)，如果程序非正常结束则调用exit(EXIT_FAILURE)。书中有关串的内容现在提前到介绍数组概念的一章。

另外还有一些改动，就不涉及 C 语言了。本书的习题现安排在各章节之后，习

题编号前的记号 ? 表明该习题有难度，适合用作编程大作业。另外，

每章内容或多或少都有调整，基本内容都调整到了前面，而那些较难理解的内容、

或者供选讲的内容，现在都移到了最后。

与第一版对比，本书最显著的新特点是引入了抽象数据类型概念。抽象数据类型

将数据类型的规范声明（specification）与实现分离。C++ 语言与 Java 语言

支持这种声明与实现的分离，但 C 语言却不提供现成的支持。我们设计了一套

简单自明的记号，用来描述抽象数据类型。基本思路是：先给出数据类型中数据

对象的定义，接着给出数据类型中各函数的名称及其调用参量。我们建议，教师

在讲解数据类型的实现细节以及相关算法的效率之前，最好应事先指导学生讨论

数据类型的规范声明。

在过去的十年，数据结构研究领域并未停滞，目前，数据结构越来越成熟。各种

实用的新型数据结构不断涌现，而且，崭新的复杂性度量方法也相继出现，这本

新书力图与这些研究进展保持同步。例如，在第2章和第3章，我们新增了利用动态数组及

其数组加倍技术实现多项式、矩阵、栈和队列的方法；第6章增

加了求最短路径的 Bellman-Ford 算法；ref{chap:chapter09}专门讨论优先级

队列，并新增了对偶堆、对称最小最大堆、区间堆等节目，取代了原先仅讨论最

小最大堆与双端堆的编排方式。

原书第一版的第10章用来讲查找结构，这本新书把原来的一章篇幅扩张成三章，第10章现在用来专讲二叉查找结构，现在的红-黑树不再由2-3 树和2-3-4 树导出。此外，这个新版还引入了自顶向下Splay 树，同时还讨论其性能优于自底向上Splay 树的原因。第11章用来讲多路查找树，B^+ 树一节是新增内容。第12章用来讲Trie 树，基本思想与第10章类似。由于 Trie 树的应用越来越广泛，因此相应篇幅大大增加了。第12章也新增了一节，内容包括后缀树以及Trie树在互联网包转发技术中的应用。

本书新版本详细讨论了分摊时间复杂度，而且大多数算法都给出了计算时间在最

优、最差情形的复杂度分析，有一些算法还包括平均情形的计算复杂度分析。分

摊时间复杂度考察给定操作序列连续执行的总效率，由 R.Tarjan 提出，与传

统的复杂度度量结果相比，分摊复杂度的度量结果在大多数情形都更加精确。

访问网址 http://www.cise.ufl.edu/~sahni/fdsc2ed 可获得本书其它信息。

课程安排

如果本书用作一学期（semister）教材，教学安排可分为中速进度和快速进度两

类。中速进度教学安排参见图1，适用于计算机专业低年级学生，最好设置为专业教学规划中的第二门课程或第三门课程。使用本书的大部分教师，包括本书作者，都选用这样的中速进度。以下大纲以 ACM 推荐的教学纲目为依据。

周次　 内容　 阅读材料 

    1     算法与数据结构引论     第1章

2     数组     第2章

3     数组（串）  第一次作业截止日期 

    4     栈与队列                第3章

    5     链表（单向链表和双向链表）               第4章

    6     链表       第二次作业截止日期 

    7     树（基本概念，二叉树）               第5章

8     树（查找，堆） 

9     期中考试 

    10    图（基本概念，存储表示）               第6章

    11    图（最短路径，生成树，拓扑排序）  第三次作业截止日期 

    12    内部排序（插入排序，快速排序和归并排序）               第7章

    13    内部排序（堆排序，基数排序）     第四次作业截止日期  

14    Hash 法               第8章

15    高级材料选讲               第9~12章

    16    高级材料选讲             第9~12章

图1    一学期课程安排（中速进度）}

围绕整个课程的教学环节，教师应布置一些编程作业，时间间隔最好均匀分布。

第一次编程作业的主要目的是熟悉编程环境。第二次编程应强调表结构的训练，

相关内容是第4章，作业可选用该章最后的习题。外部排序的内

容可不讲，把时间留给 Hash 法，Hash 法很重要，数据结构课程之后的许多课

程都要用到 Hash 法，因此最好在本课程讲授。讲完 Hash 法，还可以从第9~12章中挑选一些内容选讲，做为提高专题。

快速进度的教学安排是为研究生制订的，图2教学大纲，建议最好在研究生的第一学年开设。快速进度也可用作本科生提高课程。

编程作业与中速进度教学安排相同，不再赘述。由于课程进度较快，讲授第9~12章的时间只有四周，可按需要挑选内容选讲。

   周次　 内容　 阅读材料

    1     算法与数据结构引论             第1 章 

    2     数组            第 2 章 

    3     栈与队列       第 3 章 

             第一次作业截止日期 

    4     链表             第 4 章 

    5     树             第 5 章 

    6     树（续）         第二次作业截止日期 

    7     期中考试  

    8     图                第 6 章 

    9     图（续）     第三次作业截止日期 

    10    内部排序     第 7 章 

    11     外部排序     第 7 章 

    12     Hash 法         第 8章 

    13     优先级队列（选讲）     第 9 章 

             第四次作业截止日期 

    14     高效二叉查找树（选讲）     第 10 章 

    15     多路查找树（选讲）       第 11 章 

16     数字树查找结构（选讲）       第 12 章

图2一学期课程安排（快速进度）

数据结构的提高课程可采用图3 的教学安排，选课学生应学过数据结构的基本内容，最好有表、树、图各种数据结构的基础。

周次　 内容　 阅读材料

1     树的复习与串讲  第 5 章 

    2     图的复习与串讲  第 6 章 

    3     外部排序  第 7 章 

    4     外部排序（续）   

    5     Hash 法（复习基本 Hash 技术  第 8 章 

          Bloom 滤波器，动态 Hash 法）  第一次作业截止日期 

    6     优先级队列（左倾树，对称最小-最大堆，区间堆）  第 9 章 

    7     优先级队列（分摊复杂度，二项式堆）  第 9 章 

    8     优先级队列（Fibonacci 堆，对偶堆）  第二次作业截止日期 

    9     高效二叉查找树（最优 BST 树，AVL 树）  第 10 章 

    10    期中考试  

    11    高效二叉查找树（红-黑树，Splay 树）  

    12    多路查找树（$B$-树，$B^+$ 树）  第 11 章 

    13    数字查找结构（数字查找树，二路 Trie 树，Patricia 树）  第二次作业截止日期 

    14    多路 Trie 树 

    15    后缀树  第四次作业截止日期 

16    Trie 树与互联网包中继 

图3学期课程安排（数据结构提高课程）

有些学校一学年分四个小学期（quarter system），对于这种学期设置，完整的

数据结构课程需要占用两个小学期，教学安排可参考图4 和图5。选课学生应学过高级程序设计课程，并在这门先修课中学过算法分析与数据结构的基本内容。

周次　 内容　 阅读材料

1     算法与数组复习  第 1、2 章 

    2     栈与队列  第 3 章 

    3     链表（栈、队列、多项式）  第 4 章 

    4     链表   

    5     树（遍历、集合的表示）  第 5 章 

            第一次作业截止日期 

    6     树（堆，查找）  

          期中考试  

    7     图（遍历，连通分量）  第 6 章 

    8     图（最小生成树）  第 6 章 

    9     图（最短路径）  第 6 章 

10    图（活动网络）   第二次作业截止日期 

图4   第一个小学期

    周次　 内容　 阅读材料 

    1     内部排序（插入排序，快速排序  第 7 章 

          排序的界，$O(1)$ 空间归并，归并排序）   

    2     排序（堆排序，基数排序，链表排序，表排序）   

    3     外部排序  第 7 章 

    4     Hash 法  第 8 章 

          期中考试  

    6     优先级队列（左倾树，对称最小-最大堆，区间堆）  第 9 章 

    7     优先级队列（分摊复杂度，二项式堆，Fibonacci 堆）  第 9 章 

    8     高效二叉查找树（AVL 树或红-黑树，Splay 树）  

    9     多路查找树（B-树，B^+ 树）                  第 11 章 

                                                  第二次作业截止日期 

    10    数字查找结构（Trie 树，后缀树）               第 12 章 

图5  第二个小学期

  l

借此新书出版机会，我们再一次感谢为本书第 1 版提供过帮助和支持的各位同

事。感谢 Illinois Wesleyan University 的 Lisa Brown 教授，感谢 Lisa

Brown 教授 Programming III 课程的选课学生，感谢 Colorado School of

Mines 的 Dinesh Mehta 博士为本书第一版纠错，感谢 Illinois Wesleyan

University 的 Computer Services 机构及其员工 Trey Short 和 Curtis

Kelch，感谢他们提供的技术帮助。还要感谢 AT&T 贝尔实验室 的 Narain

Gehani，Arcadia University 的 Tomasz M"uldner，以及 Trinity

University 的 Ronald Prather，感谢他们审阅本书初稿。特别要感谢

Friedman 夫妇，Art 与 Barbara，他们从开始就是本书的出版业务负责人，此

书从初期雏形到最后出版，是经他们之手促成的。

 Ellis Horowitz

Sartaj Sahni

Susan Anderson-Freed