《实用数据结构》

第一章　算法概述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的结点ki170

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