《数据结构实验与课程设计指导书 .doc》由会员分享，可在线阅读，更多相关《数据结构实验与课程设计指导书 .doc（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构实验指导书数据结构课程组广东工业大学计算机学院2014年4月第1章 概述1.1 课程、教材和实验数据结构是计算机科学的算法理论基础和软件设计的技术基础，主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现。数据结构不仅是计算机专业的核心课程，而且已成为其他理工专业的热门选修课。课程的教学要求之一是训练学生进行复杂程序设计的技能和培养良好程序设计的习惯, 其重要程度决不亚于知识传授。因此，在数据结构的整个教学过程中, 完成习题作业和上机实习是两个至关重要的环节。习题的作用在于帮助学生深入理解教材内容, 巩固基本概念, 达到培养良好程序设计能力和习惯的目的。从认知的程度划分，数据结构的
2、习题通常可分为三类：基础知识题、算法设计题和综合实习题。基础知识题主要是检查对概念知识的识记和理解，一般可作为学生自测题。算法设计题的目的是练习对原理方法的简单应用，多数是要求在某种数据存储结构上实现某一操作，是数据结构的基础训练，构成了课外作业的主体。综合实习题则训练对知识的综合应用和软件开发能力，主要是针对具体应用问题，选择、设计、和实现抽象数据类型（ADT）的可重用模块，并以此为基础开发满足问题要求的小型应用软件，应将其看作软件工程的综合性基础训练的重要一环，给予足够的重视。本实验指导书为采用下列教材的数据结构课程而编写：1 严蔚敏，吴伟民. 数据结构（C语言版，含光盘）. 清华大学出版
3、社，2002.92 严蔚敏，吴伟民. 数据结构题集（C语言版）. 清华大学出版社，1999.2其中，数据结构题集实际上是一本较全面的学习和实验指导书。本实验指导书根据教学计划给予一些补充，与上述两本教材配合使用。数据结构题集的第一篇为习题篇，含有三百余道习题，组织成十二章，分别对应教科书中各章内容，并在每章之前给出该章的内容提要和学习要求。这些习题是作者在多年教学过程中所积累资料的基础上，参考大量国外教材之后精心设计而成的。书中对特别推荐的题目作了标记，并对每道习题的难易程度按五级划分法给出了难度系数。第二篇为实习篇，分别以抽象数据类型、线性表、栈和队列、串、数组和广义表、树和图以及查找和排序
4、为核心，设置了七组上机实习题，每组有3至9个题目供学生自由选择。期望这些实习题能对习题起到良好的扩充作用，使学生受到涉及“从问题到程序”的应用软件设计的完整过程的综合训练，培养合作能力，成为将来进行软件开发和研究工作的“实践演习”。数据结构是实践性很强的课程，光是“听”和“读”是绝对不够的。在努力提高课堂教学的同时，必须大力加强对作业实践环节的要求和管理。国内外先进院校一般都要求修读数据结构的学生每周应不少于4个作业机时，而且有一套严格的作业和实习规范和成绩评定标准，形成行之有效的教学质量保证体系。数据结构题集强调规范化在算法设计基本训练中的重要地位。在习题篇中给出了算法书写规范，在实习篇中给
5、出了实习步骤和实习报告的规范。教学经验表明，严格实施这些貌似繁琐的规范，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将能起到显著的促进作用。数据结构及其算法的教学难点在于它们的抽象性和动态性。虽然在书本教材和课堂授课（板书或投影胶片）中采用图示可以在一定程度上化抽象为直观，但很难有效展现数据结构的瞬间动态特性和算法的作用过程。在随教科书配发的光盘中，“数据结构的算法动态模拟辅助教学软件DSDEMO”是为学习并掌握数据结构中各类典型算法而开发的一个辅助教学软件，可对教科书中八十余个典型算法进行动态交互式跟踪演示，在算法执行过程中实现数据结构和算法的动态同步可视化，使学生获得仅从教材
6、文字说明中无法获得的直观知识。软件既可用于课堂讲解演示，又能供个人课外反复观察、体会和理解，对提高教学质量和效率有显著效果。在习题篇的每一章列举了与该章相关的算法清单，并在数据结构题集附录中提供该软件完整的使用说明。1.2 实验安排根据教学计划，数据结构课程的实验和上机由三部分构成：1 算法设计实验和上机（30机时）在“数据结构算法设计作业系统”上机完成40道题，学有余力的同学还可以选做另外40道题。2 抽象数据类型的实现（6学时设计性实验）实现一个抽象数据类型，并对所采用的存储结构和相关操作的实现进行讨论。3 课程设计（一周综合性实验）完成数据结构题集中的一个实习题。第2章 算法设计实验和上
7、机2.1 数据结构习题概述数据结构题集把数据结构的习题分为“基础知识题”和“算法设计题”两类。“基础知识题”主要供学生进行自测和复习之用，目的是帮助学生深化理解教科书的内容，澄清基本概念、理解和掌握数据结构中分析问题的基本方法和算法要点，为完成算法设计题做准备。“算法设计题”则侧重于基本程序设计技能的训练，相对于实习题而言，这类编程习题属于偏重于编写功能单一的“小”程序的基础训练，然而，它是进行复杂程序设计的基础，是本课程习题作业的主体和重点。各章的题量根据教学内容的多少和重要程度而定，几乎对教科书的每一小节都安排了对应的习题。但对每个学生来说，不必去解全部习题，而只须根据自己的情况从中选择若
8、干求解即可。为了表明题目的难易程度，便于学生选择，在每个题的题号之后注了一个难度系数，难度级别从至逐渐加深，其区别大致如下：难度系数为和的习题以基础知识题为主；难度系数为的习题以程序设计基础训练为主要目的，如强化对“指针”的基本操作的训练等；习题中也收纳了不少难题，其难度系数设为和，解答这些题可以激起学习潜力较大的学生的兴趣，对广泛开拓思路很有益。但习题的难度系数也只是一个相对量，学生的水平将随学习的进展而不断提高，因此没有必要去比较不同章节的习题的难度系数，此外，该难度系数值的假设是以学生没有参照习题的解答或提示为前提的。“循序渐进”是最基本的学习原则。学习者不应该片面追求难题。对于解难度系
9、数为i的习题不太费力的学生，应试试难度系数为i+1的习题，但不要把太多的时间浪费在难度系数为i+2的习题上。“少而精”和“举一反三”是实践证明行之有效的。解答习题应注重于“精”，而不要求“多”。为此，在一些值得向学生推荐的“好题”题号前加注了标记。把握住这些“关键点”，就把握住了数据结构习题、乃至数据结构课程的总脉络。2.2 算法设计的上机作业要求1使用Anyview C语言和算法书写规范写出书面作业的算法（函数），作为上机前的准备。需要强调的是“算法的可读性”。算法是为了让人来读的，而不是供机器读的。初学者总是容易忽视这一点。算法的真正意图主要在于提供一种在程序设计者之间交流解决问题方法的手
10、段。因此，可读性具有头等的重要性。不可读的算法是没有用的，由它得到的程序极容易产生很多隐藏很深的错误，且难以调试正确。一般地说，宁要一个可读性好、逻辑清晰简单、但篇幅较长的算法，也不要篇幅较小但晦涩难懂的算法。算法的正确性力求在设计算法的过程中得到保证，然而一开始做不到这一点也没多大关系，可以逐步做到。 算法设计的正确方法是：首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略逐一地解决子问题，最后严格按照和使用本章后面提供的算法书写规范和类C语言完成算法的最后版本。按照规范书写算法是一个值得高度重视的问题。在基础训练中就贯彻这一规范，不但能够有助于写出“好
11、程序”，避免形成一系列难以纠正且遗害无穷的程序设计坏习惯，而且能够培养软件工作者应有的严谨的科学工作作风。2对函数进行静态检查修改，形成准备上机的程序文本。 多数初学者在编好程序后处于以下两种状态之一：一种是对自己的“精心作品”的正确性确信不疑；另一种是认为上机前的任务已经完成，查纠错误是上机的工作。这两种态度是极为有害的。事实上，非训练有素的程序设计者编写的程序长度超过50行时，极少不含有除语法错误以外的错误。上机动态调试决不能代替静态检查，否则调试效率将是极低的。 静态检查主要有两种方法，一是用一组测试数据手工执行程序（通常应先分模块检查）；二是通过阅读或给别人讲解自己的程序而深入全面地分
12、析理解程序逻辑，在这个过程中再加入一些注解和断言。如果程序中逻辑概念清楚，后者将比前者有效。3在“Anyview C数据结构算法设计作业系统”编辑提交程序，并在系统的自动测试和提示下，调试程序，直到能通过系统的测试。“Anyview C数据结构算法设计作业系统”提供了程序可视化运行和调试的环境，为进行数据结构教学的师生提供了算法设计作业程序的可视化自动测试环境。可在该集成环境编辑C源程序，并对其进行可视化运行、分析和调试。通过设置断点、单步或变换速度的连续运行，可在多个窗口上动态观察程序执行时的数据变量的物理和逻辑2D或3D视图，使得程序运行期间本来不可见的程序对数据的处理过程和数据之间的动态
13、抽象关系全部可视化。在提交算法设计作业程序时，系统自动进行可视化测试，评判作业程序的正确性。通过对比“标准结果视图”和“作业结果视图”，作业者可对自己的程序进行直观的分析和排错。关于该作业系统的使用，请参阅系统的帮助文档。 在调试过程中可以不断借助系统的可视DEBUG的各种功能，提高调试效率。调试中遇到的各种异常现象往往是预料不到的，这时不应“苦思冥想”，而应动手确定疑点，通过修改程序来证实它或绕过它。4在调试程序的过程中，做好调试笔记，记录心得体会。调试正确后，认真整理源程序及其注释，记录带有完整注释的且格式良好的源程序清单和结果。一道算法设计作业文档包括：（1）上机前编写并经过静态检查的程
14、序文本；（2）调试笔记；（3）最后程序文本，及通过时间。2.3 算法设计上机作业1作业内容和机时40道必做题，40道选做题。每年作适当调整更换。6个课内实验机时，教师现场指导答疑。24个课外训练机时，实验教师指导答疑。学生平时可以在互联网上登录系统，做选做题。2算法设计题目文档系统为每道算法设计题提供一个题目文档，包括以下内容：（1）题目；（2）算法的函数原型；（3）可用的类型定义和函数原型。做题前，必须仔细阅读题目文档，正确理解题目和做题要求。第3章 抽象数据类型的实现3.1 实验概要实验项目名称: 抽象数据类型的实现实验项目性质: 设计性实验所属课程名称: 数据结构实验计划学时: 63.2
15、 实验目的对某个具体的抽象数据类型，运用课程所学的知识和方法，设计合理的数据结构，并在此基础上实现该抽象数据类型的全部基本操作。通过本设计性实验，检验所学知识和能力，发现学习中存在的问题。 进而达到熟练地运用本课程中的基础知识及技术的目的。3.3 预习与参考1确定要实现的抽象数据类型，并对基本操作做适当的选取和增加；2选择存储结构，并写出相应的类型定义；3设计各基本操作的实现算法，并表达为函数形式；4设计测试方案，编写主函数；5将上述4步的结果写成预习报告。3.4 实验要求和设计指标以教材中线性表，串，稀疏矩阵，广义表，二叉树，树，图以及查找表等抽象数据类型为对象，利用C语言的数据类型表示和实
16、现其中某个抽象数据类型。可选的抽象数据类型如下表所列：编号抽象数据类型基本难度教材页码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.21611动态查找表1.3数据结构P.226注：如果基本操作数量较多，可选择实现其中一个基本操作子集。实验要求如下：1参加实验的学生应首先了解设计的任务，然后根据自己的基础和能力从中选择一题
17、。一般来说，选择题目应以在规定的时间内能完成，并能得到应有的锻炼为原则。 若学生对教材以外的相关题目较感兴趣，希望选作实验的题目时，应征得指导教师的认可，并写出明确的抽象数据类型定义及说明。2. 实验前要作好充分准备，包括：理解实验要求，掌握辅助工具的使用，了解该抽象数据类型的定义及意义，以及其基本操作的算法并设计合理的存储结构。3. 实验时严肃认真，要严格按照要求独立进行设计，不能随意更改。注意观察并记录各种错误现象，纠正错误，使程序满足预定的要求，实验记录应作为实验报告的一部分。4. 实验后要及时总结，写出实验报告，并附所打印的问题解答、程序清单，所输入的数据及相应的运行结果。3.5 实验
18、仪器设备和材料软件实验室。编程环境：Anyview C可视化编程环境、TC+、C+Builder或者VC+。3.6 调试及结果测试 调试内容应包括：调试过程中遇到的问题是如何解决的以及对实验的讨论与分析；基本操作的时间复杂度和空间复杂度的分析和改进设想。列出对每一个基本操作的测试结果，包括输入和输出，测试数据应完整和严格。3.7 考核形式 考核形式以实验过程和实验报告相结合的方式进行。在实验完成后，应当场运行和答辩，由指导教师验收，只有在验收合格后才能算实验部分的结束。实验报告作为整个设计性实验评分的书面依据。设计性实验的成绩评定以选定题目的难易度、完成情况和实验报告为依据综合评分。从总体来说
19、，所实现的抽象数据类型应该全部符合要求，类型定义，各基本操作的算法以及存储结构清晰；各模快测试运行正确；程序的结构合理；设计报告符合规范。3.8 实验报告要求实验结束后要写出实验报告，以作为整个设计性实验评分的书面依据和存档材料。实验报告是反映学生实验效果的最主要的依据，也是学生正确地表达问题、综合问题和发现问题的能力的基本培养手段，因而是非常重要的内容。本设计性实验的报告要包括以下几项内容：（1）设计任务、要求及所用软件环境或工具；（2）抽象数据类型定义以及各基本操作的简要描述；（3）所选择的存储结构描述及在此存储结构上各基本操作的实现；（4）程序清单（计算机打印），输入的数据及各基本操作的
20、测试结果；（5）实验总结和体会。实验报告以规定格式的电子文档书写、打印并装订，排版及图表要清楚、工整。3.9 思考题 对设计性实验进行总结和讨论，包括本实验的优、缺点，数据存储结构的特点，与其它存储结构之间的比较等。通过总结，可以对抽象数据类型有更全面、深入的认识，这是设计性实验不可缺少的重要内容。这部分内容应作为实验报告中的一个组成部分。3.10 示例1. 题目采用字符类型为元素类型和无头结点单链表为存储结构，实现抽象数据类型List。 ADT List 数据对象：D ai | aiElemSet, i=1,2,.,n, n0 数据关系：R1 |ai-1, aiD, i=2,.,n 基本操作
21、： SetEmpty(&L) 操作结果：构造一个空的线性表L。 Destroy(&L) 初始条件：线性表L已存在。 操作结果：销毁线性表L。 Length(L) 初始条件：线性表L已存在。 操作结果：返回L中元素个数。 Get(L, i, &e) 初始条件：线性表L已存在，1iLengthList(L)。 操作结果：用e返回L中第i个元素的值。 Locate(L, e, compare() 初始条件：线性表L已存在，compare()是元素判定函数。 操作结果：返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。 Insert(&L, i, e) 初始条
22、件：线性表L已存在，1iLengthList(L)+1。 操作结果：在L的第i个元素之前插入新的元素e，L的长度加1。 Delete(&L, i, &e) 初始条件：线性表L已存在且非空，1iLengthList(L)。 操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。 Display(L) 初始条件：线性表L已存在。 操作结果：依次输出L的每个元素。 ADT List2存储结构定义公用头文件DS0.h:#include #include #include #include #include #define TRUE 1#define FALSE 0#define OK 1#def
23、ine ERROR 0#define IBFEASIBLE -1#define OVERFLOW -2 #define MAXLEN 20#define MAXSIZE 20typedef int Status;typedef char ElemType; /* 元素类型为字符类型*/（1） 顺序存储结构#define LIST_INIT_SIZE 20 /*线性表存储空间的初始分配量*/#define LISTINCREMENT 10 /*线性表存储空间的分配增量*/typedef struct ElemType *elem; /*存储空间基址*/ int length; /*当前长度*/
24、int listsize; /*当前分配的存储容量*/ SqList;（2） 无头结点单链表存储结构typedef struct LNode ElemType data; struct LNode *next; LNode, *LList; /* 不带头结点单链表类型*/（3） 带头结点单链表存储结构typedef struct LNode /* 结点类型 */ ElemType data; struct LNode *next; LNode, *Link, *Position;typedef struct LinkList /* 链表类型 */ Link head,tail; /* 分别指向
25、线性链表中的头结点和最后一个结点 */ int len; /* 指示线性链表中数据元素的个数 */ LinkList;3. 算法设计（1） 顺序存储结构Status SetEmpty(SqList &L) /*构造一个空的顺序线性表 */ L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem) return OVERFLOW; /* 存储分配失败 */ L.length=0; /* 空表长度为0 */ L.listsize=LIST_INIT_SIZE; /* 初始存储容量 */ return OK; Stat
26、us Destroy (SqList &L) /*销毁顺序线性表L */ free(L.elem); L.elem=NULL; L.length=0; L.listsize=0; return OK;int Length(SqList L) /* 求表长*/ return L.length;Status Get(SqList &L, int i, ElemType &e) /* 获取第i元素 */ if(iL.length) return ERROR; e=*(L.elem+i-1); return OK;int Locate(SqList L, ElemType x) /* 确定x在表中的位
27、序 */ ElemType *p; int i=1; /* i的初值为第1个元素的位序 */ p=L.elem; /* p的初值为第1个元素的存储位置 */ while(i=L.length & *p+!=x) +i; if(i=L.length) return i; else return 0;Status Insert(SqList &L, int i, ElemType e) /* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */ ElemType *newbase,*q,*p; if(iL.length+1) /* i值不合法 */ return ERROR; if
28、(L.length= L.listsize) /* 当前存储空间已满,增加分配 */ newbase=(ElemType *) realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType); if(!newbase) return OVERFLOW; /* 存储分配失败 */ L.elem=newbase; /* 新基址 */ L.listsize+=LISTINCREMENT; /* 增加存储容量 */ q=L.elem+i-1; /* q为插入位置 */ for(p=L.elem+L.length-1; p=q; -p) *(p+1
29、)=*p; /* 插入位置及之后的元素右移 */ *q=e; /* 插入e */ +L.length; /* 表长增1 */ return OK;Status Delete(SqList &L, int i, ElemType &e) /* 初始条件：顺序线性表L已存在，1iListLength(L) */ /* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */ ElemType *p,*q; if(i L.length) /* i值不合法 */ return ERROR; p= L.elem+i-1; /* p为被删除元素的位置 */ e=*p; /* 被删除元素的值赋给
30、e */ q= L.elem+L.length-1; /* 表尾元素的位置 */ for(+p; p=q; +p) /* 被删除元素之后的元素左移 */ *(p-1)=*p; L.length-; /* 表长减1 */ return OK;Status Display(SqList L) /* 依次显示表中元素 */ ElemType *p; int i; p=L.elem; printf( ); for(i=1; inext; free(q); q=L; return OK;int Length(LList L) /* 求表长*/ int n=0; while(L!=NULL) n+; L=
31、L-next; return n;Status Get(LList L, int i, ElemType &e) /* 获取第i元素 */ int j=1; while (jnext; j+; if(L!=NULL) e=L-data; return OK; else return ERROR; /* 位置参数i不正确 */int Locate(LList L, ElemType x) /* 确定x在表中的位序 */ int n=1; while (L!=NULL & L-data!=x) L=L-next; n+; if (L=NULL) return 0; else return n;St
32、atus Insert(LList &L, int i, ElemType e) /* 插入第i元素*/ int j=1; LList s,q; s=(LList)malloc(sizeof(LNode); s-data=e; q=L; if (i=1) s-next=q; L=s; return OK; else while(jnext!=NULL) q=q-next; j+; if (j=i-1) s-next=q-next; q-next=s; return OK; else return ERROR; /* 位置参数i不正确 */ Status Delete(LList &L, int
33、 i, ElemType &e) /* 删除第i元素*/ int j=1; LList q=L,t; if (i=1) e=q-data; L=q-next; free(q); return OK; else while (jnext!=NULL) q=q-next; j+; if (q-next!=NULL & j=i-1) t=q-next; q-next=t-next; e=t-data; free(t); return OK; else return ERROR; /* 位置参数i不正确*/ void Display(LList L) /* 依次显示表中元素 */ printf(单链表
34、显示: ); if (L=NULL) printf(链表为空!); else if (L-next=NULL) printf(%cn, L-data); else while(L-next!=NULL) printf(%c-, L-data); L=L-next; printf(%c, L-data); printf(n);（3） 带头结点单链表Status SetEmpty(LinkList &L) /* 置带头结点的空单链表*/ Link p; p=(Link)malloc(sizeof(LNode); /* 生成头结点 */ if(p) p-next=NULL; L.head=L.tai
35、l=p; L.len=0; return OK; else return ERROR;Status Destroy(LinkList &L) /* 销毁线性链表L，L不再存在 */ Link p,q; if(L.head!=L.tail) /* 不是空表 */ p=q= L.head-next; L.head-next=NULL; while(p!=L.tail) p=q-next; free(q); q=p; free(q); free(L.head); L.head=L.tail=NULL; L.len=0; return OK;int Length(LinkList L) /* 返回线性
36、链表L中元素个数 */ return L.len;Status Get(LinkList L, int i, ElemType &e) /* 获取第i元素 */ /* i=0为头结点 */ Link p; int j; if(iL.len) return ERROR; else p=L.head; for(j=1;jnext; e=p-data; return OK; int Locate(LinkList L, ElemType x) /* 确定x在表中的位序 */ int i=0; Link p=L.head; do p=p-next; i+; while(p & p-data!=x);
37、/* 没到表尾且没找到满足关系的元素 */ if (!p) return 0; else return i;Status Insert(LinkList &L, int i, ElemType e) /* 插入第i元素*/ int j=0; Link s,q; s=(Link)malloc(sizeof(LNode); s-data=e; q=L.head; while(jnext!=NULL) q=q-next; j+; if (j=i-1) s-next=q-next; q-next=s; if (L.tail=q) L.tail=s; L.len+; return OK; else re
38、turn ERROR; /* 位置参数i不正确 */Status Delete(LinkList &L, int i, ElemType &e) /* 删除第i元素*/ int j=0; Link q=L.head,t; while (jnext!=NULL) q=q-next; j+; if (q-next!=NULL & j=i-1) t=q-next; q-next=t-next; e=t-data; if(L.tail=t) L.tail=q; free(t); L.len-; return OK; else return ERROR; /* 位置参数i不正确*/void Displa
39、y(LinkList L) /* 依次显示表中元素 */ Link p; printf(单链表显示: ); if (L.head=L.tail) printf(链表为空!); else p=L.head-next; while(p-next!=NULL) printf(%c-, p-data); p=p-next; printf(%c, p-data); printf(n);4测试（1） 顺序存储结构SqList head; void main() /* 主函数*/ char e,c; int i,n,select,x1,x2,x3,x4,m,g; SetEmpty(head); n=random(8); /* 随机产生表长 */ for (i=1; i=n; i+) /* 将数据插入到顺序表中 */ c=A+random(26); Insert(head,i,c); do Display(head); printf(select 1 求长度 Le