数据结构课程设计作业(校园导游).doc

数据结构课程设计Course Design of Data Structure计算机科学与技术082姓名：* * * 学号：08422137指导老师：* * *2010年7月9日目 录1需求分析说明2概要设计说明3详细设计说明4调试分析5课程设计总结6参考书目7致谢需求分析说明随着高校校园的逐渐扩展，来访校园的人士逐渐增多， 随着校园透明度的提高，各界人士对学术氛围的追求，越来越多的人走进了大学校园，走进了象牙塔，这片静土也以它崭新的面貌，迎接着所有的到来者，以前封闭以及半封闭的校园状况随之改变，派生的是它积极的迎接挑战的状态。高等院校，历来以其悠久的历史、深厚的文化底蕴、优美的自然和人文景观吸引着人们的目光。高校校园旅游在掀起“羞答答的头盖“后，正悄然走向市场，当今高校在确立了旅游的市场可行性之后，随之而来的导游系统是势在必行，高校的旅游可以让人陶冶情操，也可以让人对学术产生浓厚的兴趣。那么如何更好的更科学的更科学的组织好高校导游，如何更方便更便捷的把高校的校园展示给世人，就成为了一个需要解决的问题。利用计算机建立一个自动的导游系统，可以很好的解决这个问题。当客人来访时，系统可以根据客人指定的景点给予相关的信息，游客可以方便的了解到每个景点的详细信息，同时可以通过系统找到起始点和终点的多条路径，通过系统的分析后，能得出一条最短路径。各个景点的全景图、局部图可以在景点浏览中找到，付予语音、图片以及相关文字说明，让游客轻轻松松掌握景点信息。概要设计说明用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求实现以下功能：（1）查询各景点的相关信息。（2）查询图中任意两个景点间的最短路径。（3）查询图中任意两个景点间的所有路径。用图的结点代表景点，用图的边代表景点意见的路径，首先设计一个图类，结点值代表景点的信息，边的权值代表景点之间的距离，结点值及边的权值用顺序表存储，所以需要设计一个顺序表类，本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个编号，用结构体类型来实现。计算路径长度和最短路线是可以用Dijkstra(迪杰斯特拉)算法实现，在主函数中用switch选择语句执行浏览景点信息或查询最短路径typedef struct ArCellint adj; /路径长度ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /图中顶点表示主要景点，存放景点的编号、名称、简介等信息，char name30;int num;char introduction200;/简介infotype;typedef structinfotype vexsMAX_VERTEX_NUM;/景点AdjMatrix arcs;/路径数组int vexnum,arcnum;/景点数，路径长度记录MGraph;void cmd(void);/在主函数中用来调用其他应用子函数的函数声明MGraph InitGraph(void);/用来构造学校地图的子函数 返回MGraph类型void Menu(void);/菜单函数；void Browser(MGraph *G);/调用MGraph类型的地址，进行void ShortestPath_DIJ(MGraph * G);/迪杰斯特拉算法求最短路径的子函数void Floyd(MGraph *G);/佛洛伊德算法void Search(MGraph *G);/寻找要查询的景点，并输出该景点的信息int LocateVex(MGraph *G,char* v);/定点位置MGraph * CreatUDN(MGraph *G);/初始化图形，接受用户输入void print(MGraph *G);/打印输出子函数详细设计说明#define INFINITY 10000 /*无穷大*/#define MAX_VERTEX_NUM 40#define MAX 40#include#include#include#includetypedef struct ArCellint adj; /路径长度ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /图中顶点表示主要景点，存放景点的编号、名称、简介等信息，char name30;int num;char introduction200;/简介infotype;typedef structinfotype vexsMAX_VERTEX_NUM;/景点AdjMatrix arcs;/路径数组int vexnum,arcnum;/景点数，路径长度记录MGraph;MGraph b;/全局变量 void cmd(void);/在主函数中用来调用其他应用子函数的函数声明MGraph InitGraph(void);/用来构造学校地图的子函数 返回MGraph类型void Menu(void);/菜单函数；void Browser(MGraph *G);/调用MGraph类型的地址，进行void ShortestPath_DIJ(MGraph * G);/迪杰斯特拉算法求最短路径的子函数void Floyd(MGraph *G);/佛洛伊德算法void Search(MGraph *G);/寻找要查询的景点，并输出该景点的信息int LocateVex(MGraph *G,char* v);/定点位置MGraph * CreatUDN(MGraph *G);/初始化图形，接受用户输入void print(MGraph *G);/打印输出子函数/*/void main(void)system(color 1f);/设置调试窗口背景和字体颜色system(mode con: cols=140 lines=130);/设置调试窗口的大小cmd();/用该函数来调用其他需要用到的函数/*/void cmd(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);/*MGraph InitGraph(void)/构造校园地图MGraph G;int i,j;G.vexnum=10;/景点数量G.arcnum=14;/路径数量for(i=0;iG.vexnum;i+)G.vexsi.num=i;/对景点进行对应编号 /*对对应的景点编号进行命名，输入简介*/strcpy(G.,行政楼); strcpy(G.roduction,学校的行政机构);strcpy(G.,图书馆);strcpy(G.roduction,藏书200万册,设施良好，环境幽雅);strcpy(G.,新理科楼);strcpy(G.roduction,学校最气派的教学楼，里面的设施比较好); strcpy(G.,川味府);strcpy(G.roduction,里面有南方各种美食，就餐环境幽雅);strcpy(G.,洗浴中心);strcpy(G.roduction,学校唯一的澡堂，在川味府旁边);strcpy(G.,中心体育场);strcpy(G.roduction,化塑胶跑道,人造草坪,适宜锻炼身体的场所);strcpy(G.,会堂);strcpy(G.roduction,学校有大型的晚会都在这里举行);strcpy(G.,钟楼广场);strcpy(G.roduction,是连大学子展现才华的地方，旁有邮局);strcpy(G.,新文科楼);strcpy(G.roduction,里面包含几个学院);strcpy(G.,清缘超市);strcpy(G.roduction,学校最大的超市，里面有很多学生使用的商品);/对有路的各景点之间的路径长度进行设置,没路的设置为无穷大 for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+)G.arcsij.adj=INFINITY;G.arcs01.adj=100;G.arcs02.adj=150;G.arcs06.adj=200;G.arcs17.adj=150;G.arcs23.adj=50;G.arcs36.adj=50;G.arcs34.adj=20;G.arcs45.adj=200;G.arcs49.adj=150;G.arcs59.adj=350;G.arcs67.adj=60;G.arcs69.adj=80;G.arcs78.adj=50;G.arcs89.adj=20;/无向图的路径是相互的 for(i=0;iG.vexnum;i+)for(j=0;j:);/*/输出所有景点信息void Browser(MGraph *G)int v;printf(n);printf(编号景点名称 简介 n);for(v=0;vvexnum;v+)printf(%-4d%-16s%-58sn,G-vexsv.num,G-,G-roduction);printf(n);/*/ 迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0为起点void ShortestPath_DIJ(MGraph * G)int v,w,i,min,t=0,x,flag=1,v0; int final20, D20, p2020;while(flag)printf(请输入一个起始景点编号:);scanf(%d,&v0);if(v0G-vexnum)printf(景点编号不存在!请重新输入景点编号:);scanf(%d,&v0);if(v0=0&v0vexnum)flag=0;for(v=0;vvexnum;v+)finalv=0;Dv=G-arcsv0v.adj;for(w=0;wvexnum;w+)pvw=0;if(DvINFINITY)pvv0=1;pvv=1;Dv0=0;finalv0=1;for(i=1;ivexnum;i+)min=INFINITY;for(w=0;wvexnum;w+)if(!finalw)if(Dwmin)v=w;min=Dw;finalv=1;for(w=0;wvexnum;w+)if(!finalw&(min+G-arcsvw.adjarcsvw.adj;for(x=0;xvexnum;x+) pwx=pvx;pww=1;for(v=0;vvexnum;v+)if(v0!=v) printf(%s,G-);for(w=0;wvexnum;w+)if(pvw&w!=v0) printf(-%s,G-);t+;if(tG-vexnum-1&v0!=v)printf( 总路线长%dmnn,Dv);/ShortestPath_DIJ end/*void Floyd(MGraph *G)int v,u,i,w,k,j,flag=1,p101010,D1010;for(v=0;vvexnum;v+)for(w=0;wvexnum;w+)Dvw=G-arcsvw.adj;for(u=0;uvexnum;u+)pvwu=0;if(DvwINFINITY)pvwv=1;pvww=1;for(u=0;uvexnum;u+)for(v=0;vvexnum;v+)for(w=0;wvexnum;w+)if(Dvu+DuwDvw)Dvw=Dvu+Duw;for(i=0;ivexnum;i+)pvwi=pvui|puwi;while(flag)printf(请输入出发点和目的地的编号:);scanf(%d%d,&k,&j);if(kG-vexnum|jG-vexnum)printf(景点编号不存在!请重新输入出发点和目的地的编号:);scanf(%d%d,&k,&j);if(k=0&kvexnum&j=0&jvexnum)flag=0;printf(%s,G-);for(u=0;uvexnum;u+)if(pkju&k!=u&j!=u)printf(-%s,G-);printf(-%s,G-);printf( 总路线长%dmn,Dkj);/Floyd end/*/寻找要查询的景点，并输出该景点的信息void Search(MGraph *G)int k,flag=1;while(flag)printf(请输入要查询的景点编号:);scanf(%d,&k);if(kG-vexnum)printf(景点编号不存在!请重新输入景点编号:);scanf(%d,&k);if(k=0&kvexnum)flag=0;printf(n);printf(编号景点名称 简介 n);printf(%-4d%-16s%-56sn,G-vexsk.num,G-,G-roduction);printf(n);/Search end/*int LocateVex(MGraph *G,char* v) int c=-1,i;for(i=0;ivexnum;i+)if(strcmp(v,G-)=0)c=i;break;return c;/*MGraph * CreatUDN(MGraph *G)/初始化图形，接受用户输入int i,j,k,w;char v120,v220;printf(请输入图的顶点数,弧数:);scanf(%d%d,&G-vexnum,&G-arcnum);printf(请输入景点的编号:、名称、简介:n);for(i=0;ivexnum;i+)printf(景点编号:);scanf(%d,&G-vexs-num);printf(景点名称:);scanf(%s,G-);printf(景点简介:);scanf(%s,G-vexs-introduction);for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)G-arcsij.adj=INFINITY;printf(请输入路径长度:n);for(k=0;karcnum;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-arcsij.adj=w;G-arcsji=G-arcsij; return G;/*void print(MGraph *G)int v,w,t=0;for(v=0;vvexnum;v+)for(w=0;wvexnum;w+) if(G-arcsvw.adj=INFINITY)printf( );else printf(%