数据结构PDF电子书下载

第1章 概论 1

1.1数据结构的概念 1

1.2数据结构的组成与分类 2

1.2.1数据的逻辑结构 2

1.2.2数据的存储结构 3

1.2.3数据的运算（集合） 5

1.3数据类型与抽象数据类型 5

1.3.1数据类型 5

1.3.2抽象数据类型 6

1.4算法的概念与描述 7

1.4.1算法的概念 7

1.4.2算法的描述 8

1.5算法分析 14

1.5.1算法性能的评价标准 14

1.5.2算法的复杂度 15

1.6本章小结 18

习题 19

第2章 顺序表 20

2.1向量 21

2.1.1向量的存储与运算 21

2.1.2目录表 24

2.2栈 25

2.2.1栈的定义与基本操作 25

2.2.2顺序栈 27

2.3栈与递归 30

2.3.1递归的概念 30

2.3.2递归过程的实现 32

2.3.3递归过程到非递归过程的转换 33

2.4队列 38

2.4.1队列的定义与基本操作 38

2.4.2顺序队列 40

2.5应用举例 43

2.5.1向量应用—约瑟夫斯问题 43

2.5.2栈的应用—括号匹配的检验与数制转换 46

2.5.3队列应用—输出杨辉三角形 52

2.6本章小结 55

习题 56

第3章 链表 57

3.1单链表 57

3.1.1单链表的概念 57

3.1.2单链表的存储描述 58

3.1.3在单链表上实现的基本运算 59

3.1.4带表头结点的单链表 62

3.2栈和队列的链接存储表示 63

3.2.1链栈 63

3.2.2链队列 64

3.3循环链表 66

3.4双链表 67

3.4.1双链表的概念 67

3.4.2带表头结点的双循环链表 68

3.4.3双循环链表的基本操作 68

3.5应用举例 70

3.5.1消除链表中的重复数据 70

3.5.2用循环链表求解约瑟夫斯问题 73

3.6本章小结 75

习题 76

第4章串 77

4.1串的基本概念 77

4.2串的存储结构 78

4.2.1顺序存储 78

4.2.2链接存储 79

4.3串的操作 80

4.4模式匹配 82

4.4.1 Brute-Force算法 82

4.4.2 KMP算法 84

4.5应用举例 88

4.6本章小结 89

习题 90

第5章 树形结构 91

5.1树形结构的概念 91

5.1.1树的概念 91

5.1.2二叉树的概念 93

5.1.3树、森林与二叉树之间的相互转换 95

5.1.4树形结构的遍历 97

5.2树形结构的存储方式 99

5.2.1链式存储 100

5.2.2顺序存储 101

5.3二叉树的遍历算法 106

5.3.1遍历二叉树的非递归算法 106

5.3.2遍历二叉树的递归算法 110

5.3.3二叉树遍历的应用举例 111

5.4线索二叉树 111

5.4.1线索二叉树的概念 111

5.4.2二叉树的线索化 112

5.4.3线索二叉树的遍历 114

5.4.4线索二叉树的插入 117

5.5堆 118

5.5.1堆的定义 118

5.5.2堆的构造 119

5.5.3堆的插入与删除 121

5.6哈夫曼树 123

5.6.1扩充的二叉树 123

5.6.2哈夫曼树 124

5.6.3哈夫曼树的应用举例 128

5.7应用举例 130

5.7.1判定树的应用—伪币鉴别问题 130

5.7.2集合的表示与并查集 131

5.7.3建立二叉树及遍历 133

5.8本章小结 135

习题 136

第6章图 139

6.1图的概念 139

6.2图的存储表示 141

6.2.1邻接矩阵表示法 141

6.2.2邻接表表示法 143

6.2.3邻接多重表表示法 145

6.3图的遍历 146

6.3.1深度优先遍历 147

6.3.2广度优先遍历 149

6.4最小（代价）生成树 151

6.4.1普里姆算法 152

6.4.2克鲁斯卡尔算法 154

6.5最短路径问题 157

6.5.1单源最短路径 157

6.5.2每对顶点间的最短路径 160

6.6拓扑排序 163

6.7关键路径 169

6.8本章小结 173

习题 174

第7章 多维数组和广义表 177

7.1多维数组 177

7.2矩阵的压缩存储 179

7.2.1特殊矩阵 179

7.2.2稀疏矩阵 181

7.3广义表 186

7.3.1广义表的概念 186

7.3.2广义表的存储结构 188

7.3.3广义表的运算 191

7.4本章小结 193

习题 193

第8章 排序 195

8.1基本概念 195

8.2插入排序 196

8.2.1直接插入排序 197

8.2.2希尔排序 198

8.2.3其他插入排序 200

8.3交换排序 204

8.3.1冒泡排序 205

8.3.2快速排序 206

8.4选择排序 209

8.4.1直接选择排序 209

8.4.2树形选择排序 211

8.4.3堆排序 213

8.5归并排序 215

8.6基数排序 218

8.6.1多排序码排序 218

8.6.2基数排序 219

8.7外排序 223

8.7.1 2路平衡归并 223

8.7.2 k路平衡归并与败者树 224

8.7.3最佳归并树 226

8.8本章小结 228

习题 229

第9章 查找 230

9.1基本概念 230

9.2线性表的查找 231

9.2.1顺序查找 231

9.2.2折半查找 232

9.2.3分块查找 235

9.3树形表的查找 237

9.3.1二叉排序树 237

9.3.2最佳二叉排序树 242

9.3.3 AVL树 245

9.3.4 B-树与B+树 252

9.4散列表的查找 261

9.4.1基本概念 261

9.4.2散列函数 264

9.4.3冲突的解决 266

9.4.4散列查找的性能 271

9.5本章小结 272

习题 273

第10章 文件 275

10.1文件的基本概念 275

10.2顺序文件 277

10.3索引文件 277

10.4索引顺序文件 279

10.4.1 ISAM文件 279

10.4.2 VSAM文件 281

10.5散列文件 282

10.6多关键字文件 283

10.6.1多重表文件 283

10.6.2倒排文件 284

10.7本章小结 285

习题 286

附录A Visual C++ 6.0集成开发环境介绍 287

附录B 常用字符与ASCII码对照表 290

参考文献 291