小学期《数据结构》实验指导书.doc

数据结构小学期实验指导书石家庄铁道学院计算机系2006.8目 录实验指导书概述3实验大纲实习题4实习报告规范5实习步骤6附录1：实验报告示例7附录2：实验教学大纲10实验指导书概述“数据结构”是计算机专业一门重要的专业技术基础课程，是一门关键性核心课程。本课程系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了多种常用的查找和排序技术，并对其进行了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。由于以下原因，使得掌握这门课程具有较大难度： · (1) 内容多，时间短，给学习带来困难；· (2) 贯穿全书的动态链表存储结构和递归技术是学习中的重点和难点；· (3) 隐含在各部分的技术和方法丰富，也是学习的重点和难点；· (4) 先修课程中所介绍的专业性知识不多，加大了学习难度。由于数据结构课程的技术性与实践性，数据结构课程实验的设置十分必要。为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。通过实验实践内容的训练，突出构造性思维训练的特征, 提高学生组织数据及编写大型程序的能力。 上机实习是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。较大的实习题比平时的习题要复杂得多，也更接近实际。实习着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力。实习还能使书上的知识变“活”，达到深化理解和灵活掌握教学内容的目的。平时的练习较偏重于如何编写功能单一的“小”算法，而实习题是软件设计的综合训练，包括问题分析，总体结构设计，用户界面设计，程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。此外，还有很重要的一点是：机器是比任何教师都严格的检查者。 每个实习题采取了统一的格式，由问题描述、基本要求、实现提示等部分组成。 问题描述旨在为读者建立问题提出的背景环境，指明问题“是什么”； 基本要求则对问题进一步求精，划出问题的边界，指出具体的参量或前提条件，并规定该题的最低限度要求； 实现提示对实现中的难点及其解法思路等问题作了简要提示，个别问题给出了参考实现。 在实现的时候应注意，要尽量减少依赖于具体机器计算环境的用法，若使用，也应在注释中指出。这样得出的程序易于在不同机器上运行，有好的可移植性。C语言是结构化程序设计语言，具有递归能力，可移植性也较好，是特别推荐的实现语言。 本书的一个特点是为实习制定了严格的规范。一种普遍存在的错误观念是，调试程序全凭运气。学生花2个小时的机上时间只找出一个错误，甚至一无所获的情况是常见的。其原因在于，很多人只认识到找错误，而没有认识到努力预先避免错误的重要性，也不知道应该如何努力。实际上，结构不好、思路和概念不清的程序可能是根本无法调试正确的。严格按照实习步骤规范进行实习，不但能有效地避免上述种种问题，更重要的是有利于培养软件工作者不可缺少的科学工作方法和作风。 在附录中提供了一个完整的实习报告示例，在起到实习报告规格范例作用的同时，还隐含地提供了很多有益的东西，比如基于数据类型的系统划分方法以及所提倡的程序设计风格等等。计算机学科在不断发展，可以使用的语言工具越来越丰富，在本书中的实习示例是应用面向过程的语言进行设计和编程，同样的实习题，也可以用面向对象的语言来实现。实验大纲实习题实习一 校园导游程序问题描述 用无向网表示学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。游客通过终端可询问： （1）从某一景点到另一景点的最短路径。（2）游客从公园进入，选取一条最佳路线。（3）使游客可以不重复地浏览各景点，最后回到出口（出口就在入口旁边）。基本要求 （1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离为此图选择适当的数据结构。 （2）把各种路径都显示给游客，由游客自己选择浏览路线。 （3）画出景点分布图于屏幕上。实现提示 （1）构造一个无向图G并用邻接矩阵来存储。 （2）利用迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组pi来记录，最短路径长度就用一维数组di存放；i的范围：020。 （3）一维数组have是用来记录最短路径出现顶点的顺序。 （4）根据起点和终点输出最短路径和路径长度。实习二 员工管理系统问题描述每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。基本要求根据实验内容编程，上机调试、得出正确的运行程序。系统能够完成员工信息的查询、更新、插入、删除、排序功能。写出实验报告（包括源程序和运行结果）。实现提示 （1）建立一个带头结点的单向链表（无序）。 （2）对单链表进行插入，删除，更新操作。 （3）在主函数中设计一个简单的菜单，分别调试上述算法。 实习报告规范实习报告的开头应给出题目、班级、姓名、学号和完成日期，并包括以下7个内容：1需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：(1)输入的形式和输入值的范围；(2)输出的形式；(3)程序所能达到的功能；(4)测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。2概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。3详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；画出函数和过程的调用关系图。4调试分析内容包括：a调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；b算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；c经验和体会等。5用户使用说明说明如何使用你编写的程序，详细列出每一步的操作步骤。6测试结果列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。7附录带注释的源程序。如果提交源程序软盘，可以只列出程序文件名的清单。在以下各实习单元中都提供了实习报告实例。值得注意的是，实习报告的各种文档资 料，如：上述中的前三部分要在程序开发的过程中逐渐充实形成，而不是最后补写(当然可以也应该最后用实验报告纸誊清或打印)。 实习步骤随着计算机性能的提高，它所面临的软件开发的复杂度也日趋增加。然而，编制一个10000行的程序的难度绝不仅仅是一个5000行的程序的两倍，因此软件开发需要系统的方法。一种常用的软件开发方法，是将软件开发过程分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实习题的复杂度远不如(从实际问题中提出来的)一个“真正的” 软件，但为了培养一个软件工作者所应具备的科学工作的方法和作风，我们制订了如下所述 完成实习的5个步骤：1问题分析和任务定义通常，实习题目的陈述比较简洁，或者说是有模棱两可的含义。因此，在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么，限制条件是什么。注意：本步骤强调 的是做什么，而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完 成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的形式；输出数据的类 型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么，是否接受非法的输入， 对非法输入的回答方式是什么等等。这一步还应该为调试程序准备好测试数据，包括合法的 输入数据和非法形式输入的数据。2数据类型和系统设计在设计这一步骤中需分逻辑设计和详细设计两步实现。逻辑设计指的是，对问题描述中 涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程 序模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各过程和函数的伪码 算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象 数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。作为逻辑设计 的结果，应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的规格说 明)，各个主要模块的算法，并画出模块之间的调用关系图。详细设汁的结果是对数据结构和 基本操作的规格说明作出进一步的求精，写出数据存储结构的类型定义，按照算法书写规范用类Pascal语言写出过程或函数形式的算法框架。在求精的过程中，应尽量避免陷入语言细节，不必过早表述辅助数据结构和局部变量。3编码实现和静态检查编码是把详细设计的结果进一步求精为程序设计语言程序。程序的每行不要超过60个字符。每个过程(函数)体，即不计首部和规格说明部分，一般不要超过40行。最长不得超过60行，否则应该分割成较小的过程(函数)。要控制1D1语句连续嵌套的深度。其他要求参见第一篇的算法书写规范。如何编写程序才能较快地完成调试是特别要注意的问题。对于编程很熟练的读者，如果基于详细设计的伪码算法就能直接在键盘上输入程序的话，则可以不必用笔在纸上写出编码，而将这一步的工作放在上机准备之后进行，即在上机调试之前直接用键盘输入。然而，不管你是否写出编码的程序，在上机之前，认真的静态检查却是必不可少的。多数初学者在编好程序后处于以下两种状态之一：一种是对自己的“精心作品”的正确性确信不疑；另一种是认为上机前的任务已经完成，纠查错误是上机的工作。这两种态度是极为有害的。事实上，非训练有素的程序设计者编写的程序长度超过50行时，极少不含有除语法错误以外的错误。上机动态调试决不能代替静态检查，否则调试效率将是极低的。静态检查主要有两种方法，一是用一组测试数据手工执行程序(通常应先分模块检查)；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注解和断言。如果程序中逻辑概念清楚，后者将比前者有效。4上机准备和上机调试上机准备包括以下几个方面：(1) 高级语言文本(体现与编译程序用户手册)的扩充和限制。(2) 如果用c语言，要特别注意平时惯用的类c语言与标准c语言之间的细微差别。(3) 熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便顺利进行上机的基本活动。(4) 掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。“磨刀不误砍柴 工”。计算机各专业的学生应该能够熟练运用高级语言的程序调试器DEBUG调试程序。上机调试程序时要带一本高级语言教材或手册。调试最好分模块进行，自底向上，即先调试低层过程或函数。必要时可以另写一个调用驱动程序。这种表面上麻烦的工作实际上可以大大降低调试所面临的复杂性，提高调试工作效率。在调试过程中可以不断借助DEBUG的各种功能，提高调试效率。调试中遇到的各种异常现象往往是预料不到的，此时不应“苦思具想”，而应动手确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，印出带有完整注释的且格式良好的源程序清单和结果。5总结和整理实习报告附录1：实验报告示例 _级 _班 _年_月_日姓名_ 学号_ 电话_ 1实验题目编制一个演示单链表插入、删除、查找等操作的程序2需求分析本演示程序用TC编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数 输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。 程序所能达到的功能：完成单链表的生成（通过插入操作）、插入、删除、查找操作 测试数据：A 插入操作中依次输入11，12，13，14，15，16，生成一个单链表B 查找操作中依次输入12，15，22返回这3个元素在单链表中的位置C 删除操作中依次输入2，5，删除位于2和5的元素3概要设计1）为了实现上述程序功能，需要定义单链表的抽象数据类型：ADT LinkList 数据对象：D=ai|aiIntegerSet,i=0,1,2,n,n0 数据关系：R=<ai,ai+1>|ai,ai+1 D基本操作：InitLinkList(&L)操作结果：构造一个空的单链表L.InsLinkList(&L,pos,e)初始条件：单链表L已存在操作结果：将元素e插入到单链表L的pos位置DelLinkList(&L,pos,&e)初始条件：单链表L已存在操作结果：将单链表L中pos位置的元素删除，元素值置入e中返回LocLinkList(L,e)初始条件：单链表L依存在操作结果：单链表L中查找是否元素e，若存在，返回元素在表中的位置；若不存在，返回-1.Menu()操作结果：在屏幕上显示操作菜单2）本程序包含7个函数： 主函数main() 初始化单链表函数InitLinkList() 显示操作菜单函数menu() 显示单链表内容函数dispLinkList() 插入元素函数InsLinkList() 删除元素函数DelLinkList() 查找元素函数LocLinkList()各函数间关系如下：4详细设计实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。1) 结点类型和指针类型typedef struct node int data;struct node *next;Node,*LinkListl;2) 单链表的基本操作为了方便，在单链表中设头结点，其data域没有意义。bool InitLinkList(LinkList &L)（伪码算法）void DispLinkList(LinkList L)（伪码算法）void menu()（伪码算法）bool InsLinkList(LinkList &L,int pos,int e)（伪码算法）bool DelLinkList(LinkList &L,int pos,int &e)（伪码算法）int LocLinkList(LinkList L,int e)（伪码算法）3) 其他模块伪码算法5调试分析(略)6使用说明程序名为LinkList.exe，运行环境为DOS。程序执行后显示=0-EXIT1-INSERT2-DELETE3-LOCATE=SELECT:在select后输入数字选择执行不同的功能。要求首先输入足够多的插入元素，才可以进行其他的操作。每执行一次功能，就会显示执行的结果（正确或错误）以及执行后单链表的内容。选择0：退出程序选择1：显示“INSERT pos,e =” ，要求输入要插入的位置和元素的值（都是整数）。选择2：显示“DELETE pos =” ，要求输入要删除元素的位置，执行成功后返回元素的值。选择3：显示“LOCATE e = ” ，要求输入要查找元素的值，执行成功后返回元素在表中的位置7测试结果1） 建立单链表：» 选择1，分别输入（0，11），（0，12），（0，13），（0，14）（0，15）。得到单链表（15，14，13，12，11）2） 插入：» 选择1输入（1，100），得到单链表（15，100，14，13，12，11）» 选择1输入（-1，2），显示输入错误» 选择1输入（7，2），显示输入错误» 选择1输入（6，2），得到单链表（15，100，14，13，12，11，2）3） 删除：» 选择2，输入1。返回e=100，得到单链表（15，14，13，12，11，2）» 选择2，输入0。返回e=15，得到单链表（14，13，12，11，2）» 选择2，输入4。返回e=2，得到单链表（14，13，12，11）» 选择2，输入5。返回输入错误4） 查找» 选择3，输入14。返回pos=0» 选择3，输入100。返回输入错误附录2：实验教学大纲小学期算法与数据结构实验教学大纲课程编号： 计划学时：2周面向专业：计算机科学与技术专业制 订：计算机软件教研室执 笔 人：武守秋审 定 人：邸书灵一、课程性质、目的及任务数据结构是计算机科学与技术专业的一门核心的专业技术基础课程，也是一门实践性很强的课程。上机实习是对学生的一种全面综合训练，是与课堂听讲、练习相辅相成的重要教学环节。通过本课程的实验教学，深化理解和灵活掌握各种基本数据结构及其应用，培养学生基本程序设计素养和良好工作作风，训练学生进行复杂程序设计的技能，提高知识的综合应用和软件开发能力。二、主要参考书1、数据结构（C语言版） 严蔚敏，吴伟民 清华大学出版社 2002年2、数据结构C语言描述 耿国华等 西安电子科技大学出版社 2002年3、Data Structure &Program Design in C Robert L.Kruse 清华大学出版社 2001年4、数据结构（用面向对象方法与C+描述） 殷人昆 清华大学出版社 1999年三、考试考核办法根据考勤、实验检查及实验报告等综合考虑给定。四、实验项目与内容提要序号实验项目名称实验内容提要实验性质实验者类别学时数开设组数每组人数实验消耗（元/人时）主要仪器设备名称及配套数1校园导游程序用无向网表示学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。验证 演示设计综合 研究生 Turbo c或vc+本科生107011专科生 2员工管理系统每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。系统能够完成员工信息的查询、更新、插入、删除、排序功能。验证 演示 设计 综合研究生 Turbo c或vc+本科生107011专科生