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

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

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

3、平面图景点的增加及删除，以及边和权值（长度）的改变2概要设计1：第一点是主界面的设计，首先，为了该系统各个功能的管理，设计出含有多个菜单项的主菜单界面，可以更方便的使用该系统。2 :第二点是存储结构的设计，采取了图结构类型（ mgraph）存储校园图的 信息，景点信息用结构数组 vexs 存储，而且利用全局变量： visited 数组用于存 储顶点是否被访问标志；d数组用于存放权值和查找路径顶点的编号；camp us是一 个图结构的全局变量。3 ：第三点是设计各个功能的实现， 学校景点的介绍通过函数 browsecompus（） 来实现；查询景点间的最段路径通过 Floyd（ 弗洛伊德 ）算法

4、实现；查询景点间的所有 路径通过 allpath 函数和 path 函数来实现；更改图的信息可以由主函数 changegraph 以及其他函数可以实现。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->,"西门 "）;strcpy（ga->roduce," 学校的正大门，设有公交站 "

5、）; strcpy（ga->," 风雨篮球场 "）; strcpy（ga->roduce,""）;strcpy（ga->," 田径场 "）;strcpy（ga->roduce," 举办运动会，平时体育跑步锻炼等 "）; strcpy（ga->," 京元食堂 "）;strcpy（ga->roduce," 新食堂 "）;strcpy

6、（ga->," 苍霞湖畔 "）;strcpy（ga->roduce," 戏称“分手湖”，景色宜人 "）;strcpy（ga->,"思源楼 "）;strcpy（ga->roduce," 学校王牌土木的教学区 "）; strcpy（ga->," 图书馆 "）;strcpy（ga->roduce," 是大学城最高的标志性建筑 "）;

7、strcpy（ga->," 北教区 "）;strcpy（ga->roduce," 北校区集中的教学楼 "）; 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;g

8、a->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->n;j+)ga->edgesji=ga->edgesij;(2) 确定顶点是否存在已经顶点是否已经被访问过来确定路径void Create_graph(graph *ga)int i,j,k,w

9、;printf(" 请输入顶点数和边数 :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

10、<=ga->n;j+) ga->edgesij=1000;for(k=0;k<ga->e;k+)printf("请输入£条边的景点序号i , j和长度：",k+1); scanf("%d %d %d",&i,&j,&w);ga->edgesij=w; ga->edgesji=w;void print(graph ga)int i,j; for(i=0;i<i+) for(j=0;j<j+)printf("%d",ij);if(j+1= printf

11、("n"); void visit(graph ga)int a;printf(" 请输入景点编号： "); scanf("%d",&a);int i;for( i=0;i<i+)if(a=i.num)printf(" 景点编号为 %d n",i.num); printf(" 景点名称为 "););printf(" 景点介绍为 "); roduce);break;无此点 n"); if(i=printf("

12、;(3) 得出景点间的最短路径 void shortestpath_djst(graph ga)void shortestpath_floyd(graph ga)int i,j,k,v,u,w,d3535,p353535; for(v=0;v<v+)for(w=0;w<w+)dvw=vw; for(u=0;u<u+) pvwu=0; if(dvw<1000) pvwv=1;pvww=1; for(u=0;u<u+)for(v=0;v<v+)for(w=0;w<w+)if(dvu+duw<dvw)dvw=dvu+duw;for(i=0;i<i

13、+)pvwi=pvui|puwi;printf("n 请输入出发点和目的地编号： "); scanf("%d %d",&k,&j);printf("nn");while(k<0|k>|j<0|j>printf("n 输入的编号不存在 "); printf("n 请重新输入编号： nn"); scanf("%d %d",&k,&j);printf("nn");printf("%s",

14、);for(u=0;u<u+)if(pkju && k!=u &&j!=u)printf("->%s",);printf("->%s",);printf("nnn总长度为 c千米nnn",dkj);(4) 得到景点之间的所有路径 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(&q

15、uot;%s->",);printf("%snn",);elses=0;while(s<if(dks<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"

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

17、<0)printf(" 此顶点d已删除",vO);return 1;n=locatevex(ga,v1);if(n<O)printf(" 此顶点d已删除",v1);return 1;mn=1OOO;nm=1OOO;return 1; int enarc(graph &ga)int m,n,distance;printf(" 请输入边的起点和终点编号，权值： "); scanf("%d %d %d",&m,&n,&distance); while(m<0|m>|

18、n<0|n>printf(" 输入错误，请重新输入： "); scanf("%d %d",&m,&n); if(locatevex(ga,m)<0)printf(" 此节点cE经删除",m);return 1; if(locatevex(ga,n)<0)printf(" 此节点d已经删除",n); return 1;mn=distance;nm=mn;return 1;4调试分析 内容包括：a调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分 析；b算法的时空分析

19、(包括基本操作和其他算法的时间复杂度和空间复杂度的分 析) 和改进设想；C 经验和体会等。5用户使用说明 通过主菜单提示，选择出你所想要知道的信息，然后通过输入节点来代替景 点，从而得到景点间的所有路径，最短路径等其他信息。6测试结果（2）（3）（4）（5）（6）7附录#define MAX 100 um=i;strcpy（ga->,"西门 "）;strcpy（ga->roduce," 学校的正大门，设有公交站 "）; strcpy（ga->," 风雨篮球场 "

20、;）; strcpy（ga->roduce,""）;strcpy（ga->," 田径场 "）;strcpy（ga->roduce," 举办运动会，平时体育跑步锻炼等 "）;strcpy（ga->," 京元食堂 "）;strcpy（ga->roduce," 新食堂 "）;strcpy（ga->," 苍霞湖畔 "）;( 1)操作的主

21、界面 学校景点的介绍 学校景点从西门的禾堂餐厅的所有路径所有路径 学校景点从西门的禾堂餐厅的所有路径最短路径 图的更改的界面 边的删除界面展示strcpy(ga->roduce," 戏称“分手湖”，景色宜人 "); strcpy(ga->," 思源楼 ");strcpy(ga->roduce," 学校王牌土木的教学区 ");strcpy(ga->," 图书馆 ");strcpy(ga->rod

22、uce," 是大学城最高的标志性建筑 ");strcpy(ga->," 北教区 ");strcpy(ga->roduce," 北校区集中的教学楼 ");strcpy(ga->," 禾堂餐厅 ");strcpy(ga->roduce,"旧食堂 ");for(i=0;i<ga->n;i+)for(j=0;j<ga->n;j+) ga->edgesij=1000;ga-&g

23、t;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->n;j+)ga->edgesji=ga->edgesij;查找景点在图中的序号int locatevex(graph ga,int v

24、) / /int i;for(i=0;i<i+) if(v=i.num)return i; return -1;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->ve

25、xsi.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("请输入£条边的景点序号i , j和长度：",k+1); scanf("%d %d %d",&i,&j,&w);ga->edgesij=w;ga->edgesji=w;void

26、 print(graph ga)int i,j;for(i=0;i<i+) for(j=0;j<j+)printf("%d",ij);if(j+1= printf("n");void visit(graph ga)int a;printf(" 请输入景点编号： "); scanf("%d",&a);int i;for( i=0;i<i+)if(a=i.num)printf(" 景点编号为 %d n",i.num); printf(" 景点名称为 ")

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

28、;u+)for(v=0;v<v+) for(w=0;w<w+) if(dvu+duw<dvw)dvw=dvu+duw;for(i=0;i<i+)pvwi=pvui|puwi;请输入出发点和目的地编号： "); printf("n scanf("%d %d",&k,&j); printf("nn");while(k<0|k>|j<0|j>printf("n 输入的编号不存在 ");printf("n 请重新输入编号： nn"); sc

29、anf("%d %d",&k,&j); printf("nn"); printf("%s",); for(u=0;u<u+)if(pkju && k!=u &&j!=u)printf("- ->%s",);printf("->%s",);printf("nnn总长度为 c千米nnn",dkj);void path(graph c,int m,int n,int k)int s

30、,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<if(dks<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 请输入您要查询的两个景点

31、的编号 :nn"); scanf("%d %d",&i,&j);printf("nn");m=locatevex(c,i);n=locatevex(c,j);d0=m;for(k=0;k<k+)visitedk=0;visitedm=1;path(c,m,n,0);void newgraph(graph &ga)int changenum;int i,m,n,t,distance,v0,v1;printf("n 请输入要修改景点的个数： n"); scanf("%d",&am

32、p;changenum);while(changenum<0|changenum>printf("n 输入错误！请重新输入 "); scanf("%d",&changenum); for(i=0;i<changenum;i+)printf("n 请输入景点的编号： "); scanf("%d,&m");t=locatevex(ga,m);printf("n 请输入景点的名称： "); scanf("%s",);printf(&qu

33、ot;n 请输入景点简介： "); scanf("%s",roduce);printf("n 请输入您要更新的边数 ");scanf("%d",&changenum);while(changenum<0|changenum>printf(" 输入错误，请重新输入： "); scanf("%d",&changenum);printf("n 请输入更新边的信息： n");for(i=1;i<=changenum;i+)prin

34、tf("n修改的第d条边的起点终点长度为：",i);scanf("%d %d %d",&v0,&v1,&distance); m=locatevex(ga,v0);n=locatevex(ga,v1);if(m>=0&&n>=0)mn=distance;nm=mn;int delvex(graph &ga) ame,i+1.name); roduce,i+1.introduce);for(i=m;i<i+)for(j=0;j<j+)i j=i+1j;for(i=

35、m;i<i+)for(j=0;j<j+)ji=ji+1;return 1;int delarc(graph &ga) um); printf(" 名称： "); scanf("%s",.name); printf(" 简介： "); scanf("%s",.introduce); +;for(i=0;i<i+)i=1000;i=1000;return 1; intchangegraph(graph &ga)int yourchoice;printf("nprintf(&q

36、uot;nprintf("nscanf("%d",&yourchoice);printf("nn");while(!(yourchoice=1|yourchoice=2|yourchoice=3|yourchoice=4|y ourchoice=5|yourchoice=6)printf(" 请重新输入： ");scanf("%d",&yourchoice);while(1)switch(yourchoice)case 1:case 2:case 3:case 4:case 5:请选择 nn(3)(5)(1)增加结点 (4) 增加边 n"); 更新信息 (6) 返回 nn" );删除结点 (2) 删除边 n");case 6: return 1;printf("nprintf("nprintf("ndelvex(ga); break; delarc(ga); break; envex(ga); break; enarc(ga); break; newgraph(ga); break;请选择 nn(3)(5)(1)增加结点更新信息删除结点 (2) 删除边 n");(4