数据结构程序设计报告.docx
- 文档编号:14172581
- 上传时间:2023-06-21
- 格式:DOCX
- 页数:23
- 大小:697.39KB
数据结构程序设计报告.docx
《数据结构程序设计报告.docx》由会员分享,可在线阅读,更多相关《数据结构程序设计报告.docx(23页珍藏版)》请在冰点文库上搜索。
数据结构程序设计报告
成绩:
________________
算法与数据结构
课程设计报告
目录
1.系统分析----------------------------------------------1
2.概要设计----------------------------------------------1
3.详细设计----------------------------------------------4
4.测试记录----------------------------------------------8
5.总结--------------------------------------------------9
六.源程序----------------------------------------9
一.系统分析
从齐鲁工业大学迎长清校区的平面图中选取16个有代表性的景点,抽象成一个无向带权图,以图中顶点表示景点,边上的权表示两地的之间的距离。
本程序的目的是为用户提供路径查询。
根据用户指定的始点和终点输出相应路径,或者根据用户指定的景点输出景点的信息。
本算法在设计时参考了《数据结构C语言版》一书中有关Floyd算法的介绍,同时借鉴了如今网上流行的设计方式。
之所以选择本算法来实现计算最短路径,原因在于本算法容易理解,可以算出任意两个节点之间的最短距离,代码编写简单。
但是,本算法缺点在于时间复杂度过高,不适合用于计算大量数据。
Floyd算法首先将两景点间路径长度数据存储于数组D[v][w]中,而后使用一个三维数组用于存放最短路径所经过的顶点,接下来使用三重循环判断两景点之间直接路径是否大于间接路径,若大于,则将三维数组中存放的顶点信息更改为简介路径所经过的顶点信息。
2.概要设计
用的图的算法进行构造,用邻接表建立图,然后再用深度优先遍历进行搜索,查找所需的路径。
再用迪杰特斯拉算法求出两个景点之间的最佳路径。
建立无向图,把学校的景点及景点的信息,连接起来
建立邻接表采用链式加顺式存储。
浏览学校的全景(Browser):
列出学校的所有的景点。
寻找最佳路径(DFSTraverse:
):
输入一个景点,会吧所有都浏览一边,并找出最佳的路径。
最短路径(ShortPath):
求出起点和终点的最佳路径,并求出最佳路径的长度。
遍历出某一起点到终点的所有路径(SearchAllPath):
找出所有路径,利用深度优先遍历。
三.详细设计
利用深度优先的思想,遍历图找出一条最佳最佳的
的路径,让它遍历所有景点。
利用递归的思想,往下遍历,访问标志位,若访问过在下次就不用访问。
若找完一个分支在下次重新遍历。
最短路径(ShortPath):
利用迪杰特斯拉算法,求v0到其余顶点的最短路径path[],distance[]是用来存放各路径的权值,借助辅助数组s[]标志,是否当前顶点属于S(1,属于)。
遍历出某一起点到终点的所有路径(SearchAllPath):
利用图的深度优先遍历,利用访问标志位。
path[]记录路径,visited[]设访问标志,v起点,des终点,length,代表的是访问景点的长度。
若碰见死路或者不同的路,则从上一个景点,从新扫描。
四.测试记录
五.总结
(1.)在课程设计中,首先要看清问题,将问题要求理解透彻,在构思要如何实现,要用到哪些函数,要用什么算法,在课程构思中选算法是一个很重要的概念,只有确定用这么算法后才能接下来的工作,将流程图画在纸上,再依次编写代码,在程序设计中,编写代码只是一个方面,调试才是关键。
(2.)调试是一个相当繁琐的过程,有许多新的问题需要被解决,但同时它也是一个比较重要的过程,因为在程序调试过程中,我们会学到很多新的东西,从而增加我们编程的经验。
(3.)必须培养严谨的思维。
在程序的设计和编写过程中,很多错误都是应为自己不够认真细致、思维不够严谨造成的。
认真复习阅读书上的程序。
以后,不管是编程还是其他方面,都要养成思维严谨的好习惯,真正弄懂每一个问题。
(4.)通过本次实习,温固了数据结构的相关知识,加深对课内所学的有关数据的逻辑结构和存储表示、数据结构的选择和应用、算法的设计和时空效率分析等课程基本内容的理解,进一步熟悉了VC++编程环境,巩固并提高了分析问题、解决实际问题的能力。
六.源程序
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#include"iostream.h"
#defineMAXEDGE500
typedefstructArcNode
{
intdata;//该弧所得指向的顶点的位置
ArcNode*nextarc;//指向下一条弧的指针
}ArcNode,*ArcLink;
typedefstructVNode//顶点信息
{
charname[30];
intnum;
charintroduction[100];
ArcLinkfirstarc;//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX+1];
typedefstructALGraph
{
AdjListvdata;
intvexnum,arcnum;//图的顶点数和弧数
}ALGraph;
intEdge[MAX][MAX];//用来存放路径的权值
intn,e;
voidCreateGraph(AdjList&g)//创建图
{//从文件读入图的信息,包括景点信息,和路的信息
FILE*fp;
intnum;
charname[20];
charinformation[100];
inti=1;
inta,b,weight;
ArcLinkp,q;//定义一条边的两个端点的临时指针
fp=fopen("tuxinxi.txt","r");//打开图信息文件
if(fp==NULL)
{
printf("图信息文件不能打开.");
exit(0);
}
for(i=1;i<=n;i++)//对路的权值进行初始化
{
for(intj=1;j<=n;j++)
{
if(i==j)Edge[i][j]=0;//主对角线上的(自己对自己付为零);
else
Edge[i][j]=MAXEDGE;
}
}
for(i=1;i<=n;i++)//初始化邻接表,
{
g[i].firstarc=NULL;
}
for(i=1;i<=n;i++)//从文件读入顶点的信息
{fscanf(fp,"%d",&num);
g[i].num=num;
fscanf(fp,"%s",name);
strcpy(g[i].name,name);
fscanf(fp,"%s",information);
strcpy(g[i].introduction,information);
}
for(intj=1;j<=e;j++)//从文件中读入边的信息
{
fscanf(fp,"%d",&a);
fscanf(fp,"%d",&b);
fscanf(fp,"%d",&weight);
Edge[a][b]=weight;
Edge[b][a]=weight;
p=(ArcLink)malloc(sizeof(ArcNode));//为顶点申请空间
p->data=a;
p->nextarc=g[b].firstarc;
g[b].firstarc=p;//把p插进来
q=(ArcLink)malloc(sizeof(ArcNode));
q->data=b;
q->nextarc=g[a].firstarc;
g[a].firstarc=q;
}
fclose(fp);
}
voidBrowser(AdjListG)//浏览整个景点
{
intv;
printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");
printf("┃编号┃景点名称┃简介┃\n");
for(v=1;v<=n;v++)
printf("┃%-4d┃%-16s┃%-56s┃\n",G[v].num,G[v].name,G[v].introduction);
printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");
}
intGetWeight(intv1,intv2)//得到两个景点之间的路的权值
{
if(v1<0||v1>n||v2<0||v2>n)
{
printf("该地点不存在!
!
");
return0;
}
returnEdge[v1][v2];
}
voidDIJ(AdjListG,intv0,intdistance[],intpath[])//迪杰特斯拉算法
{//求v0到其余顶点的最短路径path[],distance[]是用来存放各路径的权值
//借助辅助数组s[]标志,是否当前顶点属于S(1,属于)
int*s=newint[n];
intminDis=0,i=0,j=0,u=0;
for(i=1;i<=n;i++)//初始化distance[],s[],path[]
{
distance[i]=GetWeight(v0,i);
s[i]=0;
if(i!
=v0&&distance[i] elsepath[i]=-1;//v0到v0为-1 } s[v0]=1;//v0入s集 distance[v0]=0;//v0到v0的距离为零 for(i=1;i {//开始主循环,每次求得v0到某个顶点v的最短距离,并将v并入s中 minDis=MAXEDGE;//当前所知v0顶点的最近距离,并设初值为MAXEGDE intu=v0;//把v0给u for(j=1;j<=n;j++) { if(! s[j]&&distance[j] { u=j;//在s[]一直往下找 minDis=distance[j];//赋给最小路径 } } s[u]=1;//离v0最近的景点,入s[] for(j=1;j<=n;j++)//更新当前最短路径及距离 { if(! s[j]&&GetWeight(u,j) { intnewdist=distance[u]+GetWeight(u,j); if(newdist { distance[j]=newdist; path[j]=u;//记录下寻找最短的路 } } } } } voidShortPath(AdjListg)//求两点的最短路径 { intqidian,zhongdian; intdistance[MAX]; intpath[MAX]; intminPath=0; intway[MAX]; intq=0;intpre=0; printf("\n"); printf("请输入要查询的景点的起点,终点: "); scanf("%d,%d",&qidian,&zhongdian); DIJ(g,qidian,distance,path); intw=zhongdian; while(w! =qidian)//遍历path[]并把到终点的路存放在way[]中 { q++; way[q]=path[w]; w=path[w]; } printf("路径为: ");//输出路径 for(intj=q;j>=1;j--) { printf("%s-->",g[way[j]].name); } printf("%s",g[zhongdian].name); printf("\n"); printf("最短路径为%d",distance[zhongdian]); printf("\n"); } voidSerach(AdjListG)//查询景点信息 { intk,flag=1; while(flag) { printf("请输入要查询的景点编号: "); scanf("%d",&k); if(k<0||k>n) { printf("景点编号不存在! 请重新输入景点编号: "); scanf("%d",&k); } if(k>=0&&k<=n) flag=0; } printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n"); printf("┃编号┃景点名称┃简介┃\n"); printf("┃%-4d┃%-16s┃%-56s┃\n",G[k].num,G[k].name,G[k].introduction); printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n"); } voidDFS(AdjListg,intv,intvisited[])//从v个顶点深度优先搜索 { ArcLinkp; intw; visited[v]=1;//做上访问过的标记 printf("%s->",g[v].name); p=g[v].firstarc;//取该顶点链表 while(p)//遍历该链表 { w=p->data; if(visited[w]==0) DFS(g,w,visited); p=p->nextarc; } } voidDFSTraverse(AdjListg)//深度优先遍历 { intvisited[MAX+1]; intv; intnum,count=1; for(v=1;v<=n;v++) { visited[v]=0;//初始化标志位 } printf("请输入你要开始的景点: "); scanf("%d",&num); while(count<=n) {v=num; if(visited[v]==0) { DFS(g,v,visited);//对尚未访问的顶点调用DFS v++; } count++; } } voidPrintPath(AdjListg,intpath[],intlength)//打印路径 { for(inti=0;i { printf("%s-->",g[path[i]].name); } printf("\n"); } voidSearchAllPath(AdjListG,intpath[],intvisited[],intv,intdes,intlength) {//利用深度优先遍历,path[]记录路径,visited[]设访问标志,v起点,des终点,length,代表的是访问景点的长度 if(visited[v])return;//若所有的景点都访问过,则终止 path[length-1]=v;//开始记录路径 if(v==des)//若找到终点则,打印路径 { PrintPath(G,path,length); } else { visited[v]=1; for(inti=1;i<=n;i++) if(GetWeight(v,i)! =MAXEDGE&&! visited[i])//两个景点之间有路,并且还未访问过,则深度遍历 { SearchAllPath(G,path,visited,i,des,length+1); } visited[v]=0; } } voidInitGraph(AdjList&g)//初始化图的景点 { printf("请输入图中的顶点数: "); scanf("%d",&n); printf("请输入道路的数目: "); scanf("%d",&e); printf("\n"); printf("用户可以自己写文件创建图的信息."); CreateGraph(g); } charMenu()//主菜单 { charc; intflag; do{ printf("\n西安邮电学院导游图\n"); printf("┏━━━━━━━━━━━━━━━━━━━━┓\n"); printf("┃1.创建导游系统|\n"); printf("┃2.浏览校园全景┃\n"); printf("┃3.寻找某一起点的最佳路径┃\n"); printf("┃4.选择出发点和目的地┃\n"); printf("┃5.查看景点信息┃\n"); printf("┃6.浏览出一个起点的所有路径┃\n"); printf("┃7.浏览校园图┃\n"); printf("┃8.退出系统┃\n"); printf("┗━━━━━━━━━━━━━━━━━━━━┛\n"); printf("请选择(1--8)-: "); scanf("%c",&c); if(c=='1'||c=='2'||c=='3'||c=='4'||c=='5'||c=='6'||c=='7'||c=='8') flag=0; if(flag) printf("输入错误,请重新选择."); getchar(); }while(flag); returnc; } voidnarrate(AdjListg)/*说明函数*/ { inti,k=0; printf("\n\t\t*****************欢迎使用校园导游程序***************\n"); printf("\t__________________________________________________________________\n"); printf("\t\t景点名称\t\t|\t景点描述\n"); printf("\t________________________________|_________________________________\n"); for(i=1;i<=n;i++) { printf("\t%c(%2d)%-10s\t\t|\t%-25s%c\n",2,i,g[i].name,g[i].introduction,2);/*输出景点列表*/ k=k+1; } printf("\t________________________________|_________________________________\n"); } voidmain()//主函数 { AdjListg; intv0,v1,i;intvisited[MAX]; intpath[MAX]; charc; system("color5f"); do { c=Menu(); switch(c) { case'1': system("cls"); InitGraph(g); printf("\n\n\t\t\t\t请按任意键继续...\n"); getchar(); getchar(); break; case'2': system("cls"); Browser(g); break; case'3': system("cls"); narrate(g); DFSTraverse(g); printf("\n\n\t\t\t\t请按任意键继续...\n"); getchar(); getchar(); break; case'4': system("cls"); narrate(g); ShortPath(g); printf("\n\n\t\t\t\t请按任意键继续...\n"); getchar(); getchar(); break; case'5': Serach(g); printf("\n\n\t\t\t\t请按任意键继续...\n"); getchar(); getchar(); break; case'6': system("cls"); narrate(g); printf("请输入查询起点,终点: "); scanf("%d,%d",&v0,&v1); for(i=1;i<=n;i++)visited[i]=0;//初始化 SearchAllPath(g,path,visited,v0,v1,1); printf("\n\n\t\t\t\t请按任意键继续...\n"); getchar(); getchar(); break; case'7': system("cls"); PrintTU(); printf("\n\n\t\t\t\t请按任意键继续...\n"); getchar(); getchar(); break; case'8': printf("\n"); printf("\n"); printf("\n"); printf("\n"); printf("谢谢使用."); printf("\n"); break;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 程序设计 报告