第1章 绪论 1
1.1数据结构的基本概念 1
1.1.1抽象数据类型与数据结构 1
1.1.2数据的逻辑结构 3
1.1.3数据的存储结构 4
1.1.4数据的操作 5
1.2算法与算法设计 6
1.2.1算法 6
1.2.2算法设计 9
1.2.3算法分析 10
习题1 12
实习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顺序表类操作 16
2.2.3顺序表类操作的效率分析 21
2.3单链表类 23
2.3.1单链表的概念 23
2.3.2单链表的节点类 24
2.3.3单链表类的设计与实现 25
2.3.4两种存储结构性能的比较 34
2.3.5单向循环链表类 34
2.4双向链表类 39
2.4.1双向链表的概念 39
2.4.2双向链表的节点类 39
2.4.3双向链表类的设计与实现 40
2.4.4双向循环链表的概念 43
习题2 44
实习2 45
第3章 排序 46
3.1排序的基本概念 46
3.2插入排序 47
3.2.1顺序表的直接插入排序 47
3.2.2单链表的直接插入排序 50
3.2.3希尔排序 52
3.3交换排序 55
3.3.1冒泡排序 56
3.3.2改进的冒泡排序 57
3.3.3快速排序 59
3.4选择排序 62
3.4.1顺序表的直接选择排序 62
3.4.2单链表的直接选择排序 64
3.5归并排序 67
3.5.1顺序表的归并排序 68
3.5.2单链表的归并排序 71
习题3 74
实习3 75
第4章 串 77
4.1串的基本概念 77
4.1.1串的定义 77
4.1.2串的抽象数据类型 78
4.1.3串的存储结构 78
4.2顺序串类 79
4.2.1顺序串类声明 79
4.2.2顺序串类的基本操作 80
4.2.3顺序串类的运算符重载 83
4.2.4对子串的操作 85
4.3串的模式匹配算法 88
4.3.1 Brute-Force算法 89
4.3.2替换子串操作 91
习题4 92
实习4 92
第5章 栈和队列 93
5.1栈 93
5.1.1栈的定义 93
5.1.2栈的抽象数据类型 94
5.1.3顺序栈类 94
5.1.4链式栈类 98
5.1.5栈的应用 102
5.2队列 110
5.2.1队列的定义 110
5.2.2队列的抽象数据类型 111
5.2.3队列的存储结构 111
5.2.4顺序循环队列类 113
5.2.5链式队列类 116
5.2.6队列的应用 119
5.3递归 121
实习5 126
习题5 126
第6章 数组和广义表 128
6.1数组 128
6.1.1一维数组 128
6.1.2多维数组 129
6.2矩阵类 131
6.2.1矩阵类的声明 131
6.2.2矩阵类的操作 132
6.4.1稀疏矩阵的三元组线性表 136
6.4稀疏矩阵 136
6.3特殊矩阵的压缩存储 136
6.4.2三元组顺序表类 137
6.4.3三元组链表 141
6.5广义表 142
6.5.1广义表的概念 142
6.5.2广义表的存储结构 144
习题6 145
实习6 146
7.1树 147
7.1.1树的定义 147
第7章 树和二叉树 147
7.1.2树的术语 148
7.1.3树的表示方法 149
7.2二叉树 150
7.2.1二叉树的定义 150
7.2.2二叉树的性质 151
7.2.3二叉树的抽象数据类型 152
7.2.4二叉树的遍历 153
7.2.5二叉树的存储结构 154
7.2.6树与二叉树的转换 155
7.3.1二叉树的节点类 156
7.3二叉树类 156
7.3.2二叉树类的设计与实现 158
7.3.3建立二叉树的算法设计 164
7.3.4二叉树遍历的非递归算法 170
7.3.5二叉树的层次遍历 172
7.4线索二叉树 173
7.4.1线索二叉树的定义 174
7.4.2线索二叉树的节点类 175
7.4.3中序线索二叉树类 175
7.5堆排序 183
习题7 187
实习7 188
第8章 查找 190
8.1查找的基本概念 190
8.2线性表的查找 192
8.2.1顺序查找 192
8.2.2折半查找 195
8.2.3分块查找 198
8.3二叉排序树及其查找算法 200
8.4.1哈希表的基本概念 206
8.4哈希查找 206
8.4.2设计哈希函数 208
8.4.3解决冲突的方法 209
8.4.4拉链法的哈希表类 210
习题8 214
实习8 215
第9章 图 216
9.1图的基本知识 216
9.1.1图的定义 216
9.1.3子图 218
9.1.2节点的度 218
9.1.4路径、回路及连通性 219
9.1.5图的抽像数据类型 220
9.2图的存储结构 220
9.2.1邻接矩阵 220
9.2.2邻接表 222
9.3图的遍历 223
9.3.1深度优先遍历 223
9.3.2广度优先遍历 224
9.4邻接矩阵图类 224
9.5.1树与图 231
9.5最小生成树 231
9.5.2生成树 232
9.5.3最小生成树及其构造算法 233
9.6最短路径 235
习题9 236
实习9 237
第10章 综合应用设计 238
10.1用“预见算法”解骑士游历问题 238
10.2综合应用实习 246
参考文献 250