《数据结构——C语言描述（第二版）（陈慧南）十一五》是2015年西安电子科技大学出版社出版的图书，作者是陈慧南。
基本介绍
- 书名：数据结构——C语言描述（第二版）（陈慧南）十一五
- 作者：陈慧南
- ISBN：978-7-5606-2226-2
- 定价：29.75元
- 出版社：西安电子科技大学出版社
- 出版时间：2015-02
内容简介
本书为普通高等教育“十一五”国家级规划教材。
本书保留经典数据结构知识，并引入伸展树和跳表等新内容，反映抽象、封装和信息隐蔽等现代软体设计理念，重视算法的时间和空间分析，包括搜寻和排序时间的下界分析。本书使用C语言描述，内容新旧取捨恰当，广度和深度适中。
本书为普通高等教育“十一五”国家级规划教材。
本书保留经典数据结构知识，并引入伸展树和跳表等新内容，反映抽象、封装和信息隐蔽等现代软体设计理念，重视算法的时间和空间分析，包括搜寻和排序时间的下界分析。本书使用C语言描述，内容新旧取捨恰当，广度和深度适中。
本书重视实践性和程式设计。书中算法都有完整的C程式，程式代码注释详细，结构清晰，构思精巧，所有程式都已在TC 2.01下编译通过并能正确运行。这些程式既是学习数据结构和算法的很好示例，也是很好的C程式设计示例。本书最后一章为实习指导和实习题，指导学生按软体工程学的方法设计算法、编写程式和书写文档。
本书结构严谨、内容深入浅出，配有大量的实例和图示，并有丰富的习题和实习题，易教易学。
本书可作为电气信息类、电子信息科学类、管理信息系统、电子商务、教育技术等相关专业数据结构课程的教材，也可供从事计算机软体和套用开发的工程技术人员参考。
本书配有《学习指导和习题解析》，由西安电子科技大学出版社同时出版。两者结合使用，学习效果更佳。
★本书配有电子教案，需要者可登录出版社网站，免费下载。
目录
第1章 概论 1
1.1 什幺是数据结构 1
1.1.1 基本概念 1
1.1.2 数据的逻辑结构 2
1.1.3 数据的存储结构 3
1.1.4 数据结构的运算 4
1.2 数据抽象和抽象数据类型 5
1.2.1 抽象、数据抽象和过程抽象 5
1.2.2 封装与信息隐蔽 5
1.2.3 数据类型和抽象数据类型 5
1.2.4 数据结构与抽象数据类型 6
1.3 描述数据结构 7
1.3.1 数据结构的规範 7
1.3.2 实现数据结构 8
1.4 算法和算法分析 9
1.4.1 算法及其性能标準 9
1.4.2 算法的时间複杂度 10
1.4.3 渐近时间複杂度 12
1.4.4 最坏、最好和平均情况时间複杂度 13
1.4.5 算法的空间複杂度 13
小结 14
习题1 14
第2章 数组和鍊表 16
2.1 结构与联合 16
2.1.1 结构 16
2.1.2 联合 17
2.2 数组 18
2.2.1 一维数组 18
2.2.2 二维数组 18
2.2.3 多维数组 20
2.3 鍊表 20
2.3.1 指针 20
2.3.2 单鍊表 24
2.3.3 带表头结点的单鍊表 30
2.3.4 循环鍊表 31
2.3.5 双向鍊表 31
小结 33
习题2 33
第3章 堆叠和伫列 35
3.1 堆叠 35
3.1.1 堆叠ADT 35
3.1.2 堆叠的顺序表示 36
3.1.3 堆叠的连结表示 38
3.2 伫列 39
3.2.1 伫列ADT 39
3.2.2 伫列的顺序表示 40
3.2.3 伫列的连结表示 43
*3.3 表达式的计算 43
3.3.1 表达式 43
3.3.2 中缀表达式转换为后缀表达式 44
3.3.3 计算后缀表达式的值 48
*3.4 递归和递归过程 50
3.4.1 递归的概念 50
3.4.2 递归的实现 51
*3.5 演示和测试 53
小结 55
习题3 55
第4章 线性表和数组ADT 57
4.1 线性表 57
4.1.1 线性表ADT 57
4.1.2 线性表的顺序表示 58
4.1.3 线性表的连结表示 61
4.1.4 两种存储表示的比较 65
*4.2 多项式的算术运算 65
4.2.1 多项式ADT 65
4.2.2 多项式的连结表示 66
4.2.3 多项式的输入和输出 67
4.2.4 多项式相加 69
4.3 数组作为抽象数据类型 71
4.4 特殊矩阵 72
4.4.1 对称矩阵 72
*4.4.2 带状矩阵 72
4.5 稀疏矩阵 74
4.5.1 稀疏矩阵ADT 74
4.5.2 稀疏矩阵的顺序表示 74
4.5.3 稀疏矩阵转置 76
*4.5.4 稀疏矩阵相乘 78
4.5.5 稀疏矩阵的正交鍊表表示 81
*4.5.6 建立正交鍊表 84
*4.5.7 列印正交鍊表 85
小结 86
习题4 86
第5章 字元串和广义表 88
5.1 字元串 88
5.1.1 字元串ADT 88
5.1.2 字元串的存储表示 89
5.1.3 简单模式匹配算法 90
*5.1.4 模式匹配的KMP算法 93
*5.2 广义表 97
5.2.1 广义表的概念 97
5.2.2 广义表ADT 98
5.2.3 广义表的存储表示 99
5.2.4 广义表的算法 100
小结 101
习题5 101
第6章 树 102
6.1 树的基本概念 102
6.1.1 树的定义 102
6.1.2 基本术语 103
6.2 二叉树 104
6.2.1 二叉树的定义和性质 104
6.2.2 二叉树ADT 106
6.2.3 二叉树的存储表示 107
6.2.4 二叉树的遍历 111
*6.2.5 二叉树遍历的非递归算法 114
*6.2.6 二叉树遍历的套用实例 117
*6.2.7 线索二叉树 119
6.3 树和森林 122
6.3.1 森林与二叉树的转换 122
6.3.2 树和森林的存储表示 123
6.3.3 树和森林的遍历 125
*6.4 堆和优先权伫列 126
6.4.1 堆 127
6.4.2 优先权伫列 129
6.5 哈夫曼树和哈夫曼编码 132
6.5.1 树的路径长度 132
6.5.2 哈夫曼树和哈夫曼算法 134
6.5.3 哈夫曼编码 136
*6.6 并查集和等价关係 137
6.6.1 并查集 137
6.6.2 并查集的实现 138
6.6.3 集合按等价关係分组 141
小结 142
习题6 142
第7章 集合和搜寻 145
7.1 集合及其表示 145
7.1.1 集合和搜寻 145
7.1.2 集合ADT 146
7.1.3 集合的表示 147
7.2 顺序搜寻 147
7.3 二分搜寻 149
7.3.1 对半搜寻 150
7.3.2 二叉判定树 151
*7.3.3 斐波那契搜寻 153
*7.4 搜寻算法的时间下界 154
小结 155
习题7 156
第8章 搜寻树 157
8.1 二叉搜寻树 157
8.1.1 二叉搜寻树的定义 157
8.1.2 二叉搜寻树的搜寻 157
8.1.3 二叉搜寻树的插入 158
8.1.4 二叉搜寻树的删除 160
*8.1.5 二叉搜寻树的高度 162
8.2 二叉平衡树 163
8.2.1 二叉平衡树的定义 163
8.2.2 二叉平衡树的平衡旋转 164
8.2.3 二叉平衡树的插入 170
8.2.4 二叉平衡树的删除 173
8.2.5 二叉平衡数的高度 176
8.3 B - 树 176
8.3.1 m叉搜寻树 176
8.3.2 B -树的定义 178
8.3.3 B -树的高度 179
8.3.4 B -树的搜寻 179
8.3.5 B -树的插入 179
8.3.6 B -树的删除 182
*8.4 键树 184
8.4.1 键树的定义 184
8.4.2 双链树 185
8.4.3 Trie树 186
*8.5 伸展树 187
小结 190
习题8 190
第9章 跳表和散列表 192
9.1 字典 192
*9.2 跳表 192
9.2.1 什幺是跳表 193
9.2.2 跳表的搜寻 196
9.2.3 跳表的插入 197
9.2.4 跳表的删除 198
9.3 散列表 199
9.3.1 散列技术 199
9.3.2 散列函式 200
9.3.3 解决冲突的拉链法 202
9.3.4 解决冲突的线性探查法 203
9.3.5 解决冲突的其他开地址法 207
9.3.6 性能分析 209
小结 209
习题9 210
第10章 图 211
10.1 图的基本概念 211
10.1.1 图的定义与术语 211
10.1.2 图ADT 214
10.2 图的存储结构 215
10.2.1 矩阵表示法 215
10.2.2 邻接表表示法 218
*10.2.3 多重表表示法 221
10.3 图的遍历 222
10.3.1 深度优先遍历 222
10.3.2 宽度优先遍历 224
10.4 拓扑排序和关键路径 226
10.4.1 拓扑排序 226
*10.4.2 关键路径 230
10.5 最小代价生成树 233
10.5.1 普里姆算法 234
*10.5.2 克鲁斯卡尔算法 235
*10.6 最短路径 237
10.6.1 单源最短路径 238
10.6.2 所有顶点之间的最短路径 241
小结 244
习题10 244
第11章 内排序 247
11.1 排序的基本概念 247
11.2 插入排序 248
11.2.1 直接插入排序 248
11.2.2* 希尔排序 252
11.3 交换排序 253
11.3.1 冒泡排序 253
11.3.2 快速排序 255
11.4 合併排序 260
11.4.1 两路合併排序 260
11.4.2 合併排序的叠代算法 260
*11.4.3 鍊表上的合併排序 262
11.5 选择排序 265
11.5.1 简单选择排序 266
*11.5.2 堆排序 267
*11.6 排序算法的时间下界 268
*11.7 基数排序 269
小结 273
习题11 273
第12章 档案和外排序 275
*12.1 辅助存储器简介 275
12.1.1 主存储器和辅助存储器 275
12.1.2 磁碟存储器 275
12.2 档案 277
12.2.1 档案的基本概念 277
12.2.2 档案的组织方式 277
12.2.3 C语言档案 281
12.3 档案的索引结构 282
12.3.1 静态索引结构 282
12.3.2 动态索引结构 283
*12.4 外排序 283
12.4.1 外排序的基本过程 284
12.4.2 初始游程的生成 284
12.4.3 多路合併 286
12.4.4 最佳合併树 288
小结 289
习题12 290
第13章 实习指导和实习题 291
13.1 实习目的和要求 291
13.1.1 实习目的 291
13.1.2 实习要求 291
13.2 实习步骤 292
13.3 实习报告 292
13.4 实习题 293
实习1 数组操作 293
实习2 鍊表操作 294
实习3 表达式计算 294
实习4 伫列运算和用户界面设计 295
实习5 线性表运算及套用 295
实习6 一元多项式的相加和相乘 295
实习7 对称矩阵的压缩存储 296
实习8 稀疏矩阵的三元组表 296
实习9 稀疏矩阵的正交鍊表 296
实习10 字元串运算和文本处理 297
实习11 二叉树的基本运算 297
实习12 哈夫曼编码和解码系统 298
实习13 B-树检索 298
实习14 散列表检索 299
实习15 图运算及其套用 299
实习16 内排序算法及其性能比较 300
实习17 外排序 300
13.5 实习报告範例 301
13.5.1 实习题：表达式计算 301
13.5.2 实习报告 301
附录A 软体工程概述 307
A.1 软体开发方法 307
A.2 软体文档写作 309
A.3 系统测试方法 310
附录B 专用名词中英文对照表 314
参考文献 320