数据结构理论与实践PDF电子书下载

第1章 绪论 1

1.1数据结构的重要性 1

1.2基本概念和术语 5

1.2.1基本概念 6

1.2.2数据类型 8

1.3算法 10

1.3.1算法特性 11

1.3.2算法描述 12

1.3.3算法性能分析与度量 18

习题 20

第2章 线性表 22

2.1线性表的逻辑结构 22

2.1.1线性表的定义 22

2.1.2线性表的基本操作 23

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

2.2.1顺序表 24

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

2.2.3顺序表应用举例 33

2.3线性表的链式存储结构 36

2.3.1单链表 36

2.3.2单链表上的基本操作 37

2.3.3循环链表 44

2.3.4双向链表及双向循环链表 44

2.3.5链表应用举例 49

2.4一元多项式的表示及相加 52

2.5实训 56

习题 66

第3章 栈与队列 68

3.1栈 68

3.1.1栈的概念及相关操作 68

3.1.2栈的顺序存储结构及其基本运算的实现 69

3.1.3栈的链式存储结构及其基本运算的实现 75

3.2队列 79

3.2.1队列的概念和相关操作 79

3.2.2队列的顺序存储结构及其基本运算的实现 80

3.2.3队列的链式存储结构及其基本运算的实现 85

3.3栈和队列的应用 89

3.3.1栈的应用举例 89

3.3.2队列的应用举例 96

3.4实训 102

习题 118

第4章 串和数组 120

4.1串的基本概念和存储结构 120

4.1.1基本概念 120

4.1.2基本运算 121

4.1.3串的抽象数据类型描述 121

4.1.2串的存储结构 122

4.2串基本操作的实现 124

4.2.1串基本操作 124

4.2.2串的模式匹配算法 137

4.3数组的定义和运算 140

4.3.1数组的概念 140

4.3.2数组的操作 141

4.4数组顺序存储结构 141

4.4.1行优先顺序 141

4.4.2列优先顺序 141

4.4.3基本操作在顺序存储上的实现 142

4.4.4动态数组 144

4.5矩阵的压缩存储 146

4.5.1特殊矩阵 146

4.5.2压缩存储 147

4.5.3稀疏矩阵 149

4.5.4广义表 157

4.6实训 162

习题 168

第5章树 171

5.1树 171

5.1.1树的定义 171

5.1.2树的逻辑结构 173

5.1.3树的表示 173

5.2二叉树 174

5.2.1二叉树的定义 174

5.2.2二叉树的性质 176

5.2.3二叉树的存储结构 177

5.3二叉树的遍历 179

5.3.1遍历的定义 179

5.3.2遍历算法 181

5.3.3遍历的应用 184

5.4树和森林 186

5.4.1树的存储结构 186

5.4.2森林和二叉树的转换 188

5.4.3数和森林的遍历 190

5.5哈夫曼树及其应用 191

5.5.1最优二叉树（哈夫曼树） 191

5.5.2哈夫曼编码 193

5.6实训 196

习题 210

第6章图 212

6.1图的定义及术语 212

6.1.1图的定义 212

6.1.2图的逻辑结构 215

6.2图的存储结构 216

6.2.1邻接矩阵表示法 216

6.2.2邻接表 218

6.2.3十字链表 220

6.2.4邻接多重表 222

6.3图的遍历 223

6.3.1深度优先搜索 224

6.3.2广度优先搜索 225

6.4最小生成树 226

6.4.1最小生成树 226

6.4.2普里姆算法 227

6.4.3克鲁斯卡尔算法 229

6.5有向无环图及应用 230

6.5.1拓扑排序 230

6.5.2关键路径 233

6.6最短路径 236

6.6.1从一个源点到其他各点的最短路径 236

6.6.2每一对顶点之间的最短路径 238

6.7实训 240

习题 250

第7章 查找 252

7.1静态查找 253

7.1.1顺序表查找 253

7.1.2二分查找 255

7.1.3分块查找 258

7.2动态查找 260

7.2.1二叉排序树查找 260

7.2.2二叉排序树的插入 262

7.2.3二叉排序树的删除 263

7.3哈希表 264

7.3.1哈希表 264

7.3.2哈希函数的构造方法 265

7.3.3处理冲突的方法 268

7.4实训 270

习题 275

第8章 排序 276

8.1插入排序 277

8.1.1直接插入排序 278

8.1.2折半插入排序 280

8.1.3希尔排序 281

8.1.4应用举例 282

8.2交换排序 283

8.2.1冒泡排序 283

8.2.2快速排序 285

8.3选择排序 290

8.3.1直接选择排序 291

8.3.2树形选择排序 293

8.3.3堆排序 295

8.3.4应用举例 301

8.4归并排序 304

8.4.1两个有序序列的归并 304

8.4.2 2-路归并排序 305

8.4.3应用举例 307

8.5基数排序 308

8.5.1多关键字排序 308

8.5.2链式基数排序 311

8.5.3应用举例 316

8.6各种排序方法的比较和选择 316

8.6.1排序方法的比较 316

8.6.2各种内部排序方法的选择 317

8.7实训 318

习题 322

参考文献 325