数据结构实验指导书(5)

2019-03-10 18:02

}

思考题:如何求广度优先生成树?

实 验 四 顺序查找与折半查找的性能比较

题目:顺序查找与折半查找的性能比较

1问题描述

对于给定的线性表要求用顺序查找和折半查找两种方法进行查找,并进行性能比较. 2基本要求

(1)对于有序数组,修改9.1.1节中的顺序查找算法,利用数组的有序性提高查找性能;

(2)将9.1.1节中的顺序查找算法和你设计的改进算法进行比较;

(3)对于同样的数组元素,同样的待查值,将顺序查找算法和折平查找算法进行比较; (4)总结实验结果,给出不同算法进行比较的具体结论. 3.设计思想

对于给定的数组采用顺序查找时,查找失败的平均查找长度为O (n)。但对有序数组进行顺序查找,可减少查找失败的平均查找长度,因为不须遍历整个表就能确定表中不存在要查找的记录。具休算法如下:

改进的顺序查找算法

int SeqSearch2(int r[ ], int n, int k) {

r[ 0 ]=k; count =0; i=n;

while ( ++count && r[ i ]>= k) i--;

cout<<“比较的次数是:”<

对于有序数组中的前半部分、中部、后半部分三个位置的数组元素,采用验证实验所设计的顺序查找和折半查找的算法以及上述改进的顺序查找算法,比较三种方法的时间性能(即待查值与数组元素的比较次数)。

思考题:可以有多种方法提高顺序查找的时间性能,例如将数组元素按访问频度递减的顺序存放,请设计并实现一种改进的顺序查找算法。

21

2.3综合性实验

实 验 一 约瑟夫环问题

题目:约瑟夫环问题

1.问题描述

设有编号为1,2,?n的n(n>0)个人围成一个圈.每个人持有个密码m。从第1个人开始报数,报到m时停止报数,报m的人出圈,再从他的下个人起重新报数,报到m时停止报数,报m的出圈??如此下去,直到所有人全部出圈为止。当任意给定n和m后,设计算法求n个人出圈的次序。

2.基本要求

(1)建立模型,确定存储结构

(2)对任意n个人,密码为m,实现约瑟夫环问题 (3)出圈的顺序可以依次输出,也可以用一个数组存储 3.设计思想

首先,设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质,考虑采用循环链表,为了统一对表中任意结点的操作,循环链表不带头结点。将循环链表的结点定义为如下结构类型:

struct Node {

int data; //编号 Node * next; };

其次,建立一个不带头结点的循环链表并由头指针first指示。具体算法请参见2.3.2节自行设计。

最后,设计约瑟夫环问题的算法。下面给出伪代码描述,操作示意如图所示。 伪代码:

1.工作指针pre和p初始化,计数器count初始化;

pre=first; p=first->next; count=2; //为便于删除操作,从2开始计数 2.循环直到p=pre 2.1如果count=m,则 2.1.1输出结点p; 2.1.2删除结点p;

22

2.1.3计数器count清零,重新开始计数; 2.2否则,执行

2.2.1工作指针pre和p后移; 2.2.2计数器增1;

3.退出循环,链表中只剩下一个结点p,输出结点p后将结点p删除;

(a) 一般情况

(b)只剩下一个结点的特殊情况 图 约瑟夫环问题存储示意图

思考题:

(1)采用顺序存储结构如何实现约瑟夫环问题?

(2)如果每个人持有的密码不同,应如何实现约瑟夫环问题?

实 验 二 迷宫最短路径

题目:迷宫最短路径

⒈问题描述

从一个迷宫的入口到出口找出一条最短路经。用一个二维数组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)

23

如无通道,则打印: THERE IS NO PATH. ⒊实现提示 (1) 数据结构

a)为了在程序中判断方便,把迷宫扩展成为MAZE(0..m+1,0..n+1),扩展部分的元素设置为1,相当于在迷宫周围布上一圈不准通过的墙,这样,在迷宫的任一位置(I,j)上都有八个可以移动的方向。

b)用二维数组MOVE(1..8,1..2)存放八个方向上的位置量,如图所示:

(i+MOVE[1,1], j+MOVE[1,2])

,1], j+MOVE[8,2]) (i+MOVE[1,1], j+MOVE[1,2])

,1], j+MOVE[7,2]) (i+MOVE[3,1], j+MOVE[3,2])

,1], j+MOVE[6,2]) (i+MOVE[4,1], j+MOVE[4,2])

,1], j+MOVE[5,2])

24

(i+MOVE[8 (i+MOVE[7 (i+MOVE[6 (i+MOVE[5 MOVE的设置情况 i j 1 2 3 4 5 6 7 8 -1 -1 0 1 1 1 0 -1 1 0 1 1 1 0 -1 -1 -1 2 c) 为了标志已经通过的位置,采用一个标志数组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)作为第一个出发点,依次在八个反方向上搜索可通行的位置,形成第一层新的出发点,然后对第一层中各个位置分别搜索他所在八个方向上的可通行位置,形成第二层新的出发点,?,如此进行下去,直至达到出口(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),表示找到最短路径;若Q数组中已经没有位置可以作为新的出发点了,则表示迷宫没有通路。

实 验 三 静态链表实现对k个共享空间的栈进行操作的算法

题目:编制用静态链表实现对k个共享空间的栈进行各种操作的算法。

25


数据结构实验指导书(5).doc 将本文的Word文档下载到电脑 下载失败或者文档不完整,请联系客服人员解决!

下一篇:五年级下册劳动全册教案

相关阅读
本类排行
× 注册会员免费下载(下载后可以自由复制和排版)

马上注册会员

注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: