数据结构大纲及实验指导书.doc

《数据结构大纲及实验指导书.doc》由会员分享，可在线阅读，更多相关《数据结构大纲及实验指导书.doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构大纲及实验指导书数据结构大纲及实验指导书一、一、本大纲适用范围：本大纲适用范围：计算机软件专业、计算机应用专业二、二、实验与实习内容要求实验与实习内容要求 学时数：共 20 学时 内容包括线性表、串、树形结构、图形结构、排序和检索共六部分 要求：根据具体题目设计算法和程序，并在计算机上实现，具体见实验指导书第一部分第一部分概述概述一、一、实验目的实验目的数据结构是一门实践性很强的软件基础课程，为了学好这门课，每个学生必须完成一定数量的上机作业。通过本课程的上机作业，要求在数据结构的选择和应用、算法的设计及实现等方面加深对课程基础内容的理解，同时，在程序设计方法以及上机操作等基本技能和科

2、学作风方面受到比较系统和严格的训练。二、二、实验要求实验要求 问题分析问题分析充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据间的联系等。数据结构设计数据结构设计针对要求解决的问题，考虑各种可能的数据结构，并且力求从中出最佳方案(必须连同算法一起考虑)，确定主要的数据结构及全程变量。对引入的每种数据结构和全程变量要详细说明其功能、初值和操作特点。算发设计算发设计算法设计分概要设计和详细设计，概要设计着重解决程序的模块设计问题，这包括考虑如何把被开发的问题程序自顶向下分解成若干顺序模块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交

3、换问题.详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出，相当于 PASCAL 语言的过程或函数设计。测试用例设计测试用例设计准备典型测试数据和测试方案，测试数据要有代表性、敏感性，测试方案包括模块测试和模块集成测试。上机调试上机调试对程序进行编译，纠正程序中可能出现的语法错误，测试前，先运行一遍程序看看究竟将会发生什么，如果错误较多，则根据事先设计的测试方案并结合现场情况进行错误跟踪，包括打印执行路径或输出中间变量值等手段。三、三、实习报告内容实习报告内容 问题描述问题描述：包括目标、任务、条件和约束的描述。设计设计：数据结构设计和核心算法设计描述；主控及功能模块层次结构；主要功

4、能模块的输入、处理(算法框架描述)和输出；功能模块之间的调用与被调用关系等。测试测试：测试范例，测试结果，测试结果的分析与讨论，测试过程中遇到的主要问题及所采用的解决措施。使用说明和作业小结使用说明和作业小结：使用说明主要描述如何使用你的程序以及使用时的主要事项；在小结中说明程序的改进思想、经验和体会，并回答教师布置的讨论题。打印一份程序清单及运行示例的结果打印一份程序清单及运行示例的结果。将以上各项文字材料及程序清单等装订成册，形成一个完整的报告。第二部分第二部分 实验指导书实验指导书实实 验验 一一题目：迷宫最短路径题目：迷宫最短路径问题描述问题描述从一个迷宫的入口到出口找出一条最短路经。

5、用一个二维数组 MAZE(1：m，1：n)模拟迷宫，数组元素为 0 表示该位置可以通过，数组元素为 1 表示该位置不可以通行。MAZE(1，1)和 MAZE(m，n)分别为迷宫的入口和出口。基本要求基本要求(1)输入数据a.输入迷宫的大小 m 行和 n 列，两者为整数b.由随机数产生 0 或 1，建立迷宫。(2)输出数据首先输出模拟迷宫的二维数组，若存在最短路经，则由出口回朔到入口打印这一条路径，如下所示：(m，n)，(I，j)，(1，1)如无通道，则打印：THERE IS NO PATH.实现提示实现提示(1)数据结构a）为了在程序中判断方便，把迷宫扩展成为 MAZE(0：m+1，0：n+1

6、)，扩展部分的元素设置为 1，相当于在迷宫周围布上一圈不准通过的墙，这样，在迷宫的任一位置(I，j)上都有八个可以移动的方向。b）用二维数组 MOVE(1：8，1：2)存放八个方向上的位置量，如图所示：(I+MOVE1，1，j+MOVE1，2)(I+MOVE8，1，j+MOVE8，2)(I+MOVE1，1，j+MOVE1，2)(I+MOVE7，1，j+MOVE7，2)(I+MOVE3，1，j+MOVE3，2)(I+MOVE6，1，j+MOVE6，2)(I+MOVE4，1，j+MOVE4，2)(I+MOVE5，1，j+MOVE5，2)MOVE 的设置情况的设置情况Ij121-102-113014

7、1151061-170-18-1-1c)为了标志已经通过的位置，采用一个标志数组 MARK（1.m，1.n）初值为 0，在寻找路径的过程中，若通过了位置（I，j），则将 MARK（I，J）置为为 1。d)为了记录查找过程中到达位置及其前一位置，建立一个 Q（1.m*n-1，0.2）数组，对于某一个数组元素 Q(P)，其中，Q(P，0)和 Q(P，1)记下到达位置 I和 j，Q(P，2)记下其出发点在 Q 数组中的下标。（2）算法基本思想）算法基本思想将入口（1，1）作为第一个出发点，依次在八个反方向上搜索可通行的位置，形成第一层新的出发点，然后对第一层中各个位置分别搜索他所在八个方向上的可通行

8、位置，形成第二层新的出发点，如此进行下去，直至达到出口(m，n)或者迷宫所有位置都搜索完毕为止。具体实施：从(m，n)开始，将其记入 Q 数组，比如记入 Q(1)，以它作为第一个出发点，依次对八个方向进行搜索，若下一个位置(I，j)可通行并且尚未经过（即 MAZE(I，j)=0 且 MARK(I，j)=0），则记入 Q 数组，如记在 Q(P)，则在 Q(P，2)中要记下其出发点在Q数组中的下标 1，在八个方向上都搜索过以后，根据先进先出的原则 Q 从数组中重新取出一个位置作为新的出发点（这里，我们实际上把 Q 数组作为一个顺序表示的队列），重复以上过程，若能达到位置(m，n)，表示找到最短路径

9、；若 Q 数组中已经没有位置可以作为新的出发点了，则表示迷宫没有通路。实实 验验 二二题目：编制用静态链表实现对题目：编制用静态链表实现对 k 个共享空间的栈进行各种操作的算法。个共享空间的栈进行各种操作的算法。实验提示实验提示：用静态链表来实现，结构定义如下：CONST maxsize=最大单元数；K=堆栈的个数；TYPE node=RECORDdata：elemtp；next：0.maxsizeEND；VAR s：ARRAY1.maxsize OF node；Top：ARRAY1.K OF 0.maxsize；Sp：0.maxsize；初始状态，将数组 s 构成一个静态链表，即用 next

10、 域将 1 单元到 maxsize 单元连起来，将 s 看成为一个空闲单元栈，栈顶指针为 sp，初始状态 sp=1；每个堆栈的栈顶指针初值为零，即 topI=0，I=1，2，3，k。当对第 I 个栈进行压栈时，先看空闲单元栈是否为空，也即 sp 是否为 0，如果 sp 为 0，则无空闲单元，产生上溢，否则，从空闲单元栈中分配一个单元给第 I 个栈，该单元作为第 I个栈的新的栈顶；当对第 I 个栈进行弹栈操作时，若 topI=0，则产生下溢，否则，从第 I 个栈顶弹掉一个元素，并将空间释放到空闲单元堆栈中（空间的回收）。其它对堆栈的操作类似可以实现。思考题思考题：如果采用动态链接结构实现堆栈，则

11、对堆栈的压栈和弹栈操作有何特点，何时发生溢出，并比较这两种方法的各自特点。实实 验验 三三题目：模拟旅馆管理系统的一个功能题目：模拟旅馆管理系统的一个功能床位的分配与回收床位的分配与回收 问题描述：问题描述：某旅馆有 n 个等级的房间，第 I 等级有ia个房间，每个等级有ib个床位（1In）。试模拟旅馆管理系统中床位分配和回收的功能，设计能为单个旅客分配床位，在其离店便回收床位（供下次分配）的算法。基本要求基本要求（1）输入数据分配时，输入旅客姓名、年龄、性别、到达日期和所需房间等级。回收时，输入房间等级、房间号和床位号。（2）输出数据分配成功时打印旅客姓名、年龄、到达日期、房间等级、房间号码

12、和床位号码。分配不成功时，如所有等级均无床位，则打印“客满”信息；如旅客需要的等级均无空床位，则打印“是否愿意更换等级？”的询问信息。若旅客愿意更换，则重新输入有关信息，再进行分配，否则分配工作结束。实现提示实现提示（1）数据结构主要采用顺序结构链接结构的线性表及堆栈。a)每个房间用一个如下所示的具有五个字段的结点（房结点）表示：性别房间号现有空床数BTOPRLINK其中，性别：0 表示房间为空状态1 表示房间分配给女旅客2 表示房间分配给男旅客现有空床数：数据在 0ib之间，其中ib是第 I 等级一个房间 的床位数，当现有空床数为ib时，表示房间为空；为 0 时，表示房间满。RLINK：当房

13、间空时，用作空房栈的连接；当房间不空时，指向下一个房结点。BTOP：指向该房间的空床号栈栈顶。一个房间对应一个顺序表示的空床号栈。栈的容量为ib，栈中存放空床号。分配时，从栈顶取出空床号，栈顶下移（BTOP=BTOP+1）；回收时，栈顶上移（BTOP=BTOP-1），将回收的空床号填入栈顶。b)每一个等级中的空房间构成一个空房栈；已住旅客的房间构成一个链栈（简称房链），其头结点结构如下：可分配女床位总数可分配男床位总数iaibTTOPRLINK其中：ia：第 I 等级中房间总数ib第 I 等级中每个房间的床位数可分配男、女床位的总数的初值等于ia*ib，因为开始时所有房间和床位既可以分配给男旅

14、客，也可以分配给女旅客。当在房链中分配一个床位给男（女）旅客，床位总数应减 1；当从空房栈中取出一个房间作为男（女）旅客房间时，则可分配女（男）床位总数应减ib，当回收一个男（女）床位时，则可分配男（女）床位总数应加 1；当回收一个男（女）空房至空房栈时，则可分配女（男）床位总数应加ib。TTOP：指向本级空房栈栈顶，当无空房间时，TTOP=（NIL）。RLINK：指向本级房链第一个顶点，当房链为空时，RLINK=(NIL)c)顺序表 s=(missss,.,.,10)，其中，nss 1顺序存放第 1n 等级房间的头结点；0s存放内容如下所示：全店可分配女床总数全店可分配女床总数00初始时，全

15、店可分配男、女床总数相同，均为iiiba*，在分配或回收时，对各等级可分配男（女）床位总数处理的同时也要对全店可分配男（女）床总数作相应处理，当全店可分配男（女）床总数等于零时，表示客满。（2）算法设计思想）算法设计思想（略）实实 验验四四题目：串编辑题目：串编辑问题描述问题描述：本题目中的串编辑要求对串实现以下三种功能：插入：把一个字符串插入到给定串的指定位置删除：将串中某指定位置开始的若干字符从串中删除置换：用一串字符置换给定串中某指定位置开始的若干字符基本要求基本要求 输入要求：首先输入功能标志符，表明要求实现何种功能，然后再输入有关数据1输入 I，表示要求输入；然后输入插入的起始位置和

16、要插入的字符串2输入 D，表示要求删除；然后输入删除的起始位置和删除长度3输入 R，表示要求置换；然后输入置换的起始位置、置换长度和将要换入的字符串4输入 E，结束串编辑。输出数据：功能不同输出的数据不同，主要有以下几种数据：功能标志符、起始位置、删除长度、插入或置换的字符串和经过运算后的字符串。实现提示实现提示 数据结构1结点结构：一个结点由 DATA 和 LINK 两个字段组成，如下所示：DATALINK在 DATA 字段中存放一个字符2字符串结构：用一个单循环链表表示一个字符串，如，T=ABCD串可以由下面的单链循环表来表示：TT 指向循环链表的表尾。插入或置换子串的结构：用一个单链表表

17、示要插入的子串，tp 为头指阵，bn为尾指针，如：tpbn算法基本思想：算法开始时给出一个空串，用户可以在此基础上进行编辑。a）插入输入插入起始位置构造插入子串实现插入打印输出插入后的子串b)删除输出删除起始位置和删除长度实现删除打印输出删除后的字符串c）置换输入置项起始位置和被置换长度（类似删除长度）构造被置换子串（类似插入子串）调用删除过程，删除被置换的字符调用插入过程，插入置换子串d）结束串编辑，终止编辑过程实实验验五五题目：交通问题系统题目：交通问题系统问题描述：问题描述：已知某市每条公共路线及沿途所经站名，试设计一个问路程序，用户可以在任一车站通过终端询问知道：是否有公共汽车到达指定

18、的目的地?若有，告诉乘车路线。如需中途换车，应指示再那里换车基本要求：(1)数据结构：将公共汽车路线图看成是一个有向图，选择合适的数据结构，除了反映顶点(站)之间的邻接关系外，还应反映途经的路线号。注意，两站之间可能存在往返两个方向，每个方向又可能对应多个路线号。(2)算法：按选定的数据结构设计相应的算法。注意，当从乘车站到目的站存在多种乘车路线时，必须确定路线选取标准。例如，要求换车次数最少等。数据结构可以采用链接结构：typestptr=node；node=recordstname：string；link：stptrend；hdtp=array1.max of node；varhead：h

19、dtp；A数据结构也可以采用顺序结构：typenode=recordgo，back：integerend；goback=array 1.max，1.max ofnode；vara：goback；其中，aI，j.go0 表示第 i条线路上，向站 j 去方向的下一站号；ai，j.back0 表示第 i 条线路 上，站 j 回来的下一站号。若站 j 不在第 i 条线路上，ai，j.go 和 ai，j.back 均为 0。另外，还需建立两个数组；一个是线路序号和线路号“值”的对照表；另一个是站号和站名对照表。(3)对所采用的算法进行算法分析 实现提示实现提示(1)假定顶点编号为 1.n，数据结构采用连

20、接结构。设置表头数组为 head1.n，headi包含站 i的名字和一指针，该指针指向 i 的所有邻接顶点组成的单链表。单链表中的每个结点包含 3 个域：一个站号域，两个指针域。一个指针指向 i 的下一个邻接顶点，另一个指针指向从 i到该结点的所有线路号组成的链表。Typelineptr=linenodeLinenode=recordLineno：integer；Next：lineptrEnd；Stnode=recordStno：integer；Link1：stptr；Link2：lineptrEnd；(2)如果按途经站数最少的原则来确定乘车路线，实际上是最短路径问题，则可以采用 Djkstr

21、a 算法或图的宽度优先搜索算法。在保证站数最少的前提下，如果存在多种乘车路线，则可以进一步挑选换车次数最少的路线。实实验验六六题目：查找、排序算法效率的实验分析题目：查找、排序算法效率的实验分析1、问题描述：问题描述：各种查找、内排序算法的时间复杂度分析是从理论上给出了算法执行时间关于数据个数n 的阶。现通过随机输入多组不同个数的数据，对各种算法的关键字比较次数、移动次数及执行时间进行比较，以求得实验理论。2、基本要求基本要求（1）随机产生 n=100，200，300，1000，2000 个整数并存于数组 A1.n中。对主要查找算法（顺序查找、插入排序、归并排序、堆排序、快速排序）进行实验比较

22、，计算出平均比较次数nc、平均移动次数nm及执行时间nt。nc、nm由程序自动计算，nt由手工计时。（2）对实验结果数据进行对比分析3、实验提示实验提示（1）设计一个驱动程序，其任务是：随机输入一组原始数据 A1.n，对于查找还需准备一个键码值（可以随机产生，也可在 A1.n中按索引号挑选若干有代表性的数据）；对每组原始数据，分别调用查找或排序算法过程。（2）为了自动计算nc、nm需要在每个算法过程中的适当位置插入计数操作。（3）手工计算每个算法的执行时间nt时，为了减少计时误差，删除所插入的计数操作，并按 n 的大小确定一个 K，对每个查找或排序算法过程反复调用 K次，在调用开始前设置一个计时起点，在 K 次调用执行后可打印信息，作为计时的终点1t，则（1t-0t）/K 便是算法的大致执行时间。软件教研室1996 年 6月