数据结构是计算机相关专业一门重要的专业基础课程。本书基于Python语言系统介绍数据结构的知识，内容包括数据结构与算法概述、线性表、栈与队列、串、数组与广义表、基于线性表的查找算法、基于线性表的排序算法、树、基于树的查找算法、基于树的排序算法、图、计算式查找法。

周翔，福州理工学院计算与信息科学学院智能科学与技术专业带头人，省级一流本科课程线上线下混合式《数据结构》课程负责人。在多年的教学与科研工作中，一直积极探索人工智能与大数据等前沿技术与本科基础学科之间如何有效融合的教学方式的改革与创新，从而建设能够有效提高学生实践创新能力为目标的课程体系，最终构建以新工科教育新模式为前提，助力地方区域新兴产业发展的一流智能科学与技术专业的目标。省级一流本科课程认定1门，校级一流本科课程立项2门，其中1门已结题；参与省级教学改革项目2项；省级中青年项目立项2项，其中1项已结题；发表教改论文1篇，科研论文4篇，其中EI1篇，核心1篇，学报3篇；实用新型专利2项，软件著作权8项，科技成果转化金额为5万，获得校级教学成果奖1项、教学竞赛2项、教学优秀奖1项、荣誉称号2项。

第1章 数据结构与算法概述 / 1
1.1 数据结构 / 1
1.1.1 什么是数据结构 / 1
1.1.2 数据结构的分类 / 3
1.1.3 数据类型与抽象数据类型 / 6
1.2 算法 / 7
1.3 算法分析 / 9
1.3.1 算法的时间复杂度 / 10
1.3.2 算法的空间复杂度 / 13
1.4 本章习题 / 13

第2章 线性表 / 15
2.1 什么是线性表 / 15
2.2 顺序表 / 16
2.2.1 顺序表的定义 / 16
2.2.2 顺序表的实现 / 17
2.3 单链表 / 24
2.3.1 单链表的定义 / 24
2.3.2 单链表的实现 / 25
2.4 双向链表 / 34
2.4.1 双向链表的定义 / 34
2.4.2 双向链表的实现 / 34
2.5 循环链表 / 38
2.5.1 循环链表的定义 / 38
2.5.2 循环链表的实现 / 39
2.6 线性表的比较 / 42
2.6.1 顺序表与链表的比较 / 42
2.6.2 链式存储方式的比较 / 42
2.7 线性表的应用 / 43
2.7.1 一元多项式的表示及相加 / 43
2.7.2 约瑟夫环 / 47
2.8 本章实验：线性表初探 / 49
2.9 本章习题 / 50

第3章 栈与队列 / 53
3.1 什么是栈 / 53
3.2 栈的实现 / 54
3.2.1 顺序栈存储实现 / 54
3.2.2 双端栈存储实现 / 57
3.2.3 链栈存储实现 / 59
3.3 栈与递归 / 61
3.3.1 递归的概念 / 61
3.3.2 栈的应用 / 63
3.4 什么是队列 / 66
3.5 队列的实现 / 66
3.5.1 顺序队列的实现 / 66
3.5.2 循环队列的实现 / 68
3.5.3 链式队列的实现 / 71
3.6 队列的应用 / 74
3.7 讨论课：如何选择合适的线性表解决实际问题 / 75
3.8 本章实验：栈的定义与应用 / 75
3.9 本章习题 / 76

第4章 串 / 78
4.1 什么是串 / 78
4.2 串的存储结构 / 78
4.2.1 串的顺序存储实现 / 78
4.2.2 串的链式存储实现 / 83
4.3 串的模式匹配算法 / 83
4.3.1 朴素的模式匹配算法 / 83
4.3.2 KMP算法 / 85
4.4 综合实验：校友通讯录—线性表的应用 / 89
4.5 本章习题 / 90

第5章 数组与广义表 / 92
5.1 数组 / 92
5.2 矩阵存储 / 93
5.2.1 特殊矩阵 / 93
5.2.2 稀疏矩阵 / 94
5.3 广义表 / 100
5.3.1 广义表的定义 / 100
5.3.2 广义表的存储结构 / 101
5.3.3 广义表的递归运算 / 102
5.4 本章习题 / 105

第6章 基于线性表的查找算法 / 107
6.1 查找概述 / 107
6.2 顺序表查找法 / 108
6.3 折半查找法 / 108
6.4 索引顺序查找法 / 111
6.5 本章实验：折半查找 / 113
6.6 本章习题 / 113

第7章 基于线性表的排序算法 / 115
7.1 排序的概念及分类 / 115
7.2 插入排序 / 116
7.2.1 直接插入排序 / 116
7.2.2 折半插入排序 / 119
7.2.3 希尔排序 / 119
7.3 交换排序 / 120
7.3.1 冒泡排序 / 121
7.3.2 快速排序 / 123
7.4 归并排序 / 124
7.5 本章实验：冒泡排序改动算法 / 126
7.6 本章习题 / 127

第8章 树 / 129
8.1 树 / 129
8.1.1 什么是树 / 129
8.1.2 树的基本概念及常用术语 / 130
8.2 树的存储结构 / 131
8.2.1 双亲表示法 / 131
8.2.2 孩子表示法 / 132
8.2.3 孩子兄弟表示法 / 132
8.3 二叉树 / 134
8.3.1 什么是二叉树 / 134
8.3.2 二叉树的分类 / 134
8.3.3 二叉树的性质 / 135
8.4 二叉树的存储结构 / 137
8.4.1 二叉树的顺序存储 / 137
8.4.2 二叉树的链式存储 / 138
8.5 树的遍历与应用 / 139
8.5.1 二叉树的遍历 / 139
8.5.2 二叉树的应用 / 143
8.5.3 树的遍历 / 147
8.6 树的转换、构建与线索化 / 147
8.6.1 二叉树与树、森林之间的转换 / 147
8.6.2 二叉树的构建 / 150
8.6.3 线索化二叉树 / 153
8.7 哈夫曼树 / 155
8.7.1 什么是哈夫曼树 / 155
8.7.2 哈夫曼树的构造 / 155
8.7.3 哈夫曼编码 / 156
8.7.4 哈夫曼树的实现 / 157
8.8 讨论课：如何学习树 / 158
8.9 本章实验一：二叉树的创建与遍历 / 159
8.10 本章实验二：二叉树的查找 / 159
8.11 综合实验：校友通讯录—树的应用 / 160
8.12 本章习题 / 161

第9章 基于树的查找算法 / 164
9.1 二叉排序树 / 164
9.1.1 二叉排序树的插入 / 164
9.1.2 二叉排序树的删除 / 168
9.1.3 二叉排序树的查找 / 170
9.2 平衡二叉树 / 172
9.2.1 平衡二叉树的定义 / 172
9.2.2 平衡二叉树的平衡化旋转 / 173
9.3 B树 / 177
9.3.1 B树的查找 / 178
9.3.2 B树的插入 / 178
9.3.3 B+树和B*树 / 179
9.4 本章习题 / 180

第10章 基于树的排序算法 / 182
10.1 选择排序 / 182
10.1.1 简单选择排序 / 182
10.1.2 树形选择排序 / 183
10.2 堆排序 / 184
10.2.1 堆的定义 / 184
10.2.2 堆的存储 / 185
10.2.3 堆排序的思想 / 189
10.3 综合比较 / 193
10.4 本章习题 / 194

第11章 图 / 196
11.1 图的基本概念 / 196
11.1.1 什么是图 / 196
11.1.2 图的基本术语 / 196
11.2 图的存储结构 / 199
11.2.1 邻接矩阵 / 200
11.2.2 邻接表 / 202
11.2.3 十字链表 / 205
11.2.4 邻接多重表 / 207
11.3 图的遍历 / 207
11.3.1 深度优先遍历 / 208
11.3.2 广度优先遍历 / 212
11.4 图的应用 / 216
11.4.1 最小生成树 / 216
11.4.2 最短路径 / 224
11.4.3 拓扑序列 / 235
11.4.4 关键路径 / 239
11.5 讨论课：图是什么 / 245
11.6 本章实验一：图的邻接矩阵定义与创建 / 246
11.7 本章实验二：图的邻接表定义与创建 / 246
11.8 综合实验：校友通讯录—图的应用 / 247
11.9 本章习题 / 248

第12章 计算式查找法 / 251
12.1 什么是哈希表 / 251
12.2 哈希函数的构造方法 / 252
12.3 处理冲突的方法 / 253
12.3.1 开放定址法（再散列法） / 253
12.3.2 链地址法 / 255
12.3.3 再哈希法 / 256
12.3.4 建立公共溢出区 / 256
12.4 哈希查找法 / 257
12.5 讨论课：如何选择合适的算法，达到性能的最优 / 259
12.6 综合实验：校友通讯录—算法的应用 / 259
12.7 本章习题 / 260