用户注册



邮箱：

密码：

用户登录


邮箱：

密码：
记住登录一个月忘记密码？

发表随想


还能输入：200字
云代码 - c代码库

迷宫

2012-10-30 作者： 上帝是男孩举报

[c]代码库

//应用线性表解决实际问题。
//问题描述：从一个迷宫的入口到出口找出一条最短路经。用一个二维数组MAZE(1：m，
//1：n)模拟迷宫，数组元素为0 表示该位置可以通过， 数组元素为1 表示该位置不可以
//通行。MAZE(1，1)和MAZE(m，n)分别为迷宫的入口和出口。输入数据：a. 输入迷
//宫的大小m 行和n 列，两者为整数；b.由随机数产生0 或1，建立迷宫。输出数据：首
//先输出模拟迷宫的二维数组，若存在最短路经，则由出口回朔到入口打印这一条路径，
//如下所示：
//(m，n)， ……， (i，j)， ……， (1，1)
//如无通道，则打印：
//There is no path.

#include<stdio.h>
#include<stdlib.h>
#include"test5.h"
#include<string.h>
#include<time.h>

int main()
{
	int m,n;
	int MAZE[Max][Max],MARK[Max][Max];
	int (*p)[Max],(*q)[Max];
	unsigned char flag=0;
	LinkStack *S;
	QNode MOVE;

	p=MAZE;
	q=MARK;
	printf("输入行数和列数:\n");
	scanf("%d%d",&m,&n);

	S=CreateStack();//创建链式栈(查找数组)

	InitMOVE(&MOVE);//初始化方向数组
	InitMAZE(MAZE,m+2,n+2);//初始化迷宫
	InitMARK(MARK,m+2,n+2);//初始化标志数组
    InitStack(S);//初始化链式栈(查找数组)

	Display(MAZE,m+2,n+2);
	printf("\n\n");
	Display(MARK,m+2,n+2);
	printf("\n\n");
	flag=Index(p,q,&MOVE,S,m,n);//搜索迷宫是否有通路
    if(flag)
	{
		TraQueue(S);//输出栈中（查找数据）的数据
		printf("\n\n");
		Display(MARK,m+2,n+2);
	}
	else
		printf("there is no path!\n");

	return 0;
}

	




//////////////////////////////////////
/*           MAZE.cpp              */
/*                                 */
/*   filename:MAZE.h               */
/*   description:MAZE.h的实现文件  */
/*   designer: zhu jian            */
/*   data: 12-10-27                */
/*   QQ:505169307                  */
/////////////////////////////////////



#include<stdio.h>
#include<stdlib.h>
#include"test5.h"
#include<string.h>
#include<time.h>

LinkStack *CreateStack(void)//创建一个链式栈结点
{
	LinkStack *temp;
	temp=(LinkStack *)malloc(sizeof(LinkStack));
	if(!temp)
		return NULL;

	temp->count=0;
	return temp;
}

unsigned char InitMOVE(QNode *MOVE)//初始化方向数组MOVE
{
	QNode *p;
	p=MOVE;
	if(!MOVE)
		return ERROR;

	p->data[0][0]=-1;
	p->data[0][1]=0;

	p->data[1][0]=-1;
	p->data[1][1]=1;

	p->data[2][0]=0;
	p->data[2][1]=1;

	p->data[3][0]=1;
	p->data[3][1]=1;

	p->data[4][0]=1;
	p->data[4][1]=0;

	p->data[5][0]=1;
	p->data[5][1]=-1;

	p->data[6][0]=0;
	p->data[6][1]=-1;

	p->data[7][0]=-1;
	p->data[7][1]=-1;

	p->front=0;
	return OK;
}

unsigned char InitStack(LinkStack *S)//初始化链式栈（查找数组）
{
	LinkStack *p;
	SqStack *q;
	p=S;
	q=(SqStack *)malloc(sizeof(SqStack));
	if(!q || !S)
		return ERROR;

	q->data[0]=0;
	q->data[1]=0;
	q->next=NULL;
	p->top=q;
	return OK;
}

unsigned char InitMAZE(int p[][Max],int m,int n)//初始化迷宫
{
	int i,j;
	srand(time(0));
	if(!p)
		return ERROR;

	for(i=0,j=0;j<n;j++)
		p[i][j]=1;
	for(i=m-1,j=0;j<n;j++)
		p[i][j]=1;
	for(j=0,i=0;i<m;i++)
		p[i][j]=1;
	for(j=n-1,i=0;i<m;i++)
		p[i][j]=1;

	for(i=1;i<m-1;i++)
		for(j=1;j<n-1;j++)
			p[i][j]=rand()%2;

	p[1][1]=0;
	p[m-2][n-2]=0;
	return OK;
}

unsigned char InitMARK(int p[][Max],int m,int n)//初始化标志数组
{
	int i,j;
	if(!p)
		return ERROR;

	for(i=0,j=0;j<n;j++)
		p[i][j]=1;
	for(i=m-1,j=0;j<n;j++)
		p[i][j]=1;
	for(j=0,i=0;i<m;i++)
		p[i][j]=1;
	for(j=n-1,i=0;i<m;i++)
		p[i][j]=1;

	for(i=1;i<m-1;i++)
		for(j=1;j<n-1;j++)
			p[i][j]=0;

	return OK;
}

unsigned char Display(int S[][Max],int m,int n)//输出二维数组的数据
{
	int i,j;
	if(!S)
		return ERROR;

	for(i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
			printf("%d ",S[i][j]);
		printf("\n");
	}

	return OK;
}

unsigned char TraQueue(LinkStack *S)//输出栈中（查找数据）的数据
{
	int i=1,num;
	LinkStack *temp;
	temp=S;
	if(!S)
		return ERROR;

	num=temp->count;
	while(i<num)
	{
		printf("(%d,%d) ",temp->top->data[0],temp->top->data[1]);
		temp->top=temp->top->next;
		i++;
	}
	
	return OK;
}

unsigned char AlterMARK(int (*MARK)[Max],int i,int j)//修改标志数组
{
	if(!MARK)
		return ERROR;

	MARK[i][j]=1;
	return OK;
}

unsigned char InsertStack(LinkStack *S,int i,int j)//将出发点插入查找链式栈中
{
	LinkStack *temp;
	SqStack *p;
	temp=S;
	if(!S)
		return ERROR;

	p=(SqStack *)malloc(sizeof(SqStack));
	if(!p)
		return ERROR;

	p->data[0]=i;
	p->data[1]=j;
	p->next=temp->top;
	temp->top=p;
	temp->count++;
	return OK;
}

unsigned char DeQNode(QNode *MOVE,int *i,int *j)//取方向数组队列的头结点（出队）
{
	QNode *temp;
	temp=MOVE;
	if(!MOVE)
		return ERROR;

	*i=temp->data[temp->front][0];
	*j=temp->data[temp->front][1];
	
	temp->front=(temp->front+1)%8;
	return OK;
}

unsigned char  Judge(int (*MAZE)[Max],int (*MARK)[Max],LinkStack *S,int *i,int *j,int *flag)//判断下一个位置是否可以通过
{
	LinkStack *temp;

	temp=S;
	if(!MAZE || !MARK || !S)
		return ERROR;

	*i=temp->top->data[0]-*i;
	*j=temp->top->data[1]+*j;
	
	if(MAZE[*i][*j]==1 || MARK[*i][*j]==1)
	{
		*flag=0;
		return ERROR;
	}

	*flag=1;
	return OK;
}

unsigned char DeStack(LinkStack *S)//删除栈(查找数组)的头结点
{
	LinkStack *temp;
	SqStack *p;
	if(!S)
		return ERROR;

	temp=S;
	p=temp->top;
	temp->top=temp->top->next;
	temp->count--;
	free(p);

	return OK;
}

unsigned char Index(int (*MAZE)[Max],int (*MARK)[Max],QNode *MOVE,LinkStack *S,int m,int n)//搜索迷宫是否有通路
{
	int i=1,j=1,num;
	int judge=0;
	QNode *Q;
	LinkStack *temp;

	Q=MOVE;//方向数组
	temp=S;//查找数组
	if(!MAZE || !MARK || !MOVE || !S)
		return ERROR;

	AlterMARK(MARK,i,j);//修改标志数组
	InsertStack(temp,i,j);//将出发点输入到查找数组中
	while(temp->top->data[0]!=m && temp->top->data[1]!=n)
	{
		num=0;
		while(num < 8)
		{
			DeQNode(Q,&i,&j);//取方向数组队列的头结点(出队)
	        Judge(MAZE,MARK,temp,&i,&j,&judge);//判断下一个结点是否可以进行
			if(judge)
				break;
		    num++;
		}
	  
		if(num >= 8)
		{
			if(temp->count == 1)
			{
				//*flag=0;
				return ERROR;
			}
			else
				DeStack(S);//删除栈(查找数组)的头结点
		}

		if(judge)
		{
			InsertStack(temp,i,j);//将出发点输入到查找数组中 
			AlterMARK(MARK,i,j);//修改标志数组
		}
	}

//*flag=1;
	return OK;
}








///////////////////////////////////
/*           MAZE.h              */
/*                               */
/*   filename:MAZE.h             */
/*   description:MAZE的头文件    */
/*   designer: zhu jian          */
/*   data: 12-10-27              */
/*   QQ:505169307                */
///////////////////////////////////


#ifndef _DATA_STRUCTURE_MAZE_H_
#define _DATA_STRUCTURE_MAZE_H_

#ifndef ERROR
#define ERROR 0	
#endif

#ifndef OK
#define OK 1
#endif

#ifndef NULL
#define NULL 0
#endif


#define Max 30//定义行列数最大值为30

typedef struct{//定义队列的循环结构体
	int data[8][2];
	int front;
}QNode;

typedef struct SqStackNode{//定义查找数组的链式栈结构体
	int data[2];
	struct SqStackNode *next;
}SqStack;

typedef struct{//定义链式栈的头指针
	SqStack *top;
	int count;
}LinkStack;

LinkStack *CreateStack(void);//创建一个链式栈结点

unsigned char InitMOVE(QNode *MOVE);//初始化方向数组MOVE

unsigned char InitStack(LinkStack *S);//初始化链式栈(查找数组)

unsigned char InitMAZE(int p[][Max],int m,int n);//初始化迷宫

unsigned char InitMARK(int p[][Max],int m,int n);//初始化标志数组

unsigned char Display(int S[][Max],int m,int n);//输出二维数组的数据

unsigned char TraQueue(LinkStack *S);//输出栈中（查找数据）的数据

unsigned char AlterMARK(int (*MARK)[Max],int i,int j);//修改标志数组

unsigned char InsertStack(LinkStack *S,int i,int j);//将出发点插入查找链式栈中

unsigned char DeQNode(QNode *MOVE,int *i,int *j);//取方向数组队列的头结点（出队）

unsigned char Judge(int (*MAZE)[Max],int (*MARK)[Max],LinkStack *S,int *i,int *j,int *flag);//判断下一个位置是否可以通过

unsigned char DeStack(LinkStack *S);//删除栈(查找数组)的头结点

unsigned char Index(int (*MAZE)[Max],int (*MARK)[Max],QNode *MOVE,LinkStack *S,int m,int n);//搜索迷宫是否有通路


#endif


网友评论    (发表评论)


发表评论：

评论须知：

  • 1、评论每次加2分，每天上限为30；
  • 2、请文明用语，共同创建干净的技术交流环境；
  • 3、若被发现提交非法信息，评论将会被删除，并且给予扣分处理，严重者给予封号处理；
  • 4、请勿发布广告信息或其他无关评论，否则将会删除评论并扣分，严重者给予封号处理。


扫码下载

加载中，请稍后...

输入口令后可复制整站源码

加载中，请稍后...