本书是江苏省高等学校重点教材《数据结构原理与应用》的配套教材，补充与拓展课堂教学内容，衔接理论与实践。本书在选材与编排上以易读易用易练可研为目标，为数据结构相关课程提供全方位的实践练习指导。全书分为4篇： 第1篇是原理篇，简述典型结构（线性表、栈和队列、数组和矩阵、树和二叉树、图等）及其在计算机中的实现原理，查找和排序的经典算法的原理；第2篇是验证篇，提供了主教材的算法实现；第3篇是设计篇，按主教材内容顺序，为每一章设计了3～5个设计型实践活动，适合作为课程实验素材；第4篇是综合篇，给出10个涉及多个知识点的复杂设计任务，可作为课程设计的素材。 本书内容全面，可单独作为数据结构相关课程的实践教材使用。本书提供的大量源程序和设计思想，对于从事计算机应用及开发的技术人员、数据结构和程序设计教授或学习的教师和学生具有很好的参考和指导作用。 本书源程序在Visual Studio 6.0及Visual Studio 2010调试通过，源代码可以在清华大学出版社官网下载。

本书是省重点教材《数据结构原理与应用》（ISBN:9787302589327，清华大学出版社出版）的配套教材，为《数据结构》或《数据结构与算法》等课程学习提供基础知识、验证、设计、综合等全方位的实践练习服务：原理篇扼要阐述典型结构及相关应用的实现原理；验证篇实现了主教材上的算法，设计篇提供基础性训练，可作为课程实验相关内容；综合篇提供较复杂、多知识点的综合训练，可作为课程设计的素材。秉承主教材可读可学可用可研的编写理念，本教材编写的总体原则是易读易用易练可研。

数据结构是一门有关程序设计理论与实践的基础性课程。数据结构的研究范畴涵盖典型的逻辑结构在计算机中的存储设计和操作实现及查找、排序等典型算法。逻辑结构用于实体的抽象，高性能的算法需要合适的存储设计和算法设计。有效的数据结构课程学习可以提高学习者用计算机求解问题、分析问题、设计方案和解决问题的能力。但如果只知理论而不把理论落实到实践中，将无法取得这些效果。因此，数据结构课程是一门实践性很强的课程。
本书是首批国家级一流本科课程、江苏省高等学校重点教材《数据结构原理与应用》（ISBN: 9787302589327，清华大学出版社出版）的配套教材，为数据结构或数据结构与算法等课程学习提供基础知识、验证、设计、综合等全方位的实践练习服务： 原理篇扼要阐述典型结构及相关应用的实现原理；验证篇实现了主教材上的算法；设计篇提供基础性训练，可作为课程实验相关内容；综合篇提供较复杂、多知识点的综合训练，可作为课程设计的素材。秉承主教材可读可学可教可研和可练的编写理念，本书编写的总体原则是易读易用易练可研。
1. 易读
原理篇以最少的篇幅、最易理解的描述方式及最精练的语言陈述与实践活动相关的理论知识，包括结构特性与存储描述以及算法原理。验证篇给出验证程序的设计思路、程序框架、函数调用关系，方便实践者分析、阅读和理解源程序，在运行验证程序时对源代码心中有数。
2. 易用
原理篇内容可以成为学生实践活动时的理论知识手册，方便查阅。验证篇的内容使实践者上机操作无碍： 源码无偿提供；第1章中给出源码的使用方法；对每个验证程序给出了运行与操作说明，一目了然。
3. 易练
设计篇对每一个任务从多个方面给出设计提示，包括数据结构设计、功能设计、核心算法设计和算法的类语言描述，启发实践者思路，减少有些实践者因设计上的偏颇无法完成实践的挫败感。设计篇对应主教材的每一章，给出3～5个不同难度的设计任务，适合不同水平实践者的需求。实践者也可以由易到难，渐进提高知识的应用与程序设计能力。设计报告是专业能力的一个方面，在工程专业认证中把其作为与同行沟通的方式之一。本书给出了实验报告和课程设计报告的撰写提纲，明确每一项的内容，并且给出了一个完整实验报告范例。验证程序和实验报告范例，有助于学生在模仿中练习与提高。
4. 可研
本书通过设置思考题，引导学习者在与实践相关的问题上深入研究。在验证程序的 思考题中，给出研读源程序回答问题和运行程序回答问题，引导学生阅读与理解程序的设计与程序功能。设计篇的测试与思考，通过测试用例引导学生完善算法设计，并且给出触类旁通的问题或本问题的深入讲解，打开研究思考之门。
千淘万漉虽辛苦，吹尽黄沙始到金。近二十年的教学积累形成了数据结构国家一流课程，凝聚而成了《数据结构原理与应用》和《数据结构原理与应用实践教程》两本书。希望它似一颗春天的种子，在今后的岁月里经过所有使用者的养育，能够秋收万颗子，为新工科教育作一份贡献。
感谢丁红、朱玲玲、周建美和刘维华为本书所做的工作： 丁红主要编写了设计篇的第7章、综合篇任务6和查找部分的验证程序，朱玲玲主要编写了设计篇的第2章和第4章，刘维华主要编写了设计篇的第6章和综合篇任务7，周建美主要编写了队列、查找、稀疏矩阵的验证程序，其余内容由徐慧编写。在本书的编写、出版过程中，得到清华大学出版社编辑的支持，在此表示深深的感谢！特别感谢袁勤勇主任，为主教材和本书的辛勤付出！
由于编者水平和时间有限，书中涉及的编程工作量大，难免有缺点和错误，恳请同行专家和读者批评指正，使本书在使用中不断精进。

编者2022年7月

第1篇原理篇
第1章线性表3
1.1顺序表3
1.1.1顺序表存储定义与特性3
1.1.2顺序表操作实现原理4
1.1.3顺序表的应用6
1.2链表7
1.2.1单链表存储定义与特性7
1.2.2单链表操作实现原理8
1.2.3链表的应用11第2章栈13
2.1顺序栈13
2.1.1顺序栈的存储定义和特性13
2.1.2顺序栈操作实现原理14
2.2链栈14
2.2.1链栈的存储定义和特性14
2.2.2链栈操作实现原理15
2.3栈的应用16第3章队列19
3.1循环队列19
3.1.1循环队列存储定义和特性19
3.1.2循环队列操作实现原理20
3.2链队21
3.2.1链队的存储定义和特性21
3.2.2链队的操作实现原理21
3.3队列的应用22第4章数组和矩阵23
4.1数组和矩阵的存储23
4.2稀疏矩阵转置23
4.3稀疏矩阵求和24第5章树和二叉树27
5.1树27
5.2二叉树27
5.2.1二叉树的存储定义27
5.2.2二叉树操作实现原理28
5.3线索二叉树31
5.3.1线索二叉树的存储定义31
5.3.2线索二叉树操作实现原理31
5.4最优二叉树33
5.4.1最优二叉树的存储定义和特性33
5.4.2最优二叉树的构建33
5.4.3哈夫曼编码的构建34第6章图35
6.1邻接矩阵存储35
6.1.1邻接矩阵存储定义与特性35
6.1.2邻接矩阵操作实现原理36
6.2图的邻接表存储37
6.2.1邻接表存储定义与特性37
6.2.2邻接表操作实现原理38
6.3图的遍历及其应用39
6.3.1深度优先遍历39
6.3.2广度优先遍历39
6.3.3连通性问题40
6.3.4求最远顶点40
6.4图的应用41
6.4.1求最小生成树41
6.4.2单源点最短距离42
6.4.3任意两点的最短距离42
6.4.4AOE网的拓扑排序43
6.4.5AOE网的关键活动43第7章查找45
7.1线性表查找45
7.2串的模式匹配46
7.3二叉排序树47
7.3.1二叉排序树存储定义与特性47
7.3.2二叉排序树操作实现原理47
7.4散列查找48
7.4.1散列技术48
7.4.2散列表操作实现原理48第8章排序51
8.1插入类排序51
8.2交换类排序52
8.3选择排序53
8.4二路归并排序54
8.5基数排序54
第2篇验证篇
第1章绪59
1.1算法到程序转换60
1.2验证性实践步骤63
1.3实验环境简介64
1.3.1VC 6.064
1.3.2VS系列67
1.4验证程序的设计71第2章线性表73
2.1顺序表73
2.2单链表82
2.3顺序表的应用95
2.4一元稀疏多项式求和101第3章栈和队列109
3.1顺序栈109
3.2链栈116
3.3栈的应用121
3.3.1括号匹配121
3.3.2表达式计算124
3.4顺序队列133
3.5链队140
3.6队列应用147第4章稀疏矩阵153
4.1稀疏矩阵转置153
4.2稀疏矩阵求和158第5章二叉树165
5.1二叉树简介165
5.2中序线索化二叉树176
5.3哈夫曼树和哈夫曼编码183第6章图189
6.1图的实现189
6.1.1程序设计简介189
6.1.2无向图的邻接矩阵实现190
6.1.3有向网的邻接表实现202
6.2图的遍历应用217
6.2.1邻接矩阵存储的图的遍历应用217
6.2.2邻接表存储的图的遍历应用221
6.3图的应用225
6.3.1最小生成树225
6.3.2最短距离232
6.3.3拓扑排序239
6.3.4关键活动244第7章查找251
7.1静态查找251
7.2字符串匹配256
7.3二叉排序树262
7.4散列查找270第8章内部排序277
第3篇设计篇
第1章绪299
1.1实验步骤299
1.2实验报告格式301
1.3实验报告案例301第2章线性表303
2.1实验目的303
2.2实验任务303
2.2.1集合运算303
2.2.2一元多项式求导305
2.2.3有序表合并307
2.2.4循环单链表309
2.2.5约瑟夫环问题311第3章栈和队列315
3.1实验目的315
3.2实验任务315
3.2.1数制转换315
3.2.2算术表达式正确性判断317
3.2.3栈的逆置318
3.2.4求任意长两个大整数的和319
3.2.5单指针链队问题322
3.2.6杨辉三角形问题324第4章数组和矩阵327
4.1实验目的327
4.2实验任务327
4.2.1求两个对称矩阵之和与乘积327
4.2.2蛇形矩阵329
4.2.3魔方问题330第5章树与二叉树333
5.1实验目的333
5.2实验任务333
5.2.1二叉树的叶结点计数333
5.2.2复制二叉树335
5.2.3求二叉树的宽度336
5.2.4求先/中/后序遍历序列的首、尾数据元素339
5.2.5叶结点路径问题341第6章图343
6.1实验目的343
6.2实验任务343
6.2.1存储结构转换问题343
6.2.2有向图的路径问题346
6.2.3无向图的路径问题350
6.2.4俱乐部选址问题352
6.2.5物流最短路径问题354第7章查找357
7.1实验目的357
7.2实验任务357
7.2.1顺序查找与折半查找357
7.2.2用二叉排序树实现字符统计358
7.2.3拉链法处理冲突的散列表360
7.2.4开放定址法处理冲突的散列表363第8章排序367
8.1实验目的367
8.2实验任务367
8.2.1单链表上的直接插入排序367
8.2.2单链表上的简单选择排序369
8.2.3双向冒泡排序370
8.2.4序列重排372
8.2.5堆判断374
第4篇综合篇
第1章绪论379
1.1综合设计内容380
1.2综合设计报告格式381第2章综合任务383
2.1个人乐库管理系统383
2.1.1问题描述383
2.1.2分析与设计提示383
2.1.3性能要求384
2.2高校学生信息快速查询系统384
2.2.1问题描述384
2.2.2分析与设计提示384
2.2.3性能要求386
2.3纸牌游戏386
2.3.1问题描述386
2.3.2分析与设计提示387
2.3.3性能要求388
2.4排雷游戏388
2.4.1问题描述388
2.4.2分析与设计提示389
2.4.3性能要求390
2.5迷宫问题390
2.5.1问题描述390
2.5.2分析与设计提示391
2.5.3性能要求393
2.6校园导游系统393
2.6.1问题描述393
2.6.2分析与设计提示393
2.6.3性能要求395
2.7打印任务管理395
2.7.1问题描述395
2.7.2分析与设计提示396
2.7.3性能要求396
2.8教学计划编制397
2.8.1问题描述397
2.8.2分析与设计提示398
2.8.3性能要求398
2.9基于哈夫曼编码的编码译码问题398
2.9.1问题描述398
2.9.2分析与设计提示398
2.9.3性能要求399
2.10校园优秀学生的推荐与评比400
2.10.1问题描述400
2.10.2分析与设计提示400
2.10.3性能要求401

参考文献403附录实验报告示例405
实验学生基本信息管理405
1问题描述与分析405
2数据结构设计406
3算法设计407
4运行与测试409
5小结410