数据结构PDF电子书下载

目录 1

第一章 绪论 1

1.1 数据结构的产生和发展 1

1.2 什么是数据结构 2

1.3 基本术语 3

1.4 算法和算法的描述 5

1.4.1 算法 5

1.4.2 算法的描述 5

1.4.3 算法分析 6

习题一 8

第二章 线性表和数组 10

2.1 线性表及其基本运算 10

2.2 线性表的顺序存贮结构 11

2.3 线性表的链式存贮结构——单链表 14

2.3.1 单链表 14

2.3.2 单链表的运算 16

2.3.3 循环链表 18

2.4 线性表的链式存贮结构——双向链表 19

2.5 多项式相加 22

2.6 数组和数组的顺序存贮结构 25

2.6.1 数组 25

2.6.2 数组的顺序存贮结构 26

2.7 矩阵的压缩存贮 28

2.7.1 特殊矩阵的压缩存贮 28

2.7.2 稀疏矩阵的压缩存贮 29

2.8 栈 35

2.8.1 栈的定义及其运算 35

2.8.2 栈的顺序存贮结构 37

2.8.3 多栈共享邻接空间 38

2.8.4 栈的链式存贮结构 42

2.9 算术表达式求值 43

2.10 队列 45

2.10.1 队列的定义及其运算 45

2.10.2 队列的链式存贮结构 45

2.10.3 队列的顺序存贮结构 48

2.10.4 其它队列 51

3.2 串的存贮结构 54

3.1 串的基本概念 54

习题二………………………………………………… … ……（51 ） 54

第三章 串 54

3.2.1 串值的存贮 55

3.2.2 串名的存贮映象 56

3.3 串的基本运算及其实现 57

3.3.1 串的基本运算 57

3.3.2 串的基本运算的实现 58

3.4 文本编辑 63

习题三 64

第四章 树 66

4.1 树的概念与存贮表示 66

4.1.1 树的基本概念 66

4.1.2 树的存贮表示 68

4.2 二叉树 70

4.2.1 二叉树的概念 70

4.2.2 二叉树的性质 71

4.2.3 二叉树的存贮表示 74

4.3 遍历二叉树 75

4.3.1 前序遍历 76

4.3.2 中序遍历 78

4.3.3 后序遍历 80

4.4 线索二叉树 83

4.5 树、森林与二叉树的转换及遍历 90

4.5.1 树的二叉树表示 90

4.5.2 森林与二叉树的转换 91

4.6.3 哈夫曼码 93

4.5.3 树、森林的遍历 93

4.6 哈夫曼（Huffman）树及其应用 94

4.6.1 路径长度 94

4.6.2 哈夫曼树 95

习题四 100

第五章 图 102

5.1 基本术语 102

5.1.1 图 102

5.1.4 完全图 103

5.1.2 顶点的度 103

5.1.3 子图 103

5.1.5 路径和回路 104

5.1.6 连通图与连通分量 105

5.1.7 树图 105

5.1.8 网络 106

5.2 图的存贮表示 106

5.2.1 邻接矩阵 106

5.2.2 邻接表 108

5.3.1 深度优先搜索法 110

5.3 图的遍历与求图的连通分量 110

5.3.2 宽度优先搜索法 113

5.3.3 求图的连通分量 114

5.4 生成树和最小（代价）生成树 116

5.4.1 无向连通图的生成树 116

5.4.2 网络的最小（代价）生成树 116

5.4.3 最小生成树问题的解法 117

5.5 最短路径 119

5.5.1 单源最短路径问题 120

5.5.2 每对顶点间的最短路径问题 123

5.6 拓扑排序和最长路径 125

5.6.1 拓扑排序 125

5.6.2 关键路径 129

习题五 133

第六章 查找 135

6.1 基本概念 135

6.2 顺序查找 136

6.2.1 数组的顺序查找 137

6.2.2 线性链表顺序查找 138

6.3 有序数组的查找 139

6.3.1 二分查找 139

6.3.2 线性插值查找 142

6.3.3 分区查找 143

6.4 二叉排序树查找 145

6.4.1 二叉排序树的查找算法 146

6.4.2 二叉排序树的结点插入算法 147

6.4.3 二叉排序树的结点删除算法 148

6.4.4 二叉排序树查找算法分析 150

6.5 哈希查找 152

6.5.1 哈希函数与哈希表 153

6.5.2 构造哈希函数的常用方法 154

6.5.3 冲突处理 156

习题六 160

第七章 排序 161

7.1 什么是排序 161

7.2.1 冒泡排序 162

7.2 内部排序 162

7.2.2 选择排序 164

7.2.3 插入排序 166

7.2.4 归并排序 168

7.2.5 堆排序 171

7.2.6 快速排序 175

7.2.7 基数排序 180

7.3 存贮设备 183

7.3.1 磁带 184

7.3.2 磁盘 185

7.4 外部排序 186

7.4.1 磁带归并排序 186

7.4.2 初始归并段的产生 191

7.4.3 磁盘排序 193

7.4.4 最佳归并树 193

习题七 195

8.1 文件的基本概念 197

第八章 文件 197

8.2 顺序文件 198

8.3 索引文件 200

8.4 索引顺序文件 201

8.5 直接存取文件 202

8.6 链接文件和多重链表文件 204

8.7 倒排文件 205

习题八 206

参考文献 207

学习指导与实验 209