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

第1章概述 1

1.1数据结构的兴起与发展 1

目 录 1

1.2数据结构的研究对象 2

1.3数据结构的概念 3

1.4数据结构的图示 4

1.5.2线性结构 5

1.5.3树形结构 5

1.5.1集合 5

1.5数据结构的分类 5

1.5.4图状结构 6

1.6数据结构的存储 6

1.6.1存储器表示 6

1.6.2存储映像 7

1.6.3基本存储方法 7

1.7数据结构的访问接口 9

1.7.1访问接口与逻辑结构 9

1.8.1对象与类 10

1.8面向对象方法 10

1.7.3基本操作的实现 10

1.7.2基本操作的种类 10

1.8.2面向对象方法要素 11

1.8.3面向对象方法的若干述评* 13

1.8.4面向对象程序设计语言* 14

1.9面向对象与数据结构 18

1.9.1面向对象与数据结构的关系 18

1.9.2面向对象数据结构 18

1.9.3数据结构的对象模型 19

习题 20

本章小结 20

第2章程序设计基本策略与方法 21

2.1算法 21

2.1.1算法的概念 21

2.1.2算法的时间复杂度与空间复杂度 22

2.1.3算法时间复杂度的度量 24

2.2穷举法 26

2.3递推法与迭代法 26

2.3.1递推法 26

2.3.2迭代法 27

2.4.1递归与递归程序的概念 29

2.4递归法 29

2.4.2递归程序设计要点 31

2.4.3递归程序执行机理 31

2.4.4 Hanoi塔问题与运行图 33

2.5逐步求精法 35

2.5.1基本思想 35

2.5.2应用示例 35

2.6.1基本思想 37

2.6分治法 37

2.6.2平面分治法示例——顺序统计 38

2.6.3迭代分治法示例——循环赛赛程安排* 40

本章小结 42

习题 43

第3章线性表 45

3.1线性表的逻辑结构 45

3.1.1基本概念 45

3.1.2线性表抽象模型 45

3.2.1基本存储方法 49

3.2线性表的顺序存储结构 49

3.2.2面向对象描述 50

3.3异常处理与下标选择器* 59

3.3.1异常处理 59

3.3.2下标选择器 62

3.4线性表的链式存储——线性链表 66

3.4.1链式存储方法 66

3.4.2线性链表的面向对象描述 66

3.4.3线性链表的面向对象实现 69

3.5.1带头结点的链表 79

3.5几种特殊线性链表 79

3.5.2循环链表 80

3.5.3双向链表 81

3.6线性表应用示例 82

3.6.1集合运算* 82

3.6.2一元多项式相加 83

3.6.3一元多项式的乘法* 92

本章小结 92

习题 93

4.1.1栈的逻辑结构 94

4.1栈 94

第4章特殊线性表——栈、队列、串 94

4.1.2栈的顺序存储结构 96

4.1.3栈的链式存储结构 100

4.2队列 104

4.2.1队列的逻辑结构 104

4.2.2队列的顺序存储结构 105

4.2.3队列的链式存储结构 110

4.3串 112

4.3.1串的逻辑结构 112

4.3.2串的存储结构 116

本章小结 119

习题 120

第5章数组与十字链表 121

5.1数组 121

5.1.1数组的定义与运算 121

5.1.2数组的存储结构与寻址问题 122

5.1.3一维数组的存储与寻址 122

5.1.4二维数组的存储与寻址 123

5.1.5多维数组的存储与寻址 124

5.1.6寻址公式的计算 125

5.2特殊数组* 126

5.2.1对称矩阵 126

5.2.2下／上三角矩阵 127

5.3稀疏矩阵 127

5.3.1稀疏矩阵的逻辑表示 127

5.3.2三元组表存储法 128

5.3.3三元组表的操作 130

5.3.4转置操作 132

5.4.1存储方式 138

5.4十字链表 138

5.4.2十字链表对象 140

5.4.3基本操作的实现 142

本章小结 146

习题 146

第6章树形结构 148

6.1树形结构的基本概念 148

6.1.1树形结构的定义 148

6.1.2基本术语 151

6.2.2几种特殊二叉树 152

6.2.1二叉树的基本概念 152

6.2二叉树 152

6.2.3二叉树的基本性质 153

6.2.4二叉树的遍历 155

6.3二叉树的存储结构 157

6.3.1顺序存储结构 157

6.3.2链式存储结构 158

6.4二叉树对象模型 160

6.4.1二叉树结点对象 160

6.4.2二叉树对象 161

6.5二叉树的遍历操作 165

6.5.1前序遍历操作 165

6.5.2中序遍历操作 169

6.5.3后序遍历操作 170

6.6二叉树的解析表示与存储结构之间的转化 173

6.6.1双遍历结果转化为树 173

6.6.2根据广义表表示创建树 175

6.6.3根据存储结构创建广义表* 178

6.6.4根据前序扩展序列创建树* 179

6.7.1线索化的概念 181

6.7二叉树的线索化 181

6.7.2线索化算法 182

6.8树与森林 184

6.8.1树与森林的遍历 184

6.8.2树、森林与二叉树之间的转化 186

6.8.3树的存储结构 187

6.9树对象模型* 190

6.9.1树结点对象 190

6.9.2树类 191

6.10.1 哈夫曼树的基本概念 194

6.10树的应用示例——哈夫曼树 194

6.10.2哈夫曼树构造算法 195

6.10.3哈夫曼树构造算法的实现 196

6.10.4哈夫曼判定树 199

6.10.5哈夫曼编码与数据压缩 200

本章小结 201

习题 202

第7章图结构 204

7.1图的基本概念 204

7.1.1图的概念 204

7.2图的对象抽象模型 207

7.1.2图的基本操作 207

7.2.1图结点抽象模型 208

7.2.2图的边对象抽象模型 208

7.2.3图抽象对象模型 209

7.3图的存储结构 211

7.3.1邻接矩阵法 212

7.3.2邻接表 214

7.3.3十字链表* 218

7.3.4邻接多重表* 220

7.4图的遍历 222

7.4.1概述 222

7.4.2深度优先遍历 222

7.4.3深度优先遍历的性质 227

7.4.4广度优先遍历 228

7.4.5广度优先遍历的性质 232

7.5拓扑排序 232

7.5.1拓扑序列与AOV网 233

7.5.2拓扑排序算法与实现 234

7.6.1AOE网与关键路径的概念 238

7.6 AOE网与关键路径 238

7.6.2关键路径的识别 241

本章小结 242

习题 242

第8章广义表 244

8.1广义表的逻辑结构 244

8.1.1基本概念 244

8.1.2 广义表逻辑图 246

8.1.3 广义表的遍历 246

8.2广义表的存储结构 247

8.2.1基本存储方法 247

8.1.5基本操作 247

8.1.4基本特性 247

8.2.2链式结构的高级语言描述 249

8.3 广义表对象模型* 250

8.3.1广义表元素接口 250

8.3.2 广义表接口 251

8.4广义表的分支单链表对象* 254

8.4.1结点对象 254

8.4.2分支单链表对象 255

8.5.1一般问题 256

8.5广义表操作的实现* 256

8.5.2遍历操作 257

8.5.3 广义表统计计数 258

8.5.4广义表的串行化与逆串行化 259

8.5.5 广义表的复制与求尾 261

8.6广义表结构的应用 262

8.6.1多元多项式的表示 262

8.6.2层次结构的表示 263

本章小结 264

习题 264

9.1.1检索的概念 266

第9章检索结构 266

9.1概述 266

9.1.2检索结构 267

9.1.3检索算法的时间与空间复杂度分析 267

9.1.4检索算法的判定树 268

9.2线性结构的检索 270

9.2.1顺序检索 270

9.2.2折半检索 271

9.2.3斐波那契检索* 275

9.3.1概述 280

9.2.4插值检索* 280

9.3线性索引结构 280

9.3.2稠密索引 281

9.3.3分块索引 281

9.4树形索引结构与二叉排序树 283

9.4.1树形索引结构概述 283

9.4.2二叉排序树的概念 283

9.4.3二叉排序树的检索 284

9.4.4二叉排序树的插入* 286

9.4.5二叉排序树的删除* 287

9.4.6二叉排序树的分析与最优二叉排序树* 292

9.5平衡二叉排序树* 293

9.5.1基本概念 293

9.5.2若干性质 293

9.5.3局部平衡调整算法 294

9.6 B树 299

9.6.1 B树的概念 299

9.6.2 B树的存储结构 300

9.6.5 B树的插入 301

9.6.3 B树的基本操作 301

9.6.4 B树的检索方法 301

9.6.6 B树的删除 304

9.6.7 B+树 306

9.6.8 B树对象模型 307

9.7散列结构 307

9.7.1概念 307

9.7.2散列技术中的主要问题 308

9.7.3散列过程 308

9.7.4散列函数的设计 308

9.7.5冲突解决 310

本章小结 311

习题 312

第10章外存与文件组织 313

10.1 外存结构 313

10.1.1 外存简介 313

10.1.2磁带结构 313

10.1.3磁盘结构 314

10.2 文件 315

10.2.1文件的概念 315

10.2.3文件的物理组织 316

10.2.2文件操作与存取方式 316

10.2.4缓冲技术 318

10.3顺序文件 318

10.4索引文件 319

10.5 ISAM* 320

10.5.1 ISAM的概念 320

10.5.2 ISAM结构的操作 321

10.6 VSAM 322

10.6.1 VSAM的概念 322

10.6.2 VSAM结构的操作 323

10.7散列方式 324

10.8多索引文件 325

10.8.1多重表文件 325

10.8.2倒排文件 326

本章小结 327

习题 327

第11章排序算法 329

11.1概述 329

11.2插入排序 330

11.2.1直接插入排序 331

11.2.2其他插入排序算法 332

11.3交换排序 332

11.3.1 冒泡排序 333

11.3.2 冒泡算法的改进 334

11.3.3快速排序* 335

11.4选择排序 336

11.4.1直接选择排序 336

11.4.2堆排序 337

11.5.2多段二路合并 345

11.5.1二路合并 345

11.5归并排序 345

11.5.3二路归并排序 346

11.6外排序简介 348

本章小结 348

习题 349

第12章算法设计基本方法 350

12.1 回溯法与限界剪枝法 350

12.1.1基本思想 350

12.1.2迷宫问题 351

12.1.3稳定婚姻问题* 357

12.1.4 n皇后问题 365

12.1.5限界剪枝法简介* 368

12.2动态规划法 368

12.2.1动态规划法要素与最优性原理 368

12.2.2最长公共子序列 369

12.2.3流水线调度问题* 374

12.2.4多源最短路径的Floyd算法 380

12.2.5 0-1背包问题 383

12.3贪心法 385

12.3.2背包问题 386

12.3.1基本思想 386

12.3.3 Prim最小生成树算法 389

12.3.4 Kruskal最小生成树算法 396

12.3.5单源最短路径 399

12.3.6贪心法要素总结 405

本章小结 406

习题 407

词汇索引 408

参考文献 413