数据结构实验指导书(09级)

数据结构作业和实验指导书数据结构课程组广东工业大学计算机学院2011年3月-1-目录第1章概述1.1课程、教材和实验1.2作业和实验安排第2章算法设计实验和上机2.1数据结构习题概述2.2算法设计的上机作业要求2.3算法设计上机作业第3章抽象数据类型的实现3.1实验概要3.2实验目的3.3预习与参考3.4实验要求和设计指标3.5实验仪器设备和材料3.6调试及结果测试3.7考核形式3.8实验报告要求3.9思考题3.10示例第4章课程设计4.1课程设计概述4.2课程设计时间和内容4.3课程设计步骤4.4课程设计报告范例4.5课程设计考核形式和评分标准-1-第1章概述1.1课程、教材和实验数据结构是计算机科学的算法理论基础和软件设计的技术基础，主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现。数据结构不仅是计算机专业的核心课程，而且已成为其他理工专业的热门选修课。课程的教学要求之一是训练学生进行复杂程序设计的技能和培养良好程序设计的习惯,其重要程度决不亚于知识传授。因此，在数据结构的整个教学过程中,完成习题作业和上机实习是两个至关重要的环节。习题的作用在于帮助学生深入理解教材内容,巩固基本概念,达到培养良好程序设计能力和习惯的目的。从认知的程度划分，数据结构的习题通常可分为三类：基础知识题、算法设计题和综合实习题。基础知识题主要是检查对概念知识的识记和理解，一般可作为学生自测题。算法设计题的目的是练习对原理方法的简单应用，多数是要求在某种数据存储结构上实现某一操作，是数据结构的基础训练，构成了课外作业的主体。综合实习题则训练对知识的综合应用和软件开发能力，主要是针对具体应用问题，选择、设计、和实现抽象数据类型（ADT）的可重用模块，并以此为基础开发满足问题要求的小型应用软件，应将其看作软件工程的综合性基础训练的重要一环，给予足够的重视。本实验指导书为采用下列教材的数据结构课程而编写：[1]严蔚敏，吴伟民.《数据结构》（C语言版，含光盘）.清华大学出版社，2002.9[2]严蔚敏，吴伟民.《数据结构题集》（C语言版）.清华大学出版社，1999.2其中，《数据结构题集》实际上是一本较全面的学习和实验指导书。本实验指导书根据教学计划给予一些补充，与上述两本教材配合使用。《数据结构题集》的第一篇为习题篇，含有三百余道习题，组织成十二章，分别对应教科书中各章内容，并在每章之前给出该章的内容提要和学习要求。这些习题是作者在多年教学过程中所积累资料的基础上，参考大量国外教材之后精心设计而成的。书中对特别推荐的题目作了标记，并对每道习题的难易程度按五级划分法给出了难度系数。第二篇为实习篇，分别以抽象数据类型、线性表、栈和队列、串、数组和广义表、树和图以及查找和排序为核心，设置了七组上机实习题，每组有3至9个题目供学生自由选择。期望这些实习题能对习题起到良好的扩充作用，使学生受到涉及“从问题到程序”的应用软件设计的完整过程的综合训练，培养合作能力，成为将来进行软件开发和研究工作的“实践演习”。数据结构是实践性很强的课程，光是“听”和“读”是绝对不够的。在努力提高课堂教学的同时，必须大力加强对作业实践环节的要求和管理。国内外先进院校一般都要求修读数据结构的学生每周应不少于4个作业机时，而且有一套严格的作业和实习规范和成绩评定标准，形成行之有效的教学质量保证体系。《数据结构题集》强调规范化在算法设计基本训练中的重要地位。在习题篇中给出了算法书写规范，在实习篇中给出了实习步骤和实习报告的规范。教学经验表明，严格实施这些貌似繁琐的规范，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将能起到显著的促进作用。数据结构及其算法的教学难点在于它们的-2-抽象性和动态性。虽然在书本教材和课堂授课（板书或投影胶片）中采用图示可以在一定程度上化抽象为直观，但很难有效展现数据结构的瞬间动态特性和算法的作用过程。在随教科书配发的光盘中，“数据结构的算法动态模拟辅助教学软件DSDEMO”是为学习并掌握数据结构中各类典型算法而开发的一个辅助教学软件，可对教科书中八十余个典型算法进行动态交互式跟踪演示，在算法执行过程中实现数据结构和算法的动态同步可视化，使学生获得仅从教材文字说明中无法获得的直观知识。软件既可用于课堂讲解演示，又能供个人课外反复观察、体会和理解，对提高教学质量和效率有显著效果。在习题篇的每一章列举了与该章相关的算法清单，并在《数据结构题集》附录中提供该软件完整的使用说明。1.2作业和实验安排根据教学计划，数据结构课程的实验和上机由三部分构成：1．算法设计实验和上机（30机时）在“数据结构算法设计作业系统”上机完成40道必做题，学有余力的同学还可以选做另外40道选做题。2．抽象数据类型的实现（6学时设计性实验）实现一个抽象数据类型，并对所采用的存储结构和相关操作的实现进行讨论。3．课程设计（一周综合性实验）完成《数据结构题集》中的一至两个实习题。-3-第2章算法设计实验和上机2.1数据结构习题概述《数据结构题集》把数据结构的习题分为“基础知识题”和“算法设计题”两类。“基础知识题”主要供学生进行自测和复习之用，目的是帮助学生深化理解教科书的内容，澄清基本概念、理解和掌握数据结构中分析问题的基本方法和算法要点，为完成算法设计题做准备。“算法设计题”则侧重于基本程序设计技能的训练，相对于实习题而言，这类编程习题属于偏重于编写功能单一的“小”程序的基础训练，然而，它是进行复杂程序设计的基础，是本课程习题作业的主体和重点。各章的题量根据教学内容的多少和重要程度而定，几乎对教科书的每一小节都安排了对应的习题。但对每个学生来说，不必去解全部习题，而只须根据自己的情况从中选择若干求解即可。为了表明题目的难易程度，便于学生选择，在每个题的题号之后注了一个难度系数，难度级别从①至⑤逐渐加深，其区别大致如下：难度系数为①和②的习题以基础知识题为主；难度系数为③的习题以程序设计基础训练为主要目的，如强化对“指针”的基本操作的训练等；习题中也收纳了不少难题，其难度系数设为④和⑤，解答这些题可以激起学习潜力较大的学生的兴趣，对广泛开拓思路很有益。但习题的难度系数也只是一个相对量，学生的水平将随学习的进展而不断提高，因此没有必要去比较不同章节的习题的难度系数，此外，该难度系数值的假设是以学生没有参照习题的解答或提示为前提的。“循序渐进”是最基本的学习原则。学习者不应该片面追求难题。对于解难度系数为i的习题不太费力的学生，应试试难度系数为i+1的习题，但不要把太多的时间浪费在难度系数为i+2的习题上。“少而精”和“举一反三”是实践证明行之有效的。解答习题应注重于“精”，而不要求“多”。为此，在一些值得向学生推荐的“好题”题号前加注了标记◆。把握住这些“关键点”，就把握住了数据结构习题、乃至数据结构课程的总脉络。2.2算法设计的上机作业要求1．使用AnyviewC语言和算法书写规范写出书面作业的算法（函数），作为上机前的准备。需要强调的是“算法的可读性”。算法是为了让人来读的，而不是供机器读的。初学者总是容易忽视这一点。算法的真正意图主要在于提供一种在程序设计者之间交流解决问题方法的手段。因此，可读性具有头等的重要性。不可读的算法是没有用的，由它得到的程序极容易产生很多隐藏很深的错误，且难以调试正确。一般地说，宁要一个可读性好、逻辑清晰简单、但篇幅较长的算法，也不要篇幅较小但晦涩难懂的算法。算法的正确性力求在设计算法的过程中得到保证，然而一开始做不到这一点也没多大关系，可以逐步做到。算法设计的正确方法是：首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略逐一地解决子问题，最后严格按照和使用本章后面提供的算法书写规范和类C语言完成算法的最后版本。按照规范书写算法是一个值得高度重视的问题。在基础训练中就贯彻这一规范，不但能够有助于写出“好程序”，避免形成一系列难以纠正且遗害无穷的程序设计坏习惯，而且能够培养软件工作者应有的严谨的科学工作作风。2．对函数进行静态检查修改，形成准备上机的程序文本。多数初学者在编好程序后处于以下两种状态之一：一种是对自己的“精心作品”的正确性确信不疑；另一种是认为上机前的任务已经完成，查纠错误是上机的工作。这两种态度是极为有害-4-的。事实上，非训练有素的程序设计者编写的程序长度超过50行时，极少不含有除语法错误以外的错误。上机动态调试决不能代替静态检查，否则调试效率将是极低的。静态检查主要有两种方法，一是用一组测试数据手工执行程序（通常应先分模块检查）；二是通过阅读或给别人讲解自己的程序而深入全面地分析理解程序逻辑，在这个过程中再加入一些注解和断言。如果程序中逻辑概念清楚，后者将比前者有效。3．在“AnyviewC数据结构算法设计作业系统”编辑提交程序，并在系统的自动测试和提示下，调试程序，直到能通过系统的测试。“AnyviewC数据结构算法设计作业系统”提供了程序可视化运行和调试的环境，为进行数据结构教学的师生提供了算法设计作业程序的可视化自动测试环境。可在该集成环境编辑C源程序，并对其进行可视化运行、分析和调试。通过设置断点、单步或变换速度的连续运行，可在多个窗口上动态观察程序执行时的数据变量的物理和逻辑2D或3D视图，使得程序运行期间本来不可见的程序对数据的处理过程和数据之间的动态抽象关系全部可视化。在提交算法设计作业程序时，系统自动进行可视化测试，评判作业程序的正确性。通过对比“标准结果视图”和“作业结果视图”，作业者可对自己的程序进行直观的分析和排错。关于该作业系统的使用，请参阅系统的帮助文档。在调试过程中可以不断借助系统的可视DEBUG的各种功能，提高调试效率。调试中遇到的各种异常现象往往是预料不到的，这时不应“苦思冥想”，而应动手确定疑点，通过修改程序来证实它或绕过它。4．在调试程序的过程中，做好调试笔记，记录心得体会。调试正确后，认真整理源程序及其注释，记录带有完整注释的且格式良好的源程序清单和结果。一道算法设计作业文档包括：（1）上机前编写并经过静态检查的程序文本；（2）调试笔记；（3）最后程序文本，及通过时间。2.3算法设计上机作业1．作业内容和机时40道必做题，40道选做题。每年作适当调整更换。6个课内实验机时，教师现场指导答疑。24个课外训练机时，实验教师指导答疑。学生平时可以在互联网上登录系统，做选做题。2．算法设计题目文档系统为每道算法设计题提供一个题目文档，包括以下内容：（1）题目；（2）算法的函数原型；（3）可用的类型定义和函数原型。做题前，必须仔细阅读题目文档，正确理解题目和做题要求。-5-第3章抽象数据类型的实现3.1实验概要实验项目名称:抽象数据类型的实现实验项目性质:设计性实验所属课程名称:数据结构实验计划学时:63.2实验目的对某个具体的抽象数据类型，运用课程所学的知识和方法，设计合理的数据结构，并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验，检验所学知识和能力，发现学习中存在的问题。进而达到熟练地运用本课程中的基础知识及技术的目的。3.3预习与参考1．确定要实现的抽象数据类型，并对基本操作做适当的选取和增加；2．选择存储结构，并写出相应的类型定义；3．设计各基本操作的实现算法，并表达为函数形式；4．设计测试方案，编写主函数；5．将上述4步的结果写成预习报告。3.4实验要求和设计指标以教材中线性表，串，稀疏矩阵，广义表，二叉树，树，图以及查找表等抽象数据类型为对象，利用C语言的数据类型表示和实现其中某个抽象数据类型。可选的抽象数据类型如下表所列：编号抽象数据类型基本难度教材页码1复数1.0《数据结构题集》P.762有理数1.0《数据结构题集》P.763海龟作图1.2《数据结构题集》P.774一元稀疏多项式1.2《数据结构》P.405稀疏矩阵1.3《数据结构》P.966广义表1.4《数据结构》P.1077树1.5《数据结构》P.1188二叉树1.5《数据结构》P.1219图1.4《数据结构》P.15610静态查找表1.2《数据结构》P.2161