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

1、WORD格式一、课程设计目的本课程设计的目标就是要到达理论与实际应用相结合，提高学生组织数据及编写大型程序的能力，并培养根本的、良好的程序设计技能以及合作能力。设计中要求综合运用所学知识，上机解决一些与实际应用结合严密的、规模较大的问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、结实掌握数据构造和算法设计技术，掌握分析、解决实际问题的能力。通过这次设计， 要求在数据构造的逻辑特性和物理表示、数据构造的选择和应用、算法的设计及其实现等方面，加深对课程根本内容的理解。同时，在程序设计方法以及上机操作等根本技能和科学作风方面受到比较系统和严格的训练。二、课程设计内容1) 问题描述用无

2、向网表示你所在学校的校园景点平面图， 图中顶点表示主要景点， 存放景点的编号、名称、 简介等信息， 图中的边表示景点间的道路， 存放路径长度等信息。要求能够答复有关景点介绍、游览路径等问题。2) 根本要求（ 1 查询各景点的相关信息；（ 2 查询图中任意两个景点间的最短路径。（ 3 查询图中任意两个景点间的所有路径。4增加、删除、更新有关景点和道路的信息三、课程设计过程1需求分析（ 1设计学校的校园平面图，选取出假设干的具有代表性的景点构成一个抽象的无向带权图，顶点为景点，边的权值代表了景点间路径的长度。（ 2将景点的序号，名称，介绍存放起来准备查询。（ 3提供任意景点的信息；（ 4提供任意经

3、典的路径查询及其最优路线的查询（ 5平面图景点的增加及删除，以及边和权值长度的改变专业资料整理WORD格式2概要设计专业资料整理WORD格式1：第一点是主界面的设计，首先，为了该系统各个功能的管理，设计出含有多个菜单项的主菜单界面，可以更方便的使用该系统。专业资料整理WORD格式2 ：第二点是存储构造的设计，采取了图构造类型mgraph存储校园图的信息，景专业资料整理WORD格式点信息用构造数组vexs 存储，而且利用全局变量：标志； d 数组用于存放权值和查找路径顶点的编号；visited数组用于存储顶点是否被访问campus 是一个图构造的全局变量。专业资料整理WORD格式3 ：第三点是设

4、计各个功能的实现，学校景点的介绍通过函数browsecompus()来实现；专业资料整理WORD格式查询景点间的最段路径通过Floyd( 弗洛伊德) 算法实现；查询景点间的所有路径通过allpath函数和 path 函数来实现；更改图的信息可以由主函数changegraph 以及其他函数可以实现。专业资料整理WORD格式3详细设计1主要的操作界面的显示以及无向网操作void initgraph(graph *ga)int i,j;ga->n=9;ga->e=11;for( i=0;i<ga->n;i+)ga->vexsi.num=i;strcpy(ga->v

5、," 西门 "); strcpy(ga->roduce," 学校的正大门，设有公交站 "); strcpy(ga->," 风雨篮球场 "); strcpy(ga->roduce,""); strcpy(ga->," 田径场 ");strcpy(ga->roduce," 举办运动会，平时体育跑步锻炼等 "); strcpy(ga->

6、," 京元食堂 "); strcpy(ga->roduce," 新食堂 "); strcpy(ga->," 苍霞湖畔 "); strcpy(ga->roduce," 戏称“分手湖 ，风光宜人 "); strcpy(ga->," 思源楼 "); strcpy(ga->roduce," 学校王牌土木的教学区 "); strcpy(ga-&

7、gt;," 图书馆 "); strcpy(ga->roduce," 是大学城最高的标志性建筑 "); strcpy(ga->," 北教区 "); strcpy(ga->roduce," 北校区集中的教学楼 "); strcpy(ga->," 禾堂餐厅 ");专业资料整理WORD格式strcpy(ga->roduce," 旧食堂 ");

8、for(i=0;i<ga->n;i+)for(j=0;j<ga->n;j+)ga->edgesij=1000;ga->edges01=1;ga->edges12=2;ga->edges13=5;ga->edges24=4;ga->edges34=9;ga->edges45=1;ga->edges48=1;ga->edges56=5;ga->edges57=7;ga->edges78=1;ga->edges67=9;for(i=0;i<ga->n;i+)for(j=0;j<ga-&g

9、t;n;j+)ga->edgesji=ga->edgesij;2确定顶点是否存在已经顶点是否已经被访问过来确定路径void Create_graph(graph *ga)int i,j,k,w;printf(" 请输入顶点数和边数:n");scanf("%d %d",&(ga->n),&(ga->e);printf(" 请输入景点编号，景点名字，景点介绍，建立信息表 :n"); for(i=0;i<ga->n;i+)scanf("%d",&(ga->

10、vexsi.num);gets(ga->);gets(ga->roduce);for(i=0;i<ga->n;i+)for(j=0;j<=ga->n;j+)ga->edgesij=1000;for(k=0;k<ga->e;k+)printf(" 请输入 %d 条边的景点序号i， j 和长度： ",k+1);scanf("%d %d %d",&i,&j,&w);ga->edgesij=w;ga->edgesji=w;专业资料整理W

11、ORD格式void print(graph ga)int i,j;for(i=0;i<ga.n;i+)for(j=0;j<ga.n;j+)printf("%d",ga.edgesij);if(j+1=ga.n)printf("n");void visit(graph ga)int a;printf(" 请输入景点编号：");scanf("%d",&a);int i;for( i=0;i<ga.n;i+)if(a=ga.vexsi.num)printf(" 景点编号为 %d n&q

12、uot;,ga.vexsi.num);printf(" 景点名称为 ");puts();printf(" 景点介绍为 ");puts(roduce);break;if(i=ga.n)printf(" 无此点 n");3得出景点间的最短路径void shortestpath_djst(graph ga)void shortestpath_floyd(graph ga)int i,j,k,v,u,w,d3535,p353535;for(v=0;v<ga.n;v+)专业资料整理WORD

13、格式for(w=0;w<ga.n;w+)dvw=ga.edgesvw;for(u=0;u<ga.n;u+)pvwu=0;if(dvw<1000)pvwv=1;pvww=1;for(u=0;u<ga.n;u+)for(v=0;v<ga.n;v+)for(w=0;w<ga.n;w+)if(dvu+duw<dvw)dvw=dvu+duw;for(i=0;i<ga.n;i+)pvwi=pvui|puwi;printf("n请输入出发点和目的地编号：");scanf("%d %d",&k,&j);pr

14、intf("nn");while(k<0|k>ga.n|j<0|j>ga.n)printf("n输入的编号不存在");printf("n请重新输入编号：nn");scanf("%d %d",&k,&j);printf("nn");printf("%s",);for(u=0;u<ga.n;u+)if(pkju && k!=u &&j!=u)printf("->

15、%s",);printf("->%s",);printf("nnn总长度为 %d 千米 nnn",dkj);专业资料整理WORD格式4得到景点之间的所有路径专业资料整理WORD格式void path(graph c,int m,int n,int k)int s,x=0;int t;t=k+1;if(dk=n && k<8)专业资料整理WORD格式for(s=0;s<k;s+)printf("%s->",);

16、printf("%snn",);elses=0;while(s<c.n)if(c.edgesdks<1000)&&(visiteds=0)visiteds=1;dk+1=s;path(c,m,n,t);visiteds=0;s+;void allpath(graph c)int k,i,j,m,n;printf("nn请输入您要查询的两个景点的编号:nn");scanf("%d %d",&i,&j);printf("nn");m=locateve

17、x(c,i);n=locatevex(c,j);d0=m;for(k=0;k<c.n;k+)visitedk=0;专业资料整理WORD格式visitedm=1;path(c,m,n,0);5删除边int delarc(graph &ga)int m,n,v0,v1;if(ga.e<=0)printf(" 图中已经无顶边，无法删除");return 1;printf("n请输入要删除的边的起点和终点的编号：");scanf("%d %d",&v0,&v1);m=locatevex(ga,v0);if(

18、m<0)printf(" 此顶点 %d 已删除 ",v0);return 1;n=locatevex(ga,v1);if(n<0)printf(" 此顶点 %d 已删除 ",v1);return 1;ga.edgesmn=1000;ga.edgesnm=1000;ga.e-;return 1;int enarc(graph &ga)int m,n,distance;printf(" 请输入边的起点和终点编号，权值：");scanf("%d %d %d",&m,&n,&di

19、stance);while(m<0|m>ga.n|n<0|n>ga.n)printf(" 输入错误，请重新输入：");scanf("%d %d",&m,&n);专业资料整理WORD格式if(locatevex(ga,m)<0)printf(" 此节点 %d 已经删除 ",m);return 1;if(locatevex(ga,n)<0)printf(" 此节点 %d 已经删除 ",n);return 1;ga.edgesmn=distance;ga.edgesnm

20、=ga.edgesmn;return 1;4调试分析内容包括：a调试过程中遇到的问题是如何解决的以及对设计与实现的回忆讨论和分析；b算法的时空分析(包括根本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；c经历和体会等。5用户使用说明通过主菜单提示，选择出你所想要知道的信息，然后通过输入节点来代替景点，从而得到景点间的所有路径，最短路径等其他信息。专业资料整理WORD格式6测试结果 1操作的主界面2学校景点的介绍专业资料整理WORD格式3学校景点从西门的禾堂餐厅的所有路径所有路径4学校景点从西门的禾堂餐厅的所有路径最短路径专业资料整理WORD格式5图的更改的界面6边的删除界面展示专业

21、资料整理WORD格式7附录#define MAX 100/ 数据类型的定义#include<string>#include<iostream>using namespace std;int visited35;int d35;struct viewsint num;char name10;char introduce100;typedef views datatype;typedef struct datatype vexsMAX;int edgesMAXMAX;int n,e;graph;void initgraph(graph *ga)/主要的操作界面的显示以及无向

22、网操作int i,j;ga->n=9;ga->e=11;专业资料整理WORD格式for( i=0;i<ga->n;i+)ga->vexsi.num=i;strcpy(ga->," 西门 "); strcpy(ga->roduce," 学校的正大门，设有公交站 "); strcpy(ga->," 风雨篮球场 "); strcpy(ga->roduce,""); strcpy(ga->

23、," 田径场 ");strcpy(ga->roduce," 举办运动会，平时体育跑步锻炼等 "); strcpy(ga->," 京元食堂 "); strcpy(ga->roduce," 新食堂 "); strcpy(ga->," 苍霞湖畔 "); strcpy(ga->roduce," 戏称“分手湖 ，风光宜人 "); strcpy(

24、ga->," 思源楼 "); strcpy(ga->roduce," 学校王牌土木的教学区 "); strcpy(ga->," 图书馆 "); strcpy(ga->roduce," 是大学城最高的标志性建筑 "); strcpy(ga->," 北教区 "); strcpy(ga->roduce," 北校区集中的教学楼 ");

25、strcpy(ga->," 禾堂餐厅 "); strcpy(ga->roduce," 旧食堂 "); for(i=0;i<ga->n;i+)for(j=0;j<ga->n;j+)ga->edgesij=1000;ga->edges01=1;ga->edges12=2;ga->edges13=5;ga->edges24=4;ga->edges34=9;ga->edges45=1;ga->edges48=1;ga->edges56=

26、5;ga->edges57=7;ga->edges78=1;ga->edges67=9;for(i=0;i<ga->n;i+)for(j=0;j<ga->n;j+)ga->edgesji=ga->edgesij;int locatevex(graph ga,int v) / / 查找景点在图中的序号int i;专业资料整理WORD格式for(i=0;i<ga.n;i+)if(v=ga.vexsi.num)return i;return -1;void Create_graph(graph *ga)int i,j,k,w;printf(

27、" 请输入顶点数和边数:n");scanf("%d %d",&(ga->n),&(ga->e);printf(" 请输入景点编号，景点名字，景点介绍，建立信息表 :n"); for(i=0;i<ga->n;i+)scanf("%d",&(ga->vexsi.num);gets(ga->);gets(ga->roduce);for(i=0;i<ga->n;i+)for(j=0;j<=ga->

28、n;j+)ga->edgesij=1000;for(k=0;k<ga->e;k+)专业资料整理WORD格式printf(" 请输入 %d 条边的景点序号i， j 和长度：",k+1);专业资料整理WORD格式scanf("%d %d %d",&i,&j,&w);ga->edgesij=w;ga->edgesji=w;void print(graph ga)int i,j;for(i=0;i<ga.n;i+)for(j=0;j<ga.n;j+)printf("%d",ga

29、.edgesij);if(j+1=ga.n)printf("n");void visit(graph ga)专业资料整理WORD格式int a;printf(" 请输入景点编号：scanf("%d",&a);int i;");专业资料整理WORD格式for( i=0;i<ga.n;i+)if(a=ga.vexsi.num)printf(" 景点编号为 %d n",ga.vexsi.num);printf(" 景点名称为 ");puts();printf(&

30、quot; 景点介绍为 ");puts(roduce);break;if(i=ga.n)printf(" 无此点 n");void shortestpath_djst(graph ga)void shortestpath_floyd(graph ga)int i,j,k,v,u,w,d3535,p353535;for(v=0;v<ga.n;v+)for(w=0;w<ga.n;w+)dvw=ga.edgesvw;for(u=0;u<ga.n;u+)pvwu=0;if(dvw<1000)pvwv=1;pvww=1;for

31、(u=0;u<ga.n;u+)for(v=0;v<ga.n;v+)for(w=0;w<ga.n;w+)if(dvu+duw<dvw)dvw=dvu+duw;专业资料整理WORD格式for(i=0;i<ga.n;i+)pvwi=pvui|puwi;printf("n请输入出发点和目的地编号：");scanf("%d %d",&k,&j);printf("nn");while(k<0|k>ga.n|j<0|j>ga.n)printf("n输入的编号不存在&qu

32、ot;);printf("n请重新输入编号：nn");scanf("%d %d",&k,&j);printf("nn");printf("%s",);for(u=0;u<ga.n;u+)if(pkju && k!=u &&j!=u)printf("->%s",);printf("->%s",);printf("nnn总长度为

33、 %d 千米 nnn",dkj);void path(graph c,int m,int n,int k)int s,x=0;int t;t=k+1;if(dk=n && k<8)for(s=0;s<k;s+)printf("%s->",);printf("%snn",);elses=0;while(s<c.n)if(c.edgesdks<1000)&&(visiteds=0)专业资料整理WORD格式visiteds=1;dk+1=

34、s;path(c,m,n,t);visiteds=0;s+;void allpath(graph c)int k,i,j,m,n;printf("nn请输入您要查询的两个景点的编号:nn");scanf("%d %d",&i,&j);printf("nn");m=locatevex(c,i);n=locatevex(c,j);d0=m;for(k=0;k<c.n;k+)visitedk=0;visitedm=1;path(c,m,n,0);void newgraph(graph &ga)int chang

35、enum;int i,m,n,t,distance,v0,v1;printf("n请输入要修改景点的个数：n");scanf("%d",&changenum);while(changenum<0|changenum>ga.n)printf("n输入错误！请重新输入");scanf("%d",&changenum);for(i=0;i<changenum;i+)printf("n请输入景点的编号：");scanf("%d,&m");t=

36、locatevex(ga,m);printf("n请输入景点的名称：");scanf("%s",);printf("n请输入景点简介：");scanf("%s",roduce);专业资料整理WORD格式printf("n请输入您要更新的边数");scanf("%d",&changenum);while(changenum<0|changenum>ga.n)printf(" 输入错误，请重新输入：&

37、quot;);scanf("%d",&changenum);printf("n请输入更新边的信息：n");for(i=1;i<=changenum;i+)printf("n修改的第 %d 条边的起点终点长度为：",i);scanf("%d %d %d",&v0,&v1,&distance);m=locatevex(ga,v0);n=locatevex(ga,v1);if(m>=0&&n>=0)ga.edgesmn=distance;ga.edgesn

38、m=ga.edgesmn;int delvex(graph &ga)/ 删除顶点int i=0,j;int m,v;if(ga.n<=0)printf(" 图中已经无顶点");return 1;printf("n请输入要删除的景点编号：");scanf("%d",&v);while(v<0|v>ga.n)printf("n输入错误，请重新输入");scanf("%d",&v);m=locatevex(ga,v);if(m<0)printf(&quo

39、t; 此顶点 %d 已删除 ",v);return 1;专业资料整理WORD格式for(i=m;i<ga.n-1;i+)strcpy(,ga.vexsi+1.name);strcpy(roduce,ga.vexsi+1.introduce);for(i=m;i<ga.n-1;i+)for(j=0;j<ga.n;j+)ga.edgesij=ga.edgesi+1j;for(i=m;i<ga.n-1;i+)for(j=0;j<ga.n;j+)ga.edgesji=ga.edgesji+1;ga.n-;retu

40、rn 1;int delarc(graph &ga)/ 删除边int m,n,v0,v1;if(ga.e<=0)printf(" 图中已经无顶边，无法删除");return 1;printf("n请输入要删除的边的起点和终点的编号：");scanf("%d %d",&v0,&v1);m=locatevex(ga,v0);if(m<0)printf(" 此顶点 %d 已删除 ",v0);return 1;n=locatevex(ga,v1);if(n<0)printf(&qu

41、ot; 此顶点 %d 已删除 ",v1);return 1;ga.edgesmn=1000;ga.edgesnm=1000;ga.e-;return 1;int enarc(graph &ga)专业资料整理WORD格式int m,n,distance;printf(" 请输入边的起点和终点编号，权值：");scanf("%d %d %d",&m,&n,&distance);while(m<0|m>ga.n|n<0|n>ga.n)printf(" 输入错误，请重新输入："

42、);scanf("%d %d",&m,&n);if(locatevex(ga,m)<0)printf(" 此节点 %d 已经删除 ",m);return 1;if(locatevex(ga,n)<0)printf(" 此节点 %d 已经删除 ",n);return 1;ga.edgesmn=distance;ga.edgesnm=ga.edgesmn;return 1;int envex(graph &ga)/ 增加节点int i;printf(" 请输入增加节点的信息：");p

43、rintf("n编号： ");scanf("%d",&ga.vexsga.n.num);printf(" 名称： ");scanf("%s",);printf(" 简介： ");scanf("%s",roduce);ga.n+;for(i=0;i<ga.n;i+)ga.edgesga.n-1i=1000;ga.edgesiga.n-1=1000;return 1;专业资料整理WORD格式intchan

44、gegraph(graph &ga)专业资料整理WORD格式专业资料整理WORD格式int yourchoice;printf("n请选择 nnprintf("n(3)增加结点printf("n(5)更新信息(1)删除结点(2)删除边(4) 增加边 n");(6) 返回 nn" );n");专业资料整理WORD格式scanf("%d",&yourchoice);printf("nn");while(!(yourchoice=1|yourchoice=2|yourchoice=3|yourchoice=4|yourchoice=5| yourchoice=6)printf(" 请重新输入：");scanf("%d",&yourchoice);while(1)switch(yourchoice)case 1:delvex(ga); break;