数据结构 第2版PDF电子书下载

第1章　绪论 1

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

1.2　什么是数据结构 2

1.3　基本术语 3

1.4　算法和算法的描述 5

1.4.1 算法 5

1.4.2　算法的描述 6

1.4.3　算法分析 7

习题一 9

第2章　线性表和数组 11

2.1　线性表及其基本运算 11

2.2　线性表的顺序存储结构 12

2.3　线性表的链式存储结构——单链表 15

2.3.1 单链表 16

2.3.2　单链表的运算 17

2.3.3　循环链表 20

2.4　线性表的链式存储结构——双向链表 21

2.5　多项式相加 25

2.6　栈 28

2.6.1　栈的定义及其运算 28

2.6.2　栈的顺序存储结构 30

2.6.3　多栈共享邻接空间 32

2.6.4　栈的链式存储结构 35

2.7　算术表达式求值 37

2.8　队列 38

2.8.1 队列的定义及其运算 38

2.8.2 队列的链式存储结构 39

2.8.3　队列的顺序存储结构 41

2.8.4　其他队列 44

2.9　数组和数组的顺序存储结构 45

2.9.1　数组 45

2.9.2　数组的顺序存储结构 46

2.10　矩阵的压缩存储 47

2.10.1　特殊矩阵的压缩存储 48

2.10.2　稀疏矩阵的压缩存储 49

习题二 55

第3章 串 59

3.1　串的基本概念 59

3.2　串的存储结构 59

3.2.1 串值的存储 60

3.2.2　串名的存储映象 61

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

3.3.1 串的基本运算 62

3.3.2 串的基本运算的实现 63

3.4　文本编辑 68

习题三 70

第4章　树 72

4.1　树的概念与存储表示 72

4.1.1　树的基本概念 72

4.1.2　树的存储表示 74

4.2　二叉树 76

4.2.1　二叉树的概念 76

4.2.2　二叉树的性质 77

4.2.3　二叉树的存储表示 80

4.3　遍历二叉树 82

4.3.1 前序遍历 82

4.3.2 中序遍历 85

4.3.3 后序遍历 87

4.4　线索二叉树 90

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

4.5.1　树的二叉树表示 97

4.5.2　森林与二叉树的转换 97

4.5.3　树、森林的遍历 99

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

4.6.1　路径长度 100

4.6.2　哈夫曼树 101

4.6.3　哈夫曼码 105

习题四 106

第5章 图 109

5.1 基本术语 109

5.1.1 图 109

5.1.2　顶点的度 110

5.1.3 子图 110

5.1.4 完全图 111

5.1.5　路径和回路 111

5.1.6　连通图与连通分量 112

5.1.7　树图 112

5.1.8　网络 113

5.2　图的存储表示 113

5.2.1　邻接矩阵 113

5.2.2　邻接表 115

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

5.3.1　深度优先搜索法 118

5.3.2　宽度优先搜索法 120

5.3.3　求图的连通分量 122

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

5.4.1 无向连通图的生成树 123

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

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

5.5　最短路径 127

5.5.1　单源最短路径问题 127

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

5.6　拓扑排序和最长路径 133

5.6.1　拓扑排序 133

5.6.2　关键路径 138

习题五 142

第6章　查找 144

6.1 基本概念 144

6.2　顺序查找 146

6.2.1　数组的顺序查找 146

6.2.2　线性链表顺序查找 147

6.3　有序数组的查找 148

6.3.1　二分查找 148

6.3.2　线性插值查找 151

6.3.3　分区查找 152

6.4　二叉排序树查找 155

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

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

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

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

6.5　哈希查找 161

6.5.1　哈希函数与哈希表 161

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

6.5.3　冲突处理 164

习题六 168

第7章　排序 170

7.1　什么是排序 170

7.2　内部排序 171

7.2.1 冒泡排序 171

7.2.2　选择排序 173

7.2.3　插入排序 175

7.2.4　归并排序 177

7.2.5　堆排序 181

7.2.6　快速排序 185

7.2.7　基数排序 189

7.3　存储设备 193

7.3.1　磁带 194

7.3.2　磁盘 195

7.4　外部排序 196

7.4.1 磁带归并排序 196

7.4.2　初始归并段的产生 201

7.4.3　磁盘排序 203

7.4.4　最佳归并树 204

习题七 206

第8章　文件 208

8.1　文件的基本概念 208

8.2　顺序文件 209

8.3　索引文件 211

8.4　索引顺序文件 212

8.5　直接存取文件 214

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

8.7　倒排文件 217

习题八 218

习题答案 219

参考文献 265