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

数据结构教程 第4版PDF格式电子书版下载

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

第1章 绪论1

1.1什么是数据结构1

1.1.1数据结构的定义1

1.1.2逻辑结构类型4

1.1.3存储结构类型6

1.1.4数据类型和数据结构7

1.2算法及其描述10

1.2.1什么是算法10

1.2.2算法描述11

1.3算法分析13

1.3.1算法设计的目标13

1.3.2算法效率分析13

1.3.3算法存储空间分析16

1.4数据结构+算法=程序17

1.4.1程序和数据结构17

1.4.2算法和程序17

1.4.3算法和数据结构17

1.4.4数据结构的发展23

本章小结24

练习题124

上机实验题126

第2章 线性表27

2.1线性表及其逻辑结构27

2.1.1线性表的定义27

2.1.2线性表的抽象数据类型描述28

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

2.2.1线性表的顺序存储结构——顺序表29

2.2.2顺序表基本运算的实现31

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

2.3.1线性表的链式存储结构——链表38

2.3.2单链表40

2.3.3双链表47

2.3.4循环链表51

2.4线性表的应用52

2.5有序表56

2.5.1有序表的抽象数据类型描述56

2.5.2有序表的存储结构及其基本运算算法57

2.5.3有序表的归并算法57

2.5.4有序表的应用59

本章小结61

练习题261

上机实验题261

第3章 栈和队列64

3.1栈64

3.1.1栈的定义64

3.1.2栈的顺序存储结构及其基本运算的实现66

3.1.3栈的链式存储结构及其基本运算的实现68

3.1.4栈的应用70

3.2队列80

3.2.1队列的定义80

3.2.2队列的顺序存储结构及其基本运算的实现81

3.2.3队列的链式存储结构及其基本运算的实现85

3.2.4队列的应用89

3.2.5双端队列93

本章小结95

练习题395

上机实验题396

第4章串99

4.1串的基本概念99

4.2串的存储结构100

4.2.1串的顺序存储结构——顺序串100

4.2.2串的链式存储结构——链串105

4.3串的模式匹配110

4.3.1 Brute-Force算法110

4.3.2 KMP算法112

本章小结119

练习题4119

上机实验题4119

第5章 递归121

5.1什么是递归121

5.1.1递归的定义121

5.1.2何时使用递归122

5.1.3递归模型123

5.1.4递归与数学归纳法124

5.2递归调用的实现原理125

5.3递归算法的设计127

5.3.1递归算法设计的步骤127

5.3.2递归数据结构的递归算法设计128

5.3.3递归求解方法的递归算法设计130

本章小结131

练习题5132

上机实验题5132

第6章 数组和广义表133

6.1数组133

6.1.1数组的基本概念133

6.1.2数组的存储结构134

6.1.3特殊矩阵的压缩存储136

6.2稀疏矩阵138

6.2.1稀疏矩阵的三元组表示138

6.2.2稀疏矩阵的十字链表表示141

6.3广义表145

6.3.1广义表的定义145

6.3.2广义表的存储结构147

6.3.3广义表的运算148

本章小结151

练习题6151

上机实验题6152

第7章 树和二叉树154

7.1树的基本概念154

7.1.1树的定义154

7.1.2树的逻辑表示方法155

7.1.3树的基本术语156

7.1.4树的性质157

7.1.5树的基本运算158

7.1.6树的存储结构159

7.2二叉树的基本概念162

7.2.1二叉树的定义162

7.2.2二叉树的性质163

7.2.3二叉树与树、森林之间的转换164

7.3二叉树的存储结构167

7.3.1二叉树的顺序存储结构167

7.3.2二叉树的链式存储结构168

7.4二叉树的基本运算及其实现169

7.4.1二叉树的基本运算概述169

7.4.2二叉树的基本运算算法实现169

7.5二叉树的遍历172

7.5.1二叉树遍历的概念172

7.5.2二叉树遍历递归算法173

7.5.3二叉树遍历非递归算法177

7.5.4层次遍历算法182

7.6二叉树的构造184

7.7线索二叉树189

7.7.1线索二叉树的概念189

7.7.2线索化二叉树191

7.7.3遍历线索化二叉树192

7.8哈夫曼树193

7.8.1哈夫曼树概述193

7.8.2哈夫曼树的构造算法194

7.8.3哈夫曼编码195

7.9用并查集求解等价问题197

7.9.1什么叫并查集197

7.9.2并查集的算法实现199

本章小结201

练习题7201

上机实验题7202

第8章图204

8.1图的基本概念204

8.1.1图的定义204

8.1.2图的基本术语205

8.2图的存储结构207

8.2.1邻接矩阵存储方法207

8.2.2邻接表存储方法208

8.3图的遍历211

8.3.1图的遍历的概念211

8.3.2深度优先遍历211

8.3.3广度优先遍历213

8.3.4非连通图的遍历214

8.3.5图遍历算法的应用215

8.4生成树和最小生成树223

8.4.1生成树的概念223

8.4.2无向图的连通分量和生成树224

8.4.3普里姆算法225

8.4.4克鲁斯卡尔算法227

8.5最短路径231

8.5.1路径的概念231

8.5.2从一个顶点到其余各顶点的最短路径231

8.5.3每对顶点之间的最短路径236

8.6拓扑排序240

8.7 AOE网与关键路径242

本章小结246

练习题8246

上机实验题8247

第9章 查找249

9.1查找的基本概念249

9.2线性表的查找250

9.2.1顺序查找250

9.2.2折半查找251

9.2.3索引存储结构和分块查找253

9.3树表的查找256

9.3.1二叉排序树256

9.3.2平衡二叉树264

9.3.3 B—树270

9.3.4 B+树275

9.4哈希表查找276

9.4.1哈希表的基本概念276

9.4.2哈希函数构造方法277

9.4.3哈希冲突解决方法278

9.4.4哈希表上的运算281

本章小结285

练习题9285

上机实验题9286

第10章 内排序287

10.1排序的基本概念287

10.2插入排序288

10.2.1直接插入排序288

10.2.2折半插入排序290

10.2.3希尔排序291

10.3交换排序293

10.3.1冒泡排序293

10.3.2快速排序295

10.4选择排序299

10.4.1直接选择排序299

10.4.2堆排序301

10.5归并排序305

10.6基数排序307

10.7各种内排序方法的比较和选择310

本章小结311

练习题10311

上机实验题10312

第11章 外排序313

11.1外排序概述313

11.2磁盘排序314

11.2.1生成初始归并段315

11.2.2多路平衡归并317

11.2.3最佳归并树320

11.3磁带排序322

11.3.1多路平衡归并排序322

11.3.2多阶段归并排序323

本章小结325

练习题11325

上机实验题11325

第12章 文件327

12.1文件的基本概念327

12.1.1什么是文件327

12.1.2文件的逻辑结构及操作328

12.1.3文件的存储结构328

12.2顺序文件328

12.3索引文件329

12.3.1 ISAM文件330

12.3.2 VSAM文件333

12.4哈希文件335

12.5多关键字文件335

12.5.1多重表文件335

12.5.2倒排文件336

本章小结337

练习题12337

上机实验题12337

第13章 采用面向对象的方法描述算法339

13.1面向对象的概念339

13.2用C++描述面向对象的程序341

13.2.1类341

13.2.2类对象343

13.2.3构造函数和析构函数344

13.2.4派生类347

13.3用C++描述数据结构算法349

13.3.1顺序表类349

13.3.2链栈类352

13.3.3二叉树类354

附录A综合实验题358

综合实验题1链表综合算法设计358

综合实验题2求复杂表达式的值358

综合实验题3用二叉树实现家谱的相关运算358

综合实验题4求无向图中满足约束条件的路径359

综合实验题5分析二分查找成功时的平均查找长度359

综合实验题6求各种排序算法的执行时间359

附录B实验报告格式360

附录C引用型参数的说明361

附录D顺序表、顺序栈和顺序队列使用指针引用型参数的说明363

附录E书中部分算法清单366

附录F全国计算机专业数据结构2012年联考大纲369

参考文献372