数据结构课程设计-迷宫求解.doc

迷宫求解
一．问题描述
对迷宫问题的求解过程实际就是从入口开始，一步一步地走到出口的过程。
基本要求：
输入一个任意大小的迷宫数据，用递归和非递归两种方法求出一条走出迷宫的路径，并将路径输出。
二．设计思路
在本程序中用两种方法求解迷宫问题-非递归算法和递归算法。
对于非递归算法采用回溯的思想，即从入口出发，按某一方向向前探索，若能走通，并且未走过，则说明某处可以到达，即能到达新点，否则试探下一方向；若所有的方向均没有通路，或无路可走又返回到入口点。在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈保存所能到达的没一点的下标及该点前进的方向，然后通过对各个点的进出栈操作来求得迷宫通路。
对于递归算法，在当前位置按照一定的策略寻找下个位置，在下个位置又按照相同的策略寻找下下个位置…；直到当前位置就是出口点，每一步的走法都是这样的。随着一步一步的移动，求解的规模不断减小；如果起始位置是出口，说明路径找到，算法结束，如果起始位置的四个方向都走不通，说明迷宫没有路径，算法也结束。
另外，为了保证迷宫的每个点都有四个方向可以试探，简化求解过程，将迷宫四周的值全部设为1，因此将m行n列的迷宫扩建为m+2行，n+2列，同时用数组来保存迷宫阵列。
三．数据结构设计
在迷宫阵列中每个点都有四个方向可以试探，假设当前点的坐标（x，y），与其相邻的四个点的坐标都可根据该点的相邻方位而得到，为了简化问题，方便求出新点的坐标，将从正东开始沿顺时针进行的这四个方向的坐标增量放在一个结构数组move[4]中，每个元素有两个域组成，其中x为横坐标增量，y为纵坐标增量，定义如下：
typedef struct
{
int x,y;
}item;
为到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，还要将从前一点到本点的方向压入栈中。栈中的元素由行、列、方向组成，定义如下：
typedef struct
{
int x,y,d;
}DataType;
由于在非递归算法求解迷宫的过程中用到栈，所以需定义栈的类型，本程序中用的是顺序栈，类型定义如下;
typedef struct
{
DataType data[MAXSIZE];
int top;
}SeqStack, *PSeqStack;

四．功能函数设计
（1）函数PSeqStack Init_SeqStack()
此函数实现对栈的初始化工作。
（2）函数Empty_SeqStack(PSeqStack S)
此函数用于判断栈是否为空。
（3）函数Push_SeqStack (PSeqStack S, DataType x)
此函数实现入栈操作。
（4）函数Pop_SeqStack(PSeqStack S ,DataType *x)
此函数实现出栈操作。
（5）函数Destory_Seqstack(PSeqStack *S)
此函数执行栈的销毁操作，释放内存空间。
（6）函数mazepath(int maze[][n+2],item move[],int x0,int y0)
此函数实现对迷宫问题的非递归算法求解。在求解过程中需调用上面定义的关于栈的一系列函数（栈的初始化，判空，入栈，出栈，栈的销毁），进而求得迷宫路径。
（7）函数path(int maze[][n+2],item move[],int x,int y,int step)
此函数实现对迷宫问题的递归算法求解。
（8）函数print_way(int maze[][n+2],item move[])
此函数用于在递归算法求解迷宫后输出求解后的结果，即打印迷宫路径。
（9）函数copy(int maze[][n+2],int ms[][n+2])
此函数的作用是复制一下输入的原始迷宫序列，因为本程序是通过菜单选择求解迷宫的实现方式，将非递归算法和递归算法放在一起通过菜单选择实现，在调用完一种算法后，为保证调用另一种算法时原始迷宫序列未改变，所以需调用此函数来原始迷宫序列备份一下。
（10）主函数main()
定义变量，实现迷宫的输入操作，通过菜单选择求解迷宫路径的实现方法，调用相关函数。
（11）系统功能总体模块
（a）栈的初始化

（b）判栈空函数

（c）入栈

（d）出栈

（e）销毁栈

（f）非递归算法求解迷宫函数

（g）递归算法求解迷宫函数

（h）打印递归算法求解迷宫的路径函数

（i） 复制原始迷宫阵列函数

（j）主函数

五．编码实现
#include<stdio.h>
#include<stdlib.h>
#define m 6
#define n 8
#define MAXSIZE 100
typedef struct
{
int x,y;
}item;
item move[4];
typedef struct
{
int x,y,d;
}DataType;
typedef struct
{
DataType data[MAXSIZE];
int top;
}SeqStack, *PSeqStack;

PSeqStack Init_SeqStack() //栈的初始化
{
PSeqStack S;
S=(PSeqStack)malloc(sizeof(SeqStack));
if (S)
S->top=-1;
return S;
}
int Empty_SeqStack(PSeqStack S) //判栈空
{
if (S->top==-1)
return 1;
else
return 0;
}
int Push_SeqStack (PSeqStack S, DataType x) //入栈
{
if (S->top==MAXSIZE-1)
return 0; //栈满不能入栈
else
{
S->top++;
S->data[S->top]=x;
return 1;
}
}
int Pop_SeqStack(PSeqStack S ,DataType *x) //出栈
{
if (Empty_SeqStack ( S ) )
return 0; //栈空不能出栈
else
{
*x=S->data[S->top];
S->top--;
return 1;
}
}
void Destory_Seqstack(PSeqStack *S) //销毁栈
{
if(*S)
free(*S);
*S=NULL;
return;
}
int mazepath(int maze[][n+2],item move[],int x0,int y0) //非递归算法求解迷宫
{
PSeqStack S;
DataType temp;
int x,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(!Empty_SeqStack(S))
{
Pop_SeqStack(S,&temp);
printf("(%d %d) <- ",temp.x,temp.y);
}
printf("\n\n................................................................................\n");
Destory_Seqstack(&S);
return 1;
}
else
d=0;
}
else
d++;
}
}
Destory_Seqstack(&S);
return 0;

}

int path(int maze[][n+2],item move[],int x,int y,int step) //递归算法求解迷宫
{
int i;
step++;
maze[x][y]=step;
if(x==m&&y==n)
return 1;
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))
return 1;
}
step--;
maze[x][y]=0;
return 0;
}
void print_way(int maze[][n+2],item move[]) //打印递归算法求解迷宫的路径
{
int i,j;
if(path(maze,move,1,1,1))
{
printf("\n找到路径的矩阵形式输出如下：\n");
for(i=0;i<m+2;i++)
{
for(j=0;j<n+2;j++)
printf("%d ",maze[i][j]);
printf("\n");
}
printf("\n");
printf("递归算法求解的迷宫路径为（顺序为从入口到出口输出）：\n");
for(i=0;i<m+2;i++)
for(j=0;j<n+2;j++)
if(maze[i][j]>1)
printf("(%d %d) -> ",i,j);
printf("\n\n................................................................................\n");
}
else
printf("无法找到路径！\n");
}
void copy(int maze[][n+2],int ms[][n+2]) //复制原始迷宫序列函数
{

for(int i=0;i<m+2;i++)
{
for(int j=0;j<n+2;j++)
ms[i][j]=maze[i][j];

}
}
void main()
{
int maze[m+2][n+2];
item move[4];
int i,j,Q;
printf("请输入迷宫序列：\n");
for(i=0;i<m+2;i++)
{
for(j=0;j<n+2;j++)
scanf("%d",&maze[i][j]);
}
printf("\n");
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;
printf("\n");
int mase1[m+2][n+2];
copy(maze,mase1);
printf("********************************走迷宫******************************************\n");
printf("\n");
printf("1. 非递归形式走迷宫\n");
printf("2. 递归形式走迷宫\n");
printf("3. 退出\n");
printf("********************************求解方式****************************************\n");
while(1)
{
printf("\n请选择(选择0退出)：：");
scanf("%d",&Q);
switch(Q)
{
case 1:
mazepath(maze,move,1,1);
break;
case 2:
print_way(mase1,move);
break;
case 0:
exit(0);
}
}
}
六．运行与测试

七．总结
在这个课程设计中，遇到的主要问题是选择了一种实现方法后，在选择另一种时不会输出结果，但是当我把这两个程序分开调试时都会出现结果，结果还是正确的，后来经过分析知道原来是调用完一种方法后，原来输入的迷宫序列可能被改变了，因此，又增加了一个复制原始迷宫序列的函数，对原始序列进行了保存，然后在调用时就出现结果了。通过调试这个程序，熟悉了迷宫的两种求法，在调试找错过程中也学会好多。

构造n个城市连接的最小生成树
一．问题描述
一个地区的n个城市间的距离网，用Prim算法建立最小生成树，并计算得到的最小生成树的代价。
基本要求：
1) 城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。
2)表示城市间距离网的邻接矩阵(要求至少6个城市，10条边)
二．设计思路
在本程序中，各个地区之间的距离网可以用邻接矩阵表示，在进行定义时表示出相应的权值，以便计算最小代价，当权值赋为999时，表示两城市之间无路径。然后用Prim算法建立最小生成树，进而在建立过程中可以计算得到的最小生成树的代价。
三．数据结构设计
首先，在用邻接矩阵存储图时，除了用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外，还需要用一个一维数组来存储顶点信息，另外，还有图的顶点数和边数。故可将其形式描述如下：
typedef struct
{
char vertexs[MaxVertexNum];
int arcs[MaxVertexNum][MaxVertexNum];
int vertexNum,edgeNum;
}MGraph;
为实现普利姆算法求最小生成树，需设置一个辅助数组Closedge，里面存放一顶点为与已构造好的部分生成树的顶点间权值最小的顶点，边为某顶点与已构造好的部分生成树的顶点间的最小权值。定义形式如下：
typedef struct
{
int adjvertex;
int lowcost;
}ClosEdge[MaxVertexNum];

四．功能函数设计
（1）函数CreatGraph(MGraph *G)
此函数用于创建邻接矩阵，用邻接矩阵来存储图，建立各个城市之间的关系。在建立过程中，给相应的边赋权值，以表示两城市之间的代价。注： 999代表两城市之间无路径。
（2）函数MiniSpanTree_PRIM(MGraph *G,int u,ClosEdge closedge)
此函数为普利姆函数，用于求最小生成树，在此过程中求出相应的权值，及最小生成树权值之和，用于表示连接各城市之间的最小代价。
（3）主函数main（）
定义变量，分别调用相应的函数。
（4）系统功能总体模块
（a）创建邻接矩阵CreatGraph(MGraph *G)的流程图如下：

（b）构建最小生成树普利姆函数MiniSpanTree_PRIM(MGraph *G,int u,ClosEdge closedge)流程图如下:

（c）主函数main()流程图如下：

五．编码实现
#include<stdio.h>
#include<stdlib.h>
#define MaxVertexNum 30
#define INFINITY 3000
typedef struct
{
char vertexs[MaxVertexNum];
int arcs[MaxVertexNum][MaxVertexNum];
int vertexNum,edgeNum;
}MGraph;
typedef struct
{
int adjvertex;
int lowcost;
}ClosEdge[MaxVertexNum];

void CreatGraph(MGraph *G)
{
int i,j,k,n;
printf("请输入顶点数和边数：");
scanf("%d %d",&(G->vertexNum),&(G->edgeNum));
printf("\n");
for(i=0;i<G->vertexNum;i++)
{
printf("请输入第%d个顶点字符信息(共%d个)：",i+1,G->vertexNum);
scanf("%c",&(G->vertexs[i]));
getchar();
}
for(i=0;i<G->vertexNum;i++)
for(j=0;j<G->vertexNum;j++)
{
if(i==j)
G->arcs[i][j]=0;
else
G->arcs[i][j]=999;
}

for(k=0;k<(G->edgeNum);k++)
{
printf("\n");
printf("请输入边<Vi,Vj>对应的顶点序号(共%d个)：",G->edgeNum);
scanf("%d %d",&i,&j);
printf("请输入此边的权值：");
scanf("%d",&n);
G->arcs[i][j]=n;
G->arcs[j][i]=n;
}
printf("\n");
printf("图已成功创建!\n");
printf("\n");
}

void MiniSpanTree_PRIM(MGraph *G,int u,ClosEdge closedge)
{
int i,j,w,k;
int count=0;
for(i=0;i<G->vertexNum;i++)
if(i!=u)
{
closedge[i].adjvertex=u;
closedge[i].lowcost=G->arcs[u][i];
}
closedge[u].lowcost=0;
for(i=0;i<G->vertexNum-1;i++)
{
w=INFINITY;
for(j=0;j<G->vertexNum;j++)
if(closedge[j].lowcost!=0 && closedge[j].lowcost<w)
{
w=closedge[j].lowcost;
k=j;
}
closedge[k].lowcost=0;
for(j=0;j<G->vertexNum;j++)
if(G->arcs[k][j]<closedge[j].lowcost)
{
closedge[j].adjvertex=k;
closedge[j].lowcost=G->arcs[k][j];
}
}
for(i=0;i<G->vertexNum;i++)
if(i!=u)
{

printf("输出构建的最小生成树为：");
printf("%d->%d,%d\n",i,closedge[i].adjvertex,G->arcs[i][closedge[i].adjvertex]);
count+=G->arcs[i][closedge[i].adjvertex];
}
printf("\n");
printf("此最小生成树的代价为：%d",count);
printf("\n");
}

void main()
{
MGraph *G;
int u;
ClosEdge closedge;
G=(MGraph*)malloc(sizeof(MGraph));

CreatGraph(G);
printf("输入构造最小生成树的出发顶点：");
scanf("%d",&u);
printf("\n");
MiniSpanTree_PRIM(G,u,closedge);
printf("\n");

}
六．运行与测试

七．总结
本程序相对来说不太难，但在调试过程中也遇到很多错误，其中也包括很多低级错误，还有内存溢出问题，不出现结果问题，通过在猜测出问题的地方加写printf输出提示，然后查找原因，发现了好多问题。最后找到原因，加以改正。通过这次的课程设计，使我加深了对相关知识点的理解掌握，同时在设计调试过程中，也发现了好多的不足之处，对学过的好多知识点都掌握的不够牢固，所以在用起来时经常会出错，还有许多因为粗心带来的问题，虽然在这次课程设计花费了好长时间，但总的来说，收获还是挺大的。