数据结构教程 用C++实现的方法PDF电子书下载

第1章 绪论 1

1.1 数据结构课程内容及其意义 1

1.2 基本概念及术语 1

1.3 抽象数据类型及面向对象概念 2

1.4 复型数据类型 5

1.5 程序设计方法及语言 5

1.6 算法与算法分析 5

1.7 递归函数 7

习题一 9

第2章 C++面向对象程序设计要点 10

2.1 C++的函数 10

2.1.1 函数类型 10

2.1.2 函数名的重载 10

2.1.3 函数参数 11

2.1.4 成员函数的返回值 12

2.2 输入和输出 13

2.2.1 键盘屏幕输入输出方式 13

2.2.2 文件输入输出 14

2.3 C++的类 15

2.3.1 构造函数和析构函数 17

2.3.2 操作符重载 18

2.3.3 友元 18

2.3.4 分辨符 19

2.3.5 内联函数 19

2.3.6 默认值 19

2.3.7 多态性和虚函数 19

2.3.8 纯虚函数和抽象类 21

2.3.9 派生类继承方式 21

2.3.10 结构体 22

2.3.11 对象 22

2.4 抽象类型和模板 22

2.4.1 抽象类型 22

2.4.2 模板 23

习题二 23

第3章 线性表 25

3.1 线性表的抽象数据类型 25

3.2 线性表的顺序表示与实现 26

3.3 线性表的链式表示与实现 29

3.3.1 单链表(Singly Linked List) 30

3.3.2 循环链表 35

3.3.3 双向链表 35

3.4 一元多项式 37

习题三 40

第4章 栈和队列 42

4.1 栈 42

4.1.1 栈的抽象数据类型 42

4.1.2 顺序栈的表示与实现 43

4.1.3 链式栈的表示与实现 45

4.1.4 栈的应用——表达式计算 48

4.2 队列 52

4.2.1 队列的抽象数据类型 52

4.2.2 顺序队列的表示与实现 53

4.2.3 链式队列的表示与实现 56

4.2.4 队列的应用 57

4.2.5 优先级队列(Priority Queue) 59

习题四 60

第5章 数组、广义表和串 62

5.1 数组 62

5.1.1 一维数组 62

5.1.2 二维数组 62

5.2 特殊矩阵的压缩存储 64

5.2.1 对称矩阵 64

5.2.2 对角矩阵 65

5.3 稀疏矩阵的压缩存储 65

5.3.1 稀疏矩阵的三元组 65

5.3.2 三元组顺序表表示 66

5.3.3 三元组十字链表表示 72

5.4 广义表 72

5.4.1 广义表的概念 72

5.4.2 广义表的抽象数据类型 73

5.4.3 广义表的的存储结构 74

5.5 字符串 75

5.5.1 字符串抽象数据类型定义 75

5.5.2 字符串的存储结构 76

习题五 79

第6章 树和二叉树 80

6.1 树 80

6.1.1 树的定义和术语 80

6.1.2 树的表示形式 81

6.1.3 树的抽象数据类型 82

6.2 二叉树 83

6.2.1 二叉树的定义 83

6.2.2 二叉树的性质 83

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

6.2.4 二叉树的存储结构 85

6.3 二叉树的遍历 90

6.3.1 先序遍历 91

6.3.2 中序遍历 91

6.3.3 后序遍历 92

6.3.4 层次遍历 92

6.4 线索二叉树 93

6.4.1 中序线索化二叉树 95

6.5 树和森林 98

6.5.1 森林与二叉树的转换 98

6.5.2 树和森林遍历 99

6.6 哈夫曼树和应用 100

6.6.1 路径长度和哈夫曼树 100

6.6.2 哈夫曼编码 102

6.6.3 算法实现 102

习题六 106

第7章 图 109

7.1 图的基本概念及抽象数据类型 109

7.1.1 图的基本概念 109

7.1.2 图的抽象数据类型 112

7.2 图的存储结构 112

7.2.1 邻接矩阵 112

7.2.2 邻接表 115

7.2.3 邻接多重表 118

7.2.4 十字链表 118

7.3 图的遍历与连通性 119

7.3.1 深度优先搜索 119

7.3.2 广度优先搜索 121

7.3.3 连通分量 122

7.4 最小生成树 124

7.4.1 克鲁斯卡尔(Kruskal)算法 124

7.4.2 普里姆(Prim)算法 126

7.5 最短路径 128

7.5.1 从某源点到其余各定点的最短路径 129

7.5.2 每对顶点之间的最短路径 131

7.6 拓扑排序与关键路径 133

7.6.1 拓扑排序 134

7.6.2 关键路径 137

习题七 141

第8章 集合和查找 143

8.1 集合的抽象数据类型 143

8.2 集合的位向量表示及查找 144

8.3 集合的顺序表示及查找 146

8.3.1 无序顺序表查找 146

8.3.2 有序顺序表查找 148

8.4 集合的树结构表示及查找 153

8.4.1 二叉排序树 153

8.4.2 平衡二叉树 158

8.5 哈希方法 159

8.5.1 哈希函数的构造 159

8.5.2 冲突处理 161

8.5.3 基本集合操作实现 162

习题八 164

第9章 排序 166

9.1 排序的基本概念 166

9.2 插入排序 168

9.2.1 直接插入排序 168

9.2.2 折半插入排序 169

9.2.3 链表插入排序 170

9.2.4 希尔排序 172

9.3 交换排序 173

9.3.1 冒泡排序 173

9.3.2 快速排序 174

9.4 选择排序 177

9.4.1 直接选择排序 177

9.4.2 堆排序 178

9.5 归并排序 183

9.6 基数排序 185

9.6.1 多关键字排序 185

9.6.2 链式基数排序 186

习题九 189

第10章 文件 191

10.1 基本术语与概念 191

10.2 顺序文件 192

10.3 直接存取文件(Hash文件) 193

10.4 索引文件 195

10.4.1 B树 196

10.4.2 B+树 203

10.4.3 R树 205

10.5 多关键字文件 209

10.5.1 倒排文件 209

10.5.2 多重表文件 210

习题十 211

参考文献 213