数据结构-校园导游系统课程设计.doc

滨江学院

《数据结构》课程设计

题 目 校园导游咨询程序设计

学 号
学生姓名

院 系

专 业

指导教师

二Ｏ一二 年 月 日

1、 题目的内容及要求
设计一个校园导游程序，为来访的客人提供各种信息查询服务。

2、 需求分析
（1）设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示学校各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。
（2）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。
（3）为来访客人提供图中任意景点相关信息的查询。

3、概要设计
1．功能模块图；
void CreateUDN();//创建无向网
void Search();//查询景点信息
void Shortestpath(int i);//计算最短路径
void Output(int sight1,int sight2);//输出函数

2．各个模块详细的功能描述。
CreateUDN();//创建无向网、主要用来保存各景点信息
Search();//查询景点信息、景点的名称及介绍
Shortestpath(int i);//计算两景点间最短路径
Output(int sight1,int sight2);//输出两景点最短路径及信息

3.模块图

4、 详细设计
一、图的储存结构
#define Max 30000
#define NUM 10
typedef struct ArcCell
{
int adj; /* 相邻接的景点之间的路程 */ 
}ArcCell; /* 定义边的类型 */ 
typedef struct VertexType
{
int number; /* 景点编号 */ 
char *sight; /* 景点名称 */
char *description;/* 景点描述 */
}VertexType; /* 定义顶点的类型 */ 

typedef struct
{
VertexType vex[NUM]; /* 图中的顶点，即为景点 */
ArcCell arcs[NUM][NUM];/* 图中的边，即为景点间的距离 */
int vexnum,arcnum;/* 顶点数，边数 */ 
}MGraph;  /* 定义图的类型 
二、 算法
1.主程序
void main()
{

int v0,v1;
char ck;
CreateUDN(NUM,11);
do
{
ck=Menu();
switch(ck)
{
case '1':
system("cls");
// narrate();
printf("\n\n\t\t\t请选择起点景点（0～9）：");
scanf("%d",&v0);
printf("\t\t\t请选择终点景点（0～9）：");
scanf("%d",&v1);
ShortestPath(v0);  /* 计算两个景点之间的最短路径 */
output(v0,v1);  /* 计算两个景点之间的最短路径 */
printf("\n\n\t\t\t\t请按任意键继续...\n");
getchar();
getchar();
break;
case '2':search();
break;
case '3':
system("cls");
//narrate();
x[0]=1;
HaMiTonian(1);
printf("\n\n\t\t\t\t请按任意键继续...\n");
getchar();
getchar();
break;
};
}while(ck!='e');

}

2. 输出程序
void output(int sight1,int sight2)
{
int a,b,c,d,q=0;
a=sight2;
if(a!=sight1) /* 如果景点二不和景点一输入重合，则进行 */
{
printf("\n\t从%s到%s的最短路径是",G.vex[sight1].sight,G.vex[sight2].sight);/* 输出提示信息 */ 
printf("\t(最短距离为 %dm.)\n\n\t",D[a]);
printf("\t%s",G.vex[sight1].sight);
d=sight1;  /* 将景点一的编号赋值给d */ 
for(c=0;c<NUM;++c)
{
gate:;
P[a][sight1]=0;
for(b=0;b<NUM;b++)
{
if(G.arcs[d][b].adj<30000&&P[a][b]) /* 如果景点一和它的一个临界点之间存在路径且最短路径 */ 
{
printf("-->%s",G.vex[b].sight); /* 输出此节点的名称 */ 
q=q+1; /* 计数变量加一，满8控制输出时的换行 */
P[a][b]=0;
d=b;  /* 将b作为出发点进行下一次循环输出，如此反复 */
if(q%9==0) printf("\n");
goto gate;
}
}
}
}

}

3. 求最短路径
 void ShortestPath(int num)
{
int v,w,i,t;
int final[NUM];
int min;
for(v=0;v<NUM;v++)
{
final[v]=0;
D[v]=G.arcs[num][v].adj;
for(w=0;w<NUM;w++)
P[v][w]=0;
if(D[v]<30000)
{
P[v][num]=1;
P[v][v]=1;
}
}

D[num]=0;
final[num]=1;

for(i=0;i<NUM;++i)
{
min=Max;
for(w=0;w<NUM;++w)
if(!final[w])
if(D[w]<min)
{
v=w;
min=D[w];
}
final[v]=1;
for(w=0;w<NUM;++w)
if(!final[w]&&((min+G.arcs[v][w].adj)<D[w]))
{
D[w]=min+G.arcs[v][w].adj;
for(t=0;t<NUM;t++)
P[w][t]=P[v][t];
P[w][w]=1;
}
}
}

4. 说明函数
void narrate()
{
int i,k=0;
printf("\n\t\t*****************欢迎使用校园导游程序***************\n");
printf("\n\t\t********************南京信息工程大学*******************\n");
printf("\t__________________________________________________________________\n");
printf("\t\t景点名称\t\t|\t景点描述\n");
printf("\t________________________________|_________________________________\n");
for(i=0;i<NUM;i++)
{
printf("\t (%2d)%-10s\t\t\t|\t%-25s\n",i,G.vex[i].sight,G.vex[i].description);
k=k+1;
}
printf("\t________________________________|_________________________________\n");
}
5、查询景点信息
void search()
{
int num;
int i;
char c;
char name[20];

do
{
system("cls");
c=SearchMenu();
switch (c)
{
case '1':
system("cls");
narrate();
printf("\n\n\t\t请输入您要查找的景点编号：");
scanf("%d",&num);
for(i=0;i<NUM;i++)
{
if(num==G.vex[i].number)
{
printf("\n\n\t\t\t您要查找景点信息如下:");
printf("\n\n\t\t\t%-25s\n\n",G.vex[i].description);
printf("\n\t\t\t按任意键返回...");
getchar();
getchar();
break;
}
}
if(i==NUM)
{
printf("\n\n\t\t\t没有找到！");
printf("\n\n\t\t\t按任意键返回...");
getchar();
getchar();
}

break;
case '2':
narrate();
system("cls");
printf("\n\n\t\t请输入您要查找的景点名称：");
scanf("%s",name);
for(i=0;i<NUM;i++)
{
if(!strcmp(name,G.vex[i].sight))
{
printf("\n\n\t\t\t您要查找景点信息如下:");
printf("\n\n\t\t\t%-25s\n\n",G.vex[i].description);
printf("\n\t\t\t按任意键返回...");
getchar();
getchar();
break;
}
}
if(i==NUM)
{
printf("\n\n\t\t\t没有找到！");
printf("\n\n\t\t\t按任意键返回...");
getchar();
getchar();
}
break;
}
}while(c!='t');
}

6. 选择菜单
char SearchMenu()
{
char c;
int flag;
do{
flag=1;
system("cls");
narrate();
printf("\n\t\t\t┏━━━━━━━━━━━━━━━┑\n");
printf("\t\t\t┃ ┃\n");
printf("\t\t\t┃ 1、按照景点编号查询 ┃\n");
printf("\t\t\t┃ 2、按照景点名称查询 ┃\n");
printf("\t\t\t┃ t、返回 ┃\n");
printf("\t\t\t┃ ┃\n");
printf("\t\t\t┗━━━━━━━━━━━━━━━┛\n");
printf("\t\t\t\t请输入您的选择：");
scanf("%c",&c);
if(c=='1'||c=='2'||c=='t')
flag=0;
}while(flag);
return c;
}

5、运行结果及分析
系统主界面

查询路径

查询信息

6、收获及体会
非常高兴能和同学们一起做实验，感谢各位老师以及同学们对我的帮助，特别是老师循循善诱的教导和不拘一格的思路给予我无尽的启迪；这次数据结构设计的每个实验细节和每个数据，都离不开老师您的细心指导。

7、源代码
#include "string.h"
#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
#define Max 30000
#define NUM 10
typedef struct ArcCell
{
int adj;
}ArcCell;
typedef struct VertexType
{
int number;
char *sight;
char *description;
}VertexType;

typedef struct
{
VertexType vex[NUM];
ArcCell arcs[NUM][NUM];
int vexnum,arcnum;
}MGraph;

MGraph G;
int P[NUM][NUM];
long int D[NUM];
int x[9]={0};
void CreateUDN(int v,int a);
void narrate();
void ShortestPath(int num);
void output(int sight1,int sight2);
char Menu();
void search();
char SearchMenu();
void HaMiTonian(int);
void NextValue(int);
void display();
void main()
{

int v0,v1;
char ck;
CreateUDN(NUM,11);
do
{
ck=Menu();
switch(ck)
{
case '1':
system("cls");
// narrate();
printf("\n\n\t\t\t请选择起点景点（0～9）：");
scanf("%d",&v0);
printf("\t\t\t请选择终点景点（0～9）：");
scanf("%d",&v1);
ShortestPath(v0);
output(v0,v1);
printf("\n\n\t\t\t\t请按任意键继续...\n");
getchar();
getchar();
break;
case '2':search();
break;
case '3':
system("cls");
//narrate();
x[0]=1;
HaMiTonian(1);
printf("\n\n\t\t\t\t请按任意键继续...\n");
getchar();
getchar();
break;
};
}while(ck!='e');

}
char Menu()
{
char c;
int flag;
do{
flag=1;
system("cls");
narrate();
printf("\n\t\t\t┏━━━━━━━━━━━━━━━┑\n");
printf("\t\t\t┃ ┃\n");
printf("\t\t\t┃ 1、查询景点路径 ┃\n");
printf("\t\t\t┃ 2、查询景点信息 ┃\n");
printf("\t\t\t┃ 3、推荐参观路线 ┃\n");
printf("\t\t\t┃ t、退出 ┃\n");
printf("\t\t\t┃ ┃\n");
printf("\t\t\t┗━━━━━━━━━━━━━━━┛\n");
printf("\t\t\t\t请输入您的选择：");
scanf("%c",&c);
if(c=='1'||c=='2'||c=='3'||c=='t')
flag=0;
}while(flag);
return c;
}

char SearchMenu()
{
char c;
int flag;
do{
flag=1;
system("cls");
narrate();
printf("\n\t\t\t┏━━━━━━━━━━━━━━━┑\n");
printf("\t\t\t┃ ┃\n");
printf("\t\t\t┃ 1、按照景点编号查询 ┃\n");
printf("\t\t\t┃ 2、按照景点名称查询 ┃\n");
printf("\t\t\t┃ t、返回 ┃\n");
printf("\t\t\t┃ ┃\n");
printf("\t\t\t┗━━━━━━━━━━━━━━━┛\n");
printf("\t\t\t\t请输入您的选择：");
scanf("%c",&c);
if(c=='1'||c=='2'||c=='t')
flag=0;
}while(flag);
return c;
}
void search()
{
int num;
int i;
char c;
char name[20];

do
{
system("cls");
c=SearchMenu();
switch (c)
{
case '1':
system("cls");
narrate();
printf("\n\n\t\t请输入您要查找的景点编号：");
scanf("%d",&num);
for(i=0;i<NUM;i++)
{
if(num==G.vex[i].number)
{
printf("\n\n\t\t\t您要查找景点信息如下:");
printf("\n\n\t\t\t%-25s\n\n",G.vex[i].description);
printf("\n\t\t\t按任意键返回...");
getchar();
getchar();
break;
}
}
if(i==NUM)
{
printf("\n\n\t\t\t没有找到！");
printf("\n\n\t\t\t按任意键返回...");
getchar();
getchar();
}

break;
case '2':
narrate();
system("cls");
printf("\n\n\t\t请输入您要查找的景点名称：");
scanf("%s",name);
for(i=0;i<NUM;i++)
{
if(!strcmp(name,G.vex[i].sight))
{
printf("\n\n\t\t\t您要查找景点信息如下:");
printf("\n\n\t\t\t%-25s\n\n",G.vex[i].description);
printf("\n\t\t\t按任意键返回...");
getchar();
getchar();
break;
}
}
if(i==NUM)
{
printf("\n\n\t\t\t没有找到！");
printf("\n\n\t\t\t按任意键返回...");
getchar();
getchar();
}
break;
}
}while(c!='t');
}
void CreateUDN(int v,int a)
{
int i,j;
G.vexnum=v;
G.arcnum=a;
for(i=0;i<G.vexnum;++i) G.vex[i].number=i;

G.vex[0].sight="东大门";
G.vex[0].description="学校正门。";
G.vex[1].sight="气象楼";
G.vex[1].description="校气象研究楼。";
G.vex[2].sight="体育馆";
G.vex[2].description="运动，放松心情";
G.vex[3].sight="大学生活动中心";
G.vex[3].description="竞赛、晚会举办地";
G.vex[4].sight="图书馆";
G.vex[4].description="阅览，借阅图书";
G.vex[5].sight="滨江楼";
G.vex[5].description="学习，自习室";
G.vex[6].sight="综合楼";
G.vex[6].description="学习，办公室";
G.vex[7].sight="老食堂";
G.vex[7].description="餐饮休闲";
G.vex[8].sight="新食堂";
G.vex[8].description="餐饮休闲";
G.vex[9].sight="文园";
G.vex[9].description="宿舍，休息";

for(i=0;i<G.vexnum;++i)
for(j=0;j<G.vexnum;++j)
G.arcs[i][j].adj=Max;
G.arcs[0][1].adj=G.arcs[1][0].adj=2;
G.arcs[0][2].adj=G.arcs[2][0].adj=1;
G.arcs[0][3].adj=G.arcs[3][0].adj=7;
G.arcs[1][4].adj=G.arcs[4][1].adj=8;
G.arcs[2][4].adj=G.arcs[4][2].adj=9;
G.arcs[3][5].adj=G.arcs[5][3].adj=5;
G.arcs[5][7].adj=G.arcs[7][5].adj=2;
G.arcs[4][6].adj=G.arcs[6][4].adj=3;
G.arcs[4][7].adj=G.arcs[7][4].adj=2;
G.arcs[6][8].adj=G.arcs[8][6].adj=2;
G.arcs[7][8].adj=G.arcs[8][7].adj=1;
G.arcs[8][9].adj=G.arcs[9][8].adj=1;
}
void narrate()
{
int i,k=0;
printf("\n\t\t*****************欢迎使用校园导游程序***************\n");
printf("\n\t\t********************南京信息工程大学*******************\n");
printf("\t__________________________________________________________________\n");
printf("\t\t景点名称\t\t|\t景点描述\n");
printf("\t________________________________|_________________________________\n");
for(i=0;i<NUM;i++)
{
printf("\t (%2d)%-10s\t\t\t|\t%-25s\n",i,G.vex[i].sight,G.vex[i].description);
k=k+1;
}
printf("\t________________________________|_________________________________\n");
}
void ShortestPath(int num)
{
int v,w,i,t;
int final[NUM];
int min;
for(v=0;v<NUM;v++)
{
final[v]=0;
D[v]=G.arcs[num][v].adj;
for(w=0;w<NUM;w++)
P[v][w]=0;
if(D[v]<30000)
{
P[v][num]=1;
P[v][v]=1;
}
}

D[num]=0;
final[num]=1;

for(i=0;i<NUM;++i)
{
min=Max;
for(w=0;w<NUM;++w)
if(!final[w])
if(D[w]<min)
{
v=w;
min=D[w];
}
final[v]=1;
for(w=0;w<NUM;++w)
if(!final[w]&&((min+G.arcs[v][w].adj)<D[w]))
{
D[w]=min+G.arcs[v][w].adj;
for(t=0;t<NUM;t++)
P[w][t]=P[v][t];
P[w][w]=1;
}
}
}
void output(int sight1,int sight2)
{
int a,b,c,d,q=0;
a=sight2;
if(a!=sight1) /* 如果景点二不和景点一输入重合，则进行 */
{
printf("\n\t从%s到%s的最短路径是",G.vex[sight1].sight,G.vex[sight2].sight);/* 输出提示信息 */ 
printf("\t(最短距离为 %dm.)\n\n\t",D[a]);
printf("\t%s",G.vex[sight1].sight);
d=sight1;  /* 将景点一的编号赋值给d */ 
for(c=0;c<NUM;++c)
{
gate:;
P[a][sight1]=0;
for(b=0;b<NUM;b++)
{
if(G.arcs[d][b].adj<30000&&P[a][b]) /* 如果景点一和它的一个临界点之间存在路径且最短路径 */ 
{
printf("-->%s",G.vex[b].sight); /* 输出此节点的名称 */ 
q=q+1; /* 计数变量加一，满8控制输出时的换行 */
P[a][b]=0;
d=b;  /* 将b作为出发点进行下一次循环输出，如此反复 */
if(q%9==0) printf("\n");
goto gate;
}
}
}
}

}
void HaMiTonian(int m)
{
if(m>9) return;
L: NextValue(m);
if(x[m]==0)
return;
if(m==8&&G.arcs[0][x[9]-1].adj!=30000)
display();
else
HaMiTonian(m+1);
goto L;
}
void NextValue(int k)
{
int j;
l:x[k]=(x[k]+1)%10;
if(x[k]==0)
return;
if(G.arcs[x[k-1]-1][x[k]-1].adj!=30000)
{
for(j=0;j<k;j++)
if(x[j]==x[k])
goto l;
return;
}
else
goto l;
}
void display()
{
int i=0;
printf("\n\n\t");
for(i=0;i<9;i++)
printf("%s->",G.vex[x[i]-1].sight);
printf("出口");
printf("\n");
}