校园导航系统数据结构课程设计

校园导航系统数据结构课程设计前言现代社会，新兴科技日新月异，信息千变万化，人们在渴望得到最多最广的信息的同时又渴望得到信息的路径能越来越简单，易操作，而且能在简易的操作中得到更多的信息。这就要求信息咨询系统的开发者在开发之时能尽可能的全面理解客户的想法要求，而且在开发的时候能更简易的操作和更新，这种思想都符程序设计的开发思想。本次设计任务是设计学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最正确路径〔最短路径〕，其实就是数据结构中图类的问题。将校园景点作为图的结点，将景点间的路径作为图的边，路径距离作为边的权值。这样一来，求两景点间最短路径的问题就抽象成了求图中一结点到另一结点的问题。关键字：校园导航数据结构C语言目录1引言62程序设计62.1设计时间62.2设计目的62.3设计任务62.4需求分析62.5概要设计72.5.1.设计思路和主要步骤7程序流程图82.6详细设计8学校整体局部8打印图10导航函数11查找路径12记录最短路径133调试分析134附录17总结23参考文献241引言本概要设计说明书基于之前建立的软件需求设计根底上，对“蚌埠学院校园导航系统”做出概要分析。主要解决了实现该系统需求的程序模块设计问题。包括如何把该系统划分成假设干个模块、决定各个模块之间的接口、模块之间传递的信息，以及数据结构、模块结构的设计等。在以下的概要设计报告中将对在本阶段中对系统所做的所有概要设计进行详细的说明。2程序设计2.1设计时间2015-06-01—2015-06-152.2设计目的加深对《数据结构》这门课程的进一步理解与稳固通过课程设计，培养自己的编程能力以及团队协作能力加强自己对实际问题的分析能力，以及如何更好的将一些经典的算法应用于实际2.3设计任务该导航系统为参观者提供校园主要建筑的根本信息及各建筑间的距离，同时通过该系统计算出所在位置到目的地的最短路径。2.4需求分析1.程序表达的功能：(1)main()——主函数(2)navigate()——导航函数(3)pri()——打印校园平面图函数(4)visit()——递归查找路线函数2.正确输入与输出形式：如：执行建筑查询功能：输入为：sod输出为：该建筑所在的坐标为78种有花草和一些艺术标记物输入为：ld输出为：该位置没有找到你找的建筑没有找到 执行导航功能： 输入为：请输入你所在位置：gym 输入你要的目的地：sod 输出为：打印并给出所有可能走通的线路， 计算出两地间的最短路径〔距离〕 执行显示最短路径功能： 输入为：请输入你所在位置：sod 输入你要的目的地：office 输出为：其中最短路径为： 平面图中包含最短线路图， 其行走的距离为450米2.5概要设计2.5.1.设计思路和主要步骤按照需求分析，首先我们先要把学校的整体布局给设计出来，即用一个二维数组chararr[17][22]表示学校的整体布局，并将每个建筑物用特殊的符号表示：/*2为墙壁■A办公楼◆c教学区●g草坪△p操场▓0路b图书馆★M门□m食堂○h为宿舍☆T为体育馆▲l为实验室╳*/，然后要打印出学校的整体布局,设计一个pri〔char，int〕打印出学校的整体布局。在学校里，最重要的是校园的导航系统，这样可以使人耳目一新的知道某个地方的某个地方的路径，所以设计校园导航函数是必须的，因此我们设计voidnavigate(intx)函数，在图的应用中，一个最重要的知识就是求最短路径，我们并没有用迪杰斯特拉的算法和弗洛伊德算法来实现这个功能，而是利用了迷宫求解问题中的递归意义来实现求最短路径的功能voidvisit(intqiX,intqiY,intzhX,intzhY,intx)用于查找某地点到某地点的所有路径，然后进行比拟，将最短路径用函数voidfuzhi(将最短路径存放在一个数组中)。程序流程图2.6详细设计按照需求分析中的需求，和概要设计中的各流程图的模块，进行详细设计，完善各流程的代码，详细设计如下：2.6.1学校整体局部chararr[17][22]={ /*2为墙壁■A办公楼◆c教学区●g草坪△p操场▓0路b图书馆★M门□m食堂○h为宿舍☆T为体育馆▲l为实验室╳*/ //0123456789101112131415161718192021 {'2','2','2','2','2','2','2','2','2','2','2','2','2','M','2','2','2','2','2','2','2','2'}, {'2','A','A','A','0','c','c','c','c','c','c','c','c','0','2','p','p','p','p','p','p','2'}, {'2','A','A','A','0','c','c','c','c','c','c','c','c','0','2','p','p','p','p','p','p','2'}, {'2','A','A','A','0','c','c','c','c','c','c','c','c','0','2','p','p','p','p','p','p','2'}, {'2','A','A','A','0','0','0','0','0','0','0','0','0','0','2','p','p','p','p','p','p','2'}, {'2','A','A','A','0','g','g','g','g','g','g','g','g','0','2','2','2','0','2','2','2','2'}, {'M','0','0','0','0','g','g','g','g','g','g','g','g','0','0','0','0','0','0','0','m','2'}, {'2','l','l','l','0','0','0','0','0','0','0','0','0','0','h','h','h','h','h','0','m','2'}, {'2','l','l','l','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'}, {'2','l','l','l','0','b','b','b','b','b','b','b','b','0','0','0','0','0','0','0','m','2'}, {'2','l','l','l','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','0','2'}, {'2','0','0','0','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'}, {'2','T','T','T','0','b','b','b','b','b','b','b','b','0','0','0','0','0','0','0','m','2'}, {'2','T','T','T','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'}, {'2','T','T','T','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'}, {'2','T','T','T','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','M'}, {'2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2'},};4.3.2：校园建筑信息structConstructconstruct[]={ {3,4,"office", "\n|一层为经管系办公室|\n|二层为外语系办公室|\n|三层为文教系办公室|\n|四层为计算机科学与技术系办公室|\n|五楼为数理系办公室|\n\n"}, //办公室 {4,8,"classroom","学生上课的主要区域"},//教学楼A {1,13,"northDoor","是学生经常出入的门，人流量较大"},//北门 {5,17,"playground","体育课上课的场所，学生健身的去处。"},//操场 {6,1,"westDoor","是学校的正门,前方有一个面具很多的停车区"},//西门 {7,8,"sod","种有花草和一些艺术标记物"},//草坪 {9,4,"lab","学生动手实践的教室"},//实验室 {9,7,"library","开放时间为：每天的8:00~21:00\n是老师和学生学习的好去处"},//图书馆 {9,16,"Whostel","女生宿舍楼"},//宿舍楼A {7,19,"SdiningRoom","靠近女生宿舍的食堂,饭菜口味比拟可口\n人流量较大,但只在供餐时间较短"},//食堂A {12,16,"Mhostel","男生宿舍楼"},//宿舍楼B {15,16,"Thostel","教师公寓楼"},//宿舍楼C {13,19,"TdiningRoom","靠近男生宿舍楼,供餐时间较长,随时去随时有饭"},//食堂B {14,4,"gym","内部体育设施齐全,在里面可以打篮球、打排球、打羽毛球等等"},//体育馆 {15,20,"eastDoor","学校正门，老师班车出入。"},//东门 {-1,-1,"Nofound","你找的建筑没有找到"},};打印图voidpri(chara[17][22],intbushu){ inti,j; for(i=0;i<17;i++){ for(j=0;j<22;j++){ switch(a[i][j]){ case'2':printf("■");break; case'A':printf("◆");break; case'c':printf("●");break; case'g':printf("△");break; case'p':printf("▓");break; case'0':printf("");break; case'b':printf("★");break; case'M':printf("□");break; case'm':printf("○");break; case'h':printf("☆");break; case'T':printf("▲");break; case'l':printf("╳");break; case'1':printf("╬");break; } } printf("\n"); } if(bushu>0){ printf("其行走的距离为%d米\n",bushu*50); } printf("备注:\n■为墙壁,◆办公楼,●为教学区,△为草坪,▓为操场,\n"); printf("★为图书馆,□为门,○为食堂,◆为宿舍,▲为体育馆\n╳为实验室\n");}导航函数voidnavigate(intx){ shortbushu=1000;/*用于记录最短步数*/ structConstruct*qi; structConstruct*zh; intqiX,qiY,zhX,zhY; intc; inti=1; while(i==1){ printf("请输入你所在位置:"); qi=selectName(15); if((-1)==qi->x){ printf("是否重新输入你所在地:(1/0)\n"); scanf("%d",&c); if(c==1){ i=1;}else{return;}} else i=0; }; i=1; while(i==1){ printf("输入你要的目的地:"); zh=selectName(15); if((-1)==zh->x){ printf("是否重新输入你的目的地:(1/0)\n");scanf("%d",&c); if(c==1){ i=1;}else{return;}} else i=0; } qiX=qi->x; qiY=qi->y; zhX=zh->x;zhY=zh->y;num=1; visit(qiX,qiY,zhX,zhY,x); printf("其中最短路径为:\n"); pri(jilu,shortbushu);}查找路径voidvisit(intqiX,intqiY,intzhX,intzhY,intx){ //x为标志，用于控制要不要显示所有的路径 当其非0是显示所有的路径charn=arr[qiX][qiY]; arr[qiX][qiY]='1'; bushu++; if(qiX==zhX&&qiY==zhY){ if(x){ printf("第%d条线路\n",(num++)); pri(arr,bushu); } if(shortbushu>bushu){ shortbushu=bushu; fuzhi(); } } if(arr[qiX][qiY+1]=='0')visit(qiX,qiY+1,zhX,zhY,x); if(arr[qiX+1][qiY]=='0')visit(qiX+1,qiY,zhX,zhY,x); if(arr[qiX][qiY-1]=='0')visit(qiX,qiY-1,zhX,zhY,x); if(arr[qiX-1][qiY]=='0')visit(qiX-1,qiY,zhX,zhY,x); arr[qiX][qiY]=n; bushu--;}记录最短路径voidfuzhi(){ inti,j; for(i=0;i<17;i++){ for(j=0;j<22;j++){ jilu[i][j]=arr[i][j]; } }}3调试分析4附录程序源代码：#include<stdio.h>#include<string.h>#include<stdlib.h>charjilu[17][22];/*用于记录最短路径*/voidfuzhi();/*用于给最短路径赋值*/intshortbushu=1000;/*用于记录最短步数*/intnum=1;/*记录多少条路*/intbushu=0;/*记录走了多远*/structConstructselectName(int*a,intn);/*根据名字查询位置*/voidnavigate(intx);/*导航*/voidpri(char[][22],int);//打印图voidadd();//增加建筑信息voidvisit(int,int,int,int,int);//递归查找路线chararr[17][22]={ /*2为墙壁■A办公楼◆c教学区●g草坪△p操场▓0路b图书馆★M门□m食堂○h为宿舍☆T为体育馆▲l为实验室╳*/ //0123456789101112131415161718192021 {'2','2','2','2','2','2','2','2','2','2','2','2','2','M','2','2','2','2','2','2','2','2'}, {'2','A','A','A','0','c','c','c','c','c','c','c','c','0','2','p','p','p','p','p','p','2'}, {'2','A','A','A','0','c','c','c','c','c','c','c','c','0','2','p','p','p','p','p','p','2'}, {'2','A','A','A','0','c','c','c','c','c','c','c','c','0','2','p','p','p','p','p','p','2'}, {'2','A','A','A','0','0','0','0','0','0','0','0','0','0','2','p','p','p','p','p','p','2'}, {'2','A','A','A','0','g','g','g','g','g','g','g','g','0','2','2','2','0','2','2','2','2'}, {'M','0','0','0','0','g','g','g','g','g','g','g','g','0','0','0','0','0','0','0','m','2'}, {'2','l','l','l','0','0','0','0','0','0','0','0','0','0','h','h','h','h','h','0','m','2'}, {'2','l','l','l','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'}, {'2','l','l','l','0','b','b','b','b','b','b','b','b','0','0','0','0','0','0','0','m','2'}, {'2','l','l','l','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','0','2'}, {'2','0','0','0','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'}, {'2','T','T','T','0','b','b','b','b','b','b','b','b','0','0','0','0','0','0','0','m','2'}, {'2','T','T','T','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'}, {'2','T','T','T','0','b','b','b','b','b','b','b','b','0','h','h','h','h','h','0','m','2'}, {'2','T','T','T','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','M'}, {'2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2','2'},};structConstruct{ intx; inty; charname[25]; charmiaoshu[10000];};structConstructconstruct[]={ {3,4,"office", "\n|一层为经管系办公室|\n|二层为外语系办公室|\n|三层为文教系办公室|\n|四层为计算机科学与技术系办公室|\n|五楼为数理系办公室|\n\n"}, //办公室 {4,8,"classroom","学生上课的主要区域"},//教学楼A {1,13,"northDoor","是学生经常出入的门，人流量较大"},//北门 {5,17,"playground","体育课上课的场所，学生健身的去处。"},//操场 {6,1,"westDoor","是学校的正门,前方有一个面具很多的停车区"},//西门 {7,8,"sod","种有花草和一些艺术标记物"},//草坪 {9,4,"lab","学生动手实践的教室"},//实验室 {9,7,"library","开放时间为：每天的8:00~21:00\n是老师和学生学习的好去处"},//图书馆 {9,16,"Whostel","女生宿舍楼"},//宿舍楼A {7,19,"SdiningRoom","靠近女生宿舍的食堂,饭菜口味比拟可口\n人流量较大,但只在供餐时间较短"},//食堂A {12,16,"Mhostel","男生宿舍楼"},//宿舍楼B {15,16,"Thostel","教师公寓楼"},//宿舍楼C {13,19,"TdiningRoom","靠近男生宿舍楼,供餐时间较长,随时去随时有饭"},//食堂B {14,4,"gym","内部体育设施齐全,在里面可以打篮球、打排球、打羽毛球等等"},//体育馆 {15,20,"eastDoor","学校正门，老师班车出入。"},//东门 {-1,-1,"Nofound","你找的建筑没有找到"},};voidar(){ intm,n; for(m=0;m<17;m++){ for(n=0;n<22;n++){ printf("%c",arr[m][n]); } printf("\n"); }}structConstruct*selectName(intn)/*根据名字查询位置*/{ inti; charname[15]; scanf("%s",&name); for(i=0;i<n;i++){ if(strcmp(construct[i].name,name)==0){ return&construct[i]; }} printf("给位置没有找到\n"); return&construct[15];}intmain(){ inti; intn=15; structConstruct*jianzhu; while(1){ printf("欢送来到蚌埠学院,我们将为你提供贴心的导航效劳\n"); printf("*********************************************\n"); printf("1.学校整体布局\n"); printf("2.建筑查询\n"); printf("3.导航\n"); printf("4.显示最短路径\n"); printf("5.退出\n"); printf("*********************************************\n"); scanf("%d",&i); switch(i){ case1: printf("查询位置\n"); pri(arr,0); break; case2:printf("请输入查询建筑的名称:\n");jianzhu=selectName(n); if(-1!=jianzhu->x) printf("该建筑所在的坐标为%d%d\n",jianzhu->x,jianzhu->y); printf("%s\n",jianzhu->miaoshu); break; case3: printf("导航\n"); navigate(1); break; case4: printf("其中最短路径为:\n"); navigate(0); //pri(jilu,shortbushu); break; case5: printf("退出"); exit(0); break; } }; return0;}voidnavigate(intx){ shortbushu=1000;/*用于记录最短步数*/ structConstruct*qi; structConstruct*zh; intqiX,qiY,zhX,zhY; intc; inti=1; while(i==1){ printf("请输入你所在位置:"); qi=selectName(15); if((-1)==qi->x){ printf("是否重新输入你所在地:(1/0)\n"); scanf("%d",&c); if(c==1){ i=1;}else{return;}} else i=0; }; i=1; while(i==1){ printf("输入你要的目的地:"); zh=selectName(15); if((-1)==zh->x){ printf("是否重新输入你的目的地:(1/0)\n");scanf("%d",&c); if(c==1){ i=1;}else{return;}} else i=0; } qiX=qi->x; qiY=qi->y; zhX=zh->x;zhY=zh->y;num=1; visit(qiX,qiY,zhX,zhY,x); printf("其中最短路径为:\n"); pri(jilu,shortbushu);}/*2为墙壁■A办公楼◆c教学区●g草坪△p操场▓0路b图书馆★M门□m食堂○h为宿舍◆T为体育馆▲*/voidpri(chara[17][22],intbushu){ inti,j; for(i=0;i<17;i++){ for(j=0;j<22;j++){ switch(a[i][j]){ case'2':printf("■");break; case'A':printf("◆");break; case'c':printf("●");break; case'g':printf("△");break; case'p':printf("▓");break; case'0':printf("");break; case'b':printf("★");break; case'M':printf("□");break; case'm':printf("○");break; case'h':printf("☆");break; case'T':printf("▲");br