抽象数据类型的实现.doc

《抽象数据类型的实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章抽象数据类型的实现3.1实验概要实验项目名称:抽象数据类型的实现实验项目性质:设计性实验所属课程名称:数据结构实验计划学时:63.2实验目的对某个具体的抽象数据类型，运用课程所学的知识和方法，设计合理的数据结构，并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验，检验所学知识和能力，发现学习中存在的问题。进而达到熟练地运用本课程中的基础知识及技术的目的。3.3预习与参考1．确定要实现的抽象数据类型，并对基本操作做适当的选取和增加；2．选择存储结构，并写出相应的类型定义；3．设计各基本操作的实现算法，并表达为函数

2、形式；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《数

3、据结构》P.1188二叉树1.5《数据结构》P.1219图1.4《数据结构》P.15610静态查找表1.2《数据结构》P.21611动态查找表1.3《数据结构》P.226注：如果基本操作数量较多，可选择实现其中一个基本操作子集。实验要求如下：1．参加实验的学生应首先了解设计的任务，然后根据自己的基础和能力从中选择一题。一般来说，选择题目应以在规定的时间内能完成，并能得到应有的锻炼为原则。若学生对教材以外的相关题目较感兴趣，希望选作实验的题目时，应征得指导教师的认可，并写出明确的抽象数据类型定义及说明。2.实验前要作好充分准备，包

4、括：理解实验要求，掌握辅助工具的使用，了解该抽象数据类型的定义及意义，以及其基本操作的算法并设计合理的存储结构。3.实验时严肃认真，要严格按照要求独立进行设计，不能随意更改。注意观察并记录各种错误现象，纠正错误，使程序满足预定的要求，实验记录应作为实验报告的一部分。4.实验后要及时总结，写出实验报告，并附所打印的问题解答、程序清单，所输入的数据及相应的运行结果。3.5实验仪器设备和材料软件实验室。编程环境：AnyviewC可视化编程环境、TC++、C++Builder或者VC++。3.6调试及结果测试调试内容应包括：调试过程中遇

5、到的问题是如何解决的以及对实验的讨论与分析；基本操作的时间复杂度和空间复杂度的分析和改进设想。列出对每一个基本操作的测试结果，包括输入和输出，测试数据应完整和严格。3.7考核形式考核形式以实验过程和实验报告相结合的方式进行。在实验完成后，应当场运行和答辩，由指导教师验收，只有在验收合格后才能算实验部分的结束。实验报告作为整个设计性实验评分的书面依据。设计性实验的成绩评定以选定题目的难易度、完成情况和实验报告为依据综合评分。从总体来说，所实现的抽象数据类型应该全部符合要求，类型定义，各基本操作的算法以及存储结构清晰；各模快测试运行

6、正确；程序的结构合理；设计报告符合规范。3.8实验报告要求实验结束后要写出实验报告，以作为整个设计性实验评分的书面依据和存档材料。实验报告是反映学生实验效果的最主要的依据，也是学生正确地表达问题、综合问题和发现问题的能力的基本培养手段，因而是非常重要的内容。本设计性实验的报告要包括以下几项内容：（1）设计任务、要求及所用软件环境或工具；（2）抽象数据类型定义以及各基本操作的简要描述；（3）所选择的存储结构描述及在此存储结构上各基本操作的实现；（4）程序清单（计算机打印），输入的数据及各基本操作的测试结果；（5）实验总结和体会。实

7、验报告以规定格式的电子文档书写、打印并装订，排版及图表要清楚、工整。3.9思考题对设计性实验进行总结和讨论，包括本实验的优、缺点，数据存储结构的特点，与其它存储结构之间的比较等。通过总结，可以对抽象数据类型有更全面、深入的认识，这是设计性实验不可缺少的重要内容。这部分内容应作为实验报告中的一个组成部分。3.10示例1.题目采用字符类型为元素类型和无头结点单链表为存储结构，实现抽象数据类型List。ADTList{数据对象：D＝{ai

8、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{

9、ai

10、-1,ai∈D,i=2,...,n}基本操作：SetEmpty(&L)操作结果：构造一个空的线性表L。Destroy(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。Length(L)初始条件：线性表L已存在。操作结果：返回L中元素个数。Get(L,i,