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

王新宇，江苏大学计算机科学与通信工程学院，副教授。著作出版及论文发表情况：论著：（1）计算机视觉概论与操作实践，2019年12月，江苏凤凰科学技术出版社；（2）模式识别基础理论及其计算机视觉应用，2020年7月，西安电子科技大学出版社；主要论文：（1）A Zero-Watermarking Scheme for Three-Dimensional Mesh Models Based on Multi-Features， Multimedia Tools and Applications，2019，78卷第19期，SCI；（2）构造顶点分布特征的三维模型数字水印算法，计算机辅助设计与图形学学报， 2014，26卷第2期，EI；（3）数据结构课程思政教学设计与实践，计算机教育，2021，第1期。主要教学经历：C程序设计，2001年-2008年；C++程序设计，2006年-2010年；计算方法；2003年-至今；计算机图形学，2002年-至今；数据结构，2011年-至今。承担的主要教研项目：面向新工科的多维融合、多方协同的计算机专业人才培养研究与实践，江苏大学2017年高等教育教改研究课题（2017JGYB015）。承担的主要科研项目及获奖情况：主要科研项目：（1）基于模型自适应修正和协同决策的说话人鲁棒语音情感识别方法研究，国家自然科学基金（61003183）；（2）面向版权保护的三维模型鲁棒数字水印算法研究，高等学校博士学科点专项科研基金（20113227110021）；（3）三维模型鲁棒数字水印算法研究，江苏省研究生科研创新计划项目（CX10B_273Z）；科研获奖：音视频内容分析及其在行为监控与展现中的应用，江苏省科学技术进步三等奖，2018年。

第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