数据结构与算法PDF电子书下载

3.6逐步求精法 7 1

第1章 概论 1

1.1什么是数据结构 1

目 录 1

1.2数据的逻辑结构 3

1.3数据的类型 4

1.4数据的存储结构 6

1.5数据的运算 8

1.6数据的分析和性能评价 12

1.6.1算法设计的要求 12

1.6.2选择数据结构 13

1.6.3算法效率的度量 13

1.6.4算法的存储空间需求 14

小结 15

综合练习一 15

一、选择题 15

小结 1 16

二、思考题 16

三、上机题 17

第2章类C语言基础知识 18

2.1.1 C语言简史 18

2.1 C语言简介 18

2.1.2特点 19

2.1.3 C语言程序的结构 19

2.2 C语言数据类型 19

2.2.1常量与变量 19

2.2.2基本类型 20

2.2.3构造类型 20

2.2.4其他重要数据类型 22

2.3 C语言运算符与表达式 23

2.3.1 算术运算 23

2.3.2逻辑运算 24

2.3.3位运算 24

2.3.4其他重要运算符 24

2.4 C语言函数 25

2.3.5 运算符的优先级 25

2.4.2 函数的调用 26

2.4.1定义函数 26

2.4.3 函数的返回 27

2.5 C语言常用语句 28

2.5.1输入／输出语句 28

2.5.2条件语句、开关语句 29

2.5.3循环语句 30

2.6综合应用实例 33

二、思考题 1 35

三、上机题 1 36

一、选择题 38

小结 38

综合练习二 38

二、思考题 39

三、上机题 40

第3章算法基础 42

3.1 递归法 42

3.1.1递归的概念 42

3.1.2递归过程和递归工作栈 46

3.1.3递归的应用 50

3.2穷举法 54

3.3迭代法 57

3.4.1 倒推法 59

3.4递推法 59

3.4.2顺推法 61

3.5 分治法 65

3.5.1分治法的设计思想 65

3.5.2分治法所能解决的问题 65

3.5.3分治法的几种变形 70

小结 73

综合练习三 73

一、选择题 73

二、思考题 74

三、上机题 74

4.1 向量 75

4.1.1向量的运算 75

第4章顺序表 75

4.1.2 Josephus问题 77

4.2栈 78

4.3.1数制转换 81

4.3栈的应用 81

4.3.2表达式求值 82

4.3.3迷宫求解 84

4.4 队列 87

4.5利用队列打印二次展开式的算法 89

4.6限制存取点的表 91

小结 91

综合练习四 91

一、选择题 91

二、思考题 91

三、上机题 92

5.1 单链表 93

第5章链表 93

5.2栈的链表表示 96

5.3队列的链表表示 97

5.4特殊的链表 99

5.4.1 双向链表 99

5.4.2循环链表 100

5.4.3队列的循环链表表示 101

5.5一元多项式的链表表示及其运算 101

小结 104

综合练习五 104

一、选择题 104

二、思考题 105

三、上机题 106

第6章 串 107

6.1 串的概念 107

6.2串的运算实现 110

6.2.1基本的串运算 110

6.2.2串运算的实现 111

6.3字符串的模式匹配 112

6.4 KMP算法 113

综合练习六 116

一、选择题 116

二、思考题 116

三、上机题 117

第7章 多维数组与广义表 118

7.1多维数组的定义 118

7.2多维数组的逻辑结构 119

7.3多维数组的顺序存储 119

7.4矩阵的压缩存储 120

7.4.1 特殊矩阵 121

7.4.2稀疏矩阵 122

7.5 广义表 127

7.5.1 广义表的定义 127

7.5.2 广义表的存储结构 128

7.5.3 广义表的运算 130

小结 134

综合练习七 134

一、选择题 134

第8章树和森林 138

8.1树的定义和基本术语 138

8.2 二叉树 140

8.2.1二叉树的定义 140

8.2.2二叉树的性质 141

8.2.3二叉树的存储结构 142

8.3.1遍历的递归算法 143

8.3遍历二叉树 143

8.3.2遍历的非递归算法 145

8.4线索二叉树 148

8.4.1线索化二叉树 148

8.4.2遍历线索二叉树 150

8.5树的存储结构 152

8.6森林和二叉树的转换 154

8.7树和森林的遍历 155

8.8.1最优二叉树 156

8.8赫夫曼树及其应用 156

8.8.2赫夫曼编码 158

小结 160

综合练习八 160

一、选择题 160

二、思考题 161

三、上机题 161

9.1 基本概念 162

第9章查找 162

9.2线性表的查找 163

9.2.1 顺序查找 163

9.2.2二分查找 164

9.2.3 分块查找 166

9.3树表的查找 168

9.3.1 二叉排序树 168

9.3.2平衡的二叉排序树 173

9.4散列表的查找 176

9.4.1 散列表 176

9.4.2散列函数的构造方法 176

9.4.3冲突的处理 178

小结 180

综合练习九 180

一、选择题 180

三、上机题 181

二、思考题 181

第10章 图 182

10.1 图的定义和术语 182

10.2图的存储结构 184

10.2.1数组表示法 184

10.2.2邻接表表示法 185

10.2.3十字链表 188

10.2.4邻接多重表 189

10.3图的遍历 190

10.3.1深度优先搜索 190

10.3.2广度优先搜索 191

10.4图的连通性 192

10.5图的最小生成树 193

10.6拓扑排序 196

10.7关键路径（图） 197

10.8最短路径 199

10.8.1从一个结点到其他各个结点的最短路径 200

10.8.2任意两个结点的最短路径 202

小结 203

综合练习十 203

一、选择题 203

二、思考题 204

三、上机题 205

第11章排序 206

11.1概述 206

1 1.2插入排序 208

11.2.1直接插入排序 208

1 1.2.2折半插入排序 210

11.2.3表插入排序 210

11.2.4希尔排序 211

11.3交换排序 213

11.3.1起泡排序 213

11.3.2快速排序 215

11.4.1直接选择排序 216

11.4选择排序 216

1 1.4.2锦标赛排序 217

11.4.3堆排序 218

11.5归并排序 221

1 1.5.1 归并 221

11.5.2迭代的归并排序算法 222

11.5.3递归的表归并排序 223

1 1.6基数排序 224

1 1.6.1多排序码排序 224

1 1.6.2链式基数排序 225

1 1.7外排序 228

11.7.1外排序的基本过程 228

11.7.2 K路平衡归并 229

11.7.3初始归并段的生成 231

11.7.4并行操作的缓冲区处理 232

11.7.5最佳归并树 233

小结 234

综合练习十一 235

一、选择题 235

二、思考题 236

三、上机题 236

第12章文件 237

12.1文件基本概念 237

12.2顺序文件 238

12.3索引文件 239

12.4 Hash文件 240

12.5多关键字文件 241

小结 242

综合练习十二 242

一、选择题 242

二、思考题 242

三、上机题 242

13.1回溯与界限剪枝法 243

第13章算法设计基本方法 243

13.1.1 回溯与界限剪枝法经典问题 244

13.1.2回溯与界限剪枝法概述 245

13.1.3 回溯与界限剪枝法实例分析 246

13.1.4回溯与界限剪枝法综述 251

13.2贪心法 251

13.2.1贪心法经典问题 251

13.2.2贪心法概述 253

13.2.3贪心法实例分析 254

13.2.4贪心法小结 255

13.3动态规划法 255

13.3.1动态规划法经典问题 255

13.3.2动态规划法概述 256

13.3.3动态规划法实例分析 258

综合练习十三 264

一、选择题 264

小结 264

13.3.4动态规划法小结 264

二、思考题 265

三、上机题 265

参考答案 267

第1章 267

第2章 267

第3章 268

第4章 269

第5章 271

第6章 272

第7章 274

第8章 275

第9章 276

第10章 277

第11章 279

第12章 281

第13章 282

参考文献 284