数据结构 思想与实现PDF|Epub|txt|kindle电子书版本下载

数据结构 思想与实现PDF格式电子书版下载

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

第1章 引言1

1.1 算法与数据结构1

1.1.1 数据的逻辑结构2

1.1.2 数据结构的运算3

1.2 存储实现4

1.3算法分析4

1.3.1 时间复杂度的概念5

1.3.2 算法运算量的计算6

1.3.3 渐进表示法8

1.3.4 时间复杂度的计算10

1.3.5 算法的优化11

1.4 面向对象的方法15

1.4.1 面向对象的概念15

1.4.2 用面向对象的思想讨论数据结构16

1.4.3 面向对象方法中数据结构的描述和实现16

1.5 本书的结构和特点17

1.6 本书采用的算法描述工具17

1.7 总结17

1.8 习题18

第一部分 线性表21

第2章 线性表21

2.1 线性表的基本概念21

2.2 线性表的顺序实现22

2.2.1 顺序表的存储实现22

2.2.2 基本运算在顺序表上的实现23

2.2.3 顺序实现的算法分析26

2.3 线性表的链接实现26

2.3.1 单链表27

2.3.2 双链表31

2.3.3 循环链表32

2.4 线性表类的实现33

2.4.1 线性表的抽象类33

2.4.2 顺序表类的实现35

2.4.3 双链表类的实现37

2.5 STL中的线性表41

2.5.1 容器和迭代器的概念41

2.5.2 vector类和list类42

2.5.3 vector类和list类的使用44

2.5.4 双端队列-deque47

2.6 线性表的应用：文本编辑系统47

2.7 小结48

2.8 习题48

第3章 栈51

3.1 栈的基本概念51

3.2 栈的顺序实现52

3.3 栈的链接实现53

3.4 栈类的实现54

3.4.1 栈的抽象类54

3.4.2 顺序栈类的实现54

3.4.3 链接栈类的实现56

3.5 STL中的栈57

3.6 栈的应用59

3.6.1 递归消除59

3.6.2 括号配对62

3.6.3 简单的计算器72

3.7 总结82

3.8 习题83

第4章 队列84

4.1 队列的概念84

4.2 队列的顺序实现85

4.2.1 队头位置固定的顺序实现85

4.2.2 队头位置不固定的顺序实现86

4.2.3 循环队列87

4.3 队列的链接实现89

4.4 队列类的实现90

4.4.1 队列的抽象类90

4.4.2 循环队列类的实现91

4.4.3 链接队列类的实现93

4.5 STL中的队列95

4.6 队列的应用：排队系统的模拟96

4.7 总结101

4.8 习题101

第二部分 树形结构105

第5章 树105

5.1 树的概念105

5.1.1 树的定义105

5.1.2 树的基本术语106

5.1.3 树的基本运算107

5.2 二叉树107

5.2.1 二叉树的基本概念107

5.2.2 二叉树的主要性质109

5.2.3 二叉树的基本运算和二叉树的遍历111

5.2.4 二叉树的顺序实现114

5.2.5 二叉树的链接实现116

5.2.6 二叉树类的实现118

5.2.7 二叉树遍历的非递归实现126

5.3 二叉树的应用：计算表达式129

5.4 哈夫曼树和哈夫曼编码140

5.4.1 前缀编码141

5.4.2 哈夫曼算法143

5.4.3 哈夫曼树类的实现146

5.5 树和森林150

5.5.1 树的存储实现150

5.5.2 树的遍历152

5.5.3 树、林与二叉树的关系153

5.6 总结155

5.7 习题155

第6章 优先级队列158

6.1 基本的优先级队列158

6.2 二叉堆158

6.2.1 二叉堆的结构性158

6.2.2 二叉堆的有序性159

6.2.3 基于二叉堆的优先级队列的实现160

6.3 D堆168

6.4 归并优先级队列169

6.4.1 左堆169

6.4.2 斜堆171

6.4.3 贝努里队列172

6.5 STL中的优先级队列176

6.6 多服务台排队系统的模拟177

6.7 总结182

6.8 习题183

第三部分 集合187

第7章 集合与静态查找表187

7.1 集合的基本概念187

7.2 查找的基本概念187

7.3 静态表查找188

7.4 无序表的查找188

7.4.1 顺序查找188

7.4.2 顺序查找的时间复杂度分析189

7.5 有序表的查找190

7.5.1 顺序查找190

7.5.2 二分查找190

7.5.3 插值查找192

7.5.4 分块查找192

7.6 静态查找表的实现193

7.7 STL中的静态表194

7.8 总结196

7.9 习题196

第8章 查找树197

8.1 二叉查找树197

8.1.1 二叉查找树的定义197

8.1.2 二叉查找树的操作198

8.1.3 二叉查找树的性能203

8.1.4 二叉查找树类的实现204

8.2 AVL树209

8.2.1 AVL树的定义209

8.2.2 AVL树的插入操作211

8.2.3 AVL树的删除操作217

8.2.4 AVL树类的实现221

8.3 红黑树227

8.3.1 红黑树的定义227

8.3.2 红黑树的插入操作228

8.3.3 红黑树的删除操作234

8.3.4 红黑树类的实现239

8.4 AA树249

8.4.1 AA树的定义249

8.4.2 AA树的插入操作250

8.4.3 AA树的删除操作253

8.4.4 AA树类的实现256

8.5 伸展树260

8.5.1 伸展树的定义260

8.5.2 伸展操作的实现262

8.6 B树和B＋树265

8.6.1 B树266

8.6.2 B＋树267

8.7 STL中的查找表273

8.7.1 set273

8.7.2 map274

8.8 总结275

8.9 习题276

第9章 散列表278

9.1 基本概念278

9.2 散列函数279

9.3 碰撞的解决281

9.3.1 线性探测法281

9.3.2 二次探测法283

9.3.3 再散列法285

9.3.4 开散列表285

9.4 散列表类的实现286

9.4.1 散列表类的抽象类286

9.4.2 闭散列表的实现287

9.4.3 开散列表的实现290

9.5 散列表类的应用293

9.6 总结295

9.7 习题295

第10章 排序297

10.1 引言297

10.2 插入排序298

10.2.1 直接插入排序298

10.2.2 二分插入排序300

10.2.3 希尔排序300

10.2.4 希尔排序的性能302

10.3 选择排序302

10.3.1 直接选择排序303

10.3.2 堆排序304

10.4 交换排序307

10.4.1 冒泡排序307

10.4.2 快速排序308

10.5 归并排序314

10.6 外排序317

10.6.1 外排序的基本过程317

10.6.2 预处理阶段317

10.6.3 归并阶段319

10.7 总结321

10.8 习题321

第11章 不相交集323

11.1 等价关系与等价类323

11.2 不相交集324

11.3 不相交集的实现324

11.3.1 不相交集的存储实现324

11.3.2 不相交集的运算实现325

11.3.3 改进的union算法325

11.3.4 改进的find算法327

11.4 不相交集类的实现327

11.5 不相交集的应用329

11.5.1 生成迷宫329

11.5.2 最近的共同祖先问题331

11.6 总结332

11.7 习题332

第四部分 图335

第12章 图的基本概念335

12.1 图的定义335

12.2 图的基本术语336

12.3 图的基本运算338

12.4 图的存储339

12.4.1 邻接矩阵表示法339

12.4.2 邻接表表示法343

12.5 图的遍历347

12.5.1 深度优先搜索DFS348

12.5.2 广度优先搜索BFS351

12.6 图的遍历的应用353

12.6.1 无向图的连通性353

12.6.2 欧拉回路353

12.6.3 有向图的连通性359

12.6.4 拓扑排序360

12.7 总结363

12.8 习题364

第13章 最小生成树366

13.1 生成树和最小生成树366

13.2 Kruskal算法367

13.3 Prim算法370

13.4 算法的正确性374

13.5 总结375

13.6 习题375

第14章 最短路径问题376

14.1 单源最短路径376

14.1.1 非加权图的最短路径376

14.1.2 加权图的最短路径382

14.1.3 带有负权值的图387

14.1.4 无环图388

14.2 所有顶点对的最短路径390

14.3 总结393

14.4 习题393

第五部分 算法设计基础第15章 算法设计基础397

15.1 枚举法397

15.2 贪婪法398

15.3 分治法399

15.3.1 最大连续子序列和的问题399

15.3.2 整型数的乘法问题401

15.3.3 平面上的最近点问题401

15.4 动态规划402

15.4.1 硬币找零问题404

15.4.2 最优二叉查找树406

15.5 回溯法409

15.6 随机算法413

15.6.1 跳表414

15.6.2 素数检测416

15.7 总结418

15.8 习题418

参考文献420