第一章 算法概述 1
1-1 算法及其复杂性 1
1．算法的概念 1
目录 1
2．一个算法的分析 2
3．算法的时间和空间复杂性 4
1-2 算法设计的基本方法 9
1．分治法 9
2．动态规划 14
3．贪心法 15
4．倒推法 17
1．串 20
2．串变量、串组变量 20
2-1 串、串变量、串组变量 20
第二章 字符串 20
3．字符在机器内的表示形式 21
4．串变量的相互比较 22
2-2 串的运算 22
1．联接 22
2．长度函数 23
3．子串 23
4．定位函数 23
5．置换 24
6．插入 24
7．删除 25
2-3 串内的模式匹配 25
习题 29
第三章 并列表 31
3-1 并列表的一些基本知识 31
3-2 线性并列表 33
1．线性并列表的定义 33
2．线性并列表的顺序分配 33
3．线性并列表的链接分配 38
3-3 栈和队列 51
1．栈 51
2．队列 54
3-4 栈的应用 58
1．算术表达式的计算 58
2．栈在拓扑分类中的应用 62
3．用栈计算递归函数 65
3-5 栈和过程 67
3-6 压缩存贮、索引存贮和散列存贮 73
1．压缩存贮 73
2．索引存贮 76
3．散列存贮 78
3-7 多维数组 82
1．矩形数组 82
2．m维数组和Iliffe方法 89
3-8 合并与分类 91
1．分类概述 91
2．合并并列表 92
3．合并分类法 95
4．插入分类法 96
5．起泡分类法 96
6．口袋分类法 97
7．选择分类法 101
8．歇尔分类法 102
9．快速分类法 103
10．堆分类法 106
11．杂凑分类法 111
12．外部分类 111
3-9 线性并列表的查找 124
1．查找问题 124
2．顺序查找法 124
3．二分查找法 126
4．分块查找法 128
5．从线性并列表中查找第i个大的关键字的结点 129
习题 134
第四章 树 137
4-1 树和存贮树的方法 137
1．树的定义 137
2．树的基本术语和记号 137
3．树的存贮形式 138
4．树结构的应用概述 139
4-2 二叉树 144
1．二叉树的递归定义 144
2．二叉树的标准存贮形式 145
3．把一般树变成二叉树 145
4．周游二叉树 147
5．中序穿线 156
6．顺序方法存贮的二叉树 159
1．分类二叉树中的查找 161
4-3 树的查找 161
2．丰满树 162
3．在分类的二叉树上删除结点 163
4．平衡树 165
5．查找具有给定位置i的结点ki 170
6．最优查找树 173
7．最左树 180
8．键树 186
9．B-树 190
4-4 查找解答树 195
1．用解答树解答问题 195
2．背包问题 196
3．皇后问题 210
习题 215
第五章 复杂的数据结构 218
5-1 图 218
1．图的定义及有关术语 218
2．图的几种表示形式 219
3．n次m阶有根图的存贮形式 219
4．求图B的所有最大连通集合 221
5．有向图的应用 229
6．有序图和叶并列表 232
5-2 多重链接结构和组合查询 240
1．m重属性文件 240
2．几种查找m重属性文件的方法 241
习题 252
附录 本书程序流程图中使用符号的说明 254
参考文献 256