大数据结构课程设计迷宫求解Word文档下载推荐.docx
《大数据结构课程设计迷宫求解Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《大数据结构课程设计迷宫求解Word文档下载推荐.docx（23页珍藏版）》请在冰点文库上搜索。
（3）函数Push_SeqStack（PSeqStackS,DataTypex）
此函数实现入栈操作。
（4）函数Pop_SeqStack（PSeqStackS,DataType*x）
此函数实现出栈操作。
（5）函数Destory_Seqstack（PSeqStack*S）
此函数执行栈的销毁操作，释放内存空间。
（6）函数mazepath（intmaze[][n+2],itemmove[],intx0,inty0）
此函数实现对迷宫问题的非递归算法求解。
在求解过程中需调用上面定义的关于栈的一系列函数（栈的初始化，判空，入栈，出栈，栈的销毁），进而求得迷宫路径。
（7）函数path（intmaze[][n+2],itemmove[],intx,inty,intstep）
此函数实现对迷宫问题的递归算法求解。
（8）函数print_way（intmaze[][n+2],itemmove[]）
此函数用于在递归算法求解迷宫后输出求解后的结果，即打印迷宫路径。
（9）函数copy（intmaze[][n+2],intms[][n+2]）
此函数的作用是复制一下输入的原始迷宫序列，因为本程序是通过菜单选择求解迷宫的实现方式，将非递归算法和递归算法放在一起通过菜单选择实现，在调用完一种算法后，为保证调用另一种算法时原始迷宫序列未改变，所以需调用此函数来原始迷宫序列备份一下。
（10）主函数main（）
定义变量，实现迷宫的输入操作，通过菜单选择求解迷宫路径的实现方法，调用相关函数。
（11）系统功能总体模块
（a）栈的初始化
（b）判栈空函数
（c）入栈
（d）出栈
（e）销毁栈
（f）非递归算法求解迷宫函数
（g）递归算法求解迷宫函数
（h）打印递归算法求解迷宫的路径函数
（i）复制原始迷宫阵列函数
（j）主函数
五．编码实现
#include<
stdio.h>
stdlib.h>
#definem6
#definen8
#defineMAXSIZE100
itemmove[4];
PSeqStackInit_SeqStack（）//栈的初始化
{
PSeqStackS;
S=（PSeqStack）malloc（sizeof（SeqStack））;
if（S）
S->
top=-1;
returnS;
}
intEmpty_SeqStack（PSeqStackS）//判栈空
if（S->
top==-1）
return1;
else
return0;
intPush_SeqStack（PSeqStackS,DataTypex）//入栈
top==MAXSIZE-1）
//栈满不能入栈
{
top++;
data[S->
top]=x;
}
intPop_SeqStack（PSeqStackS,DataType*x）//出栈
if（Empty_SeqStack（S））
//栈空不能出栈
else
{
*x=S->
top];
top--;
}
voidDestory_Seqstack（PSeqStack*S）//销毁栈
if（*S）
free（*S）;
*S=NULL;
return;
intmazepath（intmaze[][n+2],itemmove[],intx0,inty0）//非递归算法求解迷宫
DataTypetemp;
intx,y,d,i,j;
temp.x=x0;
temp.y=y0;
temp.d=-1;
S=Init_SeqStack（）;
if（!
S）
printf（"
栈初始化失败！
"
）;
return（0）;
Push_SeqStack（S,temp）;
while（!
Empty_SeqStack（S））
Pop_SeqStack（S,&
temp）;
x=temp.x;
y=temp.y;
d=temp.d+1;
while（d<
4）
{
i=x+move[d].x;
j=y+move[d].y;
if（maze[i][j]==0）
{
temp.x=x;
temp.y=y;
temp.d=d;
Push_SeqStack（S,temp）;
x=i;
y=j;
maze[x][y]=-1;
if（x==m&
&
y==n）
{
printf（"
\n非递归算法求解的迷宫路径为（顺序为从出口到入口输出）：
\n"
while（!
{
Pop_SeqStack（S,&
printf（"
（%d%d）<
-"
temp.x,temp.y）;
}
\n\n................................................................................\n"
Destory_Seqstack（&
S）;
return1;
}
else
d=0;
}
else
d++;
}
Destory_Seqstack（&
return0;
intpath（intmaze[][n+2],itemmove[],intx,inty,intstep）//递归算法求解迷宫
inti;
step++;
maze[x][y]=step;
if（x==m&
for（i=0;
i<
4;
i++）
if（maze[x+move[i].x][y+move[i].y]==0）
if（path（maze,move,x+move[i].x,y+move[i].y,step））
return1;
step--;
maze[x][y]=0;
voidprint_way（intmaze[][n+2],itemmove[]）//打印递归算法求解迷宫的路径
inti,j;
if（path（maze,move,1,1,1））
\n找到路径的矩阵形式输出如下：
for（i=0;
m+2;
for（j=0;
j<
n+2;
j++）
printf（"
%d"
maze[i][j]）;
printf（"
递归算法求解的迷宫路径为（顺序为从入口到出口输出）：
if（maze[i][j]>
1）
（%d%d）->
"
i,j）;
无法找到路径！
voidcopy（intmaze[][n+2],intms[][n+2]）//复制原始迷宫序列函数
for（inti=0;
for（intj=0;
ms[i][j]=maze[i][j];
voidmain（）
intmaze[m+2][n+2];
itemmove[4];
inti,j,Q;
printf（"
请输入迷宫序列：
for（j=0;
scanf（"
%d"
&
maze[i][j]）;
move[0].x=0;
move[0].y=1;
move[1].x=1;
move[1].y=0;
move[2].x=0;
move[2].y=-1;
move[3].x=-1;
move[3].y=0;
intmase1[m+2][n+2];
copy（maze,mase1）;
********************************走迷宫******************************************\n"
1.非递归形式走迷宫\n"
2.递归形式走迷宫\n"
3.退出\n"
********************************求解方式****************************************\n"
while
（1）
\n请选择（选择0退出）：
：
scanf（"
Q）;
switch（Q）
case1:
mazepath（maze,move,1,1）;
break;
case2:
print_way（mase1,move）;
case0:
exit（0）;
六．运行与测试
七．总结
在这个课程设计中，遇到的主要问题是选择了一种实现方法后，在选择另一种时不会输出结果，但是当我把这两个程序分开调试时都会出现结果，结果还是正确的，后来经过分析知道原来是调用完一种方法后，原来输入的迷宫序列可能被改变了，因此，又增加了一个复制原始迷宫序列的函数，对原始序列进行了保存，然后在调用时就出现结果了。
通过调试这个程序，熟悉了迷宫的两种求法，在调试找错过程中也学会好多。
构造n个城市连接的最小生成树
一个地区的n个城市间的距离网，用Prim算法建立最小生成树，并计算得到的最小生成树的代价。
1）城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。
要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。
2）表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）
在本程序中，各个地区之间的距离网可以用邻接矩阵表示，在进行定义时表示出相应的权值，以便计算最小代价，当权值赋为999时，表示两城市之间无路径。
然后用Prim算法建立最小生成树，进而在建立过程中可以计算得到的最小生成树的代价。
首先，在用邻接矩阵存储图时，除了用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外，还需要用一个一维数组来存储顶点信息，另外，还有图的顶点数和边数。
故可将其形式描述如下：
typedefstruct
charvertexs[MaxVertexNum];
intarcs[MaxVertexNum][MaxVertexNum];
intvertexNum,edgeNum;
}MGraph;
为实现普利姆算法求最小生成树，需设置一个辅助数组Closedge，里面存放一顶点为与已构造好的部分生成树的顶点间权值最小的顶点，边为某顶点与已构造好的部分生成树的顶点间的最小权值。
定义形式如下：
intadjvertex;
intlowcost;
}ClosEdge[MaxVertexNum];
（1）函数CreatGraph（MGraph*G）
此函数用于创建邻接矩阵，用邻接矩阵来存储图，建立各个城市之间的关系。
在建立过程中，给相应的边赋权值，以表示两城市之间的代价。
注：
999代表两城市之间无路径。
（2）函数MiniSpanTree_PRIM（MGraph*G,intu,ClosEdgeclosedge）
此函数为普利姆函数，用于求最小生成树，在此过程中求出相应的权值，及最小生成树权值之和，用于表示连接各城市之间的最小代价。
（3）主函数main（）
定义变量，分别调用相应的函数。
（4）系统功能总体模块
（a）创建邻接矩阵CreatGraph（MGraph*G）的流程图如下：
（b）构建最小生成树普利姆函数MiniSpanTree_PRIM（MGraph*G,intu,ClosEdgeclosedge）流程图如下:
（c）主函数main（）流程图如下：
#defineMaxVertexNum30
#defineINFINITY3000
voidCreatGraph（MGraph*G）
inti,j,k,n;
请输入顶点数和边数：
scanf（"
%d%d"
（G->
vertexNum）,&
edgeNum））;
G->
vertexNum;
请输入第%d个顶点字符信息（共%d个）：
i+1,G->
vertexNum）;
%c"
vertexs[i]））;
getchar（）;
if（i==j）
G->
arcs[i][j]=0;
arcs[i][j]=999;
for（k=0;
k<
edgeNum）;
k++）
请输入边<
Vi,Vj>
对应的顶点序号（共%d个）：
G->
i,&
j）;
请输入此边的权值：
n）;
G->
arcs[i][j]=n;
arcs[j][i]=n;
图已成功创建!
voidMiniSpanTree_PRIM（MGraph*G,intu,ClosEdgeclosedge）
inti,j,w,k;
intcount=0;
if（i!
=u）
closedge[i].adjvertex=u;
closedge[i].lowcost=G->
arcs[u][i];
closedge[u].lowcost=0;
vertexNum-1;
w=INFINITY;
if（closedge[j].lowcost!
=0&
closedge[j].lowcost<
w）
w=closedge[j].lowcost;
k=j;
closedge[k].lowcost=0;
for（j=0;
if（G->
arcs[k][j]<
closedge[j].lowcost）
closedge[j].adjvertex=k;
closedge[j].lowcost=G->
arcs[k][j];
if（i!
输出构建的最小生成树为：
%d->
%d,%d\n"
i,closedge[i].adjvertex,G->
arcs[i][closedge[i].adjvertex]）;
count+=G->
arcs[i][closedge[i].adjvertex];
此最小生成树的代价为：
count）;
MGraph*G;
intu;
ClosEdgeclosedge;
G=（MGraph*）malloc（sizeof（MGraph））;
CreatGraph（G）;
输入构造最小生成树的出发顶点：
u）;
MiniSpanTree_PRIM（G,u,closedge）;
本程序相对来说不太难，但在调试过程中也遇到很多错误，其中也包括很多低级错误，还有内存溢出问题，不出现结果问题，通过在猜测出问题的地方加写printf输出提示，然后查找原因，发现了好多问题。
最后找到原因，加以改正。
通过这次的课程设计，使我加深了对相关知识点的理解掌握，同时在设计调试过程中，也发现了好多的不足之处，对学过的好多知识点都掌握的不够牢固，所以在用起来时经常会出错，还有许多因为粗心带来的问题，虽然在这次课程设计花费了好长时间，但总的来说，收获还是挺大的。
升级会员 