【精品】《数据结构》实验指导书(有代码)

《【精品】《数据结构》实验指导书(有代码)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构实验指导书东华大学计算机科学与技术学院2009年9月nop1一、概述1二、实验步骤2三、实验报告规范5四、算法书写规范6五、参考书目9实验O顺序表与链表10实验O实验报告示例12实验一线性表25实验报告示例：集合的并、交和差运算28实验二栈和队列42实验报告示例：迷宫问题45实验三树和二义树57实验四图60实验五查找63实验六排序65实验七综合设计性实验——航班信息的査询与检索67—、概述上机实验是对学生的一种全面综合训练，是与课堂听讲、口学和练习和辅和成的必不可少的一个教学环节。通常，实验题屮的

2、问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使读者学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。平时的练习较偏重于如何编写功能单一的“小”算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。此外，述有很重要的一点是：机器是比任何教师都严厉的检查者。为了达到上述目的，木指导书安排了

3、七个主实验单元（其中除实验0作为预备练习，训练数组和链表的编程方法和编程技巧），其它各单元的训练重点在于基本的数据结构，而不强调面面俱到。各实验单元与教科书的各章只具有粗略的对应关系，一个实验题常常涉及几部分教学内容。在每个实验单元小安排有难度不等的实验题，经验表明，如果某题的难度略高于自C过去所对付过的最难题FI的难度，则选择此题能够带来最人的收益。切忌过分追求难题或者容易的题目。一些实验题釆取了统一的格式（其余的实验题由于比较简单，没有这么详细列出来，读者可举一反三），由问题描述、基本要求、测试数据、

4、实现提示和选做内容五个部分组成。问题描述旨在为读者建立间题提出的背景环境，指明问题“是什么”，基本要求则对问题进一步求精划出问题的边界，指出具体的参量或前提条件，并规定该题的最低限度耍求，测试数据部分旨在为检查学生上机作业提供方便，在完成实验题时应口己设计完整和严格的侧试方案，当数据输入量较大时，提倡以文件形式向程序提供输入数据。在实现提示部分，对实现中的难点及其解法思路等问题作了简要提示•选做部分向那些尚有余力的读者提出了更严峻的挑战，同时也能开拓其他读者的思路，在完成基本要求时力求避免就事论事的不良思

5、想方法，尽可能寻求具有普遍意义的解法，使得程序结构合理，容易修改扩充。不难发现，这里与传统的做法不同，题目设计得非常详细。会不会限制读者的想象力、影响创造力的培养呢？冋答是：软件发展的一条历史经验就是要限制程序设计者在某些方面的创造性，从而使其创造能力集中地用到特别需要创造性的环节Z上。实验题目本身就给出了问题说明和问题分解求精的范例，使读者在无形中学会模仿，它起到把读者的思路引上止轨的作用，避免坏结构程序和坏习惯，同时也传授了系统划分方法和程序设计的一些具体技术，保证实现预定的训练意图，使某些难点和重点

6、不会被绕过去，而且也便于教学检查。题口的设计策略是：一方面使其难度和工作量都较大，另一方面给读者提供的辅助和可以模仿的成份也较多。当然述应指出的是，捉示的实现方法未必是最好的，读者不应拘泥于此，而应努力开发更好的方法和结构。本实验指导书的一个特点是为实验制定了严格的规范（见后面各章节）。一种普遍存在的错误观念是，调试程序全凭运气。学生花两个小吋的上机吋间只找出一个错误，甚至一无所获的情况是常见的。其原因在于，很多人只认识到找错误，而没冇认识到努力预先避免错误的重要性，也不知道应该如何努力。实际上,结构不好

7、、思路和概念不清晰的程序可能是根本无法调试止确的。严格按照实验步骤规范进行实验不但能冇效地避免上述种种问题，更重要的是冇利于培养软件工作者不可缺少的科学工作方法和作风。前三个实验单元提供了一个完整的实验报告示例，在起到实验报告规格范例作用的同时，述隐含地提供了很多冇益的东西，比如，基丁•数据类型的系统划分方法；递归算法设计方法和技巧；对于有天然递归属性的问题如何构造非递归算法；以及所提倡的程序设计风格等。但从另一方面看，计算机学科在不断发展，可以使用的语言工具越来越丰富，在木书屮的实验示例还只是应用面向过

8、程的语言进行设计和编写程序，同样的实验题，读者也可以用面向对彖的语言来实现。希望书屮的实验报告示例能起到一个抛砖引玉的作用，以迎来读者更多更优良的设计范例。二、实验步骤随着计算机性能的捉高，它所而临的软件开发的复杂度也H趋增加。然而，编制一个10,000行的程序的难度绝不仅仅是一个5,000行的程序两倍，因此软件开发需要系统的方法。一种常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程屮