数据结构学习辅导与实验指导

第一篇学习辅导
第1章绪论1
1.1本章导学1
1.2重点难点释疑5
1.2.1信息、数据与结构5
1.2.2数据结构、数据类型和抽象数据类型5
1.2.3逻辑结构与存储结构6
1.2.4如何选择或设计数据结构7
1.2.5问题、算法与程序7
1.2.6算法设计的一般原则8
1.2.7算法时间复杂度的分析方法9
1.3习题解析10
1.3.1课后习题讲解10
1.3.2学习自测及答案15
第2章线性表17
2.1本章导学17
2.2重点难点释疑19
2.2.1存储结构与存取结构19
2.2.2头指针、尾标志、开始结点与头结点19
2.2.3带头结点的单链表与不带头结点的单链表
的区别20
2.2.4单链表算法的设计技巧22
2.2.5有序单链表的算法设计技巧25
2.2.6循环链表的算法设计技巧27
2.2.7用单链表实现集合的操作27
2.3习题解析30
2.3.1课后习题讲解30
2.3.2学习自测及答案38
第3章特殊线性表——栈、队列和串43
3.1本章导学43
3.2重点难点释疑45
3.2.1浅析栈的操作特性45
3.2.2递归算法转换为非递归算法45
3.2.3循环队列中队空和队满的判定方法47
3.2.4如何利用循环链表实现队列的操作49
3.2.5模式匹配KMP算法中求next数组的算法49
3.3习题解析50
3.3.1课后习题讲解50
3.3.2学习自测及答案56
数据结构（C++版）学习辅导与实验指导目录
第4章广义线性表——多维数组和广义表59
4.1本章导学59
4.2重点难点释疑61
4.2.1特殊矩阵压缩存储后存储位置的计算61
4.2.2稀疏矩阵压缩存储的空间性能62
4.2.3广义表的表头和表尾62
4.3习题解析63
4.3.1课后习题讲解63
4.3.2学习自测及答案67
第5章树和二叉树69
5.1本章导学69
5.2重点难点释疑71
5.2.1二叉树和树是两种不同的树结构71
5.2.2二叉表示树72
5.2.3二叉树的构造方法73
5.2.4二叉树遍历的递归实现图解75
5.2.5二叉树算法的设计技巧75
5.2.6哈夫曼树的构造过程中应注意的问题77
5.3习题解析79
5.3.1课后习题讲解79
5.3.2学习自测及答案88
第6章图93
6.1本章导学93
6.2重点难点释疑95
6.2.1深度优先遍历算法的非递归实现95
6.2.2图的遍历算法的应用96
6.2.3有向图的强连通分量98
6.2.4Kruskal算法的实现99
6.2.5改进的拓扑排序算法100
6.3习题解析102
6.3.1课后习题讲解102
6.3.2学习自测及答案112
第7章查找技术115
7.1本章导学115
7.2重点难点释疑117
7.2.1折半查找判定树及其应用117
7.2.2时空权衡118
7.2.3平衡二叉树的调整方法119
7.2.4数学应用120
7.2.5散列查找的性能分析121
7.3习题解析123
7.3.1课后习题讲解123
7.3.2学习自测及答案129
第8章排序技术131
8.1本章导学131
8.2重点难点释疑133
8.2.1排序算法的稳定性133
8.2.2如何将排序算法移植到单链表上134
8.2.3二叉排序树与堆的区别135
8.2.4递归算法的时间性能分析135
8.3习题解析138
8.3.1课后习题讲解138
8.3.2学习自测及答案146
第9章索引技术151
9.1本章导学151
9.2习题解析153
9.2.1课后习题讲解153
9.2.2学习自测及答案156
第二篇实验指导
第10章基础实验161
10.1实验的一般步骤161
10.1.1概述161
10.1.2验证实验的一般步骤162
10.1.3设计实验和综合实验的一般步骤163
10.2设计实验164
10.2.1在数组中求最小值164
10.2.2统计候选人得票164
10.3综合实验165
10.3.1顺序查找最好、最坏和平均的时间性能165
10.3.2比较解决相同问题的不同算法的时间性能166
第11章线性表实验169
11.1验证实验169
11.1.1顺序表操作验证169
11.1.2单链表操作验证174
11.2设计实验180
11.2.1数组的循环移位180
11.2.2集合的交、并和差运算的实现181
11.3综合实验182
11.3.1约瑟夫环问题182
11.3.2一元多项式相加184
第12章特殊线性表——栈、队列和串实验187
12.1验证实验187
12.1.1栈操作验证187
12.1.2队列操作验证189
12.1.3串操作验证190
12.2设计实验191
12.2.1汉诺塔问题191
12.2.2火车车厢重排问题192
12.2.3统计文本中单词的个数193
12.3综合实验195
12.3.1表达式求值195
12.3.2迷宫问题196
12.3.3双端队列197
第13章广义线性表——多维数组和广义表实验199
13.1验证实验199
13.1.1对称矩阵的压缩存储199
13.1.2广义表操作验证200
13.2设计实验202
13.2.1稀疏矩阵的转置202
13.2.2广义表的遍历203
13.3综合实验203
13.3.1魔方阵203
13.3.2抽签游戏204
第14章树和二叉树实验207
14.1验证实验207
14.1.1树操作验证207
14.1.2二叉树操作验证208
14.2设计实验211
14.2.1求二叉树中叶子结点的个数211
14.2.2判断两棵二叉树是否相似211
14.3综合实验212
14.3.1信号放大器212
14.3.2哈夫曼编码214
第15章图实验215
15.1验证实验215
15.1.1邻接矩阵操作验证215
15.1.2邻接表操作验证217
15.2设计实验220
15.2.1求无向连通图的生成树220
15.2.2有向图的路径问题220
15.3综合实验221
15.3.1TSP问题221
15.3.2医院选址问题222
第16章查找技术实验225
16.1验证实验225
16.1.1顺序查找验证225
16.1.2折半查找验证226
16.1.3二叉排序树的建立227
16.1.4散列表的建立229
16.2设计实验230
16.2.1顺序查找与折半查找的性能比较230
16.2.2闭散列表和开散列表查找性能的比较231
16.3综合实验233
16.3.1直方图问题233
16.3.2简单个人电话号码查询系统233
第17章排序技术实验235
17.1验证实验235
17.1.1直接插入排序算法验证235
17.1.2起泡排序算法验证236
17.1.3简单选择排序算法验证237
17.2设计实验238
17.2.1直接插入排序基于单链表的实现238
17.2.2双向起泡排序240
17.3综合实验241
17.3.1各种排序算法时间性能的比较241
17.3.2机器调度问题241
附录245
附录A实验报告的一般格式245
附录B课程设计报告的一般格式246
参考文献247