计算机类专业教育 > 数据结构与算法类
数据结构 （第四版）
书号：9787113214173 套系名称：普通高等教育“十一五”国家级规划教材/普通高等院校计算机类专业规划教材·精品系列
作者：刘振鹏 王苗 赵红 出版日期：2016-02-01
定价：39.00 页码 / 开本：292 /16
策划编辑：周海燕 责任编辑：周海燕 彭立辉
适用专业：无 适用层次：高等院校
最新印刷时间：
资源下载
教学课件
教学素材(暂无)
习题答案(暂无)
教学案例(暂无)
教学设计(暂无)
教学视频(暂无)
内容简介
前言
目录
作者介绍
图书特色
本书根据教育部高等学校计算机科学与技术教学指导委员会关于“数据结构”课程的指导性大纲编写而成，系统介绍了线性结构、树形结构、图形结构中的数据表示和处理方法，以及查找、排序这两种重要的数据处理技术；阐明了各种数据结构内在的逻辑关系，探讨了它们在计算机中的存储表示，以及定义在这些数据结构上的运算和算法实现，并对算法的效率进行了简明的分析。
本书内容丰富、结构清晰，既注重基本原理，又重视算法实现，全书算法采用C++语言描述，并加以详细的注释，可读性好、实用性强。每章均附有丰富的课后习题，便于学生巩固所学知识。
本书适合作为高等院校计算机、通信工程、电子工程、信息管理等专业的教材，也可供相关证书考试、考研或从事计算机应用与工程工作的科技工作者参考。无
第 1 章 绪论......................................................................................................... 1
1.1 数据结构的概念.......................................................................................... 1
1.1.1 为什么要学习数据结构.................................................................... 2
1.1.2 相关概念和术语............................................................................... 4
1.1.3 数据结构课程的内容........................................................................ 6
1.2 数据类型和抽象数据类型............................................................................ 7
1.2.1 数据类型.......................................................................................... 7
1.2.2 抽象数据类型................................................................................... 8
1.3 算法和算法分析.......................................................................................... 9
1.3.1 算法特性.......................................................................................... 9
1.3.2 算法描述.........................................................................................10
1.3.3 算法性能分析与度量.......................................................................10
小结...................................................................................................................13
习题...................................................................................................................13
第 2 章 线性表 ................................................................................................... 16
2.1 线性表的逻辑结构......................................................................................16
2.1.1 线性表的定义..................................................................................16
2.1.2 线性表的基本操作..........................................................................17
2.2 线性表的顺序存储及运算实现...................................................................17
2.2.1 顺序表.............................................................................................18
2.2.2 顺序表上基本运算的实现...............................................................19
2.2.3 顺序表应用举例..............................................................................22
2.3 线性表的链式存储和运算实现...................................................................24
2.3.1 单链表.............................................................................................24
2.3.2 单链表上基本运算的实现...............................................................26
2.3.3 循环链表.........................................................................................31
2.3.4 双向链表.........................................................................................32
2.3.5 静态链表.........................................................................................34
2.3.6 间接寻址.........................................................................................35
2.3.7 单链表应用举例..............................................................................35
2.4 顺序表和链表的比较..................................................................................37
小结...................................................................................................................38
习题...................................................................................................................38
数据结构 第四版
2
第 3 章 栈和队列................................................................................................ 41
3.1 栈...............................................................................................................41
3.1.1 栈的定义及基本运算.......................................................................41
3.1.2 栈的存储实现和运算实现...............................................................42
3.1.3 栈的应用举例..................................................................................45
3.2 队列............................................................................................................54
3.2.1 队列的定义及基本运算...................................................................55
3.2.2 队列的存储实现及运算实现...........................................................55
3.2.3 队列应用举例..................................................................................60
小结...................................................................................................................62
习题...................................................................................................................63
第 4 章 串 .......................................................................................................... 65
4.1 串及其基本运算.........................................................................................65
4.1.1 串的基本概念..................................................................................65
4.1.2 串的基本运算..................................................................................66
4.2 串的定长顺序存储及基本运算...................................................................66
4.2.1 串的定长顺序存储..........................................................................67
4.2.2 定长顺序串的基本运算...................................................................67
4.2.3 模式匹配.........................................................................................69
4.3 串的堆存储结构.........................................................................................74
4.3.1 串名的存储映像..............................................................................74
4.3.2 堆存储结构.....................................................................................75
4.3.3 基于堆结构的串的基本运算实现....................................................75
小结...................................................................................................................77
习题...................................................................................................................77
第 5 章 数组和广义表......................................................................................... 79
5.1 数组............................................................................................................79
5.1.1 一维数组.........................................................................................79
5.1.2 多维数组.........................................................................................79
5.1.3 数组的内存映像..............................................................................80
5.2 特殊矩阵的压缩存储..................................................................................83
5.2.1 对称矩阵.........................................................................................83
5.2.2 三角矩阵.........................................................................................84
5.2.3 带状矩阵.........................................................................................85
5.3 稀疏矩阵....................................................................................................86
5.3.1 稀疏矩阵的三元组表存储...............................................................86
5.3.2 稀疏矩阵的十字链表存储...............................................................91
5.4 广义表........................................................................................................96
目 录
3
5.4.1 广义表的定义和基本运算...............................................................96
5.4.2 广义表的存储..................................................................................97
5.4.3 广义表基本操作的实现.................................................................100
小结.................................................................................................................102
习题.................................................................................................................103
第 6 章 二叉树 ................................................................................................. 105
6.1 二叉树的定义与性质................................................................................105
6.1.1 二叉树的基本概念........................................................................105
6.1.2 二叉树的主要性质........................................................................107
6.2 二叉树的基本操作与存储实现.................................................................109
6.2.1 二叉树的存储................................................................................109
6.2.2 二叉树的基本操作及实现............................................................. 111
6.3 二叉树的遍历...........................................................................................114
6.3.1 二叉树的遍历方法及递归实现......................................................114
6.3.2 二叉树遍历的非递归实现.............................................................116
6.3.3 由遍历序列恢复二叉树.................................................................119
6.3.4 不用栈的二叉树遍历的非递归方法..............................................121
6.4 线索二叉树...............................................................................................121
6.4.1 线索二叉树的定义及结构.............................................................122
6.4.2 线索二叉树的基本操作实现.........................................................123
6.5 二叉树的应用举例....................................................................................129
6.5.1 查找数据元素................................................................................129
6.5.2 统计给定二叉树中叶结点的数目..................................................129
6.5.3 创建二叉树的二叉链表存储.........................................................130
6.5.4 表达式运算...................................................................................131
6.6 哈夫曼树..................................................................................................131
6.6.1 问题引入.......................................................................................131
6.6.2 哈夫曼树的基本概念及其构造方法..............................................132
6.6.3 哈夫曼树的构造算法.....................................................................134
6.6.4 哈夫曼编码...................................................................................135
小结.................................................................................................................138
习题.................................................................................................................138
第 7 章 树与森林.............................................................................................. 141
7.1 树的概念与表示.......................................................................................141
7.1.1 树的定义及相关术语.....................................................................141
7.1.2 树的表示.......................................................................................143
7.2 树的基本操作与存储................................................................................143
7.2.1 树的基本操作................................................................................144
7.2.2 树的存储结构................................................................................144
数据结构 第四版
4
7.3 树、森林与二叉树的转换.........................................................................148
7.3.1 树转换为二叉树............................................................................148
7.3.2 森林转换为二叉树........................................................................148
7.3.3 二叉树转换为树和森林.................................................................149
7.4 树和森林的遍历.......................................................................................150
7.4.1 树的遍历.......................................................................................150
7.4.2 森林的遍历...................................................................................151
7.5 树的应用举例...........................................................................................151
7.5.1 判定树...........................................................................................151
7.5.2 集合的表示...................................................................................152
7.5.3 等价问题.......................................................................................154
小结.................................................................................................................155
习题.................................................................................................................156
第 8 章 图 ........................................................................................................ 158
8.1 图的基本概念...........................................................................................158
8.1.1 图的定义和术语............................................................................158
8.1.2 图的基本操作及类定义.................................................................161
8.2 图的存储结构...........................................................................................163
8.2.1 邻接矩阵.......................................................................................163
8.2.2 邻接表...........................................................................................165
8.2.3 十字链表.......................................................................................167
8.2.4 邻接多重表...................................................................................170
8.3 图的遍历..................................................................................................171
8.3.1 深度优先搜索................................................................................172
8.3.2 广度优先搜索................................................................................173
8.3.3 应用图的遍历判定图的连通性......................................................175
8.3.4 生成树和生成森林........................................................................176
8.4 最小生成树...............................................................................................177
8.4.1 最小生成树的概念........................................................................178
8.4.2 普里姆（Prim）算法.....................................................................179
8.4.3 克鲁斯卡尔（Kruskal）算法.........................................................181
8.5 最短路径..................................................................................................183
8.5.1 迪杰斯特拉（Dijkstra）算法........................................................183
8.5.2 弗洛伊德（Floyd）算法................................................................187
8.6 拓扑排序与关键路径................................................................................188
8.6.1 有向无环图的概念........................................................................189
8.6.2 拓扑排序.......................................................................................190
8.6.3 关键路径.......................................................................................194
小结.................................................................................................................199
目 录
5
习题.................................................................................................................200
第 9 章 查找..................................................................................................... 203
9.1 基本概念..................................................................................................203
9.1.1 相关术语.......................................................................................203
9.1.2 查找表结构...................................................................................204
9.2 静态查找表...............................................................................................205
9.2.1 顺序查找.......................................................................................205
9.2.2 折半查找.......................................................................................206
9.2.3 插值查找和斐波那契查找.............................................................209
9.2.4 分块查找.......................................................................................210
9.3 二叉排序树...............................................................................................211
9.3.1 二叉排序树的定义........................................................................211
9.3.2 二叉排序树的查找过程.................................................................211
9.3.3 二叉排序树的插入操作.................................................................212
9.3.4 二叉排序树的删除操作.................................................................213
9.4 平衡二叉树...............................................................................................216
9.4.1 平衡二叉树的定义........................................................................216
9.4.2 平衡二叉树的平衡化旋转.............................................................217
9.4.3 平衡二叉树的插入........................................................................219
9.4.4 平衡二叉树的查找性能分析.........................................................223
9.5 B树和B
+树..............................................................................................224
9.5.1 B树的定义....................................................................................224
9.5.2 B树的查找....................................................................................225
9.5.3 B树的插入....................................................................................226
9.5.4 B树的删除....................................................................................229
9.5.5 B
+树..............................................................................................230
9.6 哈希表查找...............................................................................................231
9.6.1 哈希表与哈希方法........................................................................231
9.6.2 常用的哈希函数............................................................................232
9.6.3 处理冲突的方法............................................................................234
9.6.4 哈希表的查找性能分析.................................................................236
小结.................................................................................................................237
习题.................................................................................................................238
第 10 章 排序................................................................................................... 241
10.1 排序的基本概念.....................................................................................241
10.1.1 相关术语.....................................................................................241
10.1.2 排序的时间开销..........................................................................242
10.2 插入排序................................................................................................242
10.2.1 直接插入排序..............................................................................242
数据结构 第四版
6
10.2.2 折半插入排序..............................................................................243
10.2.3 表插入排序.................................................................................244
10.2.4 希尔排序.....................................................................................247
10.3 交换排序................................................................................................248
10.3.1 冒泡排序.....................................................................................248
10.3.2 快速排序.....................................................................................249
10.4 选择排序................................................................................................252
10.4.1 简单选择排序..............................................................................252
10.4.2 树形选择排序..............................................................................253
10.4.3 堆排序.........................................................................................254
10.5 归并排序................................................................................................256
10.6 基数排序................................................................................................258
10.6.1 多关键码排序..............................................................................258
10.6.2 链式基数排序..............................................................................259
10.7 外排序....................................................................................................262
10.7.1 外排序的方法..............................................................................262
10.7.2 多路平衡归并的实现...................................................................263
小结.................................................................................................................266
习题.................................................................................................................267
附录................................................................................................................... 271
附录A 线性结构............................................................................................271
附录B 树形结构............................................................................................273
附录C 图形结构............................................................................................274
附录D 查找和排序........................................................................................276
参考文献............................................................................................................ 278本书为普通高等教育“十一五”国家级规划教材。本书根据教育部高等学校计算机科学与技术教学指导委员会关于“数据结构”课程的教学基本要求进行编写。