本书是《数据结构》（李兰、刘庆海、张艳编著，中国铁道出版社有限公司出版）的配套实训案例教程，针对高等院校应用型本科计算机专业编写。依照主教材的章节架构，本书分为三部分：第一部分首先给出主教材中每一章的知识体系、学习指南、内容提要，然后根据相关知识点设置了若干验证性、设计性和综合性的实训案例，以培养学生运用理论知识解决实际问题的能力；第二部分为针对主教材各章知识点的习题及参考答案；第三部分是模拟试题及参考答案，可帮助学生检验和巩固理论知识。

本书适合作为普通高等院校应用型本科计算机专业“数据结构”课程的实训指导教材，也可作为信息类相关专业的实训指导教材，还可以供计算机自学人员学习参考。

“数据结构”是高校计算机相关专业的核心课程之一，许多高校都开设这门课程。然而，编著者在“数据结构”实际教学过程中，发现学生欠缺解决实际问题的能力。解决这一问题的有效途径就是加强实践环节，通过实训案例提升学生的学习兴趣，培养学生如何正确判断和选择什么是最佳的数据结构和算法，以提高学生对算法时间和空间复杂度的认识。只有让学生亲自动手解决一些具体问题，才能帮助学生建立抽象思维和处理数据的能力。

本书是《数据结构》（李兰、刘庆海、张艳编著，中国铁道出版社有限公司出版）的配套实训案例教程，内容分为三部分。

第一部分：学习指导与案例，依据主教材的章节架构，设置9章内容，包含主教材中每一章的知识体系学习指南、内容提要和实训案例。每一章的实训案例根据相关知识点分为验证性实训案例、设计性实训案例和综合性实训案例。在实训案例的设计中，采用面向对象的编程方法，以体现数据结构中数据组织和数据处理的思想。其中“学习指导”包括：线性结构的定义、组织形式、结构特征和类型说明，以及在两种存储方式下实现的插入、删除、查找的算法，循环链表、双（循环）链表的结构特点和在其上的插入、删除等操作，树状结构（二叉树的二叉链表存储方式、结点结构和类型定义、二叉树的基本运算及应用），图状结构（图的存储结构的表示方法），查找（顺序查找、树表查找、散列表查找的基本思想及存储、运算的实现），排序（插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序的基本思想及实现），以及数组和字符串的操作。这部分突出实训重点，培养学生应用理论知识解决实际问题的能力。

第二部分：习题与参考答案，内容包括主教材九章内容对应的习题及参考答案。

第三部分：模拟试题与参考答案，结合“数据结构”考研试题要求，检验和巩固理论知识。

为鼓励读者自主完成习题、模拟试题的练习，第二、三部分的参考答案将以电子档形式提供，读者可在教材相应标题处扫码二维码查看，或在中国铁道出版社有限公司的教学资源平台（http://www.tdpresscom/5leds/）下载。

数据结构的思想和原理是不依赖于编程语言的，但对于每一种抽象概念的具体实现和应用则需要一种编程语言作为载体。对于要解决的同一个问题，由于所采用的数据结构可能不同，所选择的计算方法（即算法）可能不同，编写出的程序就可能不同，但只要程序正确并且有效（即具有较好的时间和空间复杂度）即可。因此，每个人按照习题编写出的算法程序不要求与本书所给的解答完全一致，具有更好的性能即可。

本书具有如下特点：

（1）给出了Dev C++ 5环境下调试通过的范例程序（可在中国铁道出版社有限公司教学资源平台www.tdpress.com/51eds/下载），以便于学生在学习相关内容后自行上机实验。

（2）实训案例的设计注重培养学生应用数据结构解决实际问题的能力，同时录制了讲解视频，读者可扫描书中二维码观看。

本书由李兰、张艳、刘庆海编著，其中第1、2、9章由李兰编著，第5、6章及模拟试题、实训案例由张艳编著，第3、4、7、8章由刘庆海编著，张艳对本书的程序做了编辑和调试。全书由李兰统稿。

由于时间仓促，加之编著者水平有限，书中难免存在疏漏与不妥之处，恳请专家和读者批评指正。

编著者   

2023年5月

第一部分  学习指导与案例

第1章  绪论 2

1.1  知识体系 2

1.2  学习指南 3

1.3  内容提要 3

第2章  线性表 5

2.1  知识体系 5

2.2  学习指南 5

2.3  内容提要 6

2.3.1  线性表 6

2.3.2  线性表的顺序存储 6

2.3.3  线性表的链式存储 7

2.4  实训案例概要 7

2.4.1  验证性实训 7

2.4.2  设计性实训 16

2.4.3  综合性实训 19

第3章  栈和队列 23

3.1  知识体系 23

3.2  学习指南 24

3.3  内容提要 24

3.3.1  栈 24

3.3.2  队列 25

3.4  实训案例概要 25

3.4.1  验证性实训 25

3.4.2  设计性实训 31

3.4.3  综合性案例 37

第4章  串 43

4.1  知识体系 43

4.2  学习指南 43

4.3  内容提要 43

4.3.1  串的定义 43

4.3.2  串的存储结构 44

4.3.3  串的模式匹配运算 44

4.4  实训案例概要 45

4.4.1  验证性实训 45

4.4.2  设计性实训 48

第5章  数组和广义表 51

5.1  知识体系 51

5.2  学习指南 51

5.3  内容提要 52

5.3.1  数组 52

5.3.2  矩阵的压缩存储 52

5.3.3  广义表 52

5.4  实训案例概要 53

5.4.1  验证性实训 53

5.4.2  设计性实训 63

第6章  树和二叉树 64

6.1  知识体系 64

6.2  学习指南 65

6.3  内容提要 65

6.3.1  树 65

6.3.2  二叉树 66

6.3.3  哈夫曼树、哈夫曼编码 67

6.4  实训案例概要 68

6.4.1  验证性实训 68

6.4.2  设计性实训 80

6.4.3  综合性实训 84

第7章  图 88

7.1  知识体系 88

7.2  学习指南 88

7.3  内容提要 89

7.3.1  图 89

7.3.2  图的遍历 89

7.3.3  最小生成树 90

7.3.4  最短路径 90

7.3.5  拓扑排序 90

7.3.6  关键路径 91

7.4  实训案例概要 91

7.4.1  验证性实训 91

7.4.2  设计性实训 98

7.4.3  综合性实训 108

第8章  查找 110

8.1  知识体系 110

8.2  学习指南 110

8.3  内容提要 111

8.3.1  顺序表的静态查找 111

8.3.2  树表的动态查找 112

8.3.3  哈希表查找 114

8.4  实训案例概要 115

8.4.1  验证性实训 115

8.4.2  设计性实训 121

8.4.3  综合性实训 124

第9章  排序 131

9.1  知识体系 131

9.2  学习指南 132

9.3  内容提要 132

9.3.1  插入排序 132

9.3.2  交换排序 132

9.3.3  选择排序 133

9.3.4  归并排序 133

9.3.5  基数排序 133

9.3.6  外部排序 133

9.4  实训案例概要 133

第二部分  习题与参考答案

一、习题 142

第1章  绪论习题 142

第2章  线性表习题 144

第3章  栈和队列习题 148

第4章  串习题 152

第5章  数组和广义表习题 154

第6章  树和二叉树习题 158

第7章  图习题 161

第8章  查找习题 164

第9章  排序习题 167

二、习题参考答案 172

第三部分  模拟试题与参考答案

一、模拟试题 174

二、模拟试题参考答案 185

李兰，硕士，教授，任职于青岛理工大学，主讲面向对象程序设计、数据结构、数据库原理、操作系统等10多门计算机主干课程。编写过6部教材，其中 一部荣获2009年山东省优秀教材二等奖，另一部教材在2020年全国高等学校优秀教材评选中获山东省优秀教材（已公示）。主持省、市、校教改项目15项，目前主持1门省级一流课程，在科研方面，参加2项国家基金，4项山东省教育厅科技项目。,张艳，女，讲师，任职于青岛理工大学，主讲数据结构、算法设计与分析、程序设计基础（C语言）、面向对象程序设计、Web系统与技术、Android程序设计、数据库系统概论、网站规划与实现等课程。参与编写《C++面向对象程序设计》教材。,刘庆海，男，讲师，任职于青岛理工大学，主讲程序设计、数据库应用及算法分析等课程，主编《计算机文化基础》《VFP程序基础》等教材。获"全国信息技术应用大赛"国家一等奖，主持并参与《计算机程序实践课的教学测评系统》、《计算机实践课技能考核方式研究与实现》和《基于Web的教学资源平台建设与研究》多项科研、教改等研究课题。荣获2015年度省青年教师教育教学研究成果二等奖、校区中青年教师教学课件比赛二等奖。

①加强实践环节，通过“项目驱动”式的实训案例，培养学生对算法时间和空间复杂度的改进认识，帮助学生建立抽象思维和处理数据的能力。
②每一章的实训案例根据相关知识点分为验证性实训案例、设计性实训案例和综合性实训案例，突出实训重点，培养学生应用理论知识解决实际问题的能力。
③配有案例操作视频。