数据结构课程设计校园导游咨询5篇

第一篇：数据结构课程设计校园导游咨询

9、校园导游咨询 问题描述：

设计一个校园导游程序，为来访的客人提供各种信息查询服务。基本要求：

⑴设计华东交通大学的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，⑵存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。⑶为来访客人提供图中任意景点相关信息的查询。⑷为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。

#include #define MAXV 100

//最大顶点个数 #define INF 32767

//用32767表示∞ #include

//调用函数system改变字体颜色的头文件

typedef int InfoType;#define MAXV 100

//最大顶点个数 //以下定义邻接矩阵类型 typedef struct {

int no;

//顶点编号

InfoType info;

//顶点其他信息 } VertexType;

//顶点类型 typedef struct

//图的定义 {

int edges[MAXV][MAXV];//邻接矩阵

int vexnum,arcnum;

//顶点数，弧数

VertexType vexs[MAXV];//存放顶点信息 } MGraph;

void ecjtumap()//建立华东交通大学地图

{ printf(“t|------------------------------|n”);printf(“t|

|n”);printf(“t|

|n”);printf(“t|

----------

|n”);printf(“t|

==============================| 国防生宿舍|

|n”);printf(“t|。

----------

|n”);printf(“t|。

。

|n”);printf(“t|。

。

|n”);printf(“t|。

。

|n”);printf(“t|。

。

|n”);printf(“t|。

。

|n”);printf(“t|

|南区四食堂|

----------

|n”);printf(“t|。

|南区礼堂 |

|n”);printf(“t|。

----------

|n”);printf(“t|。

。

|n”);printf(“t|。

。

|n”);printf(“t|。

--------。

|n”);printf(“t|

================| 校训牌|。。。。

|n”);printf(“t|

=

--------

|n”);printf(“t|

=。

|n”);printf(“t|

=。

|n”);printf(“t|

--------

---------

|n”);printf(“t|----| 南区后门 |---------| 南区大门 |------------------------|n”);printf(“t|

--------

---------

|n”);printf(“t|

---------

|n”);printf(“t|-------------------------| 北区大门 |------------------------|n”);printf(“t|

--------

|n”);printf(“t|。

--------------

|n”);printf(“t|

===========================| 15栋综合教学楼 |

|n”);printf(“t|

=

--------------

|n”);printf(“t|

=。

|n”);printf(“t|

=。

|n”);printf(“t|

=。

|n”);printf(“t|

=。

|n”);printf(“t|

=

----------

|n”);printf(“t|

===============================| 经管食堂 |

|n”);printf(“t|

=

----------

|n”);printf(“t|

=

=

|n”);printf(“t|

=

=

|n”);printf(“t|

-----------

=

|n”);printf(“t|

|轨道交通食堂|====================| 学生宿舍 |

|n”);printf(“t|

------------

|n”);printf(“t|

|n”);printf(“t|------------------------------|n”);printf(“n”);} void DispMat(MGraph g)

//输出邻接矩阵g，即输出地图各景点的图的距离 { int i,j;for(i=0;i

for(j=0;j

if(g.edges[i][j]==INF)

printf(“%3s”,“∞”);//这里分别用%3s和%3d控制输出字符∞或数字宽度为3个字符

else printf(“%3d”,g.edges[i][j]);//这样比较方便观看景点的图的邻接矩阵g

printf(“n”);} } void listmap()//建立 景点的相关信息的总浏览表

{ printf(“t

华东交通大学景点一览

nn”);printf(“t|--------|n”);printf(“t| 1：南区大门

|n”);printf(“t|--------|n”);printf(“t| 2：校训牌

|n”);printf(“t|--------|n”);printf(“t| 3：图书馆

|n”);printf(“t|--------|n”);printf(“t| 4：南区一食堂

|n”);printf(“t|--------|n”);printf(“t| 5：孔目湖

|n”);printf(“t|--------|n”);printf(“t| 6：北区大门

|n”);printf(“t|--------|n”);printf(“t| 7：15栋教学楼

|n”);printf(“t|--------|n”);printf(“t| 8：北区食堂

|n”);printf(“t|--------|n”);printf(“t| 9：科技楼

|n”);printf(“t|--------|n”);printf(“t| 10：北区篮球场

|n”);printf(“t|--------|n”);} void introduce()//根据上面的浏览表，对应出相关信息 { int a=1;printf(“n”);printf(“请输入要查看的景点:n”);printf(“输入1~10的数字选择景点，其他数字返回上一级n”);while(0

switch(a)

{case 1:printf(“1：南区大门是进入华东交通大学南区的正门n”);break;

case 2:printf(“2：校训牌是激励我们大学生积极向上n”);break;

case 3:printf(“3：图书馆是给我们大学生丰富知识的海洋n”);break;

case 4:printf(“4：南区一食堂是南区学生的吃饭的地方n”);break;

case 5:printf(“5：孔目湖是华东交通大学最迷人的地方n”);break;

case 6:printf(“6：北区大门是进入华东交通大学北区的正门n”);break;

case 7:printf(“7：15栋教学楼是一栋综合型的教学楼n”);break;

case 8:printf(“8：北区食堂是北区学生吃饭的地方n”);break;

case 9:printf(“9：科技楼是大学生上机做实验的教学楼n”);break;

case 10:printf(“10：北区篮球场是大学生锻炼身体的地方n”);break;

} } } void show_didian(int n)//根据算法求出的整型数，对应出地点//根据 xx算法求出的数字，转化为文字描述 { switch(n){case 0:printf(“1.南区大门”);break;case 1:printf(“2.校训牌”);break;case 2:printf(“3.图书馆 ”);break;case 3:printf(“4.南区一食堂”);break;case 4:printf(“5.孔目湖”);break;case 5:printf(“6.北区大门”);break;case 6:printf(“7.15栋教学楼”);break;case 7:printf(“8.北区食堂”);break;case 8:printf(“9.科技楼”);break;case 9:printf(“10.北区篮球场”);break;} } void ppath(int path[][MAXV],int i,int j)//求最短路径经过的地点 { int k=path[i][j];if(k==-1)return;ppath(path,i,k);show_didian(k);printf(“->> ”);ppath(path,k,j);} void put_shortdistance(int x,int y,int A[][MAXV],int path[][MAXV],int n){ int i,j;for(i=0;i

for(j=0;j

if(A[i][j]==INF)

{

if(i!=j)printf(“从%d到%d没有路径n”,i,j);

}

else

{

if(i==x&&j==y)

{ printf(“最短路径为：从--”);

show_didian(i);

printf(“--到--”);

show_didian(j);

printf(“--路径为--:n”);

show_didian(i);//输出起点

printf(“->>”);

ppath(path,i,j);//求最短路径经过的中间路径，若没有则不输出

show_didian(j);//输出 终点

printf(“nt路径长度为:%dn”,A[i][j]);

}

} } void shortdistance(MGraph g,int x,int y)//求最短路径用的是弗洛伊德算法

{ int A[MAXV][MAXV],path[MAXV][MAXV];//path为中间路径不包括 起点 终点

int i,j,k,n=g.vexnum;for(i=0;i

//给A数组置初值

for(j=0;j

{

A[i][j]=g.edges[i][j];path[i][j]=-1;

} for(k=0;k

//计算Ak {

for(i=0;i

for(j=0;j

//这里的3个for循环

if(A[i][j]>(A[i][k]+A[k][j]))//所以时间复杂度O(n3)

{

A[i][j]=A[i][k]+A[k][j];path[i][j]=k;

} } put_shortdistance(x,y,A,path,n);} void menu(MGraph g)//建立 菜单 页面，可以无数次选择菜单，当输入5时退出系统 { int m=1,x=1,y=1;//m的菜单选择的功能x,y分别表示从x到y的问路查询

while(m!=5){ printf(“ttt|------------------------|n”);

printf(“ttt|----------菜单----------|n”);

printf(“ttt| 1：查看地图

|n”);

printf(“ttt| 2：地图详解

|n”);

printf(“ttt| 3：景点一览表

|n”);

printf(“ttt| 4：问路查询

|n”);

printf(“ttt| 5：退出

|n”);

printf(“ttt|------------------------|n”);

printf(“请输入1~5的数字n”);

scanf(“%d”,&m);

switch(m)

{case 1:ecjtumap();break;

case 2:listmap();

introduce();break;

case 3:listmap();

introduce();

printf(“n”);break;

case 4:listmap();

printf(“请输入起点:”);

scanf(“%d”,&x);x+=-1;

printf(“请输入终点:”);

scanf(“%d”,&y);y+=-1;

shortdistance(g,x,y);break;

case 5:printf(“ttt感想使用本系统，欢迎下次继续使用n”);break;

} } } void main(){ system(“color 0a”);//输出字体为绿色

int i,j;MGraph g;int A[MAXV][10]={

{INF, 1,INF,INF,INF, 1,INF,INF,INF,INF}，{ 1,INF, 5, 6, 7,INF,INF,INF,INF,INF}，{INF, 5,INF,INF, 2,INF,INF,INF,INF,INF}，{INF, 6,INF,INF, 5,INF,INF,INF,INF,INF}，{INF, 7, 2, 5,INF,INF,INF,INF,INF,INF}，{ 1,INF,INF,INF,INF,INF, 3,INF, 5,INF}，{INF,INF,INF,INF,INF, 3,INF, 2,INF,INF}，{INF,INF,INF,INF,INF,INF, 2,INF, 8, 10}，{INF,INF,INF,INF,INF, 5,INF, 8,INF, 2}，{INF,INF,INF,INF,INF,INF,INF, 10, 2,INF}};g.vexnum=11;g.arcnum=11;for(i=0;i

for(j=0;j

g.edges[i][j]=A[i][j];printf(“n”);printf(“ttt华东交通大学导游咨询系统n”);menu(g);//进入导游系统，执行菜单功能 }

第二篇：校园导游实验报告——数据结构

数据结构实验报告

——实验六 简单校园导游程序的设计与实现

本实验的目的是通过对校园导游程序的设计与实现来熟练掌握图型结构在实际问题中的应用。

一、【问题描述】

当人们到一个陌生的地方去旅游的时候可能会找一个导游为自己在游玩的过程中提供方便。导游可以提供很多服务，比如介绍参观景点的历史背景等相关信息，推荐到下一个景点的最佳路径，以及解答旅游者所提出的关于旅游经典的相关问询等等。对于新生刚刚来到校园，对校园环境不熟悉的情况也如此，一般都是高年级的学生充当了“校园导游员”的角色，如果能够提供一个程序让新生或来访的客人自主的通过与机器的“对话”来获得相关的信息的话，将会节省大量的人力和时间。而且所提供的信息也能够做到尽可能的准确、详尽。一个成功的校园导游程序可以替代现实生活中这些“校园导游员”，更方便了大家查询校园相关的信息。

本次实验需要开发一个简单的校园导游程序，程序的主体功能为：

1、显示校园平面图，方便用户直观的看到校园的全景示意图，并确定自己的位置。

2、为用户提供对平面图中任意场所的相关信息的查询。

3、为用户提供对平面图中任意场所的问路查询。

二、【数据结构设计】

由于各个场所通过校园中的道路相连，各个场所和连接它们的道路构成了整个校园的地理环境，所以使用图这种数据结构对他们去进行描述。以图中的顶点表示校园内各个场所，应包含场所名称、代号、简介等信息；以边表示连接各个场所的道路，应包含道路的代号、路径的长度等信息。顶点和边均使用结构体定义，整个图的数据结构可以采用教材中介绍的各种表示方法，例如带权的邻接矩阵。

三、【功能（函数）设计】

1、显示校园平面图的功能模块。

通过读文件的方式将各个地点的信息读入程序中.平面图中应醒目的标识出场所的准确名称以备用户查询。河北大学校园导游的基本地点信息。

***************欢迎进入河北大学校园导游系统!**************-----------------------景点名称---------------------------

主楼 多功能馆 毓秀园 图书馆

操场

留学生楼

七教 八教

九教 成教 南大门 北大门

一教 逸夫楼 博物馆 物理楼

电信楼 化学楼 生科楼 建工楼

北院食堂

南院食堂

竹园 梅园

桂园 菊园 易百超市 北院生活园区

---------------------------地点的存储

typedef struct Vertex//顶点结构体 { int No;//地点编号

char name[20];//地点名称

char info[1000];//地点简介 }Vertex;typedef struct //无向图结构体 { Vertex view[Max_Vertex];int edges[Max_Vertex][Max_Vertex];//边的邻接矩阵

int vnum,anum;//顶点和边的个数 }Graph;

2、查询任意场所的相关信息查询的功能模块。

此模块接收用户所输入的场所名称，并将场所的简介信息反馈给用户。查找出查询的场所将其信息输出,信息通过文本文件读入 函数void introduction(Graph &G)实现

先通过strcpy进行查找，再讲找到顶点v1 G.view[v1].info输出

3、任意场所的问路查询的功能模块。

void shortpath(Graph &G,int v0,int v1)；此函数运用克鲁斯卡尔算法计算两点间最短路径。

void dispath(Graph &G)//查询最短路径 { „shortpath(G, v0, v1)； } 此模块接收用户所输入的场所名称，并在调用shortpath(G, v0, v1)；计算出最短路径相关项的信息反馈给用户。

4、求单源点到其他各点的最短路径的功能模块。

此模块计算并记录从校园门口到各个场所的最短路径。for(i=0;i

四、【界面设计】

本程序为方便用户所设计，由于使用的最终用户大多对校园的情况并不熟悉，所以在图中给出的任何提示信息一定要准确，尽量的避免歧义。

五、【编码实现】 #include #include #include #include #include #define Max_Vertex 100 #define Maxnum 1000 typedef struct Vertex//顶点结构体 { int No;//地点编号

char name[20];//地点名称

char info[1000];//地点简介 }Vertex;typedef struct //无向图结构体 { Vertex view[Max_Vertex];

int edges[Max_Vertex][Max_Vertex];//边的邻接矩阵

int vnum,anum;//顶点和边的个数 }Graph;void Creat(Graph &G){ ifstream infile(“view.txt”,ios::in);

if(!infile)

{

cout<<“文件打开错误”<

abort();

}

int i,j,k,w;

infile>>G.vnum;

infile>>G.anum;

//cout<

for(i=0;i

{

infile>>G.view[i].No>>G.view[i].name>>G.view[i].info;

}

for(i=0;i

{

for(j=0;j

G.edges[i][j]=Maxnum;

}

ifstream weight_file(“weight.txt”,ios::in);

if(!weight_file)

{

cout<<“文件打开错误”<

abort();

}

for(k=0;k

{

weight_file>>i>>j>>w;

i--;

j--;

G.edges[i][j]=w;

G.edges[j][i]=G.edges[i][j];

} } void introduction(Graph &G){ char temp[20];cout<<“请输入要查询的景点名称”<>temp;int v1,i,count=0;for(i=0;i

if(strcmp(G.view[i].name,temp)==0)

{

v1=i;

count++;

} } if(count!=1){

cout<<“输入的名称不存在”<

return;} else {

cout<<“该景点简介为”<

cout<

return;} } void shortpath(Graph &G,int v0,int v1){

int P[100];float D[100];int i,j,w;int v,pre;float min;

int final[Max_Vertex];for(v=0;v

{

final[v]=0;

D[v]=G.edges[v0][v];

if(D[v]

P[v]=v0;

if(D[v]==Maxnum)

P[v]=-2;

} D[v0]=0;final[v0]=1;P[v0]=-1;

for(i=1;i

min=Maxnum;

//min为当前所知离源点的最近距离

for(w=0;w

if(!final[w])

if(D[w]

{

j=w;

//记忆此点

min=D[w];

}

final[j]=1;

//离源点最近的j加入S集合 for(w=0;w

//更新其它点地当前最短路径

if(!final[w] &&(min+G.edges[j][w]

{

D[w]=min+G.edges[j][w];

P[w]=j;

//将w的前驱结点改为j

} }

if(P[v1]==-2)

cout<<“max”<

else

{

pre=P[v1];

cout<

cout<

cout<

while(pre>0)

{

cout<<“←”<

pre=P[pre];

}

if(v0==0)

cout<<“←”<

else

cout<

cout<

}

}

void dispath(Graph &G)//查询最短路径 { int v1,v0,i;int count=0;char temp1[20],temp2[20];cout<<“请输入要查询的两个景点名称”<>temp1>>temp2;

for(i=0;i

if(strcmp(G.view[i].name,temp1)==0)

{

v0=i;

count++;

}

if(strcmp(G.view[i].name,temp2)==0)

{

v1=i;

count++;

} } if(count!=2){

cout<<“输入的名称不存在”<

return;} else {

shortpath(G,v0,v1);

return;} } void main(){ Graph G;Creat(G);int i;char ch1;

cout<<“t***************欢迎进入河北大学校园导游系统!**************”<

cout<<“t-----------------------景点名称---------------------------”<

for(i=0;i

{

if(i%4==0)

{

cout<

cout<

}

else

{

cout<

}

}

cout<

cout<<“t---------------------------”<

cout<<“t__________________________________________________________”<

cout<<“tt 请选择要进行的操作”<

cout<<“ tt 1.查询景点信息”<

cout<<“ tt 2:显示大门到各个地点的最短路径”<

cout<<“ tt 3:查询两个景点之间的最短路径”<

cout<<“ tt 0:退出”<

cout<<“t__________________________________________________________”<

cout<<“请选择(0~2):”;

cin>>ch1;

while(!(ch1<='3'&&ch1>='0'))

{

cout<<“数据输入错误，请重新选择(0~2):”;

cin>>ch1;

}

switch(ch1)

{

case '1': introduction(G);break;

case '2' :

for(i=0;i

shortpath(G,10,i);

break;

case '3' : dispath(G);

break;

}

}while(ch1!=0);}

六、【运行与测试】

***************欢迎进入河北大学校园导游系统!**************

-----------------------景点名称---------------------------

主楼

多功能馆

毓秀园

图书馆

操场

留学生楼

七教

八教

九教

成教

南大门

北大门

一教

逸夫楼

博物馆

物理楼

电信楼

化学楼

生科楼

建工楼

北院食堂

南院食堂

竹园

梅园

桂园

菊园

易百超市

北院生活园区

---------------------------

__________________________________________________________

请选择要进行的操作

1.查询景点信息

2:显示大门到各个地点的最短路径

3:查询两个景点之间的最短路径

0:退出

__________________________________________________________ 请选择(0~2):1 请输入要查询的景点名称 主楼

该景点简介为

是河北大学本部标志性建筑，这H型高大的建筑，正对着河北大学校本部南院黑

校门，此楼于2001年建成。主要为教学、科研、办公服务。

__________________________________________________________

请选择要进行的操作

1.查询景点信息

2:显示大门到各个地点的最短路径

3:查询两个景点之间的最短路径

0:退出

__________________________________________________________ 请选择(0~2):1 请输入要查询的景点名称 哈哈

输入的名称不存在

__________________________________________________________

请选择要进行的操作

1.查询景点信息

2:显示大门到各个地点的最短路径

3:查询两个景点之间的最短路径

0:退出

__________________________________________________________ 请选择(0~2):2 南大门到主楼最短路径为50米 主楼←南大门

南大门到多功能馆最短路径为60米 多功能馆←南大门

南大门到毓秀园最短路径为60米 毓秀园←图书馆←南大门

南大门到图书馆最短路径为40米 图书馆←南大门

南大门到操场最短路径为160米 操场←毓秀园←图书馆←南大门 南大门到留学生楼最短路径为180米

留学生楼←操场←毓秀园←图书馆←南大门

南大门到七教最短路径为115米

七教←桂园←毓秀园←图书馆←南大门

南大门到八教最短路径为65米 八教←图书馆←南大门

南大门到九教最短路径为70米 九教←图书馆←南大门

南大门到成教最短路径为75米 成教←八教←图书馆←南大门

南大门到南大门最短路径为0米 南大门

南大门到北大门最短路径为25米 北大门←南大门

南大门到一教最短路径为35米 一教←北大门←南大门

南大门到逸夫楼最短路径为60米

逸夫楼←博物馆←物理楼←北大门←南大门

南大门到博物馆最短路径为45米 博物馆←物理楼←北大门←南大门

南大门到物理楼最短路径为35米 物理楼←北大门←南大门

南大门到电信楼最短路径为60米 电信楼←一教←北大门←南大门

南大门到化学楼最短路径为50米 化学楼←物理楼←北大门←南大门

南大门到生科楼最短路径为145米

生科楼←建工楼←化学楼←物理楼←北大门←南大门

南大门到建工楼最短路径为100米

建工楼←化学楼←物理楼←北大门←南大门

南大门到北院食堂最短路径为115米

北院食堂←化学楼←物理楼←北大门←南大门

南大门到南院食堂最短路径为80米 南院食堂←八教←图书馆←南大门

南大门到竹园最短路径为135米

竹园←七教←桂园←毓秀园←图书馆←南大门

南大门到梅园最短路径为145米

梅园←七教←桂园←毓秀园←图书馆←南大门

南大门到桂园最短路径为95米 桂园←毓秀园←图书馆←南大门

南大门到菊园最短路径为125米 菊园←八教←图书馆←南大门

南大门到易百超市最短路径为145米

易百超市←七教←桂园←毓秀园←图书馆←南大门

南大门到北院生活园区最短路径为159米

北院生活园区←北院食堂←化学楼←物理楼←北大门←南大门

__________________________________________________________

请选择要进行的操作

1.查询景点信息

2:显示大门到各个地点的最短路径

3:查询两个景点之间的最短路径

0:退出

__________________________________________________________ 请选择(0~2): 请输入要查询的两个景点名称 主楼 七教

主楼到七教最短路径为75米 七教←桂园←毓秀园←主楼

__________________________________________________________

请选择要进行的操作

1.查询景点信息

2:显示大门到各个地点的最短路径

3:查询两个景点之间的最短路径

0:退出

__________________________________________________________ 请选择(0~2):3 请输入要查询的两个景点名称 桌喽 菊园

输入的名称不存在

__________________________________________________________

请选择要进行的操作

1.查询景点信息

2:显示大门到各个地点的最短路径

3:查询两个景点之间的最短路径

0:退出

__________________________________________________________

请选择(0~2):

第三篇：校园导航系统数据结构课程设计

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

1引言

本概要设计说明书基于之前建立的软件需求设计基础上，对“蚌埠学院校园导航系统”做出概要分析。主要解决了实现该系统需求的程序模块设计问题。包括如何把该系统划分成若干个模块、决定各个模块之间的接口、模块之间传递的信息，以及数据结构、模块结构的设计等。在以下的概要设计报告中将对在本阶段中对系统所做的所有概要设计进行详细的说明。

2程序设计

2.1设计时间

2015-06-01—2015-06-15 2.2设计目的

1.加深对《数据结构》这门课程的进一步理解与巩固 2.通过课程设计，培养自己的编程能力以及团队协作能力

3.加强自己对实际问题的分析能力，以及如何更好的将一些经典的算法应用于实际

2.3设计任务

该导航系统为参观者提供校园主要建筑的基本信息及各建筑间的距离，同时通过该系统计算出所在位置到目的地的最短路径。

2.4需求分析

1.程序体现的功能：(1)main()——主函数

(2)navigate()——导航函数

(3)pri()——打印校园平面图函数(4)visit()——递归查找路线函数 2.正确输入与输出形式： 如：

执行建筑查询功能： ① 输入为：sod 输出为：该建筑所在的坐标为7 8 种有花草和一些艺术标记物 ② 输入为：ld 输出为：该位置没有找到 你找的建筑没有找到

执行导航功能：

输入为：请输入你所在位置：gym

输入你要的目的地：sod

输出为：打印并给出所有可能走通的线路，计算出两地间的最短路径（距离）

执行显示最短路径功能：

输入为：请输入你所在位置：sod

输入你要的目的地：office

输出为：其中最短路径为：

平面图中包含最短线路图，其行走的距离为450米

2.5概要设计

2.5.1.设计思路和主要步骤

按照需求分析，首先我们先要把学校的整体布局给设计出来，即用一个二维数组char arr[17][22]表示学校的整体布局，并将每个建筑物用特殊的符号表示：/*2为墙壁 ■ A办公楼▤ c教学区● g草坪▣ p操场▓

0 路

b图书馆★

M门□

m 食堂○h为宿舍☆

T为体育馆▢ l为实验室 ╳*/，然后要打印出学校的整体布局,设计一个pri（char，int）打印出学校的整体布局。

在学校里，最重要的是校园的导航系统，这样可以使人耳目一新的知道某个地方的某个地方的路径，所以设计校园导航函数是必须的，因此我们设计void navigate(int x)函数，在图的应用中，一个最重要的知识就是求最短路径，我们并没有用迪杰斯特拉的算法和弗洛伊德算法来实现这个功能，而是利用了迷宫求解问题中的递归意义来实现求最短路径的功能void visit(int qiX,int qiY,int zhX,int zhY, int x)用于查找某地点到某地点的所有路径，然后进行比较，将最短路径用函数void fuzhi(将最短路径存放在一个数组中)。

2.5.2程序流程图

2.6详细设计

按照需求分析中的需求，和概要设计中的各流程图的模块，进行详细设计，完善各流程的代码，详细设计如下：

2.6.1学校整体局部

char arr[17][22]={ /*2为墙壁 ■ A办公楼▤ c教学区● g草坪▣ p操场▓ 0 路 b图书馆★ M门□ m 食堂○h为宿舍☆ T为体育馆▢ l为实验室 ╳*/ // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 {'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：校园建筑信息

struct Construct construct[]={ {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:00n是老师和学生学习的好去处”},//图书馆

{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,“No found”,“你找的建筑没有找到”}, };2.6.2打印图

void pri(char a[17][22],int bushu){

int i,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”);} 2.6.3导航函数

void navigate(int x){ shortbushu=1000;/*用于记录最短步数*/ struct Construct * qi;struct Construct * zh;int qiX, qiY,zhX,zhY;int c;int i=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.6.4查找路径

void visit(int qiX,int qiY,int zhX,int zhY, int x){ //x为标志，用于控制要不要显示所有的路径 当其非0是显示所有的路径 char n=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--;} 2.6.5记录最短路径

void fuzhi(){ int i,j;for(i=0;i<17;i++){ for(j=0;j<22;j++){

jilu[i][j]=arr[i][j];

} } } 3调试分析

4附录

程序源代码： #include #include #include

char jilu[17][22];/*用于记录最短路径*/ void fuzhi();/*用于给最短路径赋值*/ int shortbushu=1000;/*用于记录最短步数*/ int num=1;/*记录多少条路*/ int bushu=0;/*记录走了多远*/

struct Construct selectName(int *a,int n);/*根据名字查询位置*/ void navigate(int x);/*导航*/ void pri(char [][22],int);//打印图

void add();//增加建筑信息

void visit(int ,int,int,int,int);//递归查找路线 char arr[17][22]={ /*2为墙壁 ■ A办公楼▤ c教学区● g草坪▣ p操场▓

0 路

b图书馆★

M门□

m 食堂○h为宿舍☆

T为体育馆▢ l为实验室 ╳*/

// 0

7 11 12 13 14 15 16 17 18 19 20 21

{'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'}, };struct Construct{ int x;int y;char name[25];char miaoshu[10000];};struct Construct construct[]={ {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:00n是老师和学生学习的好去处”},//图书馆

{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,“No found”,“你找的建筑没有找到”}, };void ar(){ int m,n;for(m=0;m<17;m++){

for(n=0;n<22;n++){

printf(“%c”,arr[m][n]);

}

printf(“n”);} }

struct Construct * selectName(int n)/*根据名字查询位置*/{

int i;char name[15];scanf(“%s”,&name);for(i=0;i

if(strcmp(construct[i].name,name)==0){

return & construct[i];

}

} printf(“给位置没有找到n”);return & construct[15];} int main(){ int i;

int n=15;struct Construct * 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){

case 1:

printf(“查询位置n”);

pri(arr,0);

break;

case 2:

printf(“请输入查询建筑的名称:n”);

jianzhu=selectName(n);

if(-1!=jianzhu->x)

printf(“该建筑所在的坐标为%d %dn”,jianzhu->x,jianzhu->y);

printf(“%sn”,jianzhu->miaoshu);

break;

case 3:

printf(“导航n”);

navigate(1);

break;

case 4:

printf(“其中最短路径为:n”);

navigate(0);

//pri(jilu,shortbushu);

break;

case 5:

printf(“退出”);

exit(0);

break;

}

};

return 0;} void navigate(int x){ shortbushu=1000;/*用于记录最短步数*/ struct Construct * qi;struct Construct * zh;int qiX, qiY,zhX,zhY;int c;int i=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为体育馆▢*/ void pri(char a[17][22],int bushu){

int i,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”);

} void visit(int qiX,int qiY,int zhX,int zhY, int x){ //x为标志，用于控制要不要显示所有的路径 当其非0是显示所有的路径

char n=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--;} void fuzhi(){ int i,j;for(i=0;i<17;i++){

for(j=0;j<22;j++){

jilu[i][j]=arr[i][j];

} } }

总结

此次课程设计相对于我来说，难度较大，相对于这个学期写的那些小算法来说，这个课程设计能充分发挥出学习数据结构后的能力；而相对于之前做的设计性实验，又有了实际的应用，现实应用度增加。

从接触C语言编程到现在，我就觉得：编程不是简简单单的写出程序，更多的是处理出现的语法和逻辑错误。在这次课程设计中，我深刻的体会到 编程不是一种简单的事，编程不但需要耐心，更需要细心。编出大体的程序架构，花费了我的时间并不多，但我很多时间是用在调试和测试数据上！有些现在看着简单的语法错误，一时竟然无从下手。我想，这和我C语言基础薄弱有很大关系，以后要加强认识。

总的来说，这次课程设计，让我学了很多，总结了很多！

参考文献

[1] 严蔚敏，吴伟民.数据结构（C语言版）[M].北京 清华大学出版社，2007 [2] 谭浩强.C程序设计（第三版）[M].北京 清华大学出版社，2007 [3] 谭浩强.C程序设计题解与上机指导（第三版）[M].北京 清华大学出版社，2007 [4] 严蔚敏，吴伟民，米 宁.数据结构题集（C语言版）[M].北京 清华大学出版社，2007 [5] 互联网的相关信息和内容

第四篇：课程设计(校园导游)

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长 春 大 学

课程设计纸

一、设计题目

校园导游咨询

二、需求分析

（1）设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示学校各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。

（2）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。

（3）为来访客人提供图中任意景点相关信息的查询。（4）界面美观，方便使用。通过主菜单操作。

三、总体设计

3.1 设计思路

设计一个校园导游系统，应用到数据结构中学到的图的建立，各景点应存在一个图中，而计算不重复路线的时候需要应用到弗洛伊德图的遍历。计算俩景点间最短路径应用到最小生成树的遍历。

景点数据装在一个图中，能够输入图的顶点和边的信息，并存储到相应存储结构中然后输出图的邻接矩阵。

邻接矩阵是表示顶点之间相邻关系。

生成树是指：如果G是一个图，这个图的生成子图T是树，那么可以说T为G的生成树。一个图有生成树当且仅当这个图连通。可通过求该网络的最小生成树达到求解线路或总代价最小的最佳方案。

弗洛伊德算法是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。它是从图的带权邻接矩A=[a(i,j)] n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；„„；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。3、2系统功能设计

本系统除了有主程序模块外还有3个子功能菜单。3个子功能的设计描述如下。（1）学校景点介绍

学校景点介绍由函数introduce()实现。当用户选择该功能，系统即能输出学校全部景点的信息：包括景点编号、景点名称及景点简介。

共 页

第 页

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长 春 大 学

课程设计纸

（2）查看两景点间最短路径

查看两景点间最短路径由函数shortestdistance()实现。该功能采用弗洛伊德（Floyd）算法实现。当用户选择该功能，系统能根据用户输入的起始景点及目的地景点编号，查询任意两个景点之间的最短路径线路及距离。

（3）退出

即退出校园导游系统，由exit(0)函数实现。3、3 模块间调用关系

主程序模块

（界面）

景点最短路径查询

景点信息查询

退出

四、详细设计 4、1数据存储

(1)无向带权图（无向网）的定义

int i,j;

char k;

for(i=0;i<=n;i++)

for(j=0;j<=n;j++)

{

cost[i][j]=INT_MAX;

}

cost[1][3]=cost[3][1]=2;

cost[2][3]=cost[3][2]=1;

cost[2][4]=cost[4][2]=2;

cost[3][10]=cost[10][3]=4;

cost[1][10]=cost[10][1]=4;

cost[2][10]=cost[10][2]=4;

cost[4][10]=cost[10][4]=4;

cost[1][4]=cost[4][1]=5;

cost[4][5]=cost[5][4]=3;

cost[4][9]=cost[9][4]=4;

共 页

第 页

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长 春 大 学

课程设计纸

cost[5][9]=cost[9][5]=8;cost[5][7]=cost[7][5]=4;cost[5][6]=cost[6][5]=2;cost[6][7]=cost[7][6]=1;cost[7][8]=cost[8][7]=3;cost[8][6]=cost[6][8]=4;cost[1][1]=cost[2][2]=cost[3][3]=cost[4][4]=cost[5][5]=0;cost[6][6]=cost[7][7]=cost[8][8]=cost[9][9]=cost[10][10]=0;

（2）全局变量定义

#define INT_MAX 10000 #define n 10 int cost[n][n];

/* 边的值*/ int shortest[n][n];

/* 两点间的最短距离*/ int path[n][n];

/* 经过的景点*/ 4、2主程序模块

用于作为界面，显示校园景点和概况描述，提供各子模块的连接 如上图所示 程序设计 while(1)

{

printf(“----------------欢迎使用中北大学导游系统!----------------n”);

printf(“1.景点信息查询„„„请按 i(introduc)键n”);

printf(“2.景点最短路径查询„请按 s(shortestdistance)键n”);

printf(“3.退出系统„„„„„请按 e(exit)键n”);

printf(“学校景点列表:n”);

printf(“1:学校南门

”);

printf(“2:学生公寓

”);

printf(“3:柏林园

”);

printf(“4:餐厅

”);

printf(“5:体育馆n”);

printf(“6:图书馆

”);

printf(“7:重点实验室

”);

printf(“8:主楼

”);

printf(“9:科艺苑

”);

printf(“10:国防生公寓n”);

printf(“请选择服务:”);

scanf(“n%c”,&k);

共 页

第 页

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长 春 大 学

课程设计纸

switch(k)

{

case 'i':

printf(“进入景点信息查询:”);

introduce();

break;

case 's':

printf(“进入最短路径查询:”);

shortestdistance();

break;

case 'e':

exit(0);

default:

printf(“输入信息错误！n请输入字母i或s或e.n”);

break;

}

} 4、3景点信息查询模块

在主菜单下，用户输入i回车，根据屏幕提示输入一个要查询的景点编号3回车后，运行结果如上图所示。

不足之处：仅能根据景点编号进行查询，可以增加根据景点名进行查询的功能。

程序设计

void introduce(){/*景点介绍*/

int a;

printf(“您想查询哪个景点的详细信息?请输入景点编号:”);

scanf(“%d”,&a);

getchar();

printf(“n”);

switch(a)

{

case 1:

printf(“1:学校南门nn 学校的正门，前面竖立着一尊彭德华的石

共 页

第 页

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长 春 大 学

课程设计纸

像，气势宏伟。nn”);break;

case 2:

printf(“2:学生公寓集中的地方。nn”);break;

case 3:

printf(“3:柏林园nn 晨读锻炼得地方。nn”);break;

case 4:

printf(“4:餐厅nn 学生老师就餐的地方nn”);break;

case 5:

printf(“5:体育馆nn 体育馆nn 学生上体育课及运动的场地，设有田径场、足球场、篮球场等。nn”);break;

case 6:

printf(“6:图书馆nn 学校信息资源中心，内设大量的自习室。nn”);break;

case 7:

printf(“7:重点实验室nn 我校的研究科研中心nn”);break;

case 8:

printf(“8:主楼nn 学校行政办公的主楼。nn”);break;

case 9:

printf(“9:科艺苑nn 有咖啡厅和放映室。nnn”);break;

case 10:

printf(“10: 国防生公寓nn 国防生居住地地方。nn”);break;

default:

printf(“景点编号输入错误！请输入1->10的数字编号！nn”);break;

} }/*introduce*/ 4、4景点最短路径查询模块

在主菜单下，用户输入3回车，根据屏幕提示输入一个出发景点编号及目的地景点号：6“,”3回车后，运行结果如上图所示。

不足之处：只能看到最短路径编号，但不知具体名称，设计还不够人性化。

程序设计（由floyed()和display(i,j)两个子模块完成）void floyed(){/*用floyed算法求两个景点的最短路径*/

共 页

第 页

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长 春 大 学

课程设计纸

int i,j,k;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{

shortest[i][j]=cost[i][j];

path[i][j]=0;

}

for(k=1;k<=n;k++)

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(shortest[i][j]>(shortest[i][k]+shortest[k][j]))

{/*用path[][]记录从i到j的最短路径上点j的前驱景点的序号*/

shortest[i][j]=shortest[i][k]+shortest[k][j];

path[i][j]=k;

path[j][i]=k;

} }/*floyed*/

void display(int i,int j){/* 打印两个景点的路径及最短距离 */

int a,b;

a=i;

b=j;

printf(“您要查询的两景点间最短路径是:nn”);

if(shortest[i][j]!=INT_MAX)

{

if(i

{

printf(“%d”,b);

while(path[i][j]!=0)

{/* 把i到j的路径上所有经过的景点按逆序打印出来*/

printf(“<-%d”,path[i][j]);

if(i

j=path[i][j];

else

i=path[j][i];

}

printf(“<-%d”,a);

printf(“nn”);

printf(“(%d->%d)最短距离是:%d米nn”,a,b,shortest[a][b]);

}

else

{

printf(“%d”,a);

while(path[i][j]!=0)

{/* 把i到j的路径上所有经过的景点按顺序打印出来*/

printf(“->%d”,path[i][j]);

共 页

第 页

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长 春 大 学

课程设计纸

if(i

j=path[i][j];

else

i=path[j][i];

}

printf(“->%d”,b);

printf(“nn”);

printf(“(%d->%d)最短距离是:%5d米nn”,a,b,shortest[a][b]);

}

}

else

printf(“输入错误！不存在此路！nn”);

printf(“n”);}/*display*/ 4、5退出

在主菜单下，用户输入e回车，即退出校园导游系统。

五、设计总结5、1用户手册

1．本程序执行文件为：湖北第二师范学院校园导游系统.exe 2．进入本系统之后，随即显示系统主菜单界面。用户可在该界面下输入各子菜单前对应的数字并按回车，执行相应子菜单命令。

3．查询景点信息都是通过输入景点编号并按回车实现，两个景点号之间用空格隔开。进入本系统后，建议先选择子菜单1――学校景点介绍，以了解景点名称和景点编号的对应关系。5、2心得体会

通过本次课程设计实验，使我更能熟练地掌握c语言和数据结构等知识的综合运

共 页

第 页

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长 春 大 学

课程设计纸

用。当然在课程设计期间，也遇到了大大小小的一些问题，是我看到了自己的不足之处，使我认识到在以后的学习中要善于发现自己的不足，找出自己的薄弱环节，以便能够更好的去巩固所学的。

本次设计中要求求最短路径，不重复走完一个图，就必须了解最短路径的算发和图的遍历。在拿到题目时，通过查找相关的资料才回忆起这两种方法的具体算法。根据程序的具体要求来设计算法。在选用存储方法是，要尽量选用时间复杂度较小的方法，这样能够节省程序执行时间，提高查询效率。

课程设计中所使用的计算机语言其使用范围比较广阔，在很多编程中都可以用到，所以无论以后我们从事计算机编程、软件设计还是硬件、网络等领域，都应该学会、学精一门编程语言，这对我们以后的学习和工作有很大的帮助。

共 页

第 页

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长 春 大 学

课程设计纸

附录

/*包含头文件*/ #include #include

/*定义符号常量*/ #define INT_MAX 10000 #define n 10

/*定义全局变量*/ int cost[n][n];/* 边的值*/ int shortest[n][n];/* 两点间的最短距离*/ int path[n][n];/* 经过的景点*/

/*自定义函数原型说明*/ void introduce();int shortestdistance();void floyed();

void display(int i,int j);

void main(){/*主函数*/

int i,j;

char k;

for(i=0;i<=n;i++)

for(j=0;j<=n;j++)

cost[i][j]=INT_MAX;

cost[1][3]=cost[3][1]=2;

cost[2][3]=cost[3][2]=1;

cost[2][4]=cost[4][2]=2;cost[3][10]=cost[10][3]=4;cost[1][10]=cost[10][1]=4;cost[2][10]=cost[10][2]=4;cost[4][10]=cost[10][4]=4;

cost[1][4]=cost[4][1]=5;cost[4][5]=cost[5][4]=3;cost[4][9]=cost[9][4]=4;cost[5][9]=cost[9][5]=8;cost[5][7]=cost[7][5]=4;

cost[5][6]=cost[6][5]=2;

共 页

第 页

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长 春 大 学

课程设计纸

cost[6][7]=cost[7][6]=1;

cost[7][8]=cost[8][7]=3;

cost[8][6]=cost[6][8]=4;

cost[1][1]=cost[2][2]=cost[3][3]=cost[4][4]=cost[5][5]=0;

cost[6][6]=cost[7][7]=cost[8][8]=cost[9][9]=cost[10][10]=0;

while(1)

{

printf(“----------------欢迎使用中北大学导游系统!----------------n”);

printf(“1.景点信息查询„„„请按 i(introduc)键n”);

printf(“2.景点最短路径查询„请按 s(shortestdistance)键n”);

printf(“3.退出系统„„„„„请按 e(exit)键n”);

printf(“学校景点列表:n”);

printf(“1:学校南门

”);

printf(“2:学生公寓

”);

printf(“3:柏林园

”);

printf(“4:餐厅

”);

printf(“5:体育馆n”);

printf(“6:图书馆

”);

printf(“7:重点实验室

”);

printf(“8:主楼

”);

printf(“9:科艺苑

”);

printf(“10:国防生公寓n”);

printf(“请选择服务:”);

scanf(“n%c”,&k);

switch(k)

{

case 'i':

printf(“进入景点信息查询:”);

introduce();

break;

case 's':

printf(“进入最短路径查询:”);

shortestdistance();

break;

case 'e':

exit(0);

default:

printf(“输入信息错误！n请输入字母i或s或e.n”);

break;

}

} }/*main*/

共 页

第 页

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长 春 大 学

课程设计纸

void introduce(){/*景点介绍*/

int a;

printf(“您想查询哪个景点的详细信息?请输入景点编号:”);

scanf(“%d”,&a);

getchar();

printf(“n”);

switch(a)

{

case 1:

printf(“1:学校南门nn 学校的正门，前面竖立着一尊彭德华的石像，气势宏伟。nn”);break;

case 2:

printf(“2:学生公寓集中的地方。nn”);break;

case 3:

printf(“3:柏林园nn 晨读锻炼得地方。nn”);break;

case 4:

printf(“4:餐厅nn 学生老师就餐的地方nn”);break;

case 5:

printf(“5:体育馆nn 体育馆nn 学生上体育课及运动的场地，设有田径场、足球场、篮球场等。nn”);break;

case 6:

printf(“6:图书馆nn 学校信息资源中心，内设大量的自习室。nn”);break;

case 7:

printf(“7:重点实验室nn 我校的研究科研中心nn”);break;

case 8:

printf(“8:主楼nn 学校行政办公的主楼。nn”);break;

case 9:

printf(“9:科艺苑nn 有咖啡厅和放映室。nnn”);break;

case 10:

printf(“10: 国防生公寓nn 国防生居住地地方。nn”);break;

default:

printf(“景点编号输入错误！请输入1->10的数字编号！nn”);break;

} }/*introduce*/

int shortestdistance(){/*要查找的两景点的最短距离*/

int i,j;

printf(“请输入要查询的两个景点的编号(1->10的数字编号并用','间隔):”);

共 页

第 页

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长 春 大 学

课程设计纸

scanf(“%d,%d”,&i,&j);

if(i>n||i<=0||j>n||j<0)

{

printf(“输入信息错误！nn”);

printf(“ 请输入要查询的两个景点的编号(1->10的数字编号并用','间隔):n”);

scanf(“%d,%d”,&i,&j);

}

else

{

floyed();

display(i,j);

}

return 1;}/*shortestdistance*/

void floyed(){/*用floyed算法求两个景点的最短路径*/

int i,j,k;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{

shortest[i][j]=cost[i][j];

path[i][j]=0;

}

for(k=1;k<=n;k++)

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(shortest[i][j]>(shortest[i][k]+shortest[k][j]))

{/*用path[][]记录从i到j的最短路径上点j的前驱景点的序号*/

shortest[i][j]=shortest[i][k]+shortest[k][j];

path[i][j]=k;

path[j][i]=k;

} }/*floyed*/

void display(int i,int j){/* 打印两个景点的路径及最短距离 */

int a,b;

a=i;

b=j;

共 页

第 页

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 长 春 大 学

课程设计纸

printf(“您要查询的两景点间最短路径是:nn”);

if(shortest[i][j]!=INT_MAX)

{

if(i

{

printf(“%d”,b);

while(path[i][j]!=0)

{/* 把i到j的路径上所有经过的景点按逆序打印出来*/

printf(“<-%d”,path[i][j]);

if(i

j=path[i][j];

else

i=path[j][i];

}

printf(“<-%d”,a);

printf(“nn”);

printf(“(%d->%d)最短距离是:%d米nn”,a,b,shortest[a][b]);

}

else

{

printf(“%d”,a);

while(path[i][j]!=0)

{/* 把i到j的路径上所有经过的景点按顺序打印出来*/

printf(“->%d”,path[i][j]);

if(i

j=path[i][j];

else

i=path[j][i];

}

printf(“->%d”,b);

printf(“nn”);

printf(“(%d->%d)最短距离是:%5d米nn”,a,b,shortest[a][b]);

}

}

else

printf(“输入错误！不存在此路！nn”);

printf(“n”);}/*display*/

共 页

第 页

第五篇：数据结构课程设计-全国铁路交通咨询模拟

数据库课程设计

—全国铁路咨询系统

目录

一．需求分析****************************************** 3

二．概要设计******************************************

三．储存结构设计**************************************

四．详细设计******************************************

五．用户手册******************************************

六．测试数据******************************************

七．心得体会****************************************** 8 11 17 18 26

一、需求分析

1、问题描述

由于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中 的时间尽可能短，出门旅游的游客则期望旅费尽可能省。编制一个全国城市间的交通咨询程 序，为旅客提供两种最优决策的交通咨询。

根据铁路的特征，数据的储存需要使用图的结构。每个城市之间有不同的车次，每个车次的始发站、路过车站和终点站都不一样，所以两个城市之间就有指向明确的边，是一个有向图；而由于车次的不一样，所以发车时间，到站时间，价格等也会不一样；所以每两个点之间不止两条边，可能存在不同的多条边。

2、功能需求

铁路咨询的对象是用户，所以，需要一个对用户友好的功能菜单，根据用户可能需要的实际需求，功能菜单中可能会包括以下要点：

1：显示所有车站信息

2: 显示所有车次信息（包括时刻表）

3: 查询车站信息

4: 查询两个城市之间的铁路信息

5: 增加或删除车站

6: 增加或删除铁路信息

7: 增加、删除或修改时刻表、距离和价格

8：寻找两城市间最省钱的一条路径

9：寻找两城市间最省时间的一条路径 10：寻找两城市间所有路径(按费用从低到高排序输出)

11：寻找两城市间所有路径(按所用时间从少到多排序输出)

12：退出咨询系统

图的初始数据从文本中读入，文本是老师给的标准数据。

3、输入及输出格式

(1):输入格式：

A：图的初始数据输入

数据的初始化是需要从文本中读入的，所以不需要有专门的文本输入函数，只需要给出读文本的函数input（）；使用input（）函数从测试数据的三个文本中读入数据，然后使用创建图的函数CreateGraph（）创建起整个图。初始数据的读入，分别是从station.txt中读入每个城市站点的名称的城市编号，从iinformation.txt中读入每个城市间的铁路信息，从railway.txt中读入所有铁路线的信息。

如：

以下从station.txt中节选部分

0 北京广州石家庄郑州武汉长沙

以下从information.txt中节选部分

出发城市编号 到达城市编号 车次 里程

费用

出发时刻

到达时刻

0

1000 287

62.5

0000

0246

0

1016 287

0060

0275

0

1001 137

23.5

0000

0117

0

1017 137

28.5

0060

0163

0

1002 1199 156.5 0000

1028

1008 1257 162.5 0000

1077

以下从railway.txt中节选部分

各条铁路线上城市编号（此行可去掉）

京广线 0 2 3 4 5 6 1

京九线 0 13 14 12

京沪线 0 8 9 10 11 7

陇海线 18 10 3 20 24 19

B：用户要求输入

用户在使用本程序时，会要求用户输入各种数据，如城市编号id、抉择选项y/n等；用户只需要按照程序菜单的要求输入即可。如城市编号id就是初始化数据（文本数据）中每个城市就有的编号，用户在不知道城市编号之前先查看一下城市信息就可以清楚明了的知道城市id了。

(2):输出格式

在系统的管理下，为了用户的查询方便，需要有多重输出方式。如每条铁路线上信息的输出。这里面就包括了，在每条铁路上所有车次信息，每个车次始发站信息、过站信息和终点站信息。

样例如下：

兰新线中有以下车次：

1005次列车运行情况：

出发城市

到达城市

车次

距离(km)出发时间

到达时间

费用(元)

兰州

酒泉

1005

748

0：0

10：41

酒泉

乌鲁木齐

1005

797

10：51 22：14

152.5

乌鲁木齐

阿拉山口

1005

477

22：24

5：13

64.5

1013次列车运行情况：

出发城市

到达城市

车次

距离(km)出发时间

到达时间

费用(元)

阿拉山口

乌鲁木齐

1013

477

0： 0

6：49

64.5

乌鲁木齐

酒泉

1013

797

6：59

18：22

152.5

酒泉

兰州

1013

748

18：32

5：13

对于每个城市信息的输出，只需要输出经过每个城市的铁路新路即可，当然必须得输出城市站点的id，方便用户的查询和管理

样例如下：

城市编号

城市名称

过站铁路线

0

北京

京广线

京九线

京沪线

广州

京广线

石家庄

京广线

郑州

京广线

陇海线

武汉

京广线

长沙

京广线

株洲

京广线

沪昆线

上海

京沪线

沪昆线

二、概要设计

1.数据特性分析

（1）：整体结构分析

铁路交通咨询模拟系统管理的是全国的各个城市间的铁路信息。对于整体的全

国铁路信息来说，每一个城市站点就是一个顶点节点，城市与城市之间的每一个车

次信息就是一条有向边。所有整个咨询系统应该是一个有向图结构。从A城市出发

到B城市，可能会有多个车次。

如下例：

出发城市

到达城市

车次

距离(km)出发时间

到达时间

费用(元)

北京

石家庄

1000

287

0： 0

4： 6

62.5

北京

石家庄

1016

287

1： 0

4：35

所以每两个城市顶点之间就可能会有多条有向边，所以这个图也不会是 一个有

向简单图了。为了城市节点能够动态的扩充和删除不受影响，我对于顶点的储存采

用链表结构不使用顺序表结构，定义一个顶点链表类VertexList。这样，虽然链表查

询和其节点的删除的时间复杂度受到了一定的影响，但这样设计出来的铁路网图才

更具有一般性个实用性。对于查找的时间复杂度问题的解决，我在后面也会给出方案。

（2）：城市顶点分析

对于每一城市来说，在全国的铁路网中，它就是一个火车站节点。每一个火车，它都应该会有自己的名字，过站的铁路线等。为了咨询系统管理和维护的方便，在 文本数据中，我们就人为的给每一个城市都编上序号id，每一个不同id对应了一

个不同的城市节点。由于每个城市的id都是唯一的，所以在顶点的链表结构里面，完全可以定义一个哈希表haxi[n]，对于haxi[i]来说，它存储的就是id为i的城市

在内存中地址。这样，顶点链表在哈希表的支持下，就能完美解决查找、添加、删除的时间复杂度问题了。

在整个铁路网中，每一个城市就是顶点，每一个顶点，就是应该有一个边链表

用于储存此城市能到达所有城市的各个不同车次的信息，也就是各个不同的边。如：

出发城市编号 到达城市编号 车次 里程

费用

出发时刻

到达时刻

0

1000 287

62.5

0000

0246

0

1016 287

0060

0275

从上例我们可以看出，对于每个顶点的不同边来说，每一个不同的边就有一个独有

的车次。所以这样，对于边的储存，我们也可以采用哈希表结构。经观察发现，每 一车次都大于1000，所以，哈希表的id=车次-1000；对于编号为a的城市节点haxi[k]

来说，它储存的是为城市a中车次为：1000+k的一条边，边里面就有到达城市、出发和到达时间、费用、距离等等。

（3）：边数据分析

对于图来讲，边就是一个逻辑结构，沟通顶点与顶点之间的关系。同时了，边还有其物理特性。他需要储存边的权值等，它需要开辟储存空间来存储数

据。在铁路网中，每两个城市之间不同的车次信息就是一条不同的边，所以，我需要把物理特性给单独列出来，成为一个类LineInformation，用于表示边

的物理信息。对于图中抽象的边，也需要定义一个类EdgeNode，用于沟通

图中原本孤立的顶点，使之变成一个完整的图

2.整体概要设计

前面，我提到了有顶点类station、顶点链表类VertexList、边的物理类LineInformation和边的逻辑类EdgeNode、火车线路类railway；对于整个完整的图类来说，还有两个主要的类没有提及，那就是图类RailwayNet和管理图类的类management。当然对于图中需要完成各个不同功能的时候，我还写了许多的辅助类。如查找两个车站之间所有路径时需要用到的LinStack，当然还有LinStack的类的基石StackNode类。整个咨询系统还有许多的结构体，这些结构体的功能我就不一一叙述了，详细可见源代码的注释。下面我就列出各个类的关系图

三．储存结构设计

1、存储结构的确定

数据结构的目的是有效组织和处理数据。为了有效组织和处理数据，先要分析多项式操作的特点和指针所占空间比例，然后确定最优的存储结构。

1.铁路网是由铁路和火车站构成，每个火车站相当于一个定点，每新建一条铁路就相当于新建定点之间的边

2.车站之间可以任意到达，可直接相连，也可以间接相连，且怎么连接是不固定的。3.综上所述，资源管理器的存储结构采用树形结构。

2、类的结构设计图：

management类图：

RailWay类图：

VertexList类图：

RailWay类图：

LineInformation类图：

EdgeNode结构图：

Station类图；

四、详细设计

1.管理类management

class management{ private:

vector m_city;vector m_edge;vector m_rail;RailwayNet m_graph;void input();void VertexDisplay();//边的输出函数，输出一条边的信息 void EdgeDisplay(EdgeNode *edge);//输出函数，被 RailwayDisplay（）调用

void NextDisplay(EdgeNode* edge, LinStack & UsedTrainNumber, int a);void RailwayDisplay();void SearchStation();void SearchRail();void EditStation();void EditRail();void EditInformation();void ShortestCost();void ShortestTime();void SearchAll(vector & AllPath);void PathDispaly(vector & path);void OrderOnCost();void OrderOnTime();public: 2.图类RailwayNet //全国铁路信息网类（邻接表图类）class RailwayNet{ private:

//私有的函数，以深度优先遍历的方式寻找两点之间的所有路径

void DepthFirstSearchPath(vector & pa, time_and_cost_path & p, VertexList vertex;//顶点链表 vector m_rail;EdgeNode *edge, int terminal, LinStack & UsedVertex);

//私有函数，以Dijkastra算法寻找最节省时间的路径

void ShortestCost(vector & OptimalPath, int origin, int terminal);// 获取起点origin到终点terminal的最少用时 void ShortestTime(int origin, int terminal);void ShortestTime2(vector & OptimalPath, int origin, int terminal);//快速排序

void QuickSort(vector & AllPath, int low, int high, int option);public:

};

VertexList & Vertex(){ return vertex;} vector & GetRail(){ return m_rail;} //插入顶点

void InsertVertex(station* s);//在顶点v1和v2之间插入一条边(边的起点为v1，终点为v2)void InsertEdge(int v1, int v2, EdgeNode* & ed);//删除编号为id的城市顶点 void DeleteVertex(int id);//删除边edge

void DeleteEdge(int v1, int v2);//创建一个邻接表图

void CreateGraph(RailwayNet & graph, vector & city, vector //输出图

void display(RailwayNet & graph);//返回顶点v1和v2的第一条边

EdgeNode* const GetFirstEdge(int v1, int v2);//获取起点origin到终点terminal的最少费用

float GetShortestCost(int origin, int terminal, LineInformation & edge);//获取边路径path中的用时

int GetPathTime(vector & path);//获取边路径path中的费用

float GetPathCost(vector & path);//对vector中的元素按照要求排序【option为 1 表示以最省钱方式，为 2 表示以最省时方式】 void Sort(vector & AllPath, int option);//求点origin到terminal的所有路径

void GetAllPath(vector & AllPath, int origin, int terminal);//求点origin到terminal的最短“路径”（路程最短或时间最省）【使用Dijkastra算法】 void BestOption(vector & OptimalPath, int option, int origin, int & edge, vector & rail);terminal);3.顶点链表类

//顶点链表类 class VertexList{ private:

station *head;//头指针

int size;//链表的大小（元素的个数）

station* haxi[1000];//哈希表，内存有节点的地址(哈希表中的下标与对应城市节点的ID相等)public:

};VertexList();~VertexList();station* & GetHead(){ return head;} int & GetSize(){ return size;} //按照id从小到大的顺序将city插入链表中 void insert(station* city);//删除城市编号为id的节点 void Delete(int id);//根据城市的id获取城市节点 station* GetVertex(int id);station** GetVertexHaxi(){ return haxi;} int IsVertexExist(int id);

4.顶点类

class station{ private:

int m_size;//边链表的大小

EdgeNode* haxi[100];//以此车站为始发站的边的哈希表(下标为：车次-1000)vector ha2;//以此车站为终点的边在其哈希表中的下标 station();//默认构造函数

station(string na, int i);//构造函数 station(const station & sta);//复制构造函数 void Delete();//删除函数 //接口函数 station* prior;//指向上一个车站 station *next;//指向下一个车站 EdgeNode *head;//指向第一条边节点 string m_name;int m_id;vector m_rail;public:

};string & GetName(){ return m_name;} int & GetId(){ return m_id;} vector & GetRail(){ return m_rail;} station* & GetPrior(){ return prior;} station* & GetNext(){ return next;} EdgeNode* & GetHead(){ return head;} int & GetSize(){ return m_size;} EdgeNode** GetHaxi(){ return haxi;} vector & GetHa(){ return ha2;} 5.边节点类EdgeNode //边结点结构体 struct EdgeNode{

LineInformation information;EdgeNode *next;//下一个边结点 EdgeNode *prior;//上一个边节点

};

6.边物理类LineInformation

class LineInformation{ private:

int m_DepartId;//出发城市编号 int m_ArriveId;//到达城市编号 int m_TrainNumber;//车次 int m_distance;//车程 float m_cost;//费用 int m_DepartTime;//出发时间 int m_ArriveTime;//到达时间

//默认构造函数 int DepartId=0, int ArriveId=0，LineInformation(int DepartId = 0, int ArriveId = 0, int Train = 0, int distance =-1, //复制构造函数

LineInformation(const LineInformation & l);~LineInformation(){};LineInformation operator=(const LineInformation& e);//接口函数

int & GetDepartTime(){ return m_DepartTime;} int & GetArriveTime(){ return m_ArriveTime;} int & GetTrainNumber(){ return m_TrainNumber;} public: float cost = 0, int DepartTime =-1, int ArriveTime =-1);

};int & GetDepartId(){ return m_DepartId;} int & GetArriveId(){ return m_ArriveId;} int & GetDistance(){ return m_distance;} float & GetCost(){ return m_cost;}

7.火车线路类railway

class railway{ private:

};string m_name;//火车线名

vector m_station;//线路进过的火车站的id railway(string s = “ ”):m_name(s){} string & GetName();vector & GetStation();void Delete(int a);public:

8.自定义栈类

template class LinStack;template class StackNode{

};

template class LinStack{ private: friend class LinStack;T data;

//定义类LinStack为友元

//数据元素 private: StackNode *next;

//指针

//前视定义,否则友元无法定义

//模板类型为T

public: //构造函数1,用于构造头结点

StackNode(StackNode *ptrNext = NULL);//构造函数2,用于构造其他结点

StackNode(const T& item, StackNode *ptrNext = NULL);~StackNode(){};

};StackNode *head;int size;

//头指针 //数据元素个数 //构造函数 public: LinStack(void);~LinStack(void);T Pop(void);

//析构函数 //入栈 //出栈 //取栈顶元素 //堆栈非空否 void Push(const T& item);T GetTop(void)const;

int NotEmpty(void)const;

bool IsInStack(T a);//判断元素a是否在栈中 void Empty();//清空栈

int GetSize();//获取栈中元素的个数 void display();//输出栈中元素

五、用户手册

1.本程序运行在Windows操作系统下，VS2013，按F7编译，F5运行。

2.在程序运行前有预设函数，最好选择预设函数，然后进行测试。

3.在菜单中选择你想进的功能，然后输入前面的数字即可。

用户菜单如下：

*****************************全国铁路交通咨询模拟**************************** 1: 显示所有车站信息

2: 显示所有车次信息（包括时刻表）

3: 查询车站信息“

4: 查询两个城市之间的铁路信息

5: 增加或删除车站

6: 增加或删除铁路信息

7: 增加、删除或修改时刻表、距离和价格

8: 寻找两城市间最省钱的一条路径

9: 寻找两城市间最省时间的一条路径

10:寻找两城市间所有路径(按费用从低到高排序输出)

11:寻找两城市间所有路径(按所用时间从少到多排序输出)

12: 退出咨询系统”

*****************************************************************************"

六、测试数据

1.用户菜单

在输入指令一栏输入你想要使用的功能的数字编号。如：输入1 功能为：显示所有车站信息

由于数据过多，这里只截取部分输出

输入指令：2 功能：查询所有车次信息

数据量太大，也只截取部分输出。

输入指令：3 功能：查询车站信息

车站信息有：

1.从此车站出发各个车次信息。2.从其他车站出发到达此车站的信息

输入指令：4 功能：查询两个车站之间的信息

查询的时候，是由先后顺序的，先输入的是出发城市，后输入的到达城市

输入指令：5 功能：增加或删除车站

样例1：增加成功

样例2：增加失败

错误原因：编号输入错误 编号id为12：九龙

所以此编号已有城市占用，输入错误

样例3：删除成功

现在可查询广州的信息

发现广州此时已不存在，删除成功

样例4：删除失败

错误原因：id为31 的城市不存在

输入指令：6 功能：增加或删除铁路信息

样例1：增加失败

失败原因：id为1的城市已删除，不能再城市1余城市6之间增加铁路

样例2：增加成功

此时新建铁路状态：还有铁路线，没有车次 注：想要铁路线有火车运行，必须补充车次信息

样例3：删除成功

样例4：删除失败

失败原因：不存在从城市9到城市13的铁路

输入指令：7 功能：增加、删除或修改时刻表、距离和价格

测试样例：

可查询修改后的价格 出发城市：6 株洲 到达城市：5 长沙

车次为：1022的信息中 价格：999 修改成功！

输入指令：8 功能：寻找两城市间最省钱的路劲

输入指令：9 功能：寻找两城市间最省时间的路劲

输入指令：10 功能：寻找两城市间所有路径(按费用从低到高排序输出)

数据过多，取前二十条显示，我也只截取前一部分数据

输入指令：11 功能：寻找两城市间所有路径(按所用时间从少到多排序输出)

数据过多，取前二十条显示，我也只截取前一部分数据

注：后面的测试时前面面修改后的结果，所以，计算的结果和初始化数据计算的结果可能会不一致，这是因为只是可能计算会用到我修改后的数据，所以存在不一致的问题。

七、心得体会