数据结构课程设计导航图.docx
- 文档编号:13285359
- 上传时间:2023-06-12
- 格式:DOCX
- 页数:50
- 大小:197.09KB
数据结构课程设计导航图.docx
《数据结构课程设计导航图.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计导航图.docx(50页珍藏版)》请在冰点文库上搜索。
数据结构课程设计导航图
西安邮电大学
(计算机学院)
数据结构设计报告
题目:
导航图
专业名称:
软件工程
班级:
班
学生姓名:
学号(8位):
指导教师:
设计起止时间:
2014年12月15日—2014年12月26日
一.设计目的
1.数据结构课程设计是让学生综合运用数据结构课程中学到的几种典型数据结构,以及程序设计语言(C语言),自行实现一个较为完整的应用系统的设计与开发
2.通过课程设计,使学生通过系统分析、系统设计、编程调试,写实验报告等环节,进一步掌握应用系统设计的方法和步骤,灵活运用并深刻理解典型数据结构在软件开发中的应用。
3.学会将知识应用于实际的方法,提高分析和解决问题的能力,增加综合能力
二.设计内容
我设计的是旅游查询系统,是用于校园的,任何景区都可以用。
对于游客来说,游客可以查询要游览的景点,可以显示出该景点的相关信息,景点等级。
也可以输入起点和终点,找到一条最短路径,或者这两点之间所有路径。
或者输入起点,自动生成一个全程最短的游览路线。
当然游客也可以查看校园的平面图。
对于管理员来说,管理员可以增,删,改景点和道路信息。
三.概要设计
1.功能模块图;
旅游查询系统
2.各个模块详细的功能描述。
1.浏览全景
显示校园的平面图,让游客大概的了解校园的形貌,以及各个景点的位置。
2.显示所有景点和路线
将所有景点和路线以列表的形式显示出来,包括景点名称,景点等级,景点描述;路线也有道路名称,道路距离,道路的起点终点。
3.最短行程查询
输入起点,显示该起点到其它所有景点的最短路径。
4.最佳游览全景路线
输入起点,生成一个最小联通路径,这样游客便能以最少的行程来游览所有景点。
5.两点之间所有路线
输入起点和终点,显示出这两点之间的所有路线供游客选择。
四.详细设计
1.功能函数的调用关系图
2.各功能函数的数据流程图
3.重点设计及编码
用DFS得出两点之间所有路线,首先输入起点和终点名称,找到其名称的下标,以起点下标开始进行深度优先遍历,每遍历到下一个邻接点让其进栈,并判断其下标是否和终点下标相同,如果相同则输出栈内所有元素,并将栈顶出栈,若不相同,继续遍历。
直至找完所有的路线。
在这里栈的作用是存储将要找到的路线。
五.测试数据及运行结果
1.正常测试数据和运行结果
六.调试情况设计技巧及体会
在求两点之间所有路径和最小联通路径的算法中,需要将邻接表转化为矩阵去做。
对于prim算法所得出的结果并不是游客所要按照的走法,只是单纯的最小生成树,若要得到一个节省的且能游览所有的景点的走法,那么需要遍历所得到的最小生成树,但并没有一个普遍的遍历方法去得到,完全需要游客自己主观的去判断怎样走才最短。
在系统管理这一功能中,只有管理员才能使用,所以必须设置密码,这样就避免了游客的操作。
对于邻接表要存储无向图,我们需要该顶点的邻接点个数,输完该顶点,再输入这些邻接点。
那么输入以某个邻接点为顶点时,之前已经输过的顶点就是它的邻接点,我们又要去输一遍它,这样太麻烦了。
那么有什么办法呢?
经过我的思考和研究,我们再输入完一个顶点(和它携带的邻接点)后,加一个算法,让这些邻接点和这个顶点关系一并接到这些以邻接点为顶点的邻接表上。
具体处理如下:
for(p=a->vertex[i].head;p!
=NULL;p=p->next)/*无向图在邻接表中相互指向*/
{if(p->adjvex>i)
{if(a->vertex[p->adjvex].head==NULL)
q=a->vertex[p->adjvex].head=(anode*)malloc(sizeof(anode));
else
{for(q=a->vertex[p->adjvex].head;q->next!
=NULL;)
q=q->next;
q->next=(anode*)malloc(sizeof(anode));
q=q->next;
}
q->next=NULL;q->adjvex=i;strcpy(q->rname,p->rname);
q->weight=p->weight;
}
}
七、源代码及相关文件
主程序代码:
#include
#include
#include
#defineinfinity32767
#definemaxsize50
typedefstruct
{
intstack[maxsize];
inttop;
}SeqStack;
typedefstructarcnode//邻接表结构体
{
charrname[20];/*路名*/
intadjvex;/*相邻景点序号*/
intweight;/*路长*/
structarcnode*next;
}anode;
typedefstructvertexnode
{
intvisit;/*访问标志*/
charvexdata[20];/*景点名称*/
charlv[10];/*景点等级*/
chardiscribe[100];/*景点描述*/
intin;/*入度*/
intout;/*出度*/
anode*head;
}vnode;
typedefstruct
{
vnodevertex[maxsize];
intvexnum;/*景点数*/
intarcnum;/*路数*/
}adjlist;
typedefstruct
{
intarcs[maxsize][maxsize];
charspotname[maxsize][100];//景点名称
intvexnum;//景点数
}adjmartrix;
voidestablish(adjlist*a)//把创建的图写入文件,放到creatgrahp(adjlist*a)中
{
inti,j;
anode*p;
FILE*sfp,*rfp;
sfp=fopen("school.txt","wt");//创建新景点文件
rfp=fopen("road.txt","wt");
fprintf(sfp,"%d%d\n",a->vexnum,a->arcnum);/*景点数和路数写到school中*/
for(i=1;i<=a->vexnum;i++)
fprintf(sfp,"%s%s%s%d%d\n",a->vertex[i].vexdata,a->vertex[i].lv,a->vertex[i].discribe,a->vertex[i].out,a->vertex[i].in);
for(i=1;i<=a->vexnum;i++)/*道路信息写到road中*/
{
p=a->vertex[i].head;
if(a->vertex[i].out!
=0)
{
fprintf(rfp,"%s%d%d\n",p->rname,p->adjvex,p->weight);
p=p->next;
}
for(j=1;j
{
fprintf(rfp,"%s%d%d\n",p->rname,p->adjvex,p->weight);
p=p->next;
}
}
fclose(sfp);//关闭文件
fclose(rfp);//关闭文件
}
voidchurudu(adjlist*a)/*计算出度和入度*/
{
inti,n;
anode*p;
for(i=1;i<=a->vexnum;i++)/*计算出度*///问题
{
p=a->vertex[i].head;
if(p!
=NULL)
{
n=1;
p=p->next;
}
else
n=0;
while(p!
=NULL)
{
n++;
p=p->next;
}
a->vertex[i].out=n;
}
for(i=1;i<=a->vexnum;i++)
a->vertex[i].in=0;/*在调用churudu()之前,原有景点入度变为0*/
for(i=1;i<=a->vexnum;i++)/*计算入度*/
{
p=a->vertex[i].head;
while(p!
=NULL)
{
a->vertex[p->adjvex].in=a->vertex[p->adjvex].in+1;/*入度自增1*/
p=p->next;
}
}
}
voidcreatgrahp(adjlist*a)/*创建图*/
{
inti,n,j;
intflag=1;
anode*p,*q;
while(flag)
{
printf("请输入景点数,路线数:
\n");
scanf("%d%d",&a->vexnum,&a->arcnum);
if(a->arcnum>(a->vexnum-1)*a->vexnum/2||a->arcnum==0)/*判断输入的景点数和路线数是否能构成一个图*/
printf("输入有误,请重新输入:
\n");
else
flag=0;
}
flag=1;
getchar();
for(i=1;i<=a->vexnum;i++)/*输入景点*/
{
printf("请输入第%d个景点名称:
\n",i);
scanf("%s",a->vertex[i].vexdata);
printf("请输入该景点等级:
\n");
scanf("%s",a->vertex[i].lv);
printf("请描述景点:
\n");
scanf("%s",a->vertex[i].discribe);
a->vertex[i].head=NULL;/*头结点置空*/
a->vertex[i].out=0;/*出度初始为0*/
}
for(i=1;i<=a->vexnum;i++)/*输入相邻景点*/
{
getchar();
printf("请输入剩余的%s的相邻景点个数:
\n",a->vertex[i].vexdata);
scanf("%d",&n);
if(n>0)
{
p=a->vertex[i].head;
if(p==NULL)
{
p=a->vertex[i].head=(anode*)malloc(sizeof(anode));/*第一次要把邻接点和头结点链接*/
while(flag)
{
printf("请输入第1个相邻景点序号和距离:
\n");
scanf("%d%d",&p->adjvex,&p->weight);
if(p->adjvex==i)
printf("输入有误,请重新输入\n");
else
flag=0;
}
flag=1;
printf("请输入路名:
\n");
scanf("%s",p->rname);
p->next=NULL;
}
else
{
for(;p->next!
=NULL;p=p->next)//如果头结点不为空,则p向后移动,防止在邻接表中相互指向时头结点被篡改
{;}
n=n+1;//因为下面的for只适用于if完成之后的操作,为了适应else完成之后的操作,需要n自增1
flag=0;
}
}
for(j=1;j { q=(anode*)malloc(sizeof(anode)); q->next=NULL; p->next=q; p=q; if(flag==1) printf("请输入第%d个相邻景点序号和距离: \n",j+1); else printf("请输入第%d个相邻景点序号和距离: \n",j); scanf("%d%d",&p->adjvex,&p->weight); printf("请输入路名: \n"); scanf("%s",p->rname); } for(p=a->vertex[i].head;p! =NULL;p=p->next)/*无向图在邻接表中相互指向*/ { if(p->adjvex>i) { if(a->vertex[p->adjvex].head==NULL) q=a->vertex[p->adjvex].head=(anode*)malloc(sizeof(anode)); else { for(q=a->vertex[p->adjvex].head;q->next! =NULL;) q=q->next; q->next=(anode*)malloc(sizeof(anode)); q=q->next; } q->next=NULL; q->adjvex=i; strcpy(q->rname,p->rname); q->weight=p->weight; } } } churudu(a); establish(a); printf("恭喜您创建完成! \n"); } voidreadfile(adjlist*a,FILE*sfp,FILE*rfp)/*读文件*/ { inti,j; anode*p,*q; fscanf(sfp,"%d%d\n",&a->vexnum,&a->arcnum);/*先读出景点数*/ for(i=1;i<=a->vexnum;i++)/*读入景点*/ { fscanf(sfp,"%s%s%s%d%d\n",a->vertex[i].vexdata,a->vertex[i].lv,a->vertex[i].discribe,&a->vertex[i].in,&a->vertex[i].out); a->vertex[i].head=NULL;/*头结点置空*/ } for(i=1;i<=a->vexnum;i++)/*读入相邻景点*/ { if(a->vertex[i].out! =0) { a->vertex[i].head=p=(anode*)malloc(sizeof(anode));/*第一次先读出头结点信息*/ fscanf(rfp,"%s%d%d",p->rname,&p->adjvex,&p->weight); p->next=NULL; } for(j=1;j { q=(anode*)malloc(sizeof(anode)); q->next=NULL; p->next=q; p=q; fscanf(rfp,"%s%d%d",p->rname,&p->adjvex,&p->weight); } } } voidshow(adjlist*a)/*显示所有景点和道路信息,管理界面显示*/ { inti; anode*p; printf("序号景点名称景点等级景点描述\n"); for(i=1;i<=a->vexnum;i++) printf("%d%s%s%s\n",i,a->vertex[i].vexdata,a->vertex[i].lv,a->vertex[i].discribe); if(a->arcnum==0) printf("没有道路! \n"); else printf("道路名称道路距离起点序号终点序号\n"); for(i=1;i<=a->vexnum;i++) { for(p=a->vertex[i].head;p! =NULL;p=p->next) if(i printf("%s%d%d%d\n",p->rname,p->weight,i,p->adjvex); } } voidadd(intk,adjlist*a)/*增加景点和路线*/ { intn,m,i,j,y,l,flag=1; anode*p,*q; charname[20]; system("cls"); show(a); if(k==4) { printf("请输入景点数和路数: \n"); scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { printf("请输入第%d个新景点名称: \n",i); scanf("%s",a->vertex[a->vexnum+i].vexdata); printf("请输入第%d个新景点等级: \n",i); scanf("%s",a->vertex[a->vexnum+i].lv); printf("请输入第%d个新景点描述: \n",i); scanf("%s",a->vertex[a->vexnum+i].discribe); a->vertex[a->vexnum+i].out=0;/*出度初始为0*/ } for(i=1;i<=n;i++)/*输入新景点的相邻景点*/ { getchar(); printf("请输入%s的相邻景点个数: \n",a->vertex[a->vexnum+i].vexdata); scanf("%d",&y); if(y>0) { a->vertex[a->vexnum+i].head=p=(anode*)malloc(sizeof(anode));/*第一次要把邻接点和头结点链接*/ while(flag) { printf("请输入第1个相邻景点序号和距离: \n"); scanf("%d%d",&p->adjvex,&p->weight); if(p->adjvex==a->vexnum+i) printf("输入有误,请重新输入: \n"); else flag=0; } flag=1; printf("请输入路名: \n"); scanf("%s",p->rname); p->next=NULL; } for(j=1;j { q=(anode*)malloc(sizeof(anode)); q->next=NULL; p->next=q; p=q; printf("请输入第%d个相邻景点序号和距离: \n",j+1); scanf("%d%d",&p->adjvex,&p->weight); printf("请输入路名: \n"); scanf("%s",p->rname); } } for(i=1;i<=n;i++)/*建立原有景点与新加景点的联系*/ for(p=a->vertex[a->vexnum+i].head;p! =NULL;p=p->next) { if(a->vertex[p->adjvex].head==NULL) q=a->vertex[p->adjvex].head=(anode*)malloc(sizeof(anode)); else { for(q=a->vertex[p->adjvex].head;q->next! =NULL;) q=q->next; q->next=(anode*)malloc(sizeof(anode)); q=q->next; } q->next=NULL; q->adjvex=a->vexnum+i; strcpy(q->rname,p->rname); q->weight=p->weight; } a->vexnum=a->vexnum+n;/*增加景点后的景点数*/ a->arcnum=a->arcnum+m;/*增加道路后的道路数*/ } else { printf("请输入要增加新道路的数量: \n"); scanf("%d",&y); a->arcnum=a->arcnum+y; for(i=1;i<=y;i++) { printf("请输入要增加新道路的起点和终点序号: \n"); scanf("%d%d",&m,&n); if(a->vertex[m].head==NULL)/*对m景点端的道路信息*/ { q=a->vertex[m].head=(anode*)malloc(sizeof(anode)); q->next=NULL; } else { for(q=a->vertex[m].head;q->next! =NULL;) q=q->next; q->next=(anode*)malloc(sizeof(anode)); q=q->next; q->next=NULL; } q->adjvex=n; printf("请输入路名: \n"); scanf("%s",q->rname); strcpy(name,q->rname);/*中间变量*/ printf("请输入第%d个新道路的长度: \n",i); scanf("%d",&q->weight); l=q->weight; if(a->vertex[n].head==NULL)/*对n景点端的道路信息,与m的相对应*/ { q=a->vertex[n].head=(anode*)malloc(sizeof(anode)); q->next=NULL; } else { for(q=a->vertex[n].head;q->next! =NULL;) q=q->next; q->next=(anode*)malloc(sizeof(anode)); q=q->next; q->next=NULL; } q->adjvex=m; strcpy(q->rname,name); q->weight=l; } } churudu(a); establish(a); printf("恭喜您增
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 导航