首页 > 图书中心 >图书详情
数据结构基础(C语言版)第2版
作者:Ellis Horowitz, Sartaj Sahni,
定价:49元
印次:1-11
ISBN:9787302186960
出版日期:2009.03.01
印刷日期:2020.12.22
本书是最经典数据结构教材的最新版本,国内外大多数的同类教材都是以本书为蓝本编写而来的。 本书用C作为描述语言,全面而生动地介绍了数据结构的有关知识,如数组、栈、队列、链表、树和图,以及构成所有软件基础的排序散列技术。此外,本书还介绍了各种高级或特殊数据结构,如优先级队列、高效二叉查找树、多路查找树等。本书对大多数算法都给出了计算时间在最优、最差情形下的复杂度分析。 本书不仅可以作为计算机及相关专业本科生“数据结构”课程的教材,也可以作为研究生第一学年的“高等数据结构”课程的教材,同时,本书所介绍的各种算法的C语言实现,对有关专业人员也具有很好的参考价值。 作者介绍: Ellis Horowitz是南加州大学计算机与电子工程系的教授。Horowitz博士已编著了10多本教材,并发表了大量学术论文。 Sartaj Sahni是佛罗里达大学计算机与信息科学系的杰出教授和讲座教授。Sahni博士已发表300多篇学术研究论文,编著了15本教材。 Susan Anderson-Freed是伊利诺伊卫斯理大学计算机系教授。她的研究领域是数据库管理系统、Web设计与开发。她毕业于诺伯特大学,并在印第安纳大学获得硕士和博士学位,以及在Bradley大学获得计算机理学硕士学位。她从1977年起就供职于伊利诺伊卫斯理大学。 【英文名】Fundamentals of Data Structures in C, 2e 【书名】数据结构基础(C语言版)(第2版) 【作者】 Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed著 【原出版社】Silicon Press
more >本书是《数据结构基础》的 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
more >