基于C语言的数字校园问题

课程设计报告报告名称：基于C语言的数字校园问题姓名：学号：【摘要】本文利用C语言，设计了一个可供游人查询校园内道路选择的系统，可以查询查询图中任意两个地点间的所有路径，并求出最短路径，同时增加、删除、更新有关地点和道路的信息。通过模拟得到测试结果。关键词：数字校园、最短路径一、设计目标事实上，如果是初来乍到的人到电子科大来，难免会遇到迷路或者不知道走哪条路最近的问题。本设计就是为了达到给他们提供这样信息的目的，设计一个方便查询各地点路径的系统。即设计一个简易的数字校园系统,实现道路的选择。二、设计要求设计一个系统，要求完成以下功能：12、查询图中任意两个地点间的最短路径。3、查询图中任意两个地点间的所有路径。4、增加、删除、更新有关地点和道路的信息。为了达到这些功能，我们可以将宿舍楼,教学楼,主楼,图书馆,食堂,超市,等等作为节点，各节点之间有道路相连,每条道路有长度，则问题转化为最优路线规划问题。因为在学校里面，人流量不算很多，车流量也可以得到控制，行人的出行基本不受干扰，则可以忽略人流量的问题。则我们需要做的工作是：1、输出顶点信息：将校园内各位置输出。2、输出边的信息：将校园内每两个位置（若两个位置之间有直接路径）的距离输出。3、修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输出每两个位置（若两个位置之间有直接路径）的距离。4、求最短路径：输出给定两点之间的最短路径的长度及途径的地点或输出任意一点与其它各点的最短路径。5、删除：删除任意一条边。6、插入：插入任意一条边。三、程序功能1、查询地点2、查询任意两地点之间的最短路径及路径长度。3、查询任意两地点之间的所有路线。4、在已有的校园导游图中添加新的地点及该地点到其他景点的路径长度。5、在已有的校园导游图中删除已有的地点及以该地点为端点的路径。6、修改已有校园导游图中的任意一个地点的名称和地点信息或任意一条路径的长度。7、重新创建一个新的学校的导游图。四、系统设计1、系统总图图1地点的名称和地点方式用Dijkstra重新创建。2、程序设计#includestdio.h#includestdio.h#includemalloc.h#includestdlib.h#defineMax20000typedefstructArcCell{intadj;/*相邻接的地点之间的路程*/}ArcCell;/*定义边的类型*/typedefstructVertexType{intnumber;/*地点编号*/charsight[100];/*地点名称*/chardescription[1000];/*地点描述*/}VertexType;/*定义顶点的类型*/typedefstruct{VertexTypevex[20];/*地点*/ArcCellarcs[20][20];/*地点间的距离*/intvexnum,arcnum;/**/}MGraph;/*定义图的类型*/MGraphG;/*把图定义为全局变量*/charnameofschool[100];intNUM=9;intP[20][20];/**/intp[20];/**/intvisited[20];/**/inta=0;/**/longintD[20];/*辅助变量存储最短路径长度*/intx[20]={0};voidCreateUDN(intv,inta);/*造图函数*/voidnarrate();/*说明函数*/voidShortestPath(intnum);/*最短路径函数*/voidoutput(intsight1,intsight2);/*输出函数*/charMenu();/*主菜单*/voidsearch();/*查询地点信息*/charSearchMenu();/*查询子菜单*/voidHaMiTonian(int);/*哈密尔顿图的遍历*/voidSearchpath1(MGraphg);/*查询两个地点间的所有路径*/voiddisppath(MGraphg,inti,intj);voidpath(MGraphg,inti,intj,intk);/*确定路径上第k+1个顶点的序号*/voidNextValue(int);voiddisplay();/*显示遍历结果*/intAddnewsight(intn);/*添加新的地点和路径*/intDeletesight(intn);/*删除地点和路径*/voidChangesight();/*修改地点和路径*/charChangemenu();/*修改路径或顶点的选择菜单*/charSightmenu();/*选择需该地点的菜单*/voidNewCreateUDN();/*创建新的导游图*/voidmain()/*主函数*/{intv0,v1;charck;system(color2);CreateUDN(NUM,11);do{ck=Menu();switch(ck){case'1':search();break;case'2':system(cls);narrate();printf(\n\n\t\t\t请选择起点地点0%d,NUM-1);scanf(%d,&v0);printf(\t\t\t请选择终点地点0%d,NUM-1);scanf(%d,&v1);ShortestPath(v0);/*计算两个地点之间的最短路径*/output(v0,v1);/*输出结果*/printf(\n\n\t\t\t\t请按任意键继续...\n);getchar();getchar();break;case'3':system(cls);narrate();x[0]=1;Searchpath1(G);printf(\n\n\t\t\t\t请按任意键继续...\n);getchar();getchar();break;case'4':system(cls);narrate();NUM=Addnewsight(NUM);system(cls);narrate();break;case'5':NUM=Deletesight(NUM);break;case'6':Changesight();break;case'7':NewCreateUDN();break;};}while(ck!='e');}charMenu()/*主菜单*/{charc;intflag;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┃4、添加新的地点和路径┃\n);printf(\t\t\t┃5、删除已有地点和路径┃\n);printf(\t\t\t┃6、修改已有地点和路径┃\n);printf(\t\t\t┃7、创建新的校园导游图┃\n);printf(\t\t\t┃e、退出┃\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=='4'||c=='5'||c=='6'||c=='7'||c=='e')flag=0;}while(flag);returnc;charSearchMenu()/*查询子菜单*/{charc;intflag;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┃e、返回┃\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=='e')flag=0;}while(flag);returnc;}voidsearch()/*查询地点信息*/{intnum;inti;charc;charname[20];do{system(cls);c=SearchMenu();switch(c){case'1':system(cls);narrate();printf(\n\n\t\t请输入您要查找的地点);scanf(%d,&num);for(i=0;iNUM;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':system(cls);narrate();printf(\n\n\t\t请输入您要查找的地点);scanf(%s,name);for(i=0;iNUM;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!='e');}voidCreateUDN(intv,inta)/*造图函数*/{inti,j;strcpy(nameofschool,电子科技大学);G.vexnum=v;/*初始化结构中的地点数和边数*/G.arcnum=a;for(i=0;i20;++i)G.vex[i].number=i;/*初始化每一个地点的编号*//*初始化每一个地点名及其地点描述*/strcpy(G.vexs[0].name,银杏大道);strcpy(G.vexs[1].name,活动中心);strcpy(G.vexs[2].name,图书馆);strcpy(G.vexs[3].name,学子食堂);strcpy(G.vexs[4].name,教学区);strcpy(G.vexs[5].name,体育馆);strcpy(G.vexs[6].name,实验楼);strcpy(G.vexs[7].name,校医院);strcpy(G.vexs[0].intro,:拥有全国最多的银杏树);strcpy(G.vexs[1].intro,:学生组织最多的地方);strcpy(G.vexs[2].intro,:藏书最多的地方);strcpy(G.vexs[3].intro,:一食堂);strcpy(G.vexs[4].intro,:品学楼);strcpy(G.vexs[5].intro,:有室内篮球场、乒乓球场、羽毛球场);strcpy(G.vexs[6].intro,:实验室最多的地方);strcpy(G.vexs[7].intro,:就是医院啦);/*这里把所有的边假定为20000地点之间是不可到达*/for(i=0;i20;++i)for(j