校园导游系统数据结构图.西安郵電學院
数据结构实验报告
题 目: 校 园 导 游 系 统
院系名称: 计 算 机 学 院
专业名称: 计算机科学与技术
班 级: 1006
学生姓名: ****
学号(8位):*****
指导教师:
******
设计起止时间:2011年12月12日~2011年12月16日
1. 题目要求
1、设计学校的校园平面图,
地点(地点名称、地点介绍)不少于10个。
2、提供图中任意地点相关信息的查询。
3、提供图中任意地点的问路查询:
1)任意两个地点之间的一条...
西安郵電學院
数据结构实验
目: 校 园 导 游 系 统
院系名称: 计 算 机 学 院
专业名称: 计算机科学与技术
班 级: 1006
学生姓名: ****
学号(8位):*****
指导教师:
******
设计起止时间:2011年12月12日~2011年12月16日
1. 题目要求
1、设计学校的校园平面图,
地点(地点名称、地点介绍)不少于10个。
2、提供图中任意地点相关信息的查询。
3、提供图中任意地点的问路查询:
1)任意两个地点之间的一条最短(中转最少)的简单路径;
2)任意两个景点的最佳访问路线(带权)查询;
3)任意两个地点之间的所有路径。
4、地点和道路的扩充以及撤销;
地点基本信息的文件存储。(附加:加分题)
二.概要设计
1.功能模块的调用关系图
2.各个模块详细的功能描述。
1.首先,main()函数调用loge()函数,输出欢迎界面,然后调用showmenu()函数来选择用户所要进行的操作。其中showmenu()函数就是一个菜单供使用者来选择他所要进行的相关操作,比如信息的查询,最短路径查询之类。
2.browser()函数,用于输出校园平面图,给用户提供校园的景点分布状况,方便用户选择景点参观。
3.Search()函数,用于查询用户所选的景点信息,用户需要输入要查询的景点编号,函数会对编号进行判断,如果是合法输入,则在屏幕上输出该景点的相关信息,包括景点名字,景点的相关介绍,否则返回重新输入。
4.SearchAllpath()函数,用于查询用户所选的任意两个景点间的所有路径,用户需要输入要查询的起始景点编号,函数会对编号进行判断,如果是合法输入,用户需要输入要查询的终点景点编号,函数会对编号进行判断,如果是合法输入,则在屏幕上输出输查询的两个景点间的所有路径,否则返回重新输入。函数使用深度遍历DeepFirstSeach()查找路径。
5.Wellway()函数,用于查询用户所选的任意两个景点间的最短路径,用户需要输入要查询的起始景点编号,函数会对编号进行判断,如果是合法输入,用户需要输入要查询的终点景点编号,函数会对编号进行判断,如果是合法输入,则在屏幕上输出输查询的两个景点间的最短路径,否则返回重新输入。函数的生成主体是迪杰斯特拉算法来计算出起点到终点之间的最短路径。
6.minway()函数,用于查询用户所选的任意两个景点间的最佳路径(即中转最少),用户需要输入要查询的起始景点编号,函数会对编号进行判断,如果是合法输入,用户需要输入要查询的终点景点编号,函数会对编号进行判断,如果是合法输入,则在屏幕上输出输查询的两个景点间的最短路径,否则返回重新输入。
7. CreatUDN()函数,创建的图,它是MGraph型,G->vexnum
示顶点的个数;G->arcnum表示边数。CreatUDN()函数的功能就是实现图的创建,将已知的景点的一些信息,转换成图的信息,并进行存储。
三.详细设计(主要函数的程序
图)
1.任意两个地点之间的一条最短(中转最少)的简单路径
利用遍历的思想,遍历图找出一条最佳最佳的的路径,让它遍历所有景点。往下遍历,访问标志位,若访问过在下次就不用访问。若找完一个分支在下次重新遍历。
zz[0]->zhi=m;
zz[0]->front=NULL;
flag[m]=1;
for(top=0;top<20;top++)
{
for(i=0;i<20;i++)
{
if(G->arcs[zz[top]->zhi][i].adj!=INFINITY&&i==n)
{
printf("%s\n",G->vexs[n].name);
printf("%s\n",G->vexs[zz[top]->zhi].name);
zz[top]=zz[top]->front;
while(zz[top]!=NULL)
{
printf("%s\n",G->vexs[zz[top]->zhi].name);
zz[top]=zz[top]->front;
}
getch();
return;
}
else if(G->arcs[zz[top]->zhi][i].adj!=INFINITY&&flag[i]==0)
{
zz[++j]->zhi=i;
zz[j]->front=zz[top];
flag[i]=1;
}
}
}
2.任意两个景点的最佳访问路线(带权)查询
利用迪杰特斯拉算法,求v0到其余顶点的最短路径D[],p [][]是用来存放各路径的权值,借助辅助数组final[]标志,是否当前顶点属于final(1,属于)。 for(v=0;v
vexnum;v++)
{
final[v]=0;
D[v]=G->arcs[v0][v].adj;
for(w=0;wvexnum;w++)
p[v][w]=0;
if(D[v]vexnum;i++)
{
min=INFINITY;
for(w=0;wvexnum;w++)
if(!final[w])
if(D[w]vexnum;w++)
if(!final[w]&&(min+G->arcs[v][w].adjarcs[v][w].adj;
for(x=0;xvexnum;x++)
p[w][x]=p[v][x];
p[w][w]=1;
}
}
v=v1;
w1=v0;
printf("%s",G->vexs[v0].name);
do
{
flag=0;min=INFINITY;
for(w=0;wvexnum;w++)
{
if(p[v][w]&&w!=v0)
{
flag=1;
if(D[w]",G->vexs[v[s]].name);
printf("%s\n",G->vexs[v[s]].name);
}
for(s = 1;svexnum;s++)
{
if(s!=i)/*保证找到的是简单路径*/
{
if(G->arcs[v[k]][s].adj!=INFINITY&&visited[s]==0)
/*当vk与vs之间有边存在且vs未被访问过*/
{
visited[s]=1; /*置访问标志位为1,即已访问的*/
v[k+1]=s; /*将顶点s加入到v数组中*/
DeepFirstSeach(G,i,j,k+1); /*递归调用之*/
visited[s]=0; /*重置访问标志位为0,即未访问的,以便该顶点能被重新使用*/
}
}
}
}若找完一个分支在下次重新遍历。
递归调用
否
4.测试数据及运行结果
1.正常测试数据和运行结果
2.异常测试数据及运行结果
五.调试情况,设计技巧及体会
1.改进
本次实习设计总体上来说是成功的,我在规定的时间内完成了老师交代的任务,并让程序能够运行起来,可以说大体上没有问题,当然在细节上还有需要改进的地方;
合理之处:
对于老师所提出的问题要求很好并及时的解决了;
程序运行整体上没有大的错误;
对于各大模块划分清晰,知道先做什么后做什么;
程序运行后界面漂亮,用户使用方便;
合理恰当的把书上所学的关于图的知识应用到程序设计之中,使程序明了可读性较高。
不合理之处:
程序之中存在一些小毛病,不能100%的运行无误;
关于文件存储这一模块掌握的不是很好,所创建的图不能很好的保存到文件之中;
程序设计中最短路径(中转最少)显示的时候是倒着显示
改进方案:
对于程序存在的小问题一个个的仔细排除,精尽量做到准确无误;对于文件和最短路径的设计应多参考相关书籍,找到合理正确的解决方法,将图存储到指定的文件中去,并且使最短路径在输出的时候能够以正确的顺序输出。
2.体会
这次课程设计给我的感触很多,课程设计没开始之前我总是在想今年的课程设计会不会象去年那样辛苦,但是这一周下来我当然也感到累,也有心情烦躁的时候,体会到调试成功时的那种喜悦。
课程设计之前老师让我们自己先想好设计思路,都要做哪些模块。那天下午编了一下午,没什么成就弄得我很心烦,再想到快要考试,那种急于求成的心更迫切,自己很难平静。第二天老师检查时我什麽都没有,看到同学的程序我开始着急了,但那会我只有一个念头我得从新开始,由于对图不是很了解,我就从读写模块开始,就使用简单的C语知识,那天早上将那两个模块给拿下了。下机后我在寝室开始编程,开始进入真正的图部分,边思考怎样可以将它们联系起来,边进行调试。对编程兴趣很浓,直到晚上十点我已经将老师的要求完成差不多。
这些日子是很辛苦,但我学到了很多东西,理解了图的运用,还和同学一起分享调试成功的那种喜悦,我完成的早,同学有问题会让我帮助,在帮他们的过程中我也学会了很多种不同的思想,让我对图有了更深刻的理解。
当然,我要感谢学校领导精心给我们安排的这次实习操作,更感谢我们的程序设计老师,是她给了我们一个相对轻松有趣的环境,让我们感到在设计中没有压力,在她的帮助下,我终于完成了本次课程设计的任务。
。
代码
#include
#include
#include
#include
#include
#define INFINITY 10000 /*无穷大*/
#define MAX_VERTEX_NUM 40
#define MAX 40
typedef struct ArCell
{
int adj; //路径长度
}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct //图中顶点表示主要景点,存放景点的编号、名称、简介等信息,s
{
char name[30];
int num;
int x;
int y;
char introduction[500];//简介
}infotype;
struct zui //最短路径记录结构体
{
int zhi;
struct zui *front;
};
typedef struct
{
infotype vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph;
MGraph b;
void showmenu();
void loge(); //启动动画
void Wellway(MGraph * ); // 计算任意两个景点之间的最短路径
MGraph InitGraph(void); //初始化
void browser(); //浏览校园全景
void Search(MGraph *G); //查看景点信息
MGraph *CreatUDN(MGraph *G); //创建图
void SearchAllpath(MGraph *G); //查找两点间所有路径
void minway(MGraph *G);
MGraph *CreatUDN(MGraph *G);
int openfile(MGraph *G);
int writefile(MGraph *G);
int writefile(MGraph *G)
{
FILE *fp;
int i;
fp = fopen("xiaoyuanxinxi.txt", "w");
if(fp == NULL)
{
printf("打开失败!");
return FALSE;
}
for(i = 0; i < 20; i++)
fwrite(&G , sizeof(MGraph), 1 ,fp);
return TRUE;
fclose(fp);
}
int openfile(MGraph *G)
{
FILE *fp;
int i = 0;
int t = 0;
fp = fopen("xiaoyuanxinxi.txt", "r");
if(fp == NULL)
{
printf("文件为空,无景点信息,请按任意键返回添加!");
return FALSE;
}
while(!feof(fp))
{
fread(&G, sizeof(MGraph), i, fp);
i++;
}
for(t=0;tvexs[t].num,G->vexs[t].name,G->vexs[t].introduction);
printf("\n");
}
fclose(fp);
return i;
}
void main(void)
{
int k;
system("mode con: cols=140 lines=130");
loge();
b=InitGraph();
system("cls");
printf(" 欢迎进入西安邮电大学校园导游咨询系统\n");
Sleep(1000);
do
{
while(1)
{
showmenu();
printf("请选择:");
scanf("%d",&k);
if(k<0||k>6)
{
printf("输入有误请重新输入\n");
scanf("%d",&k);
}
else break;
}
switch(k)
{
case 1:browser();system("cls");break;
case 2:Search(&b);system("cls");break;
case 3:SearchAllpath(&b);system("cls");break;
case 4:Wellway(&b);system("cls");break;
case 5:minway(&b);system("cls");break;
case 6:CreatUDN(&b);system("cls");break;
case 0:exit(0);
}
}while(1);
}
void showmenu()
{
printf(" ************************************\n");
printf(" $ 主要景点列表 $ \n");
printf(" $ 建议观看 $ \n");
printf(" ************************************\n");
printf(" <12> 田操场<09> 西邮小湖\n");
printf(" <2> 教学楼A<14> 体育馆\n");
printf(" <3> 教学楼B<10> 图书馆 \n");
printf(" <5> 1号实验楼<6> 2号实验楼\n");
printf(" <7> 3号实验楼<11> 校医院 \n");
printf(" <8> 大学生活动中心<4> 喷泉 \n");
printf(" <13> 美食广场<15> 旭日苑\n");
printf(" 1.查看学校景点分布图\n");
printf(" 2.查询景点简介查询\n");
printf(" 3.查询某两个景点间所有的路径\n");
printf(" 4.任意两景点之间的最佳路径\n");
printf(" 5.任意两景点之间的最短路径\n");
printf(" 6.建图并保存到文件\n");
printf(" 0.退出\n");
}
void loge()
{
printf("\t\t\t\t\t\t\t");
printf("欢"); Sleep(100);
printf("迎"); Sleep(100);
printf("进"); Sleep(100);
printf("入"); Sleep(100);
printf("西"); Sleep(100);
printf("安"); Sleep(100);
printf("邮"); Sleep(100);
printf("电"); Sleep(100);
printf("大"); Sleep(100);
printf("学"); Sleep(100);
printf("校"); Sleep(100);
printf("园"); Sleep(100);
printf("导"); Sleep(100);
printf("游"); Sleep(100);
printf("系"); Sleep(100);
printf("统"); Sleep(100);
printf("\n");
}
MGraph InitGraph()
{
MGraph G;
int i,j;
G.vexnum=20;
G.arcnum=18;
for(i=0;i20||n<0||n>20||m==n)
{
printf("输入错误,按任意键继续~!");
getch();
return ;
}
zz[0]->zhi=m;
zz[0]->front=NULL;
flag[m]=1;
for(top=0;top<20;top++)
{
for(i=0;i<20;i++)
{
if(G->arcs[zz[top]->zhi][i].adj!=INFINITY&&i==n)
{
printf("%s\n",G->vexs[n].name);
printf("%s\n",G->vexs[zz[top]->zhi].name);
zz[top]=zz[top]->front;
while(zz[top]!=NULL)
{
printf("%s\n",G->vexs[zz[top]->zhi].name);
zz[top]=zz[top]->front;
}
getch();
return;
}
else if(G->arcs[zz[top]->zhi][i].adj!=INFINITY&&flag[i]==0)
{
zz[++j]->zhi=i;
zz[j]->front=zz[top];
flag[i]=1;
}
}
}
}
void Wellway(MGraph * G) // 计算任意两个景点之间的最短路径
{
int v,w,w1,i,j,v1,min,t=0,x,flag=1,v0;
int final[20], D[20], p[20][20];
while(flag)
{
printf("请输入一个起始景点编号:");
scanf("%d",&v0);
if(v0<0||v0>G->vexnum)
{
printf("景点编号不存在!请重新输入景点编号:");
scanf("%d",&v0);
}
if(v0>=0&&v0vexnum)
flag=0;
}
flag=1;
while(flag)
{
printf("请输入一个目的地景点编号:");
scanf("%d",&v1);
if(v1<0||v1>G->vexnum)
{
printf("景点编号不存在!请重新输入景点编号:");
scanf("%d",&v1);
}
if(v1>=0&&v1vexnum)
flag=0;
}
for(v=0;vvexnum;v++)
{
final[v]=0;
D[v]=G->arcs[v0][v].adj;
for(w=0;wvexnum;w++)
p[v][w]=0;
if(D[v]vexnum;i++)
{
min=INFINITY;
for(w=0;wvexnum;w++)
if(!final[w])
if(D[w]vexnum;w++)
if(!final[w]&&(min+G->arcs[v][w].adjarcs[v][w].adj;
for(x=0;xvexnum;x++)
p[w][x]=p[v][x];
p[w][w]=1;
}
}
v=v1;
w1=v0;
printf("%s",G->vexs[v0].name);
do
{
flag=0;min=INFINITY;
for(w=0;wvexnum;w++)
{
if(p[v][w]&&w!=v0)
{
flag=1;
if(D[w]vexs[w1].xvexs[j].x)
printf("向东走%dm",G->arcs[w1][j].adj);
if(G->vexs[w1].x>G->vexs[j].x)
printf("向西走%dm",G->arcs[w1][j].adj);
if(G->vexs[w1].yvexs[j].y)
printf("向北走%dm",G->arcs[w1][j].adj);
if(G->vexs[w1].y>G->vexs[j].y)
printf("向南走%dm",G->arcs[w1][j].adj);
printf("-->%s",G->vexs[j].name);
w1=j;
p[v][j]=0;
}
else break;
}while(1);
printf("\n 总路线长%dm\n\n",D[v]);
printf("完毕,按任意键继续!\n");
getch();
}
int count=0;/*全局变量,用来记录每对顶点之间的所有路径的条数*/
int visited[MAX_VERTEX_NUM];/*全局数组,用来记录各顶点被访问的情况*/
int v[MAX_VERTEX_NUM];/*全局数组,用来存放路径上的各顶点*/
int SearchInformation(MGraph *G,int a)// 查询各景点的相关信息
{
int i;
for(i=0;i<=G->vexnum;i++)
{
if(a==i)//找到了中断
break;
}
if(i==(G->vexnum +1))//没找到继续找
{
return -1;
}
else
return G->vexs[i].num;
}
void DeepFirstSeach(MGraph *G,int i,int j,int k)
/*确定路径上第k+1个顶点的序号*/
{
int s;
if(v[k]==j)/*找到一条路径*/
{
count++;/*路径的条数值加1*/
printf("第%d条:",count);
for(s=1;s",G->vexs[v[s]].name);
printf("%s\n",G->vexs[v[s]].name);
}
for(s = 1;svexnum;s++)
{
if(s!=i)/*保证找到的是简单路径*/
{
if(G->arcs[v[k]][s].adj!=INFINITY&&visited[s]==0)
/*当vk与vs之间有边存在且vs未被访问过*/
{
visited[s]=1; /*置访问标志位为1,即已访问的*/
v[k+1]=s; /*将顶点s加入到v数组中*/
DeepFirstSeach(G,i,j,k+1); /*递归调用之*/
visited[s]=0; /*重置访问标志位为0,即未访问的,以便该顶点能被重新使用*/
}
}
}
}
void Initppath(MGraph *G,int i,int j)
{
int k;
v[1]=i;
for(k=0;kvexnum;k++)
visited[k]=0;/*初始化各顶点的访问标志位,即都为未访问过的*/
DeepFirstSeach(G,i,j,1);/*通过调用DeepFirstSeach函数,找到从vi到vj的所有路径并输出*/
}
void SearchAllpath(MGraph *G)/*查询两个景点间的所有路径*/
{ int i,j;
int b,c;
printf("请输入起点景点编号:");
scanf("%d",&b);
i=SearchInformation(G,b);
if(i==-1)
{
printf("你输入的起点景点名称不存在!\n");
return;
}
printf("请输入终点景点名称:");
scanf("%d",&c);
j=SearchInformation(G,c);
if(j==-1)
{
printf("你输入的终点景点名称不存在!\n");
return;
}
printf("从%s到%s的所有游览路径有:\n",G->vexs[i].name,G->vexs[j].name);/*输出出发景点和目地景点的名称*/
Initppath(G,i,j);/*调用Initppath函数,用来输出两个景点间的所有路径*/
}
void Search(MGraph *G)
{
int k,flag=1;
while(flag)
{
printf("请输入要查询的景点编号:");
scanf("%d",&k);
if(k<0||k>=G->vexnum)
{
printf("景点编号不存在!请重新输入景点编号:");
scanf("%d",&k);
}
if(k>=0&&kvexnum)
flag=0;
}
printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");
printf("┃编号┃景点名称 ┃简介 ┃\n");
printf("┃%-4d┃%-16s┃%-96s┃\n",G->vexs[k].num,G->vexs[k].name,G->vexs[k].introduction);
printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");
printf("完毕,按任意键继续!\n");
getch();
}
MGraph *CreatUDN(MGraph *G)//初始化图形,接受用户输入
{
int i,j,k,w,z;//i,j,k,w全为循环变量
printf("请输入图的顶点数,弧数:");
flushall();
scanf("%d,%d",&G->vexnum,&G->arcnum); //输入顶点和边数
printf("请输入景点的编号:、名称、简介:\n"); //输入景点编号,名称,简介
for(i=1;i<=G->vexnum;i++)
{
printf("景点编号:");
flushall();
scanf("%d",&G->vexs[i].num);
printf("景点名称:");
scanf("%s",G->vexs[i].name);
printf("景点简介:");
scanf("%s",G->vexs[i].introduction);
}
for(i=1;i<=G->vexnum;i++)
for(j=1;j<=G->vexnum;j++)
G->arcs[i][j].adj=INFINITY;
printf("请输入路径长度:\n"); //输入权值(路径长度)
for(k=1;k<=G->arcnum;k++)
{
printf("第%d条边:\n",k);
printf("相邻景点(i,j):"); //输入相邻景点
scanf("%d,%d",&i,&j);
printf("路径长度:"); //输入相邻景点的权值
scanf("%d",&w);
G->arcs[i][j].adj=w; //把权值赋值给无向图G所指的邻接矩阵所指的权值
G->arcs[j][i]=G->arcs[i][j];// 下边是可直接到达的景点间的距离,由于两个景点间距离是互相的,
// 所以要对图中对称的边同时赋值。
}
printf("\t创建完毕!\n");
printf("请选择操作0结束操作,1写入文件2读取文件\n");
do
{
scanf("%d",&z);
switch(z)
{
case 1: writefile(G);
case 2: openfile(G);
}
}while(z);
return G;
}
本文档为【校园导游系统数据结构图.】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。