第一篇：校园导游课程设计实验报告
《数据结构》
课 程 设 计 实 验 报 告
课程名称：
《数据结构》课程设计 课程设计题目： 校园导游 姓名：
邱可昉 院系：
计算机学院 专业：
计算机科学与技术 班级：
10052313 学号：
10051319 指导老师：
王立波
2012年5月18日
目录
1.课程设计的目的„„„„„„„„„„„„„„„„„„„„„3 2.问题分析„„„„„„„„„„„„„„„„„„„„„„„„3 3.课程设计报告内容„„„„„„„„„„„„„„„„„„„„3（1）概要设计„„„„„„„„„„„„„„„„„„„„„3（2）详细设计„„„„„„„„„„„„„„„„„„„„„3（3）测试结果„„„„„„„„„„„„„„„„„„„„„7（4）程序清单„„„„„„„„„„„„„„„„„„„„„9 4.个人小结 „„„„„„„„„„„„„„„„„„„„„„„14
1.课程设计的目的
《数据结构》是计算机软件的一门基础课程，计算机科学各领域及有关的应用软件都要用到各种类型的数据结构。学好数据结构对掌握实际编程能力是很有帮助的。为了学好《数据结构》，必须编写一些在特定数据结构上的算法，通过上机调试，才能更好地掌握各种数据结构及其特点，同时提高解决计算机应用实际问题的能力。
2.问题分析
[问题描述]（1）设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示学校各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。
（2）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。
（3）为来访客人提供图中任意景点相关信息的查询。[测试数据] 由读者根据实际情况指定。
3.课程设计报告内容
（1）概要设计
根据学校具体分布构建无向连通图，再通过几个模块运行函数完成校园信息简介查询，校园景点间最短距离计算和输出以及退出功能。
（2）详细设计
//定义全局变量 int bian[n][n];int zhjl[n][n];int path[n][n];//构建dy类 class dy{ public: dy();
~dy();void jj();int zuiduan();void floyed();void shuchu(int,int);
// 边的值
// 两点间的最短距离
// 经过的景点
};首先，通过dy类的构造函数构建邻接矩阵。dy::dy(){ for(int i=0;i bian[1][3]=bian[3][1]=150;bian[1][6]=bian[6][1]=300;bian[2][3]=bian[3][2]=100;bian[3][4]=bian[4][3]=50;bian[3][5]=bian[5][3]=200;bian[4][5]=bian[5][4]=100;bian[4][8]=bian[8][4]=350; bian[4][9]=bian[9][4]=250;bian[5][6]=bian[6][5]=100;bian[5][7]=bian[7][5]=250;bian[5][8]=bian[8][5]=300;bian[6][7]=bian[7][6]=200;bian[7][8]=bian[8][7]=100;bian[8][9]=bian[9][8]=400;bian[9][10]=bian[10][9]=100;//将各点到自己的距离定义为0 bian[1][1]=bian[2][2]=bian[3][3]=bian[4][4]=bian[5][5]=0;bian[6][6]=bian[7][7]=bian[8][8]=bian[9][9]=bian[10][10]=0;} 接着，jj函数实现景点列表输出和景点查询。void dy::jj(){ int a;cout<<“您想查询哪个景点的详细信息?”< cin>>i>>j;if(i>n||i<=0||j>n||j<=0){ cout<<“输入信息错误！”< cout<<“请输入要查询的两个景点的编号(1-10的数字编号):”< void dy::floyed(){ int i,j,k;for(i=1;i zdjl[i][j]=zdjl[i][k]+zdjl[k][j];path[i][j]=k;path[j][i]=k;} } 最后，shuchu函数判断输入两景点编号大小，完成正序输出和逆序输出。void dy::shuchu(int i,int j){ int a,b;a=i;b=j;cout<<“您要查询的两景点间最短路径是:”< cout<<“<-”< “< ”< （4）测试结果 （4）程序清单 #include using namespace std; #define INT_MAX 10000 #define n 11 //定义全局变量 int bian[n][n];int zdjl[n][n];int path[n][n]; class dy{ public: dy();~dy();void jj();int zuiduan();void floyed(); // 边的值 // 两点间的最短距离 // 经过的景点 void shuchu(int,int);};dy::dy(){ for(int i=0;i bian[1][3]=bian[3][1]=150;bian[1][6]=bian[6][1]=300;bian[2][3]=bian[3][2]=100;bian[3][4]=bian[4][3]=50;bian[3][5]=bian[5][3]=200;bian[4][5]=bian[5][4]=100;bian[4][8]=bian[8][4]=350; bian[4][9]=bian[9][4]=250;bian[5][6]=bian[6][5]=100;bian[5][7]=bian[7][5]=250;bian[5][8]=bian[8][5]=300;bian[6][7]=bian[7][6]=200;bian[7][8]=bian[8][7]=100;bian[8][9]=bian[9][8]=400;bian[9][10]=bian[10][9]=100;bian[1][1]=bian[2][2]=bian[3][3]=bian[4][4]=bian[5][5]=0;bian[6][6]=bian[7][7]=bian[8][8]=bian[9][9]=bian[10][10]=0;} dy::~dy(){} void dy::jj()int a;{ cout<<“您想查询哪个景点的详细信息?”< cout< break;case 2: cout<<“校医院是学校内设的公益性、非盈利性的医疗机构。承担学校社区范围内师生员工的“六位一体”的医疗工作。”< cout< break;case 3: cout<<“图书馆现有藏书215万册,其中印刷型图书146万册，电子图书69万册,长期订阅的中外文期刊2500余种。建有“中国学术期刊”、“万方数据资源”、“人大复印报刊资料”全文数据库、“超星数字图书馆”等信息资源镜像站。”< cout< cout< break;case 5: cout<<“ 问鼎广场是杭州电子科技大学标志性建筑，位于校图书馆正面。”< cout< break;case 6: cout<<“3教是学校机房重地。”< cout< break;case 7: cout<<“据说杭电正大门可是花了500万啊，可以说是杭电最奢侈的一个建筑物了，所以大家不可不看啊，不能错过啊~~”< cout< break;case 8: cout<<“行政楼学校领导工作和处理事务的地方。”< cout< break;case 9: cout<<“体育馆是学校举行大型活动的场所，有一个很大的篮球场。”< break;case 10: cout<<“宿舍是学生生活的基本场所，有多个食堂提供不同风味的食物，还有2个超市方便同学们的日常生活。”< cout<<“请输入1-10的数字编号:”< break;} } int dy::zuiduan(){ int i,j;cout<<“请输入要查询的两个景点的编号(1-10的数字编号):”< zdjl[i][j]=zdjl[i][k]+zdjl[k][j];path[i][j]=k;path[j][i]=k;} } void dy::shuchu(int i,int j){ int a,b;a=i;b=j;cout<<“您要查询的两景点间最短路径是:”< ”< int main(){ int i,j,s=1,k;dy dy;while(s){ cout<<“----------------杭州电子科技大学导游系统!----------------”< 4.个人小结 在前两次编写程序之后，我已经能够轻车熟路的编写程序了，对于C++的数据结构风格也有所领悟，感觉相对轻松一些。 经过这次练习，我发现我还是有一些没有注意的地方，我发现我对于书本上的知识吸收还有欠缺，然后编写程序不够仔细，有一些小差错导致编译出现错误，后来检查后修正了。我要在以后的学习中注意以下几点： 1.认真上好专业课，多在实践中锻炼自己。2.写程序要考虑周到，严密。 3.在做设计的时候要有信心，有耐心，不浮躁。 4.认真学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。 5.在课余时间多写程序，熟练掌握在调试程序过程中常见的错误，一边节约调试程序的时间。 校园导游实验报告 学号：200930457018 姓名：熊博 班级：09计科1班 完成日期：2010-12-21 1、问题描述 制作陶瓷学院的校园导游图，游客通过终端可询问：（1）从某一景点到另一景点的最短路径。 （2）游客从公园进入，选取一条最佳路线3，使游客可以不重复地游览各景点，最后回到出口（出口就在入口处旁边） 2、要求 （1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离。为此图选择适当的数据结构。 （2）把各种路径都显示给游客，由游客自己选择游览路线。（3）画出景点分布图于屏幕上。 3、实现提示 （1）第一实际是最短路径问题，如果有几条路径长度相同，可选择途径景点较少的路径提供给游客。 （2）第二问可采用深度优先搜索，如果有多种路径可选择，则选择带权路径最小的路线提供给游客。 2.概要设计： typedef struct ArCell { int adj; //路径长度 }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct //图中顶点表示主要景点，存放景点的信息 { char name[30];int num;int x;int y;char introduction[500];//简介 }infotype;typedef struct { infotype vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum;}MGraph;MGraph b; void dij(MGraph *);计算出起点到其他各个顶点之间的最短路径 void floyd(MGraph *);计算任意两个景点之间的最短路径 void Search(MGraph *G);查看景点信息 void jdbrowser();查看主要景点布局图 3.详细设计： main函数： void main(){ int k;system(“color cf”);system(“mode con: cols=140 lines=130”);b=InitGraph();system(“cls”);printf(“ 欢迎您进入景德镇陶瓷学院学校园导游咨询系统n”);printf(“ttn”);Sleep(1000);do { while(1) { printf(“ n”); printf(“ 主要景点列表 n”); printf(“ n”); printf(“ <1> 操场 <2> 游泳馆 n”); printf(“ <3> 3教 <4> 体育馆 n”); printf(“ <5> 2教 <6> 1教 n”); printf(“ <7> 图书馆 <8> 2实验楼 n”); printf(“ <9> 9实验楼 <10> 医院 n”); printf(“ <11> 东西办 <12> 9#宿舍楼 n”); printf(“ <13> 综合食堂 <14> 二三食堂 n”); printf(“ <15> 80广场 <16>大门 n”); printf(“ n”); printf(“ttn”); printf(“ ┏━━━━━━━━━━━━━━━━━━━━━━━┓n”); printf(“ ┃ 1.查看主要景点布局图 ┃n”); printf(“ ┃ 2.查看景点信息 ┃n”); printf(“ ┃ 3.查看某一景点到其他景点的最短路径 ┃n”); printf(“ ┃ 4.查看任意两个景点之间的最短路径 ┃n”); printf(“ ┃ 0.退出系统 ┃n”); printf(“ ┗━━━━━━━━━━━━━━━━━━━━━━━┛n”); printf(“请输入您的选择选择，按回车键结束:”); scanf(“%d”,&k); if(k<0||k>5) { printf(“输入有误请重新输入，按回车键结束!n”); scanf(“%d”,&k); } else break;} switch(k){ case 1:jdbrowser();system(“cls”);break;case 2:Search(&b);system(“cls”);break;case 3:dij(&b);system(“cls”);break;case 4:floyd(&b);system(“cls”);break;case 0:exit(0); } }while(1);} 图形初始化函数： MGraph InitGraph(){ MGraph G;int i,j;G.vexnum=17;G.arcnum=19;for(i=0;i G.vexs[i].num=i;strcpy(G.vexs[1].name,“操场”);strcpy(G.vexs[1].introduction,“足球场，现代化塑胶跑道,人造草坪,锻炼身体的场所”);strcpy(G.vexs[2].name,“游泳馆”);strcpy(G.vexs[2].introduction,“一般只是暑假期间开放，水不是很干净”);strcpy(G.vexs[3].name,“3教”);strcpy(G.vexs[3].introduction,“多媒体教学场所,设施先进,环境良好”);strcpy(G.vexs[4].name,“体育馆”);strcpy(G.vexs[4].introduction,“里面有篮球场还有羽毛球场，平时用作羽毛球场地”);strcpy(G.vexs[5].name,“2教”);strcpy(G.vexs[5].introduction,“学院第二大教学楼,环境较差”);strcpy(G.vexs[6].name,“1教”);strcpy(G.vexs[6].introduction,“学院最大的教学楼,共5层，环形建筑,适宜学习”);strcpy(G.vexs[7].name,“图书馆”);strcpy(G.vexs[7].introduction,“藏书60万册,设施良好，2楼为电子阅览室，环境幽雅”);strcpy(G.vexs[8].name,“2实验楼”);strcpy(G.vexs[8].introduction,“信息科学与技术学院所在地”);strcpy(G.vexs[9].name,“9实验楼”);strcpy(G.vexs[9].introduction,“学校机房所在地”);strcpy(G.vexs[10].name,“医院”);strcpy(G.vexs[10].introduction,“校医院,设施不是很齐全，收费较贵”);strcpy(G.vexs[11].name,“春晖楼”);strcpy(G.vexs[11].introduction,“全体教师办公场所，楼高12层，各种设施齐全”);strcpy(G.vexs[12].name,“9#宿舍楼”);strcpy(G.vexs[12].introduction,“装饰古朴，设施还算齐全，就是挤了点”);strcpy(G.vexs[13].name,“综合食堂”);strcpy(G.vexs[13].introduction,“新建标准化食堂，食物种类多，但是价格比较贵。”);strcpy(G.vexs[14].name,“二三食堂”);strcpy(G.vexs[14].introduction,“收费比较便宜的食堂，二楼的套餐还可以，主要是便宜，不过菜有点难吃”);strcpy(G.vexs[15].name,“80广场 ”);strcpy(G.vexs[15].introduction,“新建的广场，据说由80界校友捐赠。”);strcpy(G.vexs[16].name,“大门”);strcpy(G.vexs[16].introduction,“我们学校的大门，车辆进出的地方。设有保安。”);G.vexs[1].x=1;G.vexs[1].y=3;G.vexs[2].x=2;G.vexs[2].y=3;G.vexs[3].x=1;G.vexs[3].y=2;G.vexs[4].x=2;G.vexs[4].y=2;G.vexs[5].x=2;G.vexs[5].y=1;G.vexs[6].x=3;G.vexs[6].y=1;G.vexs[7].x=3;G.vexs[7].y=2;G.vexs[8].x=3;G.vexs[8].y=3;G.vexs[9].x=3;G.vexs[9].y=4;G.vexs[10].x=4;G.vexs[10].y=1;G.vexs[11].x=5;G.vexs[11].y=1;G.vexs[12].x=5;G.vexs[12].y=4;G.vexs[13].x=6;G.vexs[13].y=1;G.vexs[14].x=6;G.vexs[14].y=3;G.vexs[15].x=5;G.vexs[15].y=3;for(i=0;i for(j=0;j G.arcs[i][j].adj=INFINITY;G.arcs[1][2].adj=40;G.arcs[2][8].adj=80; G.arcs[2][4].adj=50;G.arcs[3][4].adj=10; G.arcs[4][7].adj=42; G.arcs[4][5].adj=50;G.arcs[5][6].adj=40; G.arcs[6][7].adj=50; G.arcs[6][16].adj=20;G.arcs[6][10].adj=100;G.arcs[7][8].adj=50;G.arcs[8][9].adj=100;G.arcs[8][15].adj=200;G.arcs[10][11].adj=100;G.arcs[11][13].adj=50; G.arcs[15][14].adj=80;G.arcs[13][14].adj=100;G.arcs[11][15].adj=100;G.arcs[12][15].adj=10;for(i=1;i for(j=1;j G.arcs[i][j].adj=G.arcs[j][i].adj; return G;}//InitGraph end 迪杰斯特拉算法求一点到任意其他景点的最短路径： void dij(MGraph * G){ int v,w,w1,i,j,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=1;v final[v]=0; D[v]=G->arcs[v0][v].adj;for(w=1;w p[v][w]=0;if(D[v] { p[v][v0]=1;p[v][v]=1; } } D[v0]=1;final[v0]=1;for(i=1;i min=INFINITY; for(w=1;w if(!final[w]) if(D[w] final[v]=1; for(w=1;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=1;v flag=0;min=INFINITY; for(w=1;w { if(p[v][w]&&w!=v0) { flag=1; if(D[w] } } if(flag) { if(G->vexs[w1].x printf(“向东走%dm”,G->arcs[w1][j].adj); if(G->vexs[w1].x>G->vexs[j].x) printf(“向西走%dm”,G->arcs[w1][j].adj); if(G->vexs[w1].y printf(“向北走%dm”,G->arcs[w1][j].adj); if(G->vexs[w1].y>G->vexs[j].y) printf(“向南走%dm”,G->arcs[w1][j].adj); printf(“-->%s”,G->vexs[j].name); w1=j; p[v][j]=0; } else break; }while(1); printf(“n 总路线长%dmnn”,D[v]);} printf(“完毕，按任意键继续!n”);getch();Floyd算法求任意两点间的最短距离： void floyd(MGraph * G) // 计算任意两个景点之间的最短路径 { int v,w,w1,i,j,v1,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;} flag=1;while(flag){ printf(“请您输入一个目的地景点编号，按回车键结束:”); scanf(“%d”,&v1); if(v1<0||v1>G->vexnum) { printf(“景点编号不存在!请重新输入景点编号:”); scanf(“%d”,&v1); } if(v1>=0&&v1 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;for(i=1;i 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; } } v=v1; w1=v0; printf(“%s”,G->vexs[v0].name);do { flag=0;min=INFINITY; for(w=0;w { if(p[v][w]&&w!=v0) { flag=1; if(D[w] } } if(flag) { if(G->vexs[w1].x printf(“向东走%dm”,G->arcs[w1][j].adj); if(G->vexs[w1].x>G->vexs[j].x) printf(“向西走%dm”,G->arcs[w1][j].adj); if(G->vexs[w1].y printf(“向北走%dm”,G->arcs[w1][j].adj); if(G->vexs[w1].y>G->vexs[j].y) printf(“向南走%dm”,G->arcs[w1][j].adj); printf(“-->%s”,G->vexs[j].name); w1=j; p[v][j]=0; } else break; }while(1);printf(“n 总路线长%dmnn”,D[v]);printf(“完毕，按任意键继续!n”);getch();} 查询景点信息函数： 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┃%-96s┃n”,G->vexs[k].num,G->vexs[k].name,G->vexs[k].introduction);printf(“┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛n”);printf(“完毕，按任意键继续!n”);getch();} 主要的景点显示函数： void jdbrowser(){ printf(“●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●n”);printf(“● ●n”); printf(“● (9)九实验楼 (12)九栋 ●n”); printf(“● ┃ ┃ ●n”); printf(“● ┃ ┃ ●n”); printf(“● (1)操场━━(2)游泳馆━━━━(8)二实验楼━━━━━━━━━━━━━━━━━(15)80广场━━━━(14)二三食堂 ●n”);printf(“● ┃ ┃ ┃ ┃ ●n”); printf(“● ┃ ┃ ┃ ┃ ●n”); printf(“● (3)三教━━(4)体育馆━━━━━(7)图书馆 ┃ ┃ ●n”);printf(“● ┃ ┃ ┃ ┃ ●n”); printf(“● ┃ ┃ ┃ ┃ ●n”); printf(“● (5)二教━━━━━━(6)一教━━━━━━━━━━━━(10)医院━━━━━(11)东西办━━━━(13)综合食堂 ●n”);printf(“● ┃ ●n”); printf(“● (16)大门 ●n”); printf(“● ●n”); printf(“●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●n”);printf(“输出完毕，按任意键返回!n”);getch();} 4.使用说明： （1）.查看主要景点布局图（2）.查看景点信息 （3）.查看某一景点到其他景点的最短路径（4）.查看任意两个景点之间的最短路径 （0）.退出系统 5.测试结果： 主界面 景点图 景点信息 从某点到其他点的最短路径 任意两点的最短路径 退出系统 6.参考资料： 1、《数据结构（C语言版）》 严蔚敏，吴伟民 清华大学出版社 2、《数据结构—C语言描述》 耿国华等 西安电子科技大学出版社 3、Data Structure &Program Design in C Robert L.Kruse 清华大学出版社 4、《数据结构（用面向对象方法与C++描述）》 殷人昆 清华大学出版社 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长 春 大 学 课程设计纸 一、设计题目 校园导游咨询 二、需求分析 （1）设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示学校各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 （2）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 （3）为来访客人提供图中任意景点相关信息的查询。（4）界面美观，方便使用。通过主菜单操作。 三、总体设计 3.1 设计思路 设计一个校园导游系统，应用到数据结构中学到的图的建立，各景点应存在一个图中，而计算不重复路线的时候需要应用到弗洛伊德图的遍历。计算俩景点间最短路径应用到最小生成树的遍历。 景点数据装在一个图中，能够输入图的顶点和边的信息，并存储到相应存储结构中然后输出图的邻接矩阵。 邻接矩阵是表示顶点之间相邻关系。 生成树是指：如果G是一个图，这个图的生成子图T是树，那么可以说T为G的生成树。一个图有生成树当且仅当这个图连通。可通过求该网络的最小生成树达到求解线路或总代价最小的最佳方案。 弗洛伊德算法是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。它是从图的带权邻接矩A=[a(i,j)] n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；„„；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。3、2系统功能设计 本系统除了有主程序模块外还有3个子功能菜单。3个子功能的设计描述如下。（1）学校景点介绍 学校景点介绍由函数introduce()实现。当用户选择该功能，系统即能输出学校全部景点的信息：包括景点编号、景点名称及景点简介。 共 页 第 页 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长 春 大 学 课程设计纸 （2）查看两景点间最短路径 查看两景点间最短路径由函数shortestdistance()实现。该功能采用弗洛伊德（Floyd）算法实现。当用户选择该功能，系统能根据用户输入的起始景点及目的地景点编号，查询任意两个景点之间的最短路径线路及距离。 （3）退出 即退出校园导游系统，由exit(0)函数实现。3、3 模块间调用关系 主程序模块 （界面） 景点最短路径查询 景点信息查询 退出 四、详细设计 4、1数据存储 (1)无向带权图（无向网）的定义 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; （2）全局变量定义 #define INT_MAX 10000 #define n 10 int cost[n][n]; /* 边的值*/ int shortest[n][n]; /* 两点间的最短距离*/ int path[n][n]; /* 经过的景点*/ 4、2主程序模块 用于作为界面，显示校园景点和概况描述，提供各子模块的连接 如上图所示 程序设计 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; } } 4、3景点信息查询模块 在主菜单下，用户输入i回车，根据屏幕提示输入一个要查询的景点编号3回车后，运行结果如上图所示。 不足之处：仅能根据景点编号进行查询，可以增加根据景点名进行查询的功能。 程序设计 void introduce(){/*景点介绍*/ int a; printf(“您想查询哪个景点的详细信息?请输入景点编号:”); scanf(“%d”,&a); getchar(); printf(“n”); switch(a) { case 1: printf(“1:学校南门nn 学校的正门，前面竖立着一尊彭德华的石 共 页 第 页 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长 春 大 学 课程设计纸 像，气势宏伟。nn”);break; case 2: printf(“2:学生公寓集中的地方。nn”);break; case 3: printf(“3:柏林园nn 晨读锻炼得地方。nn”);break; case 4: printf(“4:餐厅nn 学生老师就餐的地方nn”);break; case 5: printf(“5:体育馆nn 体育馆nn 学生上体育课及运动的场地，设有田径场、足球场、篮球场等。nn”);break; case 6: printf(“6:图书馆nn 学校信息资源中心，内设大量的自习室。nn”);break; case 7: printf(“7:重点实验室nn 我校的研究科研中心nn”);break; case 8: printf(“8:主楼nn 学校行政办公的主楼。nn”);break; case 9: printf(“9:科艺苑nn 有咖啡厅和放映室。nnn”);break; case 10: printf(“10: 国防生公寓nn 国防生居住地地方。nn”);break; default: printf(“景点编号输入错误！请输入1->10的数字编号！nn”);break; } }/*introduce*/ 4、4景点最短路径查询模块 在主菜单下，用户输入3回车，根据屏幕提示输入一个出发景点编号及目的地景点号：6“,”3回车后，运行结果如上图所示。 不足之处：只能看到最短路径编号，但不知具体名称，设计还不够人性化。 程序设计（由floyed()和display(i,j)两个子模块完成）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(“您要查询的两景点间最短路径是:nn”); 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(“nn”); printf(“(%d->%d)最短距离是:%d米nn”,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(“nn”); printf(“(%d->%d)最短距离是:%5d米nn”,a,b,shortest[a][b]); } } else printf(“输入错误！不存在此路！nn”); printf(“n”);}/*display*/ 4、5退出 在主菜单下，用户输入e回车，即退出校园导游系统。 五、设计总结5、1用户手册 1．本程序执行文件为：湖北第二师范学院校园导游系统.exe 2．进入本系统之后，随即显示系统主菜单界面。用户可在该界面下输入各子菜单前对应的数字并按回车，执行相应子菜单命令。 3．查询景点信息都是通过输入景点编号并按回车实现，两个景点号之间用空格隔开。进入本系统后，建议先选择子菜单1――学校景点介绍，以了解景点名称和景点编号的对应关系。5、2心得体会 通过本次课程设计实验，使我更能熟练地掌握c语言和数据结构等知识的综合运 共 页 第 页 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长 春 大 学 课程设计纸 用。当然在课程设计期间，也遇到了大大小小的一些问题，是我看到了自己的不足之处，使我认识到在以后的学习中要善于发现自己的不足，找出自己的薄弱环节，以便能够更好的去巩固所学的。 本次设计中要求求最短路径，不重复走完一个图，就必须了解最短路径的算发和图的遍历。在拿到题目时，通过查找相关的资料才回忆起这两种方法的具体算法。根据程序的具体要求来设计算法。在选用存储方法是，要尽量选用时间复杂度较小的方法，这样能够节省程序执行时间，提高查询效率。 课程设计中所使用的计算机语言其使用范围比较广阔，在很多编程中都可以用到，所以无论以后我们从事计算机编程、软件设计还是硬件、网络等领域，都应该学会、学精一门编程语言，这对我们以后的学习和工作有很大的帮助。 共 页 第 页 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长 春 大 学 课程设计纸 附录 /*包含头文件*/ #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); 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:学校南门nn 学校的正门，前面竖立着一尊彭德华的石像，气势宏伟。nn”);break; case 2: printf(“2:学生公寓集中的地方。nn”);break; case 3: printf(“3:柏林园nn 晨读锻炼得地方。nn”);break; case 4: printf(“4:餐厅nn 学生老师就餐的地方nn”);break; case 5: printf(“5:体育馆nn 体育馆nn 学生上体育课及运动的场地，设有田径场、足球场、篮球场等。nn”);break; case 6: printf(“6:图书馆nn 学校信息资源中心，内设大量的自习室。nn”);break; case 7: printf(“7:重点实验室nn 我校的研究科研中心nn”);break; case 8: printf(“8:主楼nn 学校行政办公的主楼。nn”);break; case 9: printf(“9:科艺苑nn 有咖啡厅和放映室。nnn”);break; case 10: printf(“10: 国防生公寓nn 国防生居住地地方。nn”);break; default: printf(“景点编号输入错误！请输入1->10的数字编号！nn”);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(“输入信息错误！nn”); 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(“您要查询的两景点间最短路径是:nn”); 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(“nn”); printf(“(%d->%d)最短距离是:%d米nn”,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(“nn”); printf(“(%d->%d)最短距离是:%5d米nn”,a,b,shortest[a][b]); } } else printf(“输入错误！不存在此路！nn”); printf(“n”);}/*display*/ 共 页 第 页 数据结构实验报告 ——实验六 简单校园导游程序的设计与实现 本实验的目的是通过对校园导游程序的设计与实现来熟练掌握图型结构在实际问题中的应用。 一、【问题描述】 当人们到一个陌生的地方去旅游的时候可能会找一个导游为自己在游玩的过程中提供方便。导游可以提供很多服务，比如介绍参观景点的历史背景等相关信息，推荐到下一个景点的最佳路径，以及解答旅游者所提出的关于旅游经典的相关问询等等。对于新生刚刚来到校园，对校园环境不熟悉的情况也如此，一般都是高年级的学生充当了“校园导游员”的角色，如果能够提供一个程序让新生或来访的客人自主的通过与机器的“对话”来获得相关的信息的话，将会节省大量的人力和时间。而且所提供的信息也能够做到尽可能的准确、详尽。一个成功的校园导游程序可以替代现实生活中这些“校园导游员”，更方便了大家查询校园相关的信息。 本次实验需要开发一个简单的校园导游程序，程序的主体功能为： 1、显示校园平面图，方便用户直观的看到校园的全景示意图，并确定自己的位置。 2、为用户提供对平面图中任意场所的相关信息的查询。 3、为用户提供对平面图中任意场所的问路查询。 二、【数据结构设计】 由于各个场所通过校园中的道路相连，各个场所和连接它们的道路构成了整个校园的地理环境，所以使用图这种数据结构对他们去进行描述。以图中的顶点表示校园内各个场所，应包含场所名称、代号、简介等信息；以边表示连接各个场所的道路，应包含道路的代号、路径的长度等信息。顶点和边均使用结构体定义，整个图的数据结构可以采用教材中介绍的各种表示方法，例如带权的邻接矩阵。 三、【功能（函数）设计】 1、显示校园平面图的功能模块。 通过读文件的方式将各个地点的信息读入程序中.平面图中应醒目的标识出场所的准确名称以备用户查询。河北大学校园导游的基本地点信息。 ***************欢迎进入河北大学校园导游系统!**************-----------------------景点名称--------------------------- 主楼 多功能馆 毓秀园 图书馆 操场 留学生楼 七教 八教 九教 成教 南大门 北大门 一教 逸夫楼 博物馆 物理楼 电信楼 化学楼 生科楼 建工楼 北院食堂 南院食堂 竹园 梅园 桂园 菊园 易百超市 北院生活园区 ---------------------------地点的存储 typedef struct Vertex//顶点结构体 { int No;//地点编号 char name[20];//地点名称 char info[1000];//地点简介 }Vertex;typedef struct //无向图结构体 { Vertex view[Max_Vertex];int edges[Max_Vertex][Max_Vertex];//边的邻接矩阵 int vnum,anum;//顶点和边的个数 }Graph; 2、查询任意场所的相关信息查询的功能模块。 此模块接收用户所输入的场所名称，并将场所的简介信息反馈给用户。查找出查询的场所将其信息输出,信息通过文本文件读入 函数void introduction(Graph &G)实现 先通过strcpy进行查找，再讲找到顶点v1 G.view[v1].info输出 3、任意场所的问路查询的功能模块。 void shortpath(Graph &G,int v0,int v1)；此函数运用克鲁斯卡尔算法计算两点间最短路径。 void dispath(Graph &G)//查询最短路径 { „shortpath(G, v0, v1)； } 此模块接收用户所输入的场所名称，并在调用shortpath(G, v0, v1)；计算出最短路径相关项的信息反馈给用户。 4、求单源点到其他各点的最短路径的功能模块。 此模块计算并记录从校园门口到各个场所的最短路径。for(i=0;i 四、【界面设计】 本程序为方便用户所设计，由于使用的最终用户大多对校园的情况并不熟悉，所以在图中给出的任何提示信息一定要准确，尽量的避免歧义。 五、【编码实现】 #include char name[20];//地点名称 char info[1000];//地点简介 }Vertex;typedef struct //无向图结构体 { Vertex view[Max_Vertex]; int edges[Max_Vertex][Max_Vertex];//边的邻接矩阵 int vnum,anum;//顶点和边的个数 }Graph;void Creat(Graph &G){ ifstream infile(“view.txt”,ios::in); if(!infile) { cout<<“文件打开错误”< abort(); } int i,j,k,w; infile>>G.vnum; infile>>G.anum; //cout< for(i=0;i { infile>>G.view[i].No>>G.view[i].name>>G.view[i].info; } for(i=0;i { for(j=0;j G.edges[i][j]=Maxnum; } ifstream weight_file(“weight.txt”,ios::in); if(!weight_file) { cout<<“文件打开错误”< abort(); } for(k=0;k { weight_file>>i>>j>>w; i--; j--; G.edges[i][j]=w; G.edges[j][i]=G.edges[i][j]; } } void introduction(Graph &G){ char temp[20];cout<<“请输入要查询的景点名称”< if(strcmp(G.view[i].name,temp)==0) { v1=i; count++; } } if(count!=1){ cout<<“输入的名称不存在”< return;} else { cout<<“该景点简介为”< cout< return;} } void shortpath(Graph &G,int v0,int v1){ int P[100];float D[100];int i,j,w;int v,pre;float min; int final[Max_Vertex];for(v=0;v { final[v]=0; D[v]=G.edges[v0][v]; if(D[v] P[v]=v0; if(D[v]==Maxnum) P[v]=-2; } D[v0]=0;final[v0]=1;P[v0]=-1; for(i=1;i min=Maxnum; //min为当前所知离源点的最近距离 for(w=0;w if(!final[w]) if(D[w] { j=w; //记忆此点 min=D[w]; } final[j]=1; //离源点最近的j加入S集合 for(w=0;w //更新其它点地当前最短路径 if(!final[w] &&(min+G.edges[j][w] { D[w]=min+G.edges[j][w]; P[w]=j; //将w的前驱结点改为j } } if(P[v1]==-2) cout<<“max”< else { pre=P[v1]; cout< cout< cout< while(pre>0) { cout<<“←”< pre=P[pre]; } if(v0==0) cout<<“←”< else cout< cout< } } void dispath(Graph &G)//查询最短路径 { int v1,v0,i;int count=0;char temp1[20],temp2[20];cout<<“请输入要查询的两个景点名称”< for(i=0;i if(strcmp(G.view[i].name,temp1)==0) { v0=i; count++; } if(strcmp(G.view[i].name,temp2)==0) { v1=i; count++; } } if(count!=2){ cout<<“输入的名称不存在”< return;} else { shortpath(G,v0,v1); return;} } void main(){ Graph G;Creat(G);int i;char ch1; cout<<“t***************欢迎进入河北大学校园导游系统!**************”< cout<<“t-----------------------景点名称---------------------------”< for(i=0;i { if(i%4==0) { cout< cout< } else { cout< } } cout< cout<<“t---------------------------”< cout<<“t__________________________________________________________”< cout<<“tt 请选择要进行的操作”< cout<<“ tt 1.查询景点信息”< cout<<“ tt 2:显示大门到各个地点的最短路径”< cout<<“ tt 3:查询两个景点之间的最短路径”< cout<<“ tt 0:退出”< cout<<“t__________________________________________________________”< cout<<“请选择(0~2):”; cin>>ch1; while(!(ch1<='3'&&ch1>='0')) { cout<<“数据输入错误，请重新选择(0~2):”; cin>>ch1; } switch(ch1) { case '1': introduction(G);break; case '2' : for(i=0;i shortpath(G,10,i); break; case '3' : dispath(G); break; } }while(ch1!=0);} 六、【运行与测试】 ***************欢迎进入河北大学校园导游系统!************** -----------------------景点名称--------------------------- 主楼 多功能馆 毓秀园 图书馆 操场 留学生楼 七教 八教 九教 成教 南大门 北大门 一教 逸夫楼 博物馆 物理楼 电信楼 化学楼 生科楼 建工楼 北院食堂 南院食堂 竹园 梅园 桂园 菊园 易百超市 北院生活园区 --------------------------- __________________________________________________________ 请选择要进行的操作 1.查询景点信息 2:显示大门到各个地点的最短路径 3:查询两个景点之间的最短路径 0:退出 __________________________________________________________ 请选择(0~2):1 请输入要查询的景点名称 主楼 该景点简介为 是河北大学本部标志性建筑，这H型高大的建筑，正对着河北大学校本部南院黑 校门，此楼于2001年建成。主要为教学、科研、办公服务。 __________________________________________________________ 请选择要进行的操作 1.查询景点信息 2:显示大门到各个地点的最短路径 3:查询两个景点之间的最短路径 0:退出 __________________________________________________________ 请选择(0~2):1 请输入要查询的景点名称 哈哈 输入的名称不存在 __________________________________________________________ 请选择要进行的操作 1.查询景点信息 2:显示大门到各个地点的最短路径 3:查询两个景点之间的最短路径 0:退出 __________________________________________________________ 请选择(0~2):2 南大门到主楼最短路径为50米 主楼←南大门 南大门到多功能馆最短路径为60米 多功能馆←南大门 南大门到毓秀园最短路径为60米 毓秀园←图书馆←南大门 南大门到图书馆最短路径为40米 图书馆←南大门 南大门到操场最短路径为160米 操场←毓秀园←图书馆←南大门 南大门到留学生楼最短路径为180米 留学生楼←操场←毓秀园←图书馆←南大门 南大门到七教最短路径为115米 七教←桂园←毓秀园←图书馆←南大门 南大门到八教最短路径为65米 八教←图书馆←南大门 南大门到九教最短路径为70米 九教←图书馆←南大门 南大门到成教最短路径为75米 成教←八教←图书馆←南大门 南大门到南大门最短路径为0米 南大门 南大门到北大门最短路径为25米 北大门←南大门 南大门到一教最短路径为35米 一教←北大门←南大门 南大门到逸夫楼最短路径为60米 逸夫楼←博物馆←物理楼←北大门←南大门 南大门到博物馆最短路径为45米 博物馆←物理楼←北大门←南大门 南大门到物理楼最短路径为35米 物理楼←北大门←南大门 南大门到电信楼最短路径为60米 电信楼←一教←北大门←南大门 南大门到化学楼最短路径为50米 化学楼←物理楼←北大门←南大门 南大门到生科楼最短路径为145米 生科楼←建工楼←化学楼←物理楼←北大门←南大门 南大门到建工楼最短路径为100米 建工楼←化学楼←物理楼←北大门←南大门 南大门到北院食堂最短路径为115米 北院食堂←化学楼←物理楼←北大门←南大门 南大门到南院食堂最短路径为80米 南院食堂←八教←图书馆←南大门 南大门到竹园最短路径为135米 竹园←七教←桂园←毓秀园←图书馆←南大门 南大门到梅园最短路径为145米 梅园←七教←桂园←毓秀园←图书馆←南大门 南大门到桂园最短路径为95米 桂园←毓秀园←图书馆←南大门 南大门到菊园最短路径为125米 菊园←八教←图书馆←南大门 南大门到易百超市最短路径为145米 易百超市←七教←桂园←毓秀园←图书馆←南大门 南大门到北院生活园区最短路径为159米 北院生活园区←北院食堂←化学楼←物理楼←北大门←南大门 __________________________________________________________ 请选择要进行的操作 1.查询景点信息 2:显示大门到各个地点的最短路径 3:查询两个景点之间的最短路径 0:退出 __________________________________________________________ 请选择(0~2): 请输入要查询的两个景点名称 主楼 七教 主楼到七教最短路径为75米 七教←桂园←毓秀园←主楼 __________________________________________________________ 请选择要进行的操作 1.查询景点信息 2:显示大门到各个地点的最短路径 3:查询两个景点之间的最短路径 0:退出 __________________________________________________________ 请选择(0~2):3 请输入要查询的两个景点名称 桌喽 菊园 输入的名称不存在 __________________________________________________________ 请选择要进行的操作 1.查询景点信息 2:显示大门到各个地点的最短路径 3:查询两个景点之间的最短路径 0:退出 __________________________________________________________ 请选择(0~2): 9、校园导游咨询 问题描述： 设计一个校园导游程序，为来访的客人提供各种信息查询服务。基本要求： ⑴设计华东交通大学的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，⑵存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。⑶为来访客人提供图中任意景点相关信息的查询。⑷为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 #include //最大顶点个数 #define INF 32767 //用32767表示∞ #include //调用函数system改变字体颜色的头文件 typedef int InfoType;#define MAXV 100 //最大顶点个数 //以下定义邻接矩阵类型 typedef struct { int no; //顶点编号 InfoType info; //顶点其他信息 } VertexType; //顶点类型 typedef struct //图的定义 { int edges[MAXV][MAXV];//邻接矩阵 int vexnum,arcnum; //顶点数，弧数 VertexType vexs[MAXV];//存放顶点信息 } MGraph; void ecjtumap()//建立华东交通大学地图 { printf(“t|------------------------------|n”);printf(“t| |n”);printf(“t| |n”);printf(“t| ---------- |n”);printf(“t| ==============================| 国防生宿舍| |n”);printf(“t|。 ---------- |n”);printf(“t|。 。 |n”);printf(“t|。 。 |n”);printf(“t|。 。 |n”);printf(“t|。 。 |n”);printf(“t|。 。 |n”);printf(“t| |南区四食堂| ---------- |n”);printf(“t|。 |南区礼堂 | |n”);printf(“t|。 ---------- |n”);printf(“t|。 。 |n”);printf(“t|。 。 |n”);printf(“t|。 --------。 |n”);printf(“t| ================| 校训牌|。。。。 |n”);printf(“t| = -------- |n”);printf(“t| =。 |n”);printf(“t| =。 |n”);printf(“t| -------- --------- |n”);printf(“t|----| 南区后门 |---------| 南区大门 |------------------------|n”);printf(“t| -------- --------- |n”);printf(“t| --------- |n”);printf(“t|-------------------------| 北区大门 |------------------------|n”);printf(“t| -------- |n”);printf(“t|。 -------------- |n”);printf(“t| ===========================| 15栋综合教学楼 | |n”);printf(“t| = -------------- |n”);printf(“t| =。 |n”);printf(“t| =。 |n”);printf(“t| =。 |n”);printf(“t| =。 |n”);printf(“t| = ---------- |n”);printf(“t| ===============================| 经管食堂 | |n”);printf(“t| = ---------- |n”);printf(“t| = = |n”);printf(“t| = = |n”);printf(“t| ----------- = |n”);printf(“t| |轨道交通食堂|====================| 学生宿舍 | |n”);printf(“t| ------------ |n”);printf(“t| |n”);printf(“t|------------------------------|n”);printf(“n”);} void DispMat(MGraph g) //输出邻接矩阵g，即输出地图各景点的图的距离 { int i,j;for(i=0;i for(j=0;j if(g.edges[i][j]==INF) printf(“%3s”,“∞”);//这里分别用%3s和%3d控制输出字符∞或数字宽度为3个字符 else printf(“%3d”,g.edges[i][j]);//这样比较方便观看景点的图的邻接矩阵g printf(“n”);} } void listmap()//建立 景点的相关信息的总浏览表 { printf(“t 华东交通大学景点一览 nn”);printf(“t|--------|n”);printf(“t| 1：南区大门 |n”);printf(“t|--------|n”);printf(“t| 2：校训牌 |n”);printf(“t|--------|n”);printf(“t| 3：图书馆 |n”);printf(“t|--------|n”);printf(“t| 4：南区一食堂 |n”);printf(“t|--------|n”);printf(“t| 5：孔目湖 |n”);printf(“t|--------|n”);printf(“t| 6：北区大门 |n”);printf(“t|--------|n”);printf(“t| 7：15栋教学楼 |n”);printf(“t|--------|n”);printf(“t| 8：北区食堂 |n”);printf(“t|--------|n”);printf(“t| 9：科技楼 |n”);printf(“t|--------|n”);printf(“t| 10：北区篮球场 |n”);printf(“t|--------|n”);} void introduce()//根据上面的浏览表，对应出相关信息 { int a=1;printf(“n”);printf(“请输入要查看的景点:n”);printf(“输入1~10的数字选择景点，其他数字返回上一级n”);while(0 switch(a) {case 1:printf(“1：南区大门是进入华东交通大学南区的正门n”);break; case 2:printf(“2：校训牌是激励我们大学生积极向上n”);break; case 3:printf(“3：图书馆是给我们大学生丰富知识的海洋n”);break; case 4:printf(“4：南区一食堂是南区学生的吃饭的地方n”);break; case 5:printf(“5：孔目湖是华东交通大学最迷人的地方n”);break; case 6:printf(“6：北区大门是进入华东交通大学北区的正门n”);break; case 7:printf(“7：15栋教学楼是一栋综合型的教学楼n”);break; case 8:printf(“8：北区食堂是北区学生吃饭的地方n”);break; case 9:printf(“9：科技楼是大学生上机做实验的教学楼n”);break; case 10:printf(“10：北区篮球场是大学生锻炼身体的地方n”);break; } } } void show_didian(int n)//根据算法求出的整型数，对应出地点//根据 xx算法求出的数字，转化为文字描述 { switch(n){case 0:printf(“1.南区大门”);break;case 1:printf(“2.校训牌”);break;case 2:printf(“3.图书馆 ”);break;case 3:printf(“4.南区一食堂”);break;case 4:printf(“5.孔目湖”);break;case 5:printf(“6.北区大门”);break;case 6:printf(“7.15栋教学楼”);break;case 7:printf(“8.北区食堂”);break;case 8:printf(“9.科技楼”);break;case 9:printf(“10.北区篮球场”);break;} } void ppath(int path[][MAXV],int i,int j)//求最短路径经过的地点 { int k=path[i][j];if(k==-1)return;ppath(path,i,k);show_didian(k);printf(“->> ”);ppath(path,k,j);} void put_shortdistance(int x,int y,int A[][MAXV],int path[][MAXV],int n){ int i,j;for(i=0;i for(j=0;j if(A[i][j]==INF) { if(i!=j)printf(“从%d到%d没有路径n”,i,j); } else { if(i==x&&j==y) { printf(“最短路径为：从--”); show_didian(i); printf(“--到--”); show_didian(j); printf(“--路径为--:n”); show_didian(i);//输出起点 printf(“->>”); ppath(path,i,j);//求最短路径经过的中间路径，若没有则不输出 show_didian(j);//输出 终点 printf(“nt路径长度为:%dn”,A[i][j]); } } } void shortdistance(MGraph g,int x,int y)//求最短路径用的是弗洛伊德算法 { int A[MAXV][MAXV],path[MAXV][MAXV];//path为中间路径不包括 起点 终点 int i,j,k,n=g.vexnum;for(i=0;i //给A数组置初值 for(j=0;j { A[i][j]=g.edges[i][j];path[i][j]=-1; } for(k=0;k //计算Ak { for(i=0;i for(j=0;j //这里的3个for循环 if(A[i][j]>(A[i][k]+A[k][j]))//所以时间复杂度O(n3) { A[i][j]=A[i][k]+A[k][j];path[i][j]=k; } } put_shortdistance(x,y,A,path,n);} void menu(MGraph g)//建立 菜单 页面，可以无数次选择菜单，当输入5时退出系统 { int m=1,x=1,y=1;//m的菜单选择的功能x,y分别表示从x到y的问路查询 while(m!=5){ printf(“ttt|------------------------|n”); printf(“ttt|----------菜单----------|n”); printf(“ttt| 1：查看地图 |n”); printf(“ttt| 2：地图详解 |n”); printf(“ttt| 3：景点一览表 |n”); printf(“ttt| 4：问路查询 |n”); printf(“ttt| 5：退出 |n”); printf(“ttt|------------------------|n”); printf(“请输入1~5的数字n”); scanf(“%d”,&m); switch(m) {case 1:ecjtumap();break; case 2:listmap(); introduce();break; case 3:listmap(); introduce(); printf(“n”);break; case 4:listmap(); printf(“请输入起点:”); scanf(“%d”,&x);x+=-1; printf(“请输入终点:”); scanf(“%d”,&y);y+=-1; shortdistance(g,x,y);break; case 5:printf(“ttt感想使用本系统，欢迎下次继续使用n”);break; } } } void main(){ system(“color 0a”);//输出字体为绿色 int i,j;MGraph g;int A[MAXV][10]={ {INF, 1,INF,INF,INF, 1,INF,INF,INF,INF}，{ 1,INF, 5, 6, 7,INF,INF,INF,INF,INF}，{INF, 5,INF,INF, 2,INF,INF,INF,INF,INF}，{INF, 6,INF,INF, 5,INF,INF,INF,INF,INF}，{INF, 7, 2, 5,INF,INF,INF,INF,INF,INF}，{ 1,INF,INF,INF,INF,INF, 3,INF, 5,INF}，{INF,INF,INF,INF,INF, 3,INF, 2,INF,INF}，{INF,INF,INF,INF,INF,INF, 2,INF, 8, 10}，{INF,INF,INF,INF,INF, 5,INF, 8,INF, 2}，{INF,INF,INF,INF,INF,INF,INF, 10, 2,INF}};g.vexnum=11;g.arcnum=11;for(i=0;i for(j=0;j g.edges[i][j]=A[i][j];printf(“n”);printf(“ttt华东交通大学导游咨询系统n”);menu(g);//进入导游系统，执行菜单功能 }第二篇：校园导游实验报告
第三篇：课程设计(校园导游)
第四篇：校园导游实验报告——数据结构
第五篇：数据结构课程设计校园导游咨询
点击咨询 