数据结构及应用 C语言描述PDF电子书下载

第一部分 概论 3

第1章 数据结构 3

1.1 什么是数据 3

1.2 什么是数据结构 3

1.2.1 数据的逻辑结构 3

1.2.2 数据的存储结构 4

1.2.3 数据的运算 5

1.3 什么是数据类型 5

1.4 知识点小结 6

习题 6

第2章 算法 7

2.1 什么是算法 7

2.2 算法的描述 7

2.3 算法分析 8

2.3.1 时间复杂度 8

2.3.2 渐近符号 9

2.3.3 空间复杂度 10

2.3.4 复杂度分析举例 10

2.4 知识点小结 13

习题 13

第二部分 预备知识第3章 C语言、递归及存储分配方式 16

3.1 C语言的相关内容 16

3.1.1 函数的参数传递与结果返回 16

3.1.2 结构体类型 17

3.1.3 指针 18

3.2 递归 18

3.3 存储分配方式 19

3.4 知识点小结 20

习题 20

第三部分 线性结构第4章 线性表 22

4.1 线性表的类型定义 22

4.1.1 线性表的逻辑结构 22

4.1.2 线性表的基本运算 22

4.2 线性表的顺序存储表示 23

4.2.1 顺序表 23

4.2.2 顺序表中基本运算的实现 24

4.3 线性表的链式存储表示 30

4.3.1 单链表 30

4.3.2 单链表中基本运算的实现 31

4.4 线性表的其他链式存储表示 38

4.4.1 静态单链表 38

4.4.2 双（向）链表 41

4.4.3 循环单（向）链表 43

4.4.4 循环双（向）链表 46

4.5 线性表的应用举例 47

4.6 顺序表和链表的比较 48

4.7 知识点小结 49

习题 49

第5章 栈 51

5.1 栈的类型定义 51

5.1.1 栈的逻辑结构 51

5.1.2 栈的基本运算 52

5.2 栈的顺序存储表示 52

5.2.1 顺序栈 52

5.2.2 顺序栈中基本运算的实现 53

5.3 栈的链式存储表示 55

5.3.1 链栈 55

5.3.2 链栈中基本运算的实现 55

5.4 两个方向生长的栈 56

5.5 栈的应用举例 57

5.6 知识点小结 61

习题 61

第6章 队列 63

6.1 队列的类型定义 63

6.1.1 队列的逻辑结构 63

6.1.2 队列的基本运算 63

6.2 队列的链式存储表示 64

6.2.1 链队列 64

6.2.2 链队列中基本运算的实现 65

6.3 队列的顺序存储表示 66

6.3.1 顺序队列 66

6.3.2 循环队列 69

6.3.3 循环队列中基本运算的实现 71

6.4 双端队列 74

6.5 队列的应用举例 74

6.6 知识点小结 75

习题 76

第7章 串 77

7.1 串的类型定义 77

7.1.1 串的逻辑结构 77

7.1.2 串的基本运算 77

7.2 串的顺序存储表示 78

7.3 串的堆分配存储表示 80

7.4 串的块链存储表示 81

7.5 串的模式匹配 82

7.6 知识点小结 88

习题 88

第8章 数组及广义表 89

8.1 数组的类型定义 89

8.1.1 数组的定义 89

8.1.2 数组的性质 89

8.1.3 数组的基本运算 89

8.2 数组的顺序存储表示 90

8.3 特殊矩阵的压缩存储 92

8.3.1 特殊形状矩阵的压缩存储 93

8.3.2 随机稀疏矩阵的压缩存储及其运算 95

8.4 广义表 104

8.4.1 广义表的基本概念 104

8.4.2 广义表的基本运算 105

8.4.3 广义表的存储结构 106

8.5 知识点小结 108

习题 108

第四部分 非线性结构第9章 树 110

9.1 概述 110

9.1.1 树的定义及基本术语 110

9.1.2 树的存储结构 112

9.2 二叉树 123

9.2.1 二叉树的定义 123

9.2.2 二叉树的性质 123

9.2.3 二叉树的存储结构 128

9.3 二叉树的遍历 132

9.3.1 遍历操作 132

9.3.2 先序遍历 132

9.3.3 中序遍历 133

9.3.4 后序遍历 134

9.3.5 层次遍历 135

9.3.6 二叉树遍历的应用举例 136

9.4 线索二叉树 144

9.4.1 二叉树的线索化 145

9.4.2 线索二叉树上的运算 149

9.5 二叉树的应用 156

9.5.1 哈夫曼树及其应用 156

9.5.2 二叉排序树 161

9.5.3 平衡二叉树 163

9.6 树、森林与二叉树的相互转换 166

9.6.1 树与二叉树的相互转换 166

9.6.2 森林与二叉树的相互转换 168

9.7 树、森林的遍历 169

9.7.1 树的遍历 169

9.7.2 森林的遍历 169

9.8 树的应用举例 170

9.9 知识点小结 171

习题 172

第10章 图 173

10.1 概述 173

10.1.1 图的定义及基本术语 173

10.1.2 图的存储结构 179

10.1.3 图的创建 184

10.2 图的遍历 187

10.2.1 深度优先搜索遍历 187

10.2.2 广度优先搜索遍历 191

10.2.3 图遍历的应用举例 193

10.3 生成树 194

10.3.1 连通图的生成树 194

10.3.2 连通网的最小生成树 195

10.4 最短路径 197

10.4.1 单源最短路径 197

10.4.2 每对顶点间的最短路径 201

10.5 有向无环图及其应用 205

10.5.1 AOV网与拓扑排序 205

10.5.2 AOE网与关键路径 207

10.6 知识点小结 209

习题 209

第五部分 两种重要运算第11章 查找 212

11.1 查找的基本概念 212

11.2 主要查找方法简介 213

11.3 静态查找 213

11.3.1 顺序查找 213

11.3.2 二分查找 215

11.3.3 分块查找 219

11.4 动态查找 220

11.5 散列查找 227

11.5.1 散列表的概念 228

11.5.2 散列函数的构造方法 228

11.5.3 处理冲突的方法 229

11.5.4 散列表的查找 232

11.6 知识点小结 234

习题 235

第12章 内排序 236

12.1 排序的基本概念 236

12.2 插入排序 237

12.2.1 直接插入排序 237

12.2.2 希尔排序 241

12.3 交换排序 242

12.3.1 冒泡排序 242

12.3.2 快速排序 244

12.4 选择排序 247

12.4.1 直接选择排序 247

12.4.2 树形选择排序 248

12.4.3 堆排序 249

12.5 归并排序 254

12.6 分配排序 255

12.6.1 箱排序 255

12.6.2 基数排序 255

12.7 各种内排序法的比较 257

12.8 知识点小结 257

习题 258

第六部分 文件的组织结构及排序第13章 文件 260

13.1 文件的基本概念 260

13.2 顺序文件 260

13.3 索引文件 261

13.4 索引顺序文件 262

13.5 散列文件 267

13.6 多关键字文件 268

13.7 知识点小结 268

习题 268

第14章 外排序 269

14.1 多路平衡归并 269

14.2 置换选择排序 272

14.3 归并树及最佳归并树 274

14.4 知识点小结 275

习题 275

参考文献 276