第1章 绪论 1
1.1引言 1
1.2数据结构的主要概念与术语 2
1.3抽象数据类型的概念与描述 4
1.3.1基本数据类型的概念 4
1.3.2抽象数据类型 5
1.4算法的度量 8
1.4.1算法的定义 8
1.4.2算法效率的度量 9
1.5面向对象C＋＋描述工具简介 11
1.5.1函数的定义格式 11
1.5.2函数模板 11
1.5.3类的定义 12
小结 16
习题 17
第2章 线性表 18
2.1案例引入及分析 18
2.1.1学生基本信息管理 18
2.1.2线性表的定义 18
2.1.3线性表的存储结构 20
2.2学生基本信息管理之顺序表的实现 22
2.2.1学生基本信息管理之顺序表类定义 22
2.2.2学生基本信息管理之顺序表操作实现 23
2.2.3学生基本信息管理之顺序表的主程序的实现 28
2.2.4顺序表的其他操作 30
2.3学生基本信息管理之单链表实现 31
2.3.1学生基本信息管理之单链表类定义 32
2.3.2学生基本信息管理之单链表操作实现 32
2.3.3学生基本信息管理之单链表的主程序的实现 40
2.3.4单链表的其他操作 42
2.4算法分析 44
2.5循环链表和双向链表 46
2.5.1循环链表 46
2.5.2双向链表 47
2.5.3双向链表的类定义 47
2.6静态链表 51
2.7顺序结构与链表结构的比较 54
小结 54
习题 55
第3章 堆栈 58
3.1案例引入及分析 58
3.1.1提交批改作业 58
3.1.2堆栈的定义 58
3.1.3堆栈的存储结构 59
3.2提交批改作业的顺序实现 64
3.3提交批改作业的链式实现 65
3.4算法分析 67
3.5堆栈的其他应用 67
3.5.1堆栈与递归的实现 67
3.5.2表达式求值 69
3.5.3背包问题 72
小结 75
习题 75
第4章 队列 77
4.1案例的引入及分析 77
4.1.1看病排队候诊 77
4.1.2队列的定义 77
4.1.3队列的存储结构 78
4.2看病排队候诊的顺序实现 83
4.3看病排队候诊的链式实现 85
4.4算法分析 87
4.5队列的其他应用 87
4.5.1二进制数转换为十进制数 87
4.5.2十进制数转换为二进制数 88
小结 89
习题 90
第5章 串 91
5.1案例引入及分析 91
5.1.1大整数计算器 91
5.1.2串的定义 91
5.1.3串的存储结构 93
5.2大整数计算器的顺序实现 97
5.3大整数计算器的链式实现 99
5.4算法分析 101
5.5串的其他应用 101
5.5.1简单模式匹配 101
5.5.2 KMP模式匹配 102
小结 106
习题 106
第6章 广义表和数组 108
6.1案例引入及分析 108
6.1.1本科生导师制问题 108
6.1.2广义表的定义 108
6.1.3广义表的存储结构 110
6.2本科生导师制问题的实现 111
6.2.1实现内容 111
6.2.2实现过程 112
6.3数组 120
6.3.1数组的定义 120
6.3.2数组的存储结构 122
6.4矩阵的压缩存储 123
6.4.1特殊矩阵的压缩存储 123
6.4.2稀疏矩阵的压缩存储 124
小结 136
习题 136
第7章 树和二叉树 139
7.1案例引入及分析 139
7.1.1家谱管理 139
7.1.2树和二叉树的定义 140
7.1.3树和二叉树的存储结构 144
7.1.4树与二叉树的转换 149
7.1.5森林与二叉树的转换 151
7.1.6树与森林的遍历 151
7.2家谱管理的实现 152
7.3遍历二叉树 154
7.3.1前序遍历 154
7.3.2中序遍历 155
7.3.3后序遍历 156
7.3.4按层次遍历 156
7.4线索二叉树 157
7.5树的其他应用——哈夫曼树及编码 161
7.5.1哈夫曼树 161
7.5.2哈夫曼编码 162
小结 163
习题 164
第8章 图 165
8.1图的基本概念与术语 165
8.1.1图的基本概念 165
8.1.2图的基本术语 166
8.1.3抽象数据类型 169
8.2图的存储结构 171
8.2.1邻接矩阵 171
8.2.2邻接表 173
8.2.3双链式存储结构 174
8.3图的ADT设计与实现 179
8.4图的遍历 180
8.4.1深度优先搜索 181
8.4.2广度优先搜索 183
8.5图的连通性 184
8.5.1无向图的连通分量和生成树 184
8.5.2有向图的强连通分量 185
8.5.3最小生成树 186
8.6最短路径 192
8.6.1单源最短路径 192
8.6.2任意顶点间的最短路径 196
8.7有向无环图及其应用 196
8.7.1拓扑排序 196
8.7.2关键路径 199
小结 202
习题 202
第9章 查找 207
9.1查找的基本概念 207
9.2静态查找表 208
9.2.1顺序查找表 209
9.2.2有序表的查找 209
9.2.3静态索引顺序表的查找 212
9.3动态查找表 213
9.3.1二叉排序树和平衡二叉树 214
9.3.2 B-树和B＋树 226
9.4哈希表 233
9.4.1哈希表与哈希函数 233
9.4.2哈希函数的构造方法 234
9.4.3解决冲突的方法 236
9.4.4哈希表的查找及其效率分析 239
小结 241
习题 242
第10章 排序 245
10.1排序的基本概念 245
10.2插入排序 246
10.2.1直接插入排序 246
10.2.2折半插入排序 247
10.2.3 2—路插入排序 249
10.2.4表插入排序 250
10.2.5希尔排序 251
10.3交换排序 252
10.3.1冒泡排序 252
10.3.2快速排序 253
10.4选择排序 256
10.4.1简单选择排序 256
10.4.2堆排序 257
10.5二路归并排序 259
10.6基数排序 260
10.6.1多关键字排序 260
10.6.2链式基数排序 260
10.6.3各种排序方法的比较 265
小结 266
习题 266