《数据结构》实验指导书

《《数据结构》实验指导书》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验指导书课程名称：数据结构计算机科学与工程系《数据结构》课程组目录前言1一、实验的作用和目的2二、实验方式与考核方式2三、实验要求3四、实验报告要求4五、实验内容5实验一线性表应用5实验二栈与队列应用10实验三二叉树的操作14实验四图的遍历18实验五查找算法应用21六、选做实验内容24实验六排序24实验七数组和广义表26实验八串27前言《数据结构》数据结构是计算机科学与技术及相关专业的一门重要专业基础课，它主要介绍线性结构、树型结构、图状结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法，以及算法的时间、空间效率

2、分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过本课程的学习，使学生熟练地掌握数据结构的内在逻辑关系及其在计算机中的表示方法（存储结构），以及相关基本操作的算法实现；掌握典型算法的设计思想及程序实现；熟悉各种数据结构在计算机科学中的基本应用；培养和训练学生结合实际应用，根据实际问题选取合适的数据结构、存储方案设计出简洁、高效、实用的算法；并为学习《操作系统》、《编译原理》、《数据库原理》等后续课程和研制开发各种系统和应用软件打下扎实的理论与实践基础。学习这门课程，习题和实验是两个关键环节。学生理解

3、算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写此实验指导书。实验指导书按照实验教学大纲的要求，为每个主要的知识点精选了的典型的实验题目，对每个实验题目提出具体实现要求，并对算法的实现进行提示，希望对同学实验有所帮助。《数据结构》课程组2005年5月一、实验的作用和目的实验课是对学生的一种全面综合训练，是与课堂教学、课后练习相辅相成的必不可少的一个教学环节。《数据结构》是一门实践性很强的软件基础课程，为了学好这门课，每个学生必须完成一定数量的上机实验作业。

4、通过课程的上机实验，可使学生深刻理解各种逻辑结构、存储结构的特性；学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。本课程的实验着眼于原理与应用的结合点。通过课程的实验，培养学生分析问题，并能针对实际应用问题选择适用的逻辑结构、存储结构，设计和实现相应算法。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练，培养设计具有专业水准应用程序的能力。二、实验方式与考核方式课程实验采用课内实验学时与课外实验学

5、时相结合（课外实验学时是课内实验学时的2倍）的方式。本课程的课内实验学时为16学时，要完成的5个实验主要覆盖线性表、栈和队列、树、图、查找五部分内容。每个实验中的题目按类型可分为验证型、设计性、综合实验,按难度可分为达到“实验设置基本要求”和“实验设置较高要求”的实验。每次实验，每位同学可结合自己的情况，从任课教师布置的题目中选取具体实验题目，按要求完成实验任务。任课教师一般提前2周布置实验任务和具体实验题目。学生要在课下充分了解实验内容，并完成问题分析、算法设计，并利用课外实验学时基本完成程序设计。每个实验的课内实验学时

6、安排同学集中在本系实验室进行，任课教师和实验指导教师针对同学的不同问题分别进行指导，并检查实验完成情况，要求学生回答相关的问题。每次实验完成后，学生需整理实验结果，并完成实验报告。实验成绩从两方面评定：实验完成情况和实验报告质量。实验完成情况：指导教师根据学生的实验准备情况、实验难度、实验完成情况、源程序质量、回答问题情况、实验纪律等方面给分。实验报告书写：学生在实验后的一周内提交打印好的实验报告。教师根据实验报告质量评定成绩。5实验总成绩=（∑第i次实验成绩）i=1三、实验要求⒈问题分析：充分地分析和理解问题本身，弄清要

7、求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据间的联系等。⒉数据结构设计：针对要求解决的问题，考虑各种可能的数据结构，并且力求从中出最佳方案（必须连同算法一起考虑），确定主要的数据结构及全程变量。对引入的每种数据结构和全程变量要详细说明其功能、初值和操作特点。⒊算法设计：算法设计分概要设计和详细设计，概要设计着重解决程序的模块设计问题，包括考虑如何把程序自顶向下分解成若干顺序模块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交换问题。详细设计则要决定每个模块内部的具体算法，包括输入、处理和

8、输出，相当于C语言中具体的函数设计。⒋测试用例设计：准备典型测试数据和测试方案，测试数据要有代表性、敏感性，测试方案包括模块测试和模块集成测试。⒌上机调试并分析结果：对程序进行编译，纠正程序中可能出现的语法错误。测试前，先运行一遍程序看看究竟将会发生什么，如果错误较多，则根据事先设计的测试方案并结合现场