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

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