数据结构实用教程PDF电子书下载

第1章 绪论 1

1.1数据结构概述 1

1.1.1 基本概念 1

1.1.2数据结构 2

1.2算法 5

1.2.1算法的概念 5

1.2.2算法的描述 7

1.3 算法分析 11

1.3.1 时间复杂度 11

1.3.2空间复杂度 13

小结 13

知识巩固 13

实训演练 14

第2章线性表 16

2.1 线性表的定义及操作 16

2.1.1线性表的定义 16

2.1.2线性表的操作 17

2.2线性表运算 17

2.2.1顺序存储实现 18

2.2.2链式存储实现 21

2.2.3循环链表实现 24

2.2.4双向循环链表 25

2.2.5 顺序表与链表的比较 27

2.3经典应用实例 28

2.3.1 约瑟夫问题 28

2.3.2多项式求和 32

小结 37

知识巩固 38

实训演练 39

第3章 栈 41

3.1 栈的定义及基本运算 41

3.1.1 栈的定义 41

3.1.2栈的基本运算 42

3.2栈的顺序存储实现 42

3.2.1 栈的顺序存储 42

3.2.2栈的基本运算在顺序栈上的实现 43

3.2.3 栈的应用 44

3.3栈的链式存储实现 45

3.3.1栈的链式存储 45

3.3.2 栈的基本运算在链栈上的实现 45

3.4经典应用实例 46

3.4.1 数制转换 46

3.4.2表达式求值 48

小结 55

知识巩固 56

实训演练 57

第4章 队列 58

4.1 队列的定义及基本运算 58

4.1.1 队列的定义 58

4.1.2 队列的基本运算 59

4.2队列的顺序存储实现 59

4.2.1 队列的顺序存储 59

4.2.2 队列的基本运算在顺序存储上的实现 60

4.2.3循环队列 60

4.3 队列的链式存储实现 62

4.3.1 队列的链式存储 62

4.3.2 队列的基本运算在链式存储上的实现 63

4.4经典应用实例 64

4.4.1 迷宫问题 64

4.4.2模拟就诊过程 68

小结 72

知识巩固 72

实训演练 74

第5章 串 75

5.1 串的概念与操作 75

5.1.1 串的概念 75

5.1.2 串的操作 76

5.1.3 malloc（）和free（）函数 77

5.2 串的顺序存储结构与运算 78

5.2.1 串的顺序存储结构 78

5.2.2 串的基本运算及算法 78

5.2.3 常用的字符串处理函数 79

5.3 串的链式存储结构与运算 81

5.3.1 串的链式存储结构 81

5.3.2 串的基本运算 82

5.4经典应用实例 84

5.4.1 测试串的基本操作 84

5.4.2模式匹配 91

小结 94

知识巩固 94

实训演练 95

第6章 数组和广义表 97

6.1 数组 97

6.1.1 一维数组 97

6.1.2二维数组 98

6.1.3 多维数组 99

6.2矩阵的压缩存储 99

6.2.1 三角矩阵 99

6.2.2对称矩阵 101

6.2.3 稀疏矩阵 101

6.2.4带状矩阵 103

6.3 广义表 104

6.3.1 广义表的概念 104

6.3.2广义表的存储结构 104

6.3.3 广义表的运算 105

6.4经典应用实例 106

6.4.1 矩阵鞍点 106

6.4.2稀疏矩阵相加 108

小结 113

知识巩固 113

实训演练 114

第7章 树 115

7.1 树的定义及基本概念 115

7.1.1树的定义 115

7.1.2树的基本术语 116

7.1.3树的存储结构 117

7.2二叉树 118

7.2.1二叉树的定义 118

7.2.2二叉树的性质 118

7.2.3 二叉树的存储结构 120

7.3二叉树的遍历及算法 122

7.3.1 二叉树的遍历 122

7.3.2二叉树遍历算法 124

7.4树、森林与二叉树的转换 125

7.4.1树转换为二叉树 125

7.4.2森林转换为二叉树 126

7.4.3二叉树转换为树 128

7.4.4二叉树转换为森林 128

7.4.5树和森林的遍历 129

7.5 哈夫曼树 129

7.5.1 哈夫曼树及其构造 129

7.5.2哈夫曼树的应用 131

7.6经典应用实例 133

7.6.1二叉树的操作 133

7.6.2信息编码 136

小结 142

知识巩固 142

实训演练 143

第8章 图 145

8.1 基本概念 145

8.1.1 图的实际背景 145

8.1.2图的定义和术语 146

8.2图的存储结构 148

8.2.1 图的顺序存储——邻接矩阵 148

8.2.2图的链式存储——邻接表 150

8.3 图的遍历 151

8.3.1深度优先搜索遍历 151

8.3.2广度优先搜索遍历 152

8.4生成树 154

8.4.1最小生成树 154

8.4.2最小生成树算法 157

8.5 拓扑排序 159

8.5.1 拓扑排序的概念 159

8.5.2拓扑序列 160

8.5.3拓扑排序算法 160

8.6经典应用实例 161

8.6.1 最短路径 161

8.6.2教学计划编制 166

小结 169

知识巩固 169

实训演练 170

第9章 内部排序 172

9.1 基本概念 172

9.2插入排序 173

9.2.1直接插入排序 174

9.2.2折半插入排序 175

9.2.3希尔排序 176

9.3 交换排序 177

9.3.1 冒泡排序 177

9.3.2快速排序 179

9.4选择排序 180

9.4.1直接选择排序 181

9.4.2堆排序 182

9.5 归并排序 184

9.6基数排序 186

9.6.1多关键字排序 186

9.6.2链式基数排序 186

9.7经典应用实例 189

9.7.1考试成绩排序 189

9.7.2荷兰国旗问题 191

小结 193

知识巩固 194

实训演练 195

第10章 查找 197

10.1 基本概念 197

10.2线性表的查找 198

10.2.1 顺序查找 198

10.2.2二分查找 199

10.2.3分块查找 200

10.3树表的查找 201

10.3.1 二叉排序树查找 201

10.3.2平衡二叉树查找 203

10.4散列表查找 204

10.4.1散列表的概念 204

10.4.2散列函数的构造 205

10.4.3处理冲突的方法 206

10.4.4散列表的查找分析 207

10.5经典应用实例 207

10.5.1 模拟算法查询过程 208

10.5.2电话号码查询 211

小结 216

知识巩固 216

实训演练 218

参考文献 220