没有合适的资源?快使用搜索试试~ 我知道了~
校园导游系统数据结构图.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 201 浏览量
2023-10-18
22:34:59
上传
评论
收藏 1.66MB PDF 举报
温馨提示
试读
30页
校园导游系统数据结构图.pdf
资源推荐
资源详情
资源评论
西安郵電學院
数据结构实验报告
题 目:
统 游 系校 园 导
院学 算 机 院系名称: 计
计算机科学与技术专
业名称:
1006 级:班
****
学生姓名:
***** 位)8:学号(
******
指导教师:
设计起止时间:
年日月年 20111212~20111216 日月
一. 题目要求
1、设计学校的校园平面图,
地点(地点名称、地点介绍)不少于 10 个。
2、提供图中任意地点相关信息的查询。 3、提供图中任意地点的问路查询: 1)任意两
个地点之间的一条最短(中转最少)的简单路径; 2)任意两个景点的最佳访问路线(带权)
查询;
3)任意两个地点之间的所有路径。 4、地点和道路的扩充以及撤销; 地点基本信息的
文件存储。(附加:加分题)
二.概要设计
1.功能模块的调用关系图
创建图
查看景点简介 景点查询
开始主循
环,每次求得到某个顶点的最短路径,并放入 p[][]中
min = INFINITY//当前所知的最短距离,设初值为
INFINITY/ !final[w]&&(min+G->arcs[v][w].adj<D[w])
一直往下找 min=p[][]
v[k+1]=s
visited[s]=1
输出路径 结束
主函数
任意两景点间 任意两景点间 最佳路径(路最短路径(中程最短)
转最少)
任意两景点间所有路径
保存景点
开始
G->arcs[v[k]][s].adj!=INFINITY&&visited[s]==0
否
v[k]==j
.2
各个模块详细的功能描述。
函数来选择用户所要进行的函数,输出欢迎界面,然后调用 showmenu()
首先,main()函数调用 loge()1.函数就是一个菜单供使用者来选择他所要进行的相关操作,比如信息的查询,最短
showmenu()操作。其中 路径查询之类。 函数,用于输出校园平面图,给用户提供校园的景点分布状况,方便用户选择
景点参观。2.browser()函数,用于查询用户所选的景点信息,用户需要输入要查询的景点编号,函数会对编号进行 3.Search()
判断,如果是合法输入,则在屏幕上输出该景点的相关信息,包括景点名字,景点的相关介绍,否则返回 重新输入。
函数,用于查询用户所选的任意两个景点间的所有路径,用户需要输入要查询的起始 4.SearchAllpath()景点编号,函数会
对编号进行判断,如果是合法输入,用户需要输入要查询的终点景点编号,函数会对编号进行判断,如果是合法输入,
则在屏幕上输出输查询的两个景点间的所有路径,否则返回重新输入。函 查找路径。数使用深度遍历 DeepFirstSeach()
函数,用于查询用户所选的任意两个景点间的最短路径,用户需要输入要查询的起始景点 5.Wellway().
编号,函数会对编号进行判断,如果是合法输入,用户需要输入要查询的终点景点编号,函数会对编号进行判断,如果
是合法输入,则在屏幕上输出输查询的两个景点间的最短路径,否则返回重新输入。函数的生成主体是迪杰斯特拉算法
来计算出起点到终点之间的最短路径。
6.minway()函数,用于查询用户所选的任意两个景点间的最佳路径(即中转最少),用户需要输入要查询的起始景点编号,
函数会对编号进行判断,如果是合法输入,用户需要输入要查询的终点景点编号,函数会对编号进行判断,如果是合法
输入,则在屏幕上输出输查询的两个景点间的最短路径,否则返回重新输入。
7. CreatUDN()函数,创建的图,它是 MGraph 型,G->vexnum 表示顶点的个数;G->arcnum 表示边数。CreatUDN()函数
的功能就是实现图的创建,将已知的景点的一些信息,转换成图的信息,并进行存储。
三.详细设计(主要函数的程序流程图)
1.任意两个地点之间的一条最短
(中转最少)的简单路径
利用遍历的思想,遍历图找出一条最佳最佳的的路径,让它遍历所有景点。往下遍历,访问标志
位,若访问过在下次就不用访问。若找完一个分支在下次重新遍历。
zz[0]->zhi=m;
zz[0]->front=NULL;
flag[m]=1;
for(top=0;top<20;top++)
{
for(i=0;i<20;i++)
{
if(G->arcs[zz[top]->zhi][i].adj!=INFINITY&&i==n)
{
printf(%s,G->vexs[n].name);
printf(%s,G->vexs[zz[top]->zhi].name);
zz[top]=zz[top]->front;
while(zz[top]!=NULL)
{
printf(%s,G->vexs[zz[top]->zhi].name);
zz[top]=zz[top]->front;
}
getch();
return;
}
else if(G->arcs[zz[top]->zhi][i].adj!=INFINITY&&flag[i]==0)
{
zz[++j]->zhi=i;
zz[j]->front=zz[top];
flag[i]=1;
}
}
}
开始
n
m,终点 输入起始点
if(G->arcs[zz[top]->zhi][i].a
dj!=INFINITY&&i==n)
i++
i<G->vexnu
结束
任意两个景点的最佳访问路线(带权)查询 2.
是用来存放各路径的权值,[][]v0 到其余顶点的最短路径 D[],p 利用迪杰特斯拉算法,求
for(v=0;v<G->vexnum;v++) )。标志,是否当前顶点属于 final(1,属于借助辅助数组 final[]{
final[v]=0;
D[v]=G->arcs[v0][v].adj;
for(w=0;w<G->vexnum;w++)
p[v][w]=0;
if(D[v]<INFINITY)
{
p[v][v0]=1;p[v][v]=1;
}
}
D[v0]=0;final[v0]=1;
for(i=1;i<G->vexnum;i++)
{
min=INFINITY;
for(w=0;w<G->vexnum;w++)
if(!final[w])
if(D[w]<min){v=w;min=D[w];}
final[v]=1;
for(w=0;w<G->vexnum;w++)
if(!final[w]&&(min+G->arcs[v][w].adj<D[w]))
{
D[w]=min+G->arcs[v][w].adj;
for(x=0;x<G->vexnum;x++)
p[w][x]=p[v][x];
p[w][w]=1;
}
}
v=v1;
w1=v0;
printf(%s,G->vexs[v0].name);
do
{
flag=0;min=INFINITY;
for(w=0;w<G->vexnum;w++)
{
if(p[v][w]&&w!=v0)
{
剩余29页未读,继续阅读
资源评论
hhappy0123456789
- 粉丝: 59
- 资源: 5万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功