课程设计参考题目_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
课程设计参考题目
上传于||暂无简介
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
你可能喜欢1076人阅读
算法 数据结构（38）
主要涉及无线网创建和单源最短路径问题
设计要求：设计平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。
基本要求：
1）设计校园平面图，在校园景点选10个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。
2）为来访客人提供图中任意景点相关信息的查询。
3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。
实现提示：一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均含有相关信息。
#include &stdio.h&
#include &stdlib.h&
#define OK 1
#define ERROR -1
#define OVERFLOW 0
#define MAXVER 20
//定义最大定点数
#define MAXINT 200
#define NULL 0
typedef char verT
//定义顶点类型
typedef struct ver
//关于景点(顶点)信息存放（结构体数组）
char name[20];
//存放景点名称
//存放景点代号
char intro[20];
//景点简介
}Ver[MAXVER];
typedef struct
//无向网存放景区信息
//定义顶点
int arcs[MAXVER][MAXVER]; //定义弧
int vernum,
//定义最大顶点数 和弧
int locate(MGraph G,verType ch) //查找顶点在数组中的下标
for(i=0;i&G.vernum&&ch!=G.verx[i].i++);
status createUDN(MGraph &G,int &v)
//创建无向网
int i,j,w,k;
verType ch1,ch2;
printf(&请输入场所的个数和路径数：格式如2 3\n&);
scanf(&%d%d&,&G.vernum,&G.arcsnum);
fflush(stdin);
printf(&请输入顶点信息\n&);
for(i=0;i&G.i++)
printf(&\n请输入第%d个景点名称:\n&,i+1);
scanf(&%s&,&G.verx[i].name);
fflush(stdin);
printf(&请输入景点代号，用一个字符表示如A\n&);
scanf(&%c&,&G.verx[i].mask);
fflush(stdin);
printf(&请对景点简单介绍\n&);
scanf(&%s&,&G.verx[i].intro);
fflush(stdin);
for(i=0;i&G.i++)
for(j=0;j&G.j++)
G.arcs[i][j]=MAXINT;
//赋初值为无穷大
printf(&请输入场所间距离：格式A B 3\\n \n&);
for(i=0;i&G.i++)
printf(&请输入第%d对值\n&,i+1);
scanf(&%c %c %d&,&ch1,&ch2,&w);
//输入顶点符号和权值
fflush(stdin);
k=locate(G,ch1);
//获得顶点下标
j=locate(G,ch2);
G.arcs[k][j]=w;
//为临界矩阵赋值
G.arcs[j][k]=G.arcs[k][j];
//无向图为对称矩阵
return OK;
void message(MGraph G)
//进行信息查询
printf(&请输入要查询景点代号如A\n&);
scanf(&%c&,&mask);
fflush(stdin);
for(int i=0;i&G.i++)
if(mask==G.verx[i].mask)
printf(&景点名称：%s\n景点简介：%s&,G.verx[i].name,G.verx[i].intro);
int search(MGraph G)
//进行最短路径查询
char value1,value2;
//存放两个值得下标
int all=0;
//记录经过点的个数
int lujing[MAXINT][MAXINT];
//用来 记录路径
for (int m=0;m&MAXINT;m++)
for (int n=0;n&MAXINT;n++)
lujing[m][n]=NULL;
int D[MAXVER],P[MAXVER],
bool final[MAXVER];
printf(&\n请输入两个场所值求其最短距离和路径 如A B\n&);
scanf(&%c %c&,&value1,&value2);
i=locate(G,value1);
//获得第一个顶点下标
j=locate(G,value2);
//获取第二个顶点下标
for(int v=0;v&G.++v)
//初始化工作
//从起始点到另外点均未找到最短路径 主要是定义一个集合将访问过的点设置值为true
刚开始集合为空
D[v]=G.arcs[i][v];
//从其余点到起始点距离(记录是最短距离
D[i]=0;final[i]=
//起始点到起始点距离为0 起始点设置为已经访问过
P[sub]=-1;
for(int out=1;out&G.out++)
//最多扩充n-1个点到已经访问过的点集
min=MAXINT;
for(int w=0;w&G.w++)
// 在当前未选择点集中选估计距离最小的顶点k
if(!final[w])
if(D[w]&min) { q=w; min=D[w]; }
//将最小距离点加入到已经访问过点集中
for( w=0;lujing[q][w]!=NULL;w++){}
lujing[q][w]=q;
for(int m=0;m&G.m++)
//调整剩余点到起始点的估计距离
if(!final[m]&&(min+G.arcs[q][m]&D[m]))
D[m]=min+G.arcs[q][m];sub=q;
for( w=0;lujing[q][w]!=NULL ;w++)
lujing[m][w]=lujing[q][w];
for(;lujing[m][w]!=NULL;w++)
lujing[m][w]=NULL;
printf(&最短路径为%d\n&,D[j]);
printf(&依次经过景区为:&);
printf(&%c
&,value1);
for (int c=0;lujing[j][c]!=NULL;c++)
printf(&%c
&,G.verx[lujing[j][c]].mask);
int main()
printf(&请先输入建立校园图所需要的信息：\n\n&);
if(createUDN(G,v))
//创建无向网
printf(&\n\n查询某个景点信息请输入1\n&);
printf(&查询两个景点之间最短距离请输入2\n&);
printf(&退出请输入0\n&);
scanf(&%d&,&alter);
fflush(stdin);
switch(alter)
case 0:return 0;
case 1: message(G);
case 2:search(G);
}while(alter);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：174715次
积分：3637
积分：3637
排名：第5708名
原创：200篇
转载：13篇
评论：45条
(1)(4)(1)(2)(11)(38)(29)(29)(7)(1)(1)(10)(15)(14)(3)(4)(8)(7)(1)(18)(7)君，已阅读到文档的结尾了呢~~
校园导航问题问题,校园导航,校..
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
校园导航问题
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口}