数据结构与算法

（1）特色及突破①案例式引入，解决实际问题每章以真实的应用案例作为开篇，在知识点讲解以后再给出完整的解决方案，激发学生兴趣，并展示数据结构在解决实际问题中的重要性。在引入案例时，提供详细的场景描述，包括问题的背景、挑战和需求，这有助于学生理解为什么需要特定的数据结构来解决问题。②完善代码结构，增强宏观理解2015年使用过大多数985、211高校在用的清华大学严蔚敏教授的《数据结构（C语言版）》，此教材使用伪代码，对初学者挑战太大，学生觉得太难了，于是换成李云清教授的《数据结构》，此教材所有算法均配有源码，学生对基本算法上手比较快，一直沿用至今，但该教材只有子函数没有主函数，学生初学时自己编写代码运行会有小困难。因此，本教材计划增加主函数，引领读者对各个基本操作有机结合有一个宏观体验，另外，对不同的逻辑结构和同一逻辑结构的不同存储结构进行比较，让读者清楚何种情况下选择何种结构效率更高。③新增代码构建思路，培养学生的结构化思维目前国内教材对于算法原理讲解较多，算法构建思路相对薄弱，对应用型大学学生来说，如何通过分析需求、选择合适的逻辑和存储结构、构建自己的程序设计思维，最后设计出算法这个过程特别重要，能够帮助学生把知识点内化，解决“看起来容易写起来难”的问题，所以，本教材计划在普通教材算法描述和算法分析的基础上，增加问题分析、计算模型和算法设计环节，逐步培养读者的算法设计思维。④新增适合人工智能和大数据的经典算法增加一个章节用来讲解分治法、回溯法、贪心算法和动态规划等经典算法，提高读者分析问题和设计算法的能力，也为后续《机器学习》、《深度学习》等课程的算法学习奠定基础。（2）重难点处理①“本章小结”突出重难点每章最后设计“本章小结”环节，帮助读者梳理所学知识，对重难点内容进一步强化。②微课视频讲解对重难点在知识点旁边配备微课视频讲解二维码，读者可扫描二维码进行预习和复习，可通过反复观看结合教材文字内容加深理解。

本书是一本针对计算机科学领域的专业基础性教材。全书共分为9章，涵盖了数据结构与算法的基本概念、线性表、栈和队列、串、树、图、查找、排序、算法分析与设计等方面的知识。本书的编写以“案例驱动”为特色，通过生动的案例引人，帮助读者更加直观地理解和应用理论知识。此外，本书还采用了大量的图解和代码示例、以深入浅出的方式呈现出复杂的算法过程，帮助读者轻松地掌握编程方法。本书内容难度适中，适用于应用型大学的学习者，旨在培养学生的结构化思维能力，提升学生解决实际问题的能力，并为学生构建稳周的数据结构与算法知识体系打下基础。

主要担任课程：C语言程序设计、数据结构与算法设计、通信系统综合实训、专业英语主要发表论文：1、2022年1月《The Construction and Research of the Platform of Intelligent Sharing Laboratory Based on Big Data》，EI会议2、2021年8月《基于OBE理念的通信专业实训课程改革研究与探索》3、2020年10月《基于iLab三层架构的智能共享实验室的研究》4、2018年6月《对分课堂在《专业英语》教学中的应用与研究》5、2017年5月 《数据结构与算法课程教学改进与探索》6、2017年4月 《基于B/S模式的中小企业信息管理系统的实现》主持项目：1、2021.12-至今，武汉工商学院“成果导向”课程教学改革实践项目，主持2、2019.3-至今，《基于iLab结构的智能共享实验室的研究》，湖北省科技厅指导规划项目，主持3、2017.9-2018.9，《教育部产学合作协同育人通信综合实训室建设项目》，主持4、2019.3-2020.3，《2018-2019学年第二学期课堂教学使用智慧教学工具课程》，主持5、2019.2-2020.2，《2019年“课程思政”专项课程建设》，主持6、2019.6-2021.6，《基于OBE理念的通信专业实训课程改革》，主持所获荣誉及奖励：1、2023年1月 校年度优秀员工2、2022年1月 校“教学创新大赛”一等奖3、2020年12月 校年度优秀员工4、2020年12月 指导学士学位论文获校级优秀学士学位论文指导老师5、2017年12月 校年度优秀员工

第1章绪论1
1.1数据结构的研究内容1
1.2数据结构的基本概念1
1.2.1逻辑结构2
1.2.2存储结构4
1.3常用术语5
1.3.1数据6
1.3.2数据对象6
1.3.3数据元素6
1.3.4数据项7
1.4数据类型和抽象数据类型7
1.4.1数据类型7
1.4.2抽象数据类型8
1.5算法和算法分析9
1.5.1算法的定义及特性9
1.5.2算法的评价标准9
1.5.3算法的时间复杂度10
1.5.4算法的空间复杂度13
1.6C语言基础15
1.6.1指针16
1.6.2结构体16
1.6.3函数参数传递18
1.6.4内存的动态分配与释放20
1.7本章小结21
习题22
第2章线性表24
2.1案例引入24
2.2线性表的基本概念25
2.2.1线性表的定义及特点25
2.2.2线性表的基本操作26
2.3线性表的顺序存储27
2.3.1顺序表的定义27
2.3.2顺序表基本操作的实现28
2.3.3顺序表的应用38
2.4线性表的链式存储41
2.4.1单链表的定义41
2.4.2单链表基本操作的实现42
2.4.3单链表的应用56
2.4.4循环单链表58
2.4.5双向链表61
2.5顺序表和链表的比较66
2.6案例分析与实现67
2.6.1案例一67
2.6.2案例二70
2.7本章小结74
习题76
第3章栈和队列78
3.1案例引入78
3.2栈80
3.2.1栈的定义及其运算描述80
3.2.2顺序栈及其基本操作81
3.2.3链栈及其基本操作84
3.3队列88
3.3.1队列的定义及运算描述88
3.3.2顺序队列及其基本操作89
3.3.3链队及其基本操作95
3.4案例分析与实现100
3.4.1案例一100
3.4.2案例二101
3.4.3案例三104
3.4.4案例四109
3.5本章小结111
习题111
第4章串113
4.1案例引入113
4.2串及其基本运算114
4.2.1串的基本概念114
4.2.2串的基本运算115
4.3串的存储结构122
4.3.1串的顺序存储结构122
4.3.2串的链式存储结构124
4.4串的模式匹配125
4.4.1朴素的模式匹配算法125
4.4.2KMP算法128
4.5案例分析与实现134
4.6本章小结136
习题137
第5章树139
5.1案例引入139
5.2树140
5.2.1树的定义140
5.2.2树的基本术语140
5.2.3树的存储结构141
5.3二叉树145
5.3.1二叉树的定义145
5.3.2二叉树的性质146
5.3.3二叉树的存储结构148
5.4二叉树的遍历149
5.4.1二叉树的遍历方法及递归实现149
5.4.2二叉树遍历的非递归实现152
5.4.3根据遍历序列确定二叉树154
5.5二叉树遍历的应用155
5.5.1二叉树的建立155
5.5.2复制二叉树156
5.5.3计算二叉树的深度157
5.5.4二叉树的查找158
5.5.5判断二叉树是否等价158
5.5.6统计二叉树中结点的个数159
5.5.7统计二叉树的叶子数160
5.6线索二叉树160
5.6.1线索二叉树的基本概念160
5.6.2线索二叉树的构造及遍历161
5.7树、森林与二叉树的转换164
5.7.1树、森林到二叉树的转换164
5.7.2二叉树到树、森林的转换165
5.8哈夫曼树及其应用166
5.8.1哈夫曼树的基本概念166
5.8.2哈夫曼编码168
5.9案例分析与实现169
5.10本章小结174
习题175
第6章图177
6.1案例引入177
6.2图的定义和基本术语179
6.2.1图的定义179
6.2.2图的基本术语179
6.3图的存储结构182
6.3.1邻接矩阵182
6.3.2邻接表187
6.4图的遍历191
6.4.1广度优先遍历（BFS）191
6.4.2深度优先遍历（DFS）195
6.5图的应用198
6.5.1*小生成树198
6.5.2*短路径212
6.6案例分析与实现226
6.6.1案例一226
6.6.2案例二228
6.7本章小结233
习题235
第7章查找237
7.1案例引入237
7.2查找的基本概念237
7.2.1查找的定义238
7.2.2查找方法的分类239
7.2.3查找用到的结构和函数240
7.3线性表的查找240
7.3.1顺序查找240
7.3.2折半查找243
7.3.3分块查找247
7.4树表查找250
7.4.1二叉排序树250
7.4.2平衡二叉排序树261
7.5案例分析与实现273
7.5.1案例一273
7.5.2案例二275
7.6本章小结279
习题280
第8章排序283
8.1案例引入283
8.2排序的基本概念与分类284
8.2.1排序的基本概念284
8.2.2排序方法的分类286
8.2.3排序用到的结构与函数287
8.3插入排序288
8.3.1直接插入排序288
8.3.2希尔排序290
8.4交换排序293
8.4.1冒泡排序293
8.4.2快速排序296
8.4.3直接选择排序299
8.4.4堆排序301
8.5本章小结319
8.5.1排序算法的性能比较319
8.5.2排序算法比较320
习题320
第9章算法分析与设计323
9.1分治算法323
9.1.1分治算法概述323
9.1.2案例分析与实现323
9.2回溯算法326
9.2.1回溯算法概述326
9.2.2案例分析与实现327
9.3贪心算法329
9.3.1贪心算法概述329
9.3.2案例分析与实现330
9.4动态规划算法333
9.4.1动态规划算法概述333
9.4.2案例分析与实现334
9.5本章小结338
习题338
参考文献340