国外经典教材 C++数据结构与程序设计 Robert l. kruse 美) 著 Alexander J Ryba 钱丽萍 译 清华大学出版社 北京 内容简介 这木精心制作的课本结合面向对象程序设计和C+燥有力的特性,构建数据结构的基本思想,设 计了程序和存趣的应用。在此过程中,本书探讨了作为软件设计基本工其的间题求解和设计原理、数 据抽象、递归和算法比较分。本书使用真实的案例征究、可用软件开发和程序设计项目来增 强理解。 本内容详尽且配有大量的实例利习题。中所有算法都做了详细的注解,有利J该者理解算法 的实质和编程恩想 本书既可作为高等学校计算机及相关专业学生的教材,亦叫供计算机应用领城图工程技术人员参 老,尤其遁合于应用C++语言编程的科技人员 Simplified Chinese edition copyright C 2003 by PEARSON EDUCATION ASIA LIMITED and TSINGHUA UNIVERSITY PRESS. Original English language title from Proprietor,'s edition of the Work Original English language title: Data Structures and Program Design in C++, 1st Edition by Robert L Kruse, Alexander J Ryba, Copyright o 1999 EsRN:0-l3-768995-0 All Rights Reserved Published by arrangement with the original publisher, Pearson Education, InC. publishing as Prentice-Halt, Inc. This edition is authorized for sale only in the People's Republic of China (excluding the Special Administrative Region of Hong Kong and macao 本书中文简体翻译版由 Pearson Education授权给清华半出版社在国境内(不包括中国香港、澳门特 别行政区)出版发行。 北京市版权局若作权合同登记号图字:01-2003-0566 本书封面贴有 Pearson educatioη培生教育出版集团)激光防伪标签,无标釜者不得销售。 图书在版编目(cP)数据 C艹数据結构与程序设计!(美〕克鲁斯(KTse,R.L),(美)瑞贝(Rya,A.J)著;钱丽萍译.一北 尔:清华大学出版礼,2003 国外经典教材 书名原文: Data Structures and Program Design in C .C…I①克…②瑞…③栈…Ⅲ①C语占一程设计一教材②数据结构一敕材Ⅳ.①TP12 ISBN730247804-1 12)TP311 12 十国版本图书馆CP数据核字(2003)第604!号 出版者:清华大学出版社 地址:北京清华大学学研大厦 http://www.tup n邮编:100084 社总机:0106270175客户服务:010462776969 文稿编辑:汤涌涛 封面设计:久久度企划 印装者:清华大学印刷 发行者:新华书店总店北京发行所 开本:18 0印张:37.5字数:908 版次:2049年1月第!版204年1小第1次印丽 书号:BN130247804568 印数 定价:59.00元 本书如存在文字不濆、巅印以及缺页、倒页、脱页等印装质量问题,请与清华大学出版社出版部联系 调换。联系电话:(010)62770175-303或(010)62795704 读者对本书的赞誉 ★★★★★ 木书以前的 Pascal版本特别易于阅读也是我学习数据结构的用书。课本中包含的许 多图表对于理解算法来说其价值是无法衡量的。本将对以前的版本做了进一步改进加入 了更直观的图片,并对旧书进行了更新,加入了旧书编写时未出现的一些新的算法和分析技 术,如平摊分析。作者的编写风格完全易于理解。我收集有多本有关算法和数据结构的书, 而这一本是迄今为止可读性最好的 Jeffrey Hsu,摘自亚马逊网站 ★★★★★ 我个人认为,作为数据结构的入门书籍这本书是极好的。首先,它通过有趣而具体的 例子成功地激发了学生学习相关主题的兴趣。其次,它注意使用图画和色彩,从而使得阅读 尽可能寳易。最后,作者在程序中精细地“提升”了“结构”的概念并在整篇课文中都说朔了 它的重要性 名谈者,摘自亚马逊网站 ★★★★★ 本书对那些需要研究构成通用程序的数据结构的C程序设计新手来说是优秀的资源 例如课文以一定的深度讨论了队列栈、哈希表和递归,但这些讨论却是易于理解的 名读者,摘自亚马逊网站 ★★★★★ 如果你是一个中级C+程序设计者则本书以一种清晰的方式介绍了数据结构,书中有 些我在教科书中曾看到过的最好的图形。每一章的结尾都包含了非常好的练习和高级阅 读物的列表(出色的特征)。也许对于高级学生来说,这本书显得不够详细,但我确实非常喜 欢这本书。非常感谢作者! 摘自亚马逊网站 前 木匠学徒可能仅仅需要一把斧头和一把锯子,而建筑师却使用许多精密的工具。计算 机程序设计同样需要完善的工具来应对实际应用的复杂性,而只有不断使用这些工具进彳 实践才能积累使用技能。本书将结构化问题求解、面向对象的程序设计数据抽象以及算 法的比较分析看作程厅设计的基本工具。书中详细设计了几个柑当规馍的案例研究,以此 说明如何同时使用所有这些r具来建立完整的程序 我们所研究的许多算法和数据结构拥有内在的简洁性,这是一种掩盖了它们的应用范 围和能力的简洁性。用不了多长时间,学生即发现在预备课程中经常使用的一些天真的方 法得到了巨大的改进。然而方法的这种简洁性却被不确定性淡化了。学生很快又发现,几 种方法中的哪一种在特定应用中能证明是最佳的,其答案近非显而易见。因此我们利用这 个机会,及早地介绍那些既具有内在趣味性,又具有实际重要性的真正复杂的问题,并展示 数学方法在算法验证和分析中的应用 许多学生感到很难将抽象的概念转化为实践。因此,本书特别关注了将概念表达成算 法和将算法细化成能运用于实际问题的具体程序。类似地,本书将数据说明和抽象的过程 放在数据结构选择及其实现之前。 精心设计启发性的例子继之以更通用的形式来表达这个概念,我们认为这是一个从具 体到抽象的发展过程。大多数学生在其学业的早期,需要通过目睹所学概念的直接应用来 加以巩固,他们需要编写并且运行程序,以阐明自己所学的每个重要概念。因此忄书包含许 多例子程序,有较短的函数,也有相当长的完整程序。另外,习题和程序设计项目构成了本 书不可缺少的部分。其中许多习题和项目是所学主题的直接应用,经常要求编写和运行程 序,以此可以测试和比较算法。有些是比较大的项目,并且有一些项目适合学生小组共同设 计完成 本书中的程序釆用流行的面向对象语言C+编写。我们认为许多面向对象的技术为数 据结构设计的基本原理提供了自然的实现。这样,C++允许我们构造安全,有效和简单的数 据结构实现。我们承认(艹+很复杂,学生们需要通过学习一门数据结构课程来深化和提炼 他们对这门语言的理解。在编写本书的过程中,我们尽量通过仔细介绍和解释C++各种面 向对象的特征来支持这种深化。因此,我们在第1章开始时假设读者能自如地使用℃++的 基本部分(实质上是C的子集),并逐步地加入C+的面向对象的元素,如类、方法、构造函 数继承、动态内存管理、忻构函数、拷贝构造函数、重载函数和运算符模板虚函数和STL 当然,本书重点讲述的是数据结构,因此对不太了解C++的学生来说,阅读本书前需要先学 习一本十+程序设计的课本 大纲 学头程序设计原理 第1章通过完成首个大型项目 Conway的LIc游戏),详细说明面向对象的程序设计、 ++数据结构与程序设计 自顶向下的细化、复査和测试的原理,向学生展示这些原理,并且希望他们从头到尾都遵循 这些原理。同时,这个项目为学生提供了一个机会来复习C++基本特征的语法,C++是本书 通篇使用的程序设计语言。 栈 第2章介绍我们要学习的第一种数据结构一·栈。本章将栈应用到反转输入、模拟桌 面计算器和检查括弧嵌套等程序设计中。开始时利用STL栈实现,随后设计和使用我们自 己的栈实现。第2章的一个主要目的是使学生理解信息隐藏封装和数据抽象这些概念后 面的思想,并将自顶向下的设计方法应用于数据和算法。本章最后对抽象数据类型进行了 介绍。 好兴头队列 队列是第3章的中心论点。本章详细说明抽象数据类型的几种不同实现,并设计一个 大型的应用程序来说明不同实现的相对优点。本章介绍了继承这-重要的面向对象技术 关x链栈和队列 第4章提供栈和队列的链式实现。本章首先对C+中的指针和动态内存管理做一个全 面的介绍。在展示一种简单的链栈实现后,我们讨论析构函数、拷贝构造函数和重载赋值运 算符,它们都是链式结构的安全的C+实现中所需要的 头关递归 第5章通过研究栈与递归问题的求解和程序设计之间的关系来继续阐明栈。本书通过 研究几个实质性的递归应用来巩固这些概念,这些应用包括呵溯和树结构的程序。如果需 要的话,本章可以安排在此处之前第2章结束后的任何时候学习。 ￥表和宇符串 第6章的主题是以链式和邻接实现的更通用的表。本章也包含封装的字符串的实现、 C++模板介绍和对算法分析的非形式化的介绍 查找 头关排序 表和信息检索 第?章第8章和第9章分别介绍查找排序和表格访问(包含散列)的算法。这些章节 阐述算法和相关抽象效据类型、数据结构及实现之间的相互关系。课本中为初步的算法分 析引人“大O”和相关符号,并强调在空间、时间和程序设计强度的最佳利用方面作出关键 的选择。这些选择要求我们找到分析方法来评价算法,而进行这些分析犹如一场战斗,需要 利用组合数学这样的武器。在初级水平我们既不期望学生全面掌握,也不期望他们拥有完 备的数学知识而使自己的技能变得完美。因此,我们的目的是帮助学生认识到这些技能的 重要性,期待以后有机会再学习数学 并二叉树 二叉树肯定是数据结构中最精致和有用的数据结构之一。第10章将对它进行研究,并 将它与表查找排序中的概念相结合。作为递归定义的数据结构,二叉树为学牛灵活地在 数据结构和算法中应用递归提供了条件。本章以基本主题开始,并进展到诸如伸展树和平 摊算法分析这样的高深的主题 前言 关多路树 第11章继续学习更复杂的数据结构,包括Tri树、B-树和红树 图 第12章介绍图,将它作为对问题求解有用的更通用的结构,并介绍图中最短路径和最 小生成树的一些经典算法。 头兴兴案例研究:波兰表示法 第13章中的案例研究相当详细地分析了波兰表示法,以此研究递归树和栈作为问题 求解和算法设计工具的相互关系。所涉及的一些问题能允当编译器设计的一个非形式化的 介绍。我们照例将这个算法完全设计成一个能运行的→+程序,此程序接受输入普通(中 缀)形式的表达式将它翻译成后缀形式,并用指定的变量值评估此表达式。第13章可安排 在1.1节完成后的任何时候学习。 附录中的几个论趟并非切合于本书主题,但学生在课程准备过程中经常遗漏它们 装长共数学方法 附录A介绍了离散数学中的一些论题。它的最后两节是斐波纳契数( Fibonacci miumber)和卡塔数( Catalan number),这两节更为复杂,并且并非课本中任何重要论题所 必需的但附录中将它们包含进来是鼓脑更偏向数学的综合兴趣。 炊兴关随机数 附录B讨论伪随机数生成器和应用,这是许多学生感兴趣的论题但它不适合放在本 课程的正文中。 x*￥软件包和实用函数 附录C对本书中设计和多次使用的各种实用程序和数据结构软件包进行分类。附录C 中讨论了声明和定义文件、变换单位、本书中通篇所用的实用程序包和个计算CPU时间 的软件包。 ￥*兴程序被计技术规则、启示和易犯的错误 最后,附录D收集了所有的程序设计技术规则及分散在本书中的所有启示和易犯的错 误,并将它们按主题红织以方便参考 课程结构 ￥必备条件 学习本书的必备条件是学习过一门基本的程序设计课程,具有使用C+基本特征的经 验。然而因为我们仅仅是逐步谨慎地引入复杂的C+技术,我们相信,结合使用一本补充 的C++课本和关于C++语言问题的更多的用法说明和重点,之本书提供了C+版的数据 结构教程即使对于程序设计背景是另一门语言(如C,Pasa或Java)的学生,这本书仍然 适用 中学数学的良好知识能满足几乎所有的算法分析的需要,但进一步的《可能是同步的 离散数学的知识准备将颇有价值。附录A中复习了所有要求的数学知识。 内容 本书供诸如 ACM Course cs2(程序设计和实现)、 ACM Course cs7(数据结构和算法 +数据结构与程序设计 分析)或结合了这些课程的某门课程俠用。木书完全覆盖了ACM/EEE关于数据结构和算 法的大多数知识单元,它们包括 AL基本数据结构,如数组、表、栈、队列、树和图 AL2抽象数据类型 AL3递归和递归算法; AL4使用大符号的复杂性分析; AL6排序和查找; AL8带有大型案例研究的实际问题求解策略。 本书不论述3个最高级的知识单元;AL5(复杂性类,NP完全问题)AL7(可计算性和 不可判定性)和AL9(并行和分布式算法 本书中大多数章节都是首先介绍核心主题然后给出例子、应用和更大的案例研究。因 此,如果时间仅允许简要学习某个主题,则可以在不失连续性的情况下仅学习核心主题,快 速地从一章跳到另一章。然而当时间允许时,学习那些附加的主题和完成的项目都将使学 生和教师从中获益。 并“两学期课程 基木上可以用两学期的时间学完本书,学完本书后您就可以了解问题求解、数据结构 程序开发和算法分析等领域的许多论题。学生需要时问和实践米理解通用方法。通过将数 据抽象、数据结构和算法的学习同它们在现实规模的项目中的实现相结合,一门综合的课程 可以奠定一个坚实的基础,此后可以基于它学习更多的理论课程。即使本书没有完全覆盖 它们,但也提供了足够的深度,使得感兴趣的学生在以后的工作中可以继续用它作为参考书 目。无论如何,分配主要的程序设计项目并给予足够的时间来完成它们,这一点是重要的。 补充材料 除本书全部内容以外,还有一些补充材料包括 来自课本的所有的软件包程序和其他C++代码段,其格式便于按需并人其他程序 课本中一些示例程序和几乎所有程序设计项的可执行的版本(DOs或 Windows 平台) 课本中每节的提要或总结,适于用作学习指南 这些材料可通过fp方式获取:以anonymous用户登录进站点ftpb.penhale.comn,并转 到目录pwb/em/ com puter-sctence.0/re/p。 致谢 这些年来,本书的Paca版和C语言版得到许多人的帮助,他们是家人、期友、同事和学 生,在以前的书中曾特别提到过其中一些人。其他的许多入在学这些书或是其各种语言 ①)参见〔 omputing Curricula1991:Rpr加ACMⅠ LEF-CS uint Curriculurrt Task Force ACM Press, New York, 1990 前 的译本的同时,友好地将他们的意见和建议转发给我们所有这些都有助于我们将这个书做 得更好 感谢下列审阅者的建议,他们在许多方面帮助我们改进本书。他们是: Vander Linden 加尔文学院)、 Jens gregor田纳西州大学)、 Victor Berry(波士顿大学) Jeffery Leon(伊利 诺伊大学芝加哥分校)、 Susan hutt(密苏里哥伦比亚大学) Fred harris(内华达大学)、zhi Li Zhang(明尼苏达大学)和 Andrew Surg(新墨西哥技术学院)。 Alex ryba特别感谢 Marquette学的 Wim rustenburg和 John siren,近年来从他们 那里获得了富有成效的建议和鼓励还要感谢以前的学生 Rick vogel和 Jun Wang提出的 意见 Robert Kruse特感谢 PreteX公司 Paul manihot不断提出忠告并给予帮助,他最初 是一名出色的学生,后来作为一名可靠的研究助手,现在已成为一名得力的同事。他在书籍 制作的软件开发,项目管理,对出版商、印刷工和作者的问题解答以及为这项工作的各方面 提出忠告和鼓励等方銜都做出了重要的页献 没有 Prentice hall的编辑人员,特别是出版商 Alan Apt、采编 Laura steele和主编 Marcia horton热心的支持真诚的鼓励和极大的耐心,这个项目不会开始,当然也不会完 成。他们和其他制作人员的帮助是无价的 Robert l. Kr Tusi Alexander J. Ryb