数据结构与算法PDF电子书下载

第1章 概论 1

1.1 问题求解 1

1.1.1 问题描述：股市的传言 2

1.1.2 问题分析和抽象 2

1.1.3 数据结构和算法设计 3

1.2 数据结构 6

1.2.1 数据的逻辑结构 6

1.2.2 数据的存储结构 7

1.2.3 抽象数据类型 9

1.3 算法 11

1.3.1 算法的概念 11

1.3.2 算法设计 12

1.4 算法分析 14

1.4.1 渐进分析方法 15

1.4.2 最佳、最差和平均情况 19

1.4.3 时间和空间的折衷 21

1.4.4 求解问题时数据结构的选择和评价 22

本章小结 22

习题 23

上机题 24

第2章 线性表 26

2.1 线性表的概念 26

2.1.1 线性表的抽象数据类型 26

2.1.2 线性表的存储结构 28

2.1.3 线性表运算分类 29

2.2 顺序表 29

2.2.1 顺序表的类定义 29

2.2.2 顺序表的运算实现 31

2.3 链表 34

2.3.1 单链表 34

2.3.2 双链表 40

2.3.3 循环链表 42

2.4 线性表实现方法的比较 44

本章小结 44

习题 45

上机题 45

第3章 栈与队列 46

3.1 栈 46

3.1.1 栈的抽象数据类型 47

3.1.2 顺序栈 47

3.1.3 链式栈 50

3.1.4 表达式求值 52

3.1.5 栈与递归 58

3.2 队列 68

3.2.1 队列的抽象数据类型 68

3.2.2 顺序队列 69

3.2.3 链式队列 72

3.3 栈与队列的深入讨论 74

3.3.1 顺序栈与链式栈的比较 74

3.3.2 顺序队列与链式队列的比较 75

3.3.3 限制存取点的表 75

本章小结 76

习题 77

上机题 77

第4章 字符串 79

4.1 字符串的基本概念 79

4.1.1 字符编码 79

4.1.2 字符的编码顺序 80

4.1.3 字符串抽象数据类型 81

4.2 字符串的存储结构和实现 82

4.2.1 字符串的顺序存储 82

4.2.2 字符串类class String的存储结构 84

4.2.3 字符串运算的实现 87

4.3 字符串的模式匹配 89

4.3.1 朴素的模式匹配算法 90

4.3.2 字符串的特征向量 93

4.3.3 KMP模式匹配算法 96

本章小结 97

习题 98

上机题 99

第5章 二叉树 100

5.1 二叉树的概念 100

5.1.1 二叉树的定义和基本术语 100

5.1.2 满二叉树、完全二叉树、扩充二叉树 101

5.1.3 二叉树的主要性质 102

5.2 二叉树的周游 104

5.2.1 二叉树的抽象数据类型 104

5.2.2 深度优先周游二叉树 106

5.2.3 广度优先周游二叉树 111

5.3 二叉树的存储结构 112

5.3.1 二叉树的链式存储结构 112

5.3.2 完全二叉树的顺序存储结构 115

5.4 二叉搜索树 116

5.5 堆与优先队列 120

5.5.1 堆的定义及其实现 120

5.5.2 优先队列 126

5.6 Huffman树及其应用 127

5.6.1 Huffman树 127

5.6.2 Huffman编码 129

本章小结 131

习题 131

上机题 133

第6章 树 135

6.1 树的定义和基本术语 135

6.1.1 树和森林 135

6.1.2 森林与二叉树的等价转换 137

6.1.3 树的抽象数据类型 139

6.1.4 树的周游 140

6.2 树的链式存储结构 143

6.2.1 “子结点表”表示方法 143

6.2.2 静态“左子／右兄”表示法 144

6.2.3 动态表示法 145

6.2.4 动态“左子／右兄”二叉链表表示法 145

6.2.5 父指针表示法和在并查集中的应用 148

6.3 树的顺序存储结构 153

6.3.1 带右链的先根次序表示 153

6.3.2 带双标记的先根次序表示 154

6.3.3 带度数的后根次序表示 155

6.3.4 带双标记的层次次序表示 156

6.4 K叉树 157

本章小结 158

习题 158

上机题 159

第7章 图 161

7.1 图的定义和基本术语 161

7.2 图的抽象数据类型 165

7.3 图的存储结构 166

7.3.1 相邻矩阵 166

7.3.2 邻接表 169

7.3.3 十字链表 173

7.4 图的周游 174

7.4.1 深度优先周游 175

7.4.2 广度优先周游 176

7.4.3 拓扑排序 177

7.5 最短路径 179

7.5.1 单源最短路径 180

7.5.2 每对顶点之间的最短路径 182

7.6 最小生成树 184

7.6.1 Prim算法 185

7.6.2 Kruskal算法 187

本章小结 189

习题 190

上机题 192

第8章 内排序 194

8.1 排序问题的基本概念 194

8.2 插入排序 195

8.2.1 直接插入排序 196

8.2.2 Shell排序 198

8.3 选择排序 200

8.3.1 直接选择排序 200

8.3.2 堆排序 202

8.4 交换排序 204

8.4.1 冒泡排序 204

8.4.2 快速排序 206

8.5 归并排序 212

8.6 分配排序和索引排序 215

8.6.1 桶式排序 216

8.6.2 基数排序 217

8.6.3 索引排序 226

8.7 排序算法的时间代价 228

8.7.1 简单排序算法的时间代价 228

8.7.2 排序算法的理论和实验时间 229

8.7.3 排序问题的下限 232

本章小结 234

习题 236

上机题 240

第9章 文件管理和外排序 241

9.1 主存储器和外存储器 241

9.2 文件的组织和管理 242

9.2.1 文件组织 243

9.2.2 C＋＋的流文件 244

9.3 外排序 245

9.3.1 置换选择排序 245

9.3.2 二路外排序 248

9.3.3 多路归并——选择树 250

本章小结 257

习题 258

上机题 259

第10章 检索 260

10.1 基于线性表的检索 261

10.1.1 顺序检索 261

10.1.2 二分检索 263

10.1.3 分块检索 266

10.2 集合的检索 268

10.2.1 集合的数学特性 268

10.2.2 计算机中的集合 269

10.3 散列方法 274

10.3.1 散列函数 276

10.3.2 开散列方法（拉链法） 280

10.3.3 闭散列方法（开地址法） 282

10.3.4 闭散列表的算法 285

10.3.5 散列方法的效率分析 290

10.3.6 散列方法的应用 292

本章小结 293

习题 294

上机题 297

第11章 索引技术 300

11.1 线性索引 301

11.2 静态索引——多分树 302

11.3 倒排索引 303

11.3.1 基于属性的倒排 303

11.3.2 对正文文件的倒排 305

11.4 动态索引 308

11.4.1 B树 308

11.4.2 B＋树 314

11.4.3 B树的性能分析 317

11.4.4 动态索引和静态索引性能的比较 319

11.5 位索引技术 320

11.5.1 位图索引 320

11.5.2 签名文件 321

11.6 红黑树 322

11.6.1 红黑树的定义 322

11.6.2 红黑树的相关性质 323

11.6.3 插入结点算法 323

11.6.4 删除结点算法 325

本章小结 328

习题 330

上机题 334

第12章 高级数据结构 335

12.1 多维数组 335

12.1.1 多维数组的存储 335

12.1.2 特殊矩阵 336

12.1.3 稀疏矩阵 337

12.2 广义表和存储管理 339

12.2.1 广义表的定义和存储结构 339

12.2.2 可利用空间表 342

12.2.3 存储的动态分配和回收 344

12.2.4 失败处理策略和无用单元回收 347

12.3 Trie结构和Patricia树 348

12.4 改进的二叉搜索树 352

12.4.1 最佳二叉搜索树 353

12.4.2 平衡的二叉搜索树 361

12.4.3 伸展树 369

本章小结 374

习题 375

上机题 376

参考文献 382