清华大学出版社：《数据结构基础》课程教材书籍PDF电子书（C语言版，第2版，Ellis Horowitz Sartaj Sahni 著，Susan Anderson-Freed 朱仲涛 译）

世界著名计算机教材精选 数据结构基础 (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

章现在用米专讲二又在找结构，现在的红-黑树不再由23树和23-4树导。此外，这个新 版还引入了自顶向下Splay树，同时还讨论其性能优于白底向上Splay树的原。第11章用 米讲多路查找树，B+树一节是新增内容。第12章用米讲Trie树，基本思想与第10章类似 由于Te树的应用越米越泛，因此相应篇幅人人增加了，第12章也新增了一节，内容包 括后缀树以及T树在互联网包转发技术中的v用。 本书新版本详细讨论了分摊时间复杂度，而且大多数算法都给出了计算时间在最优、最 差情形的复华度分析，有一些算法还句括平均情形的算复度分析。分雄时间度老 给定揉作序列连续执行的总效率，由R.Tarjan提出，马与传统的复杂度度量结果相比，分摊复 杂度的度量结果在大多数情形都更加精确。 访问网址http:/ww.cise.uf1,edu/~sahni/Edsc2ed可获得本书其它信息。 课程安排 如果本书用作一学期(semister)教材，教学安排可分为中速进度和快速进度两类。中速 进度教学安排参见图1，适用丁计算机专业低年级学生，最好设置为专业教学规划中的第 门课程域第三门课程。使用本书的大部分教师，包括本书作者，都选用这样的中速进度。以 下大纲以ACM推荐的教学纲目为依据。 周次 阅读材料 1 算法与数据结构引论 第1章 数组 第2章 3 数组（串） 第一次作业截止日期 栈与队列 第3章 链表（单向裤表和双向链表） 第4章 6 链表 第次作业截止日期 树（基本概念，叉树） 第5章 树（查找，堆） 9 期中考试 图（基本概念，存储表示） 第6章 11 图（最短路径，生成树，拓扑排序） 第二次作业截止日期 内部排序（插入排序，快速排序和归并序） 第7章 内都非序（维子，基数排非子） 第四次作业业止日期 Hash法 第8章 15 高级材料选讲 第9~12章 16 高级材料选讲 第9~12章 图1一学期课程安排（中速进度） 用绕整个课程的教学环节，教师应布置一些编程作业，时间间隔最好均分布。第 次编程作业的主要日的是熟悉编程环境。第次编程应强调表结构的训练，相关内容是第4 章，作业可选用该章最后的习题。外部排序的内容可不讲，把时间留给Hash法，Hash法很

1V 章现在用来专讲二叉A找 结构,现 在的红-黑树不再 由 ⒉3树 和 ⒉3△ 树导||丨。此外,这 个新 版还引入了臼顶向 卜Splay树 ,同 时还讨论其性能优 l∴臼底向上 Splay树 的原冈。第 11章 川 来讲多路查找树,B+树 一 9足 新增内容。第 12章 用来讲 Trie树 ,基 本思想与第 10章 类似。 由△Trie树 的应用越来越广泛,囚 此相应篇幅人人增加了。第 12章 也新增了 一节,内 容包 括后缀树以及 Trie树 在互联网包转发技术中的应用。 本书新版本详细讨论了分摊时间复杂度,而 且人多数算法都给出了计算时间在最优 、最 差情形的复杂度分析,有 一些算法还包括平均情形的计算复杂度分析。分摊时问复杂度考察 给定操作序列连续执行的总效率,由 R.%犭 an捉 出,与 传统的复杂度度蚩结呆相比,分 摊复 杂度的度量结呆在大多数情形都更加精确。 访 问 网 址 http:〃 ww。 c土 se。 uf1。 edu/~sahn土 /fdsc2ed可 获 得 本 书 其 它 信 息 。 课程安排 如呆本书用作 一学期 (semister)教 材,教 学安排可分为中速进度和快速进度两类。中速 进度教学安排参见图 1,适 用 丁计算机专业低年级学生,最 好设置为专业教学规划中的第工 门课程或第二门课程。使用本书的大部分教师,包 括本书作者,都 选用这样的中速进度。以 卜人纲以 ACM推 荐的教学纲 日为依据。 周次 内 容 阅读材料 1 2 3 在 5 6 7 8 9 10 11 12 13 14 15 16 算法与数据结构引论 数组 数组 (串 ) 栈与队列 链表 (单 向链表和双 向链表) 链表 树 (基本概念,工 叉树) 树 (查找,堆 ) 期中考试 图 (基本概念,存 储表示) 图 (最短路径,生 成树,拓 扑排序) 内部排序 (插入排序,快 速排序和归并排序) 内部排序 (堆排序,基 数排序) Hash法 高级材料选讲 高级材料选讲 第 1章 第 2章 第一次作业截止日期 第 3章 第 4章 第工次作业截止 日期 第 5章 第 6章 第二次作业截止 日期 第 7章 第四次作业截 止日期 第 8章 第 9~12章 第 9~12章 图 1一 学期课程安排 (中速进度 ) 围绕整个课程的教学环节,教 师应布置一些编程作业 ,时 间间隔最好均匀分布。第一 次编程作业的主要 日的是熟悉编程环境。第工次编程应强调表结构的训练,相 关内容是第 4 章,作 业可选用该章最后的习题。外部排序的内容可不讲,把 时间留给 Hash法 ,Hash法 很

重要，数据结构课程之后的许多课程都要用到Hash法，因此最好在本课程讲授。讲完Hash 法，还可以从第912章中挑选一些内容选讲，做为提高专题。 快速进度的教学安排是为研究生制订的，图2是教学人纲，建议最好在研究生的第一学 年开设。快速进度也可用作本科生提高误程。编程作业与中速进度教学安排相同，不再赘述 由J课程进度较快，讲授第912章的时间只有四周，可按需要挑选内容选讲。 周次内容 阅读材料 1 算法与数据结构引论 第1草 数组 第2章 3 栈与队列 第3章 第一次作业截止日期 4 链表 第4章 5 树 第5章 6 树（续） 第次作业截止日期 期中考试 8 第6章 0 图（续） 第：次作业截止日期 10 内部排的 第7 11 外部并序 第7宵 12 Hash法 第8草 13 优级队列（洗业） 第9当 第四次作业截止日期 14 高效二义查找树（选讲）》 第10肾 15 多路在找树（选讲） 第11景 16 数字树查找结构（选讲 第12音 图2一学期课程安排（快速进度） 数据结构的提高课程可采用图3的教学安排，选课学生应学过数据结构的基本内容，最 好有表、树、图各种数据结构的基础。 有些学校一学年分四个小学期(quarter system),对门这种学期设置，完整的数据结构 课程需要占用两个小学期，教学安排可参考图4和图5。选课学生应学过扁级程序设计课程， 并在这门先修课中学过算法分析与数据结构的基本内容。 借此新书出版机会，我们再一次感谢为本第1版提供过帮助和支持的各位同事。感 i谢Illinois Wesleyan University的Lisa Brown教授，感谢Lisa Brown教授ProgrammingⅢ 课#的选课学生，感谢Colorado School of Mines的Dinesh Mehta博十为本书第一版纠错， 感谢llinois Wesleyan University的Computer Services机构及其员I,Trey Short和Curtis Kelch,感谢他们提供的技术帮助。还要感谢AT&T贝尔实验室的Narain Gehani,Arcadia University的Tomasz Muldner,以及Trinity University的Ronald Prather,.si谢他们市阅本 书初稿。特别要感谢Friedman夫妇，Art与Barbara,他从开始就是本的l版业务负责

V ⒋要,数 据结构课稆之后的许多课稆都耍用到 HⅡ h法 ,lkl此 最好在本课不V讲 授。讲完 Hash 法,还 叮以从第 9~12章 中挑选一些 内容选讲,做 为提高专题。 快速进庋的教I安 排是为研究生制订的,图 2足 教I大 纲,建 议最好在研究生的第一学 午开设。快速进度也可丹l作本科生提高课稆。编稆作业 lj中速进度教学安排相同,不 再赘述。 由 J∵课程进度较快,讲 授第 9~12章 的时间只有四周,可 按需要挑选 内容选讲。 周 次 内容 阅读材料 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 算法与数据结构引论 数细 栈 与队列 链表 树 树 (续 ) 期中考试 图 图 (续 ) 内部爿u冫 外部排序 Hash法 优先级队列 (选讲) 高效⊥义苻找树 (选讲) 多路今找树 (选讲) 数字树杏找结构 (选讲) 第 1章 第 2章 第 3章 第一次作业截 丨卜日匆j 第 茌章 第 5章 第工次作业截J卜日期 第 6章 第I次 作业截止 日期 第 7章 第 7章 第 8章 第 9章 第四次作业截 丨卜日期J 第 10崇 第 11崇 第 12章 · 图 2一 I期 课不V安 排 (快速进度 ) 数据结构的提高课程可采川图 3的 教学安排,选 课学生应学过数据结构的基本内容,最 好有表、树、图各种数据结构的基础。 有些学校一学年分四个小学期 (quarter叩 stem),对 J1这种学期设置,完 整的数据纬构 课稆需要 丨圬用两个小学期,教 学安排可参考图茌和图5。选课学生应学过高级不V序 设计课程, 并在这门先修课中学过算法分析与数据结构的基本内容。 借 此 新 书 出 版 机 会 ,我 们 再 一 次 感 谢 为 本 书 第 1版 捉 供 过 帮 助 和 攴 持 的 各 位 同 芋 。 感 谢 Ⅲ hoisl/Vesleyan University的 Lisa Brown教 授 ,感 谢 Ⅱ sa Brown教 授 Pr。 gramming III 课 稆 的 选 课 学 生 ,感 谢 Colorado School of Mines的 Dinesh Mehta溥 十 为 本 书 第 一 版 纠 错 , 感 谢 Ⅲ hois Wesleyan University的 Computer Services机 构 及 其 员 I Trey Short和 Curtis Kelch,感 谢 他 们 提 供 的 技 术 帮 助 。 还 要 感 谢 AT&T贝 尔 实 验 室 的 Narain Gehani,Arcadia University的 Tomasz Muldner,以 及 Trinity University的 Ronald Prather,感 谢 他 亻门 审 阅 本 书 初 稿 。 特 别 耍 感 谢 Friedman大 妇 ,Art IJ Barbara,他 们 从 开 始 就 是 本 |氵的 出 版 业 务 负 责

周次内容 阅读材料 1 树的复习与串 第5竟 2 图的复习与串讲 第6章 3 外部排序 第7章 4 外都排序（续）》 5 Hash法（复习基本Hash技术 第8章 Bloom虑波器，动泰Hash法) 第一次作业截止日期 6 优先级队列（左倾树，对称最小-最大堆，区间堆） 第9章 1 休级队列（分雄复杂度，二项式雅】 第9章 8 优先级队列(Fibonacci堆，对偶堆) 第二次作业截止日期 9 高效一义脊找树（最优BST树，AVL树） 第10章 10 期中考试 11 高效二义查找树（红-黑树，Splay树） 12 多路查找树(B-树，B+树) 第11肖 13 数字在找结构（数字杏找树，二路Tnie树，Patricia第：次作业截止日期 14 多路Trie树 15 后缀树 第四次作业截止日期 16Trie树互联网包中维 图3学期课程安排（数据结构提高课程）》 周次内容 阅读材料 1 算法马数组复习 第1、2章 2 栈队列 第3章 链表（栈、队列、多项式） 第4章 4 链表 5 树（遍历、集合的表示〉 第5章 第一次作业截止日期 6 树（堆，查找 期中考试 7 图（遍历，连通分量 第6章 图（最小生成树） 第6草 9 图（最短路径） 第6音 10 图（活动网络） 第二次作业截止日期 图4第一个小学期

V1 周次 内 容 阅读材料 1 树 的复习与串讲 第 5章 2 图 的复习与串讲 第 6章 3 外 部排序 第 7章 在 外 部排序 (续 ) 5 Hash法 (复 习 基 本 Hash技 术 第 8章 Bloom滤 波器,动 态 Hash法 ) 第 一次作业截 丨L日 期 6 优 先级队列 (左倾树,对 称最小-最人堆,区 间堆) 第 9章 7 优 先级队列 (分摊复杂度,二 项式堆) 第 9章 8 优 先级队列 (F山onacci堆 ,对 偶堆) 第 工次作业截 l⒈日期 9 高 效工叉莶找树 (最优 BsT树 ,AVL树 ) 第 10章 10 期 中考试 11 高 效工叉杏找树 (红-黑树,Splay树 ) 12 多 路莶找树 (B-树 ,B+树 ) 第 11章 13 数 字佥找结构 (数字贲找树,工 路 Trie树 ,Patricia 第 ∷次作业截 |卜冂期 树) ⒕ 多 路 Trie树 15 后 缀树 第 四次作业截 |卜日期 16 Trie树 与互联网包中继 图 3学 期课稆安排 (数据纬构提高课程) 月次 内 容 阅读材料 1 算 法与数组复习 2 栈 Jj队 列 3 链 表 (栈 、队列、多项式) 茌 链 表 5 树 (遍历、集合的表示) 6 树 (堆 ,杏 找) 期中考试 7 图 (遍历,连 通分蚩) 8 图 (最 小生成树) 9 图 (最 短路径) 10 图 (活动网络) 第 1、⒉章 第 3章 第 茌章 第 5章 第一次作业截 丨卜日期 第 6章 第 6章 第 6章 第工次作业截 丨卜日期 图 4第 一个小学期

周次内容 阅读材利 1 内部拌序（插入排序，快速播序 第7草 排序的界，O(1)空间归并，1并排序) 2 排序（堆排序，基数排序，链表排序，表排序） 3 外部子 第7章 Hash法 第8章 中考试 6 优先级队列（左倾树，对称成小敏人推，区间堆）第9章 7 优先级队列（分推复杂度，二项式推，Fibonacci堆）第9单 高效二找树(AVL树域-黑树，Splay树) 9 多路布找树(B-树，B+树) 第11章 第：次作业截止H期 10数字在找结构(Trie树，后缀树) 第12汽 图5第二个小学 人，此从初明推形到最后出版，是经他！之手促成的 Ellis Horowitz Sartai Sahni Susan Anderson-Freed

飞`11 周次 内 容 阅}女小扌卡I| 1 内 部排序 (插入排序,快 速排序 第 7崇 排序的界,O(1)空 间旷l并,丿l丿{∶扌|⒈∫丫) 2 排 序 (堆排序,基 数排序,链 表排序,表 排∫r) 3 外 部排△ 第 7崇 4 Hash法 第 8崇 期中考试 6 优 先级队列 (左倾树,对 称最小-鼓 人堆,l×问J住) 第 9幸 7 优 先级队列 (分摊复杂度,工 项式堆,Fibonacci堆 ) 第 9章 8 高 效 工 义 夺 找 树 (AVL树 或 纟I∶-熙 树 ,Splay树 ) 9 多 路 夺找树 (B-树 ,B+树 ) 第 11幸 第∷∶次ll∶业截 |卜H坩 j 10 数 字合找结构 (Trie树 ,后 缀树) 第 12屮 图 5第 二个小 丿j夕J妙| 人,此 |氵从初期雏形到鼓后出版,足 经他们之 T促 成的G E11is I-Ioroˇvitz %r叫 Sahni Susan AndersOn-Freed

目录 第1章基本概念 1 S11概观：系统生命周期 1 S1.2指针和动态存储分配 ，。，。，,。，+。··”.·。 3 512.1指针 3 61.2.2动态存储分配 4 12.3指针隐患，········· 6 51.3算法形式规范. 6 5131综论，.，。，。，···. 6 $1.3.2递归算法 11 514数据抽象。·。，·，···························. 4 S1.5性能分析 61.5.1空间复於度.·. 18 515.2时间复杂度 。 $1.5.3渐近记号(0，⊙) 15.4实际复尔度，· 名 S1.6性能度量. 35 s1.61定时，. S1.6.2生成测试数据 39 517参考文献和选读材料··.··························· 40 第2章数组和结构 41 62.1数组. 2.1数组的抽象数据类型 41 $2.1.2C语言的数组 41 2.2数组的动态存储分配 44 6221一准数组。，。，。，·。，·。，·········· 44 6222-维数组 523结构体和联合体···。··，·。，··。··········.········· 47 52.3.1结构体 62.3.2联合体.·. 49 23.3结构的内部实现·················· 50 8234白用结构.，. 50 24多项式， 5 2.41多项式的抽象数据类型。··。·，.·······.····，··· 51 242多项式的表示。···，·····，············· 52 243多项式加法.·.。. 55 4

目 第 1章§1.1 §1.2 基本概 念 概 观:系 统 生 命 周 期 。. . 指 针和动 态 存 储 分 配 . . §1.2.1 指 针 ˉ . . . . . §1.2.2 动 态 存储分配 . . §1.2.3 指 钅|ˉ隐患 . . 。 . 算法形式 规 范 。. .。. . § 1.3.1 综 论 . . 。 . . § 1.3.2 递 归 算 法 。 . . . 数 据 抽 象 . ,. 。 . . 性 能 分 析 . . 。 。 . . § 1.5.1 空 间 复 杂 度 . . . § 1.5.2 时 间 复 杂 度 .。 . . § 1.5.3 渐 近 记 号 (O'Ω 'Θ ) 11334666 11 14 17 18 20 27 33 35 35 39 40 41 41 41 41 4茌 4茌 44 47 47 49 50 50 51 51 52 55 §1.3 §1.在 §1.5 § 1.5。 茌 实 际 复 杂 度 . . . . § 1.6 性 能 度 量 . . . 。 . . § 1.6.1 定 时 . . . . . . §1.6.2 生 成测试数据 . . 。 §1.7 参 考文 献 和 选读材 料 . . 第 2章 数 组 和 结 构 皿 .1 数 组 。 . . . . . · · . §2.1.1 数 细~的抽象数据类 型 . 皿 。 1.2C语 言 的 数 组 . . . llz.2 数 组的动 态 存储分 配 . 。 . 皿 .2.1 一 维 数 细 ~. . . . § 2.2· 2 工 维 数 细 . . . 。 。 ⒓。3 结 构 体和联合体 . . 。,. 皿 。 3.1 结 构 体 . . . . . 皿 .3.2 联 合 体 。 . .。 . . · 皿.3.3 结 构的内 部 实 现 . . § 2。 ⒊ 4 白 引 用 结 构 . . . . 皿 。 4 多 项 式 。 . . . . . . · §2。4.1 多 项 式的抽象数据类 犁 皿。4.2 多 项式 的表示 . . 。 § 2。 4.3 多 项 式 加 法 。 . . , 1X