资源描述：
《数据结构大纲及实验指导书》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、数据结构大纲及实验指导书一、本大纲适用范围：计算机软件专业、计算机应用专业二、实验与实习内容要求1•学时数：共20学时2.内容包括线性表、串、树形结构、图形结构、排序和检索共六部分3•要求：根据具体题目设计算法和程序，并在计算机上实现，具体见实验指导书第一部分概述一、实验目的《数据结构》是一门实践性很强的软件基础课程，为了学好这门课，每个学生必须完成一定数量的上机作业。通过木课程的上机作业，要求在数据结构的选择和应用、算法的设计及实现等方面加深对课程基础内容的理解，同时，在程序设计方法以及上机操作等棊本技能和科学作风方面受到比较系统和严格的训练。二、实验要求1.问题分析充分地分析和理解
2、问题木身，弄清要求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据间的联系等。2.数据结构设计针对要求解决的问题，考虑各种可能的数据结构，并且力求从中出最住方案（必须连同算法一起考虑），确定主要的数据结构及全程变量。对引入的每种数据结构和全程变量要详细说明其功能、初值和操作特点。3.算发设计算法设计分概要设计和详细设计，概要设计着重解决程序的模块设计问题，这包括考虑如何把被开发的问题程序口顶向卜-分解成若干顺序模块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交换问题.详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出，相当于PASCAL语言的过
3、程或函数设计。4.测试用例设计准备典型测试数据和测试方案，测试数据要冇代表性、敏感性，测试方案包括模块测试和模块集成测试。5.上机调试对程序进行编译，纠正程序屮可能出现的语法错课，测试前，先运行一遍程序看看究竟将会发生什么，如果错误较多，则根据事先设计的测试方案并结合现场情况进行错误跟踪，包括打卬执行路径或输出中间变量值等手段。三、实习报告内容1•问题描述：包括冃标、任务、条件和约束的描述。2.设计：（1）数据结构设计和核心算法设计描述；（2）主控及功能模块层次结构；（3）主要功能模块的输入、处理（算法框架描述）和输出；（4）功能模块Z间的调用与被调用关系等。3•测试：测试范例，测试结
4、果，测试结果的分析与讨论，测试过程屮遇到的主要问题及所采用的解决捲施。4.使用说明和作业小结：（1）使用说明主耍描述如何使用你的程序以及使用时的主耍事项；（2）在小结中说明程序的改进思想、经验和体会，并回答教师布置的讨论题。5•打印一份程序清单及运行示例的结果。将以上各项文字材料及程序清单等装订成册，形成一个完整的报告。第二部分实验指导书实验一题目：迷宫最短路径1•问题描述从一个迷宫的入口到出口找出—•条最短路经。用一个二维数组MAZE(1：m,1：n)模拟迷宫，数组元素为()表示该位置可以通过，数组元素为1表示该位置不可以通行。MAZE(1,1)和MAZE(m,n)分别为迷宫的入口和
5、出口。2•基本要求(1)输入数据久输入迷宫的大小m行和n列，两者为整数b.由随机数产生0或1,建立迷宫。(2)输岀数据首先输岀模拟迷宫的二维数纟FI，若存在最短路经，则由出口回朔到入口打卬这一条路径，如下所示：(m,n),,(I,j),,(1,1)如无通道，则打印：THEREISNOPATH.3•实现提示(1)数据结构a)为了在程序屮判断方便，把迷宫扩展成为MAZE(()：m+1,0：n+1),扩展部分的元素设置为1,相当于在迷宫周围布上一圈不准通过的墙，这样，在迷宫的任一位置(1,j)上都有八个可以移动的方向。b)用二维数mMOVE(l：8,1：2)存放八个方向上的位置罐，如图所示：
6、2])2])MOVE的设置情况121・102-1130141151061・170・18-1-1a)为了标志已经通过的位置，采用一个标志数纟RMARKl..n)初值为()，在寻找路径的过程中，若通过了位置(I,j),则将MARK(I,J)置为为1。b)为了记录查找过程中到达位置及其前一位置，建立一个0..2)数组，对于某一个数纽元索Q(P)，具中，Q(P，0)和Q(P,1)记下到达位置I和j,Q(P,2)记下其出发点在Q数组中的下标。(1)算法基本思想将入口(1,1)作为第一个出发点，依次在八个反方向上搜索可通行的位置，形成第一层新的出发点，然后对第一层屮各个位置分别搜索他所在八个方向上
7、的可通行位置，形成第二层新的出发点，…，如此进行下去，直至达到出口(m,n)或者迷宫所有位置都搜索完毕为止。具体实施：从(m,n)开始，将其记入Q数组，比如记入Q(l),以它作为第一个出发点，依次对八个方向进行捜索，若下一个位置(I,j)可通行并尚未经过(即MAZE(I,j)=0KMARK(I,j)=0),则记入Q数组，如记在Q(P),则在Q(P,2)中要记下其出发点在Q数组中的F标1,在八个方向上都搜索过以后，根据先进先出的原则Q从数组中重新
