数据结构PDF电子书下载

第一章 绪论 1

1.1 引言 1

1.2 什么是数据结构 2

1.3 关于算法语言和算法分析的说明 3

第二章 线性表和向量 6

2.1 线性表及其存贮结构 6

2.1.1 线性表 6

2.1.2 对线性表的运算 7

2.1.3 线性表的存贮结构 7

2.1.4 线性表的插入和删除 8

2.2 栈和队列 11

2.2.1 栈 11

2.2.2 计算表达式——栈的应用举例 16

2.2.3 队列 18

2.3 数组 21

2.3.1 数组的顺序分配 21

2.3.2 稀疏矩阵的一种表示法 23

2.4 一个迷宫问题 29

第三章 链表 34

3.1 线性链表 34

3.2 带链的栈和队列 38

3.3 多项式相加问题 40

3.4 循环链表 43

3.5 多重链表 44

3.5.1 双重链表和动态存贮分配 45

3.5.2 十字链表和稀疏矩阵 50

3.6 广义表 53

4.2 串的运算 57

第四章 串 57

4.1 什么是串 57

4.2.1 联接 58

4.2.2 求子串 58

4.2.3 求串的长度 59

4.2.4 求子串在串中的序号 59

4.2.5 置换 59

4.3 串的存贮结构 61

4.3.1 串值——字符序列的存贮 61

4.3.2 串变量的存贮映象 62

4.4 文本编辑 64

第五章 树 67

5.1 基本术语 67

5.2 树的存贮结构 68

5.3.1 二叉树的性质 69

5.3 二叉树 69

5.3.2 二叉树的存贮结构 72

5.3.3 树的二叉树表示 73

5.3.4 森林和二叉树间的转换 74

5.4 遍历二叉树 76

5.5 线索树 79

5.6 树的应用 83

5.6.1 二叉排序树 83

5.6.2 哈夫曼树及哈夫曼算法 86

5.6.3 判定树 90

第六章 图 93

6.1 基本术语 93

6.2.1 用二维数组表示图的邻接矩阵 95

6.2 图的存贮结构 95

6.2.2 邻接表 96

6.2.3 邻接多重表 97

6.3 遍历图和求图的连通分量 98

6.3.1 深度优先搜索 98

6.3.2 广度优先搜索 100

6.3.3 求图的连通分量 101

6.4 生成树 102

6.5 最短路径 104

6.5.1 从某个源点到其余各顶点的最短路径 104

6.5.2 每一对顶点之间的最短路径 107

6.6 拓扑排序 109

6.7 关键路径 113

7.1.1 顺序查找 119

第七章 查找 119

7.1 几个基本查找方法 119

7.1.2 折半查找 120

7.1.3 分块查找 124

7.2 哈希法 126

7.2.1 构造哈希函数的几种方法 128

7.2.2 处理冲突的方法 132

7.2.3 哈希法的分析 136

第八章 内部排序 139

8.1 插入排序 139

8.2 希尔排序 141

8.3 选择排序 142

8.4 堆排序 143

8.5 快速排序 147

8.6 归并排序 150

8.7 基数排序 151

8.8 各种排序方法的比较 154

第九章 外部排序 156

9.1 存贮设备 156

9.1.1 磁带 156

9.1.2 磁盘 157

9.2 磁带排序 158

9.2.1 平衡归并排序 159

9.2.2 多步归并排序 161

9.3 初始归并段的分布与产生 162

9.3.1 初始归并段的分布 162

9.3.2 初始归并段的产生——置换选择排序 165

9.4.1 磁盘排序 167

9.4 磁盘排序 167

9.4.2 最佳归并树 168

第十章 文件 171

10.1 基本术语 171

10.2 文件组织 173

10.2.1 顺序文件 173

10.2.2 索引文件 175

10.2.3 索引顺序文件 177

10.2.4 直接存取文件 181

10.2.5 多重链表文件 183

10.2.6 倒排文件 185

附录 186

参考文献 202