77范文网 - 专业文章范例文档资料分享平台

数据结构实验指导书

来源:网络收集 时间:2019-03-10 下载这篇文档 手机版
说明:文章内容仅供预览,部分内容可能不全,需要完整文档或者需要复制内容,请下载word后使用。下载word有问题请添加微信号:或QQ: 处理(尽可能给您提供完整文档),感谢您的支持与谅解。点击这里给我发消息

数据结构实验指导书

修订日期:2008年5月 修订单位:计算机科学与技术系 执笔人:魏海平 冯锡伟 李文超 一、 本大纲适用范围:

计算机科学与技术专业;信息与计算科学专业;软件工程专业 二、 实验与实习内容要求 ⒈ 学时数:共32学时 ⒉ 内容

包括线性表、串、树形结构、图形结构、排序和检索共六部分。

⒊ 要求:根据具体题目设计算法和程序,并在计算机上实现,具体见实验指导书。 1

1概 述 ......................................................................... 3

1.1实验目的 ................................................................. 4 1.2 实验要求 ................................................................. 4

1.2.1验证实验的一般步骤 ................................................. 4 1.2.2设计实验和综合实验的一般步骤........................................ 5 1.3实习报告内容 ............................................................. 6 2 实验指导书 ..................................................................... 6

2.1验证性实验 ............................................................... 6

实 验 一 单链表操作验证 ............................................... 6 实 验 二 二叉树操作验证 .............................................. 14 实 验 三 散列表的建立 ................................................ 16 2.2设计性实验 .............................................................. 18

实 验 一 统计候选人得票 .............................................. 18 实 验 二 汉诺塔问题 .................................................. 19 实 验 三 求无向连通图的生成树 ........................................ 20 实 验 四 顺序查找与折半查找的性能比较 ................................ 21 2.3综合性实验 .............................................................. 22

实 验 一 约瑟夫环问题 ................................................ 22 实 验 二 迷宫最短路径 ................................................. 23 实 验 三 静态链表实现对k个共享空间的栈进行操作的算法 ................ 25 实 验 四 模拟旅馆管理系统的一个功能——床位的分配与回收 .............. 26 实 验 五 串编辑 ................................................... 28 实 验 六 哈夫曼编码 .................................................. 29 实 验 七 交通问题系统 ............................................ 30 实 验 八 医院选址问题 ................................................ 32 实 验 九 查找、排序算法效率的实验分析 ............................ 33 实 验 十 简单个人电话号码查询系统 .................................... 33 实 验 十一 各种排序算法时间性能的比较 ................................ 35 实 验 十二 机器调度问题 .............................................. 35

2

1概 述

数据结构是一门实践性很强的课程,只靠读书和做习题是不能提高实践能力的,尤其是在数据结构中要解决的问题更接近于实际。数据结构的实验是对学生的一种全面的综合训练,与程序设计语言课程中的实验不同,数据结构课程中的实验多属创造性的活动,需要学生自己分析问题,设计数据结构和算法,再上机调试和测试程序。数据结构实验是一种自主性很强的学习过程,其教学目的主要有两个:(1)深化理解和掌握书本上的理论知识,将书本上的知识变“活”;(2)理论和实践相结合,使学生学会如何把书本上有关数据结构和算法的知识用于解决实际问题,培养数据结构的应用能力和软件工程所需要的实践能力。

为了达到上述目的,本书安排了如下三类实验:

(1)验证实验:其主要内容是将书上的重要数据结构上机实现,深化理解和掌握理论知识,这部分的实验不需要学生自己设计,只须将给定的方案实现即可;

(2)设计实验:其主要内容是针对具体问题,应用某一个知识点,自己设计方案,并上机实现,目的是培养学生对数据结构的简单应用能力;

(3)综合实验:其主要内容是针对具体问题,应用某几个知识点,自己设计方案,并上机实现,目的是培养学生对数据结构的综合应用能力。

在验证实验中,由实验目的、实验内容、实现提示和实验程序等4部分组成,其中实验目的明确了该实验要学生掌握哪些知识点;实验内容规定了实验的具体任务;实现提示给出了数据结构和算法的设计方法;实验程序给出了实验的范例程序,并且在主教材的随书光盘中有该实验涉及到的数据结构的全部实现。在验证实验中,不要求但鼓励学生在完成实验任务的基础上,对该实验涉及的数据结构的其他实现方法进行探索。

在设计实验和综合实验中,由问题描述、基本要求、设计思想、思考题等4部分组成,其中问题描述是为学生建立问题的背景环境,指明“问题是什么”;基本要求是对问题的实现进行基本规范,保证预定的训练意图,使某些难点和重点不会被绕过去,而且也便于教学检查;设计思想给出了设计数据结构和算法的主要思路;思考题引导学生在做完实验后进行总结和扩充。

虽然在设计实验和综合实验中都给出了一定的设计方案,但是,学生不应拘泥于这些分析和设计,要尽量发挥想象力和创造力。对于一个实际问题,每个人可能会有不同的解决办法,本书给出的范例方案,只是希望把学生的思路引人正轨,提出了思考问题的方法,但是不希望限制学生的思维,鼓励学生自己设计解决方案。

3

1.1实验目的

《数据结构》是一门实践性很强的软件基础课程,为了学好这门课,每个学生必须完成一定数量的上机作业。通过本课程的上机作业,要求在数据结构的选择和应用、算法的设计及实现等方面加深对课程基础内容的理解,同时,在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

1.2 实验要求

1.2.1验证实验的一般步骤

验证实验安排的内容在书上都能找到具体的实现方法,并且在主教材的随书光盘中也都有相应的程序实现。这些验证实验是学生在学习完一种数据结构后进行的,对于深化理解和掌握相应数据结构具有很重要的意义。

1.预备知识的学习

由于篇幅所限,本书没有整理验证实验所用到的预备知识,但主教材中的相关内容已经叙述得很清楚了,需要学生在实验前复习实验所用的预备知识。这需要学生有自主的学习意识和整理知识的能力。

2.上机前的准备

将实现提示中给出的数据类型和算法转换为对应的程序,并进行静态检查,尽量减少语法错误和逻辑错误。

很多学生在上机时只带一本数据结构书或实验指导书,而书上只有算法设计而没有实验程序,于是就直接在键盘上输入程序,结果不仅程序的输入速度慢,而且编译后出现很多错误。上机前的充分准备能高效利用机时,在有限的时间内完成更多的实验内容。

3.上机调试和测试程序

调试程序是一个辛苦但充满乐趣的过程,也是培养程序员素质的一个重要环节。很多学生都有这样的经历:花了好长时间去调试程序,错误却越改越多。究其原因,一方面,是对调试工具不熟悉,出现了错误提示却不知道这种错误是如何产生的;另一方面,没有认识到努力预先避免错误的重要性,也就是对程序进行静态检查。

对程序进行测试,首先须设计测试数据。在数据结构中测试数据须考虑以下两种情况。(1)一般情况:例如循环的中间数据、随机产生的数据等;(2)特殊情况:例如循环的边界条件、数据结构的边界条件等。

4.实验报告

4

在实验后要总结和整理实验报告。

1.2.2设计实验和综合实验的一般步骤

设计实验和综合实验的自主性比较强,涉及到的知识点也比较多,可以在课程设计中完成,设计实验建议由单人完成,综合实验建议由多人完成,主要目的是为了培养数据结构的应用能力、软件工程的规范训练、团队精神和良好的科学作风。

1.问题分析

在设计实验和综合实验中的问题描述通常都很简洁,因此,首先要充分理解问题,明确问题要求做什么,限制条件是什么,也就是对所要完成的任务做出明确的描述,例如,输入数据的类型、值的范围以及输人的形式,输出数据的类型、值的范围以及输出的形式,哪些属于非法输人,等等。在问题分析时还应该准备好测试数据。

2.概要设计

概要设计是对问题描述中涉及到的数据定义抽象数据类型,设计数据结构,设计算法的伪代码描述。在这个过程中,要综合考虑系统的功能,使得系统结构清晰、合理、简单,抽象数据类型尽可能做到数据封闭,基本操作的说明尽可能明确。而不必过早地考虑存储结构,不必过早地考虑语言的实现细节,不必过早地表述辅助数据结构和局部变量。

3.详细设计

在详细设计阶段,要设计具体的存储结构(即用C++描述抽象数据类型对应的类)以及算法所需的辅助数据结构,算法在伪代码的基础上要考虑细节问题并用C++描述。

此外,还要设计一定的用户界面。数据结构课程实验的主要目的是为了培养数据结构的应用能力,因此在实验中不要求图形界面,只要在屏幕上提示用户每一步操作的输入,并将结果物出即可。

4.编码实现和静态检查

将详细设计阶段的结果进一步优化为C++程序,并完成静态检查。

很多初学者在编写程序后都有这样的心态:确信自己的程序是正确的,认为上机前的任务已经完成,检查错误是计算机的事。这种心态是极为有害的,这样的上机调试效率是极低的。事实上,即使有几十年经验的高级软件工程师,也经常利用静态检查来查找程序中的错误。

5.上机调试和测试程序

掌握调试工具,设计测试数据,上机调试和测试程序。调试正确后,认真整理源程序和注释,给出带有完整注释且格式良好的源程序清单和结果。

6.总结并整理实验报告

5

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读,免费范文网,提供经典小说综合文库数据结构实验指导书在线全文阅读。

数据结构实验指导书.doc 将本文的Word文档下载到电脑,方便复制、编辑、收藏和打印 下载失败或者文档不完整,请联系客服人员解决!
本文链接:https://www.77cn.com.cn/wenku/zonghe/511413.html(转载请注明文章来源)
Copyright © 2008-2022 免费范文网 版权所有
声明 :本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。
客服QQ: 邮箱:tiandhx2@hotmail.com
苏ICP备16052595号-18
× 注册会员免费下载(下载后可以自由复制和排版)
注册会员下载
全站内容免费自由复制
注册会员下载
全站内容免费自由复制
注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: