数据结构-实验.doc

PAGE 1 PAGE 3 计算机与信息工程学院 《 数 据 结 构 》 实验指导书 第一部分 综 述 一 简 介 数据结构是计算机相关专业的一门重要基础课，上机实验可以达到对学生所学理论基础知识进行综合训练的目的，与课堂教学、学生自学以及习题练习等相辅相成，必不可少，是一个十分重要的教学环节。 通常，实验题目中的问题比平时的习题练习要复杂得多，也更接近实际。实验着眼于原理与应用相结合，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。平时的习题练习较偏重于如何编写功能单一的“小”算法，而实验不仅要把算法改为是标准语言下的程序来实现而且要训练软件设计的综合素质，包括问题分析、总体结构设计、用户界面设计、程序设计和程序调试的基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。此外，还有很重要的一点是：机器是比任何教师都严厉的检查者，可以看到书上的所有算法绝大多数都不能在机器上运行，必须经过标准语言的深化与改造，在不存在任何逻辑和语法错误的情况下才能编译执行。 为了达到上述目的，本书根据数据结构教学内容与之配套安排了六个必做实验题目和多个选做题目，训练重点在于基本的数据结构，而不强调面面俱到。各实验与教科书中各章的对应知识点具有对应关系，在学完相应的理论知识以后即可以做对应的实验，当然有些实验可能常常涉及几部分教学内容。 每个实验题均采取了统一的格式，由问题描述、目的要求、程序设计思路和实现、测试与调试、实现提示和存在问题讨论等五个部分组成。问题描述旨在让学生把所做实验的理论依据进行简单的阐述；目的要求则是让学生对实验目的用意有明确的认识和对学生的实验提供一定的指导性意见和建议；程序设计思路要求学生学会对问题进一步求精，划出问题的边界，指出具体的参量或前提条件，并规定该题的最低限度要求，在清晰的思路下完成程序的代码实现。测试调试部分旨在让学生充分训练和掌握在及其上调试程序的方法和技巧，达到理论与实践相结合的目的，充分提高学生的动手能力，是开展实验教学的重要目的之一，同时为检查学生上机作业、检查学生对课堂教学中所学理论知识的掌握程度提供可靠的依据。存在问题讨论部分让学生对自己所做实验进行最后的总结分析探讨，充分自我审视，找出仍然存在的问题，并给出自己的改进思路，对实现中的难点及其解法思路等问题作简要提示。选做部分向那些尚有余力的读者提出了更好的开拓型思维机会，旨在培养学生独立分析问题、解决问题的能力。通过讨论、分析和研究力求避免就事论事，形成良好的思想方法，尽可能寻求具有普遍意义的解法，使得程序结构合理，容易修改扩充。 本书的一个特点是为实验制定了严格的规范。一种普遍存在的错误观念是，调试程序全凭运气。学生花两个小时的上机时间只找出一个错误，甚至一无所获的情况是常见的。其原因在于，很多人只认识到找错误，而没有认识到努力预先避免错误的重要性，也不知道应该如何努力。实际上，结构不好、思路和概念不清的程序可能是根本无法调试正确的。严格按照实验步骤规范进行实验不但能有效地避免上述种种问题，更重要的是有利于培养软件工作者不可缺少的科学工作方法和作风。 为每个实验提供都了完整的实验报告格式要求，在起到实验报告规格范例作用的同时，还提供了很多有益的东西，比如，基于数据类型的系统划分方法；递归算法设计方法和技巧；对于有天然递归属性的问题如何构造非递归算法；以及所提倡的程序设计风格等。 二 实验步骤 随着计算机性能的提高，它所面临的软件开发的复杂度也日趋增加。然而，编制一个10,000行的程序的难度绝不仅仅是一个5，000行的程序两倍，因此软件开发需要系统的方法。一种常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题的复杂度远不如(从实际问题中提出来的)一个“真正的”软件，但为了培养一个软件工作者所应具备的科学工作的方法和作风，我们制订了如下所述完成实习的五个步骤: (一)问题分析和任务定义 通常，实验题目的陈述比较简洁，或者说是有模棱两可的含义。因此，在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么，限制条件是什么。注意：本步骤强调的是做什么，而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么？是否接受非法的输入？对非法输入的回答方式是什么等。这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式的输入数据。 (二)数据类型和系统设计 在设计这一步骤中需分逻辑设计和详细设计两步实现。逻