本书是由编著者积累多年讲授“数据结构”课程及指导学生实验的教学实践经验编写而成的。编著者力图通过指导学生的实验实践和大量典型例题的解析,帮助学生深入学习、掌握并灵活运用数据结构知识。

本书作为高等学校计算机基础教育规划教材《数据结构》的配套教材,可以配合主教材使用,起到衔接课堂教学与实验教学、课下辅导的作用,可作为高等院校学生学习“数据结构”课程的参考书,对于从事计算机应用及开发的技术人员以及相关专业的自学者,也具有一定的参考价值。

在计算机教育中，“数据结构”的核心地位与重要作用是普遍公认的，而学习“数据结构”的困难也为广大师生所共识。

根据编著者多年的教学经验，学习数据结构的主要困难在于解题。解题中经常会出现错误的原因在于: 一是教材中没有重点解释；二是教师授课时无法做到面面俱到。因此，要学好数据结构，仅仅通过课堂教学或自学来掌握理论知识是远远不够的，还必须加强实践。除了完成数据结构的习题以外，还需要上机完成数据结构实验的若干任务。为此，我们编写了这本《数据结构习题解答与实验指导》。

本书是高等院校计算机基础教育规划教材《数据结构》的配套实验用书。全书共分为3篇: 第一篇为学习指导与习题解答，主要帮助读者理解数据结构的各种基本知识点和要点，并且提供了原教材的习题参考解答；第二篇为数据结构实验，本篇要求读者在实验前做好充分准备，然后利用课内学时和课外时间进行上机实践，实验后认真书写实验报告；第三篇为数据结构课程设计，此部分含大型作业题，主要帮助读者在完成数据结构的实验之外，再进一步去完成数据结构课程设计的若干实践任务，以帮助读者上机调试、运行各种典型的算法和自己编制的算法，从实践中得到锻炼和提高，从而学会运用理论知识去解决软件开发中的实际问题，达到学以致用的目的。

本书使用C语言来描述算法和数据结构，各实验中的程序都在Cfree或Visual C++ 6.0中调试通过，以方便读者在计算机上进行实践，有助于理解算法的实质和基本思想。

本书内容既配合原教材，又有相对的独立性，内容安排由浅入深，可以循序渐进地培养学生的实践技能。本书既可以作为高校计算机及相关专业本科生的配套教材，也可以作为专科和成人教育的辅助教材。另外，本书还可供从事计算机应用等工作的工程技术人员参考，读者只需掌握C语言编程的基本技术就可以学习本书。

由于编著者水平有限，因此书中难免有不足之处，殷切希望广大读者批评、指正。

编著者

2018年4月数据结构习题解答与实验指导目录第一篇学习指导与习题解答

第1章概论3

1.1学习指导3

1.1.1基本知识点3

1.1.2要点分析4

1.2习题参考解答5

第2章线性表8

2.1学习指导8

2.1.1基本知识点8

2.1.2要点分析9

2.2习题参考解答10

第3章栈和队列16

3.1学习指导16

3.1.1基本知识点16

3.1.2要点分析17

3.2习题参考解答18

第4章串26

4.1学习指导26

4.1.1基本知识点26

4.1.2要点分析27

4.2习题参考解答27

第5章数组和广义表32

5.1学习指导32

5.1.1基本知识点32

5.1.2要点分析33

5.2习题参考解答33

第6章树和二叉树38

6.1学习指导38

6.1.1基本知识点38

6.1.2要点分析41

6.2习题参考解答43

第7章图49

7.1学习指导49

7.1.1基本知识点49

7.1.2要点分析52

7.2习题参考解答52

第8章查找65

8.1学习指导65

8.1.1基本知识点65

8.1.2要点分析66

8.2习题参考解答67

第9章排序73

9.1学习指导73

9.1.1基本知识点73

9.1.2要点分析73

9.2习题参考解答74

第二篇数据结构实验

第10章数据结构实验概述85

10.1实验教学的目的85

10.2实验教学的主要内容85

10.3实验步骤86

10.4实验报告示例88

第11章数据结构实验安排91

11.1线性表91

11.1.1顺序表操作(验证实验)91

11.1.2单链表操作(验证实验)94

11.1.3约瑟夫环问题(设计实验)97

11.1.4一元多项式加(减)法计算器(设计实验)98

11.2栈和队列98

11.2.1顺序栈操作(验证实验)98

11.2.2链栈操作(验证实验)101

11.2.3顺序队列操作(验证实验)105

11.2.4链队列操作(验证实验)111

11.2.5括号匹配的检验(设计实验)114

11.2.6栈逆置队列(设计实验)115

11.3树和二叉树116

11.3.1二叉树操作(验证实验)116

11.3.2哈夫曼编码问题(设计实验)122

11.4图123

11.4.1无向图的邻接矩阵操作(验证实验)123

11.4.2无向图的邻接表操作(验证实验)124

11.4.3单源点最短路径问题(设计实验)128

11.4.4多源点最短路径问题(设计实验)128

11.5查找129

11.5.1查找算法(验证实验)129

11.5.2哈希表设计(设计实验)139

11.6排序140

11.6.1直接插入排序(设计实验)140

11.6.2希尔排序(设计实验)142

11.6.3冒泡排序(设计实验)143

11.6.4直接选择排序(设计实验)144

11.6.5快速排序(设计实验)144

11.6.6归并排序(设计实验)145

第三篇数据结构课程设计

第12章数据结构课程设计概述149

12.1课程设计的目的149

12.2课程设计的时间安排150

12.3课程设计的指导教师150

12.4课程设计的选题内容和要求150

12.5课程设计的实施步骤151

12.6课程设计总结报告的撰写规范151

12.7课程设计的上交材料152

12.8课程设计的成绩评定152

第13章数据结构课程设计安排153

13.1线性表(课程设计1)153

13.1.1顺序表的就地逆置153

13.1.2单链表的就地逆置157

13.2栈(课程设计2)160

13.2.1用栈逆置一个单链表163

13.2.2共享栈的设计166

13.3队列(课程设计3)168

13.4树和二叉树(课程设计4)175

13.4.1二叉树的生成175

13.4.2最优二叉树(哈夫曼树)的建立178

13.5图(课程设计5)181

13.5.1图的存储结构181

13.5.2图的遍历184

13.5.3图的应用186

13.6查找(课程设计6)188

13.7排序(课程设计7)194

13.8大型作业题(课程设计8)207

13.9数据结构课程设计补充题目210

第14章数据结构课程设计案例——图书管理信息系统的设计与实现224

14.1设计要求224

14.2设计分析225

14.2.1数据文件类型设计225

14.2.2系统功能算法描述227

14.3设计的实现231

14.4测试运行实例241

14.4.1主控菜单的设计241

14.4.2测试运行实例242

参考文献248

本书作为规划教材《数据结构》的配套教材，可以配合主教材使用，起到衔接课堂教学与实验教学、课下辅导的作用，可作为高等院校学生学习数据结构课程的参考书。全书由三部分组成。第一部分为学习提要和习题解答；第二部分为实验指导；第三部分为数据结构课程设计。

本书作为规划教材《数据结构》的配套教材，可以配合主教材使用，起到衔接课堂教学与实验教学、课下辅导的作用，可作为高等院校学生学习数据结构课程的参考书。全书由三部分组成。第一部分为学习提要和习题解答；第二部分为实验指导；第三部分为数据结构课程设计。