目录



第1章绪论/1
1.1数据结构的起源与发展1
1.2基本概念和术语3
1.3理解数据结构4
1.4数据的逻辑结构和存储结构5
1.4.1逻辑结构6
1.4.2存储结构7
1.5数据类型和抽象数据类型9
1.5.1数据类型9
1.5.2抽象数据类型10
1.6算法与算法效率分析11
1.6.1数据结构与算法的关系11
1.6.2算法的定义12
1.6.3算法的5大特性12
1.6.4算法设计的要求13
1.6.5算法效率分析14
1.6.6算法的时间复杂度14
1.6.7算法存储空间需求19
1.7预备知识20
1.7.1C函数20
1.7.2自定义数据类型名21
1.8本章小结23
1.9习题与实验23
第2章线性表/26
2.1问题的提出27
2.2线性表28
2.2.1线性表的定义28
2.2.2线性表的顺序存储结构31
2.2.3顺序表的基本操作实现33
2.2.4线性表的链式存储结构42
2.2.5单向链表的基本操作实现44
2.2.6线性表的两种存储结构的区别55
2.3案例实现56
2.3.1基于顺序表的新生成绩管理系统56
2.3.2基于单向链表的新生成绩管理系统60
2.4其他形式的链表61
2.4.1单向循环链表的定义61
2.4.2单向循环链表的基本操作实现63
2.4.3双向循环链表的定义65
2.4.4双向循环链表的基本操作实现66
2.5线性表的应用68
2.5.1两个线性表的合并68
2.5.2一元多项式的应用71
2.6字符串匹配算法75
2.6.1串的基本概念75
2.6.2串的模式匹配算法75
2.7本章小结83
2.8习题与实验84
新编数据结构及算法教程（第2版）目录第3章栈与队列/88
3.1问题的提出88
3.2栈90
3.2.1栈的定义90
3.2.2栈的顺序存储结构91
3.2.3顺序栈的基本操作实现93
3.2.4栈的链式存储结构97
3.2.5链栈的基本操作实现97
3.2.6栈的两种存储结构的区别101
3.2.7案例实现: 基于栈的括号匹配101
3.3栈的应用103
3.3.1表达式求值103
3.3.2栈与递归109
3.4队列117
3.4.1队列的定义117
3.4.2队列的顺序存储结构119
3.4.3循环队列的基本操作实现121
3.4.4队列的链式存储结构125
3.4.5链队列的基本操作实现126
3.4.6队列的两种存储结构的区别130
3.4.7案例实现: 基于队列的医院挂号模拟系统130
3.5队列的应用132
3.6共用栈和双队列138
3.6.1共用栈138
3.6.2双端队列140
3.7本章小结140
3.8习题与实验141
第4章数组与广义表/146
4.1多维数组146
4.1.1数组的逻辑结构146
4.1.2数组的内存映像147
4.2特殊矩阵的压缩存储149
4.2.1对称矩阵150
4.2.2三角矩阵151
4.2.3带状矩阵152
4.3稀疏矩阵153
4.3.1稀疏矩阵的三元组表存储153
4.3.2稀疏矩阵的十字链表存储159
4.4广义表164
4.4.1广义表的定义和基本运算164
4.4.2广义表的存储166
4.4.3广义表基本操作的实现169
4.5本章小结171
4.6习题与实验171
第5章树和二叉树/174
5.1问题的提出175
5.2树的定义和基本术语176
5.2.1树的递归定义176
5.2.2树的基本术语176
5.2.3树的表示177
5.2.4树的抽象数据类型描述179
5.3二叉树及其应用179
5.3.1二叉树的定义179
5.3.2二叉树的性质181
5.3.3二叉树的抽象数据类型183
5.3.4二叉树的存储结构185
5.3.5二叉树的遍历188
5.3.6二叉树遍历的递归算法188
5.3.7二叉树遍历的非递归算法190
5.3.8二叉树的层次遍历算法197
5.3.9二叉树遍历算法的应用199
5.3.10案例实现: 基于表达式二叉树的动态表达式计算214
5.4线索二叉树215
5.4.1线索二叉树的定义215
5.4.2线索二叉树的基本操作实现217
5.4.3基于中序线索二叉树的遍历算法223
5.5树、森林与二叉树的转换及其应用224
5.5.1树、森林与二叉树的转换224
5.5.2树的存储结构225
5.5.3树的简单应用230
5.5.4树和森林的遍历237
5.5.5案例实现: 基于树结构的行政机构管理239
5.6哈夫曼树及其应用241
5.6.1最优二叉树——哈夫曼树241
5.6.2哈夫曼树及哈夫曼编码的构建算法245
5.7本章小结250
5.8习题与实验250
第6章图/255
6.1问题的提出256
6.2图的定义和基本术语257
6.2.1图的定义257
6.2.2图的基本术语257
6.2.3图的分类258
6.2.4图的抽象数据类型定义260
6.3图的存储结构262
6.3.1图的邻接矩阵表示262
6.3.2图的邻接表表示266
6.3.3有向图的十字链表表示270
6.3.4无向图的邻接多重表表示271
6.4图的遍历273
6.4.1连通图的深度优先搜索273
6.4.2连通图的广度优先搜索277
6.4.3非连通图的深度（广度）优先遍历279
6.4.4图的遍历算法应用279
6.5图的连通性286
6.5.1无向图的连通分量和生成树286
6.5.2求最小生成树的普里姆算法287
6.5.3求最小生成树的克鲁斯卡尔算法293
6.6最短路径298
6.6.1求图中从某个源点到其余各点的最短路径算法298
6.6.2求图中每一对顶点之间的最短路径算法307
6.7有向无环图及其应用312
6.7.1AOV网络及拓扑排序313
6.7.2AOE网络及关键路径316
6.8本章小结323
6.9习题与实验324
第7章查找表/330
7.1问题的提出330
7.2基本概念与描述331
7.2.1查找的基本概念331
7.2.2查找性能分析332
7.2.3数据类型描述332
7.3线性表查找333
7.3.1顺序查找333
7.3.2二分查找335
7.3.3分块查找339
7.3.4案例实现: 学生信息表查询341
7.4树表查找345
7.4.1二叉排序树345
7.4.2平衡二叉树354
7.4.3B树和B+树371
7.4.4案例实现: 基于二叉排序树的学生信息管理380
7.5哈希表385
7.5.1哈希表的概念385
7.5.2常用的哈希函数386
7.5.3处理冲突的方法389
7.5.4哈希表的查找及其性能分析393
7.6本章小结394
7.7习题与实验395
第8章排序/398
8.1问题的提出398
8.2基本概念399
8.3插入排序400
8.3.1直接插入排序401
8.3.2折半插入排序403
8.3.3希尔排序404
8.4交换排序405
8.4.1冒泡排序406
8.4.2快速排序407
8.5选择排序410
8.5.1简单选择排序410
8.5.2堆排序411
8.6归并排序416
8.7基数排序418
8.7.1多关键字排序418
8.7.2链式基数排序419
8.8案例实现: 学生成绩排序系统422
8.9各种内部排序方法的性能比较427
8.10本章小结428
8.11习题与实验428
附录A扩展思维/430
A.1人体网格模型的表示430
A.2图像分割431
A.2.1图像的表示431
A.2.2区域划分原理432
A.3仿真路网建模433
A.3.1路网定义及建模433
A.3.2路网建模结果435
A.4路径规划435
A.5购物推荐436
参考文献/438