首页 > 图书中心 >图书详情

数据结构基础(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 >
扫描二维码
下载APP了解更多

同系列产品more >

图像处理、分析与机器视觉(第4版)...

Milan Sonka,Vaclav Hla
定 价:99元

查看详情
计算机体系结构

Gerard Blanchet, Bertr
定 价:39元

查看详情
操作系统原理与应用(第4版)

Michael Palmer, Michae
定 价:98元

查看详情
软件架构与模式

Joachim Goll 著 贾山
定 价:49元

查看详情
无线移动网络安全(第2版)

Man Young Rhee 著 葛秀
定 价:59元

查看详情
图书分类全部图书
more >
  • 第1章 基本概念

    1.1 概述:系统生命周期

    1.2 指针和动态存储分配

    1.3 算法形式规范

    1.4 数据抽象

    1.5 性能分析

    1.6 性能度量

    1.7 参考文献和选读材料

    第2章 数组和结构

    2.1 数组

    2.2 数组的动态存储分配

    2.3 结构体和联合体

    2.4 多项式

    2.5 稀松矩阵

    2.6 多维数组的表示

    2.7 字符串

    2.8 参考文献和选读材料

    2.9 补充习题

    第3章 栈与队列

    3.1 栈

    3.2 动态栈

    3.3 队列

    3.4 动态循环队列

    3.5 迷宫问题

    3.6 表达式求值

    3.7 多重栈与多重队列

    3.8 补充习题

    第4章 链表

    4.1 单向链表

    4.2 用C语言表示单向链表

    4.3 链式栈与链式队列

    4.4 多项式

    4.5 其它链表操作

    4.6 等价类

    4.7 稀疏矩阵

    4.8 双向链表

    第5章 树

    5.1 引论

    5.2 二叉树

    5.3 遍历二叉树

    5.4 其它二叉树操作

    5.5 线索二叉树

    5.6 堆

    5.7 二叉查找树

    5.8 选拔树

    5.9 森林

    5.10 不相交集合的表示

    5.11 二叉树的计数

    5.12 参考文献和选读材料

    第6章 图

    6.1 图的抽象数据类型

    6.2 图的基本操作

    6.3 最小代价生成树

    6.4 最短路径和迁移闭包

    6.5 活动网络

    6.6 参考文献和选读材料

    6.7 补充习题

    第7章 排...

精彩书评more >

标题

评论

版权所有(C)2019 清华大学出版社有限公司 京ICP备10035462号 京公网安备11010802013248号

联系我们 | 网站地图 | 法律声明 | 友情链接 | 盗版举报 | 人才招聘