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

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

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

前言页1

前言1

第1章 绪论1

本章要点1

1.1 数据结构的概念及分类1

1.1.1 数据与数据结构1

1.1.2 数据结构的分类2

1.2 抽象数据类型及面向对象概念4

1.2.1 数据类型4

1.2.2 数据抽象与抽象数据类型5

1.2.3 面向对象的概念6

1.2.4 用于描述数据结构的语言7

1.3 算法定义7

1.4.1 算法的性能标准9

1.4 算法性能分析与度量9

1.4.2 算法的后期测试10

1.4.3 算法的事前估计11

1.4.4 渐进的时间复杂度16

1.4.5 渐进的空间复杂度19

小结19

习题20

第2章 数组23

本章要点23

2.1 作为抽象数据类型的数组23

2.1.1 在C++中数组的定义和初始化23

2.1.2 作为抽象数据类型的数组24

2.1.3 数组的顺序存储方式26

2.2 顺序表28

2.2.1 线性表的概念28

2.2.2 顺序表的定义和特点29

2.2.3 顺序表的搜索、插入和删除32

2.2.4 作为抽象数据类型，使用顺序表的事例33

2.3 稀疏矩阵34

2.3.1 稀疏矩阵的抽象数据类型34

2.3.2 稀疏矩阵的压缩表示35

2.4 字符串36

2.4.1 字符串抽象数据类型和类定义36

2.4.2 字符串操作的实现37

小结40

习题41

第3章 链表45

本章要点45

3.1 单链表45

3.1.1 单链表的概念45

3.1.2 单链表的类定义46

3.1.3 单链表中的插入与删除47

3.1.4 带表头结点的单链表49

3.1.5 单链表的模板类50

3.1.6 静态链表54

3.2 循环链表55

3.3 多项式及其相加56

3.3.1 多项式抽象数据类型与*this指针56

3.3.2 多项式的表示57

3.3.3 多项式的加法59

3.4 双向链表61

3.4.1 双向链表的概念61

3.4.2 带表头结点的双向循环链表62

3.4.3 双向循环链表的搜索、插入和删除算法63

3.5 稀疏矩阵65

小结67

习题68

第4章 栈和队列71

本章要点71

4.1 栈71

4.1.1 栈的定义71

4.1.2 顺序栈--栈的数组存储表示71

4.1.3 链式栈--栈的链接存储表示74

4.2 表达式的计算76

4.2.1 表达式76

4.2.2 应用后缀表示计算表达式的值77

4.2.3 中缀表示与其他表示之间转换80

4.3 队列83

4.3.1 队列的定义83

4.3.2 循环队列--队列的顺序存储表示83

4.3.3 链式队列--队列的链接存储表示86

4.3.4 队列的应用举例--打印二项展开式(a+b)的系数87

4.4 优先级队列89

4.4.1 优先级队列的定义89

4.4.2 优先级队列的存储表示和实现90

小结91

习题92

第5章 递归94

本章要点94

5.1 递归的概念94

5.2 递归过程与递归工作栈98

5.2.1 递归工作栈98

5.2.2 用栈实现递归过程的非递归算法99

5.2.3 用迭代法实现递归过程101

5.3 用回潮法求解迷宫问题103

5.4 广义表107

5.4.1 广义表的概念108

5.4.2 广义表的表示及操作109

5.4.3 广义表存储结构的实现110

5.4.4 广义表的递归算法114

小结121

习题121

第6章 树与森林124

本章要点124

6.1 树和森林的概念124

6.1.1 树的定义124

6.1.2 树的术语125

6.1.3 树的抽象数据类型126

6.2 二叉树126

6.2.1 二叉树的定义126

6.2.2 二叉树的性质127

6.2.3 二叉树的抽象数据类型128

6.2.4 二叉树的表示129

6.3 遍历二叉树134

6.3.1 遍历二叉树的递归算法135

6.3.2 应用遍历二叉树的事例136

6.3.3 遍历二叉树的非递归算法138

6.3.4 二叉树的计数141

6.4 线索化二叉树144

6.4.1 线索144

6.4.2 中序线索化二叉树144

6.5 堆150

6.5.1 堆的定义150

6.5.2 堆的建立151

6.5.3 堆的插入与删除153

6.6 树与森林154

6.6.1 树的存储表示155

6.6.2 森林与二叉树的转换157

6.6.3 树的遍历158

6.6.4 森林的遍历160

6.7 霍夫曼树161

6.7.1 路径长度161

6.7.2 霍夫曼树162

6.7.3 霍夫曼编码164

小结165

习题166

第7章 集合与搜索169

本章要点169

7.1 集合及其表示169

7.1.1 集合基本概念169

7.1.2 用位向量实现集合抽象数据类型169

7.1.3 用有序链表实现集合的抽象数据类型172

7.1.4 并查集177

7.2 静态搜索表180

7.2.1 搜索的概念180

7.2.2 静态搜索结构181

7.2.3 顺序搜索183

7.2.4 基于有序顺序表的折半搜索185

7.3 二叉搜索树188

7.3.1 定义188

7.3.2 二叉搜索树上的搜索189

7.3.3 二叉搜索树的插入191

7.3.4 二叉搜索树的删除192

7.3.5 二叉搜索树的搜索效率194

7.4 AVL树196

7.4.1 AVL树的定义196

7.4.2 平衡化旋转197

7.4.3 AVL树的插入和删除200

7.4.4 AVL树的高度203

小结203

习题204

第8章 图207

本章要点207

8.1 图的基本概念207

8.1.1 图的基本概念207

8.1.2 图的抽象数据类型210

8.2 图的存储表示210

8.2.1 邻接矩阵211

8.2.2 邻接表213

8.2.3 邻接多重表217

8.3 图的遍历与连通性219

8.3.1 深度优先搜索220

8.3.2 广度优先搜索221

8.3.3 连通分量222

8.3.4 重连通分量224

8.3.5 图的遍历举例：欧拉回路问题225

8.4 最小生成树227

8.4.1 克鲁斯卡尔算法228

8.4.2 普里姆算法230

8.5 单源最短路径问题232

8.6 活动网络(activity network)235

8.6.1 用顶点表示活动的网络235

8.6.2 用边表示活动的网络239

小结243

习题244

本章要点247

9.1 概述247

第9章 排序247

9.2 插入排序249

9.2.1 直接插入排序249

9.2.2 折半插入排序251

9.2.3 链表插入排序251

9.2.4 希尔排序253

9.3 交换排序255

9.3.1 起泡排序255

9.3.2 快速排序256

9.4 选择排序259

9.4.1 直接选择排序260

9.4.2 锦标赛排序261

9.4.3 堆排序261

9.5.1 归并264

9.5 归并排序264

9.5.2 迭代的归并排序算法265

9.5.3 递归的链表归并排序267

9.6 基数排序268

9.6.1 多排序码排序269

9.6.2 链式基数排序270

9.7 外排序272

9.7.1 外排序的基本过程272

9.7.2 k路平衡归并与败者树274

9.7.3 初始归并段的生成277

9.7.4 最佳归并树279

小结281

习题282

10.1 静态索引结构285

10.1.1 线性索引285

本章要点285

第10章 索引与散列285

10.1.2 倒排表287

10.1.3 m路静态搜索树288

10.2 动态索引结构289

10.2.1 动态的m路搜索树289

10.2.2 B树291

10.2.3 B树的插入293

10.2.4 B树的删除295

10.2.5 B+树297

10.3 散列300

10.3.1 词典的抽象数据类型300

10.3.2 散列表与散列方法301

10.3.3 散列函数302

10.3.4 处理冲突的闭散列方法305

10.3.5 处理冲突的开散列方法--链地址法310

10.3.6 散列表分析312

10.4 可扩充散列313

10.4.1 二叉Trie树313

10.4.2 将二叉Trie树转换为目录表314

10.4.3 目录表扩充与收缩316

10.4.4 性能分析317

小结318

习题318

附录A 用C++描述面向对象程序322

A.1 用模板定义C++中的类322

A.2 类中成员函数的实现323

A.3 函数名重载和操作符重载327

A.4 C++中的主函数328

附录B 教学进度与习题安排参考329

附录C 词汇索引330

参考文献337