用户注册



邮箱：

密码：

用户登录


邮箱：

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

发表随想


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

迷宫

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

[c]代码库

view sourceprint?
//应用线性表解决实际问题。
//问题描述：从一个迷宫的入口到出口找出一条最短路经。用一个二维数组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、请勿发布广告信息或其他无关评论，否则将会删除评论并扣分，严重者给予封号处理。


扫码下载

加载中，请稍后...

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

加载中，请稍后...