数据结构——Python语言描述

Python是目前流行的程序设计语言，国内高校已陆续使用。本书根据普通高等院校计算机专业本科生的教学需求，并按照数据结构课程教学大纲的规定，同时在参考兄弟院校使用的经典教材和教案的基础上，基于Python作为描述语言编写而成。
本书介绍了线性表、栈、队列、串、树和图等基本数据结构，以及这些数据结构的相关应用，还介绍了查找和排序的常用算法。本书在介绍内容时，理论和实践并重，而且配有一定数量的上机实验和习题，帮助读者加深对相关知识点的理解。
本书内容重点突出，语言精练易懂，可作为普通高等院校计算机及相关专业数据结构课程的教材，也可供计算机及相关专业的教学人员、科研人员、数据结构或算法的爱好者使用。高职高专类学校选用本书时可以根据学校和学生的实际情况略去某些章节。

第1章 绪论 1
1.1 数据结构概述 2
1.1.1 什么是数据结构 2
1.1.2 数据的逻辑结构 3
1.1.3 数据的存储结构 4
1.2 数据类型概述 6
1.2.1 数据类型 6
1.2.2 抽象数据类型 7
1.3 算法概述 9
1.3.1 什么是算法 9
1.3.2 算法的时间复杂度 9
1.3.3 算法的空间复杂度 12
1.4 本章小结 13
1.5 上机实验 14
1.5.1 基础实验 14
1.5.2 综合实验 15
习题 16
第2章 线性表 18
2.1 线性表简介 19
2.2 顺序表 21
2.2.1 顺序表的概念 21
2.2.2 顺序表的操作 22
2.2.3 顺序表的应用 29
2.3 链表 31
2.3.1 链表的基本概念 32
2.3.2 单链表 35
2.3.3 循环单链表 45
2.3.4 双链表 50
2.3.5 循环双链表 58
2.3.6 链表的应用 64
2.4 本章小结 78
2.5 上机实验 79
2.5.1 基础实验 79
2.5.2 综合实验 81
习题 85
第3章 栈、队列和递归 87
3.1 栈 88
3.1.1 栈的基本概念 88
3.1.2 栈的顺序存储 89
3.1.3 栈的链式存储 97
3.1.4 栈的典型应用 107
3.2 队列 112
3.2.1 队列的基本概念 112
3.2.2 队列的顺序存储 113
3.2.3 队列的链式存储 125
3.2.4 队列的典型应用 136
3.3 递归 139
3.3.1 什么是递归 139
3.3.2 递归算法的设计和实现 141
3.3.3 递归到非递归的转换 146
3.4 本章小结 154
3.5 上机实验 154
3.5.1 基础实验 154
3.5.2 综合实验 156
习题 158
第4章 串、数组和广义表 160
4.1 串 161
4.1.1 串的基本概念 161
4.1.2 串的顺序存储及运算 163
4.1.3 串的链式存储及运算 167
4.1.4 串的模式匹配 173
4.2 数组和特殊矩阵 185
4.2.1 数组的基本概念 185
4.2.2 数组的顺序存储 187
4.2.3 特殊矩阵 188
4.3 广义表 192
4.3.1 广义表的基本概念 192
4.3.2 广义表的存储 194
4.3.3 广义表的操作 196
4.4 本章小结 202
4.5 上机实验 202
4.5.1 基础实验 202
4.5.2 综合实验 204
习题 206
第5章 树、二叉树和森林 208
5.1 树 209
5.1.1 树的基本概念 209
5.1.2 树的存储 215
5.1.3 树的遍历 219
5.2 二叉树 220
5.2.1 二叉树的基本概念 220
5.2.2 二叉树的存储 225
5.2.3 二叉树的遍历 228
5.2.4 线索二叉树 242
5.2.5 二叉树的典型应用 247
5.3 森林 253
5.3.1 森林的定义 253
5.3.2 树、森林和二叉树 254
5.3.3 树或森林转换为二叉树 255
5.3.4 二叉树转换为森林或树 256
5.4 哈夫曼树 257
5.4.1 哈夫曼树的基本概念 258
5.4.2 哈夫曼算法及实现 259
5.4.3 哈夫曼编码及应用 262
5.5 本章小结 266
5.6 上机实验 267
5.6.1 基础实验 267
5.6.2 综合实验 269
习题 271
第6章 图 273
6.1 图的基本概念 274
6.1.1 图的定义 274
6.1.2 图的相关术语 275
6.1.3 图的性质 280
6.2 图的存储结构 280
6.2.1 数组表示法 280
6.2.2 邻接表表示法 282
6.2.3 十字链表表示法 285
6.2.4 邻接多重表表示法 287
6.3 图的遍历 289
6.3.1 深度优先遍历 289
6.3.2 广度优先遍历 291
6.4 图的最小生成树 293
6.4.1 基本概念 293
6.4.2 Prim算法 294
6.4.3 Kruskal算法 296
6.4.4 应用实例 298
6.5 最短路径 300
6.5.1 基本概念 300
6.5.2 从某源点到其余各顶点的最短
路径 300
6.5.3 每一对顶点之间的最短路径 303
6.5.4 应用实例 305
6.6 拓扑排序 306
6.6.1 基本概念 306
6.6.2 拓扑排序的实现 307
6.7 关键路径 310
6.7.1 基本概念 310
6.7.2 求关键路径的算法 311
6.8 本章小结 316
6.9 上机实验 317
6.9.1 基础实验 317
6.9.2 综合实验 319
习题 322
第7章 查找 326
7.1 查找的基本概念 327
7.1.1 相关术语 327
7.1.2 查找表的基本操作 328
7.2 基于静态查找表的查找 329
7.2.1 顺序查找 330
7.2.2 折半查找 332
7.2.3 索引查找 336
7.3 基于动态查找表的查找 338
7.3.1 树查找 338
7.3.2 哈希表查找 369
7.4 本章小结 384
7.5 上机实验 385
7.5.1 基础实验 385
7.5.2 综合实验 386
习题 387
第8章 内排序 389
8.1 排序的基本概念 390
8.2 插入排序 393
8.2.1 直接插入排序 393
8.2.2 折半插入排序 396
8.2.3 希尔排序 398
8.2.4 表插入排序 401
8.3 交换排序 403
8.3.1 冒泡排序 403
8.3.2 快速排序 407
8.4 选择排序 410
8.4.1 简单选择排序 410
8.4.2 树形选择排序 412
8.4.3 堆排序 414
8.5 归并排序 418
8.6 基数排序 421
8.6.1 多关键字排序 421
8.6.2 链式基数排序 423
8.7 本章小结 427
8.8 上机实验 429
8.8.1 基础实验 429
8.8.2 综合实验 431
习题 434
第9章 外排序 436
9.1 外排序概述 437
9.1.1 典型的外存储设备 437
9.1.2 外排序的基本方法 438
9.2 磁盘排序 439
9.2.1 磁盘排序过程 439
9.2.2 多路平衡归并 441
9.2.3 初始归并段的生成 444
9.2.4 很好归并树 446
9.3 本章小结 449
9.4 上机实验 449
9.4.1 基础实验 449
9.4.2 综合实验 449
习题 451