数据结构程序设计报告.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）;//对尚未访问的顶点调用ＤＦＳ
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;
升级会员 