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

第1章 引论 1

1.1数据结构的概念 1

1.2数据结构的内容 5

1.2.1数据的逻辑结构 5

1.2.2数据的存储结构 6

1.3算法 6

1.3.1算法的概念 7

1.3.2算法的评价标准 7

1.3.3算法的描述 8

1.3.4算法性能分析 10

习题 14

第2章 线性表 16

2.1应用实例 16

2.2线性表的概念及运算 17

2.2.1线性表的逻辑结构 17

2.2.2线性表的运算 17

2.3线性表的顺序存储 18

2.3.1顺序表 18

2.3.2顺序表的基本运算 19

2.4线性表的链式存储 23

2.4.1单链表 23

2.4.2单链表基本运算 24

2.4.3循环链表 31

2.4.4双向链表 32

2.4.5静态链表 33

2.5顺序表和链表的比较 33

2.6实例分析与实现 34

习题 42

第3章 栈和队列 45

3.1应用实例 45

3.2栈 46

3.2.1栈的概念及运算 46

3.2.2栈的顺序存储结构 47

3.2.3栈的链式存储结构 50

3.2.4栈的应用 52

3.3队列 57

3.3.1队列的概念及其运算 57

3.3.2循环队列 59

3.3.3链队列 61

3.4实例分析与实现 63

3.5算法总结——递归与分治算法 69

习题 71

第4章 串 73

4.1应用实例 73

4.2串及其运算 74

4.2.1串的基本概念 74

4.2.2串的基本运算 75

4.2.3串的基本运算示例 77

4.3串的存储结构及实现 77

4.3.1定长顺序串 77

4.3.2堆串 80

4.3.3块链串 82

4.4串的模式匹配 83

4.4.1 BF模式匹配算法 84

4.4.2 KMP模式匹配算法 85

4.5实例分析与实现 91

4.5.1串的实例分析 91

4.5.2简单文本编辑软件的实现 92

4.6算法总结 94

习题 95

第5章 多维数组和广义表 97

5.1应用实例 97

5.2多维数组 97

5.3矩阵的压缩存储 99

5.3.1特殊矩阵 99

5.3.2稀疏矩阵 100

5.4广义表 107

5.4.1广义表的概念 107

5.4.2广义表的存储 108

5.4.3广义表的操作 109

5.5实例分析与实现 111

习题 113

第6章 树 115

6.1应用实例 115

6.2树的概念 117

6.2.1树的定义与表示 117

6.2.2树的基本术语 118

6.2.3树的抽象数据类型定义 119

6.3二叉树 120

6.3.1二叉树的定义 120

6.3.2二叉树的性质 122

6.3.3二叉树的存储 124

6.4二叉树的遍历 126

6.4.1二叉树的遍历及递归实现 126

6.4.2二叉树遍历的非递归实现 128

6.4.3遍历算法的应用 132

6.4.4由遍历序列确定二叉树 136

6.5线索二叉树 137

6.5.1线索二叉树的基本概念 137

6.5.2线索二叉树的基本操作 138

6.6树和森林 140

6.6.1树的存储 140

6.6.2树、森林与二叉树的转换 143

6.6.3树和森林的遍历 146

6.7哈夫曼树及其应用 148

6.7.1哈夫曼树 148

6.7.2哈夫曼编译码 151

6.8实例分析与实现 153

6.8.1表达式树 153

6.8.2树与等价类的划分 155

6.8.3回溯法与N皇后问题 158

6.9算法总结 160

习题 161

第7章 图 164

7.1应用实例 164

7.2图的基本概念 165

7.3图的存储结构 167

7.3.1邻接矩阵 167

7.3.2邻接表 169

7.3.3十字链表 171

7.3.4多重链表 172

7.4图的遍历 173

7.4.1深度优先搜索遍历 173

7.4.2广度优先搜索遍历 175

7.5图的应用 176

7.5.1最小生成树 176

7.5.2拓扑排序 181

7.5.3关键路径 184

7.5.4最短路径 188

7.6实例分析与实现 192

7.7算法总结——贪心算法 199

习题 203

第8章 查找 207

8.1概述 207

8.2基于线性表的查找 208

8.2.1顺序查找 208

8.2.2折半查找 210

8.2.3索引查找 213

8.3基于树的查找 214

8.3.1二叉排序树 214

8.3.2平衡二叉树 220

8.3.3 B树和B+树 228

8.3.4伸展树 234

8.3.5红黑树 236

8.4散列 241

8.4.1 Hash函数的构造方法 241

8.4.2处理冲突的方法 243

8.4.3 Hash表查找 245

8.5算法总结 248

习题 249

第9章 排序 252

9.1概述 252

9.2插入类排序 254

9.2.1直接插入排序 255

9.2.2折半插入排序 257

9.2.3希尔排序 258

9.3交换类排序 259

9.3.1冒泡排序 259

9.3.2快速排序 262

9.4选择类排序 264

9.4.1简单选择排序 264

9.4.2树形选择排序 265

9.4.3堆排序 267

9.5归并类排序 272

9.5.1二路归并排序 272

9.5.2自然归并排序 274

9.6分配类排序 275

9.6.1多关键字排序 275

9.6.2链式基数排序 276

9.7外部排序 278

9.7.1置换选择排序 279

9.7.2多路归并外排序 281

9.8算法总结 285

习题 286

参考文献 288