第1章 绪论 1
1.1数据结构的基本概念 1
1.2抽象数据类型和软件构造方法 4
1.3算法和算法的时间复杂度 5
1.3.1算法 5
1.3.2算法设计目标 7
1.3.3算法时间效率的度量 7
习题1 12
第2章 线性表 14
2.1线性表抽象数据类型 14
2.1.1线性表的定义 14
2.1.2线性表抽象数据类型 15
2.2顺序表类 16
2.2.1顺序表的存储结构 16
2.2.2顺序表类定义 17
2.2.3顺序表类实现 17
2.2.4顺序表类方法的效率分析 21
2.2.5顺序表类应用举例 21
2.3单链表类 24
2.3.1单链表的结构 24
2.3.2结点类的定义和实现 27
2.3.3单链表类的定义和实现 28
2.3.4单链表操作的效率分析 33
2.3.5单链表应用举例 33
2.4循环单链表 34
2.5双向链表 35
2.6静态链表 36
2.7设计举例 37
2.7.1顺序表设计举例 37
2.7.2单链表算法设计举例 39
习题2 44
第3章 堆栈和队列 46
3.1堆栈 46
3.1.1堆栈的基本概念 46
3.1.2堆栈抽象数据类型 48
3.1.3顺序堆栈类 48
3.1.4链式堆栈类 50
3.2堆栈应用 54
3.2.1括号匹配问题 54
3.2.2表达式计算问题 57
3.3队列 62
3.3.1队列的基本概念 62
3.3.2队列抽象数据类型 62
3.3.3顺序队列 63
3.3.4顺序循环队列类 65
3.3.5链式队列类 67
3.3.6队列的应用 70
3.4优先级队列 72
3.4.1顺序优先级队列类 72
3.4.2优先级队列的应用 75
习题3 76
第4章 串 79
4.1串 79
4.1.1串及其基本概念 79
4.1.2串的抽象数据类型 80
4.1.3 C＋＋语言的串函数 81
4.2串的存储结构 84
4.2.1串的顺序存储结构 84
4.2.2串的链式存储结构 85
4.3动态数组实现的串类 85
4.3.1动态数组串类的定义 86
4.3.2构造函数和析构函数 87
4.3.3插入、删除和取子串成员函数 88
4.3.4常用操作符重载 90
4.3.5逻辑操作符重载 92
4.3.6测试 92
4.4串的模式匹配算法 95
4.4.1 Brute-Force算法 95
4.4.2 KMP算法 97
4.4.3 Brute-Force算法和KMP算法的运行效率比较 103
习题4 105
第5章 数组 107
5.1数组 107
5.1.1数组的定义 107
5.1.2数组的实现机制 108
5.1.3数组抽象数据类型 108
5.2动态数组类 109
5.3特殊矩阵 113
5.3.1特殊矩阵的压缩存储 113
5.3.2 n阶对称矩阵顺序表类 115
5.4稀疏矩阵 118
5.4.1稀疏矩阵的压缩存储 118
5.4.2三元组顺序表类 119
5.4.3三元组链表 125
习题5 127
第6章 递归算法 129
6.1递归的概念 129
6.2递归算法的执行过程 131
6.3递归算法的设计方法 133
6.4递归过程和运行时栈 136
6.5递归算法的效率分析 138
6.6递归算法到非递归算法的转换 140
6.7设计举例 144
6.7.1一般递归函数设计举例 144
6.7.2回溯法及设计举例 147
习题6 152
第7章 树和二叉树 155
7.1树 155
7.1.1树的定义 155
7.1.2树的表示方法 156
7.1.3树的抽象数据类型 157
7.1.4树的存储结构 158
7.2二叉树 161
7.2.1二叉树的定义 161
7.2.2二叉树抽象数据类型 162
7.2.3二叉树的性质 162
7.2.4二叉树的存储结构 164
7.3以结点类为基础的二叉树设计 167
7.3.1二叉树的结点类 167
7.3.2二叉树的遍历 168
7.3.3二叉树遍历的应用 171
7.3.4应用举例 173
7.3.5非递归的二叉树遍历算法 175
7.4二叉树类 176
7.5二叉树的分步遍历 180
7.5.1二叉树遍历游标类 180
7.5.2二叉树中序遍历游标类 182
7.5.3二叉树层序遍历游标类 186
7.6线索二叉树 189
7.7哈夫曼树 191
7.7.1哈夫曼树的基本概念 191
7.7.2哈夫曼编码问题 193
7.7.3哈夫曼编码的软件设计 194
7.8等价问题 200
7.9树与二叉树的转换 204
7.10树的遍历 205
习题7 206
第8章 图 209
8.1图 209
8.1.1图的基本概念 209
8.1.2图的抽象数据类型 211
8.2图的存储结构 212
8.2.1图的邻接矩阵存储结构 212
8.2.2图的邻接表存储结构 214
8.3邻接矩阵图类 214
8.4图的遍历 221
8.4.1图的深度和广度优先遍历算法 221
8.4.2图的深度和广度优先遍历函数实现 222
8.5最小生成树 226
8.5.1最小生成树的基本概念 226
8.5.2普里姆算法 227
8.5.3克鲁斯卡尔算法 232
8.6最短路径 233
8.6.1最短路径的基本概念 233
8.6.2从一个顶点到其余各顶点的最短路径 234
8.6.3每对顶点之间的最短路径 238
8.7拓扑排序 239
8.8关键路径 242
习题8 247
第9章 排序 249
9.1排序的基本概念 249
9.2插入排序 251
9.2.1直接插入排序 251
9.2.2希尔排序 254
9.3选择排序 256
9.3.1直接选择排序 256
9.3.2堆排序 257
9.4交换排序 262
9.4.1冒泡排序 262
9.4.2快速排序 264
9.5归并排序 267
9.6基数排序 269
9.7性能比较 272
习题9 273
第10章 查找 275
10.1查找的基本概念 275
10.2静态查找表 276
10.2.1顺序表上的查找 276
10.2.2有序顺序表上的查找 278
10.2.3索引顺序表 280
10.3动态查找表 282
10.3.1二叉排序树和平衡二叉树 282
10.3.2 B树和B＋树 292
10.4哈希表 297
10.4.1哈希表的基本概念 297
10.4.2哈希函数构造方法 299
10.4.3哈希冲突解决方法 300
10.4.4哈希表类 302
习题10 308
附录 部分典型习题解答 309
参考文献 322