校园导游程序(c++)
问题描述:
用无向网表示你所在学校的校园景点平面图,图中顶点表示主要景点,存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。
基本要求：
1、查询各景点的相关信息。
2、查询图中任意两个景点间的最短路径。
3、查询图中任意两个景点间的所有路径。
4、增加、删除、更新有关景点和道路的信息。
/*校园导游程序*//*[问题描述]
用无向网表示学校的校园景点平面图，图中顶点表示主要景点，
存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。
游客通过终端可询问：
（1）从某一景点到另一景点的最短路径。
（2）游客从公园进入，选取一条最佳路线。
（3）使游客可以不重复地浏览各景点，最后回到出口（出口就在入口旁边）。
[基本要求]
（1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，
边上的权值表示距离．为此图选择适当的数据结构。
（2）把各种路径都显示给游客，由游客自己选择浏览路线。
（3）画出景点分布图于屏幕上。
[实现提示]
（1）构造一个无向图G并用邻接矩阵来存储。
（2）利用迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组p[i][]来记录，
最短路径长度就用一维数组d[i]存放；i的范围：0～20。
（3）一维数组have[]是用来记录最短路径出现顶点的顺序。
（4）根据起点和终点输出最短路径和路径长度。
*/
#define INFINITY 10000 /*无穷大*/
#define MAX_VERTEX_NUM 40
#define MAX 40
#include
#include
#include
#include
typedef struct ArCell
{
int adj; //路径长度
}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct //图中顶点表示主要景点，存放景点的编号、名称、简介等信息，{
char name[30];
int num;
char introduction[100];//简介
}infotype;
typedef struct
{
infotype vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph;
MGraph b;
void cmd(void);
MGraph InitGraph(void);
void Menu(void);
void Browser(MGraph *G);
void ShortestPath_DIJ(MGraph * G);
void Floyd(MGraph *G);
void Search(MGraph *G);
int LocateVex(MGraph *G,char* v);
MGraph * CreatUDN(MGraph *G);
void print(MGraph *G);
/******************************************************/
void main(void)
{
system("color 1f");
system("mode con: cols=140 lines=130");
cmd();
}
/******************************************************/
void cmd(void)
{
int i;
b=InitGraph();
Menu();
scanf("%d",&i);
while(i!=5)
{
switch(i)
{
case 1:system("cls");Browser(&b);Menu();break;
case 2:system("cls");ShortestPath_DIJ(&b);Menu();break;
case 3:system("cls");Floyd(&b);Menu();break;
case 4:system("cls");Search(&b);Menu();break;
case 5:exit(1);break;
default:break;
}
scanf("%d",&i);
}
}
MGraph InitGraph(void)
{
MGraph G;
int i,j;
G.vexnum=10;
G.arcnum=14;
for(i=0;i G.vexs[i].num=i; strcpy(G.vexs[0].name,"综合食堂"); strcpy(G.vexs[0].introduction,"新建标准化食堂"); strcpy(G.vexs[1].name,"东西办公楼"); strcpy(G.vexs[1].introduction,"全体教师办公场所，楼高12层，各种设施齐全"); strcpy(G.vexs[2].name,"5号学生宿舍楼"); strcpy(G.vexs[2].introduction,"计算机系男生宿舍楼，苏式建筑"); strcpy(G.vexs[3].name,"医院"); strcpy(G.vexs[3].introduction,"校医院,设施不是很齐全，只能看小病，收费较贵"); strcpy(G.vexs[4].name,"图书馆"); strcpy(G.vexs[4].introduction,"藏书60万册,设施良好，2楼为电子阅览室，环境幽雅"); strcpy(G.vexs[5].name,"足球场"); strcpy(G.vexs[5].introduction,"现代化塑胶跑道,人造草坪,适宜锻炼身体的场所"); strcpy(G.vexs[6].name,"沁园"); strcpy(G.vexs[6].introduction,"绿树成荫,适宜休息和读书"); strcpy(G.vexs[7].name,"主教学楼"); strcpy(G.vexs[7].introduction,"学院最大的教学楼,共5层，环形建筑,适宜学习"); strcpy(G.vexs[8].name,"西教学楼"); strcpy(G.vexs[8].introduction,"学院第二大教学楼,环境较差"); strcpy(G.vexs[9].name,"多媒体楼"); strcpy(G.vexs[9].introduction,"多媒体教学场所,设施先进,环境良好"); for(i=0;i for(j=0;j G.arcs[i][j].adj=INFINITY; G.arcs[0][1].adj=100; G.arcs[0][2].adj=200; G.arcs[0][6].adj=400; G.arcs[1][7].adj=300; G.arcs[2][3].adj=120; G.arcs[3][6].adj=220; G.arcs[3][4].adj=100; G.arcs[4][5].adj=300; G.arcs[4][9].adj=250; G.arcs[5][9].adj=350; G.arcs[6][7].adj=60; G.arcs[6][9].adj=200; G.arcs[7][8].adj=50; G.arcs[8][9].adj=20; for(i=0;i for(j=0;j G.arcs[j][i].adj=G.arcs[i][j].adj; return G; }//InitGraph end void Menu() { printf("\n 石家庄铁道学院导游图\n"); printf(" ┏━━━━━━━━━━━━━━━━━━━━┓\n"); printf(" ┃ 1.浏览校园全景┃\n"); printf(" ┃ 2.查看所有游览路线┃\n"); printf(" ┃ 3.选择出发点和目的地┃\n"); printf(" ┃ 4.查看景点信息┃\n"); printf(" ┃ 5.退出系统┃\n"); printf(" ┗━━━━━━━━━━━━━━━━━━━━┛\n"); printf("Option-:"); } void Browser(MGraph *G) { int v; printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n"); printf("┃编号┃景点名称┃简介 ┃\n"); for(v=0;v printf("┃%-4d┃%-16s┃%-56s┃ \n",G->vexs[v].num,G->vexs[v].name,G->vexs[v].introduction); printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n"); } // 迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0为起点 void ShortestPath_DIJ(MGraph * G) { int v,w,i,min,t=0,x,flag=1,v0; int final[20], D[20], p[20][20]; while(flag) { printf("请输入一个起始景点编号:"); scanf("%d",&v0); if(v0<0||v0>G->vexnum) { printf("景点编号不存在!请重新输入景点编号:"); scanf("%d",&v0); } if(v0>=0&&v0 flag=0; } for(v=0;v { final[v]=0; D[v]=G->arcs[v0][v].adj; for(w=0;w p[v][w]=0; if(D[v] { p[v][v0]=1;p[v][v]=1; } } D[v0]=0;final[v0]=1; { min=INFINITY; for(w=0;w if(!final[w]) if(D[w] final[v]=1; for(w=0;w if(!final[w]&&(min+G->arcs[v][w].adj { D[w]=min+G->arcs[v][w].adj; for(x=0;x p[w][x]=p[v][x]; p[w][w]=1; } } for(v=0;v { if(v0!=v) printf("%s",G->vexs[v0].name); for(w=0;w { if(p[v][w]&&w!=v0) printf("-->%s",G->vexs[w].name); t++; } if(t>G->vexnum-1&&v0!=v)printf(" 总路线长%dm\n\n",D[v]); } }//ShortestPath_DIJ end void Floyd(MGraph *G) { int v,u,i,w,k,j,flag=1,p[10][10][10],D[10][10]; for(v=0;v for(w=0;w { D[v][w]=G->arcs[v][w].adj; for(u=0;u p[v][w][u]=0; if(D[v][w] { p[v][w][v]=1;p[v][w][w]=1; } } for(v=0;v for(w=0;w if(D[v][u]+D[u][w] { D[v][w]=D[v][u]+D[u][w]; for(i=0;i p[v][w][i]=p[v][u][i]||p[u][w][i]; } while(flag) { printf("请输入出发点和目的地的编号:"); scanf("%d%d",&k,&j); if(k<0||k>G->vexnum||j<0||j>G->vexnum) { printf("景点编号不存在!请重新输入出发点和目的地的编号:"); scanf("%d%d",&k,&j); } if(k>=0&&k flag=0; } printf("%s",G->vexs[k].name); for(u=0;u if(p[k][j][u]&&k!=u&&j!=u) printf("-->%s",G->vexs[u].name); printf("-->%s",G->vexs[j].name); printf(" 总路线长%dm\n",D[k][j]); }//Floyd end void Search(MGraph *G) { int k,flag=1; while(flag) { printf("请输入要查询的景点编号:"); scanf("%d",&k); if(k<0||k>G->vexnum) { printf("景点编号不存在!请重新输入景点编号:"); scanf("%d",&k); } if(k>=0&&k flag=0; } printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n"); printf("┃编号┃景点名称┃简介 ┃\n"); printf("┃%-4d┃%-16s┃%-56s┃ \n",G->vexs[k].num,G->vexs[k].name,G->vexs[k].introduction); printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n"); }//Search end int LocateVex(MGraph *G,char* v) { int c=-1,i; for(i=0;i if(strcmp(v,G->vexs[i].name)==0) {c=i;break;} return c; } MGraph * CreatUDN(MGraph *G)//初始化图形，接受用户输入 { int i,j,k,w; char v1[20],v2[20]; printf("请输入图的顶点数,弧数:"); scanf("%d%d",&G->vexnum,&G->arcnum); printf("请输入景点的编号:、名称、简介:\n"); for(i=0;i { printf("景点编号:"); scanf("%d",&G->vexs->num); printf("景点名称:"); scanf("%s",G->vexs[i].name); printf("景点简介:"); scanf("%s",G->vexs->introduction); } for(i=0;i for(j=0;j G->arcs[i][j].adj=INFINITY; printf("请输入路径长度:\n"); for(k=0;k { printf("第%d条边:\n",k+1); printf("景点对(x,y):"); scanf("%s",v1); scanf("%s",v2); printf("路径长度:"); scanf("%d",&w); i=LocateVex(G,v1); j=LocateVex(G,v2); if(i>=0&&j>=0) { G->arcs[i][j].adj=w; G->arcs[j][i]=G->arcs[i][j]; } } return G; } void print(MGraph *G) { int v,w,t=0; for(v=0;v for(w=0;w { if(G->arcs[v][w].adj==INFINITY) printf("∞"); else printf("%-7d",G->arcs[v][w].adj); t++; if(t%G->vexnum==0) printf("\n"); } } 校园导游咨询 [问题描述] 设计一个校园导游程序，为来访的客人提供各种信息查询服务。 [基本要求] (1)设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 (2)为来访客人提供图中任意景点相关信息的查询。 (3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。 一需求分析 1从中北大学平面图中选取10个大家熟悉的景点，抽象成一个无向带权图（如图所示）。以图中顶点表示景点，边上的权值表示两地的距离。 2本程序的目的是为用户提供路径咨询和景点查询。根据用户指定的始点和终点输出相应路径或者根据用户指定的景点输出景点的信息。 南 北 二、概要设计 1本文采用的数据结构 */ /*包含头文件*/ #include #include /*定义符号常量*/ #define INT_MAX 10000 #define n 10 /*定义全局变量*/ int cost[n][n];/* 边的值*/ int shortest[n][n];/* 两点间的最短距离*/ int path[n][n];/* 经过的景点*/ /*自定义函数原型说明*/ void introduce(); int shortestdistance(); void floyed(); void display(int i,int j); 2个人分工 （1）景点信息查询 （2）两景点的最短距离 （3）两个景点之间的路径 void main() {/*主函数*/ int i,j; char k; for(i=0;i<=n;i++) for(j=0;j<=n;j++) cost[i][j]=INT_MAX; cost[1][3]=cost[3][1]=2; cost[2][3]=cost[3][2]=1; cost[2][4]=cost[4][2]=2; cost[3][10]=cost[10][3]=4; cost[1][10]=cost[10][1]=4； cost[2][10]=cost[10][2]=4； cost[4][10]=cost[10][4]=4； cost[1][4]=cost[4][1]=5; cost[4][5]=cost[5][4]=3; cost[4][9]=cost[9][4]=4; cost[5][9]=cost[9][5]=8; cost[5][7]=cost[7][5]=4; cost[5][6]=cost[6][5]=2; cost[6][7]=cost[7][6]=1; cost[7][8]=cost[8][7]=3; cost[8][6]=cost[6][8]=4; cost[1][1]=cost[2][2]=cost[3][3]=cost[4][4]=cost[5][5]=0; cost[6][6]=cost[7][7]=cost[8][8]=cost[9][9]=cost[10][10]=0; while(1) { printf("----------------欢迎使用中北大学导游系统!----------------\n"); printf("1.景点信息查询………请按i (introduc)键\n"); printf("2.景点最短路径查询…请按s (shortestdistance)键\n"); printf("3.退出系统……………请按e (exit)键\n"); printf("学校景点列表:\n"); printf("1:学校南门"); printf("2:学生公寓"); printf("3:柏林园"); printf("4:餐厅"); printf("5:体育馆\n"); printf("6:图书馆"); printf("7:重点实验室"); printf("8:主楼"); printf("9:科艺苑"); printf("10:国防生公寓\n"); printf("请选择服务:"); scanf("\n%c",&k); switch(k) { case 'i': printf("进入景点信息查询:"); introduce(); break; case 's': printf("进入最短路径查询:"); shortestdistance(); break; case 'e': exit(0); default: printf("输入信息错误！\n请输入字母i或s或e.\n"); break; } } }/*main*/ void introduce() {/*景点介绍*/ int a; printf("您想查询哪个景点的详细信息?请输入景点编号:"); scanf("%d",&a); getchar(); printf("\n"); switch(a) { case 1: printf("1:学校南门\n\n 学校的正门，前面竖立着一尊彭德华的石像，气势宏伟。\n\n");break; case 2: printf("2:学生公寓集中的地方。\n\n");break; case 3: printf("3:柏林园\n\n 晨读锻炼得地方。\n\n");break; case 4: printf("4:餐厅\n\n 学生老师就餐的地方\n\n");break; case 5: printf("5:体育馆\n\n 体育馆\n\n 学生上体育课及运动的场地，设有田径场、足球场、篮球场等。\n\n");break; case 6: printf("6:图书馆\n\n 学校信息资源中心，内设大量的自习室。\n\n");break; case 7: printf("7:重点实验室\n\n 我校的研究科研中心\n\n");break; case 8: printf("8:主楼\n\n 学校行政办公的主楼。\n\n");break; case 9: printf("9:科艺苑\n\n 有咖啡厅和放映室。\n\n\n");break; case 10: printf("10: 国防生公寓\n\n 国防生居住地地方。\n\n");break; default: printf("景点编号输入错误！请输入1->10的数字编号！\n\n"); break; } }/*introduce*/ int shortestdistance() {/*要查找的两景点的最短距离*/ int i,j; printf("请输入要查询的两个景点的编号(1->10的数字编号并用','间隔):"); scanf("%d,%d",&i,&j); if(i>n||i<=0||j>n||j<0) { printf("输入信息错误！\n\n"); printf(" 请输入要查询的两个景点的编号(1->10的数字编号并用','间隔):\n"); scanf("%d,%d",&i,&j); } else { floyed(); display(i,j); } return 1; }/*shortestdistance*/ void floyed() {/*用floyed算法求两个景点的最短路径*/ int i,j,k; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { shortest[i][j]=cost[i][j]; path[i][j]=0; } for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(shortest[i][j]>(shortest[i][k]+shortest[k][j])) {/*用path[][]记录从i到j的最短路径上点j的前驱景点的序号*/ shortest[i][j]=shortest[i][k]+shortest[k][j]; path[i][j]=k; path[j][i]=k; } }/*floyed*/ void display(int i,int j) {/* 打印两个景点的路径及最短距离*/ int a,b; a=i; b=j; printf("您要查询的两景点间最短路径是:\n\n"); if(shortest[i][j]!=INT_MAX) { if(i { printf("%d",b); while(path[i][j]!=0) {/* 把i到j的路径上所有经过的景点按逆序打印出来*/ printf("<-%d",path[i][j]); if(i j=path[i][j]; else i=path[j][i]; } printf("<-%d",a); printf("\n\n"); printf("(%d->%d)最短距离是:%d米\n\n",a,b,shortest[a][b]); } else { printf("%d",a); while(path[i][j]!=0) {/* 把i到j的路径上所有经过的景点按顺序打印出来*/ printf("->%d",path[i][j]); if(i j=path[i][j]; else i=path[j][i]; } printf("->%d",b); printf("\n\n"); printf("(%d->%d)最短距离是:%5d米\n\n",a,b,shortest[a][b]); } } else printf("输入错误！不存在此路！\n\n"); printf("\n"); }/*display*/ 校园导游咨询 [问题描述] 设计一个校园导游程序，为来访的客人提供各种信息查询服务。 [基本要求] （1）设计你所在学校的校园平面图，所含景点不少于10(*6*)个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 （2）为来访客人提供图中任意景点相关信息的查询。 （3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 ************************************************ 感想： 拿到这一题目，我有一种似曾相似的感觉，yeah~ 跟以前学C语言时做的“学生成绩管理系统”类似，程序功能就是多了求最短路径，用到图方面的算法。所以我异想天开，认为简单的把“学生成绩管理系统”加以修改，增加一个求最短路径函数就大功告成了。结果写到最后麻烦就来了：景点结构体信息是可以保存到文件mystud.dat文件了，可边的信息该怎么表示出来？边似乎跟景点压根儿没联系得上。实在没办法，只好多建一文件me.dat独立存放边的信息。 通过写这个程序，给我的教训是深刻的，也让我重新认识到程序设计思路、规划的重要性。 特发以下代码，让自己和后来者引以为戒！！！#include #include #include #include #include #define M 10000 #define MaxSize 6//设定校园景点数 #define M 10000 //景点结构体 struct location { char name[10]; char information[100]; int vertex; struct location *link; }stu; int adjacency[MaxSize][MaxSize]; FILE *fp,*fp1;//指向文件指针 void initiate();//输入函数 void Views();//浏览函数 void Quit();//退出 void mainenu();//主菜单 void FindShortest(); struct location *search(struct location *h,int x);//查找函数 struct location *creat(int n);//创建动态链表 void PrintChain(struct location *head);//输出所查找景点的函数void mainmenu() { int key; system("cls"); printf("\n"); printf("\t ︿☆☆迷你校园导游☆☆︿\n"); printf("\t\t○----------------------------------○\n"); printf("\t\t| 1.初始化校园各景点|\n"); printf("\t\t| 2.浏览各个景点的简介信息|\n"); printf("\t\t| 3.查找某景点到另一景点的最短路线|\n"); printf("\t\t| 4.退出导游系统|\n"); printf("\t\t○----------------------------------○\n"); printf("\t\t请您选择:"); key=getch(); switch(key) { case '1': initiate();break; case '2': V iews();break; case '3': FindShortest();break; case '4': Quit();break; } } /*************************************/ /* 录入景点及初始化道路信息*/ /*************************************/ void initiate() { char ch; int i=1;//记录文件中景点总数 int j,k,s;//s为路线长度 if((fp=fopen("D:\\mystud.dat","a+b"))==NULL)//打开/建立景点文件 { printf("can't open file\n"); exit(1); } if((fp1=fopen("D:\\me.dat","a+b"))==NULL)//打开/建立道路文件 { printf("can't open file\n"); exit(1); } while(fread(&stu,sizeof(struct location),1,fp)!=0)//统计文件中景点总数i++; do { system("cls");//清屏 printf("\n"); printf("\n"); printf("输入编号为%d 的的景点:",i-1); gets(https://www.doczj.com/doc/8016163140.html,); printf("输入景点简介信息:");gets(https://www.doczj.com/doc/8016163140.html,rmation); printf("______________________________\n"); printf("确定该景点的编号:"); scanf("%d",&stu.vertex); fwrite(&stu,sizeof(struct location),1,fp);//把输入的景点数据写入文件中 i++;//继续统计景点总数 printf("还要输入新的景点吗(y/n)?\t"); if(i>MaxSize) break; ch=getch();getchar(); }while(ch=='y');//选择是否还输入数据 fclose(fp);//关闭文件 //(显示出输入的景点信息） if((fp=fopen("D:\\mystud.dat","rb"))==NULL) { printf("can't open file\n"); exit(1); } system("cls"); printf("\t--------------------------------------------------\n"); while(fread(&stu,sizeof(struct location),1,fp)!=0) { //将文件中数据读入程序中 printf("\t"); printf("%d %s",stu.vertex,https://www.doczj.com/doc/8016163140.html,); if(++i==5) printf("\n"); }
相关主题
文本预览