数据结构教程 C语言版PDF电子书下载

前言 1

第1章 概述 1

1．1 什么是数据结构 1

1．2 基本概念及术语 2

1．3 数据的存贮结构 4

1．3．1 顺序存贮结构 4

1．3．2 链式存贮结构 5

1．4 关于算法的描述及算法分析的说明 6

小结 6

练习题 7

2．1．2 线性表的运算 8

2．1．1 线性表的定义 8

2．1 线性表 8

第2章 线性数据结构 8

2．1．3 线性表的顺序存贮结构 9

2．1．4 线性表的链式存贮结构 16

2．2 栈 31

2．2．1 栈的定义 31

2．2．2 栈的基本运算 32

2．2．3 栈的存贮结构 32

2．2．4 栈的应用 36

2．3 队列 39

2．3．1 队列的定义 39

2．3．2 队列的基本运算 39

2．3．3 队列的存贮结构 39

2．3．4 队列的应用 46

2．4．1 特殊矩阵 50

2．4 矩阵的压缩存贮 50

2．4．2 稀疏矩阵 52

2．4．3 稀疏矩阵的十字链表 60

小结 70

练习题 71

第3章 树和二叉树 74

3．1 树的定义和基本术语 74

3．2 树的存贮结构和线性表示 76

3．2．1 树的存贮结构 76

3．2．2 树的线性表示 77

3．2．3 树的遍历 92

3．3．1 二叉树的定义和存贮结构 96

3．3 二叉树 96

3．3．2 二叉树的基本性质 97

3．3．3 几中特殊的二叉树 98

3．3．4 二叉树存贮结构的建立 100

3．4 二叉树的遍历和线索化 108

3．4．1 二叉树的递归遍历算法 109

3．4．2 二叉树的非递归遍历算法 109

3．4．3 遍历算法的应用 114

3．4．4 二叉树的线索化 118

3．5 树向二叉树的转换 125

3．6 树的应用 131

小结 139

练习题 141

4．1 图的基本术语 144

第4章 图 144

4．2 图的存贮结构 146

4．2．1 邻接矩阵 146

4．2．2 邻接表 151

4．3 图的遍历 154

4．3．1 深度优先搜索 155

4．3．2 广度优先搜索 160

4．3．3 图遍历算法的应用 162

4．4 最小生成树 169

4．5 单源最短路径 173

4．6 拓扑排序 177

4．7 关键路径 180

练习题 187

小结 187

第5章 查找 190

5．1 查找的基本概念 190

5．2 线性表的查找 191

5．2．1 顺序查找 191

5．2．2 二分查找 193

5．2．3 分块查找 195

5．3 排序树的查找 198

5．3．1 二叉排序树 198

5．3．2 丰满二叉树 206

5．3．3 平衡二叉树 207

小结 208

练习题 209

6．2．1 简单选择排序 211

6．2 选择排序 211

6．1 排序的基本概念 211

第6章 排序 211

6．2．2 堆排序 213

6．3 插入排序 217

6．3．1 直接插入排序 217

6．3．2 二分插入排序 218

6．3．3 希尔（shell）排序 219

6．4 交换排序 220

6．4．1 冒泡排序 220

6．4．2 快速排序 221

6．5 归并排序 223

6．5．1 有序文件的归并 223

6．5．2 归并排序 224

6．6 基数排序 225

6．7 各种排序方法的选择与使用 230

小结 230

第7章 文件 234

7．1 外存贮器 234

7．1．1 磁带机 235

7．1．2 磁盘机 235

7．1．3 硬盘驱动器 236

7．2 文件的特性及基本概念 236

7．3 顺序文件 237

7．4 索引文件 238

7．5 随机存取文件 239

练习题 240

参考文献 241