高等学校计算机类课程应用型人才培养规划教材:数据结构导学与上机指导

本书根据“数据结构”课程的实际教学情况，在内容上力图具有一定的先进性和较强的适应性。遵循这一原则，在编写时着重讲述原理、概念和实例，将各章的知识要点进行归纳和总结；对难以理解的问题进行讲解和指导，对涉及重要知识点的典型题目进行分析和解答，帮助读者理解数据结构的内容，掌握各种数据结构的表示方法及应用实现。 

本书根据“数据结构”课程的实际教学情况，将各章的知识要点进行归纳和总结，对难以理解的问题进行讲解和指导，对涉及重要知识点的典型题目进行分析和解答，帮助读者理解数据结构的内容，掌握各种数据结构的表示方法及应用实现。为了提高学生的实践技能，编写了上机实验题目，希望对学生的上机实践起到一定的指导作用。本书按章节顺序，分为10章，每章按4个模块编写：重点内容概要、常见题型及典型题精解、学习效果测试、上机实验题目及参考代码。本书适合作为高等院校计算机类专业学生的教学用书，也可作为自学计算机编程者的参考用书。

李晓霞（1977.4—），女，甘肃张掖人，汉族，工学硕士（兰州大学计算机软件与理论专业硕士），现为河西学院副教授，从事计算机专业教学工作19年，主讲课程《数据结构》，《C程序设计》，《数据结构》课程2013年被评为校级精品课程，目前主持校级项目5项，发表SCI/EI论文4篇，省级论文十多篇，主编教材1部，参编教材1部。

第1 章 绪论……………………………….11.1 重点内容概要……………………… 11.1.1 基本概念和术语……………. 11.1.2 算法和算法分析……………. 21.2 常见题型及典型题精解………… 31.3 学习效果测试……………………… 61.4 上机实验题及参考代码………… 8第2 章 线性表………………………….112.1 重点内容概要……………………. 112.1.1 线性表……………………….. 112.1.2 线性表的顺序表示与实现……………………….. 122.1.3 线性表的链式表示与实现……………………….. 142.2 常见题型及典型题精解………. 182.3 学习效果测试……………………. 232.4 上机实验题及参考代码………. 27第3 章 栈和队列……………………….323.1 重点内容概要……………………. 323.1.1 栈……………………………… 323.1.2 队列………………………….. 353.2 常见题型及典型题精解………. 403.3 学习效果测试……………………. 443.4 上机实验题及参考代码………. 47第4 章 串………………………………..514.1 重点内容概要……………………. 514.1.1 串的基本概念……………… 514.1.2 串的存储结构……………… 524.1.3 串的模式匹配算法………. 584.2 常见题型及典型题精解………. 604.3 学习效果测试……………………. 654.4 上机实验题及参考代码………. 66第5 章 数组和广义表…………………705.1 重点内容概要……………………. 705.1.1 数组的定义………………… 705.1.2 数组的存储结构………….. 705.1.3 广义表的定义……………… 765.1.4 广义表的存储结构………. 785.1.5 广义表的基本操作实现… 795.2 常见题型及典型题精解………. 805.3 学习效果测试……………………. 835.4 上机实验题及参考代码………. 85第6 章 树和二叉树……………………916.1 重点内容概要……………………. 916.1.1 树……………………………… 916.1.2 二叉树……………………….. 926.1.3 遍历二叉树和线索二叉树……………………….. 996.1.4 二叉树的非递归实现….. 1016.1.5 树和森林………………….. 1036.1.6 赫夫曼树及应用………… 1056.2 常见题型及典型题精解…….. 1056.3 学习效果测试………………….. 1126.4 上机实验题及参考代码…….. 116第7 章 图………………………………1237.1 重点内容概要………………….. 1237.1.1 图的基本概念……………. 1237.1.2 图的存储结构……………. 1247.1.3 图的遍历………………….. 1277.1.4 图的连通性及最小生成树……………………… 1317.1.5 有向无环图及其应用….. 132数据结构导学与上机指导II7.1.6 最短路径………………….. 1347.2 常见题型及典型题精解…….. 1347.3 学习效果测试………………….. 1407.4 上机实验题及参考代码…….. 144第8 章 查找……………………………1488.1 重点内容概要………………….. 1488.1.1 基本概念………………….. 1488.1.2 静态查找表………………. 1498.1.3 动态查找表………………. 1528.1.4 哈希表……………………… 1558.1.5 各种查找方法的比较….. 1588.2 常见题型及典型题精解…….. 1588.3 学习效果测试………………….. 1658.4 上机实验题及参考代码…….. 169第9 章 排序……………………………1719.1 重点内容概要………………….. 1719.1.1 排序的基本概念………… 1719.1.2 插入排序………………….. 1729.1.3 交换排序………………….. 1739.1.4 选择排序………………….. 1759.1.5 归并排序………………….. 1789.1.6 基数排序………………….. 1799.1.7 各种内部排序方法的比较…………………………. 1809.1.8 外部排序简介……………. 1819.2 常见题型及典型题精解…….. 1819.3 学习效果测试………………….. 1849.4 上机实验题及参考代码…….. 187第10 章 文件………………………….19110.1 重点内容概要………………… 19110.1.1 文件的基本概念………. 19110.1.2 顺序文件………………… 19210.1.3 索引文件………………… 19210.1.4 索引顺序文件………….. 19210.1.5 直接存取文件（散列文件）……………. 19310.1.6 多关键字文件………….. 19410.2 常见题型及典型题精解…… 19410.3 学习效果测试………………… 19710.4 上机实验题及参考代码…… 200第1 章 绪论……………………………….11.1 重点内容概要……………………… 11.1.1 基本概念和术语……………. 11.1.2 算法和算法分析……………. 21.2 常见题型及典型题精解………… 31.3 学习效果测试……………………… 61.4 上机实验题及参考代码………… 8第2 章 线性表………………………….112.1 重点内容概要……………………. 112.1.1 线性表……………………….. 112.1.2 线性表的顺序表示与实现……………………….. 122.1.3 线性表的链式表示与实现……………………….. 142.2 常见题型及典型题精解………. 182.3 学习效果测试……………………. 232.4 上机实验题及参考代码………. 27第3 章 栈和队列……………………….323.1 重点内容概要……………………. 323.1.1 栈……………………………… 323.1.2 队列………………………….. 353.2 常见题型及典型题精解………. 403.3 学习效果测试……………………. 443.4 上机实验题及参考代码………. 47第4 章 串………………………………..514.1 重点内容概要……………………. 514.1.1 串的基本概念……………… 514.1.2 串的存储结构……………… 524.1.3 串的模式匹配算法………. 584.2 常见题型及典型题精解………. 604.3 学习效果测试……………………. 654.4 上机实验题及参考代码………. 66第5 章 数组和广义表…………………705.1 重点内容概要……………………. 705.1.1 数组的定义………………… 705.1.2 数组的存储结构………….. 705.1.3 广义表的定义……………… 765.1.4 广义表的存储结构………. 785.1.5 广义表的基本操作实现… 795.2 常见题型及典型题精解………. 805.3 学习效果测试……………………. 835.4 上机实验题及参考代码………. 85第6 章 树和二叉树……………………916.1 重点内容概要……………………. 916.1.1 树……………………………… 916.1.2 二叉树……………………….. 926.1.3 遍历二叉树和线索二叉树……………………….. 996.1.4 二叉树的非递归实现….. 1016.1.5 树和森林………………….. 1036.1.6 赫夫曼树及应用………… 1056.2 常见题型及典型题精解…….. 1056.3 学习效果测试………………….. 1126.4 上机实验题及参考代码…….. 116第7 章 图………………………………1237.1 重点内容概要………………….. 1237.1.1 图的基本概念……………. 1237.1.2 图的存储结构……………. 1247.1.3 图的遍历………………….. 1277.1.4 图的连通性及最小生成树……………………… 1317.1.5 有向无环图及其应用….. 132数据结构导学与上机指导II7.1.6 最短路径………………….. 1347.2 常见题型及典型题精解…….. 1347.3 学习效果测试………………….. 1407.4 上机实验题及参考代码…….. 144第8 章 查找……………………………1488.1 重点内容概要………………….. 1488.1.1 基本概念………………….. 1488.1.2 静态查找表………………. 1498.1.3 动态查找表………………. 1528.1.4 哈希表……………………… 1558.1.5 各种查找方法的比较….. 1588.2 常见题型及典型题精解…….. 1588.3 学习效果测试………………….. 1658.4 上机实验题及参考代码…….. 169第9 章 排序……………………………1719.1 重点内容概要………………….. 1719.1.1 排序的基本概念………… 1719.1.2 插入排序………………….. 1729.1.3 交换排序………………….. 1739.1.4 选择排序………………….. 1759.1.5 归并排序………………….. 1789.1.6 基数排序………………….. 1799.1.7 各种内部排序方法的比较…………………………. 1809.1.8 外部排序简介……………. 1819.2 常见题型及典型题精解…….. 1819.3 学习效果测试………………….. 1849.4 上机实验题及参考代码…….. 187第10 章 文件………………………….19110.1 重点内容概要………………… 19110.1.1 文件的基本概念………. 19110.1.2 顺序文件………………… 19210.1.3 索引文件………………… 19210.1.4 索引顺序文件………….. 19210.1.5 直接存取文件（散列文件）……………. 19310.1.6 多关键字文件………….. 19410.2 常见题型及典型题精解…… 19410.3 学习效果测试………………… 19710.4 上机实验题及参考代码…… 200

“数据结构”课程是理工科院校计算机类相关专业必修的一门专业核心基础课，对初学者来说是比较困难、比较抽象的一门课程。本书根据“数据结构”课程的实际教学情况，在内容上力图具有一定的先进性和较强的适应性。遵循这一原则，在编写时着重讲述原理、概念和实例，将各章的知识要点进行归纳和总结；对难以理解的问题进行讲解和指导，对涉及重要知识点的典型题目进行分析和解答，帮助读者理解数据结构的内容，掌握各种数据结构的表示方法及应用实现。为了提高学生的实践技能，编写了上机实验题，希望对学生的上机实践起到一定的指导作用。本书共分10 章，每章按4 个模块编写：一、重点内容概要。这部分列出了每章的基本概念、基本术语、数据结构的存储描述、算法及算法分析。二、常见题型及典型题精解。根据本科课程考试和考研要求，总结每章的考点，精选出常见及典型题目，进行详细分析解答。三、学习效果测试。这部分是为读者检查学习效果和应试能力而设计的，通过练习，读者可以进一步加深对所学内容的理解，增强解题能力。四、上机实验题及参考代码。这部分给出典型的上机实验题的设计算法，在实验题的设计中，采用结构化编程方法，体现了数据结构中数据组织和数据处理的思想。本书从指导课程教学和考试的角度，通过大量涉及内容广、常见及经典的题型提供算法的思想，并对算法进行分析，提供了“数据结构”的解题方法、解题规律和解题技巧。这对提高读者分析问题的能力，理解基本要领和理论，开拓解题思路，会起到良好的效果。对于学习效果测试题，希望读者在学习过程中独立思考，自己动手解题。在本书的编写过程中，王玉明院长、赵柱处长、吴建军院长及祁昌平老师对本书的编写提出许多宝贵意见，在此表示衷心的感谢。由于时间仓促，编者水平有限，书中疏漏与不妥之处在所难免，恳请读者批评指正。编 者2019 年6 月