数据结构 C++描述PDF电子书下载

第1章 概论 1

1.1 数据结构课程的研究内容 1

1.1.1 从几个程序设计问题的讨论开始 1

1.1.2 用计算机解决实际问题的过程 5

1.1.3 学习数据结构课程的意义 8

1.2 基本术语 9

1.3 算法描述及分析 10

1.3.1 算法描述语言概述 10

1.3.2 算法分析 11

本章小结 12

习题 13

第2章 栈 14

2.1 栈的定义和运算 14

2.1.1 基本概念 14

2.1.2 栈的运算 15

2.2 顺序栈 18

2.2.1 栈的顺序存储结构 18

2.2.2 顺序栈的C＋＋描述 18

2.2.3 顺序栈上运算的实现 19

2.3 栈的应用实例 21

本章小结 24

习题 24

第3章 顺序队列 26

3.1 队列的定义和运算 26

3.1.1 基本概念 26

3.1.2 队列的运算 26

3.2 顺序队列与循环队列 28

3.2.1 存储结构 29

3.2.2 顺序队列中实现运算的讨论 29

3.2.3 队列的应用概述 32

本章小结 33

习题 34

第4章 链栈和链队列 35

4.1 链表结构 35

4.1.1 指针与动态变量 35

4.1.2 链表基本结构 37

4.2 链栈 38

4.2.1 链栈的存储结构 39

4.2.2 链栈的运算实现 39

4.3 链队列 42

4.3.1 链队列的存储结构 42

4.3.2 链队列的运算实现 43

本章小结 45

习题 45

第5章 线性表 46

5.1 线性表的定义和运算 46

5.1.1 线性表的定义 46

5.1.2 线性表的运算 47

5.2 顺序表 49

5.2.1 线性表的顺序存储结构 49

5.2.2 顺序表运算的实现 49

5.2.3 顺序表的应用 52

5.3 链表 55

5.3.1 线性表的链表存储结构 55

5.3.2 链表运算的实现 57

5.3.3 其他形式的链表结构 66

5.4 串 69

5.4.1 串的定义和运算 69

5.4.2 串的存储 69

本章小结 71

习题 72

第6章 递归 73

6.1 引言 73

6.2 递归程序的定义及其一般形式 74

6.2.1 递归程序的定义 74

6.2.2 递归程序的一般形式 75

6.3 递归调用的内部实现原理 75

6.3.1 一般函数的内部实现 75

6.3.2 递归调用的内部实现原理 77

6.4 递归程序的阅读 79

6.5 递归程序的正确性证明和编写 81

6.5.1 递归程序的正确性证明 81

6.5.2 递归程序的编写 83

6.6 递归的模拟 84

6.7 递归技术应用 91

本章小结 95

习题 95

第7章 数组和广义表 99

7.1 数组 99

7.1.1 数组的定义和运算 99

7.1.2 数组的顺序存储 100

7.1.3 矩阵的压缩存储 101

7.2 广义表 103

7.2.1 广义表的基本概念 103

7.2.2 广义表的基本运算 104

7.2.3 广义表的存储 105

本章小结 106

习题 106

第8章 树 108

8.1 树 108

8.2 二叉树 110

8.2.1 二叉树的基本概念 110

8.2.2 二叉树的性质 111

8.2.3 二叉树的存储结构 113

8.3 二叉树的遍历 114

8.3.1 遍历算法的实现 115

8.3.2 二叉树遍历算法的应用 119

8.4 线索二叉树 121

8.4.1 线索二叉树结构 121

8.4.2 线索二叉树中前驱后继的求解 123

8.5 树和森林 125

8.5.1 树的存储结构 125

8.5.2 树（森林）与二叉树的转换 128

8.5.3 树（森林）的遍历 130

8.6 哈夫曼树 131

8.6.1 问题描述及求解方法 132

8.6.2 应用实例 135

本章小结 136

习题 136

第9章 图 140

9.1 基本概念 140

9.2 图的存储结构 143

9.2.1 邻接矩阵表示 143

9.2.2 邻接表表示 144

9.3 图的遍历算法及其应用 146

9.3.1 深度优先搜索遍历算法及其应用 146

9.3.2 广度优先搜索遍历算法及其应用 151

9.4 最小生成树 154

9.4.1 Prim算法 155

9.4.2 Kruskal算法 159

9.5 有向无环图 161

9.5.1 拓扑排序 161

9.5.2 关键路径 164

9.6 最短路径 168

9.6.1 从单个顶点到其余各顶点之间的最短路径 168

9.6.2 各顶点之间的最短路径 172

本章小结 175

习题 175

第10章 查找 178

10.1 概述 178

10.2 顺序表的查找 179

10.2.1 简单顺序查找 179

10.2.2 有序表的二分查找 180

10.2.3 索引顺序表的查找 183

10.3 树表的查找 183

10.3.1 二叉排序树及其查找 184

10.3.2 平衡二叉树 186

10.4 散列表的查找 191

10.4.1 散列表的基本概念 191

10.4.2 散列函数的构造方法 192

10.4.3 处理冲突的方法 193

10.4.4 散列表的查找 195

本章小结 195

习题 196

第11章 排序 198

11.1 概述 198

11.1.1 排序及其分类 198

11.1.2 排序算法的分析指标 199

11.2 插入排序 199

11.2.1 直接插入排序 199

11.2.2 希尔排序 201

11.3 交换排序 203

11.3.1 冒泡排序 203

11.3.2 快速排序 204

11.4 选择排序 207

11.4.1 直接选择排序 207

11.4.2 堆排序 208

11.5 归并排序 213

11.5.1 归并 213

11.5.2 归并排序 213

本章小结 214

习题 215