单元1 数据结构概述与基本算法分析 1
教学导航 1
引例剖析 1
任务1-1分析学生数据的结构特点和存储方式 1
任务1-2分析自行车的零部件结构和数据特点 3
任务1-3探析城市之间通信网络的最小造价问题 3
知识梳理 5
1.1数据结构的基本概念 5
1.2数据类型与抽象数据类型 7
1.3算法和算法分析 8
算法探究 11
任务1-4设计算法实现3个整数由小到大排序 11
任务1-5设计算法计算正整数的阶乘 12
任务1-6设计算法采用递归法计算阶乘 13
任务1-7设计算法判断素数 14
典型应用 15
任务1-8设计算法计算矩阵的乘法 15
任务1-9设计算法实现超长正整数求和运算 17
小试牛刀 18
任务1-10分析图书数据的结构特点和存储方式 18
任务1-11分析家族的家谱结构和数据特点 19
任务1-12分析建设城市之间高速公路网的最小造价问题 19
任务1-13探析时间最短的乘坐地铁线路 20
任务1-14分析最佳游览线路规划问题 22
任务1-15设计算法在数组中查找给定值 22
任务1-16设计算法计算阶乘的累加和 23
单元习题 24
单元2 线性表的分析与应用 27
教学导航 27
引例剖析 27
任务2-1以顺序表方式在数据表中插入与删除记录数据 27
任务2-2以单链表方式在数据表中插入与删除记录数据 30
知识梳理 36
2.1线性表的基本概念 37
2.2线性表的基本操作 37
2.3顺序表 38
2.4单链表 39
2.5循环链表 40
2.6双向链表 40
算法探究 41
任务2-3设计算法实现顺序表的基本操作 41
任务2-4设计算法实现单链表的基本操作 46
任务2-5设计算法实现双向链表的基本操作 53
任务2-6设计算法创建循环链表 59
典型应用 61
任务2-7应用顺序表实现“七乐彩”福利彩票的生成和中奖查询 61
任务2-8应用静态循环链表求解约瑟夫环 64
任务2-9应用动态循环链表求解约瑟夫环 66
小试牛刀 69
任务2-10设计算法实现顺序表的就地逆置 69
任务2-11设计算法实现单链表的逆置操作 70
任务2-12设计算法实现双向链表的逆序输出 71
单元习题 72
单元3 栈和队列的分析与应用 75
教学导航 75
引例剖析 75
任务3-1编写程序模拟子弹进出弹夹的过程 75
任务3-2编写程序模拟银行排队存取款的过程 78
知识梳理 80
3.1栈的定义 81
3.2栈的基本操作 81
3.3栈的存储结构 82
3.4队列 82
3.5队列的基本操作 82
3.6队列的存储结构 83
算法探究 83
任务3-3设计算法实现顺序栈的基本操作 83
任务3-4设计算法实现链栈的基本操作 87
任务3-5设计算法实现顺序队列的基本操作 91
任务3-6设计算法实现链队的基本操作 96
典型应用 100
任务3-7应用顺序栈实现十进制转换为其他进制 100
任务3-8应用顺序栈实现超长整数的加法运算 103
任务3-9应用顺序栈求算术表达式的值 108
任务3-10应用顺序队列实现消息的加密和解密 116
任务3-11应用链队输出符合规定要求的符号三角形 118
小试牛刀 122
任务3-12应用顺序栈将字符串逆序输出 122
任务3-13应用顺序栈检测括号是否匹配 123
任务3-14应用链栈判断字符串是否为回文字符串 124
任务3-15应用顺序队列模拟医院排队看病 126
单元习题 127
单元4 树结构的分析与应用 130
教学导航 130
引例剖析 130
任务4-1编写程序模拟家谱结构建立与遍历二叉树 131
知识梳理 135
4.1二叉树的基本概念 135
4.2树的基本概念 137
4.3树的表示 138
4.4二叉树的主要性质 139
4.5二叉树的存储结构 140
4.6树的存储结构 142
4.7二叉树的基本操作及实现 144
4.8二叉树的遍历 145
4.9树的基本操作 148
4.10树的遍历 149
4.11线索二叉树的定义及结构 149
4.12哈夫曼树及其应用 150
算法探究 151
任务4-2设计算法建立二叉树及实现其基本操作 151
任务4-3设计算法实现二叉树的多种遍历方式 157
任务4-4设计算法建立二叉线索树及实现其基本操作 166
任务4-5设计算法建立树及实现其基本操作 172
任务4-6设计算法建立哈夫曼树 181
任务4-7设计算法应用哈夫曼树构造哈夫曼编码方案 183
典型应用 188
任务4-8应用二叉树和栈求表达式的值 188
任务4-9应用哈夫曼编码实现文本文件的加密和解密 197
小试牛刀 203
任务4-10设计算法判断一棵二叉树是否为完全二叉树 203
任务4-11应用哈夫曼编码进行解码 204
单元习题 205
单元5 图结构的分析与应用 210
教学导航 210
引例剖析 210
任务5-1建立地铁站点的邻接矩阵 210
知识梳理 214
5.1图的基本概念 214
5.2图的基本操作 217
5.3图的存储表示方法 217
5.4图的遍历 219
5.5图的最小生成树 220
5.6图的最短路径 220
5.7AOV网与拓扑排序 222
算法探究 223
任务5-2设计算法建立有向图的邻接矩阵表示 223
任务5-3设计算法建立无向图的邻接表表示 225
任务5-4设计算法实现邻接矩阵表示的图的深度优先遍历 228
任务5-5设计算法实现邻接表表示的图的深度优先遍历 230
任务5-6设计算法实现邻接矩阵表示的图的广度优先遍历 233
任务5-7设计算法实现邻接表表示的图的广度优先遍历 235
典型应用 238
任务5-8应用普里姆算法求解最小生成树 238
任务5-9应用克鲁斯卡尔算法求解最小生成树 243
任务5-10应用迪杰斯特拉算法求解单源图的最短路径 248
任务5-11应用弗洛伊德算法求解无向图的最短路径 253
任务5-12编写程序实现拓扑排序算法并输出拓扑序列 257
小试牛刀 261
任务5-13建立高速公路线路图的邻接矩阵表示 261
任务5-14建立有向图的邻接表表示 261
任务5-15求解高速公路线路图的最小生成树 262
任务5-16求解花费时间最短的游览线路 262
单元习题 262
单元6 排序的分析与应用 266
教学导航 266
引例剖析 266
任务6-1应用直接插入排序法对磁盘数据进行排序 266
任务6-2应用选择排序法对商品数据进行排序 269
知识梳理 273
6.1排序的基本概念 273
6.2插入排序 274
6.3交换排序 276
6.4选择排序 278
6.5二路归并排序 279
算法探究 280
任务6-3设计算法实现插入排序 280
任务6-4设计算法实现希尔排序 282
任务6-5设计算法实现冒泡排序 284
任务6-6设计算法实现快速排序 286
任务6-7设计算法实现简单选择排序 290
任务6-8设计算法实现堆排序 292
任务6-9设计算法实现二路汇并排序 298
典型应用 300
任务6-10应用冒泡排序法和选择排序法对图书数据进行排序 300
任务6-11应用希尔排序法和堆排序法对学生数据进行排序 304
小试牛刀 307
任务6-12编写程序应用插入排序法实现图书销量的降序排列 307
任务6-13编写程序应用选择排序法实现成绩的降序排列 308
任务6-14编写程序应用冒泡排序法实现学生姓名的降序排列 309
单元习题 309
单元7 查找的分析与应用 315
教学导航 315
引例剖析 315
任务7-1查找指定名称的手机数据 315
知识梳理 317
7.1查找的基本概念 317
7.2静态查找 319
7.3二叉排序树及查找 322
7.4哈希表查找 323
算法探究 327
任务7-2设计算法应用顺序查找法查找指定数据 327
任务7-3设计算法应用折半查找法查找指定数据 329
任务7-4设计算法建立二叉排序树并查找指定数据 332
任务7-5设计算法应用哈希表实现数据的查找 335
典型应用 338
任务7-6应用顺序查找法查找图书数据 338
任务7-7应用二叉排序树查找学生数据 339
小试牛刀 341
任务7-8应用顺序查找法查找指定学号的学生数据 341
任务7-9应用折半查找法查找指定姓名的学生数据 342
单元习题 343
附录A 数据结构综合训练 345
附录B 数据结构常见术语中英文对照表 349
参考文献 351