数据结构与算法PDF|Epub|txt|kindle电子书版本网盘下载

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

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第1章 基础知识1

1.1 数据结构的基本概念1

1.2 抽象数据类型5

1.3 问题、算法和程序6

1.4 算法分析概述7

1.5 时间复杂度10

1.6 渐近分析12

1.6.1 上限表示法12

1.6.2 下限表示法13

1.6.3 Θ表示法14

1.6.4 化简法则14

1.7 空间复杂度17

1.8 C＋＋语言基础18

1.8.1 面向对象的概念19

1.8.2 数据声明和作用域20

1.8.3 输入／输出21

1.8.4 函数23

1.8.5 参数传递24

1.8.6 函数重载26

1.8.7 动态内存分配26

1.8.8 C＋＋的模板27

本章小结28

习题28

第2章 线性表31

2.1 线性表的定义31

2.2 线性表的顺序存储结构32

2.2.1 顺序存储结构32

2.2.2 顺序存储结构的实现34

2.3 线性表的链式存储结构37

2.3.1 单链表37

2.3.2 双向链表43

2.3.3 循环链表46

2.4 线性表应用举例48

2.4.1 一元多项式的表示48

2.4.2 商品链更新50

本章小结51

习题51

第3章 受限线性表——栈、队列及串55

3.1 操作受限线性表——栈55

3.2 栈的存储结构56

3.2.1 顺序栈的定义及实现57

3.2.2 链栈的定义及实现60

3.3 栈的应用63

3.3.1 括号匹配检验63

3.3.2 栈与递归65

3.4 操作受限线性表——队列69

3.5 队列的存储结构及实现70

3.5.1 顺序队列的定义及实现70

3.5.2 队列的链式存储结构及实现74

3.6 队列的应用78

3.6.1 杨辉三角形78

3.6.2 火车车厢重排79

3.7 类型受限线性表——字符串82

3.7.1 串的定义83

3.7.2 串的操作83

3.7.3 串的存储结构84

3.7.4 串类及其实现85

3.7.5 串的模式匹配88

本章小结92

习题92

第4章 扩展线性表——数组与广义表96

4.1 扩展线性表——数组96

4.1.1 数组的定义96

4.1.2 数组的基本操作97

4.1.3 数组的存储结构97

4.1.4 矩阵的压缩存储98

4.2 扩展线性表——广义表104

4.2.1 广义表的定义及性质104

4.2.2 广义表的存储表示105

4.2.3 广义表的递归操作110

本章小结113

习题114

第5章 树和二叉树115

5.1 树的定义与基本术语115

5.1.1 树的定义115

5.1.2 相关的基本术语116

5.2 二叉树的定义、性质和存储结构117

5.2.1 二叉树的定义117

5.2.2 二叉树的主要性质118

5.2.3 二叉树的存储结构122

5.3 二叉树的遍历125

5.3.1 二叉树的先序遍历126

5.3.2 二叉树的中序遍历127

5.3.3 二叉树的后序遍历129

5.4 二叉树应用1：哈夫曼树133

5.4.1 哈夫曼树的构造133

5.4.2 哈夫曼编码137

5.5 二叉树应用2：二叉查找树140

5.5.1 二叉查找树的定义140

5.5.2 二叉查找树的查找141

5.5.3 二叉查找树的插入143

5.5.4 二叉查找树的删除145

5.6 二叉树应用3：平衡二叉查找树148

5.6.1 平衡二叉树的定义148

5.6.2 平衡化旋转149

5.6.3 平衡二叉查找树的插入154

5.6.4 平衡二叉查找树的删除155

5.7 二叉树应用4：堆与优先队列158

5.7.1 堆与优先队列的定义与实现158

5.7.2 堆的插入和堆顶删除160

5.8 树与森林164

5.8.1 树的存储结构164

5.8.2 树、森林与二叉树的转换167

5.8.3 树与森林的遍历169

本章小结170

习题170

第6章 图177

6.1 图的定义和术语177

6.2 图的存储结构181

6.2.1 邻接矩阵存储方法182

6.2.2 邻接表存储方法185

6.3 图的遍历190

6.3.1 深度优先搜索191

6.3.2 广度优先搜索194

6.4 图的应用1：拓扑排序196

6.5 图的应用2：关键路径200

6.6 图的应用3：最短路径205

6.6.1 单源点最短路径问题205

6.6.2 任意对顶点之间的最短路径210

6.7 图的应用4：图的最小生成树213

6.7.1 Prim算法214

6.7.2 Kruskal算法217

本章小结220

习题220

第7章 排序算法224

7.1 排序的基本概念224

7.2 简单排序226

7.2.1 简单插入排序226

7.2.2 冒泡排序229

7.2.3 简单选择排序232

7.3 高级排序234

7.3.1 希尔排序234

7.3.2 快速排序236

7.3.3 归并排序241

7.3.4 树形选择排序1：锦标赛排序243

7.3.5 树形选择排序2：堆排序245

7.4 关键字比较排序下界问题249

7.5 非关键字比较的排序250

7.5.1 基数排序250

7.5.2 多关键字排序253

7.6 各种排序算法的比较254

本章小结255

习题255

第8章 查找算法258

8.1 查找的基本概念258

8.2 静态查找表259

8.2.1 顺序表的查找260

8.2.2 折半查找261

8.3 散列表263

8.3.1 哈希函数的常用构建方法264

8.3.2 解决冲突的办法266

8.3.3 哈希表的实现270

8.3.4 哈希表的分析273

8.4 线性索引274

8.5 树形索引275

8.5.1 2-3树276

8.5.2 B树278

8.5.3 B+树286

本章小结288

习题288

第9章 算法设计常用方法289

9.1 贪心算法289

9.1.1 活动安排问题289

9.1.2 贪心算法的设计思想291

9.1.3 贪心算法的应用294

9.2 分治算法302

9.2.1 分治算法的基本思想302

9.2.2 分治算法复杂度分析304

9.2.3 大整数相乘307

9.2.4 矩阵乘法309

9.2.5 快速排序算法的改进312

9.3 动态规划317

9.3.1 动态规划原理317

9.3.2 最优二叉查找树321

9.3.3 最长公共子序列325

9.4 回溯算法327

9.4.1 回溯算法的思想328

9.4.2 N皇后问题331

9.4.3 迷宫问题332

本章小结336

习题337

第10章 计算复杂性简介340

10.1 基本概念340

10.1.1 非确定性算法340

10.1.2 P类与NP类问题342

10.2 NP难与NP完全问题343

10.2.1 问题变换与计算复杂度归约343

10.2.2 NP完全性344

10.3 NP完全问题的例子346

10.3.1 CNF-SAT问题346

10.3.2 3-SAT问题348

10.3.3 团问题349

10.3.4 顶点覆盖问题350

10.3.5 其他一些NP完全问题351

本章小结351

习题352

附录353

附录A “数据结构与算法”课内实验设计353

附录B “数据结构与算法”专题实验设计354

参考文献362