本书秉承第一版的教学方式,将理论与实践相融合,以降低课程学习难度,提高教学效率。同时为反映行业技术变化和课程改革新成果,对原有内容进行了修订与完善。全书将直流电路、交流电路、磁路、异步电动机四部分内容分为九个任务:安全用电和节约用电常识,电路模型的建立及基本物理量测试,电阻、电感及电容元件检测,万用表的装配与调试,单相正弦交流电路的分析与测试,三相交流电的识读及测试,变压器的认识与测试,三相异步电动机的认识,三相异步电动机简单控制电路实现。在教材编写过程中,以学生的就业为导向,以提高学生操作技能和职业素养为目的,以职业岗位和岗位群所需的电工技能为切入点,参照初、中级电工的职业资格标准和行业标准,强化职业能力培养。
本书适合作为高职院校机电工程类、电子信息类、通信工程类、自动化技术类专业教材,也适合中等职业学校、各级技能培训学校、职工大学等选用,还可作为电类从业人员自学的参考资料。
本书根据“数据结构”课程的实际教学情况,在内容上力图具有一定的先进性和较
强的适应性。遵循这一原则,在编写时着重讲述原理、概念和实例,将各章的知识要点
进行归纳和总结;对难以理解的问题进行讲解和指导,对涉及重要知识点的典型题目进
行分析和解答,帮助读者理解数据结构的内容,掌握各种数据结构的表示方法及应用实
现。
“数据结构”课程是理工科院校计算机类相关专业必修的一门专业核心基础课,对初
学者来说是比较困难、比较抽象的一门课程。
本书根据“数据结构”课程的实际教学情况,在内容上力图具有一定的先进性和较
强的适应性。遵循这一原则,在编写时着重讲述原理、概念和实例,将各章的知识要点
进行归纳和总结;对难以理解的问题进行讲解和指导,对涉及重要知识点的典型题目进
行分析和解答,帮助读者理解数据结构的内容,掌握各种数据结构的表示方法及应用实
现。为了提高学生的实践技能,编写了上机实验题,希望对学生的上机实践起到一定的
指导作用。
本书共分10 章,每章按4 个模块编写:
一、重点内容概要。这部分列出了每章的基本概念、基本术语、数据结构的存储描
述、算法及算法分析。
二、常见题型及典型题精解。根据本科课程考试和考研要求,总结每章的考点,精
选出常见及典型题目,进行详细分析解答。
三、学习效果测试。这部分是为读者检查学习效果和应试能力而设计的,通过练习,
读者可以进一步加深对所学内容的理解,增强解题能力。
四、上机实验题及参考代码。这部分给出典型的上机实验题的设计算法,在实验题
的设计中,采用结构化编程方法,体现了数据结构中数据组织和数据处理的思想。
本书从指导课程教学和考试的角度,通过大量涉及内容广、常见及经典的题型提供
算法的思想,并对算法进行分析,提供了“数据结构”的解题方法、解题规律和解题技
巧。这对提高读者分析问题的能力,理解基本要领和理论,开拓解题思路,会起到良好
的效果。对于学习效果测试题,希望读者在学习过程中独立思考,自己动手解题。
在本书的编写过程中,王玉明院长、赵柱处长、吴建军院长及祁昌平老师对本书的
编写提出许多宝贵意见,在此表示衷心的感谢。
由于时间仓促,编者水平有限,书中疏漏与不妥之处在所难免,恳请读者批评指正。
编 者
李晓霞(1977.4—),女,甘肃张掖人,汉族,工学硕士(兰州大学计算机软件与理论专业硕士),现为河西学院副教授,从事计算机专业教学工作19年,主讲课程《数据结构》,《C程序设计》,《数据结构》课程2013年被评为校级精品课程,目前主持校级项目5项,发表SCI/EI论文4篇,省级论文十多篇,主编教材1部,参编教材1部。
第1 章 绪论.....................................1
1.1 重点内容概要........................... 1
1.1.1 基本概念和术语................ 1
1.1.2 算法和算法分析................ 2
1.2 常见题型及典型题精解............ 3
1.3 学习效果测试........................... 6
1.4 上机实验题及参考代码............ 8
第2 章 线性表...............................11
2.1 重点内容概要......................... 11
2.1.1 线性表............................. 11
2.1.2 线性表的顺序表示
与实现............................. 12
2.1.3 线性表的链式表示
与实现............................. 14
2.2 常见题型及典型题精解.......... 18
2.3 学习效果测试......................... 23
2.4 上机实验题及参考代码.......... 27
第3 章 栈和队列............................32
3.1 重点内容概要......................... 32
3.1.1 栈.................................... 32
3.1.2 队列................................ 35
3.2 常见题型及典型题精解.......... 40
3.3 学习效果测试......................... 44
3.4 上机实验题及参考代码.......... 47
第4 章 串......................................51
4.1 重点内容概要......................... 51
4.1.1 串的基本概念.................. 51
4.1.2 串的存储结构.................. 52
4.1.3 串的模式匹配算法.......... 58
4.2 常见题型及典型题精解.......... 60
4.3 学习效果测试......................... 65
4.4 上机实验题及参考代码.......... 66
第5 章 数组和广义表.....................70
5.1 重点内容概要......................... 70
5.1.1 数组的定义..................... 70
5.1.2 数组的存储结构.............. 70
5.1.3 广义表的定义.................. 76
5.1.4 广义表的存储结构.......... 78
5.1.5 广义表的基本操作实现... 79
5.2 常见题型及典型题精解.......... 80
5.3 学习效果测试......................... 83
5.4 上机实验题及参考代码.......... 85
第6 章 树和二叉树........................91
6.1 重点内容概要......................... 91
6.1.1 树.................................... 91
6.1.2 二叉树............................. 92
6.1.3 遍历二叉树和线索
二叉树............................. 99
6.1.4 二叉树的非递归实现..... 101
6.1.5 树和森林....................... 103
6.1.6 赫夫曼树及应用............ 105
6.2 常见题型及典型题精解........ 105
6.3 学习效果测试....................... 112
6.4 上机实验题及参考代码........ 116
第7 章 图....................................123
7.1 重点内容概要....................... 123
7.1.1 图的基本概念................ 123
7.1.2 图的存储结构................ 124
7.1.3 图的遍历....................... 127
7.1.4 图的连通性及最小
生成树........................... 131
7.1.5 有向无环图及其应用..... 132
数据结构导学与上机指导
II
7.1.6 最短路径....................... 134
7.2 常见题型及典型题精解........ 134
7.3 学习效果测试....................... 140
7.4 上机实验题及参考代码........ 144
第8 章 查找.................................148
8.1 重点内容概要....................... 148
8.1.1 基本概念....................... 148
8.1.2 静态查找表................... 149
8.1.3 动态查找表................... 152
8.1.4 哈希表........................... 155
8.1.5 各种查找方法的比较..... 158
8.2 常见题型及典型题精解........ 158
8.3 学习效果测试....................... 165
8.4 上机实验题及参考代码........ 169
第9 章 排序.................................171
9.1 重点内容概要....................... 171
9.1.1 排序的基本概念............ 171
9.1.2 插入排序....................... 172
9.1.3 交换排序....................... 173
9.1.4 选择排序....................... 175
9.1.5 归并排序....................... 178
9.1.6 基数排序....................... 179
9.1.7 各种内部排序方法的
比较............................... 180
9.1.8 外部排序简介................ 181
9.2 常见题型及典型题精解........ 181
9.3 学习效果测试....................... 184
9.4 上机实验题及参考代码........ 187
第10 章 文件...............................191
10.1 重点内容概要..................... 191
10.1.1 文件的基本概念.......... 191
10.1.2 顺序文件..................... 192
10.1.3 索引文件..................... 192
10.1.4 索引顺序文件.............. 192
10.1.5 直接存取文件
(散列文件)................ 193
10.1.6 多关键字文件.............. 194
10.2 常见题型及典型题精解...... 194
10.3 学习效果测试..................... 197
10.4 上机实验题及参考代码...... 200第1 章 绪论.....................................1
1.1 重点内容概要........................... 1
1.1.1 基本概念和术语................ 1
1.1.2 算法和算法分析................ 2
1.2 常见题型及典型题精解............ 3
1.3 学习效果测试........................... 6
1.4 上机实验题及参考代码............ 8
第2 章 线性表...............................11
2.1 重点内容概要......................... 11
2.1.1 线性表............................. 11
2.1.2 线性表的顺序表示
与实现............................. 12
2.1.3 线性表的链式表示
与实现............................. 14
2.2 常见题型及典型题精解.......... 18
2.3 学习效果测试......................... 23
2.4 上机实验题及参考代码.......... 27
第3 章 栈和队列............................32
3.1 重点内容概要......................... 32
3.1.1 栈.................................... 32
3.1.2 队列................................ 35
3.2 常见题型及典型题精解.......... 40
3.3 学习效果测试......................... 44
3.4 上机实验题及参考代码.......... 47
第4 章 串......................................51
4.1 重点内容概要......................... 51
4.1.1 串的基本概念.................. 51
4.1.2 串的存储结构.................. 52
4.1.3 串的模式匹配算法.......... 58
4.2 常见题型及典型题精解.......... 60
4.3 学习效果测试......................... 65
4.4 上机实验题及参考代码.......... 66
第5 章 数组和广义表.....................70
5.1 重点内容概要......................... 70
5.1.1 数组的定义..................... 70
5.1.2 数组的存储结构.............. 70
5.1.3 广义表的定义.................. 76
5.1.4 广义表的存储结构.......... 78
5.1.5 广义表的基本操作实现... 79
5.2 常见题型及典型题精解.......... 80
5.3 学习效果测试......................... 83
5.4 上机实验题及参考代码.......... 85
第6 章 树和二叉树........................91
6.1 重点内容概要......................... 91
6.1.1 树.................................... 91
6.1.2 二叉树............................. 92
6.1.3 遍历二叉树和线索
二叉树............................. 99
6.1.4 二叉树的非递归实现..... 101
6.1.5 树和森林....................... 103
6.1.6 赫夫曼树及应用............ 105
6.2 常见题型及典型题精解........ 105
6.3 学习效果测试....................... 112
6.4 上机实验题及参考代码........ 116
第7 章 图....................................123
7.1 重点内容概要....................... 123
7.1.1 图的基本概念................ 123
7.1.2 图的存储结构................ 124
7.1.3 图的遍历....................... 127
7.1.4 图的连通性及最小
生成树........................... 131
7.1.5 有向无环图及其应用..... 132
数据结构导学与上机指导
II
7.1.6 最短路径....................... 134
7.2 常见题型及典型题精解........ 134
7.3 学习效果测试....................... 140
7.4 上机实验题及参考代码........ 144
第8 章 查找.................................148
8.1 重点内容概要....................... 148
8.1.1 基本概念....................... 148
8.1.2 静态查找表................... 149
8.1.3 动态查找表................... 152
8.1.4 哈希表........................... 155
8.1.5 各种查找方法的比较..... 158
8.2 常见题型及典型题精解........ 158
8.3 学习效果测试....................... 165
8.4 上机实验题及参考代码........ 169
第9 章 排序.................................171
9.1 重点内容概要....................... 171
9.1.1 排序的基本概念............ 171
9.1.2 插入排序....................... 172
9.1.3 交换排序....................... 173
9.1.4 选择排序....................... 175
9.1.5 归并排序....................... 178
9.1.6 基数排序....................... 179
9.1.7 各种内部排序方法的
比较............................... 180
9.1.8 外部排序简介................ 181
9.2 常见题型及典型题精解........ 181
9.3 学习效果测试....................... 184
9.4 上机实验题及参考代码........ 187
第10 章 文件...............................191
10.1 重点内容概要..................... 191
10.1.1 文件的基本概念.......... 191
10.1.2 顺序文件..................... 192
10.1.3 索引文件..................... 192
10.1.4 索引顺序文件.............. 192
10.1.5 直接存取文件
(散列文件)................ 193
10.1.6 多关键字文件.............. 194
10.2 常见题型及典型题精解...... 194
10.3 学习效果测试..................... 197
10.4 上机实验题及参考代码...... 200