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

第一篇学习辅导

第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