数据结构PDF电子书下载

第1章 绪论 1

1.1数据结构的研究内容 1

1.2数据结构的基本概念和相关术语 2

1.3抽象数据类型及其实现 3

1.3.1数据类型 3

1.3.2抽象数据类型 4

1.4算法与算法分析 5

1.4.1算法的描述 5

1.4.2算法的时间复杂度分析 6

1.4.3算法的空间复杂度分析 7

1.5小结 8

1.6应试加油站 8

1.6.1重点提示 8

1.6.2考研真题解析 8

1.7习题 10

第2章 线性表 12

2.1线性表的定义及其运算 12

2.1.1什么是线性表 12

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

2.2线性表顺序存储结构的定义 14

2.2.1线性表顺序存储结构的定义 14

2.2.2顺序表的基本操作及实现 15

2.2.3顺序表的应用 18

2.3线性表的链式存储结构与实现 20

2.3.1线性表的链式存储结构 20

2.3.2单链表及其基本操作 21

2.3.3循环链表的基本操作及实现 29

2.3.4双链表的基本操作及实现 34

2.3.5循环双链表 38

2.4上机实训 39

实训一：顺序表的操作 39

实训二：单链表链接 41

实训三：循环链表链接 44

实训四：循环双链表操作 48

2.5小结 52

2.6应试加油站 53

2.6.1重点提示 53

2.6.2考研真题解析 53

2.7习题 60

第3章 栈和队列 65

3.1栈 65

3.1.1什么是栈 65

3.1.2栈的抽象数据类型 66

3.1.3栈的顺序存储结构及实现 66

3.1.4栈的链式存储结构与实现 70

3.2栈的应用 74

3.2.1表达式求值 74

3.2.2数制转换 76

3.2.3括号匹配检验 77

3.2.4栈与递归的实现 79

3.3队列 80

3.3.1什么是队列 80

3.3.2队列的抽象数据类型 81

3.3.3队列的顺序存储结构与实现 81

3.3.4队列的链式存储结构与实现 88

3.4队列的应用 91

3.5上机实训 95

实训一：利用栈寻找迷宫路径 95

实训二：利用队列模拟病人看病 98

3.6小结 103

3.7应试加油站 103

3.7.1重点提示 103

3.7.2考研真题解析 103

3.8习题 109

第4章串 113

4.1串的定义 113

4.1.1什么是串 113

4.1.2串的抽象数据类型 113

4.2串的存储结构与实现 114

4.2.1串的顺序存储结构与实现 114

4.2.2串的堆存储结构与实现 119

4.2.3串的块链存储结构与实现 119

4.3串的模式匹配算法 120

4.3.1简单的模式匹配算法——BF算法 120

4.3.2改进的模式匹配算法——KMP算法 122

4.4串的应用 124

4.5上机实训 125

实训一：显示多位数数字字符 125

实训二：块链的基本操作 127

实训三：统计串中最长的重复子串 133

4.6小结 135

4.7应试加油站 136

4.7.1重点提示 136

4.7.2考研真题解析 136

4.8习题 138

第5章 数组与广义表 140

5.1数组的定义 140

5.1.1什么是数组 140

5.1.2数组的抽象数据类型 141

5.2数组的顺序存储结构与实现 141

5.2.1数组的顺序存储结构 141

5.2.2基本操作的实现 142

5.3矩阵的压缩存储 145

5.3.1特殊矩阵 145

5.3.2稀疏矩阵 148

5.4广义表抽象数据类型 152

5.4.1广义表的定义 152

5.4.2广义表的抽象数据类型 152

5.4.3广义表的存储结构 153

5.4.4广义表的应用 154

5.5上机实训 156

实训一：两个矩阵的相乘操作 156

实训二：用三元组实现两个矩阵的乘法 158

实训三：广义表的基本运算 161

5.6小结 167

5.7应试加油站 167

5.7.1重点提示 167

5.7.2考研真题解析 168

5.8习题 171

第6章树 173

6.1树的基本概念和相关术语 173

6.1.1树的定义 173

6.1.2基本术语 174

6.2二叉树 175

6.2.1二叉树的定义 175

6.2.2二叉树的性质 176

6.2.3二叉树的抽象数据类型 177

6.2.4二叉树的存储结构 179

6.3遍历二叉树 183

6.3.1遍历的定义 183

6.3.2遍历算法 184

6.4线索二叉树 187

6.5树和森林 190

6.5.1树的存储结构 190

6.5.2森林与二叉树的转换 191

6.5.3树和森林的遍历 193

6.6哈夫曼树及其应用 193

6.6.1哈夫曼树的概念 193

6.6.2哈夫曼树的构造算法 194

6.6.3哈夫曼编码 196

6.7上机实训 198

实训一：运算二叉树 198

实训二：统计二叉树结点的个数 201

实训三：统计二叉树的宽度 202

实训四：按层遍历二叉树 204

6.8小结 208

6.9应试加油站 208

6.9.1重点提示 208

6.9.2考研真题解析 208

6.10习题 216

第7章图 219

7.1图的定义和相关术语 219

7.1.1图的定义 219

7.1.2图的基本术语 220

7.1.3图的抽象数据类型 222

7.2图的存储结构 223

7.2.1邻接矩阵表示法 223

7.2.2邻接表表示法 225

7.2.3十字链表表示法 227

7.2.4多重邻接表表示法 227

7.3图的遍历 228

7.3.1深度优先遍历 229

7.3.2广度优先遍历 230

7.4最小生成树 231

7.4.1生成树的概念 231

7.4.2最小生成树 231

7.4.3 Prim算法 235

7.5最短路径 238

7.5.1单源点最短路径问题 238

7.5.2所有顶点对最短路径问题 240

7.6拓扑排序 241

7.7关键路径 244

7.8上机实训 244

实训一：遍历算法 244

实训二：Prim算法 249

7.9小结 253

7.10应试加油站 253

7.10.1重点提示 253

7.10.2考研真题解析 254

7.11习题 265

第8章 查找 270

8.1查找的基本概念 270

8.2静态查找表 271

8.2.1顺序表的查找 271

8.2.2有序表的查找 271

8.2.3索引顺序表的查找 272

8.2.4静态树表的查找 274

8.3动态查找表 275

8.3.1二叉排序树 275

8.3.2平衡二叉树 277

8.3.3 B-和B+树 282

8.3.4键树 290

8.4哈希表 291

8.4.1哈希表的概念 291

8.4.2哈希表的构造方法 291

8.4.3处理冲突的方法 292

8.4.4哈希表的查找及分析 295

8.5上机实训 296

实训一：二叉排序树的查找 296

实训二：哈希查找 300

8.6小结 302

8.7应试加油站 303

8.7.1重点提示 303

8.7.2考研真题解析 303

8.8习题 309

第9章 内部排序 312

9.1插入排序 312

9.1.1直接插入排序 312

9.1.2希尔排序 314

9.2交换排序 315

9.2.1冒泡排序 315

9.2.2快速排序 317

9.3选择排序 319

9.3.1简单选择排序 319

9.3.2堆排序 320

9.4归并排序 322

9.5基数排序 324

9.6各种内排序方法的比较 327

9.7上机实训 328

实训一：双向冒泡排序 328

实训二：数组归并排序 330

实训三：计数排序 333

实训四：字符串排序 335

实训五：最高位关键字排序MSD 338

9.8小结 341

9.9应试加油站 342

9.9.1重点提示 342

9.9.2考研真题解析 342

9.10习题 346

参考文献 348