顺序表之迷宫问题（C实现）

朱雀 2022-08-14 04:55 107阅读 0赞

迷宫图

![20151122132048831][]

data.h

#ifndef _DATA_H
    #define _DATA_H
    
    typedef struct
    {
    	int y;
    	int x;
    }POS;
    
    typedef struct
    {
    	int sno;
    	POS seat;
    	int di;
    }ElemType;
    
    #endif

stack.h

#ifndef _STACK_H
    #define _STACK_H
    
    #include "data.h"
    
    #define STACK_INIT_SIZE 10
    #define STACK_INCREME	10
    
    typedef struct
    {
    	ElemType * base;
    	ElemType *top;
    	int size;
    }STACK;
    
    STACK * InitStack();
    
    void DestroyStack(STACK *s);
    
    int Push(STACK *s,ElemType *e);
    
    int Pop(STACK *s,ElemType *e);
    
    int IsEmpty(STACK *s);
    
    #endif

stack.c

#include "stack.h"
    #include <stdio.h>
    #include <stdlib.h>
    
    STACK * InitStack()
    {
    	STACK * s = (STACK *)malloc(sizeof(STACK));
    	if(s == NULL)
    		exit(0);
    	s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    	if(s->base == NULL) exit(0);
    	s->top = s->base;
    	s->size = STACK_INIT_SIZE;
    	return s;
    }
    
    void DestroyStack(STACK *s)
    {
    	free(s->base);
    	free(s);
    }
    
    int Push(STACK *s,ElemType *e)
    {
    	if(s == NULL || e == NULL)
    		return 0;
    	if(s->top - s->base >= s->size)
    	{
    		s->base = (ElemType *)realloc(s->base,
    			(s->size + STACK_INCREME) *sizeof(ElemType));
    		if(s->base == NULL)
    			return 0;
    		s->top = s->base + s->size;
    		s->size = s->size + STACK_INCREME;
    	}
    //	*s->top = *e;
    //	s->top ++;
    	*s->top++ = *e;
    	return 1;
    }
    
    int Pop(STACK *s,ElemType *e)
    {
    	if(s == NULL || e == NULL)
    		return 0;
    	if(s->base == s->top) return 0;
    	*e = *--s->top;
    	return 1;
    }
    
    int IsEmpty(STACK *s)
    {
    	return s->top == s->base ? 1 : 0;
    }

main.c

#include "stack.h"
    #include <stdio.h>
    #include <conio.h>
    #include <stdlib.h>
    
    int item[10][10]={
    	{1,1,1,1,1,1,1,1,1,1},	
    	{1,0,0,1,0,0,0,1,0,1},	
    	{1,0,0,1,0,0,0,1,0,1},	
    	{1,0,0,0,0,1,1,0,0,1},	
    	{1,0,1,1,1,0,0,0,0,1},	
    	{1,0,0,0,1,0,0,0,0,1},	
    	{1,0,1,0,0,0,1,0,0,1},	
    	{1,0,1,1,1,0,1,1,0,1},	
    	{1,1,0,0,0,0,0,0,0,1},	
    	{1,1,1,1,1,1,1,1,1,1}};
    static const POS inPos = {1,1},outPos = {8,8};
    
    int IsPass(POS curP)
    {
    	return item[curP.y][curP.x] == 0 ? 1 : 0;
    }
    
    POS NextPos(POS curP,int di)//0,1,2,3
    {
    	POS p = curP;
    	switch(di)
    	{
    	case 0:
    		p.x --;
    		break;
    	case 1:
    		p.y++;
    		break;
    	case 2:
    		p.x++;
    		break;
    	case 3:
    		p.y--;
    	}
    	return p;
    }
    
    void PrintItem(POS curP)
    {
    	int i,j;
    	system("cls");
    	for(i=0;i<10;i++)
    	{
    		for(j=0;j<10;j++)
    		{
    			if(i == curP.y && j== curP.x)
    			{
    				printf("@");
    				continue;
    			}
    			if(item[i][j] == 1)
    				printf("*");
    			else
    				printf(" ");
    		}
    		printf("\n");
    	}
    }
    
    void main()
    {
    	ElemType e;
    	int setp = 1;
    	POS curPos = inPos;
    	STACK *s = InitStack();
    
    	PrintItem(inPos);
    	getch();
    	do
    	{
    		if(IsPass(curPos))
    		{
    			e.sno = setp;
    			e.di = 0;
    			e.seat = curPos;
    			Push(s,&e);
    			item[curPos.y][curPos.x] = 2;
    			if(curPos.y == outPos.y && curPos.x == outPos.x)
    			{
    				printf("OK");
    				break;
    			}
    			PrintItem(curPos);
    			getch();
    			curPos = NextPos(curPos,0);
    			setp++;
    			
    		}else
    		{
    			Pop(s,&e);
    			while(e.di == 4 && !IsEmpty(s))
    			{
    				item[curPos.y][curPos.x] = 3;
    				Pop(s,&e);
    			}
    			if(e.di < 3)
    			{
    				e.di++;
    				Push(s,&e);
    				curPos = NextPos(e.seat,e.di);
    			}
    		}
    	} while(!IsEmpty(s));
    }

VC6运行效果图

初始状态图

![20151122132436610][]

寻找出口过程图

![20151122132440374][]

找到出口图

![20151122132444942][]

\*该程序按任意键就会移动寻找出口的那个物体

[20151122132048831]: /images/20220731/05935cd1a2554816a14db71aebd493d0.png
[20151122132436610]: /images/20220731/ee464a9d10be4adcb3ca5ea76a9a03f9.png
[20151122132440374]: /images/20220731/ac19868521514af182a9b358ed9c8bbf.png
[20151122132444942]: /images/20220731/48778f754f2440838cf7dbe811c896bb.png