数据结构PDF电子书下载

上篇 理论篇 1

第1章 绪论 1

1.1数据结构研究对象 1

1.2数据结构的发展概况及其在计算机科学中的地位 4

1.3基本概念和术语 4

1.4数据类型和抽象数据类型 6

1.4.1数据类型 6

1.4.2抽象数据类型 6

1.5算法和算法分析 7

1.5.1算法 7

1.5.2算法分析 9

本章小结 11

本章习题 12

第2章 线性表 13

2.1线性表的基本概念 13

2.1.1线性表的定义 13

2.1.2线性表的抽象数据类型 15

2.1.3线性表的存储结构 16

2.2线性表的顺序存储结构——顺序表 17

2.2.1顺序表的定义 17

2.2.2顺序表的基本运算 19

2.2.3顺序表的优缺点 24

2.2.4顺序表的应用 25

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

2.3.1单链表的定义 27

2.3.2单链表的基本运算 29

2.3.3静态链表 38

2.3.4循环链表 39

2.3.5双向链表 41

2.3.6单链表的应用 43

2.4顺序表和链表的比较 46

2.5线性表的应用 46

本章小结 52

本章习题 52

第3章 栈和队列 56

3.1栈的基本概念 56

3.1.1栈的定义 56

3.1.2栈的抽象数据类型 57

3.2栈的存储结构 58

3.2.1顺序栈的定义 58

3.2.2顺序栈的基本运算 59

3.2.3链栈的定义 62

3.2.4链栈的基本运算 62

3.2.5顺序栈和链栈的比较 65

3.3栈的应用 65

3.4栈与递归 73

3.4.1递归的定义 73

3.4.2递归的使用情况 73

3.4.3递归过程的实现 75

3.4.4递归的应用举例 76

3.5队列的基本概念 81

3.5.1队列的定义 81

3.5.2队列的抽象数据类型 81

3.6队列的存储结构 82

3.6.1循环队列的定义 83

3.6.2循环队列的基本运算 85

3.6.3链队列的定义 88

3.6.4链队列的基本运算 89

3.6.5循环队列和链队列的比较 91

3.7队列的应用 92

本章小结 94

本章习题 95

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

4.1串 97

4.1.1串的基本概念及操作 97

4.1.2串的定长顺序存储及基本运算 99

4.1.3模式匹配 101

4.2数组 102

4.2.1数组的定义及操作 102

4.2.2数组的顺序存储与实现 103

4.2.3特殊矩阵的压缩存储 105

4.2.4随机稀疏矩阵的压缩存储 107

4.3广义表 117

4.3.1广义表的基本概念和操作 117

4.3.2广义表的存储 119

4.3.3广义表基本操作的实现 120

本章小结 122

本章习题 123

第5章 树和二叉树 128

5.1树的定义及基本术语 129

5.1.1树的定义 129

5.1.2树的表示 131

5.1.3树的基本术语 131

5.2二叉树 132

5.2.1二叉树的定义 132

5.2.2二叉树的性质 135

5.2.3二叉树的存储结构 137

5.3遍历二叉树 139

5.3.1二叉树的递归遍历 140

5.3.2二叉树的非递归调用 141

5.3.3二叉树遍历算法的应用 143

5.4线索二叉树 146

5.4.1线索二叉树的定义和结构 146

5.4.2二叉树的线索化 147

5.4.3线索二叉树中结点的前驱和后继查找 148

5.5树和森林 149

5.5.1树的存储 149

5.5.2森林的存储结构 153

5.5.3树和森林的基本操作 153

5.6哈夫曼树及其应用 157

5.6.1最优二叉树（哈夫曼树） 157

5.6.2哈夫曼编码 159

5.6.3哈夫曼编码算法 160

本章小结 162

本章习题 163

第6章图 166

6.1图的基本概念 166

6.2图的存储结构 168

6.2.1邻接矩阵 168

6.2.2邻接表 170

6.2.3十字链表 172

6.2.4邻接多重表 173

6.3图的遍历 175

6.3.1深度优先搜索 175

6.3.2广度优先搜索 177

6.4最小生成树 178

6.4.1克鲁斯卡尔算法 179

6.4.2普里姆算法 181

6.5最短路径 184

6.5.1求某个顶点（单源点）到其余各顶点的最短路径 185

6.5.2每一对顶点之间的最短路径 188

6.6拓扑排序 192

6.7关键路径 195

本章小结 198

本章习题 198

第7章 排序 202

7.1排序的基本概念 202

7.2插入排序 203

7.2.1直接插入排序 203

7.2.2希尔排序 205

7.3交换排序 206

7.3.1冒泡排序 206

7.3.2快速排序 208

7.4选择排序 213

7.4.1简单选择排序 213

7.4.2堆排序 214

7.5归并排序 218

7.6基数排序 221

7.7各种内部排序方法的比较 225

7.8外部排序简介 226

本章小结 227

本章习题 228

第8章 查找 229

8.1查找的基本概念 229

8.2静态查找表 230

8.2.1顺序表的查找 230

8.2.2有序表的折半查找 230

8.2.3索引顺序表的查找 232

8.3动态查找表 233

8.3.1二叉排序树 233

8.3.2平衡二叉树 239

8.3.3 B-树 246

8.4哈希表 250

8.4.1哈希函数的确定方法 250

8.4.2处理冲突的方法 251

8.4.3哈希查找算法分析 252

本章小结 252

本章习题 252

第9章 文件 253

9.1文件的基本概念和存储结构 253

9.2顺序文件 254

9.3索引文件 255

9.4散列文件 256

9.5多关键字文件 256

9.5.1多重表文件 257

9.5.2倒排文件 258

本章小结 258

本章习题 258

下篇 实验篇 259

实验1顺序表 259

实验2链表 261

实验3栈 270

实验4队列 272

实验5串、数组和广义表 281

实验6树和二叉树 286

实验7图 293

实验8排序 304

实验9查找 313

参考文献 322