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

第1章 概论 1

1.1 数据结构的基本概念 1

1.2 数据结构的基本术语 2

1.3 算法描述 7

1.4 算法分析 8

1.4.1 时间复杂度 9

1.4.2 空间复杂度 9

小结 10

习题 10

第2章 C语言基础知识 14

2.1 基本语法 14

2.1.1 程序的基本结构 14

2.1.2 数据表示 14

2.1.3 常量和变量 15

2.1.4 运算符和表达式 16

2.1.5 语句分类 18

2.2 结构化程序设计和函数 18

2.2.1 结构化程序设计 18

2.2.2 函数的基本概念 19

2.2.3 函数的递归调用 22

2.3 基本控制结构 23

2.3.1 分支结构 23

2.3.2 循环程序设计 24

2.4 数组的定义及使用 25

2.4.1 数组的基本概念 25

2.4.2 数组的定义及引用 26

2.4.3 字符数组和字符串 27

2.5 指针 27

2.5.1 指针的概念和使用 27

2.5.2 指针和动态内存分配 29

2.5.3 指针和一维数组 31

2.5.4 指针与函数 34

2.5.5 指针与字符串 38

2.6 结构体 39

2.6.1 结构体类型定义及引用 39

2.6.2 结构体和数组 41

2.6.3 结构体和指针 42

2.6.4 枚举和自定义类型 43

小结 44

习题 44

第3章 线性表 49

3.1 线性表的概念及运算 49

3.1.1 线性表的逻辑结构 49

3.1.2 线性表的运算 50

3.2 线性表的顺序表示 52

3.2.1 顺序表的定义 52

3.2.2 顺序表的基本运算 54

3.3 线性表的链式表示 57

3.3.1 线性链表 57

3.3.2 循环链表 63

3.3.3 双向链表 64

3.4 顺序表和链表的比较 65

3.5 串 66

3.5.1 串的基本概念及运算 66

3.5.2 串的存储结构 68

3.5.3 串的模式匹配算法 71

小结 76

习题 77

第4章 栈和队列 81

4.1 栈 81

4.1.1 栈的概念及运算 81

4.1.2 栈的表示 82

4.2 栈的应用举例 85

4.2.1 简单应用 85

4.2.2 数制转换 86

4.2.3 表达式求值 87

4.2.4 迷宫的求解 90

4.3 栈与递归 94

4.4 队列 95

4.4.1 队列的概念及运算 95

4.4.2 顺序队列 96

4.4.3 链队列 100

4.5 队列的应用举例 102

小结 104

习题 105

第5章 多维数组和广义表 108

5.1 数组的定义 108

5.2 数组的表示 108

5.3 矩阵的压缩存储 110

5.3.1 特殊矩阵 110

5.3.2 稀疏矩阵 112

5.4 广义表的概念 121

5.5 广义表的存储 122

5.5.1 头尾表示法 122

5.5.2 孩子兄弟表示法 123

5.5.3 广义表的运算 124

小结 127

习题 127

第6章 树 131

6.1 树的概念 131

6.1.1 树的定义 131

6.1.2 树的表示方法 132

6.2 二叉树 133

6.2.1 二叉树的概念 133

6.2.2 二叉树的性质 135

6.2.3 二叉树的存储 136

6.2.4 二叉树的基本操作及实现 139

6.3 二叉树的遍历 141

6.3.1 先序遍历二叉树 141

6.3.2 中序遍历二叉树 142

6.3.3 后序遍历二叉树 142

6.3.4 层次遍历 142

6.3.5 二叉树遍历的非递归实现 143

6.3.6 由遍历序列恢复二叉树 146

6.4 线索二叉树 148

6.4.1 线索二叉树的定义及结构 148

6.4.2 线索二叉树的基本操作实现 150

6.5 树和森林 155

6.5.1 树、森林与二叉树的转换 155

6.5.2 树的存储结构 157

6.5.3 树的遍历 161

6.5.4 森林的遍历 162

6.6 哈夫曼树及其应用 162

6.6.1 哈夫曼树 162

6.6.2 哈夫曼编码 165

小结 167

习题 168

第7章 图 173

7.1 图的概念 173

7.1.1 图的基本概念 173

7.1.2 图的基本操作 176

7.2 图的存储结构 176

7.2.1 邻接矩阵表示法 176

7.2.2 邻接表表示法 178

7.2.3 十字链表表示法 180

7.3 图的遍历 182

7.3.1 深度优先搜索遍历 182

7.3.2 广度优先搜索遍历 184

7.4 生成树和最小生成树 185

7.4.1 生成树 185

7.4.2 最小生成树 187

7.5 有向无环图及其应用 192

7.5.1 拓扑排序 194

7.5.2 关键路径 198

7.6 最短路径 202

7.6.1 单源最短路径 202

7.6.2 所有顶点对之间的最短路径 205

小结 207

习题 207

第8章 排序 211

8.1 基本概念 211

8.2 插入排序 212

8.2.1 直接插入排序 212

8.2.2 希尔排序 213

8.3 交换排序 215

8.3.1 冒泡排序 215

8.3.2 快速排序 216

8.4 选择排序 219

8.4.1 直接选择排序 219

8.4.2 堆排序 219

8.5 归并排序 222

8.5.1 2-路归并的迭代算法 223

8.5.2 2-路归并的递归算法 223

8.6 基数排序 224

8.6.1 多关键字排序 224

8.6.2 链式基数排序 225

8.7 内部排序方法的比较 228

8.8 外部排序简介 230

小结 233

习题 233

第9章 查找 239

9.1 基本概念 239

9.2 线性表的查找 240

9.2.1 顺序查找 240

9.2.2 二分查找 241

9.2.3 分块查找 243

9.3 树表的查找 245

9.3.1 二叉排序树 245

9.3.2 平衡二叉树 250

9.3.3 B-树 255

9.4 散列表的查找 260

9.4.1 散列表 260

9.4.2 散列函数的构造方法 261

9.4.3 冲突处理的方法 263

9.4.4 散列表的查找及分析 265

小结 265

习题 266

第10章 文件 269

10.1 文件的基本概念 269

10.1.1 文件及其类别 269

10.1.2 文件的操作 270

10.1.3 文件的结构 271

10.2 顺序文件 271

10.3 索引文件 272

10.4 索引顺序文件 274

10.4.1 ISAM文件 274

10.4.2 VSAM文件 276

10.5 散列文件 279

10.6 多关键字文件 279

10.6.1 多重表文件 280

10.6.2 倒排文件 281

小结 281

习题 282

附录A 习题参考答案 283

参考文献 313