数据结构 炫动的0、1之弦PDF|Epub|txt|kindle电子书版本网盘下载

数据结构 炫动的0、1之弦PDF格式电子书版下载

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

第1章 数据结构基础1

1.1什么是数据结构1

1.2数据结构的定义1

1.3数据结构的目的2

1.4数据结构的种类3

1.5数据结构与抽象数据类型5

1.6数据结构的特性6

1.7数据结构的表现方式7

1.8数据结构的基本操作10

1.8.1数据结构操作的成本10

1.8.2最好、最坏、平均12

1.8.3 O、Ω、？表示12

1.9数据结构的哲学13

1.10为什么学习数据结构15

思考题16

第2章 栈结构17

2.1后进先出即为栈17

2.2栈的定义18

2.3栈的实现19

2.4栈的应用22

2.4.1应用1：乘坐校园通勤车22

2.4.2应用2：反转波兰计算器23

2.4.3表达式的前、中、后缀表示及其转换30

2.4.4应用3：括号匹配30

2.5链接栈（栈的链接实现）32

2.6链接栈存在的问题35

思考题39

第3章 队列结构40

3.1先进先出即为队列40

3.2队列的实现41

3.3队列实现的别样问题44

3.4队列的环形实现45

3.5基于计数器的循环队列的实现47

3.6队列应用举例49

3.6.1应用1：先来先得礼品专送49

3.6.2应用2：机场模拟程序50

3.7链接队列58

3.8链接队列应用举例：多项式算术62

思考题70

第4章 表结构72

4.1表的定义72

4.2表的实现73

4.3表结构应用举例：查找特定位置上的乘客编号77

4.4链表——链接实现的表结构78

4.4.1链表的插入操作80

4.4.2链表的删除操作82

4.4.3链表的其他操作82

4.4.4链表操作的时间成本84

4.4.5链表的优化：记住当前位置84

4.5双链表86

4.6基于数组和基于链表实现的表结构比较91

4.7链表的应用举例：字典92

4.8讨论：栈、队列、表、栈表、队表96

思考题98

第5章 查找操作99

5.1什么是查找99

5.2查找的实现100

5.3顺序查找101

5.4折半查找102

5.5查找的成本下限106

5.6常数查找107

5.6.1直接查找107

5.6.2间接查找107

思考题112

第6章 排序操作114

6.1什么是排序114

6.2排序的实现115

6.3插入排序116

6.4选择排序119

6.5冒泡/沉底排序120

6.6希尔排序122

6.7归并排序124

6.7.1归并排序的时间复杂性126

6.7.2归并排序的链表实现127

6.8快速排序131

6.8.1快速排序的过程131

6.8.2快速排序的时间成本分析134

思考题135

第7章 高级表结构136

7.1穷则思变136

7.2跳转表138

7.2.1跳转表的定义139

7.2.2跳转表操作140

7.3索引表146

7.4哈希表（散列表）148

7.4.1哈希函数149

7.4.2哈希结构中的碰撞问题150

7.4.3开放寻址哈希151

7.4.4封闭寻址哈希152

7.4.5探寻序列的设计153

7.4.6哈希结构的查找效率155

7.4.7哈希表的实现155

7.4.8哈希表结构的测试157

7.5讨论：跳转表、哈希表、索引表159

思考题160

第8章 树结构161

8.1树结构的定义162

8.2二叉树165

8.2.1二叉树的另一种表示166

8.2.2二叉树的遍历166

8.2.3编译器中用到的二叉树结构169

8.2.4二叉树的基本操作170

8.3二叉查找树171

8.3.1二叉查找树的查找操作173

8.3.2二叉查找树的插入操作174

8.3.3二叉查找树的删除操作176

8.3.4构建初始二叉查找树180

8.3.5二叉查找树结构的测试181

8.3.6二叉查找树的高度184

8.4平衡二叉树187

8.5 AVL高度平衡树188

8.5.1 AVL树的实现189

8.5.2 AVL树的插入操作190

8.5.3 AVL树的节点删除操作199

8.5.4 AVL树结构的测试203

8.6满二叉树和完全二叉树206

思考题207

第9章 高级树结构208

9.1仅有二叉树是不够的208

9.2 B树209

9.2.1 B树的结构209

9.2.2 B树的键值210

9.2.3 B树的优势210

9.3 B+树和B﹡树211

9.3.1 B+树的定义211

9.3.2 B+树的操作212

9.3.3 B/B+树的代码实现217

9.3.4 B+树的初始构建222

9.3.5 B+树结构对磁盘查找的支持223

9.4伸展树结构224

9.4.1伸展树的特点224

9.4.2伸展树的操作225

9.4.3伸展树的实现227

9.4.4伸展树结构的测试232

9.5哈夫曼树234

9.5.1构造哈夫曼树235

9.5.2哈夫曼树的应用236

9.6树的转换238

9.6.1一般树到二叉树的转换238

9.6.2森林到二叉树的转换240

9.7树和森林的遍历240

9.8其他树结构242

思考题243

第10章 堆结构244

10.1什么是堆结构244

10.2二叉堆结构246

10.2.1二叉堆的表示246

10.2.2二叉堆的实现246

10.2.3堆的初始化构建249

10.2.4堆结构的测试——堆排序252

10.2.5堆的合并255

10.3幂树255

10.4幂堆256

10.4.1幂堆的实现257

10.4.2幂堆的合并操作259

10.4.3幂堆的插入操作260

10.4.4在幂堆里获取最大值261

10.4.5在幂堆里删除最大值262

10.5斐波那契堆263

10.5.1斐波那契堆的定义263

10.5.2斐波那契堆的操作实现264

10.5.3斐波那契堆的节点更新操作265

10.5.4删除任意节点操作265

思考题267

第11章 图结构268

11.1图无处不在268

11.2图的定义270

11.3图的表示272

11.4图的遍历276

11.5图的最短路径操作279

11.5.1 Dijkstra方法280

11.5.2 Dijkstra方法的正确性证明281

11.5.3最短路径方法的代码实现282

11.6最小生成树操作283

11.6.1 Prim方法284

11.6.2 Prim方法的正确性证明285

11.6.3 Prim方法的代码实现286

11.7图的拓扑排序操作287

11.7.1深度优先的拓扑排序288

11.7.2广度优先拓扑排序290

11.8图结构的测试291

思考题295

第12章 集合结构297

12.1什么是集合结构297

12.2数值集合298

12.2.1数值集合的实现298

12.2.2数值集合结构的测试301

12.3基于动态数组的集合结构303

12.4基于位矢量的集合结构304

12.4.1基于位矢量的集合结构定义304

12.4.2位矢量集合结构的并、交、减操作306

12.4.3位矢量集合结构的其他操作307

12.4.4位矢量集合结构的测试308

12.5基于链表的集合结构309

思考题314

第13章 划分结构315

13.1划分结构315

13.1.1划分结构的实现316

13.1.2划分结构的测试318

13.1.3划分结构的操作成本321

13.2划分森林结构322

13.2.1划分森林的实现323

13.2.2构建与析构323

13.2.3查找和合并324

13.3优化的划分结构实现326

13.3.1路径压缩326

13.3.2按规模合并328

13.3.3按秩合并330

13.3.4划分类结构的测试331

13.4划分结构的应用334

思考题337

附录338

附录1标准模板结构338

FL1.1标准模板库数据结构的分类338

FL1.2迭代器类339

FL1.3容器类343

FL1.4容器适配器类349

FL1.5标准模板类里的通用函数349

思考题351

附录2数据结构考研真题解析352

FL2.1 2009年全国硕士研究生入学统一考试计算机科学与技术学科联考数据结构部分考题352

FL2.2 2010年全国硕士研究生入学统一考试计算机科学与技术学科联考数据结构部分考题355

结语：数据结构之弦359

参考文献362