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

2019-03-10 18:02

⑵ 若有,告诉乘车路线。如需中途换车,应指示再那里换车

基本要求:

(1) 数据结构: 将公共汽车路线图看成是一个有向图,选择合适的数据结构,

除了反映顶点(站)之间的邻接关系外,还应反映途经的路线号。注意,两站之间可能存在往返两个方向,每个方向又可能对应多个路线号。

(2) 算法: 按选定的数据结构设计相应的算法。注意,当从乘车站到目的站存

在多种乘车路线时,必须确定路线选取标准。例如,要求换车次数最少等。 数据结构可以采用链接结构:

struct NODE {

char* stname; struct NODE* link; };

struct NODE hdtp[MAX+1];

数据结构也可以采用顺序结构:

struct NODE{ int go,back; };

struct NODE a[max+1,max+1];

其中,a[I,j].go>0 表示第i条线路上,向站j 去方向的下一站号;a[i,j].back>0表示第i条线路 上,站j回来的下一站号。若站j不在第i条线路上,a[i,j].go 和 a[i,j].back 均为0。

另外,还需建立两个数组;一个是线路序号和线路号“值”的对照

表;另一个是站号和站名对照表。 (3)

对所采用的算法进行算法分析

2. 实现提示

(1) 假定顶点编号为1..n,数据结构采用连接结构。设置表头数组为head[1..n],head[i]包含站i的名字和一指针,该指针指向i的所有邻接顶点组成的单链表。单链表中的每个结点包含3个域:一个站号域,两个指针域。一个指针指向i的下一个邻接顶点,另一个指针指向从i到该结点的所有线路号组成的链表。

struct LINENODE {

int lineno;

struct LINENODE* next; };

31

struct STNODE { int stno;

struct LINENODE* Link1,*Link2; };

(2) 如果按途经站数最少的原则来确定乘车路线,实际上是最短路径问题,则可以采用Djkstra算法或图的宽度优先搜索算法。在保证站数最少的前提下,如果存在多种乘车路线,则可以进一步挑选换车次数最少的路线。

实 验 八 医院选址问题

题目:医院选址问题

1.问题描述

n个村庄之间的交通图可以用有向网图来表示,图中边

2.基本要求

(1)建立模型,设计存储结构; (2)设计算法完成问题求解; (3)分析算法的时间复杂度。 3.设计思想

医院选址问题实际是求有向图中心点的问题。首先定义顶点的偏心度。

设图G=(V,E),对任一顶点k,称E(k)=max{d(i,k)}(i∈V)为顶点k的偏心度。显然,偏心度最小的顶点即为图G的中心点。

如图 (a)所示是一个带权有向图,其各顶点的偏心度如图(b)所示。

图 带权有向图及各顶点的偏心度

医院选址问题的算法用伪代码描述如下:

32

1.对加权有向图,调用Floyd算法,求每对顶点间最短路径长度的矩阵; 2.对最短路径长度矩阵的每列求大值,即得到各顶点的偏心度; 3.具有最小偏心度的顶点即为所求。

【思考题】图的存储结构和算法的设计需要一定的灵活性和技巧。从医院选址问题 的求解过程,你有什么感想?

实 验 九 查找、排序算法效率的实验分析

题目:查找、排序算法效率的实验分析

1.问题描述:

各种查找、内排序算法的时间复杂度分析是从理论上给出了算法执行时间关于数据个数n的阶。现通过随机输入多组不同个数的数据,对各种算法的关键字比较次数、移动次数及执行时间进行比较,以求得实验理论。

2.基本要求

(1)随机产生n=100,200,300,1000,2000个整数并存于数组A[1..n]中。对主要查

找算法(顺序查找、插入排序、归并排序、堆排序、快速排序)进行实验比较,计算出平均比较次数cn、平均移动次数mn及执行时间tn。cn、mn由程序自动计算,tn由手工计时。 (2)对实验结果数据进行对比分析 3.实验提示

(1)设计一个驱动程序,其任务是:随机输入一组原始数据A[1..n],对于查找还需准备一个键码值(可以随机产生,也可在A[1..n]中按索引号挑选若干有代表性的数据);

对每组原始数据,分别调用查找或排序算法过程。

(2)为了自动计算cn、mn需要在每个算法过程中的适当位置插入计数操作。 手工计算每个算法的执行时间tn时,为了减少计时误差,删除所插入的计数操作,并按n的大小确定一个K,对每个查找或排序算法过程反复调用K次,在调用开始前设置一个计时起点,在K次调用执行后可打印信息,作为计时的终点t1,则(t1-t0)/K便是算法的大致执行时间。

实 验 十 简单个人电话号码查询系统

题目:简单个人电话号码查询系统

33

1.问题描述

人们在日常生活中经常要查找某个人或某个单位的电话号码,本实验将实现一个简

(a)直方图的表格形式(b)直方图的图形形式

图 求直方图示例

单的个人电话号码查询系统,根据用户输人的信息(例如姓名等)进行快速查询。

2.基本要求

(1)在外存上,用文件保存电话号码信息; (2)在内存中,设计数据结构存储电话号码信息; (3)提供查询功能:根据姓名实现快速查询; (4)提供其他维护功能,例如插人、删除、修改等。 3.设计思想

由于要管理的电话号码信息较多,而且要在程序运行结束后仍然保存电话号码信息,所以电话号码信息采用文件的形式存放到外存中。在系统运行时,要将电话号码信息从文件调人内存来进行查找等操作,为了接收文件中的内容,要有一个数据结构与之对应,可以设计如下结构类型的数组来接收数据: const int max=10; struct TeleNumber {

string name; //姓名

string phoneNumber; //固定电话号码 string mobileNumber; //移动电话号码 string email; //电子邮箱 }Tele[max];

为了实现对电话号码的快速查询,可以将上述结构数组排序,以便应用折半查找,但是,在数组中实现插人和删除操作的代价较高。如果记录须频繁进行插人或删除操作,可以考虑采用二叉排序树组织电话号码信息,则查找和维护都能获得较高的时间性能。更复

34

杂地,须考虑该二叉排序树是否平衡,如何使之达到平衡。有关折半查找和二叉排序树的具体算法请参见主教材相关内容。

实 验 十一 各种排序算法时间性能的比较

题目:各种排序算法时间性能的比较

1.问题描述

对本章的各种排序方法(直接插人排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和归并排序)的时间性能进行比较。

2.基本要求

(1)设计并实现上述各种排序算法,

(2)产生正序和逆序的初始排列分别调用上述排序算法,并比较时间性能; (3)产生随机的初始排列分别调用上述排序算法,并比较时间性能。 3.设计思想

上述各种排序方法都是基于比较的内排序,其时间主要消耗在排序过程中进行的记录的比较和移动,因此,统计在相同数据状态下不同排序算法的比较次数和移动次数,即可实现比较各种排序算法的目的。

直接插人排序、起泡排序、直接选择排序在10.2~10.4节中已经实现,请仿照相关部分中的方法在其他排序算法中的适当位置插人计数器统计记录的比较次数和移动次数。

思考题:如果测算每种排序算法所用的实际时间,应如何修改排序算法?

实 验 十二 机器调度问题

题目:机器调度问题

1.问题描述

机器调度是指有m台机器要处理n个作业,设作业i的处理时间为ti,则对n个作业进行机器分配,使得:

(1)一台机器在同一时间内只能处理一个作业; (2)一个作业不能同时在两台机器上处理; (3)作业i一旦运行,则需要ti个连续时间单位。

设计算法进行合理调度,使得在m台机器上处理n个作业所需要的处理时间最短。 2.基本要求

(1)建立问题模型,设计数据结构;

35


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

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

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

马上注册会员

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