第1章 数据结构与算法绪论………………………1
1.1 算法 ………………………1
1.1.1 生活中的算法 ………………………1
1.1.2 算法的定义 ………………………3
1.2 数据结构 ……………………………3
1.2.1 数据结构的定义 ………………………3
1.2.2 数据结构的设计原则 ………………………4
1.3 数据结构与算法的关系 ………………………4
1.4 数据结构与算法的应用 ………………………5
1.5 小结与习题 …………………………6
1.5.1 小结 ………………………6
1.5.2 习题 ……………………………6
第2章 算法复杂度分析………………………7
2.1 案例：一个简单的搜索引擎………………………7
2.1.1 案例描述 ………………………7
2.1.2 案例实现 ………………………7
2.2 算法复杂度的概念………………………10
2.2.1 算法………………………10
2.2.2 算法复杂度………………………11
2.2.3 算法复杂度的重要性………………………11
2.3 时间复杂度的分析方法………………………12
2.3.1 时间复杂度的概念………………………12
2.3.2 时间复杂度的作用………………………12
2.3.3 时间复杂度的分析方法………………………12
2.3.4 常见的时间复杂度示例………………………12
2.3.5 案例分析………………………14
2.4 空间复杂度的分析方法 ………………………14
2.4.1 空间复杂度的概念………………………14
2.4.2 空间复杂度的作用………………………15
2.4.3 空间复杂度的分析方法 ………………………16
2.4.4 常见的空间复杂度示例………………………17
2.4.5 案例分析………………………18
2.5 最好、最坏和平均情况分析………………………19
2.5.1 概念………………………19
2.5.2 分析示例………………………19
2.6 小结与习题 ………………………20
2.6.1 小结 ………………………20
2.6.2 习题………………………21
2.7 实训任务……………………………21
2.8 课外拓展………………………22
第3章 线性数据结构 …………………………23
3.1 案例：简单的计算器………………………23
3.1.1 案例描述………………………23
3.1.2 案例实现………………………23
3.2 线性数据结构的概念………………………28
3.2.1 数据结构的分类………………………28
3.2.2 线性数据结构………………………28
3.2.3 非线性数据结构………………………29
3.3 数组………………………30
3.3.1 数组的概念………………………30
3.3.2 数组的操作………………………30
3.3.3 数组的优、缺点………………………35
3.3.4 数组的应用………………………35
3.4 链表…………………………35
3.4.1 链表的概念………………………35
3.4.2 链表的实现及操作………………………36
3.4.3 链表的优、缺点………………………44
3.4.4 链表的扩展………………………45
3.4.5 链表的应用………………………46
3.5 栈………………………46
3.5.1 栈的概念………………………46
3.5.2 栈的实现及操作………………………46
3.5.3 栈的优、缺点………………………52
3.5.4 栈的应用………………………53
3.6 队列…………………………53
3.6.1 队列的概念………………………53
3.6.2 队列的实现及操作………………………54
3.6.3 队列的优、缺点………………………64
3.6.4 队列的应用………………………65
3.7 小结与习题………………………65
3.7.1 小结……………………………65
3.7.2 习题………………………66
3.8 实训任务…………………………67
3.9 课外拓展…………………………67
第4章 树 ………………………………69
4.1 案例：文件系统的遍历………………………69
4.1.1 案例描述………………………69
4.1.2 案例实现………………………70
4.2 树的概念……………………………72
4.2.1 树的基本概念………………………72
4.2.2 二叉树的基本概念………………………74
4.3 二叉树的实现及基本操作………………………77
4.3.1 二叉树节点定义………………………77
4.3.2 二叉树的操作………………………78
4.4 二叉树的遍历………………………79
4.4.1 二叉树遍历的概念………………………79
4.4.2 广度优先遍历………………………80
4.4.3 深度优先遍历………………………82
4.5 二叉树的应用………………………85
4.6 小结与习题………………………86
4.6.1 小结………………………86
4.6.2 习题………………………87
4.7 实训任务………………………87
4.8 课外拓展………………………88
第5章 图 ……………………………90
5.1 案例：社交网络中的关系处理………………………90
5.1.1 案例描述………………………90
5.1.2 案例实现………………………91
5.2 图的概念………………………………93
5.2.1 图的定义………………………93
5.2.2 图的分类与常用术语………………………94
5.3 图的实现及基本操作………………………97
5.3.1 图的实现………………………97
5.3.2 图的基本操作 ………………………102
5.4 图的遍历 ………………………111
5.4.1 图的遍历的概念 ………………………111
5.4.2 广度优先遍历 ………………………112
5.4.3 深度优先遍历 ………………………115
5.5 图的应用 …………………………117
5.6 小结与习题 ………………………117
5.6.1 小结 …………………………117
5.6.2 习题 ………………………118
5.7 实训任务 …………………………119
5.8 课外拓展 …………………………120
第6章 搜索算法………………………121
6.1 案例：图书馆图书检索系统 ………………………121
6.1.1 案例描述 ………………………121
6.1.2 案例实现 ………………………122
6.2 线性搜索 ………………………124
6.2.1 线性搜索的基本原理 ………………………124
6.2.2 线性搜索算法 ………………………124
6.2.3 线性搜索的应用场景 ………………………125
6.3 有序表搜索 ………………………125
6.3.1 有序表搜索基本原理 ………………………125
6.3.2 二分搜索算法 ………………………126
6.3.3 插值搜索算法 ………………………128
6.3.4 斐波那契搜索算法 ………………………130
6.3.5 有序表搜索的应用场景 ………………………134
6.4 二叉排序树 ………………………134
6.4.1 二叉排序树的概念 ………………………134
6.4.2 二叉排序树的操作 ………………………135
6.4.3 二叉排序树的应用场景 ………………………141
6.5 哈希表与哈希搜索 ………………………142
6.5.1 哈希表与哈希搜索的概念 ………………………142
6.5.2 哈希表实现………………………143
6.5.3 哈希冲突 ………………………148
6.5.4 哈希表与哈希搜索的应用场景 ………………………160
6.6 小结与习题………………………161
6.6.1 小结 …………………………161
6.6.2 习题 ………………………161
6.7 实训任务 …………………………162
6.8 课外拓展 …………………………163
第7章 排序算法………………………165
7.1 案例：电商平台商品列表 ………………………165
7.1.1 案例描述 ………………………165
7.1.2 案例实现………………………166
7.2 排序算法 …………………………167
7.2.1 排序算法的定义 ………………………167
7.2.2 常见排序算法 ………………………168
7.2.3 排序算法分析 ………………………169
7.3 插入排序 …………………………170
7.3.1 算法原理 ………………………170
7.3.2 算法实现………………………170
7.3.3 算法分析 ………………………171
7.3.4 算法优化之希尔排序 ………………………172
7.4 选择排序 …………………………173
7.4.1 算法原理 ………………………173
7.4.2 算法实现………………………174
7.4.3 算法分析 ………………………175
7.5 冒泡排序 …………………………175
7.5.1 算法原理 ………………………175
7.5.2 算法实现………………………178
7.5.3 算法分析 ………………………179
7.6 快速排序 …………………………179
7.6.1 算法原理 ………………………179
7.6.2 算法实现 ………………………181
7.6.3 算法分析 ………………………182
7.7 归并排序………………………182
7.7.1 算法原理 ………………………182
7.7.2 算法实现 ………………………183
7.7.3 算法分析 ………………………184
7.8 桶排序………………………185
7.8.1 算法原理 ………………………185
7.8.2 算法实现………………………186
7.8.3 算法分析 ………………………187
7.9 计数排序 ………………………188
7.9.1 算法原理 ………………………188
7.9.2 算法实现………………………189
7.9.3 算法分析 ………………………191
7.10 基数排序………………………191
7.10.1 算法原理………………………191
7.10.2 算法实现………………………192
7.10.3 算法分析………………………194
7.11 小结与习题………………………194
7.11.1 小结………………………194
7.11.2 习题………………………195
7.12 实训任务………………………196
7.13 课外拓展………………………197

蔡顺达，男，硕士，现为温州职业技术学院教师，软件设计师，前蚂蚁金服高级工程师。具有丰富大型分布式系统开发实践经验，主要从事大数据系统设计与实施、软件工程领域建模及分布式系统开发等相关领域研究与应用工作。近年主持和参与校级横向项目30余项，指导学生参与职业院校技能大赛等省级竞赛获得包括一等奖在内的奖项10余项。