数据结构PDF电子书下载

第1章 绪论 1

1.1 引言 1

1.2 数据结构中的基本概念和术语 4

1.3 算法和算法描述 12

1.3.1 算法的概念 12

1.3.2 算法的描述方法 13

1.4 算法的评价方法 16

1.4.1 评价算法的一般原则 16

1.4.2 算法的复杂度 17

1.5 C＋＋中的typedef、模板与异常处理 24

本章小结和学习要点 33

习题1 34

思考题1 36

上机题1 36

第2章 线性表 37

2.1 线性表及其基本操作 37

2.1.1 线性表的逻辑结构定义 37

2.1.2 线性表的抽象数据类型定义 38

2.2 线性表的顺序存储结构——顺序表 40

2.2.1 顺序表的基本表示 40

2.2.2 顺序表模板类表示下的基本操作 44

2.2.3 顺序表表示线性表下的其他操作 49

2.2.4 间接寻址方式及其他方式实现的顺序表 56

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

2.3.1 单链表 56

2.3.2 循环单链表 67

2.3.3 双链表及循环双链表 68

2.3.4 静态链表 71

2.3.5 间接寻址方式实现的单链表 73

2.4 线性表的应用 73

2.4.1 一元多项式的表示及相加 73

2.4.2 算法举例 77

2.5 顺序表和单链表的比较 82

2.5.1 时间性能比较 82

2.5.2 空间性能比较 82

本章内容小结和学习要点 83

习题2 84

思考题2 88

上机题2 88

第3章 栈和队列 89

3.1 栈 89

3.1.1 栈的逻辑结构 89

3.1.2 栈的顺序存储结构——顺序栈 91

3.1.3 栈的链式存储结构 96

3.2 队列 99

3.2.1 队列的逻辑结构 99

3.2.2 队列的链式存储结构 102

3.2.3 队列的顺序存储结构 106

3.3 栈和队列的综合应用 115

3.3.1 算术表达式求值 115

3.3.2 用顺序栈作辅助存储结构求迷宫的一条路径解 124

本章内容小结和学习要点 126

习题3 126

思考题3 128

上机题3 129

第4章 字符串 130

4.1 串及其运算 130

4.2 串的顺序存储结构 134

4.3 串的链式存储结构 137

4.4 串的模式匹配算法 138

4.5 串的应用 149

4.5.1 大整数加法 149

4.5.2 名字特征数 152

本章小结和学习要点 153

习题4 153

思考题4 154

上机题4 154

第5章 数组和广义表 155

5.1 数组的寻址和运算 155

5.2 矩阵的压缩存储 159

5.2.1 特殊矩阵 160

5.2.2 稀疏矩阵 163

5.3 广义表 170

5.3.1 广义表的概念 170

5.3.2 广义表的存储结构 172

5.3.3 广义表的操作 174

本章小结和学习要点 178

习题5 178

思考题5 180

上机题5 180

第6章 树和二叉树 182

6.1 树的基本定义 182

6.2 二叉树 186

6.2.1 二叉树的定义和基本运算 187

6.2.2 二叉树的性质 189

6.2.3 二叉树的存储结构 192

6.3 二叉树的建立和遍历 197

6.3.1 遍历二叉树 197

6.3.2 建立和释放一棵二叉树的二叉链表 202

6.3.3 二叉链表其他函数和主函数 204

6.3.4 二叉树的三种遍历的非递归算法 206

6.3.5 二叉树的其他算法例 210

6.4 线索二叉树 213

6.5 树和森林 219

6.6 哈夫曼树及其应用 228

本章小结和学习要点 237

习题6 237

思考题6 242

上机题6 242

第7章 图的数据结构 243

7.1 图的定义、基本术语和操作 243

7.2 图的存储结构 248

7.2.1 邻接矩阵 248

7.2.2 边数组 252

7.2.3 邻接表 252

7.2.4 图的十字链表表示 258

7.2.5 邻接多重表 260

7.3 图的遍历 262

7.3.1 深度优先搜索遍历图 262

7.3.2 广度优先搜索遍历图 266

7.3.3 图的遍历 268

7.4 图的连通性和生成树 270

7.4.1 图的连通性和连通分量 270

7.4.2 生成树和生成森林 272

7.4.3 最小生成树 274

7.5 最短路径问题 283

7.5.1 求某个源点到其余各顶点的最短路径 283

7.5.2 求带权图中每一对顶点之间的最短路径 288

7.6 拓扑排序 291

7.7 求关键路径 298

7.8 图的遍历算法的应用 305

7.8.1 求过给定点v长度大于或等于k的简单有向回路 305

7.8.2 地图四色问题 306

本章小结和学习要点 308

习题7 308

思考题7 313

上机题7 313

第8章 排序 315

8.1 排序的基本概念和术语 315

8.2 插入排序 318

8.2.1 直接插入排序 318

8.2.2 谢尔排序 322

8.3 选择排序 324

8.3.1 简单选择排序 325

8.3.2 改进的简单选择排序 326

8.3.3 堆排序 327

8.4 交换排序 333

8.4.1 冒泡排序 333

8.4.2 快速排序 335

8.5 归并排序 340

8.6 基数排序 342

8.7 各种内部排序算法的比较 346

本章小结和学习要点 349

习题8 350

思考题8 355

上机题8 355

第9章 查找 356

9.1 查找的基本概念和术语 356

9.2 以顺序表为基础的查找 358

9.2.1 顺序表的顺序查找 358

9.2.2 有序表的二分法查找 361

9.2.3 静态树表的查找 366

9.2.4 分块查找 370

9.3 树形结构的查找 373

9.3.1 二叉排序树 373

9.3.2 平衡二叉树 383

9.4 散列表的查找 391

9.4.1 散列技术中的主要概念 391

9.4.2 散列函数的构造方法 392

9.4.3 冲突的处理方法 396

9.4.4 散列表上的查找算法 400

9.4.5 散列表查找的时间复杂度分析 400

本章小结和学习要点 405

习题9 405

思考题9 408

上机题9 408

第10章 索引技术 409

10.1 索引的基本概念 409

10.2 线性索引 410

10.2.1 稠密索引 410

10.2.2 稀疏索引 411

10.2.3 多重表 413

10.2.4 倒排表 413

10.3 树形索引 415

10.3.1 B－树 415

10.3.2 B＋树 424

10.3.3 键树 425

本章内容小结和学习要点 432

习题10 432

思考题10 434

上机题10 434

主要参考文献 435

附录 上机实验报告格式 437

索引 439