世界著名计算机教材精选 数据结构基础 (C语言版)（第2版） Ellis Horowitz Sartaj Sahni 著 Susan Anderson-Freed 朱仲涛译 FUNDAMENTALS OF DATA STRUCTURES IN C Second Edition 清华大学出版社
世界著名计算机教材精选 Fundamentals of Data Structures in C Second Edition 数据结构基础 (C语言版) (第2版) Ellis Horowitz Sartaj Sahni 著 Susan Anderson-Freed 朱仲涛 译 清华大学出版社 北京
世界著名计算机教材精选 Fundamentals of Data Structures in C Second Edition 数据结构基础 (C语 言版) (第 2版 ) E11is HorOwitz Sart刂 Sahni Susan AndersOn-Freed 朱仲涛 清 华大学 出版社 北 京 著 译
中译本序 《数据结构基础》是一本优秀的数据结构教材，取材企面，难易适中，内容组织合理，详 略得当，深入浅出，而且论证逻辑性强，所以广为国内外高校计算机专业选用。此外，这本 英文教材对国内许多数据结构教材的编写也有显芳影响。 此中译本是《数据结构基础》C语言版第2版的译本，第1版相比，新版篇幅扩张很 大，内突全面更新，全书覆盖①线性（序）数据类型、②树型数据类型、⑧网状数据类型， 以及④排序算法马⑤查找算法。基本数据结构包括线性表（数组马与链表）、栈与队列、树、 图等经典内容，特点为运用抽象数据类型(ADT)观点 现。另外，书中包含人量符合 ANSI C标准的程序，实例卡常，习题众多，并有人苹图表。 本书最鲜明的特点是：用儿乎一半篇幅，即第8~12章，详细讨论了各种查找表结构及其 查找算法，而且内容组织很新颖。这最后5章既包括今找法的经典内容，如Hash法和AVL 树等：也包括数据结构研究的新进展，如分摊复杂度分析等：还包括当前数据结构研究的热 点，即各种堆结构。这部分内容特别适合数据结构提高课程，也特别适合学过基本数据结构 的读者白学提高。以下列出本书有关杏找的内容及其编排体系。 香找 Hash法 一静态Hash法 动态Hash法 -优先级队列 单、双端优先级队列 二项式堆 -Fibonacci堆 配偶堆 对称域小一最人堆 X间证 高效二义查找树 最术“叉杏找树 AVL树 红红一树 play树 多路查找树 m-路查找树 一B-树、B+-树 数字查找树（键树） Trie树与Patricia树 后缀树 本书章节之后的习题与补充习题也各有特色。习题中的一些是正文内容的补充'扩充
中译本序 《数据结构基础》是 一本优秀的数据结构教材,取 材仝面,难 易适中,内 容组织合理,详 略得当,深 入浅出,而 且论证逻辑性强,所 以广为国内外高校计算机专qL选 用。此外,这 本 英文教材对国内许多数据结构教材的编写也有显荠影响。 此中译本是 《数据结构基础》C语 言版第 2版 的译本,ⅠJ第 1版 相比,新 版篇幅扩张很 大,内 容全面更新,全 书覆盖 ⊙线性 (序 )数 据类型、②树型数据类型、③ 网状数据类型, 以及 ④排序算法与 ⑤合找算法。基本数据结构包括线性表 (数组与链表)、栈Jj队 列、树、 图等经典内容,特 点为运用抽象数据类型 (ADT)观 点 —— \t现 。另外,书 中包含人量符合 ANSI C标 准的程序,实 例丰宫,习 题众多,并 有人蚩图表。 本书最鲜明的特点是:用 儿乎一半篇幅,即 第 8~12章 ,详 细讨论了各种莶找表结构及其 查找算法,而 且内容组织很新颖。这最后 5章 既包括合找法的经典内容,如 Hash法 和 灬几 树等;也 包括数据结构研究的新进展,如 分摊复杂度分析等;还 包括当前数据结构研究的热 点,即 各种堆结构。这部分内容特别适合数据结构提高课稆,也 特别适合学过基本数据结构 的读者 白学提高。以 卜列出本书有关杏找的内容及其编排体系。 伶 找 静态 Hash法 动态 Hash法 —优先级队列 单、双端优先级队列 工项式堆 Fibonacc1士 住 配偶堆 对称最小—最人堆 区间堆 高效工叉佥找树 多路杏找树 嗦L L鳍 γ% 数字查找树 (键树) Trie树 lJ PatriCia树 后缀树 本书章节之后的习题与补充习题也各有特色。习题中的 一些足正文内容的补充 丨J扩 充, 1
可以培养读者独立思考，举一反三的能力。附加习题中的一些编程人作业，如随机走动、骑 十征程、扑克接龙、迷宫求解等，均令人兴趣盎然，读者如果编程求解，既有助丁完全彻底 地了解基本概念、扎实地掌握教材内容，又能迅速提高编程水平。还有，每章最的参考文 狱1洗读材料也很全面，可作数据结构研究人员【算去研究人员的入门卖物，为开楼柑关切 究奠定基础。 中译本全书由译者排版，排版T具是X(CJK)与AMS-TEX。译本中用到的西文正文 字体为palatino,数学字体为mathpazo:书体排版采用cctbook.cls样式类，该样式类的 作者是张林波：程序代码排版采用1 istings.sty样式。中译本全f插图均为火量图，全部 由译者制作，具是pic的xy.sty,作者是Kristoffer H.Rose与Ross Moore,驱动程序是 dvips。.中译本全书索引凭借makeindex I.具制作，人名索引与部分知识点索引由sed/awk 程序协助完成。排版T作环境是FreeBSD7.O,编辑器是GNU emacs+auctex。. 借此中译本出版机会，首先感谢清华人学数据结构课程主讲教师殷人：与邓俊辉，与他 们合作，无论日常教学工作、教学法研讨，还是编写教材，译者均获流太多，还要特别感谢 严蔚敏老师对译者教学工作起步阶段的指点。最后，感谢所有选修、旁听译者数据结构课程 的同学和进修教师，感谢各位深程助教，表心感谢他的支持和鼓励，他对此中译本的 待是译者孜孜不倦的全都动力。 译事艰辛、作繁重，没有出版补编辑的鼎力支持，这本中译本是不可能完成的。感谢 清华人学出版社龙启铭先生，身为此中译本责任编辑，他从译水策划、监督进度，到审阅全 书、精心校对，甚至版式设计，事无巨细，都付出了人精力。衷心感谢龙启铭先生给予译 者的所有帮助。 固于译者的专业素养'与翻译水平，此中译本一定有不少错随之处，恳请读者批评指止 译者 2008年12刀
11 可以培养读者独立思考,举 一反二的能力。附加丬题中的一些编程人作业,如 随机走动 、骑 十征程 、扑克接龙、迷宫求解等,均 令人兴趣 杰然,渎 者如呆编稆求解,既 有助 J·完全彻底 地了解基本概念、扎实地掌握教材内容,义 能迅速捉高编稆水平。还有,每 章最后的参考文 献与选读材料也很全面,可 作数据结构研究人员!j算法研究人员的入门读物,为 开展相关研 究奠定基础。 中泽本全书由泽者排版,排 版I具 是 LATEX(CJK)!j AMS司 Ⅸ。泽本中用到的内文正文 字体为 Palatino,数 学字体为 mathpazo;|氵 体排版采用 cctbook。 c1s样 式类,该 样式类的 作者是张林波;程 序代码排版采用 1土st土ngs.sty样 式。中泽本全书插图均为矢鞋图,仝 部 由译者制作,⒈ 具是X-pk的 xy.sty,作 者是 Kristoffer H,Rose与 Ross Moore,驱 动稆序是 dvips。 中泽本全书索引凭借 make土 ndex卜 具制作,人 名索引与部分知识点索引由sed/awk 程序协助完成。排版 ⒈作环境是 FreeBSD7.0,编 辑器是 GNU emacs+aL】 ctex。 借此中译本出版机会,首 先感谢清华人学数据结构课稆主讲教师殷人L己!J邓俊辉,!j他 们合作,无 论 日常教学I作 、教学法研讨,还 是编写教材,泽 者均获益太多。还耍特别感谢 严蔚敏老师对泽者教学 「作起步阶段的指点。最后,感 谢所有选修、旁听泽者数据结构课秽 的同学和进修教师,感 谢各位课稆助教,衷 心感谢他们的支持和鼓励,他 们对此中译本的J叨 待是译者孜孜不倦的全部动力。 泽事艰辛、 「作繁重,没 有出版社编辑的鼎力支持,这 本屮泽本是不可能完成的。感谢 清华入学出版社龙启铭先生,身 为此中泽本责任编辑,他 从泽节策划、监督进度,到 审阅仝 书、精心校对,甚 至版式设计,书 无巨细,都 付出了人甘精力。衷心J凼谢龙启铭先生给 予译 者的所有帮助。 囿T泽 者的专业素养 JJ翻 译水平,此 中泽本 一定仃不少错陋之处,恳 请读者批评指正。 译者 2008铒 :12月
前言 本书是《数据结构基础》的C语言版。州C语言讲授数据结构，原闪不止一个。首先 或者说至关重要的原因是，C语言适用于各种机型，就是说，无论个人计算机（如P℃机和 Mac机)，或者基于Uix的系统，C语言均为士流开发语言。其次，C语言本身也在不断进 化，时至今日，C编译器功能愈发强人、C编程开发环境越米越`泛，我们理应为数据结构 的初学者贡献一个C语言版本的数据结构教材。还有，在计算机科学的教学体系中，C语言 的地位也相当重要，举例米说，在程序设计误程里讲授的许多重要概念，诸如虚拟存储、文 件系统、自动语法生成、词法分析、网络编程等等，都是由C语言实现的。因此，当前通行 的教学理念是，尽早介绍C语言，这样可以为学生预备足够的时间磨练C语言的编程技能， 从而可以保证，学生在学习各种重要概念之前，就做好了必要准各 本书所有C语言程序都符合ANSIC标准。ANSI C标准的制订始于1983年，日的是增 强早期的C语言功能，为此ANSI标准增加了一些新的语言特征，例如，函数肖部引入了类 刑信息，这样不但令程序更易读，还使程序史加可综。 本书保留了第1版以及其它程序设计语言版本的特色，依然包括算法'与计算时间复杂 度的详细讨论。而且，本书的章节组织与文体风格也尽苹与第1版保持一致。然而，我们 并未墨守陈规，本书也有一些改进之处。举例米说，指针马动态存储分配这两部分内容是 C语言最常用的概念和技术，现在提前到了第一章：分外，程序中的出错信息现在统一写到 stderr设备：还有，系统功能调用结米之后i,例如，在调州ma1loc之后，现在都要检在返 问状态，判断是否成功返同。为了避免过」繁琐而不易理解，中特别定义了若干宏语 句，以便程序简短而且易读，例如，宏语句MLoc在调州ma11oc的同时还要判断返同结 果是否正确。如果程序正常结宋则调用exit(EXIT SUCCESS),如果程序非正常结来则调用 exit(EXIT_FAILURE)。中有关申的内容现在提前到介绍数组概念的一章 另外还有一些收动，就不涉及C语言了。本的习题现安排在各章节之后，习题编号前 的记号·表明该习题有难度，适合用作编程人作业。另外，每章内容域多或少都有调整，基 本内容都调整到了前面，而那些较难理解的内容、或者供选讲的内容，现在都移到了最后。 马与第一版对比，本书最显芳的新特点是引入了抽象数据类型概念。抽象数据类型将数掘 类型的规范声明(specification)与实现分离。C+语与Java语言支持这种声明'与实现的 分离，但C语言却不提供现成的支持。我们设计了一套简单山明的记号，用米描述抽象数据 类型。基本思路是：先给出数据类型中数据对象的定义，接着给出数据类型中各函数的名称 及其调用参革。我们建议，教师在讲解数据类型的实现细节以及相关算法的效率之前，最好 应事先指导学生讨论数据类型的规范声明。 在过去的十年，数据结构研究领域并未停滞，口前，数据结构越米越成熟。各种实州的 新型数据结构不断浦现，而且，崭新的复杂性度量方法也相继出现，这本新书力图这些研 究进展保持同步。例如，在第2章和第3章，我新增了利用动态数组及其数组加倍技术 实现多项式、矩阵、栈和队列的方法：第6章增加了求最短路径的Bellman-Ford算法：第g 章专门讨论优先级队列，并新增了对偶堆、对称最小最人堆、区间堆等节日，取代了原先仅 寸论最小最大堆'双端堆的编排方式。 原书第一版的第10章州米讲有找结构，这本新书把原米的一章篇幅扩张成三章，第10
亠一 一口 亠刖 本 u是 《数据结构基础 》的 C语 言版。川 C语 言讲授数据结构,原 Fkl不lL一 个。莳先, 或者说至关重要的原冈是,C语 言适用 于各种机型,就 是说,无 论个人计算机 (如 PC机 和 Mac机 ),或 者基 于Unix的 系统,C语 亩均为主流开发语言。其次,C语 言本身也在不断进 化,时 至今 日,C编 泽器功能愈发强大、C编 程开发环境越来越广泛,我 们理应为数据结构 的初学者贡献一个 C语 言版本的数据结构教材。还有,在 计算机科学的教学体系中,C语 言 的地位也相当重要,举 例来说,在 程序设计课稆里讲授的许多重要概念,诸 如虚拟存储、文 件系统、白动语法生成、词法分析、网络编程等等,都 是由 C语 言实现的。囚此,当 前通行 的教学理念是,尽 早介纟`{C语 占,这 样可以为学土预备足够的时问磨练 C语 言的编程技能, 从而可以保证,学 生在学习各种重耍概念之前,就 做好了必耍准备。 本书所有 C语 言程序都符合 ANsI C标 准。ANsI C标 准的制订始 于19sS年 ,日 的楚增 强早期的 C语 言功能,为 此 ANsI标 准增加了一些新的语言特征,例 如,函 数首部引入了类 型信息,这 样不但令程序更易读,还 使稆序吏加可靠。 本书保留了第 1版 以及其它程序设计语 窝版本的特色,依 然包括算法 IJ计 算时间复杂 度的详细讨论。而且 ,本 书的章 iy细织与文体风格也丿s蚩 与第 1版 保持 一致。然而,我 们 并木墨守陈规,本 书也有 一些改进之处。举例来说,指 针与动态存储分配这两部分内容是 C语 高最常用的概念和技术,现 在捉前到了第一 章;另 外,稆 序中的出错信息现在统一写到 stderr设 备;还 有,系 统功能调用结束之后,例 如,在 调用 ma11。 c之 后,现 在都耍检杏返 冂状态,判 断是否成功返冂。为了避免稆序过 J1繁琐而不易理解,|氵中特别定义了若干宏语 句,以 便稆序简短而且易读,例 如,宏 语句 阻 LLoC在 调用 ma11。 c的 同时还要判断返冂结 呆是否正确。如呆不V序 正常结束则调用 exit(EXIT SUCCESS),如 呆稆序非正常结束则调用 exit(EXIT FAILURE)。 }氵中有关串的内容现在提前到介纟亻{数组概念的一章。 另外还有 一些改动,就 不涉及 C语 古了。本 |氵的习题现安排 /t各 章节之后,习 题编号前 的记号 ↑表明该习题有难度,适 合用作编稆入作业。另外,每 节内容或多或少都有调整,基 本内容都调整到了前面,而 那些较难理解的内容、或者供选讲的内容,现 在都移到了最后。 与第一版对 比,本 书最显荠的新特点足引入了抽象数据类烈概念。抽象数据类珥q将数据 类型的规范声明 (speci丘cation)!J实 现分离。C++· 讠∫i占丿j Java语 亩支持这种声明 %实 现的 分离,但 C语 言却不捉供现成的支持。我们 设计了一套简单臼明的记圩,用 来描述抽象数据 类型。基本思路足:先 给出数据类丐u屮数据对象的定义,接 若给出数据类型中各函数的名称 及其调用参董。我们建议,教 师在讲解数据类Ⅱ刂的实现细 |∵以及相关算法的效率之前,鼓 好 应芋先指导学生讨论数据类矸u的规范声明。 在过 去的十年,数 据结构研究领域并未停滞,目 前,数 据纬构越来越成熟。各种实川的 新型数据结构不断涌现,而 且 ,崭 新的复杂性度鞋方法也相继tJ{现,这 本新书力图与这些研 究进展保持同步。例如,在 第 2章 和第 3章 ,我 们新增了利用动态数组及其数细加倍技术 实现多项式、矩阵、栈和队列的方法;第 6聿 增加了求最短路径的 Bellman-Ford算 法 :第 9 章专门讨论优先级队列,并 新增了对偶堆、对称最小最人堆、Ⅸ间堆等节日,取 代了原先仅 讨论最小最大堆 !J双 端堆的编排方式。 原书第 一版的第 10章 用来讲杏找结构,这 本新书把原来的一章篇幅扩张成二章,第 10