数据结构与算法设计相关课程是计算机专业教学中的核心课程，也是各类程序设计竞赛及互联网公司与软件企业招聘考查的重要方面。本书按照"数据结构—算法设计”的路线系统地介绍数据结构与算法设计的主要内容。其中，数据结构部分包括线性表、栈、队列、字符串、数组、广义表、树和图，以及两种常用的数据操作——查找和排序；算法设计部分包括递归与分治法、动态规划、贪心法、回溯法和分支限界法；最后以"快递超市信息管理系统”作为案例介绍面向实际应用开展分析、设计、编码与测试的完整过程。 本书融入了思政元素，注重培养学习者解决问题的思维能力，拥有丰富且形式多样的习题，能够同时满足数据结构与算法设计的教学和学习需求。 本书可以作为高等院校计算机科学与技术、软件工程、信息安全、智能科学与技术、物联网工程等计算机相关专业的本科生教材，也可以作为从事计算机应用开发的工程技术人员的参考用书。

驱动计算机解决问题的一组指令被称为程序。程序通过采用某种方法处理问题的相关信息得到相应的结果来解决问题，必然涉及问题相关信息的描述和解决问题的方法，数据结构就是描述问题相关信息的数据模型，算法则是处理问题的策略和方法。因此，瑞士计算机科学家、图灵奖获得者Niklaus Wirth 提出了“算法+数据结构=程序”这一计算机技术领域的著名公式。数据结构与算法设计相关课程一直以来都是计算机专业教学中的核心课程，也是各类程序设计竞赛及互联网公司与软件企业招聘考查的重要方面。要从事计算机科学与技术相关的工作，尤其是计算机应用领域的开发工作，必须掌握数据结构与算法设计的专业知识。 目前已经出版的有关数据结构与算法设计的教材大多独立介绍数据结构或算法设计的相关内容，同时包含两部分内容的教材较少，少量的此类教材也往往偏重于某一方面，对于另一方面的介绍不够充分。当前高校的人才培养模式正在发生重大变革，越来越多的高校通过调整专业培养计划缩减本科毕业所需的学时和课程，为学生提供更多的自主学习和实践的时间。数据结构课程和算法设计课程的合并逐渐成为调整计算机专业人才培养方案的一种趋势。同时，课程思政理念的提出要求本科生的思想政治教育不能再完全依赖专门的思政课程，而要发挥各门课程的思政教育功能，实现全员、全过程、全方位育人。当前对课程思政的探索和实践主要集中在教学环节，缺少符合课程思政理念的教材，导致课程育人体系缺失了教材思政这一关键的模块。基于上述原因，编写与出版融入思政元素、包含数据结构与算法设计课程内容、理论与实践完整且丰富的数据结构与算法设计教材是必要的。 全书共14章。第1章介绍数据结构与算法设计的基本知识、基础概念和方法。第2章至第6章介绍各种典型的数据结构及应用，包括线性表、栈、队列、字符串、数组、广义表、树和图。第7章和第8章分别介绍两种常用的数据操作——查找和排序。第9章至第13章分别介绍5种常用的算法设计方法，包括递归与分治法、动态规划、贪心法、回溯法和分支限界法。第14章通过一个案例介绍面向实际应用开展分析、设计、编码与测试的完整过程。 本书的特色如下。 （1）引入爱国主义、传统文化、大国工匠、科技报国和使命担当等思政元素，与基础概念、基本理论、基本方法等专业知识的传授融为一体，能够为选用本书作为教材的任课教师提供思政元素，助力课程思政教学。 （2）采用开篇统领、分部独立、交叉融合、前后呼应的组织结构，既对数据结构与算法设计的主要内容进行了充分展开，又对两者之间的交叉和关联部分进行了合并与呼应，能够同时满足数据结构与算法设计的教学和学习需求。 （3）注重培养学习者解决问题的思维能力。本书注重阐述问题的分析过程，不仅体现了“知其然”，更体现了“知其所以然”。应用实例采用“问题分析—算法描述—算法实现”这一体现问题求解过程的案例分析方法，清晰地展示了问题求解过程的完整脉络，能够为学习者的应用实践提供借鉴，有助于培养学习者解决问题的思维能力。 （4）有充分且细致的算法描述与代码注释。本书使用自然语言描述算法，给出了算法的C++实现代码，并对代码附有详细的注释，有助于学习者更好地理解和掌握算法。 （5）有丰富且形式多样的习题。本书收集与整理了大量习题，难度由浅入深，既适合入门学习者，也适合进阶学习者。 另外，本书提供电子教案及配套源码，所有源码全部在Microsoft Visual Studio 2015上运行通过。 全书的编写工作由王新宇老师和毛启容老师统筹协调；王新宇、王新胜、杨洋、刘金平、郑文怡、林琳6位老师参与了本书的编写工作；王新宇老师对全书进行了统稿、修改与完善；施化吉、辛燕2位老师负责全书的审阅。 在编写工作中，编者参考了国内外诸多数据结构教材和算法设计教材，从中汲取了一些好的思路和优秀的素材，在此向相关作者致谢。电子工业出版社负责本书编辑出版工作的全体人员为本书的出版付出了大量的辛勤劳动，他们细致认真、一丝不苟的工作精神保证了本书的出版质量，在此向他们表示诚挚的感谢。 由于编者的知识与写作水平有限，本书难免存在不足之处，欢迎同行专家和广大读者提出宝贵意见，让本书得以不断改进。 编者 2022年5月

第1章 绪论 1 1.1 数据结构的研究内容 1 1.2 数据结构的概念 4 1.2.1 基本术语 4 1.2.2 数据结构的三个要素 5 1.3 算法的定义和评价 7 1.3.1 算法的定义 7 1.3.2 算法的评价 7 1.4 算法性能分析 8 1.4.1 算法的时间复杂度分析 8 1.4.2 算法的空间复杂度分析 11 1.5 算法的设计与描述 11 1.5.1 算法设计的一般步骤 11 1.5.2 算法设计的基本策略 12 1.5.3 算法的描述 13 1.6 本章小结 14 习题一 15 第2章 线性表 18 2.1 线性表的定义及基本操作 18 2.2 线性表的顺序表示和实现 19 2.2.1 顺序表的定义 19 2.2.2 顺序表的类模板定义 20 2.2.3 顺序表基本操作的实现 20 2.3 线性表的链式表示和实现 25 2.3.1 单链表 25 2.3.2 单循环链表 32 2.3.3 双向循环链表 33 2.3.4 静态链表 37 2.4 线性表的应用 41 2.5 本章小结 45 习题二 46 第3章 栈和队列 49 3.1 栈 50 3.1.1 栈的定义 50 3.1.2 顺序栈 51 3.1.3 链栈 54 3.2 栈的应用 58 3.3 队列 65 3.3.1 队列的定义 66 3.3.2 循环队列 66 3.3.3 链队列 72 3.4 队列的应用 76 3.5 本章小结 82 习题三 82 第4章 字符串、数组和广义表 86 4.1 字符串 87 4.1.1 字符串的定义 87 4.1.2 C++字符串操作 88 4.1.3 模式匹配 88 4.2 数组 93 4.2.1 数组的定义 93 4.2.2 数组的顺序存储结构 93 4.3 特殊矩阵的压缩存储 95 4.3.1 对称矩阵和三角矩阵 95 4.3.2 带状矩阵 96 4.3.3 稀疏矩阵 97 4.4 广义表 101 4.5 本章小结 101 习题四 102 第5章 树 105 5.1 树的定义与术语 106 5.1.1 树的定义 106 5.1.2 树的术语 107 5.1.3 树的表示方法 107 5.1.4 树的基本操作 108 5.2 二叉树 108 5.2.1 二叉树的定义 108 5.2.2 二叉树的性质 109 5.2.3 二叉树的基本操作 110 5.3 二叉树的存储结构 111 5.3.1 二叉树的顺序存储结构 111 5.3.2 二叉树的链式存储结构 112 5.3.3 二叉树的二叉链表类模板 定义 112 5.4 二叉树的遍历 115 5.4.1 先序遍历 116 5.4.2 中序遍历 116 5.4.3 后序遍历 117 5.4.4 层次遍历 117 5.4.5 基于遍历的操作 118 5.5 线索二叉树 121 5.5.1 线索二叉树的定义 121 5.5.2 中序线索二叉树类模板定义 122 5.6 二叉树的应用 126 5.6.1 堆 127 5.6.2 哈夫曼树 133 5.7 树和森林 136 5.7.1 树的存储结构 136 5.7.2 树、森林和二叉树的转换 138 5.7.3 树的遍历 141 5.7.4 森林的遍历 141 5.8 本章小结 142 习题五 142 第6章 图 146 6.1 图的定义与术语 146 6.1.1 图的定义 146 6.1.2 图的术语 147 6.1.3 图的基本操作 149 6.2 图的存储结构 149 6.2.1 邻接矩阵 150 6.2.2 邻接表 156 6.2.3 邻接多重表 164 6.2.4 十字链表 165 6.3 图的遍历 166 6.3.1 深度优先遍历 166 6.3.2 广度优先遍历 168 6.4 图的应用 170 6.4.1 最小生成树 170 6.4.2 最短路径 173 6.4.3 活动网络 177 6.5 本章小结 184 习题六 185 第7章 查找 189 7.1 查找的基本概念 189 7.2 线性表的查找 191 7.2.1 顺序查找 191 7.2.2 折半查找 193 7.2.3 索引查找 195 7.3 树表查找 198 7.3.1 二叉排序树 198 7.3.2 平衡二叉树 206 7.3.3 B-树与B+树 213 7.4 散列查找 218 7.4.1 散列表的概念 218 7.4.2 散列函数的构造方法 219 7.4.3 解决冲突的方法 222 7.4.4 散列查找及其性能分析 224 7.5 本章小结 227 习题七 228 第8章 排序 231 8.1 排序的基础知识 232 8.2 交换排序 233 8.2.1 冒泡排序 233 8.2.2 快速排序 235 8.3 插入排序 237 8.3.1 直接插入排序 237 8.3.2 折半插入排序 239 8.3.3 希尔排序 240 8.4 选择排序 241 8.4.1 简单选择排序 242 8.4.2 堆排序 243 8.5 归并排序 245 8.5.1 两路归并算法 245 8.5.2 两路归并排序 247 8.6 基数排序 248 8.6.1 多关键字排序 248 8.6.2 链式基数排序 249 8.7 排序方法的比较 252 8.8 本章小结 253 习题八 253 第9章 递归与分治法 256 9.1 递归程序设计 256 9.1.1 递归的定义 256 9.1.2 递归的适用条件 257 9.1.3 递归的程序设计 259 9.1.4 递归的优缺点 264 9.2 分治法 265 9.2.1 分治法的基本思想 265 9.2.2 分治法的适用条件 266 9.2.3 分治法的设计步骤 266 9.3 分治法的应用实例 267 9.3.1 选择问题 267 9.3.2 排序问题 272 9.3.3 大整数的乘法 273 9.3.4 Strassen矩阵乘法 276 9.3.5 棋盘覆盖问题 278 9.3.6 循环赛日程安排 281 9.4 本章小结 284 习题九 284 第10章 动态规划 286 10.1 动态规划概述 286 10.1.1 动态规划的基本思想 286 10.1.2 动态规划的适用条件 287 10.1.3 动态规划的设计步骤 289 10.2 动态规划的应用实例 291 10.2.1 矩阵连乘问题 291 10.2.2 投资问题 295 10.2.3 0-1背包问题 299 10.2.4 最长公共子序列问题 303 10.3 本章小结 308 习题十 308 第11章 贪心法 310 11.1 贪心法概述 310 11.1.1 贪心法的基本思想 310 11.1.2 贪心法的适用条件 311 11.1.3 贪心法和动态规划的区别 312 11.1.4 贪心法的设计算法的步骤 312 11.1.5 贪心算法的正确性证明 313 11.2 贪心法的应用实例 313 11.2.1 活动安排问题 313 11.2.2 最优装载问题 316 11.2.3 背包问题 318 11.3 本章小结 321 习题十一 321 第12章 回溯法 323 12.1 回溯法概述 323 12.1.1 问题的解空间 323 12.1.2 回溯法的基本思想 325 12.1.3 回溯法的设计步骤与算法 框架 327 12.1.4 子集树与排列树 328 12.1.5 回溯法的适用条件 330 12.2 回溯法的应用实例 331 12.2.1 0-1背包问题 331 12.2.2 装载问题 335 12.2.3 n皇后问题 339 12.2.4 旅行商问题 342 12.3 本章小结 346 习题十二 346 第13章 分支限界法 348 13.1 分支限界法概述 348 13.1.1 分支限界法的基本思想 348 13.1.2 分支限界法的三个关键 问题 349 13.1.3 分支限界法的设计步骤 350 13.1.4 分支限界法的时间性能 350 13.1.5 分支限界法的适用条件 350 13.2 分支限界法的应用实例 351 13.2.1 0-1背包问题 351 13.2.2 旅行商问题 358 13.2.3 流水作业调度 360 13.2.4 单源点最短路径问题 365 13.3 本章小结 367 习题十三 367 第14章 快递超市信息管理系统 369 14.1 问题描述 369 14.2 需求分析 370 14.3 概要设计 370 14.3.1 模块设计 370 14.3.2 界面设计 371 14.3.3 类和数据结构设计 371 14.4 详细设计 373 14.4.1 类的详细设计 373 14.4.2 系统功能的详细设计 376 14.5 编码 377 14.6 测试 386 14.7 本章小结 391 习题十四 391 参考文献 392

http://www.hxedu.com.cn/hxedu/fg/book/bookinfo.html?code=G0449780