数据结构与算法

全书共分为9章，主要包括绪论、线性表、栈和队列、字符串、树、图、查找、排序、算法分析与设计等内容，本书的特色是深入浅出，既注重理论又重视实践。，用案例驱动方式来设计内容，全书配有大量的例题和详尽的注释，各章都有小结和不同类型的习题。书中自始至终使用C语言来描述算法和数据结构，全部程序都在DEV或Visual C++ 6.0中调试通过。 本书是针对应用型大学的人工智能、大数据等专业“数据结构”课程编写的教材，可作为普通高等学校计算机及相关专业本科生的教材，也可以作为专科和成人教育的教材，还可供从事计算机应用的科技人员参考。

主要担任课程：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.6 C语言基础 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.2 KMP算法 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