本书针对应用型本科高校计算机类专业编写，讲解数据结构的概念和原理，分析数据结构的基本运算，并给出了解决实际问题的各种经典算法。全书内容包括线性表、栈和队列、串、数组和广义表、树和二叉树、图、查找、排序。本书内容精练、逻辑性强、注重基础、突出重点、实例丰富、实用性强。
书中采用 C++语言描述算法，清晰简洁，易于学生理解和掌握。为帮助读者深入理解、巩固和深化理论知识，每章后配有习题，可供不同层次的读者选用。
本书适合作为应用型本科高校计算机类专业教材，也可作为信息类专业教材，还可作为计算机自学人员的学习用书。

“数据结构”是高等院校计算机科学与技术、网络空间安全、数据科学与大数据技术等计算机类专业的核心课程之一，是研究数据建模和人工智能的基础，也是计算机类专业考研的主要课程。掌握本课程的相关知识点，对于提高学生的计算思维、逻辑抽象思维、参加各类算法大赛，都有着非常重要的作用。
党的二十大报告提出，“坚持以人民为中心发展教育，加快建设高质量教育体系”，为了扎实落实“加强教材建设和管理”这一重要任务，满足社会对应用型人才的要求，探索和发展应用型本科高校的培养体系，提升学生对知识的实际运用能力，尤其是综合运用所学知识的能力，编著者组织一线教师编著了本书及配套的实训教程。书中内容丰富、系统、完整、深浅适度，语言生动形象，是编著者多年教学经验和心得体会的结晶。
本书内容分为9章，系统地讲解了线性表、栈、队列、串、数组、树、图等基本数据元素之间内在的逻辑关系，数据在计算机上的存储结构以及在各种结构上相关运算的实现，着重论述了查找和排序操作的各种典型算法及其实现。本书内容精练、逻辑性强、注重基础、突出重点，内容编排合理，结构清晰完整，在保证学科体系完整的基础上，不过度强调理论的深度和难度，注重应用型人才专业技能和工程应用技术的培养，既保证了一定的学术深度，又减少了知识重复。采用C++语言描述的数据结构与算法及泛型编程，具有高效、清晰、实用等特点。在书中加大训练部分的比重，采用“任务驱动”的编写方式，以实际问题引出相关的理论和概念，用实例导入本章的知识点，通过分析归纳，介绍解决实际问题的思想和方法。本书层次清晰，脉络分明，可读性和可操作性强。此外，本书配有实验分析案例和习题指导书，旨在帮助读者理解、巩固和深化应用知识的能力。
线上线下混合式学习已成为一种新的教学生态，本书是与在线课程资源双向关联、形成书网合一立体化的新形态教材，基于“互联网+”形成了相对稳定的纸质教材与动态更新的数字化资源，将信息技术与教学需求相融合，更好地实现课堂线上线下的深度融合。本书配有数据结构学习、实践网站，课程学习网址：https://www.educoder.net/paths/gtfnshro（可扫描下页二维码进入在线学习）。编著者精心制作了教学PPT，还录制了重要知识点的微视频，可在网站在线观看，也可以扫描书中的二维码，在手机等移动终端上观看。本书还对数据结构的知识脉络进行了清晰的梳理，支持学生拓展学习宽度，引导学生深度思考，把以教师“教”为中心转变成以学生“学”为中心。
各种数据结构中的算法描述都要选用一种语言工具，早期的数据结构教材大都采用Pascal语言为描述工具，后来出现了C语言作为描述工具。随着面向对象程序设计的兴起，如今采用C++语言、Java语言和Python语言作为描述工具更为普遍。本书采用C++语言描述数据结构和算法。考虑到使用本书的读者可能只学过C语言程序设计，而没有学过C++程序设计，书中体现算法的大部分代码并没有用到C++很深的知识点，懂C语言的读者完全能读懂。为了帮助读者快速掌握C++面向对象程序设计，使读者更好地学习数据结构自身的知识内容，减轻描述工具语言所带来的困扰，编著者在智慧树上建设了一门C++面向对象程序设计学习网站，有需要的读者可以扫描下方的二维码，或登录网址https://coursehome.zhihuishu.com/ourseHome/1000009965进行学习，有问题可以在问答区提问，课程团队有专职教师回答。
本书适合作为应用型本科高校计算机类专业教材，也可作为信息类专业教材，还可作为计算机自学人员的学习用书。本书兼顾不同层次的需求，具体授课时可根据各校的教学计划在内容上适当加以取舍。授课总学时可安排为48～64学时。
本书由李兰、刘庆海、张艳编著，其中第1章、第2章、第9章由李兰撰写，第3章、第4章、第7章、第8章由刘庆海撰写，第5章、第6章由张艳编撰写。李兰负责全书的统稿，并对部分章节和程序作了编辑和调试。
本书是编著者对高校计算机专业进行应用型教学改革的一次尝试。由于编著者水平有限，书中难免有遗漏或不妥之处，恳请广大读者指正。

第 1 章 绪论  1 
1.1 问题求解策略 ·······1 
1.1.1 问题抽象和求解 ·········· 1 
1.1.2 问题求解过程 ············· 2 
1.1.3 计算机求解问题过程 ···· 2 
1.2 数据结构概念 ·······3 
1.2.1 数据结构实例 ············· 3 
1.2.2 基本概念和术语 ·········· 6 
1.2.3 数据结构······ 7 
1.3 算法及其描述 ····· 10 
1.3.1 算法 ··········· 10 
1.3.2 算法描述····· 11 
1.4 算法分析与评价 ·· 12 
1.4.1 算法的设计要求 ········· 12 
1.4.2 算法效率的度量 ········· 12 
小结 ········· 15 
习题 ········· 15 
第 2 章 线性表 ·········· 19 
2.1 线性表的基本概念 ············· 19 
2.1.1 线性表的定义 ············ 19 
2.1.2 线性表的抽象数据类型  20 
2.2 线性表的顺序结构及运算实现 ············· 21 
2.2.1 线性表的顺序存储结构  21 
2.2.2 线性表在顺序存储结构下的运算实现 ·········· 23 
2.3 线性表的链式存储和运算实现 · 28 
2.3.1 链表的存储结构 ········· 29 
2.3.2 单链表 ········ 31 
2.3.3 循环链表····· 37 
2.3.4 双向链表····· 38 
2.3.5 循环双链表 · 42 
2.3.6 静态链表····· 43 
2.4 线性表的应用——一元多项式计算 ······· 44 
2.4.1 一元多项式表示 ········· 44 
2.4.2 一元多项式相加 ········· 45 
2.5 顺序表和链表的比较 ·········· 46 
小结 ········· 47 
习题 ········· 48 
第 3 章 栈和队列 ······· 52 
3.1 栈 ····· 52 
3.1.1 定义及其基本运算 ······ 52 
3.1.2 顺序栈及基本运算 ······ 54 
3.1.3 链式栈及基本运算 ······ 58 
3.2 栈的应用 ··········· 61 
3.2.1 中缀表达式 · 62 
3.2.2 后缀表达式 · 62 
3.2.3 后缀表达式求值 ········· 64 
3.3 栈与递归 ··········· 65 
3.3.1 递归定义····· 65 
3.3.2 递归过程····· 66 
3.3.3 应用举例····· 66 
3.4 队列··· 69 
3.4.1 定义及其基本运算 ······ 69 
3.4.2 顺序队列及基本运算 ··· 71 
3.4.3 链式队列及基本运算 ··· 74 
3.3.4 队列应用举例 ············ 77 
小结 ········· 79 
习题 ········· 79 
第 4 章 串 ·· 84 
4.1 串及其运算 ········ 84 
4.1.1 串的逻辑结构 ············ 84 
4.1.2 串的基本运算 ············ 85 
4.2 串的存储结构 ····· 87 
4.2.1 串的顺序存储结构及其基本运算的实现 ······· 87 
4.2.2 串的链式存储结构及其基本运算的实现 ······· 89 
4.2.3 串的堆分配存储结构及其基本运算的实现 ···· 93 
4.3 串的模式匹配 ····· 95 
4.3.1 Brute-Force 算法 ········· 95 
4.3.2 KMP 算法 ··· 96 
4.3.3 Sunday 算法 · 99 
4.4 串的应用 ·········· 100 
小结 ········ 101 
习题 ········ 101 
第 5 章 数组和广义表 ············· 104 
5.1 数组·· 104 
5.1.1 数组的定义 ············· 104 
5.1.2 数组的基本操作 ······· 105 
5.1.3 数组的存储结构 ······· 106 
5.2 矩阵的压缩存储 · 108 
5.2.1 特殊矩阵的压缩存储方法 ········· 108 
5.2.2 稀疏矩阵的压缩存储方法 ·········· 110 
5.3 广义表 ············· 120 
5.3.1 广义表的定义 ·········· 120 
5.3.2 广义表的存储结构 ···· 122 
5.3.3 广义表的基本操作 ···· 124 
小结 ········ 129 
习题 ········ 130 
第 6 章 树和二叉树 ·· 135 
6.1 树的基本概念 ···· 135 
6.1.1 树的定义和表示 ······· 135 
6.1.2 树的基本术语 ·········· 136 
6.2 二叉树 ············· 138 
6.2.1 二叉树的定义 ·········· 138 
6.2.2 二叉树的性质 ·········· 138 
6.3 二叉树的存储表示 ············ 142 
6.3.1 二叉树的顺序存储表示 ············ 142 
6.3.2 二叉树的链式存储表示 ············ 143 
6.4 二叉树的遍历及其应用 ······ 145 
6.4.1 二叉树遍历的递归算法 ············ 146 
6.4.2 二叉树遍历的应用 ···· 148 
6.4.3 二叉树遍历的非递归算法 ········· 151  
6.5 线索二叉树 ······· 157 
6.5.1 线索二叉树的概念 ···· 157 
6.5.2 中序线索化二叉树 ···· 159 
6.5.3 遍历中序线索化二叉树 ············ 163 
6.6 树与森林 ·········· 164 
6.6.1 树的存储表示 ·········· 164 
6.6.2 树/森林与二叉树的转换 ··········· 166 
6.6.3 树与森林的遍历 ······· 169 
6.7 哈夫曼树及其应用 ············ 170 
6.7.1 带权路径长度 ·········· 172 
6.7.2 哈夫曼树··· 173 
6.7.3 哈夫曼编码 ············· 177 
小结 ········ 178 
习题 ········ 179 
第 7 章 图  183 
7.1 图及其基本运算 · 183 
7.1.1 图的定义··· 183 
7.1.2 图的基本术语 ·········· 184 
7.1.3 图的基本运算 ·········· 185 
7.2 图的存储结构 ···· 186 
7.2.1 邻接矩阵··· 186 
7.2.2 邻接表 ······ 187 
7.2.3 十字链表··· 189 
7.2.4 邻接多重表 ············· 190 
7.3 图的遍历 ·········· 191 
7.3.1 深度优先遍历 ·········· 191 
7.3.2 广度优先遍历 ·········· 193 
7.4 最小生成树 ······· 195 
7.4.1 克鲁斯卡尔算法 ······· 195 
7.4.2 普里姆算法 ············· 197 
7.5 最短路径 ·········· 199 
7.5.1 求某一顶点到其余顶点的最短路径 ··········· 199 
7.5.2 每对顶点之间的最短路径 ········· 203 
7.6 拓扑排序 ·········· 206 
V 
7.7 关键路径 ·········· 209 
小结 ········ 213 
习题 ········ 213 
第 8 章 查找 ··········· 218 
8.1 基本概念 ·········· 218 
8.2 顺序表的静态查找 ············ 219 
8.2.1 顺序查找··· 219 
8.2.2 二分查找··· 220 
8.2.3 分块查找··· 223 
8.3 树表的动态查找 · 226 
8.3.1 二叉排序树 ············· 227 
8.3.2 平衡二叉树 ············· 232 
8.3.3 B 树 ········· 236 
8.4 哈希表查找 ······· 238 
8.4.1 哈希表的基本思想 ···· 238 
8.4.2 哈希函数的构造方法 · 238 
8.4.3 散列冲突及解决方法 · 240 
8.4.4 散列查找的性能分析 · 242 
小结 ········ 243 
习题 ········ 244 
第 9 章 排序 ··········· 248 
9.1 排序的基本概念 · 248 
9.1.1 排序及其分类 ·········· 248 
9.1.2 排序算法的效率分析 · 249 
9.2 插入排序 ·········· 250 
9.2.1 直接插入排序 ·········· 250 
9.2.2 折半插入排序 ·········· 252 
9.2.3 希尔排序··· 253 
9.3 交换排序 ·········· 255 
9.3.1 冒泡排序··· 255 
9.3.2 快速排序··· 257 
9.4 选择排序 ·········· 260 
9.4.1 简单选择排序 ·········· 260 
9.4.2 堆排序 ······ 261 
9.5 归并排序 ·········· 266 
9.6 基数排序 ·········· 269 
9.7 外部排序 ·········· 271 
9.7.1 外部排序过程 ·········· 272 
9.7.2 多路平衡归并 ·········· 272 
9.7.3 置换-选择排序 ········· 274 
9.8 各种排序方法的比较 ········· 275 
小结 ········ 276 

李兰，教授，主讲面向对象程序设计、数据结构、数据库原理、操作系统等10多门计算机主干课程。编写过6部教材，其中 一部荣获2009年山东省优秀教材二等奖，另一部教材在2020年全国高等学校优秀教材评选中获山东省优秀教材。主持省、市、校教改项目15项，目前主持1门省级一流课程，在科研方面，参加2项国家基金，4项山东省教育厅科技项目。

刘庆海，主讲程序设计、数据库应用及算法分析等课程，主编《计算机文化基础》《VFP程序基础》等教材。获"全国信息技术应用大赛"国家一等奖，主持并参与《计算机程序实践课的教学测评系统》、《计算机实践课技能考核方式研究与实现》和《基于Web的教学资源平台建设与研究》多项科研、教改等研究课题。荣获2015年度省青年教师教育教学研究成果二等奖、校区中青年教师教学课件比赛二等奖。

张艳，主讲数据结构、算法设计与分析、程序设计基础（C语言）、面向对象程序设计、Web系统与技术、Android程序设计、数据库系统概论、网站规划与实现等课程。参与编写《C++面向对象程序设计》教材。

（1）配有慕课课程，书中设置二维码，书中扫码即可观看教学视频。
（2）配有数据结构实验教程，有助于学生巩固理论知识，提高实践操作技能。