校园导游图

《数据结构》课程设计报告设计题目校园导游图学院名称信息工程学院专业班级计算机科学与技术（2）班姓名晁勉学号 1212210226一. 题目：校园导游图二. 设计目标通过设计一个校园导游图，进一步理解数据结构中有关于图的基本概念、定义术语、存储结构等，理解图在描述现实问题中的能力，明白数据结构在程序设计中的重要性等。

三. 问题描述给出学校的导游图（景点不少于10个），游客通过终端询问可知：任一景点的相关信息：从某一景点到另一景点的最短简单路径；游戏从校园大门进入，选一条最佳路线，使游客可以不重复地游览个景点，最后回到出口（出口就在入口旁边）。

四. 需求分析需求：（1）将导游图看作一张带权无向图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息；（2）可以通过菜单提示操作，浏览校园全部景点；（3）查看所有游览路线，将某个景点的所有路线展示给游客；（4）选择出发点和目的地，将最短路线展示给游客；（5）输入景点编号，查看某个景点的信息。

分析：完成对整个校园导游图系统的功能实现，需要对的每一项功能都有清楚的设想和认识，了解并明确每一项功能的实现需要解决的问题，选择正确并且高效的算法把问题逐个解决，最终实现程序的正确调试运行。

有以下设计思路：（1）结合本校的实际情况，选出10个景点；（2）为选出的10个景点赋上相关信息（景点编号、名称、简介）；（3）根据选出来的10个景点用邻接矩阵存储校园图。

（4）利用C语言和数据结构编写实现校园导游图系统各功能的实现；（5）根据人为赋值的路权，设计算法计算任意两点之间的最短路径并显示；（6) 综上所诉，用一个主函数把这些板块合成，生产一个菜单界面呈现在用户面前。

五. 概要设计程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。

课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。

六. 详细设计采用C语言定义相关的数据类型写出各模块的类C码算法图的定义typedefstructArCell{intadj; //路径长度}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct //图中顶点表示主要景点，存放景点的编号、名称、简介等信息，初始化图形MGraph * CreatUDN(MGraph *G)//接受用户输入{inti,j,k,w;char v1[20],v2[20];printf("请输入图的顶点数,弧数:");scanf("%d%d",&G->vexnum,&G->arcnum);printf("请输入景点的编号、名称、简介:\n");for(i=0;i<G->vexnum;i++){printf("景点编号:");scanf("%d",&G->vexs->num);printf("景点名称:");scanf("%s",G->vexs[i].name);printf("景点简介:");scanf("%s",G->vexs->introduction);}for(i=0;i<G->vexnum;i++)for(j=0;j<G->vexnum;j++)G->arcs[i][j].adj=INFINITY;printf("请输入路径长度:\n");for(k=0;k<G->arcnum;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 main(){printf("\n 榆林学院导游图 \n");printf("********************************************\n");printf(" * 1.浏览校园全景 *\n");printf(" * 2.查看所有游览路线 *\n");printf(" * 3.选择出发点和目的地 *\n");printf(" * 4.查看景点信息 *\n");printf(" * 5.退出系统 *\n");printf(" ********************************************\n");printf("请选择您所需要的操作:");}画出主要函数的流程图七.测试分析白盒：查看代码完整性代码完整。

黑盒：测试是否可以正确的初始化，编码，译码，打印哈夫曼树等操作黑盒检测：打开VC++6.0开发环境，编译连接程序是否有错；连接生成可执行exe文件八. 使用说明首先启动VC++开发环境，新建工程project，设定工程project 的名称和保存位置，工程的描述信息生产，从而建立了一个空的工程文件。

向工程中添加新建源代码的类型、名称、保存位置，设定源代码的类型、名称并添加到工程中，在源代码文件添加程序代码，编写完成后编译，查看运行结果。

注意：一个工程project中可以有多个源文件、多个头文件；但这些段代码文件中只能出现一个main函数，作为整个程序运行的入口；必须关闭前一次程序运行结果窗口，才能进行下一次程序运行。

编译程序无错后运行，根据主菜单提示输入所需要的操作，当输入1-5时显示运行结果，否则重新输入。

操作结束后，根据提示再选择景点时，当输入0-9显示运行结果，否则重新输入，操作完成后，根据菜单提示退出系统，运行结束。

九.测试数据1.主菜单2.校园各景点展示3.景点路线4.从出发点到目的地的路线5.景点信息查询十. 课程设计总结通过课程设计，使我对《数据结构》这门课程有了更深一步的认识。

它是计算机程序设计的重要理论技术基础，在软件专业的学习中占据着十分重要的地位。

同时也使我知道，要学好这门课程，基础是非常重要的，比如说以前学习的C语言为这门课、为程序的设计打下了重要的基础。

也让我明白，上课认真听讲通过编写实验代码和调试运行，我们可以逐步积累调试C程序的经验并逐渐培养我们的编程能力、增强用计算机解决世界问题的能力。

在课程设计过程中，总会感觉无从下手。

因为上课时听的理论知识，各种算法总感觉挺似容易理解的，但是在真正的运用过程中，却不能把理论知道很好的和实践结合起来。

因此，在学知识的过程中，一定要多动手、动脑，将所学的知识熟练掌握，自如运用。

课程设计具有较强的可应用性和实践性，也是一个很考验毅力的过程，一个小小的错误就会导致整个程序出错，代价就是花费更长的时间去解决。

因此，我们应该认真的对待课程设计，无论是编程设计还是分析总结都应该做到尽善尽美，这样才能提高我们的学习能力，为自己以后的发展打下扎实的基础。

此外，对程序的测试应该要仔细，以确保各个模块的正确性和完整性，最后集成起来测试其是否正确和完整地实现了问题描述中要求的功能。

通过运用《数据结构》中的算法思想并结合C语言的基本知识，编写校园导游图的程序设计，使我受益匪浅，也让我明白了自己在这方面知识上的欠缺，比如不能完整的编写一个程序使之如自己预想的那样呈现在主菜单上，当然，我一定会再接再厉，努力改进，提高自己。

源程序代码：#include<stdlib.h>#include<stdio.h>#include<conio.h>#include<string.h>#define INFINITY 10000#define MAX_VERTEX_NUM 40#define MAX 40typedefstructArCell{intadj; //路径长度}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct //图中顶点表示主要景点，存放景点的编号、名称、简介等信息，{char name[30];intnum;char introduction[100];//简介}infotype;typedefstruct{infotypevexs[MAX_VERTEX_NUM];AdjMatrix arcs;intvexnum,arcnum;}MGraph;MGraph b;voidcmd(void);MGraphInitGraph(void);void Menu(void);void Browser(MGraph *G);voidShortestPath_DIJ(MGraph * G);void Floyd(MGraph *G);void Search(MGraph *G);intLocateVex(MGraph *G,char* v);MGraph * CreatUDN(MGraph *G);void print(MGraph *G);void main(void){system("color 0f");system("mode con: cols=140 lines=130");cmd();}voidcmd(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);}}MGraphInitGraph(void){MGraph G;inti,j;G.vexnum=10;G.arcnum=14;for(i=0;i<G.vexnum;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,"榆林学院的南大门，正门之一");strcpy(G.vexs[2].name,"13号公寓楼");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,"学院的主楼，各级领导办公的地方，外观新颖，楼内干净，设备齐全");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,"就餐窗口少，饭味不可口且价格较贵，但比旧餐厅好的是新设了卖饮品的餐位");strcpy(G.vexs[8].name,"田径场");strcpy(G.vexs[8].introduction,"塑胶跑道,人造草坪,适宜锻炼身体的好地方，学院的大型室外活动也都在此举行");strcpy(G.vexs[9].name,"2号教学楼");strcpy(G.vexs[9].introduction,"学院的多媒体教学场所,设施先进,环境良好，网速较快，是各院系学生练机的首选之地");for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++)G.arcs[i][j].adj=INFINITY;G.arcs[0][1].adj=100;G.arcs[0][2].adj=100;G.arcs[0][6].adj=800;G.arcs[1][7].adj=300;G.arcs[2][3].adj=400;G.arcs[3][6].adj=600;G.arcs[3][4].adj=200;G.arcs[4][5].adj=700;G.arcs[4][9].adj=550;G.arcs[5][9].adj=500;G.arcs[6][7].adj=900;G.arcs[6][9].adj=150;G.arcs[7][8].adj=350;G.arcs[8][9].adj=450;for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++)G.arcs[j][i].adj=G.arcs[i][j].adj;return G;}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("请选择您所需要的操作:");}void Browser(MGraph *G){int v;printf("************************************************************* ******************************************\n");printf("编号景点名称简介\n");for(v=0;v<G->vexnum;v++)printf("%-4d%-16s%-56s\n",G->vexs[v].num,G->vexs[v].name,G->vexs[v].i ntroduction);printf("************************************************************* ******************************************\n");}voidShortestPath_DIJ(MGraph * G){intv,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<G->vexnum)flag=0;}for(v=0;v<G->vexnum;v++){final[v]=0;D[v]=G->arcs[v0][v].adj;for(w=0;w<G->vexnum;w++)p[v][w]=0;if(D[v]<INFINITY){p[v][v0]=1;p[v][v]=1;}}D[v0]=0;final[v0]=1;for(i=1;i<G->vexnum;i++){min=INFINITY;for(w=0;w<G->vexnum;w++)if(!final[w])if(D[w]<min){v=w;min=D[w];}final[v]=1;for(w=0;w<G->vexnum;w++)if(!final[w]&&(min+G->arcs[v][w].adj<D[w])){D[w]=min+G->arcs[v][w].adj;for(x=0;x<G->vexnum;x++)p[w][x]=p[v][x];p[w][w]=1;}}for(v=0;v<G->vexnum;v++){if(v0!=v) printf("%s",G->vexs[v0].name);for(w=0;w<G->vexnum;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]); }}void Floyd(MGraph *G){intv,u,i,w,k,j,flag=1,p[10][10][10],D[10][10];for(v=0;v<G->vexnum;v++)for(w=0;w<G->vexnum;w++){D[v][w]=G->arcs[v][w].adj;for(u=0;u<G->vexnum;u++)p[v][w][u]=0;if(D[v][w]<INFINITY){p[v][w][v]=1;p[v][w][w]=1;}}for(u=0;u<G->vexnum;u++)for(v=0;v<G->vexnum;v++)for(w=0;w<G->vexnum;w++)if(D[v][u]+D[u][w]<D[v][w]){D[v][w]=D[v][u]+D[u][w];for(i=0;i<G->vexnum;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<G->vexnum&&j>=0&&j<G->vexnum)flag=0;}printf("%s",G->vexs[k].name);for(u=0;u<G->vexnum;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]);}void Search(MGraph *G){intk,flag=1;while(flag){printf("请输入要查询的景点编号:");scanf("%d",&k);if(k<0||k>G->vexnum){printf("景点编号不存在!请重新输入景点编号:");scanf("%d",&k);}if(k>=0&&k<G->vexnum)flag=0;}printf("************************************************************* *************************************\n");printf("编号景点名称简介\n");printf("%-4d%-16s%-56s\n",G->vexs[k].num,G->vexs[k].name,G->vexs[k].i ntroduction);printf("************************************************************* *************************************\n");}intLocateVex(MGraph *G,char* v){int c=-1,i;for(i=0;i<G->vexnum;i++)if(strcmp(v,G->vexs[i].name)==0){c=i;break;}return c;}MGraph * CreatUDN(MGraph *G)//初始化图形，接受用户输入{inti,j,k,w;char v1[20],v2[20];printf("请输入图的顶点数,弧数:");scanf("%d%d",&G->vexnum,&G->arcnum);printf("请输入景点的编号、名称、简介:\n");for(i=0;i<G->vexnum;i++){printf("景点编号:");scanf("%d",&G->vexs->num);printf("景点名称:");scanf("%s",G->vexs[i].name);printf("景点简介:");scanf("%s",G->vexs->introduction);}for(i=0;i<G->vexnum;i++)for(j=0;j<G->vexnum;j++)G->arcs[i][j].adj=INFINITY;printf("请输入路径长度:\n");for(k=0;k<G->arcnum;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){intv,w,t=0;for(v=0;v<G->vexnum;v++)for(w=0;w<G->vexnum;w++){ if(G->arcs[v][w].adj==INFINITY) printf("∞ ");elseprintf("%-7d",G->arcs[v][w].adj); t++;if(t%G->vexnum==0)printf("\n");}}。