数据结构与算法课程设计说明书-校园导航问题

PAGEPAGE1数据结构与算法课程设计说明书

学院、系：软件学院专业软件工程设计题目：校园导航问题需求分析1.1

问题的提出针对学校现代化的实现，对于来我校的游客能够更方便的了解学校的景点，便于参观，也减少导游人员的是数量，于是编写了这个校园导航系统。1.2任务与分析校园导航模型是由景点和景点之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的顶点代表景点，用图的边代表景点之间的路径。顶点值代表景点信息，边的权值代表景点间的距离。顶点值及边的权值用直接在程序中给予赋值。优化办法(需要设计一个顺序表类。)保证每两个景点之间有多条道路并且每条路的长度不同。本系统需要查看景点平面图以及查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个数字代号。计算路径长度和最短路线时可用狄克斯特拉（Dijkastra）算法实现。平面图信息可以通过多条printf语句来实现。最后用switch选择语句选择执行浏览推荐路线或查询最短路径，并且主页面会简单描述景点的信息。2选题要求设计内容：设计学校的平面图（至少包括10个以上的场所）。每两个场所间可以有不同的路，且路长也可能不同；（2）提供起始点与终点能自动找出从任意场所到达另一场所的最佳路径（最短路径）。设计要求：(1)符合课题要求，实现相应功能；(2)要求界面友好美观，操作方便易行；(3)注意程序的实用性、安全性；3程序设计方法及主要函数介绍3.1概要设计查询功能:

ShortestPath()函数查询两景点间的最短路径长度和最短路径路线需要写求最短路径的函数来实现，而对于最短路径用上图的边的权值问题由创建无向图(或者有向网)函数实现，详细设计模块有具体说明。显示功能:show()函数在校园导航系统的首页就要显示主要的选择菜单，而菜单则由主函数调用主菜单和造图函数以及说明函数来实现。在进行查询两景点的路径时也会显示路径，则有一个输出函数执行。以及显示校园的景点平面图(至少包含10个景点)校园导航问题3.2总体设计框架图校园导航问题查询景点路线显示导航地图退出查询景点路线显示导航地图退出图3.1总体设计框架图3.3

程序运行平台Windows

7

DEV4.9923.4详细设计及流程图ShortestPath()函数开始开始所有顶点的最短路径都求出？所有顶点的最短路径都求出？结束Yes结束No选取不在S中且具有最小距离的顶点选取不在S中且具有最小距离的顶点找到最小的顶点？找到最小的顶点？Yes修改不在S中顶点的最小距离No修改不在S中顶点的最小距离顶点加入S中顶点加入S中图3.4-1ShortestPath()函数流程图4程序源代码（包括注释）#include<stdio.h>#include<conio.h>#include<string.h>#include<stdlib.h>#include<time.h>#defineMax65535#defineNUM15typedefstructArcCell{intadj;}ArcCell;typedefstructVertexType{intnumber;char*sight;char*description;}VertexType;typedefstruct{VertexTypevex[NUM];ArcCellarcs[NUM][NUM];intvexnum,arcnum;}MGraph;MGraphG;intP[NUM][NUM];//起始景点和终止景点对应的数字编号二维数组longintD[NUM];//最短路径长度表示数组voidCreateUDN(intv,inta);voiddeclare();voidShortestPath(intnum);voidoutput(intsight1,intsight2);charMenu();voidshow1();intmain()/*主函数*/{chari;system("color4f");/*修改控制台的颜色信息,中北大学特有的红色风格*/system("modecon:cols=150lines=140");/*设置批处理运行时窗口大小的*/ CreateUDN(NUM,27);Menu();}voidshow1()/*校园部分地图展示函数*/{ printf("\t\t★★欢迎使用中北大学校园导航系统★★\n");time_tt; t=time(NULL);//获取当前系统的日历时间 printf("\t\t现在的时间是%s",ctime(&t));//输出本地时间 printf("\t\t\t\t中北大学平面图:\n\n"); printf("\t0学校南门\n"); printf("\t┃\n"); printf("\t┏━━1德怀楼━━━━━━━━2酬学楼\n"); printf("\t┃┃\n"); printf("\t┃┃\n"); printf("\t┃┃\n"); printf("\t┃┃\n"); printf("\t3工字楼┃\n"); printf("\t┃┃\n"); printf("\t4勤学楼┃\n"); printf("\t┃┃\n"); printf("\t5诚学楼━━━━━━━6明学楼━━┃\n"); printf("\t┃\n"); printf("\t7柏林园\n"); printf("\t┃\n"); printf("\t8龙山公园━━9广播站━━━━10鸿学楼━━━11图书馆\n"); printf("\t┃┃\n"); printf("\t┃┃\n"); printf("\t━━━━━━━━12中央大道━━━━━━━13瑞学楼━━━14思学楼\n");}charMenu()/*主菜单*/{declare();//调用介绍函数intv0,v1;inti=1,j;while(i){printf("\n");/*功能菜单*/printf("请输入要选择操作的数字:\n");printf("\t\t\t2.显示导航地图\n");printf("\t\t\t1.查询景点路线\n");printf("\t\t\t0.退出\n");scanf("%d",&j);switch(j){case0:printf("\n\t\t\t谢谢使用中北大学校园导航系统!\n"); exit(0);break;case1:system("cls");show1(); printf("\n\n\t\t\t请选择起点景点（0～14）："); scanf("%d",&v0); printf("\t\t\t请选择终点景点（0～14）："); scanf("%d",&v1); ShortestPath(v0); output(v0,v1); printf("\n\n\t\t\t\t请按任意键继续...\n"); getchar(); getchar(); system("cls");break;case2:show1(); printf("\n\n\t\t\t\t请按任意键继续...\n"); getchar(); getchar();break;default:printf("\n输入无效，请重新选择操作!\n");break;}}return0;}voidCreateUDN(intv,inta)/*构造无向图函数*/{inti,j;G.vexnum=v;//图的顶点G.arcnum=a;//图的弧数for(i=0;i<G.vexnum;++i) G.vex[i].number=i; G.vex[0].sight="学校南门";G.vex[0].description="漂亮，气派";//顶点的附加信息 G.vex[1].sight="德怀楼";G.vex[1].description="元帅雕塑巍巍矗立的地方"; G.vex[2].sight="酬学楼";G.vex[2].description="传说中最阴森的教学楼"; G.vex[3].sight="工字楼";G.vex[3].description="俯视图形似工这个汉字"; G.vex[4].sight="勤学楼";G.vex[4].description="破破旧旧的教学楼"; G.vex[5].sight="诚学楼";G.vex[5].description="教学楼"; G.vex[6].sight="明学楼";G.vex[6].description="教学楼"; G.vex[7].sight="柏林园";G.vex[7].description="散心的好去处"; G.vex[8].sight="龙山公园";G.vex[8].description="永远阻挡不了驴友的脚步"; G.vex[9].sight="广播站";G.vex[9].description="中北之声"; G.vex[10].sight="鸿学楼";G.vex[10].description="艺术学院楼,浓郁的艺术气息"; G.vex[11].sight="图书馆";G.vex[11].description="充满学习氛围的地方"; G.vex[12].sight="中央大道";G.vex[12].description="路也许真的很宽"; G.vex[13].sight="瑞学楼";G.vex[13].description="教学楼"; G.vex[14].sight="思学楼";G.vex[14].description="教学楼"; for(i=0;i<G.vexnum;++i) for(j=0;j<G.vexnum;++j)//行列控制无向图路径长度(也就是权值)，邻接矩阵表示法 G.arcs[i][j].adj=Max;//弧v1,v2的权值如果为最大值就说明此路不通。 G.arcs[0][1].adj=G.arcs[1][0].adj=41; G.arcs[0][2].adj=G.arcs[2][0].adj=135; G.arcs[0][3].adj=G.arcs[3][0].adj=193; G.arcs[1][2].adj=G.arcs[2][1].adj=97; G.arcs[1][3].adj=G.arcs[3][1].adj=155; G.arcs[1][4].adj=G.arcs[4][1].adj=203; G.arcs[2][4].adj=G.arcs[4][2].adj=148; G.arcs[3][5].adj=G.arcs[5][3].adj=91; G.arcs[5][7].adj=G.arcs[7][5].adj=152; G.arcs[3][6].adj=G.arcs[6][3].adj=116; G.arcs[4][6].adj=G.arcs[6][4].adj=87; G.arcs[4][7].adj=G.arcs[7][4].adj=178; G.arcs[5][8].adj=G.arcs[8][5].adj=323; G.arcs[6][8].adj=G.arcs[8][6].adj=375; G.arcs[7][8].adj=G.arcs[8][7].adj=172; G.arcs[6][9].adj=G.arcs[9][6].adj=471; G.arcs[8][9].adj=G.arcs[9][8].adj=247; G.arcs[8][10].adj=G.arcs[10][8].adj=497; G.arcs[9][10].adj=G.arcs[10][9].adj=276; G.arcs[9][11].adj=G.arcs[11][9].adj=351; G.arcs[10][11].adj=G.arcs[11][10].adj=77; G.arcs[9][12].adj=G.arcs[12][9].adj=74; G.arcs[11][12].adj=G.arcs[12][11].adj=24; G.arcs[12][13].adj=G.arcs[13][12].adj=100; G.arcs[11][13].adj=G.arcs[13][11].adj=110; G.arcs[11][14].adj=G.arcs[14][11].adj=183; G.arcs[13][14].adj=G.arcs[14][13].adj=78;}voiddeclare()/*说明函数*/{inti,k=0;printf("\n\t\t欢迎使用校园导航系统\n");printf("\t_______________________________________________________________________\n");printf("\t\t景点名称\t\t|\t景点概述\n");printf("\t________________________________|_______________________________________\n");for(i=0;i<NUM;i++)//循环输出景点及其对应的介绍{ printf("\t%c(%2d)%-10s\t\t|\t%-30s%c\n",4,i,G.vex[i].sight,G.vex[i].description,4);//分别是边界控制的特殊符号，景点名称，景点介绍 k=k+1;}printf("\t_______________________________|_________________________________________\n");}voidShortestPath(intnum)/*迪杰斯特拉算法最短路径函数num为入口点的编号*/{intv,w,i,t;intfinal[NUM];intmin;for(v=0;v<NUM;v++){ final[v]=0; D[v]=G.arcs[num][v].adj;for(w=0;w<NUM;w++) P[v][w]=0;//设置空路径if(D[v]<65535){ P[v][num]=1; P[v][v]=1;}}D[num]=0;//初始化，num顶点属于集合final[num]=1;for(i=0;i<NUM;++i)//开始主循环，每次求得输入的起点景点到终点顶点的最短路径，并且加入顶点弧集合{ min=Max;//先给出最近距离 for(w=0;w<NUM;++w) if(!final[w])//w顶点在集合中 if(D[w]<min) { v=w;min=D[w];//w顶点距离输入的起始景点更近 } final[v]=1;//把距离输入的起始景点更近的加入集合中 for(w=0;w<NUM;++w)//更新当前最短路径及距离 if(!final[w]&&((min+G.arcs[v][w].adj)<D[w]))//修改D[w]和P[w] { D[w]=min+G.arcs[v][w].adj; for(t=0;t<NUM;t++) P[w][t]=P[v][t]; P[w][w]=1;//P[w]=P[v]+P[w] } }}voidoutput(intsight1,intsight2)/*输出函数*/{ inta,b,c,d,q=0; a=sight2;//这个是要到达的景点 if(a!=sight1)//要保证出发和结束不一样 { printf("\n\t从%s到%s的最短路径是",G.vex[sight1].sight,G.vex[sight2].sight); prin