高级搜索  |  搜索帮助
最近的浏览历史
购买此书的人还购买过
书  名:数据结构基础(C++语言版)第2版
  • 作  者: Ellis Horowitz, Sartaj Sahni,
  • 出版时间: 2009-03-01
  • 出 版 社: 清华大学出版社
  • 字  数: 746 千字
  • 印  次: 1-1
  • 印  张: 31
  • 开  本: 16开
  • ISBN: 9787302187035
  • 装  帧: 平装
  • 定  价:¥49.00
电子书价:¥34.30 折扣:70折 节省:¥14.70 vip价:¥34.30 电子书大小:7.92M
配套资源下载:
  • 名称
  • 说明
  • 权限
  • 文件大小
  • 点击图标下载
  • 图书样章
  • 所有用户
  • 256K
共有商品评论0条 查看评论摘要
内容简介
  本书是最经典数据结构教材的最新版本,国内外大多数的同类教材都是以本书为蓝本编写而来的。
本书用C++作为描述语言,全面而生动地介绍了数据结构的有关知识,如数组、栈、队列、链表、树和图,以及构成所有软件基础的排序散列技术。此外,本书还介绍了各种高级或特殊数据结构,如优先级队列、高效二叉查找树、多路查找树等。本书对大多数算法都给出了计算时间在最优、最差情形下的复杂度分析。本书的更新版已涵盖了C++语言的最新特性。
本书不仅可以作为计算机及相关专业本科生“数据结构”课程的教材,也可以作为研究生第一学年的“高等数据结构”课程的教材,同时,本书所介绍的各种算法的C++语言实现,对有关专业人员也具有很好的参考价值。

作者介绍:
Ellis Horowitz是南加州大学计算机与电子工程系的教授。Horowitz博士已编著了10多本教材,并发表了大量学术论文。

Sartaj Sahni是佛罗里达大学计算机与信息科学系的杰出教授和讲座教授。Sahni博士已发表300多篇学术研究论文,编著了15本教材。

Dinesh Mehta是科罗拉多矿业大学教授,数学与计算机科学系的副主任。Mehta博士已发表30多篇期刊和会议论文。

【英文名】Fundamentals of Data Structures in C++ , 2E
【书名】数据结构基础(C++语言版)(第2版)
【作者】 Ellis Horowitz, Sartaj Sahni, Dinesh Mehta 著
【定价】49.00元
【原出版社】Silicon Press
前言
  前 言
自从1995年本书的第1版发行以来,C++语言已经发生了许多明显的变化。基于这些变化,我们在本书新版本中也进行了多处修改。例如,将C++的例外(exception)和模板(template)等概念添加到新版本中。也对标准模板库(STL)函数进行了介绍。随着STL(以及像Boost和LEAD等其他函数库)的广泛使用,产生了一些关于应该如何看待数据结构的有趣问题。毫无疑问,从软件开发的角度看,用STL来实现数据结构比程序员自己实现它要容易得多。根据这种观点,人们有理由认为,未来对数据结构的应用会像今天的组合式程序设计一样。也就是说,在今后,程序设计中的数据结构问题将交给程序语言和编译器来处理,它将不再属于主流程序设计人员需要考虑的技术范围。
然而,从教学的角度来看,数据结构显然是计算机科学领域的基本技术,它不应该被简单化,也不能为了让其更容易被理解而将一些难懂的内容从教材中删除。因此,在本书新版本的编写过程中,我们仍然认为,让学生了解如何实现和分析高效的数据结构,并掌握其中的本质内容是非常重要的。基于这种观点,本书继续强调数据结构的底层实现技术细节,并对各种数据结构操作算法的复杂性进行精确地分析。
除了增加一些与C++语言有关的内容之外,在新版本中我们还对数据结构的内容进行了一些扩充和修改。第2章(数组)增加了对“数组加倍”技术的讨论,这种技术的特点是,当向一个数组插入元素或从中删除元素时,可以重新改变数组的大小,而不会因此产生对数组操作复杂性不利的影响。关于这种技术的讨论,被编排在有关动态数组的章节中。第3章(栈和队列)增加了有关队列抽象数据类型的数组实现的一些技术细节。第4章(链表)增加了对迭代器改进技术的讨论。在第5章(树)和第6章(图)中没有增加新的概念。在第7章(排序)中,我们删除了对时间复杂度为O(1)的归并方法的讨论。在第8章(散列)中,专门增加了一节讨论“安全哈希函数”,在动态散列一节中增加了一些新内容(特别将动态散列与数组加倍进行了比较)。我们把“布隆过滤器”的内容也移到了这一章中。第9章(优先队列)也有多处被修改。我们增加了关于“重量左偏树”(除了高度左偏树以外)和“配对堆”(作为斐波那契堆的一种替代)的讨论。我们删除了最小-最大堆,并用更有效的对称“最小-最大堆”和“区间堆”替代。
我们对本书第1版中的第10章(查找结构)内容进行了重要扩充,并将这一章的内容分成3章: 高效二叉查找树(第10章)、多路查找树(第11章)和数字查找结构(第12章)。在第1版中,“红-黑树”是从“234-树”中导出的(而234-树的讨论是在23-树之后)。在本版本中,我们独立地给出了红-黑树定义,这就使得教师不必先讲解23-树或234-树,再讲解红-黑树(有关23-树和234-树的内容已被删除,因为它们可以作为B-树的一种特例)。在第10章中还增加了“自顶向下的伸展树”一节(除了前一版的自底向上的伸展树之外)。第11章包含了对B树的讨论。因为B+树在数据库中的应用,在这一章中我们增加了对它的详细讨论。最后,第12章中只是简单地讨论了数字查找树、二叉Trie树和Patrica树。这些内容在前一版本中是被重点介绍的。在这一版本中,我们选择了重点介绍更广泛使用的“多路Trie树”。关于Trie树的各种变化和实现也在本书中被进一步探讨。这一章中还包含了一节关于“后缀树”的内容,以及关于Trie树在Internet包转发中应用的内容。
在URL地址http://www.mines.edu/~dmehta/FDS_CPP/中有本书中程序的代码、勘误表和一些从第1版中已删除章节的pdf文件。
数据结构基础(C++语言版)(第2版)前言本书的使用
对于准备使用本书作为教材,并在一学期内讲授该课程的教师,建议采用两种授课方案: 中级程度和高级程度。对于计算机专业的学生,建议采用中级程度方案。本门课程可能是他们课程计划中的第2门或第3门课程。对大部分教师,包括本书作者,都可按照中级程度进行教学。以下教学大纲是与ACM推荐的课程计划中课程C2(课程计划78, CACM 3/79 和CACM 8/85)相对应的。教学计划--中级程度
周次内 容阅读章节1C++和算法介绍第1章2C++和数组第2章3数组(串)完成第1次程序设计作业4栈和队列第3章5链表(单链表和双向链表)第4章6链表完成第2次程序设计作业7树(基本概念和二叉树)第5章8树(查找和堆)9期中考试10图(基本概念和表示)第6章11图(最短路径、生成树、拓扑排序)完成第3次程序设计作业12内部排序(插入、快速和归并)第7章13内部排序(堆和基数)完成第4次程序设计作业14散列第8章15选择高级主题第9章~第12章16选择高级主题第9章~第12章 建议布置若干次程序设计作业,时间上有所间隔,并贯穿整个学期。第1次作业的目的是使学生熟悉计算机环境。第2次作业应该重点强调链表结构,相关内容将在第4章介绍。在第4章的练习中,给出了一些程序设计的题目。中等程度的课程进度中不包括外部排序的内容,这样做的目的是留更多的时间讲授更重要的内容,即散列。散列的概念将在以后多门课程中应用,所以,在本门课程中详细讨论是非常重要的。讲授完散列后,建议从第9章~第12中选择一些高级主题进行讲授。
高级程度的教学内容适合于研究生一年级或本科生高年级。推荐的教学进度如下。 教学计划--高级程度
周次内 容阅读章节1C++和算法介绍第1章2C++和数组第2章3栈和队列第3章
完成第1次程序设计作业4链表第4章5树第5章6树(继续)完成第2次程序设计作业7期中考试8图第6章9图(继续)完成第3次程序设计作业10内部排序第7章11外部排序第7章12散列第8章13优先队列第9章
完成第4次程序设计作业14高效二叉查找树(可选内容)第10章15多路查找树(可选内容)第11章16数字查找结构(可选内容)第12章 高级程度教学计划中的程序设计作业和期中考试安排与中级程度完全相同。但总的教学进度更快。对于高级程度教学计划,安排了4周学习第9章~第12章内容,这就使得其他章的教学内容要相应地减少。
最后,将给出高级数据结构的教学课程计划。假定学生已经了解了一些基本概念,特别是关于链表、树和图的概念。在高级数据结构教学计划中,我们计划用4周的时间对基本概念进行深入的回顾,这在时间上应该是足够了。高级数据结构
周次内 容阅读章节1复习树第5章2复习图第6章续表
周次内 容阅读章节3内部排序第7章4外部排序5散列(复习基本概念,布隆过滤器和动态散列)第8章
完成第1次程序设计作业6优先队列(左偏树、对称最小-最大堆和区间堆)第9章7优先队列(分摊复杂性和二项式堆)第9章8优先队列(斐波那契堆和配对堆)完成第2次程序设计作业9高效二叉查找树(最优二叉查找树和AVL树)第10章10期中考试11高效二叉查找树(红-黑树和伸展树)12多路查找树(B-树和B+树)第11章13数字查找结构(数字查找树、二叉Trie树和Patricia树)第12章
完成第3次程序设计作业14多路Trie15后缀树完成第4次程序设计作业16Trie和因特网包转发 对于实行4学期制的学校,以下给出了两个可供参考的两学期教学计划。该计划假设学生在先修的高级程序设计课程中对算法分析和数据结构的基本概念已经有所了解。第1学期
周次内 容阅读章节1算法和数组回顾第1章和第2章2栈和队列第3章3链表(栈、队列和多项式)第4章4链表5树(遍历和集合表示)第5章
完成第1次程序设计作业6树(堆和查找)期中考试7图(遍历和元素)第6章8图(最小生成树)9图(最短路径)完成第2次程序设计作业10图(活动网络)第2学期
周次内 容阅读章节1内部排序(插入、快速、下界和归并排序)第7章2排序(堆、基数、链式排序和表排序)3外部排序第7章4散列第8章5期中考试完成第1次程序设计作业6优先队列(左偏树、对称最小-最大堆和区间堆)第9章7优先队列(斐波那契堆)8高效二叉查找树(AVL或红-黑树,伸展树)第10章9多路查找树(B-树和B+树)完成第2次程序设计作业
第11章10数字查找结构(Tries和后缀树)第12章关于第1版的说明
为什么要用C++语言来描述数据结构?原因有多种。其中最重要的原因是: 授课教师纷纷采用C++语言作为讲授数据结构这门课程的首选语言。这并不会令人感到惊讶,因为C++语言具有清晰地定义抽象数据类型(类)的层次结构的能力,它是一种描述数据结构规范及其操作的理想语言。这种语言具备了面向对象编程方法所必须拥有的所有重要方面,包括信息隐藏、数据抽象和继承。
C++编译器及其特点: 我们采用ANSI C++标准描述本书中的所有程序。关于这些标准的说明可以查阅Ellis和Stroustrop编写的The Annotated C++ Reference Manual一书。本书中给出的所有程序都通过了编译并进行了测试。我们在安装了DOS/Windows 3.1操作系统的Intel/386计算机上运行Borland C/C++ 3.1编译器,并对程序进行了编译。我们也在安装了SUNOS 4.x操作系统的 SUN Sparctation计算机上通过GNU C++编译器对程序进行了编译。C++语言一直在不断进化,像模板和嵌套类这些新特性在几年前是没有的。根据我们的经验,有许多商业C++编译器(特别是旧版本)不能够很好地支持某些新的C++特性,在这种情况下,你可以删除或修改与模板相关的语句。
C++指导: 本书假设读者熟悉C语言,但不要求一定要掌握C++语言。在前4章中,我们提供了一些C++指导,大致说明这种语言的相关特点。第1.4节描述了C++语言中不同于C且与类和继承无关的一些特性。第2.1节介绍了C++语言的类。第3.1节介绍模板函数和类。第3.4节简单地描述了继承,以及如何使用它将两种数据结构进行关联。第4.11节详细说明了动态类型和虚拟函数。
面向对象的程序设计: 不能仅仅将C++语言作为对本书中数据结构进行编程的工具来使用,我们更加强调采用与优异的面向对象程序设计方法相一致的方法来使用C++语言的特性,并且要阐明在这种情况下使用这种语言的原因。这也是我们的职责所在。例如,第4章描述了链式数据结构的设计过程,同时也说明了如何通过使用模板,在一个迭代器类的相加操作中重用(reusable)它。我们强调这种设计过程,是因为其中用到的概念在任何采用结点和指针的结构中都普遍适用。在整本书中,我们始终强调抽象数据类型和信息隐藏的概念,并将这种概念融入到每一种数据结构的描述之中。对于既不熟悉数据结构,又不掌握面向对象编程的学生,教师要想在讲解数据结构的同时,阐明一种数据结构以及它与其他数据结构之间通过继承建立的关联关系是很困难的。另一方面,对于一本用C++语言描述的数据结构书籍来说,如果它不能够清晰地展示出这种基于继承的面向对象编程模式的威力,那么它也不能够算是完整的。在本书中,我们的做法是: 首先仅仅介绍各种数据结构的概念,不讨论怎样将这种数据结构与面向对象编程相结合,以免将问题复杂化。然后,当介绍完若干种类型的数据结构的概念之后,在单独的一个章节中来讨论(或者在练习中探讨)怎样在面向对象的框架中实现这些数据结构。这样做可以将选择权交给授课教师,由教师根据学生熟悉面向对象编程方法的程度来决定是否讨论继承的应用问题。
最后,利用C++语言的动态类型可以定义结点指针,用于指向不同的结点结构。这一特性在Pascal和C语言中是没有的。在第4.12节讨论异构链表时,使用了这种特性。对于那些使用C语言或者Pascal语言讲授数据结构的教师,将会发现本书在算法和计算时间分析方面进行了深入讨论。另外,我们在本书的章节组织方面也尽量使本书的风格与较早出版的相关书籍保持一致。
致谢(第1版)
我们向在本书出版过程中给予我们帮助的所有人致以真诚的谢意。感谢在田纳西大学和田纳西航空学院学习高级数据结构课程的学生们,他们发现了原稿中的一些疏忽之处。我们尤其感谢乔治·布拉斯特(George Blust)和埃捷尤蒂·戴维(Anjanjyoti Das)对本书作出的评价意见。我们也要向凯廷·道斯(Ketan Doshi) (Remedy集团)、德诺克·伊利(Derek Ealy) 、麦瑞·路彼兹(Mario Lopez)教授(丹佛大学)、苏艾·塞蒂(Sudhir Shetty) (Arrowsmith科技有限公司)和露丝·唐(Rose Tsang) (明尼苏达大学)表示感谢,他们对原稿进行了修订,并提出了一些有价值的建议。我们还要感谢英·苏(Ying Shu) (南加里佛尼亚大学)在GNU C++编译器上对程序进行的测试工作。我们特别感谢巴布诺(Barbara)和阿特·富利德门(Art Friedman) ,他们作为本书最早的出版人,在本书的孕育之初给予了我们诚挚的支持。我们要特别感谢裴尼·霍尔(Penny Hull)副主席,她热情的帮助加快了本书出版的进程。
致谢(第2版)
我们感谢纳瑞·哥汗尼(Narain Gehani)博士,他对原稿的改进提出了一些建议。

埃利斯·霍罗维兹(Ellis Horowitz)
萨尔塔·萨尼(Sartaj Sahni)
荻尼斯·梅塔(Dinesh Mehta)
目录
目 录
第1章 基本概念1
1.1 概述:系统生命周期1
1.2 面向对象的程序设计3
1.2.1 算法分解与面向对象分解3
1.2.2 基本定义和面向对象编程的概念3
1.2.3 程序设计语言的演化和C++语言历史4
1.3 数据抽象和封装4
1.4 C++语言基础8
1.4.1 C++程序的组织结构8
1.4.2 C++语言的作用域9
1.4.3 C++的语句与操作符10
1.4.4 C++语言中的数据声明10
1.4.5 C++语言的注释11
1.4.6 C++语言的输入输出11
1.4.7 C++语言的函数13
1.4.8 C++语言的参数传递13
1.4.9 C++语言的函数名重载14
1.4.10 内联函数14
1.4.11 C++语言的动态内存分配15
1.4.12 例外15
1.5 算法规范17
1.5.1 概述17
1.5.2 递归算法20
1.6 标准模板库24
1.7 性能分析和度量27
1.7.1 性能分析28
1.7.2 性能度量45
1.7.3 测试数据的生成50
1.8 参考文献和推荐读物54第2章 数组55
2.1 抽象数据类型和C++类55
2.1.1 C++类介绍55
2.1.2 C++语言中的数据抽象和封装56
2.1.3 声明类对象和调用成员函数56
2.1.4 特别类操作57
2.1.5 其他主题60
2.1.6 ADT和C++类60
2.2 将数组作为一种抽象数据类型62
2.3 多项式抽象数据类型64
2.3.1 多项式的表示65
2.3.2 多项式的加法67
2.4 稀疏矩阵71
2.4.1 绪论71
2.4.2 稀疏矩阵的表示法72
2.4.3 转置一个矩阵73
2.4.4 矩阵的乘法76
2.5 多维数组的表示81
2.6 字符串抽象数据类型84
2.6.1 一种简单的字符串模式匹配算法85
2.6.2 字符串模式匹配: Knuth-Morris-Pratt算法85
2.7 参考文献和推荐读物89
2.8 附加习题89数据结构基础(C++语言版)(第2版)目录第3章 栈和队列94
3.1 C++模板94
3.1.1 模板函数94
3.1.2 用模板表示容器类96
3.2 栈的抽象数据类型99
3.3 队列抽象数据类型103
3.4 C++中的子类型和继承109
3.5 一个迷宫问题112
3.6 计算表达式116
3.6.1 表达式116
3.6.2 后缀表达式118
3.6.3 中缀表达式转换成后缀表达式119
3.7 附加习题122第4章 链表124
4.1 单链表和链124
4.2 用C++语言表示链表126
4.2.1 在C++语言中定义结点126
4.2.2 用C++语言设计一个链表类127
4.2.3 C++语言中的指针操作130
4.2.4 链表的控制操作131
4.3 链的模板类134
4.3.1 用模板实现链表134
4.3.2 链表迭代器135
4.3.3 链表操作138
4.3.4 类的重用140
4.4 循环链表141
4.5 可用空间链表143
4.6 链式栈和链式队列144
4.7 多项式146
4.7.1 多项式的表示146
4.7.2 多项式相加147
4.7.3 用循环链表表示多项式150
4.8 等价类152
4.9 稀疏矩阵157
4.9.1 稀疏矩阵的表示157
4.9.2 稀疏矩阵的输入159
4.9.3 删除稀疏矩阵160
4.10 双向链表162
4.11 广义表165
4.11.1 广义表的表示165
4.11.2 表的递归算法168
4.11.3 引用计数、共享和递归表171第5章 树176
5.1 概述176
5.1.1 术语表176
5.1.2 树的表示178
5.2 二叉树180
5.2.1 抽象数据类型180
5.2.2 二叉树的性质181
5.2.3 二叉树的表示183
5.3 二叉树的遍历和迭代程序185
5.3.1 概述185
5.3.2 中序遍历185
5.3.3 先序遍历187
5.3.4 后序遍历187
5.3.5 迭代中序遍历188
5.3.6 层次遍历190
5.3.7 不使用栈的遍历191
5.4 补充的二叉树操作193
5.4.1 复制二叉树193
5.4.2 检测相等193
5.4.3 满足性问题194
5.5 线索二叉树196
5.5.1 线索196
5.5.2 线索二叉树的中序遍历197
5.5.3 在线索二叉树上插入一个结点198
5.6 堆200
5.6.1 优先队列200
5.6.2 大顶堆的定义201
5.6.3 大顶堆的插入202
5.6.4 大顶堆的删除203
5.7 二叉查找树205
5.7.1 定义205
5.7.2 二叉查找树的查找206
5.7.3 二叉查找树的插入208
5.7.4 二叉查找树的删除209
5.7.5 二叉树的连接和分裂210
5.7.6 二叉查找树的高度212
5.8 选择树213
5.8.1 概述213
5.8.2 胜者树213
5.8.3 败者树214
5.9 森林215
5.9.1 将森林转换成二叉树215
5.9.2 森林的遍历216
5.10 离散集合表示217
5.10.1 概述217
5.10.2 并和查找操作217
5.10.3 等价类的应用223
5.11 二叉树计数225
5.11.1 不同的二叉树225
5.11.2 栈排列226
5.11.3 矩阵相乘227
5.11.4 不同二叉树的个数228
5.12 参考文献和推荐读物229第6章 图230
6.1 图的抽象数据类型230
6.1.1 概述230
6.1.2 定义231
6.1.3 图的表示234
6.2 图的基本操作240
6.2.1 深度优先搜索240
6.2.2 广度优先搜索241
6.2.3 连通分量242
6.2.4 生成树243
6.2.5 重连通分量244
6.3 最小代价生成树248
6.3.1 克鲁斯卡尔算法248
6.3.2 普里姆算法251
6.3.3 索林算法252
6.4 最短路径和传递闭包253
6.4.1 单源/多目标: 非负权值253
6.4.2 单源/多目标: 任意权值257
6.4.3 多源最短路径259
6.4.4 传递闭包260
6.5 活动网络263
6.5.1 顶点表示活动的网络(AOV网)263
6.5.2 用边表示活动的网络(AOE网)267
6.5.3 事件最早发生时间的计算269
6.5.4 事件最迟发生时间的计算269
6.6 参考文献和推荐读物272
6.7 附加习题273第7章 排序275
7.1 目的275
7.2 插入排序278
7.3 快速排序280
7.4 排序算法能够多快283
7.5 归并排序284
7.5.1 归并284
7.5.2 迭代归并285
7.5.3 递归归并287
7.6 堆排序289
7.7 多关键字排序292
7.8 链和列表排序295
7.9 内部排序总结302
7.10 外部排序306
7.10.1 概述306
7.10.2 k路归并308
7.10.3 并行操作的缓存处理309
7.10.4 顺串产生313
7.10.5 顺串的最佳归并315
7.11 参考文献和推荐读物318第8章 散列319
8.1 绪论319
8.2 静态散列319
8.2.1 哈希表319
8.2.2 哈希函数320
8.2.3 安全哈希函数323
8.2.4 溢出处理325
8.2.5 溢出技术的理论分析329
8.3 动态散列331
8.3.1 动态散列的目的331
8.3.2 使用目录的动态散列332
8.3.3 不使用目录的动态散列334
8.4 布隆过滤器335
8.4.1 勘误文件的应用335
8.4.2 设计布隆过滤器337
8.5 参考文献和推荐读物338第9章 优先队列340
9.1 单端和双端优先队列340
9.2 左偏树342
9.2.1 高度左偏树342
9.2.2 重量左偏树346
9.3 二项式堆349
9.3.1 代价分摊349
9.3.2 二项式堆的定义350
9.3.3 二项式堆的插入操作351
9.3.4 合并两个二项式堆352
9.3.5 删除最小元素352
9.3.6 分析354
9.4 斐波那契堆356
9.4.1 定义356
9.4.2 从斐波那契堆中删除元素356
9.4.3 减小键值357
9.4.4 级联剪切357
9.4.5 分析358
9.4.6 在最短路径问题上的应用360
9.5 配对堆361
9.5.1 定义361
9.5.2 合并和插入操作362
9.5.3 减小键值363
9.5.4 删除最小元素363
9.5.5 删除任意元素365
9.5.6 实现问题365
9.5.7 复杂度366
9.6 对称最小-最大堆366
9.6.1 定义及性质366
9.6.2 SMMH的表示367
9.6.3 插入操作368
9.6.4 删除操作371
9.7 区间堆373
9.7.1 定义及性质373
9.7.2 区间堆的插入操作374
9.7.3 删除最小元素376
9.7.4 初始化区间堆377
9.7.5 区间堆操作的复杂度377
9.7.6 互补范围搜索问题377
9.8 参考文献和推荐读物379第10章 高效二叉查找树382
10.1 最优二叉查找树382
10.2 AVL树388
10.3 红黑树398
10.3.1 定义398
10.3.2 红黑树的表示399
10.3.3 查找400
10.3.4 插入400
10.3.5 删除403
10.3.6 红黑树的合并403
10.3.7 红黑树的分裂404
10.4 伸展树406
10.4.1 自底向上的伸展树406
10.4.2 自顶向下的伸展树409
10.5 参考文献和推荐读物413第11章 多路查找树415
11.1 m路查找树415
11.1.1 定义和性质415
11.1.2 对m路查找树进行查找416
11.2 B-树417
11.2.1 定义和性质417
11.2.2 B-树的元素个数417
11.2.3 插入418
11.2.4 删除420
11.3 B+树427
11.3.1 定义427
11.3.2 查找428
11.3.3 插入428
11.3.4 删除429
11.4 参考文献和推荐读物433第12章 数字查找结构434
12.1 数字查找树434
12.1.1 定义434
12.1.2 查找、插入和删除434
12.2 二叉Trie树和Patricia树435
12.2.1 二叉Trie树435
12.2.2 压缩二叉Trie树436
12.2.3 Patricia树436
12.3 多路Trie树440
12.3.1 定义440
12.3.2 查找Trie树442
12.3.3 抽样策略442
12.3.4 插入Trie树444
12.3.5 从Trie树中删除444
12.3.6 不同长度的关键字444
12.3.7 Trie树的高度445
12.3.8 空间需求与其他结点结构445
12.3.9 前缀查找和应用448
12.3.10 压缩Trie树449
12.3.11 带跳过字段的压缩Trie树451
12.3.12 带标号边的压缩Trie树452
12.3.13 压缩Trie树需要的空间453
12.4 后缀树454
12.4.1 你是否见过这个字符串454
12.4.2 后缀树数据结构455
12.4.3 查找子串(查找后缀树)457
12.4.4 后缀树上的其他技巧458
12.5 Trie树和Internet包转发460
12.5.1 IP路由460
12.5.2 1-比特Trie树460
12.5.3 固定跨度Trie树461
12.5.4 可变跨度Trie树463
12.6 参考文献和推荐读物465术语表466
Copyright(C)清华大学出版社有限公司,All Rights Reserved 京ICP备10035462号 联系我们