第1章 数据结构概论 1
1.1 数据与信息 2
1.2 数据处理(Data Processing) 3
1.3 计算机任务处理的方式 5
1.4 程序的产生 5
1.5 程序的分析 6
1.6 算法 9
1.7 复杂度(Complexity) 13
1.9 参数的传递 15
1.8 NP-COMPLETE问题 15
1.10 数据结构(Data Structure) 17
习题 18
第2章 数组结构 19
2.1 数组的定义 20
2.2 数组表示法 20
2.3 稀疏矩阵(Sparse Matrix) 26
2.4 数组的应用 28
2.4.1 多项式的数据结构 28
2.4.2 多项式相加 30
2.4.3 上三角形和下三角形存储方式 31
2.4.4 矩阵乘积 34
习题 35
第3章 链表 37
3.1 链表的定义 38
3.2 动态内存分配 38
3.3 链表的建立 38
3.4 链表的遍历 41
3.6 链表内结点的删除 42
3.5 链表的连接 42
3.7 释放链表的内存空间 43
3.8 链表内结点的插入 44
3.9 链表结构的反转 45
3.10 循环链表结构 47
3.11 使用循环链表结构表示稀疏数组 51
3.12 双向链表结构 55
3.13 循环双向链表结构 60
习题 62
第4章 递归 63
4.1 何谓递归 64
4.2 递归工作原则 65
4.3 递归的执行过程 66
4.4 递归的应用 69
4.4.1 汉诺塔问题(Towers of Hanoi) 69
4.4.2 迷宫问题(Mazing Problem) 71
4.4.3 八皇后问题(Eight Queen Problem) 74
4.4.4 骑士问题 78
4.5 递归程序与非递归程序的差异 80
习题 81
第5章 栈 83
5.1 栈的定义 84
5.2 栈的表示及操作方式 84
5.3 栈的应用 86
5.3.1 算术运算式的转换(Expression Conversion) 86
5.3.2 子程序调用(Subroutine call) 90
5.3.3 中断处理(Interrupt Processing) 90
5.3.5 汉诺塔问题(Towers of Hanoi) 91
5.3.4 编译错误处理(Compiler Syntax Processing) 91
5.3.6 迷宫问题(Mazing Problem) 94
5.3.7 八皇后问题(Eight Queen Problem) 96
习题 98
第6章 队列 101
6.1 队列的定义 102
6.2 线性队列的表示及操作方式 102
6.2.1 以数组表示线性队列 102
6.2.2 以链表表示线性队列 106
6.3.1 以数组表示循环队列 107
6.3 循环队列的表示及操作方式 107
6.3.2 以链表表示循环队列 110
习题 112
第7章 树 113
7.1 基本术语 114
7.2 树的表示法 115
7.3 二叉树 118
7.3.1 二叉树的建立 121
7.3.2 二叉树的遍历 122
7.3.3 二叉树的排序 125
7.3.5 二叉树的删除 126
7.3.4 二叉树的查找 126
7.3.6 一般树转换至二叉树 128
7.3.7 二叉表示树(Binary Expression Tree) 130
7.3.8 相关二叉树 133
7.3.8.1 完全平衡树(Perfectly Balanced Tree) 133
7.3.8.2 满二叉树(Full Binary Tree) 134
7.3.8.3 完全二叉树(Complete Binary Tree) 134
7.3.8.4 线索二叉树(Threaded Binary Tree) 134
7.3.8.5 扩充二叉树(Extended Binary Tree) 135
7.3.8.6 哈夫曼树(Huffman Tree) 137
7.4 树的应用 140
7.4.1 皇后问题 140
7.4.2 井字游戏 141
7.4.3 决策树 143
7.4.4 高度平衡二叉树(Height Balanced Binary Tree，AVL Tree) 144
7.4.5 2-3树与2-3-4树 148
7.4.6 红-黑树 152
7.4.7 最小-最大堆集树 154
7.4.8 双堆集树 156
7.4.9 B树 157
习题 159
第8章 图 163
8.1 前言 164
8.2 图的基本概念 164
8.3 图的存储结构 168
8.3.1 邻接矩阵(Adjacency matrix) 168
8.3.2 邻接表(adjacency list) 170
8.3.3 邻接多重表(Adjacency multilist) 171
8.3.4 索引表(Indexed Table) 172
8.4 图的遍历(Graph Traversal) 173
8.5 生成树(Spanning Tree) 174
8.6 拓扑排序(Topological Sorting) 179
8.7 最短路径 182
习题 188
第9章 排序 191
9.1 前言 192
9.2 内部排序法 193
9.2.1 冒泡排序法(Bubble Sort) 193
9.2.2 线性选择排序法(Linear Selection Sort) 195
9.2.3 交换-线性选择排序法(Linear Selection With Exchange Sort) 197
9.2.4 二次选择排序法(Quadratic Selection Sort) 198
9.2.5 中心插入排序法(Centered Insertion Sort) 200
9.2.6 折半插入排序法(Binary Insertion Sort) 203
9.2.7 快速排序法(Quick Sort) 205
9.2.8 希尔排序法(Shell Sort) 208
9.2.9 归并排序法(Merge Sort) 211
9.2.10 堆排序法(Heap sort) 216
9.2.11 二叉树排序法(Binary Tree Sort) 221
9.2.12 计数排序法(Counting Sort) 225
9.2.13 基数排序法(Radix Sort) 227
9.3 外部排序法 230
9.3.1 直接归并排序法(Direct Merge Sort) 230
9.3.2 自然归并排序法(Natural Merge Sort) 230
9.3.3 K路归并法(k-Way Merge Sort) 232
9.3.4 多段归并法(Polyphase Merge) 234
9.4 排序法的效益评估 236
习题 237
第10章 查找 239
10.2 顺序查找法(Sequential Search) 240
10.1 前言 240
10.3 折半查找法(Binary Search) 242
10.4 杂凑查找法(Hashing) 243
10.4.1 直接定址法(direct addressing) 244
10.4.2 抽取法(extraction) 244
10.4.3 除法(division method) 245
10.4.4 乘法(multiplicative method) 245
10.4.7.1 开放地址法(open addressing) 246
10.4.7 解决杂凑冲突的方法 246
10.4.6 折叠法(folding method) 246
10.4.5 中段平方法(midsquare method) 246
10.4.7.2 双重杂凑法(double hashing) 248
10.4.7.3 分开链接法(separate chaining) 249
10.4.8 从杂凑表删除项目 249
10.4.9 杂凑法的评估 250
10.5 树状查找法 250
10.5.1 折半查找树(Binary Search Tree) 250
10.5.2 B-Tree查找法(B-Tree Search) 251
10.6 斐波那齐查找法(Fibonacci Search) 252
习题 256