数据结构PDF电子书下载

第1章 绪论 1

1.1数据结构的由来与发展 1

1.1.1什么是数据结构 1

1.1.2数据结构的发展简史 4

1.2数据结构的有关概念与术语 5

1.3抽象数据类型 8

1.4算法和算法分析 11

1.4.1算法的概念与性质 11

1.4.2算法设计的分类 12

1.4.3算法的设计要求 12

1.4.4算法分析 12

本章小结 12

习题 16

第2章 线性表 17

2.1线性表的类型定义 17

2.1.1线性表的概念 17

2.1.2线性表的抽象数据类型定义 18

2.2线性表的顺序表示和实现 20

2.2.1顺序表 20

2.2.2顺序表上基本运算的实现 21

2.2.3顺序表的应用举例 24

2.3线性表的链式表示和实现 25

2.3.1线性链表的概念 25

2.3.2单链表上基本运算的实现 27

2.3.3线性链表的应用举例 32

2.3.4循环链表 34

2.3.5双向链表 34

2.4静态链表 36

2.5一元多项式的表示和运算 38

本章小结 40

习题 40

第3章 栈和队列 42

3.1栈的概念及操作 42

3.1.1栈的定义 42

3.1.2栈的抽象数据类型定义 42

3.2栈的存储和运算实现 43

3.2.1顺序栈 43

3.2.2链栈 46

3.3栈的应用举例 47

3.3.1数制转换问题 47

3.3.2表达式中括号匹配的检验 48

3.3.3栈在递归中的应用 48

3.3.4表达式求值 52

3.3.5迷宫问题 54

3.4队列的概念及操作 57

3.4.1队列的定义 57

3.4.2队列的抽象数据类型定义 57

3.4.3其他操作受限的线性表 58

3.5队列的存储和运算实现 58

3.5.1顺序队列 58

3.5.2链队列 61

本章小结 63

习题 63

第4章 数组、串和广义表 65

4.1数组 65

4.1.1数组的概念及其抽象数据类型定义 65

4.1.2数组的顺序实现 66

4.1.3矩阵的压缩存储 70

4.2串 82

4.2.1串的概念及其抽象数据类型定义 82

4.2.2串的表示与实现 84

4.2.3串的模式匹配算法 87

4.3广义表 91

4.3.1广义表的概念及其抽象数据类型定义 91

4.3.2广义表的实现 92

本章小结 96

习题 96

第5章树 98

5.1树的基本概念 98

5.2二叉树 101

5.2.1二叉树的定义与性质 101

5.2.2二叉树的存储与实现 104

5.2.3二叉树的遍历 107

5.3线索二叉树 112

5.4树和森林 115

5.4.1树的存储 115

5.4.2树、森林与二叉树的转换 117

5.4.3树和森林的遍历 118

5.5 Huffman树和Huffman编码 118

5.6等价类问题 121

本章小结 124

习题 124

第6章图 126

6.1图的基本概念 126

6.2图的表示和存储实现方法 128

6.2.1图的抽象数据类型定义 128

6.2.2邻接矩阵存储结构 129

6.2.3邻接表存储结构 130

6.2.4十字链表存储结构 134

6.2.5邻接多重表存储结构 135

6.3图的遍历 136

6.3.1深度优先遍历 136

6.3.2广度优先遍历 137

6.4最小生成树 138

6.4.1 Prim算法 139

6.4.2 Kruskal算法 141

6.5最短路径 142

6.5.1无权图的最短路径 143

6.5.2 Dijkstra算法 144

6.5.3 Floyd算法 146

6.6拓扑排序 146

6.7关键路径 147

本章小结 150

习题 150

第7章 查找 153

7.1查找的基本概念 153

7.2静态查找表 155

7.2.1顺序表的查找 155

7.2.2有序表的查找 156

7.2.3分块查找 160

7.3动态查找表 162

7.3.1二叉排序树 162

7.3.2平衡二叉树 167

7.3.3 B-树 173

7.3.4 B+树 177

7.4哈希表上的查找 178

7.4.1哈希表的概念 178

7.4.2哈希函数的构造方法 180

7.4.3处理冲突的方法 181

7.4.4哈希表的查找及其性能分析 183

7.4.5哈希表的有关算法 185

本章小结 187

习题 187

第8章 排序 189

8.1概述 189

8.2插入排序 191

8.2.1直接插入排序 191

8.2.2折半插入排序 193

8.2.3希尔排序 194

8.3交换排序 195

8.3.1冒泡排序 195

8.3.2快速排序 196

8.4选择排序 198

8.4.1简单选择排序 198

8.4.2树选择排序 199

8.4.3堆排序 200

8.5归并排序 202

8.6基数排序 204

8.7内部排序方法比较 207

8.8外部排序概述 208

本章小结 209

习题 209

部分习题参考答案或提示 211

参考文献 218