数据结构 C语言版 第2版PDF|Epub|txt|kindle电子书版本网盘下载

数据结构 C语言版 第2版PDF格式电子书版下载

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

第1章 绪论1

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

1.1.1为什么要学习数据结构1

1.1.2与数据结构相关的基本术语2

1.1.3数据结构的分类5

1.1.4数据结构的存储结构6

1.1.5定义在数据结构上的操作7

1.1.6“好”数据结构7

1.2使用C语言描述数据结构7

1.2.1 C语言的数据类型8

1.2.2算法的控制结构9

1.2.3算法的函数结构10

1.2.4动态存储分配12

1.2.5逻辑和关系运算的约定12

1.2.6输入与输出13

1.3算法和算法设计13

1.3.1算法的定义和特性13

1.3.2算法的设计步骤14

1.3.3算法设计的基本方法15

1.4算法分析与度量18

1.4.1算法的评价标准18

1.4.2算法的时间和空间复杂度度量18

1.4.3算法的渐近分析21

小结24

习题24

第2章 线性表27

2.1线性表27

2.1.1线性表的定义和特点27

2.1.2线性表的主要操作28

2.2顺序表29

2.2.1顺序表的定义和特点29

2.2.2顺序表的结构定义30

2.2.3顺序表查找操作的实现31

2.2.4顺序表插入和删除操作的实现32

2.2.5顺序表的应用：集合运算34

2.3单链表35

2.3.1单链表的定义和特点35

2.3.2单链表的结构定义36

2.3.3单链表中的插入与删除36

2.3.4带头结点的单链表40

2.3.5单链表的遍历与创建42

2.3.6单链表的应用：集合运算44

2.3.7循环链表46

2.3.8双向链表50

2.3.9静态链表53

2.4顺序表与线性链表的比较54

2.5线性表的应用：一元多项式及其运算56

2.5.1一元多项式的表示56

2.5.2多项式的结构定义57

2.5.3多项式的加法59

2.5.4扩展阅读：多项式的乘法60

小结62

习题63

第3章 栈和队列66

3.1栈66

3.1.1栈的概念66

3.1.2顺序栈67

3.1.3扩展阅读：多栈处理70

3.1.4链式栈73

3.1.5扩展阅读：栈的混洗74

3.2队列76

3.2.1队列的概念76

3.2.2循环队列76

3.2.3链式队列80

3.3栈的应用82

3.3.1数制转换82

3.3.2括号匹配83

3.3.3表达式的计算与优先级处理84

3.3.4栈与递归的实现88

3.4队列的应用91

3.5在算法设计中使用递归92

3.5.1汉诺塔问题与分治法92

3.5.2直接把递归过程改为非递归过程94

3.5.3扩展阅读：递归过程的非递归模拟算法95

3.5.4迷宫问题与回溯法98

3.5.5计算组合数与动态规划101

3.6扩展阅读：双端队列102

3.6.1双端队列的概念102

3.6.2输入受限的双端队列103

3.6.3输出受限的双端队列104

3.6.4双端队列的存储表示104

3.7扩展阅读：优先队列106

3.7.1优先队列的概念106

3.7.2优先队列的实现107

小结108

习题108

第4章 数组、串和广义表112

4.1数组112

4.1.1一维数组112

4.1.2多维数组114

4.2特殊矩阵的压缩存储116

4.2.1对称矩阵的压缩存储117

4.2.2三对角矩阵的压缩存储118

4.2.3扩展阅读：w对角矩阵的压缩存储119

4.3稀疏矩阵120

4.3.1稀疏矩阵的概念120

4.3.2稀疏矩阵的顺序存储表示121

4.3.3稀疏矩阵的链表表示124

4.4字符串125

4.4.1字符串的概念126

4.4.2字符串的初始化和赋值126

4.4.3自定义字符串的存储表示128

4.4.4串的模式匹配132

4.5广义表140

4.5.1广义表的概念140

4.5.2广义表的性质141

4.5.3广义表的链接表示141

4.5.4扩展阅读：三元多项式的表示147

小结148

习题149

第5章 树与二叉树152

5.1树的基本概念152

5.1.1树的定义和术语152

5.1.2树的基本操作154

5.2二叉树及其存储表示155

5.2.1二叉树的概念155

5.2.2二叉树的性质156

5.2.3二叉树的主要操作158

5.2.4二叉树的顺序存储表示159

5.2.5二叉树的链表存储表示160

5.3二叉树的遍历161

5.3.1二叉树遍历的递归算法162

5.3.2递归遍历算法的应用举例163

5.3.3二叉树遍历的非递归算法166

5.3.4利用队列实现二叉树的层次序遍历169

5.3.5非递归遍历算法的应用举例170

5.3.6二叉树的计数171

5.4线索二叉树174

5.4.1线索二叉树的概念174

5.4.2线索二叉树的种类175

5.4.3中序线索二叉树的建立和遍历176

5.4.4先序与后序线索二叉树178

5.5树与森林180

5.5.1树的存储表示180

5.5.2森林与二叉树的转换184

5.5.3树与森林的深度优先遍历185

5.5.4树与森林的广度优先遍历187

5.5.5树遍历算法的应用举例188

5.6 Huffman树190

5.6.1带权路径长度的概念190

5.6.2 Huffman树的概念191

5.6.3扩展阅读：最优判定树194

5.6.4 Huffman编码196

5.7堆198

5.7.1小根堆和大根堆198

5.7.2堆的建立199

5.7.3堆的插入201

5.7.4堆的删除202

5.8等价类与并查集202

5.8.1等价关系与等价类202

5.8.2确定等价类的方法203

5.8.3并查集的定义及其实现203

5.8.4并查集操作的分析和改进205

5.9扩展阅读：八皇后问题与树的剪枝207

5.9.1八皇后问题的提出207

5.9.2八皇后问题的状态树208

5.9.3八皇后问题算法210

小结211

习题212

第6章图216

6.1图的基本概念216

6.1.1与图有关的若干概念216

6.1.2图的基本操作219

6.2图的存储结构221

6.2.1图的邻接矩阵表示221

6.2.2图的邻接表表示225

6.2.3邻接矩阵表示与邻接表表示的比较229

6.2.4图的邻接多重表和十字链表表示230

6.3图的遍历231

6.3.1深度优先搜索232

6.3.2广度优先搜索234

6.3.3连通分量235

6.3.4双连通图237

6.3.5有向图的强连通分量238

6.4最小生成树240

6.4.1最小生成树求解和贪心法240

6.4.2 Kruskal算法242

6.4.3 Prim算法244

6.4.4扩展阅读：其他建立最小生成树的方法246

6.5最短路径248

6.5.1非负权值的单源最短路径248

6.5.2扩展阅读：边上权值为任意值的单源最短路径问题252

6.5.3所有顶点之间的最短路径254

6.5.4无权值的最短路径257

6.6活动网络259

6.6.1 AOV网络与拓扑排序259

6.6.2 AOE网络与关键路径法262

小结267

习题268

第7章 查找273

7.1查找的概念及简单查找方法273

7.1.1查找的基本概念273

7.1.2顺序查找法274

7.1.3折半查找法276

7.1.4扩展阅读：次优查找树279

7.1.5扩展阅读：斐波那契查找和插值查找282

7.1.6扩展阅读：跳表283

7.2二叉查找树284

7.2.1二叉查找树的概念285

7.2.2二叉查找树的查找285

7.2.3二叉查找树的插入286

7.2.4二叉查找树的删除288

7.2.5二叉查找树的性能分析289

7.3 AVL树292

7.3.1 AVL树的概念292

7.3.2平衡化旋转293

7.3.3 AVL树的插入295

7.3.4 AVL树的删除296

7.3.5 AVL树的性能分析299

7.4 B树300

7.4.1索引顺序表与分块查找300

7.4.2多级索引结构与m叉查找树301

7.4.3 B树的概念302

7.4.4 B树上的查找304

7.4.5 B树上的插入305

7.4.6 B树上的删除306

7.4.7 B＋树308

7.5扩展阅读：其他查找树311

7.5.1红黑树311

7.5.2伸展树313

7.5.3字典树315

7.6散列表及其查找317

7.6.1散列的概念318

7.6.2常见的散列函数318

7.6.3解决冲突的开地址法321

7.6.4解决冲突的链地址法327

7.6.5散列法分析329

小结330

习题330

第8章 排序335

8.1排序的概念335

8.1.1排序的相关概念335

8.1.2排序算法的性能分析336

8.1.3数据表的结构定义337

8.2插入排序338

8.2.1直接插入排序338

8.2.2基于静态链表的直接插入排序339

8.2.3折半插入排序341

8.2.4希尔排序342

8.3交换排序343

8.3.1起泡排序344

8.3.2快速排序345

8.3.3快速排序的改进算法348

8.4选择排序350

8.4.1简单选择排序350

8.4.2锦标赛排序351

8.4.3堆排序352

8.5归并排序356

8.5.1二路归并排序的设计思路356

8.5.2二路归并排序的递归算法356

8.5.3扩展阅读：基于链表的归并排序算法358

8.5.4扩展阅读：迭代的归并排序算法359

8.6基数排序361

8.6.1基数排序362

8.6.2 MSD基数排序362

8.6.3 LSD基数排序364

8.7内排序算法的分析和比较367

8.7.1排序方法的下界367

8.7.2各种内排序方法的比较368

8.8外排序371

8.8.1常用的外存储器与缓冲区371

8.8.2基于磁盘的外排序过程372

8.8.3 m路平衡归并的过程374

8.8.4初始归并段的生成378

8.8.5最佳归并树381

8.8.6磁带归并排序382

小结385

习题386

附录A实训作业要求与样例391

A.1实训作业要求391

A.2实训作业样例392

附录B词汇索引397

参考文献405