C语言 校园导游图
云南大学软件学院数据结构实验报告
（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度： B □
序号学号姓名成绩
指导教师（签名）
学期：2010秋季学期
任课教师:
实验题目: 图及其应用
小组长:
联系电话:
电子邮件:
完成提交时间： 2010年 12月27日
一、【实验构思（Conceive）】(10%)
（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）
本次实验的主要目的在于熟悉图这种数据结构的表示和应用，学会运用图对实际问题进行建模和设计，以便在实际问题背景下灵活运用图和抽象数据类型的基本操作。具体要求如下：根据云南大学呈贡校区主要道路建筑示意图，测量出主要建筑（教学楼、办公楼、食堂、学生宿舍、运动场、乘车点等）之间的距离。以图为工具，建立模型，用户（师生）通过终端可询问：从某一建筑到另一建筑的最短路径，用户从校园某处（由用户选定）进入，选取一条最佳路线，使用户可以不重复地浏览各建筑，最后回到出口（出口就在入口旁边）。
基本思路：用无向网表示校区内的各建筑的平面图，图中顶点表示主要建筑，存放建筑的编号、名称、简介等信息，图中的边表示建筑间的道路，存放路径长度等信息。将导游图看作一张带权无向图，顶点表示校园的各个建筑，边表示各建筑之间的道路，边上的权值表示距离，为此图选择适当的数据结构。把各种路径都显示给用户，由用户自己选择浏览路线。首先用指针数组存储景点信息，即图中顶点和边的信息。景点数据信息由程序指定存储，然后采用迪杰斯特拉算法求出最短路径，即从人口出发，顺着某一条边开始循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合置，求得一条通路。最后调用子函数将路径结果和景点信息打印出来。
算法思想：首先构造一个无向图G并用邻接矩阵来存储，建立一个指针数组将图的信息存储起来。然后利用迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组p[v][w]来记录，最短路径长度就用一维数组D[w]存放。即从人口出发，顺着某一条边开始循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合置，求得一条通路。根据起点和终点输出最短路径和路径长度，最后调用子函数将路径结果打印出来。对于用户查询的景点信息，通过指针直接访问该图中的顶点，并将该顶点中存储的信息显示出来。
二、【实验设计(Design)】(20%)
（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）
抽象数据类型：
typedef struct ArcCell{
int adj; //相邻接的景点之间的距离
}ArcCell; //定义边的类型
typedef struct VertexType{
int number; //景点编号
char* sight; //景点名称
char* info; //景点描述
}VertexType; //定义顶点的类型
typedef struct{
VertexType vex[NUM]; //图中的顶点，即为景点
ArcCell arc[NUM][NUM]; //图中的边，即为景点间的距离
int vexnum,arcnum; //顶点数，边数
}MGraph; //定义图的类型
void main() //主函数,主要就是调用图的建立函数和路径求解函数等
char Menu() // 主菜单函数，为用户提供人性化的选择，然后调用相应的函数
void Create(int v,int a) //创建图函数，构造一个无向图G并用邻接矩阵来存储，建立一个指针数组将图的信息存储起来，包括景点的序号、名称和介绍
void List() //景点列表函数，利用for循环将顶点的信息即景点的序号和名称全部打印出来
void Path(int num) //迪杰斯特拉算法最短路径函数num为入口点的编号，利用循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合，求得一条最短的路径void Output(int sight1,int sight2) // 输出函数，输出景点的名称和sight1到sight2的最短路径长度，存放在D[]数组中
void HaMiTonian(int m) // 哈密尔顿图的遍历，递归遍历图中的各个顶点，求最短路径
void display() //显示哈密尔顿图的遍历的结果，打印出最短路径
函数的调用关系：
三、【实现描述（Implement）】(30%)
（本部分应包括：抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。）函数设计：
void main() //主函数
{
int v0,v1;
int i,num;
char flag;
Create(NUM,11);
do
{ flag=Menu();
switch(flag)
{ case '1':
system("cls"); //执行系统命令，清楚先前屏幕显示的内容
List(); //输出景点列表
printf("\n\n\t请选择起点景点（0～26）：");
scanf("%d",&v0);
printf("\t请选择终点景点（0～26）：");
scanf("%d",&v1);
Path(v0); //计算两个景点之间的最短路径
Output(v0,v1); //输出结果
printf("\n\n\t请按任意键继续...\n");
getchar(); //利用getchar()函数让程序运行到上一行时，等待按下下一个键才返回getchar(); break;
case '2':
system("cls");
List(); //输出景点列表
printf("\n\n\t请输入您要查找的景点编号：");
scanf("%d",&num);
for(i=0;i { if(num==G.vex[i].number) {printf("\n\n\t您要查找景点信息如下:"); printf("\n\n\t%s:",G.vex[i].sight); printf("\t%s\n\n",G.vex[i].info); printf("\n\t按任意键返回..."); getchar(); getchar();break; } } if(i==NUM) { printf("\n\n\t没有找到！"); printf("\n\n\t按任意键返回..."); getchar(); getchar(); } break;} }while(flag!='0');} char Menu() // 主菜单 {char c; int flag; do{ flag=1; system("cls"); List(); // 输出景点列表 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请输入您的选择："); scanf("%c",&c); if(c=='1'||c=='2'||c=='0') flag=0; }while(flag); return c; } void Create(int v,int a) //创建图函数 { int i,j; G.vexnum=v; //初始化结构中的景点数和边数 G.arcnum=a; for(i=0;i G.vex[i].number=i; //初始化每一个景点的编号 //初始化没一个景点名及其景点描述 G.vex[0].sight="云大西二门"; G.vex[0].info="云南大学西二门是目前云南大学主要的进出口"; G.vex[1].sight="百家道"; G.vex[1].info="正对西二门的一条大道，直接通向校园各个地方"; G.vex[2].sight="文典广场"; G.vex[2].info="学校举行重大活动的广场，另外还在这里举行升国旗仪式"; G.vex[3].sight="云大会堂"; G.vex[3].info="这里是学校举行重要典礼和仪式的室内场所以及学生活动中心"; G.vex[4].sight="中山邦翰楼"; G.vex[4].info="教学楼，一楼设有学生事务中心，是学生处和教务处的办公所在地"; G.vex[5].sight="仰止楼"; G.vex[5].info="云南大学图书馆"; G.vex[6].sight="桦苑"; G.vex[6].info="研究生宿舍生活区"; G.vex[7].sight="楠苑"; G.vex[7].info="经济学院、信息学院、体育学院、商旅学院、城建学院、数统学院和中加合作项目等学院的学生宿舍生活区"; G.vex[8].sight="格物楼"; G.vex[8].info="综合教学楼和自习室，一般是理工科学院的学生上公共课和自习"; G.vex[9].sight="楠苑体育场"; G.vex[9].info="学生上体育课和进行体育锻炼的地方，目前设有篮球场、网球场、排球场和田径场"; G.vex[10].sight="知味堂"; G.vex[10].info="学生餐厅，设有二个一般食堂、一个风味食堂和一个清真食堂"; G.vex[11].sight="楠苑超市"; G.vex[11].info="云南大学后勤教育超市之一，为学生提供各种生活学习用品"; G.vex[12].sight="综合服务楼"; G.vex[12].info="综合服务中心，一楼设有超市、药店、眼镜店、饰品店、农行ATM机和茶室，三楼是学校学生会、自律委、社联等各校级的办公室"; G.vex[13].sight="楸苑"; G.vex[13].info="软件学院、物科学院、化工学院、生科学院和资环学院等学院的学生宿舍生活区"; G.vex[14].sight="力行楼"; G.vex[14].info="公共教学楼，一楼设有公共机房"; G.vex[15].sight="软件楼"; G.vex[15].info="软件学院行政办公楼和实验楼"; G.vex[16].sight="校医院"; G.vex[16].info="学生医疗场所"; G.vex[17].sight="明远楼"; G.vex[17].info="教学楼，尚在建设当中"; G.vex[18].sight="至公大道"; G.vex[18].info="正对学校正大门的道路"; G.vex[19].sight="行政办公楼"; G.vex[19].info="学校行政办公部门所在地"; G.vex[20].sight="云大北门"; G.vex[20].info="学校正大门"; G.vex[21].sight="文汇楼"; G.vex[21].info="文科学院教学楼"; G.vex[22].sight="余味堂"; G.vex[22].info="学生吃饭的地方，设有二个一般食堂和一个清真食堂"; G.vex[23].sight="梓苑超市"; G.vex[23].info="超市，为学生提供各种生活学习用品"; G.vex[24].sight="梓苑"; G.vex[24].info="公管学院、人文学院、艺术学院、外国语学院和法学院的学生生活区"; G.vex[25].sight="钟楼"; G.vex[25].info="云大标志性建筑之一，每天上课的钟声从这里响起"; G.vex[26].sight="校车乘车点"; G.vex[26].info="可以在此乘坐校车至校本部"; //这里把所有的边假定为10000，含义是这两个景点之间是不可到达 for(i=0;i for(j=0;j G.arc[i][j].adj=Max; //下边是可直接到达的景点间的距离，由于两个景点间距离是互相的，所以要对图中对称的边同时赋值 G.arc[0][1].adj=G.arc[1][0].adj=10; G.arc[1][2].adj=G.arc[2][1].adj=20; G.arc[2][3].adj=G.arc[3][2].adj=20; G.arc[1][4].adj=G.arc[4][1].adj=50; G.arc[4][5].adj=G.arc[5][4].adj=200; G.arc[4][6].adj=G.arc[6][4].adj=130; G.arc[5][7].adj=G.arc[7][5].adj=600; G.arc[5][8].adj=G.arc[8][5].adj=800; G.arc[5][9].adj=G.arc[9][5].adj=600; G.arc[7][8].adj=G.arc[8][7].adj=100; G.arc[7][9].adj=G.arc[9][7].adj=600; G.arc[7][10].adj=G.arc[10][7].adj=150; G.arc[7][11].adj=G.arc[11][7].adj=110; G.arc[7][12].adj=G.arc[12][7].adj=100; G.arc[8][12].adj=G.arc[12][8].adj=80; G.arc[9][11].adj=G.arc[11][9].adj=700; G.arc[10][11].adj=G.arc[11][10].adj=5; G.arc[10][12].adj=G.arc[12][10].adj=50; G.arc[10][13].adj=G.arc[13][10].adj=150; G.arc[12][13].adj=G.arc[13][12].adj=100; G.arc[12][26].adj=G.arc[26][12].adj=20; G.arc[13][14].adj=G.arc[14][13].adj=200; G.arc[13][15].adj=G.arc[15][13].adj=250; G.arc[13][16].adj=G.arc[16][13].adj=700; G.arc[13][26].adj=G.arc[26][13].adj=100; G.arc[14][15].adj=G.arc[15][14].adj=20; G.arc[14][16].adj=G.arc[16][14].adj=500; G.arc[14][17].adj=G.arc[17][14].adj=1500; G.arc[16][17].adj=G.arc[17][16].adj=1300; G.arc[17][18].adj=G.arc[18][17].adj=50; G.arc[17][25].adj=G.arc[25][17].adj=300; G.arc[18][19].adj=G.arc[19][18].adj=30; G.arc[19][20].adj=G.arc[20][19].adj=100; G.arc[20][21].adj=G.arc[21][20].adj=950; G.arc[20][22].adj=G.arc[22][20].adj=900; G.arc[21][22].adj=G.arc[22][21].adj=150; G.arc[21][24].adj=G.arc[24][21].adj=110; G.arc[21][25].adj=G.arc[25][21].adj=750; G.arc[22][23].adj=G.arc[23][22].adj=40; G.arc[22][24].adj=G.arc[24][22].adj=120; G.arc[23][24].adj=G.arc[24][23].adj=60; G.arc[24][1].adj=G.arc[1][24].adj=300; } void List() //景点列表函数 {int i,k=0; printf("\n\t\t********************欢迎使用校园导游程序******************\n"); printf("\n\t\t**********************************************************\n"); printf("\t\t\t\t 景点名称\t\t\t"); printf("\n\t\t__________________________________________________________\n"); for(i=0;i { printf("\t\t┃\t\t(%2d)%-10s\t\t\t\t┃\n",i,G.vex[i].sight); //输出景点列表 k=k+1;} printf("\t\t__________________________________________________________\n"); } void Path(int num) //迪杰斯特拉算法最短路径函数num为入口点的编号 { int v,w,i,t; //i、w和v为计数变量 int final[NUM]; int min; for(v=0;v { final[v]=0; //假设从顶点num到顶点v没有最短路径 D[v]=G.arc[num][v].adj;//将与之相关的权值放入D中存放 for(w=0;w P[v][w]=0; if(D[v]<20000) //存在路径 { P[v][num]=1; // 存在标志置为一 P[v][v]=1; // 自身到自身 }} D[num]=0; final[num]=1; //初始化num顶点属于S集合 //开始主循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合for(i=0;i {min=Max; //当前所知离顶点num的最近距离 for(w=0;w if(!final[w]) //w顶点在v-s中 if(D[w] {v=w; min=D[w];} final[v]=1; //离num顶点更近的v加入到s集合 for(w=0;w if(!final[w]&&((min+G.arc[v][w].adj) {D[w]=min+G.arc[v][w].adj; for(t=0;t P[w][t]=P[v][t]; P[w][w]=1;}}} void Output(int sight1,int sight2) // 输出函数 {int a,b,c,d,q=0; a=sight2; //将景点二赋值给a if(a!=sight1) //如果景点二不和景点一输入重合，则进行... {printf("\n\t从*%s*到*%s*的最短路径是",G.vex[sight1].sight,G.vex[sight2].sight);//输出提示信息 printf("\t(最短距离为:%dm.)\n\n\t",D[a]); // 输出sight1到sight2的最短路径长度，存放在D[]数组中 printf("\t%s",G.vex[sight1].sight); //输出景点一的名称 d=sight1; //将景点一的编号赋值给d for(c=0;c {gate:; //标号，可以作为goto语句跳转的位置 P[a][sight1]=0; for(b=0;b {if(G.arc[d][b].adj<20000&&P[a][b]) //如果景点一和它的一个临界点之间存在路径 且最短路径 {printf("-->%s",G.vex[b].sight); //输出此节点的名称 q=q+1; //计数变量加一，满8控制输出时的换行 P[a][b]=0; d=b; // 将b作为出发点进行下一次循环输出，如此反复 if(q%9==0) printf("\n"); goto gate; //使用goto语句改变程序流向，转去执行语句标号gate所标识的语句 }//if(G.arcs[d][b].adj<20000&&P[a][b]) }//for(b=0;b } //for(c=0;c }//if(a!=sight1) } void HaMiTonian(int m) // 哈密尔顿图的遍历 { if(m>26) return; L: NextValue(m); //标号，可以作为goto语句跳转的位置 if(x[m]==0) return; if(m==26&&G.arc[0][x[26]-1].adj!=0000) display(); else HaMiTonian(m+1); goto L; //使用goto语句改变程序流向，转去执行语句标号L所标识的语句 } void NextValue(int k) { int j; l:x[k]=(x[k]+1)%10; //标号，可以作为goto语句跳转的位置 if(x[k]==0) return; if(G.arc[x[k-1]-1][x[k]-1].adj!=10000) { for(j=0;j if(x[j]==x[k]) goto l; return; } else goto l; //使用goto语句改变程序流向，转去执行语句标号l所标识的语句 } void display() { int i=0; for(i=0;i<26;i++) printf("%s->",G.vex[x[i]-1].sight); } 关键算法的时间复杂度：经分析，这个程序在用迪杰斯特拉算法求最短路径时最为复杂，其时间复杂度最大为O（i*w）,其中i、w均为计数变量。 四、【测试结果（Testing）】(10%) （本部分应包括：对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析总结） 经过对实验结果的分析和验证表明，该出现运行后能够找到某一建筑到另一建筑的最短路径，用户从校园某处（由用户选定）进入，选取一条最佳路线，使用户可以不重复地浏览各建筑，最后回到出口（出口就在入口旁边），程序编写符合题目B难度的要求，并且能够正常运行。 四、【实验总结】(10%) （本部分应包括：自己在实验中完成的任务，注意组内的任意一位同学都必须独立完成至少一项接口的实现；对所完成实验的经验总结、心得） 在这次实验中，我所编写的程序符合题目基本要求。能够找到某一建筑到另一建筑的最短路径，用户从校园某处（由用户选定）进入，选取一条最佳路线，使用户可以不重复地浏览各建筑，最后回到出口。这次使用图的建立存储和遍历最后实现了题目中导游图的建立和最短路径求解，掌握了图的存储以及图形结构上的各种操作，灵活运用数据结构解决实际问题。但是这个程序只是一个比较简单的图的建立和路径求解程序，还存在比较多的问题，例如：没有图形化的界面，不能打印出学校的示意图，用户不能直观的通过示意图来确定游览路径，还有更加广阔的运用发展空间，我们可以把它开发成一个实用性比较强的导游程序，使用户更直观的了解学校示意图。同时通过这次实验对数据结构中的抽象数据类型和图形结构的使用方法和一些基本操作有了更深的理解和运用。本次实验没有完成CDIO项目要求的任务，但是能够建立一个简单的带权无向图和自动求解最短路径的程序，但由于不是界面模式运行，应用效果不太美观，需要在今后的学习中不断改进，完善程序。 五、【项目运作描述（Operate）】(10%) （本部分应包括：项目的成本效益分析，应用效果等的分析。） 由于这个程序不是界面模式运行，几乎没有成本效益，应用效果也欠佳。 六、【代码】(10%) （本部分应包括：完整的代码及充分的注释。注意纸质的实验报告无需包括此部分。格式统一为，字体: Georgia , 行距: 固定行距12，字号: 小五） 程序源代码详见电子版实验报告！ #include #include #include #include #define Max 10000 #define NUM 27 typedef struct ArcCell{ int adj; //相邻接的景点之间的距离 }ArcCell; //定义边的类型 typedef struct VertexType{ int number; //景点编号 char* sight; //景点名称 char* info; //景点描述 }VertexType; //定义顶点的类型 typedef struct{ VertexType vex[NUM]; //图中的顶点，即为景点 ArcCell arc[NUM][NUM]; //图中的边，即为景点间的距离 int vexnum,arcnum; //顶点数，边数 }MGraph; //定义图的类型 MGraph G; //把图定义为全局变量 int P[NUM][NUM]; long int D[NUM]; //辅助变量存储最短路径长度 int x[26]={0}; void Create(int v,int a); //造图函数 void List(); //列表函数 void Path(int num); //最短路径函数 void Output(int sight1,int sight2); //输出函数 char Menu(); //主菜单 void HaMiTo nian(int); //哈密尔顿图的遍历 void NextValue(int); void display(); //显示遍历结果 void main() //主函数 { int v0,v1; int i,num; char flag; Create(NUM,11); do { flag=Menu(); switch(flag) { case '1': sy stem("cls"); //执行系统命令，清楚先前屏幕显示的内容 List(); //输出景点列表 printf("\n\n\t请选择起点景点（0～26）："); scanf("%d",&v0); printf("\t请选择终点景点（0～26）："); scanf("%d",&v1); Path(v0); //计算两个景点之间的最短路径 Output(v0,v1); //输出结果 printf("\n\n\t请按任意键继续...\n"); getchar(); //利用getchar()函数让程序运行到上一行时，等待按下下一个键才返回getchar(); break; case '2': sy stem("cls"); List(); //输出景点列表 printf("\n\n\t请输入您要查找的景点编号："); scanf("%d",&num); for(i=0;i { if(num==G.vex[i].number) { printf("\n\n\t您要查找景点信息如下:"); printf("\n\n\t%s:",G.vex[i].sight); printf("\t%s\n\n",G.vex[i].info); printf("\n\t按任意键返回..."); getchar(); getchar(); break; } } if(i==NUM) { printf("\n\n\t没有找到！"); printf("\n\n\t按任意键返回..."); getchar(); getchar(); } break; } }while(flag!='0'); } char Menu() // 主菜单 { char c; int flag; do{ flag=1; sy stem("cls"); List(); // 输出景点列表 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请输入您的选择："); scanf("%c",&c); if(c=='1'||c=='2'||c=='0') flag=0; }while(flag); return c; } void Create(int v,int a) //创建图函数 { int i,j; G.vexnum=v; //初始化结构中的景点数和边数 G.arcnum=a; for(i=0;i G.vex[i].number=i; //初始化每一个景点的编号 //初始化没一个景点名及其景点描述 G.vex[0].sight="云大西二门"; G.vex[0].info="云南大学西二门是目前云南大学主要的进出口"; G.vex[1].sight="百家道"; G.vex[1].info="正对西二门的一条大道，直接通向校园各个地方"; G.vex[2].sight="文典广场"; G.vex[2].info="学校举行重大活动的广场，另外还在这里举行升国旗仪式"; G.vex[3].sight="云大会堂"; G.vex[3].info="这里是学校举行重要典礼和仪式的室内场所以及学生活动中心"; G.vex[4].sight="中山邦翰楼"; G.vex[4].info="教学楼，一楼设有学生事务中心，是学生处和教务处的办公所在地"; G.vex[5].sight="仰止楼"; G.vex[5].info="云南大学图书馆"; G.vex[6].sight="桦苑"; G.vex[6].info="研究生宿舍生活区"; G.vex[7].sight="楠苑"; G.vex[7].info="经济学院、信息学院、体育学院、商旅学院、城建学院、数统学院和中加合作项目等学院的学生宿舍生活区"; G.vex[8].sight="格物楼"; G.vex[8].info="综合教学楼和自习室，一般是理工科学院的学生上公共课和自习"; G.vex[9].sight="楠苑体育场"; G.vex[9].info="学生上体育课和进行体育锻炼的地方，目前设有篮球场、网球场、排球场和田径场"; G.vex[10].sight="知味堂"; G.vex[10].info="学生餐厅，设有二个一般食堂、一个风味食堂和一个清真食堂"; G.vex[11].sight="楠苑超市"; G.vex[11].info="云南大学后勤教育超市之一，为学生提供各种生活学习用品"; G.vex[12].sight="综合服务楼"; G.vex[12].info="综合服务中心，一楼设有超市、药店、眼镜店、饰品店、农行ATM机和茶室，三楼是学校学生会、自律委、社联等各校级的办公室"; G.vex[13].sight="楸苑"; G.vex[13].info="软件学院、物科学院、化工学院、生科学院和资环学院等学院的学生宿舍生活区"; G.vex[14].sight="力行楼"; G.vex[14].info="公共教学楼，一楼设有公共机房"; G.vex[15].sight="软件楼"; G.vex[15].info="软件学院行政办公楼和实验楼"; G.vex[16].sight="校医院"; G.vex[16].info="学生医疗场所"; G.vex[17].sight="明远楼"; G.vex[17].info="教学楼，尚在建设当中"; G.vex[18].sight="至公大道"; G.vex[18].info="正对学校正大门的道路"; G.vex[19].sight="行政办公楼"; G.vex[19].info="学校行政办公部门所在地"; G.vex[20].sight="云大北门"; G.vex[20].info="学校正大门"; G.vex[21].sight="文汇楼"; G.vex[21].info="文科学院教学楼"; G.vex[22].sight="余味堂"; G.vex[22].info="学生吃饭的地方，设有二个一般食堂和一个清真食堂"; G.vex[23].sight="梓苑超市"; G.vex[23].info="超市，为学生提供各种生活学习用品"; G.vex[24].sight="梓苑"; G.vex[24].info="公管学院、人文学院、艺术学院、外国语学院和法学院的学生生活区"; G.vex[25].sight="钟楼"; G.vex[25].info="云大标志性建筑之一，每天上课的钟声从这里响起"; G.vex[26].sight="校车乘车点"; G.vex[26].info="可以在此乘坐校车至校本部"; //这里把所有的边假定为10000，含义是这两个景点之间是不可到达 for(i=0;i for(j=0;j G.arc[i][j].adj=Max; //下边是可直接到达的景点间的距离，由于两个景点间距离是互相的，所以要对图中对称的边同时赋值 G.arc[0][1].adj=G.arc[1][0].adj=10; G.arc[1][2].adj=G.arc[2][1].adj=20; G.arc[2][3].adj=G.arc[3][2].adj=20; G.arc[1][4].adj=G.arc[4][1].adj=50; G.arc[4][5].adj=G.arc[5][4].adj=200; G.arc[4][6].adj=G.arc[6][4].adj=130; G.arc[5][7].adj=G.arc[7][5].adj=600; G.arc[5][8].adj=G.arc[8][5].adj=800; G.arc[5][9].adj=G.arc[9][5].adj=600; G.arc[7][8].adj=G.arc[8][7].adj=100; G.arc[7][9].adj=G.arc[9][7].adj=600; G.arc[7][10].adj=G.arc[10][7].adj=150; G.arc[7][11].adj=G.arc[11][7].adj=110; G.arc[7][12].adj=G.arc[12][7].adj=100; G.arc[8][12].adj=G.arc[12][8].adj=80; G.arc[9][11].adj=G.arc[11][9].adj=700; G.arc[10][11].adj=G.arc[11][10].adj=5; G.arc[10][12].adj=G.arc[12][10].adj=50; G.arc[10][13].adj=G.arc[13][10].adj=150; G.arc[12][13].adj=G.arc[13][12].adj=100; G.arc[12][26].adj=G.arc[26][12].adj=20; G.arc[13][14].adj=G.arc[14][13].adj=200; G.arc[13][15].adj=G.arc[15][13].adj=250; G.arc[13][16].adj=G.arc[16][13].adj=700; G.arc[13][26].adj=G.arc[26][13].adj=100; G.arc[14][15].adj=G.arc[15][14].adj=20; G.arc[14][16].adj=G.arc[16][14].adj=500; G.arc[14][17].adj=G.arc[17][14].adj=1500; G.arc[16][17].adj=G.arc[17][16].adj=1300; G.arc[17][18].adj=G.arc[18][17].adj=50; G.arc[17][25].adj=G.arc[25][17].adj=300; G.arc[18][19].adj=G.arc[19][18].adj=30; G.arc[19][20].adj=G.arc[20][19].adj=100; G.arc[20][21].adj=G.arc[21][20].adj=950; G.arc[20][22].adj=G.arc[22][20].adj=900; G.arc[21][22].adj=G.arc[22][21].adj=150; G.arc[21][24].adj=G.arc[24][21].adj=110; G.arc[21][25].adj=G.arc[25][21].adj=750; G.arc[22][23].adj=G.arc[23][22].adj=40; G.arc[22][24].adj=G.arc[24][22].adj=120; G.arc[23][24].adj=G.arc[24][23].adj=60; G.arc[24][1].adj=G.arc[1][24].adj=300; } void List() //景点列表函数 { int i,k=0; printf("\n\t\t********************欢迎使用校园导游程序******************\n"); printf("\n\t\t**********************************************************\n"); printf("\t\t\t\t 景点名称\t\t\t"); printf("\n\t\t__________________________________________________________\n"); for(i=0;i { printf("\t\t┃\t\t(%2d)%-10s\t\t\t\t┃\n",i,G.vex[i].sight); //输出景点列表 k=k+1; } printf("\t\t__________________________________________________________\n"); } void Path(int num) //迪杰斯特拉算法最短路径函数num为入口点的编号 { int v,w,i,t; //i、w和v为计数变量 int final[NUM]; int min; for(v=0;v { final[v]=0; //假设从顶点num到顶点v没有最短路径 D[v]=G.arc[num][v].adj;//将与之相关的权值放入D中存放 for(w=0;w P[v][w]=0; if(D[v]<20000) //存在路径 { P[v][num]=1; // 存在标志置为一 P[v][v]=1; // 自身到自身 } } D[num]=0; final[num]=1; //初始化num顶点属于S集合 //开始主循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合 for(i=0;i { min=Max; //当前所知离顶点num的最近距离 for(w=0;w if(!final[w]) //w顶点在v-s中 if(D[w] { v=w; min=D[w]; } final[v]=1; //离num顶点更近的v加入到s集合 for(w=0;w if(!final[w]&&((min+G.arc[v][w].adj) D[w]=min+G.arc[v][w].adj; for(t=0;t P[w][t]=P[v][t]; P[w][w]=1; } } } void Output(int sight1,int sight2) // 输出函数 { int a,b,c,d,q=0; a=sight2; //将景点二赋值给a if(a!=sight1) //如果景点二不和景点一输入重合，则进行... { printf("\n\t从*%s*到*%s*的最短路径是",G.vex[sight1].sight,G.vex[sight2].sight);//输出提示信息 printf("\t(最短距离为:%dm.)\n\n\t",D[a]); // 输出sight1到sight2的最短路径长度，存放在D[]数组中printf("\t%s",G.vex[sight1].sight); //输出景点一的名称 d=sight1; //将景点一的编号赋值给d for(c=0;c { gate:; //标号，可以作为goto语句跳转的位置 P[a][sight1]=0; for(b=0;b { if(G.arc[d][b].adj<20000&&P[a][b]) //如果景点一和它的一个临界点之间存在路径且最短路径 { printf("-->%s",G.vex[b].sight); //输出此节点的名称 q=q+1; //计数变量加一，满8控制输出时的换行 P[a][b]=0; d=b; // 将b作为出发点进行下一次循环输出，如此反复 if(q%9==0) printf("\n"); goto gate; //使用goto语句改变程序流向，转去执行语句标号gate所标识的语句 }//if(G.arcs[d][b].adj<20000&&P[a][b]) }//for(b=0;b } //for(c=0;c }//if(a!=sight1) } void HaMiTo nian(int m) // 哈密尔顿图的遍历 { if(m>26) return; L: NextValue(m); //标号，可以作为goto语句跳转的位置 if(x[m]==0) return; if(m==26&&G.arc[0][x[26]-1].adj!=0000) display(); else HaMiTo nian(m+1); goto L; //使用go to语句改变程序流向，转去执行语句标号L所标识的语句} void NextValue(int k) { int j; l:x[k]=(x[k]+1)%10; //标号，可以作为goto语句跳转的位置 if(x[k]==0) return; if(G.arc[x[k-1]-1][x[k]-1].adj!=10000) { for(j=0;j if(x[j]==x[k]) goto l; return; } else goto l; //使用go to语句改变程序流向，转去执行语句标号l所标识的语句 } void display() { int i=0; for(i=0;i<26;i++) printf("%s->",G.vex[x[i]-1].sight); } 课程论文（设计）2011-2012学年第2学期 课程名称：数据结构课程设计 课程性质：实践课 专业班级： 考核方式：考查 学生姓名： 学号： 学时：1周 教师姓名： 目录 1. 作业内容 (1) 2. 基本思路 (1) 2.1 本校10个景点 (1) 2.2 图的初始化 (2) 2.3 图的遍历 (2) 2.4 求最短路径 (3) 3.系统流程 (4) 3.1 系统的简单说明 (4) 3.2 系统流程图 (5) 4. 系统运行效果图 (5) 4.1 校园导游界面 (5) 4.2 华农校园地图 (6) 4.3 景点的相关信息查询 (6) 4.4 任意两个景点间的最短路径 (7) 4.5 退出校园导游系统 (8) 5.总结 (9) 6.参考文献 (10) 1. 作业内容 设计一个校园导游程序，为来访客人提供各种信息查询任务。基本要求： （1）设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介信息，以边表示路权，存放路径长度等相关信息。 （2）为来访客人提供图中任意景点相关信息的查询 （3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 2. 基本思路 要完成对整个导游图系统的功能实现，需要对的每一项功能都有清楚的设想和认识，了解并明确每一项功能的实现需要解决的问题，选择正确并且高效的算法把问题逐个解决，最终实现程序的正确调试运行。有以下设计思路： （1）.结合本校的实际情况，选出10个景点； （2）.人为手工为选出的10个景点赋上相关信息（名称、代号、简介信息、以及路权等等）； （3）.根据选出来的10个景点用邻接矩阵存储校园图。 （4）.依照景点的相关信息创建校园图。 （5）.把纸质上的内容，利用C++编程语言编写查找景点相关信息的程序。 （6).根据人为赋值的路权，迪杰斯特拉算法计算任意两点之间的最短路径。 （7）.综上所诉，用一个主函数把这些板块合成，生产一个菜单界面呈现在用户面前。 为此，可把系统分为以下几个核心：图的初始化、图的遍历、求最佳路线。 2.1 选出本校10个景点 结合华南农业大学实际情况，我选出以下10个景点，从1到10编号： XX公园申报4A级旅游景区自查情况汇报 关键字：XX公园申报4A级旅游景区自查情况汇报 更新时间：2010-10-18 **市旅游局: 为提升景区品位，提高景区景观质量，员工服务水平和服务质量，规景区开发与管理，根据《旅游景区质量等级划分与评定》标准对AAAA级旅游区的要求，**文化主题公园拟申报AAAA级旅游区，并于2010年4月对照《旅游景区质量等级划分与评定》标准，开展了创建申报AAAA级旅游景区的自检自查工作。现将自查情况汇报如下： 一、基本情况 **文化主题公园占地面积8.5平方公里，集生态植被、峡谷、瀑布、溶洞、湖泊、溪流、壮族风情为一体，是国唯一生命文化主题公园。景区定位为“奇景观光、生命文化、水上娱乐、壮乡风情”，目前已开辟建设有图腾林、烧香石、雏凤堂、女儿湖等景点20余处。2007年4月正式对外开放，景区认真贯彻落实《旅游景区质量等级的划分与评定》标准的各项要求，坚持以诚信经营为基础，以服务游客为宗旨，努力提高景区景观质量、员工服务水平和服务质量。几年来，景区服务实现零投诉，游客综合满意率不断提升。 二、成立自检自查领导小组 旅游局及旅游公司高度重视创建申报工作，为确保创建申报工作的顺利实施，专门聘请旅游管理专家策划方案。并成立了以旅游局局长为组长，旅游公司总经理为副组长，景区管理处负责人及相关部门责任人为成员的申A创建工作领导小组，领导小组下设办公室，由凤凰谷风景区负责人为具体责任人，负责景区申报的各项筹备工作。 三、自检自查情况 创建工作领导小组于2010年4月15日按《旅游区（点）质量等级划分与评定》和《评分细则》对景区进行了自评,评分情况如下：服务与环境质量达到906分，景观质量达到87分，游客意见满意度达到95分，符合AAAA级旅游景区申报条 课程设计报告 课程名称：数据结构与算法 题目名称：校园导游系统 学生学院：数学与计算机科学系 专业班级： 2016级计算机科学与技术本科班小组组长：王明 小组成员: 王明郑双凤吕运发 指导老师：熊小颖老师 2017年10月15日 目录 一、设计目的3 二、问题描述3 三、基本要求3 四、概要设计3 五、主程序4 六、测试数据13 6.1调试程序所用数据13 6.2程序的调试结果 七、总结 一、设计目的 随着现代社会生活节奏的加快，人们外出旅行以寻求放松的时间越来越多。考虑到游客不可能对所有景点都有所了解，因此可能无法找到游玩景点最省时，最高效的路径，而人工导游成本又过高，故使用C语言，基于《数据结构》中图的相关算法开发了“南昌师范学院导游系统”。开发本系统目的在于为来访我校的游客提供一条最短游览路径，本系统从实际出发，通过对校园平面图的分析，将其转化为数据并保存在系统中，因此系统提供的路径具有较大的可信性。 二、问题描述 设计校园导游程序，为来访的客人提供服务，为来访我校的游客提供一条在游客当前位置到目的地的最短游览路径，找到游玩景点最 省时，最高效的路径。 三、基本要求 1.假设有一所校园的平面图，所含景点不小于10个，请选择适当 的坐标来表示出该图上的各个景点。 2.为来访的客人提供从当前位置到其他景点的最短路径的咨询； 3.必须具有校园平面图的修改和扩充功能（即某些景点坐标的修改 和景点个数的增加）。 四、概要设计 算法思路 本设计的重难点在于问题二的解决。利用了弗洛伊德算法函数设计Floyd() 本算法在设计时参考了《数据结构C语言版》一书中有关Floyd算法的介绍，同时借鉴了如今网上流行的设计方式。之所以选择本算法来实现计算最短路径，原因在于本算法容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。 但是，本算法缺点在于时间复杂度过高，不适合用于计算大量数据。Floyd算法首先将两景点间路径长度数据存储于数组D[v][w]中，而后使用一个三维数组用于存放最短路径所经过的顶点，接下来使用三重循环判断两景点之间直接路径是否大于间接路径，若大于，则将三维数组中存放的顶点信息更改为简介路径所经过的顶点信息。以上部分完成后，当用于标记输入数据是否合法的 1、需求分析 设计一个校园导游系统程序，为来访的客人提供各种服务的信息查询。 (1).设计工商学院校园无向图，所含的景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 (2).为来访客人提供图中任意景点相关信息的查询。 (3).为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 2、设计思路 校园旅游模型是由景点和景点之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表景点，用图的边代表景点之间的路径。所以首先应设计一个图类。结点值代表景点信息，边的权值代表景点间的距离。结点值及边的权值用顺序表存储，所以需要设计一个顺序表类。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个代码，用结构体类型实现。计算路径长度和最短路线时可用弗洛伊德（Floyd）算法实现。最后用switch选择语句选择执行浏览景点信息或查询最短路径。 3 算法设计 3.1 概要设计 3.1.1程序中包含的模块 （1）主程序模块 主函数：void main(void) void cmd(void) cmd修改显示框大小,字体背景颜色,初始化景点，景点信息打印菜单， MGraph InitGraph(void); //初始化图。 MGraph * CreatUDN(MGraph *G);//初始化图形接受用户输入 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); // 迪杰斯特拉算法计算起点各顶点间短路径, void print(MGraph *G);//输出函数 （2）查询模块 景点信息查询：void introduce() 最短路径查询：要查找的两景点的最短距离：用floyd算法求两 校园导游系统设计与实现 目录 1.设计要求 2.1需求分析 2.2概要设计 2.3各个模块名称和功能 2.4 系统导游主界面 2.4.1前台系统 2.4.2后台系统 2.4.3退出系统 3实验总结 参考文献 附件 1.设计要求 设计一个校园导游程序，为来访的客人提供各种信息查询服务。 2.1需求分析 ⑴设计学校的校园平面图。选取若干个有代表性的景点抽象成一个无向带权图（无向网），所含景点不少于30 个。以图中顶点表示校内各景点，边上的权值表示两景点之间的距离。 ⑵存放景点代号、名称、简介等信息供用户查询。 ⑶为来访客人提供图中任意景点相关信息的查询。 ⑷为来访客人提供图中任意景点之间的问路查询。 ⑸可以为校园平面图增加或删除景点或边，修改边上的权值等。 景点距离图 2.2概要设计 校园旅游模型是由景点和景点之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表景点，用图的边代表景点之间的路径。所以首先应设计一个图类。结点值代表景点信息，边的权值代表景点间的距离。结点值及边的权值用顺序表存储，所以需要设计一个顺序表类。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个代码，用结构体类型实现。计算路径长度和最短路线时可用迪杰斯特拉（Dijkastra）算法实现。最后用switch 选择语句选择执行浏览景点信息或查询最短路径。 1、主界面设计 为了实现校园导游系统各功能的管理，首先设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户使用本系统。 2、存储结构设计 本系统采用图结构类型（mgraph）存储抽象校园图的信息。其中，各景点间的邻接关系用图邻接矩阵类型（adjmatrix）存储；景点（顶点）信息用结构数组(vexs)存储，其中每个数组元素是一个结构变量，包含景点编号、景点名称及景点介绍三个分量；图的顶点个数及边的条数由分量vexnum、arcnum 表示，它们是整型数据。 3、系统功能设计 本系统除了要完成图的初始化功能外还设置了9个子功能。图的初始化由initgraph()函数实现。依据读入的图的顶点个数和边的条数，分别初始化图结构中图的顶点数组和图的邻接矩阵。9个子功能的设计描述如下。 ⑴景点信息查询 景点信息查询由函数seeabout()实现。该功能根据用户输入的景点编号输出该景点的相关信息。如景点编号、名称等。 ⑵学校景点介绍 学校景点介绍由函数browsecampus()实现。当用户选择该功能，系统即能输出学校全部景点的信息：包括景点编号、景点名称及景点介绍。 ⑶相邻的景点及其距离 为使游客能够知道其周围的景点和路径，方便他们迅速知道其所在位置和周围信息 ⑷查看浏览线路 查看浏览线路由函数shortestpath_dij()实现。该功能采用迪杰斯特拉(Dijkstra)算法实现。当用户选择该功能，系统能根据用户输入的起始景点编号，求出从该景点到其他景点的最短路径线路及距离。当用户选择该功能，系统能根据用户输入的起始景点及目的景点编号，查询任意两个景点之间的最短路径线路及距离。 ⑸更改图信息 修改一个已有景点的相关信息、删除一个景点及其相关信息、删除一条路径、加一条路径、修改路径长度、添加一个景点 ⑹数据安全防范 设置密码，能保证数据不会被随便更改，由pass()判定密码是否正确，可由changepw()函数修改密码，初始密码为gdufsx ⑺写入文件并保存修改 打开该软件，若没有graph.txt，则会由系统初始化生成一个graph.txt，若已存在该文档会由该文档中的内容初始化系统。 ⑻恢复初始状态 若数据已经显得很杂乱并很难修理，就可以启用这个功能 课程设计说明书 课程名称：数据结构与算法 设计题目：校园导游系统 院系：计算机科学与信息工程学院 学生姓名： 学号： 专业班级：计算机科学与技术信息技术方向11-1 指导教师： 2013年6月21日 课程设计任务书 校园导游系统 摘要： 随着社会经济的发展，人们接近自然的机会就越多，因此外出旅游现在被越来越多的都市人所看中，所以如何快速方便的找到我们想要的旅游景点的信息和最短路径，如何简单的修改相关的信息，就成了很重要的问题。 本设计基于图的结构，用数组表示法创建一个无向图，针对游客的实际需求，将安阳工学院的景点编号、名称、介绍等信息放入到图的顶点当中，将路径长度的信息存放在弧当中。利用弗洛伊德算法求出两个景点之间的最短路径，利用迪杰斯特拉算法来求从一个景点到其他剩余的所有景点的最短距离；用相应的函数来查找景点，并显示出它的编号，信息，简介。并进行一定的界面美化，更贴近用户，相应的提示使用户操作起来更容易。 关键词：最短路径、查找景点信息、无向图 目录 1. 设计背景 (3) 1.1程序设计内容 (4) 1.2程序设计要求 (4) 2．设计方案 (4) 2.1 校园景点图 (5) 2.2 程序模块图 (5) 2.3 主函数设计简要 (6) 2.4 各函数模块的功能 (6) 3. 方案实施 (7) 3.1 程序执行流程图 (7) 3.2 主函数设计思想 (7) 4. 结果测试 (9) 4.1 主函数功能模块测试 (9) 4.2 主函数功能测试 (9) 4.3 各功能所执行的操作 (12) 5. 结论 (12) 6. 收获与致谢 (13) 7. 参考文献 (14) 8. 附件 (14) 1. 设计背景 实验四：图（内容：某公园导游图） 一、问题描述： 公园导游系统：给出一张某公园的导游图，游客通过终端询问可知︰从某一景到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。 二、设计描述： 1.输入导游图的算法（存储方法）.本程序特地设计函数void initgraph()用于实现键盘输入图的结构； 2.可访问导游图中任一景点的算法.为此设计了函数void vist(GraphMatrix graph)用于实现访问任一景点的信息； 3.最短路径从一景点到另一景点的算法。利用floyd算法-实现每一对景点间的最短路径。 并利用void outgraph()函数实现显示起始点和终点间的最短路径和其长度； 三、程序清单： #include VexType vexs[MAXVEX]; /* 顶点信息 */ AdjType arcs[MAXVEX][MAXVEX]; /* 边信息 */ } GraphMatrix; GraphMatrix graph; //定义一个图graph typedef struct //定义最短路径ShortPath结构 { AdjType a[MAXVEX][MAXVEX]; /* 关系矩阵A，存放每对顶点间最短路径长度 */ int nextvex[MAXVEX][MAXVEX]; /* nextvex[i][j]存放vi到vj最短路径上vi的后继顶点的下标值 */ } ShortPath; ShortPath path; //定义路径path void floyd(GraphMatrix * pgraph, ShortPath * ppath) //floyd算法-用于实现每一对景点间的最短路径 { int i, j, k; for (i = 0; i < pgraph->n; i++) for (j = 0; j < pgraph->n; j++) { if (pgraph->arcs[i][j] != MAX) ppath->nextvex[i][j] = j; else ppath->nextvex[i][j] = -1; ppath->a[i][j] = pgraph->arcs[i][j]; } for (k = 0; k < pgraph->n; k++) for (i = 0; i < pgraph->n; i++) for (j = 0; j < pgraph->n; j++) { if ( ppath->a[i][k] >= MAX || ppath->a[k][j] >= MAX ) 洛阳理工学院 课程设计报告 课程名称数据结构课程设计 题目校园导游程序 课程设计任务书 1、设计题目：校园导游程序 2、设计内容与要求： [问题描述] 用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。[基本要求] （1）查询各景点的相关信息； （2）查询图中任意两个景点间的最短路径。 （3）查询图中任意两个景点间的所有路径。 （4）增加、删除、更新有关景点和道路的信息。 课程设计评语 成绩： 指导教师：_______________ 年月日 3、流程图 4、模块划分 （1）主函数：void main( ) （2）void CreateUDN(int v,int a); /* 造图函数*/ （3）void narrate(); /*说明函数*/ （4）void ShortestPath(int num); /*最短路径函数*/ （5）void output(int sight1,int sight2); /*输出函数*/ （6）char Menu(); /* 主菜单*/ （7）void search(); /* 查询景点信息*/ （8）char SearchMenu(); /* 查询子菜单*/ （9）void HaMiTonian(int); /*图的遍历*/ （10）void Searchpath1(MGraph g);/*查询两个景点间的所有路径*/ （11）void disppath(MGraph g,int i,int j); （12）void path(MGraph g,int i,int j,int k);/*确定路径上第k+1个顶点的序号*/（13）void NextValue(int); （14）void display(); /* 显示遍历结果*/ （15）int Addnewsight(int n); /*添加新的景点和路径*/ 导游咨询系统 1 需求分析编制一个为来访客人进行最短路径导游的程序 (1) 从学校的平面图上选取n 个有代表性的景点，根据用户指定的起点和终点输出相应路 径，或根据用户指定的景点输出景点的信息。 (2) .为来访客人提供图中任意景点相关信息的查询。 (3) .为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 2、设计思路校园旅游模型是由景点和景点之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表景点，用图的边代表景点之间的路径。所以首先应设计一个图类。 (草稿纸) 结点值代表景点信息，边的权值代表景点间的距离。 结点值及边的权值用顺序表存储，所以需要设计一个顺序表类。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个代码，用结构体类型实现。计算路径长度和最短路线时可用弗洛伊德( Floyd )算法实现。最后用switch 选择语句选择执行浏览景点信息或查询最短路径。 3 算法设计 一、概要设计 程序中包含的模块 (1)主程序模块主函数：void main() (2)查询模块景点信息查询：void CreateUDN() (3)打印模块打印两个景点的路径及最短距离：void display() 模块间的调用关系 主函数main()调用：void CreateUDN() void ShortestPath()/* 要查找的两景点的最短距离*/ void NextValue() void HaMiTonian() void display() /* 打印两个景点的路径及最短距离*/ 3.2 详细设计界面菜单设计：char Menu() { char c; int flag; do{ flag=1; 课题五：校园导游程序 1)问题描述 用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。 2)基本要求 （1）查询各景点的相关信息； （2）查询图中任意两个景点间的最短路径。 （3）能够将图的信息保存到文件中，并指定文件打开。 （4）增加、删除、更新有关景点和道路的信息。 附加难度：有余力的同学可以考虑用图形界面实现寻址的过程 3) 设计思想 核心数据结构定义一个图，将图保存后，对图进行面向指定节点到各个节点的最短路径的操作。可以再文件中保存多个导游图，例如保存学校图、芜湖市图等文件。开始时选择文件，将指定文件中的信息导入到内存的图中。 #define Infinity 1000 #define MaxVertexNum 35 #define MAX 40 #include 教学资料参考范本 幼儿园大班学习活动：公园导游图范文 __________________ 撰写人： __________________门：部 __________________间：时 1 / 6 设计思路： 在最近开展的“我的城市”主题活动中，幼儿关注的焦点从中国到上海，从黄浦江、东方明珠、高架路到星罗棋布的公园、绿地。他们对自己幼儿园的位置、家的所在地及周边熟悉的设施、路名都很热衷于去看一看、找一找。我园遵循生活教育的理念，提倡让幼儿从自己身边开始，与周边环境互动。我们居住的社区和幼儿园附近有一个小公园——东安公园，班里一半以上的幼儿都去过。所以，我选择了东安公园的导游图作为活动的载体：一是因为幼儿对公园比较熟悉，二是因为公园大小合适幼儿后期的真实体验。 整个教学活动主要分为三个流程：寻找游玩地点(东安公园)——观察公园导游图——根据要求，设计游玩路线。在寻找幼儿园位置的过程中充分调动幼儿已有的生活经验：观察导游图引发幼儿对各种图示、标志的经验，交流、关注身边的事物；自主设计游玩路线，这对刚升 人大班的幼儿是一种挑战，因为其中整合了空间方位、时间安排、生活习惯等要素，在师生、生生的互动中使幼儿在计划一件事情的时候能有更周全、更合理的思维方式。幼儿间的差异也是一种学习资源，幼儿尝试用符号表示路线的不同方法、有条理地介绍自己的想法，都是教师要捕捉的有价值的经验点。活动的延伸部分，我还在个体学习活动中让幼儿设计从不同的门进入、出来，引导幼儿经验的迁移。让他们能在以后的实际生活中学会运用，为生活带来方便。 活动目标： 2 / 6 1．看看、说说东安公园导游图，了解图示、标志在我们生活中的作用和意义。 2．尝试设计游玩路线，用符号、语言清楚地记录、表达自己的想法。活动准备： 1．材料准备：PPT、上海地图的局部图、东安公园导游图、彩笔每组一盒。 2．经验准备：幼儿有去公园游玩的经历，熟悉周边环境、设施。 活动过程： 一、寻找游玩地点——东安公园 通过在周边地图上找找东安公园在哪里，引导幼儿回忆，并借助图示进行有效观察。 1．引出话题：东安公园在哪里? 重庆科技学院 课程设计报告 院（系）:_电气与信息工程学院专业班级:计科普0902 设计地点（单位）____计算机基础自主学习中心I306___设计题目:_________校园导游咨询____________________ 重庆科技学院 课程设计任务书设计题目：校园导游咨询 教研室主任：指导教师：向毅、陈刘奎、熊茜 2010年 12 月 20日 摘要 现代快节奏的生活使得都市人越来越渴望亲近自然，因此外出旅游现在被越来越多的都市人所看中，所以如何快速方便的找到我们想要的旅游景点的信息和最短路径就成了一个很重要的问题。 本设计基于图的结构，创建一个无向图，针对游客的实际需求，将重庆科技学院的景点编号、名称、介绍等信息放入到图的顶点当中并保存在景点文本文件当中，将两个景点的编号和它们之间的距离当作权值也保存到权值文本文件当中，利用迪杰斯特拉算法来求从一个景点到另一个景点的最短距离，利用strcmp();函数来查找景点，并显示出它的信息，从而解决了要查找景点信息和景点之间的最短路径的问题，最后按照显示屏上的提示进行相关的操作。 关键词：无向图、查找信息、最短距离、校园导游咨询 目录 摘要.................................................................................................................................................. II 1 设计内容和要求 (1) 1.1设计内容 (1) 1.1设计要求 (1) 2 概要设计 (2) 2.1 程序的模块图 (2) 2.2 主函数的概要设计 (3) 2.3 查找介绍函数的概要设计 (3) 2.4 查找最短路径函数的概要设计 (3) 2.5 退出函数的概要设计 (3) 3 详细设计 (4) 3.1 程序的流程图 (4) 3.2 主函数的详细设计 (5) 3.3 查找介绍函数的详细设计 (5) 3.4 查找最短路径函数的详细设计 (6) 3.5 退出函数的详细设计 (8) 3.6 数据结构的详细设计 (8) 4 软件测试 (10) 4.1 菜单的测试 (10) 4.2 查找景点简介的测试 (10) 4.3 查找两个景点之间的最短距离的测试 (11) 4.4 退出的测试 (11) 5 软件使用说明 (12) 6 致谢 (13) 7 参考文献 (14) 8 附录 (15) 计算机科学与技术教研室 课程设计说明书（2014-2015学年第1学期） 注：成绩均用百分制。总成绩=平时成绩*20%+报告成绩*40%+演示与答辩成绩*40% 设计题目：校园附近门店服务查询系统 1、课程设计目的 （1）数据结构课程设计是综合运用数据结构课程中学到的几种典型数据结构，以及程序设计语言（C++语言），自行实现一个较为完整的应用系统。 （2）通过系统分析、系统设计、编程调试，写实验报告等环节，进一步掌握应用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的应用。 （3）学会将知识应用于实际的方法，提高分析和解决问题的能力，增加综合能力。 1）熟练掌握链表存储结构及其建立过程和常用操作； 2）学会自己调试程序的方法并掌握一定的技巧； 3）通过温习旧的知识，学习新知识，并提高分析和解决问题的能力。 2、课程设计正文 2.1概要设计 2.1.1 系统分析 该系统主要功能包括：增添服务信息、查询服务信息、修改服务信息、删除服务信息以及推荐路径等。 1.主程序模块：连接各种功能子模块，使用循环等待用户操作，完成程序的基本操作实现功能。 2.菜单显示模块：生成每个菜单的显示界面，使程序更简单清晰。 3.查询服务信息：用户在选择此功能模块后，按照屏幕上方提示的服务信息名称及其对应的编号，要求用户输入想要查询的服务信息的编号，回车后系统将在已存储的服务信息中进行匹配，若该景点信息尚未存储则将提示错误；若找到对应信息则系统将输出服务信息，显示于幕上方。 4.查询两服务信息最短路径：运用弗洛伊德算法，用户在选择此功能模块后，按照屏幕上方提示的服务信息名称及其对应的编号，要求用户输入起点和终点的编号,系统将在已存储的景点中进行匹配，若未找到所需查询的服务信息编号，系统将提示错误并要求用户再次输入。若输入信息合法，则回车后系统将给出最短路径，显示于屏幕上方。 5.删除服务信息：用户操作功能模块，由主程序直接调用的函数模块，将功能具象化，系统工具函数模块，先查找到所存在的服务信息，然后对用户希望删除的服务信息进行删除操作，若所要删除的服务信息不存在，则输出不存在此服务信息。 西安郵電大学 数据结构课程设计报告题目：校园导游系统 院系名称： 专业名称： 班级： 学生姓名： 学号（8位）： 指导教师： 设计起止时间：2013年12月16日~2013年12月27日 一. 设计目的 （1）了解二叉树特性、存储及其操作实现，在计算机领域运用二叉树编译代码实现一件简单实际的操作，熟练掌握二叉树的三种遍历递归与非递归的实现；（2）掌握图的两种遍历深度优先遍历和广度优先遍历，了解两者的区别和优缺点。学习在计算机中表示和处理图形结构以及绘制简单的地图并输出，熟练掌握图的逻辑结构和存储结构，学习用算法来解决实际问题； （3）掌握邻接链表和邻接矩阵的存储结构，以及这两者的区别，会用邻接链表和邻接数组两种方法来实现数据的存储与读取； （4）巩固文件的存储与读取部分，以便能够加深对文件读写的理解和更好的更熟练的实际应用； （5）学会用计算机解决实际问题，将生活中的问题数据化，然后输入到计算机中以便更快的解决，提高自己的实践能力以及自身的学习能力，加深对课本知识的理解和掌握。 二. 设计内容 <1> 设计题目：设计一个校园导游程序，并按各要求进行编程： 要求： （1）设计并显示学校的校园平面图， 地点（地点名称、地点介绍）， 路线（公里数）均不少于10个。 （2）提供图中任意地点相关信息的查询。 （3）提供图中任意地点的问路查询： 1>任意两个地点之间的一条最短的简单路径； （最短路径长度——中转次数最少） 2>任意两个地点之间的一条最佳访问路线； （带权（公里数）最短路径长度） 3>任意两个地点之间的所有简单路径。 （4）提供图中所有地点的最佳布网方案； （5）增加新地点和路线、撤销旧地点和路线。 三．概要设计 实验三：校园导游咨询 一、设计方案简介 设计一个校园导游程序，为来访的客人提供各种信息查询服务。 1）设计你所在学校的校园平面图， 2）为来访客人提供图中任意景点相关信息的查询。 3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 二、设计题目实现: 实际需求 1）设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息：以边表示路径，存放路径长度等相关信息。 2）为来访客人提供图中任意景点相关信息的查询。 3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 2）概要设计 1、校园全景一览图、显示出校园的平面图。 2、提供校园中任意景点问路查询，即求任意两个景点之间的所有路径。 3、提供校园图中多个景点的最佳访问路线查询，即求途径这过个景点的最佳（短）路径。 1．功能模块图； void Map();//校园地图 void CreateGraph();//创建图 void OutputPlace();//输出景点列表 void SearchPlace();//查询景点信息 void SearchPath();//查询最短路径 void Shortpath(int i);//计算最短路径 void Output(int sight1,int sight2);//输出函数 2．各个模块详细的功能描述。 Map();//显示校园整体的地图、包含学校各景点的详细位置 CreateGraph();//创建图、主要用来保存各景点信息 OutputPlace();//输出景点列表、供选择景点信息查询时使用 SearchPlace();//查询景点信息、景点的名称及介绍 SearchPath();//查询最短路径、两景点间最短距离 Shortpath(int i);//计算两景点间最短路径 Output(int sight1,int sight2);//输出两景点最短路径及信息 四．详细设计 1．功能函数的调用关系图 2．各功能函数的数据流程图 全局变量 Graph G; int path[NUM][NUM]; int D[NUM]; Main() CreateGraph() Map() SearchPlace() SearchPath() Outputplace() Shortpath(i); Output(i,j); #include G.vexnum=10; G.arcnum=10; for(i=0;i 实验四：图(内容：某公园导游图) 一、问题描述： 公园导游系统：给出一张某公园的导游图，游客通过终端询问可知：从某一景到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口(出口就在入口旁边) 。 、设计描述： 1. 输入导游图的算法(存储方法) .本程序特地设计函数void initgraph() 用于实现键盘输入图的结构； 2. 可访问导游图中任一景点的算法.为此设计了函数void vist(GraphMatrix graph) 用于实现访问任一景点的信息； 3. 最短路径从一景点到另一景点的算法。利用floyd 算法-实现每一对景点间的最短路径。 并利用void outgraph() 函数实现显示起始点和终点间的最短路径和其长度；三、程序清单： #include typedef float AdjType; typedef struct { int n; VexType vexs[MAXVEX]; AdjType arcs[MAXVEX][MAXVEX]; } GraphMatrix; GraphMatrix graph; int i, j, k; fOr (i = 0; i < pgraph->n; i++) fOr (j = 0; j < pgraph->n; j++) { if (pgraph->arcs[i][j] != MAX) ppath->nextvex[i][j] = j; else ppath->nextvex[i][j] = -1; ppath->a[i][j] = pgraph->arcs[i][j]; } for (k = 0; k < pgraph->n; k++) for (i = 0; i < pgraph->n; i++) for (j = 0; j < pgraph->n; j++) { if ( ppath->a[i][k] >= MAX || ppath->a[k][j] >= MAX ) continue; //定义图结构 /* 图的顶点个数 */ /* 顶点信息 */ /* 边信息 */ //定义一个图 graph typedef struct { AdjType a[MAXVEX][MAXVEX]; int nextvex[MAXVEX][MAXVEX]; } ShortPath; ShortPath path; //定义最短路径ShOrtPath 结构 /* 关系矩阵 A ，存放每对顶点间最短路径长度 */ /* nextvex[i][j] 存放 vi 到 vj 最短路径上 vi 的后继顶点的下标值 */ //定义路径 path vOid flOyd(GraphMatrix * pgraph, ShOrtPath * ppath) //flOyd 算法 -用于实现每一对景点间的最短路径 课程设计 题目公园导游图 教学院计算机学院 专业计算机网络技术 班级09网络技术（1） 姓名 指导老师冯珊、熊敬一 2010 年12 月30 日 课程设计任务书 2009～2010学年第 1学期 学生姓名：何雪梅专业班级： 09网络技术 指导教师：冯姗、熊敬一工作部门：计算机学院 一、课程设计题目:公园导游图 二、课程设计内容 给出一张某公园的导游图，游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。 三、进度安排 1．初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数； 2．完成最低要求：建立一个文件，包括5个景点情况，能完成遍历功能； 3．进一步要求：进一步扩充景点数目，画出景点图，有兴趣的同学可以自己扩充系统功能。 四、基本要求 1. 界面友好，函数功能要划分好 2. 总体设计应画一流程图 3. 程序要加必要的注释 4. 要提供程序测试方案 5. 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值 的。 教研室主任签名： 年月日 目录 摘要 1 问题描述 (3) 1.1图、无向图 (3) 1.1.1图的存储结构 (3) 1.1.2 图的邻接矩阵表示法 (3) 1.2算最短路径 (4) 1.3无向图遍历 (4) 1.4广度优先搜索 (4) 2.系统分析 (5) 2.1系统流程图 (5) 3 系统设计 (5) 3.1主要数据结构 (6) 3.2主要函数说明 (6) 3.3主要算法说明 (6) 3.3.1数组表示法 (6) 3.3.2F LOYD算法 (6) 4 心得体会 (7) 附录一：源程序 (8) 附录三：参考文献 (14)数据结构课程设计报告(校园导游系统)附有源代码
某公园申报国家4A级旅游景区自查情况汇报
校园导游系统
校园导游系统程序课程设计报告
校园导游系统设计与实现
校园导游系统
某数据结构课程设计公园导游图
校园导游程序
[精选]校园导游系统实训报告资料
校园导游系统程序
幼儿园大班学习活动公园导游图范文
基于无向图的校园导游系统数据结构课程设计报告
校园导游服务咨询系统C++(含源代码)说明书---2015
校园导游系统
校园导游咨询程序
校园导游咨询系统源代码
某数据结构课程设计公园导游图
公园导游图课程设计