标题:迷宫问题 数据结构
只看楼主
Facker摩羯
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2014-12-28
 问题点数:0 回复次数:0 
迷宫问题 数据结构
这程序段在VC++6.0上运行有错,请大神看一下,怎么改
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
//*************参数定义****************
int m,n;                                
int **maze = NULL;        //表示迷宫
struct Element
{            //这里就是定义节点  
    int i;
    int j;
    int di;
};
typedef struct LinkStack
{        //这里就是定义链栈...
    struct Element element;
    struct LinkStack * next;
    struct LinkStack * prior;
}LinkStack;
LinkStack *top = NULL;        //栈顶指针,因为是链栈,所以栈顶指针要是一个指针变量
LinkStack *head = NULL;        //链栈的头指针
int count=0;                            //路径计数
int mgpath(int xi,int yi,int xe,int ye);
//**************迷宫输出函数****************
void printMaze(int ** maze)                //输出迷宫
{
    int i,j;
    printf("您的迷宫图如下所示:\n");
    for(i=0; i<m+2; i++)
    {
        for(j=0; j<n+2; j++)
        {
            printf("%4d",maze[i][j]);
        }
            printf("\n");
    }
        printf("\n******************************\n");
}
void addWall(int ** maze)                //给迷宫加墙
{
    int i,j;
    for(i=0; i<m+2; i++)
    {
        for(j=0; j<n+2; j++) {
            if(i==0){
                maze[i][j] = 1;
            }
            if(i>0 && i<(m+2-1)) {
                maze[i][0]=1;
                maze[i][n+2-1]=1;
                break;
            }
            if(i==m+2-1) {
                maze[i][j]=1;        
            }
        }
    }
}

//********************迷宫初始化函数***********
int ** initMaze()
{                        //对迷宫进行初始化的函数
    int i,j;
    int flag = 0;
    printf("请输入迷宫的行数 m=");
    scanf("%d",&m);
    printf("请输入迷宫的列数 n=");
    scanf("%d",&n);
    maze = (int **)malloc(sizeof(int *) * (m+2));  //开辟迷宫的存储空间
    printf("\n*****************************************\n");
    for(i=0; i<n+2; i++)
    {
        *(maze+i) = (int *)malloc(sizeof(int)*(n+2));      
    }
    addWall(maze);            //给迷宫加墙
    printf("\n请输入迷宫的各行各列(注意:最后一个数需要是0):\n用空格隔开,0代表路,1代表墙\n\n");    //保证出口是路,所以最后一个数要是0
    for(i=1;i<=m;i++) {
            for(j=1;j<=n;j++)
            {
                scanf("%d",&maze[i][j]);
            }
    }
    printf("\n***************************************\n");
printMaze(maze); //输出迷宫图
return maze;
}

//****************递归寻找所有通路函数************

void mazePath()
{
if(top == head && head != NULL)   //终止递归的条件
    {
        return;
    }
    int k = 0;
    int find = 0;
    int i = 0,j=0;
    int di = -1;
    if(top != NULL)di=top->element.di; //di一开始就保存当前栈顶指针所指的节点的方向
    LinkStack *node= (LinkStack *) malloc(sizeof(LinkStack));    //每一次递归都首先开辟节点(因为要查找元素,所以要先开辟节点)
    node->element.di = di;
    if(top == NULL)
    {
        head = (LinkStack *) malloc(sizeof(LinkStack));             //链表的头指针
        head->element.i = 1;
        head->element.j = 0;
        head->element.di = 1;
        head->prior = NULL;
        top = head;
        node->element.i = 1;
        node->element.j = 1;
        node->element.di = -1;
    }
    top->next = node;
    node->next = NULL;
    node->prior = top;
    top = node;             //新开辟节点进栈
    di = top->element.di;//取得当前栈顶指针所指的元素的方向
    while(di<4 && find == 0)
    {
        di++;
        switch(di)
        {
            case 0:    i = top->prior->element.i - 1;j = top->prior->element.j;break;
            case 1:    i = top->prior->element.i;j = top->prior->element.j + 1;break;
            case 2:    i = top->prior->element.i + 1;j = top->prior->element.j;break;
            case 3: i = top->prior->element.i;j = top->prior->element.j - 1;break;
          }
        if(maze[i][j] == 0)find = 1;
    }
    if(i == m && j == n)  
    {
        top->element.i = m;
        top->element.j = n;
        top->prior->element.di = di;
        printf("%4d:",++count);
        LinkStack * n = head->next;
        while(n != NULL)
        {
            printf("(%d,%d,%d )  ",n->element.i,n->element.j,n->element.di);//找到出口,输出路径
            printf(" -> ");
            if((k + 1)%5 == 0)
            {
                printf("\n\t");
            }
            k++;
            n = n->next;
        }
        printf("出口");
        printf("\n");
        maze[top->element.i][top->element.j] = 0;
        top = top->prior; //退栈
        free(node);
        mazePath();
    }
    else
    {
        if(find == 1)
        {
            top->prior->element.di = di;  //退栈时,当找到下一个可走的节点后必须对当前节点的方向进行了更新
            top->element.i = i;
            top->element.j = j;   
            top->element.di = -1;
            maze[i][j] = -1;              //避免重复走到该点
            mazePath();
        }
        else
        {
            maze[top->prior->element.i][top->prior->element.j] = 0;  //让它成为下条路径的可走路径
            top = top->prior->prior;         //退栈   
            free(node);
            mazePath();
        }
    }
   
}

//*******************穷举求解通路函数*********************
int mgpath(int xi,int yi,int xe,int ye)
{    printf("非递归通路:\n");
    int i,j;
    int find;
    int di;
        LinkStack *node= (LinkStack *) malloc(sizeof(LinkStack));
                head = (LinkStack *) malloc(sizeof(LinkStack));             //链表的头指针
                head->element.i = 1;
                 head->element.j = 0;
                head->element.di = 1;
                head->prior = NULL;
                top = head;
                node->element.i = xi;                       //入口节点进栈
                node->element.j = yi;
                node->element.di = -1;
                maze[1][1]=1;                           //进栈后标记为不可走节点
                top->next = node;
                head->next=node;
                node->next = NULL;
                node->prior = top;
                di=    node->element.di;
                top=node;
                LinkStack * n = head->next;

         while(top->prior!= NULL)
        {
            find=0;//find的初始化
            di=top->element.di;
            while(di<4&&find==0)                   //寻找下一个可走节点
            {
                di++;
                switch(di)
                {
                   case 0:i=top->element.i-1;j=top->element.j;break;
                     case 1:i=top->element.i;j=top->element.j+1;break;
                    case 2:i=top->element.i+1;j=top->element.j;break;
                     case 3:i=top->element.i,j=top->element.j-1;break;
 
if(maze[i][j]==0){find=1;top->element.di=di;printf("find找到的点%d,%d,%d",i,j);}  
 //find为1表示为找到下一个可走节点
            }
 if(find==1)                                         
    {
    if(i==xe&&j==ye&&maze[i][j]==0)                //如果找到的节点是出口
        {

        LinkStack *node1= (LinkStack *) malloc(sizeof(LinkStack));    //出口节点入栈
                    top->element.di=di;
                    node1->element.i=i;
                    node1->element.j=j;
                    node1->element.di=-1;
                    top->next=node1;
                     node1->next=NULL;
                     node1->prior=top;
                     top=node1;
                    maze[i][j]=1;
                    printf("     ");
                        while(n!=NULL)                         //输出栈
                        {printf("(%d,%d,%d)",n->element.i,n->element.j,n->element.di);
                            printf("  -> ");
                             n=n->next;
                            }
                        printf("出口");
                        printf("\n");
                        return(0);
                }
                else                                     //如果找到的点不是出口         
                {
                     LinkStack *node1= (LinkStack *) malloc(sizeof(LinkStack));
 //可走节点入栈
                    top->element.di=di;
                    node1->element.i=i;
                    node1->element.j=j;
                    node1->element.di=-1;
                    top->next=node1;
                     node1->next=NULL;
                     node1->prior=top;
                     top=node1;
                    maze[i][j]=1;
    printf("找到的节点有%d,%d,%d",node1->element.i,node1->element.j,node1->element.di);
                    
                }

            }
            else                          //没有下一个可走节点就将该节点退栈
            {
                 maze[top->element.i][top->element.j]=0;
                 top = top->prior;    //退栈  
                 free(top->next);
            }
        }
        return(0);                                             
}
//******************主函数**************************

void main()
 {
    int i;
    initMaze();
    mazePath();
        if(count==0)
        {printf("************");
        printf("\n该迷宫没有通路\n");
        return;
        }
         printf("\n**************************\n");
    mgpath(1,1,m,n);
    if(head != NULL)        //释放内存
    {
        free(head);
    }
    return;
}
搜索更多相关主题的帖子: element include 
2014-12-28 13:29



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-440452-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.120082 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved