文档库 最新最全的文档下载
当前位置:文档库 › 003课程设计源码

003课程设计源码

#include
#include
#include
#include
#define Max 20000
#define NUM 10 //景点个数

typedef struct ArcCell
{
int adj; //路径的权值
}ArcCell;

typedef struct VertexType
{
int number; //编号
char *sight; //景点名称
char *description;//景点信息描述
}VertexType;

typedef struct
{
VertexType vex[NUM];//图的顶点数
ArcCell arcs[NUM][NUM];//存放边的邻接矩阵
int vexnum,arcnum;//图的顶点总数,边数
}MGraph; //图的结构

MGraph G; //抽象数据类型图的电定义
int P[NUM][NUM]; //创建path存放两点间的最短路径的前驱结点
long int D[NUM]; //路径长度
int x[10]={0};//初始化推荐景点编号
void CreateUDN(int v,int a);//创建图
void narrate(); //景点信息描述界面
void ShortestPath(int num);//求最短路径
void output(int sight1,int sight2);//输出路径距离
char Menu(); //系统主界面
void search(); //分类查找景点编号
char SearchMenu(); //查找主界面
void HaMiTonian(int); //推荐景点分析
void NextValue(int); //推荐路径景点算法
void display();//输出最佳景点路径
int main()
{

int v0,v1;
char ck;
CreateUDN(NUM,11);
do
{
ck=Menu();
switch(ck)
{
case '1':
system("cls");
narrate();
printf("\n\n\t\t\t请选择起点景点(0~9):");
scanf("%d",&v0);
printf("\t\t\t请选择终点景点(0~9):");
scanf("%d",&v1);
ShortestPath(v0);
output(v0,v1);
printf("\n\n\t\t\t\t请按任意键继续...\n");
getchar();
getchar();
break;
case '2':search();
break;
case '3':
system("cls");
narrate();
x[0]=1;
HaMiTonian(1);
printf("\n\n\t\t\t\t请按任意键继续...\n");
getchar();
getchar();
break;
};
}while(ck!='0');
return 0;

}
//系统主界面
char Menu()
{
char c;
int flag;
do{
flag=1;
system("cls");
narrate();
printf("\n\t\t\t┏━━━━━━━━━━━━━━━┑\n");
printf("\t\t\t┃ ┃\n");
printf("\t\t\t┃ 1、查询景点路径 ┃\n");
printf("\t\t\t┃ 2、查询景点信息 ┃\n");
printf("\t\t\t┃ 3、推荐参观路线 ┃\n");
printf("\t\t\t┃ 0、退出 ┃\n");
printf("\t\t\t┃ ┃\n");
printf("\t\t\t┗━━━━━━━━━━━━━━━┛\n");
printf("\t\t\t\t请输入您的选择:");
scanf("%c",&c);
if(c=='1'||c=='2'||c=='3'||c=='0')
flag=0;
}while(flag);
return c;
}
//分类查找主界面
char SearchMenu()
{
char c;
int flag;
do{
flag=1;
system("cls");
narrate();
printf("\n\t\t\t┏━━━━━━━━━━━━━━━┑\n");
printf("\t\t\t┃ ┃\n");
printf("\t\t\t┃ 1、按照景点编号查询 ┃\n");

printf("\t\t\t┃ 2、按照景点名称查询 ┃\n");
printf("\t\t\t┃ 0、返回 ┃\n");
printf("\t\t\t┃ ┃\n");
printf("\t\t\t┗━━━━━━━━━━━━━━━┛\n");
printf("\t\t\t\t请输入您的选择:");
scanf("%c",&c);
if(c=='1'||c=='2'||c=='0')
flag=0;
}while(flag);
return c;
}
//查找景点编号
void search()
{
int num;
int i;
char c;
char name[20];

do
{
system("cls");
c=SearchMenu();
switch (c)
{
case '1':
system("cls");
narrate();
printf("\n\n\t\t请输入您要查找的景点编号:");
scanf("%d",&num);
for(i=0;i{
if(num==G.vex[i].number)
{
printf("\n\n\t\t\t您要查找景点信息如下:");
printf("\n\n\t\t\t%-25s\n\n",G.vex[i].description);
printf("\n\t\t\t按任意键返回...");
getchar();
getchar();
break;
}
}
if(i==NUM)
{
printf("\n\n\t\t\t没有找到!");
printf("\n\n\t\t\t按任意键返回...");
getchar();
getchar();
}

break;
case '2':
narrate();
system("cls");
printf("\n\n\t\t请输入您要查找的景点名称:");
scanf("%s",name);
for(i=0;i{
if(!strcmp(name,G.vex[i].sight))
{
printf("\n\n\t\t\t您要查找景点信息如下:");
printf("\n\n\t\t\t%-25s\n\n",G.vex[i].description);
printf("\n\t\t\t按任意键返回...");
getchar();
getchar();
break;
}
}
if(i==NUM)
{
printf("\n\n\t\t\t没有找到!");
printf("\n\n\t\t\t按任意键返回...");
getchar();
getchar();
}
break;
}
}while(c!='0');
}
//创建图
void CreateUDN(int v,int a)
{
int i,j;
G.vexnum=v;
G.arcnum=a;
for(i=0;iG.vex[i].number=i;

G.vex[0].sight="行政楼";
G.vex[0].description="学校领导,办公室之地。";
G.vex[1].sight="校大礼堂";
G.vex[1].description="业余活动,举办各种晚会。";
G.vex[2].sight="第一教学楼";
G.vex[2].description="教室,自习上课室";
G.vex[3].sight="第五教学楼";
G.vex[3].description="教室,自习上课室";
G.vex[4].sight="逸夫图书馆";
G.vex[4].description="阅览室,借阅图书";
G.vex[5].sight="南区食堂";
G.vex[5].description="餐饮休闲";
G.vex[6].sight="北区食堂";
G.vex[6].description="餐饮休闲";
G.vex[7].sight="南区田径场";
G.vex[7].description="运动比赛娱乐";
G.vex[8].sight="第二教学楼";
G.vex[8].description="教室,自习上课室";
G.vex[9].sight="高级餐馆稻蕙楼";
G.vex[9].description="餐饮休闲娱乐";


for(i=0;ifor(j=0;jG.arcs[i][j].adj=Max;
G.arcs[0][1].adj=G.arcs[1][0].adj=1209;
G.arcs[0][2].adj=G.arcs[2][0].adj=688;
G.arcs[0][3].adj=G.arcs[3][0].adj=588;
G.arcs[1][4].adj=G.arcs[4][1].adj=1109;
G

.arcs[2][4].adj=G.arcs[4][2].adj=267;
G.arcs[3][5].adj=G.arcs[5][3].adj=499;
G.arcs[4][6].adj=G.arcs[6][4].adj=255;
G.arcs[4][7].adj=G.arcs[7][4].adj=1409;
G.arcs[5][7].adj=G.arcs[7][5].adj=999;
G.arcs[6][8].adj=G.arcs[8][6].adj=778;
G.arcs[7][8].adj=G.arcs[8][7].adj=399;
G.arcs[8][9].adj=G.arcs[9][8].adj=900;
}
//景点信息描述界面
void narrate()
{
int i,k=0;
printf("\n\t\t*****************欢迎使用校园导游程序***************\n");
printf("\n\t\t********************江西农业大学*******************\n");
printf("\t__________________________________________________________________\n");
printf("\t\t景点名称\t\t|\t景点描述\n");
printf("\t________________________________|_________________________________\n");
for(i=0;i{
printf("\t (%2d)%-10s\t\t\t|\t%-25s\n",i,G.vex[i].sight,G.vex[i].description);
k=k+1;
}
printf("\t________________________________|_________________________________\n");
}
//求最短路径
void ShortestPath(int num)
{
int v,w,i,t;
int final[NUM];
int min;
for(v=0;v{
final[v]=0;
D[v]=G.arcs[num][v].adj;
for(w=0;wP[v][w]=0;
if(D[v]<20000)
{
P[v][num]=1;
P[v][v]=1;
}
}

D[num]=0;
final[num]=1;

for(i=0;i{
min=Max;
for(w=0;wif(!final[w])
if(D[w]{
v=w;
min=D[w];
}
final[v]=1;
for(w=0;wif(!final[w]&&((min+G.arcs[v][w].adj){
D[w]=min+G.arcs[v][w].adj;
for(t=0;tP[w][t]=P[v][t];
P[w][w]=1;
}
}
}
//输出路径距离
void output(int sight1,int sight2)
{
int a,b,c,d,q=0;
a=sight2;
if(a!=sight1)
{
printf("\n\t从%s到%s的最短路径是",G.vex[sight1].sight,G.vex[sight2].sight);
printf("\t(最短距离为 %d m.)\n\n\t",D[a]);
printf("\t%s",G.vex[sight1].sight);
d=sight1;
for(c=0;c{
gate:;
P[a][sight1]=0;
for(b=0;b{
if(G.arcs[d][b].adj<20000&&P[a][b])
{
printf("-->%s",G.vex[b].sight);
q=q+1;
P[a][b]=0;
d=b;
if(q%8==0) printf("\n");
goto gate;
}
}
}
}

}
//推荐景点分析
void HaMiTonian(int m)
{
if(m>8)
return;
L: NextValue(m);
if(x[m]==0)
return;
if(m==7&&G.arcs[0][x[8]-1].adj!=20000)
display();
else
HaMiTonian(m+1);
goto L;
}
//推荐路径景点算法
void NextValue(int k)
{
int j;
l:x[k]=(x[k]+1)%10;
if(x[k]==0)
return;
if(G.arcs[x[k-1]-1][x[k]-1].adj!=20000)
{
for(j=0;jif(x[j]==x[k])
goto l;
return;
}
else
goto l;
}
//输出最佳景点路径
void display()
{
int i=0;
printf("\n\n\t");
for(i=0;i<8;i++)
printf("%s->",G.vex[x[i]-1].sight);
printf("出口");
printf

("\n");
}

相关文档