c 언어 데이터 구조의 미로

현재 인터넷 상에 서 미로 에 대한 해답 은 버 전이 셀 수 없 이 많다.본인 의 흰 둥 이 는 미로 에 대한 자신의 구 해 라 는 작은 항목 을 붙 이 고 자신 이 쓴 것 입 니 다.같은 어려움 을 겪 고 있 는 사람들 을 도 울 수 있 기 를 바 랍 니 다. 왜냐하면 저 는 한참 동안 어려움 을 겪 었 기 때 문 입 니 다......................................
먼저, 미궁 에 대한 해답 을 표시 하고, 먼저 저 는 자신의 생각 을 제시 하고, '궁 거 해답' 의 방법 (엄 울 민 선생님 의 데이터 구조 라 는 책 에서 언급 한 바 와 같이 처음에는 방법 과 이름 을 몰 랐 습 니 다.) 사실은 간단하게 말 하면 하나의 길, 하나의 길 을 시험 해 보 는 것 입 니 다. 물론 마음대로 해 서 는 안 됩 니 다. 제 방법 은 입구 에서 출발 하여 한 방향 으로 앞으로 탐색 하 는 것 입 니 다.통 하면 계속 앞으로 간다.그렇지 않 으 면 표 시 를 남기 고 원래 의 길 로 되 돌아 가 모든 길이 끝 날 때 까지 계속 탐색 한다.아니면 창고 의 선진 적 인 구조 로 일 로 를 보존 하 는 노선 입 니까?코드 는 스 택 의 순 서 를 사용 하여 배열 형식의 구 조 를 실현 합 니 다 (스 택 에 대해 상세 하 게 설명 하지 않 았 습 니 다).

//     
#ifndef AFXSTD_H
#define AFXSTD_H   

#include
#include
#include
#include
using namespace std;   
// cout; cin;C++     
#endif

//         
#ifndef MAZE_H
#define MAZE_H

#define ROWSIZE 10        //    
#define COLSIZE 10
#define Reachable   0    //       
#define Bar         1    //   
#define Foot        2    //  
#define Mark        3    //      
typedef int MapType[ROWSIZE][COLSIZE]; //      

typedef struct 
{
	int row;// x
	int col;// y;
}PosType;                   //     

typedef struct
{
	int ord;            //          
	PosType seat;      //    
	int di; //    // 1 2 3 4
}MElemType;      //        

typedef MElemType SElemType; //  stack   



bool MazePass(MapType maze,PosType curpos);
void FootPrint(MapType maze,PosType curpos);      //    
PosType NextPos(PosType curpos,int di);             //     
void MarkPrint(MapType maze,PosType curpos);         //       
bool MazePath(MapType maze,PosType start,PosType end);    //      
void PrintMap(MapType maze);                           //    


#endif

//     
#include"Maze.h"
#ifndef SEQSTACK_H
#define SEQSTACK_H
#define STACKSIZE 100

//typedef int SElemType;

struct SeqStack
{
	SElemType *data;
	int maxsize;
	int top;
};

void Init_Stack(SeqStack &st);
void Destroy_Stack(SeqStack &st);
void Stack_Clear(SeqStack &st);
bool Stack_Empty(SeqStack &st);
bool Stack_Full(SeqStack &st);
int Stack_Size(SeqStack &st);
bool Stack_Push(SeqStack &st,const SElemType &x);
bool Stack_Pop(SeqStack &st, SElemType &x);

SElemType GetTop(SeqStack &st);
void Pop(SeqStack &st);

#endif

이상 은 헤더 파일 의 생 성과 구조 체 의 생 성 입 니 다. 지금 은 구조 체 의 중요성 을 깊이 느끼 고 있 습 니 다.구조 체 를 잘 만 들 지 못 하 는 것 은 자신 에 게 구 덩이 를 파 는 것 입 니 다. 명심 하 세 요!!
지금 함수 코드 를 붙 여 놓 으 세 요. 설명 은 최선 을 다 해 쓰 겠 습 니 다.(창고 의 문 제 는 제 가 나중에 다시 자세하게 논술 하 겠 습 니 다. 이번 의 중점 은 미궁의 해답 에 있 기 때문에 창고 의 상세 한 코드 를 직접 붙 이 고 양 해 를 바 랍 니 다.)

//         
#include"AfxStd.h"
#include"Stack.h"

bool Stack_Resize(SeqStack &st)
{
	SElemType *s = (SElemType*)malloc(sizeof(SElemType)*st.maxsize * 2);
	if(NULL == s) return false;
	for(int i = 0;i<= st.top;++i)
	{
		s[i] = st.data[i];
	}
	free(st.data);
	st.data = s;
	st.maxsize = st.maxsize * 2;
	return true;
}
void Init_Stack(SeqStack &st)
{
	st.maxsize = STACKSIZE;
	st.top = -1;
	st.data = (SElemType*)malloc(sizeof(SElemType)*st.maxsize);
	if(NULL == st.data)
	{
		exit(0);
	}
}
void Destroy_Stack(SeqStack &st)
{
	free(st.data);
	st.data = NULL;
	st.maxsize = 0;
	st.top = -1;
}

void Stack_Clear(SeqStack &st)
{
	st.top = -1;
}
bool Stack_Empty(SeqStack &st)
{
	return Stack_Size(st) == 0;
}
bool Stack_Full(SeqStack &st)
{
	return Stack_Size(st) == st.maxsize;
}

int Stack_Size(SeqStack &st)
{
	return st.top + 1;
}

bool Stack_Push(SeqStack &st,const SElemType &x)
{
	if(Stack_Full(st) && ! Stack_Resize(st))
	{
		return false;
	}
	st.data[++st.top] = x;
	return true;
}
bool Stack_Pop(SeqStack &st, SElemType &x)
{
	if(Stack_Empty(st))
	{
		return false;
	}
	x = st.data[st.top--];
	return true;
}

//          
#include"AfxStd.h"
#include"Maze.h"
#include"Stack.h"


/////////////////////////////////////////////////

bool MazePass(MapType maze,PosType curpos)   //        
{
	return maze[curpos.row][curpos.col] == Reachable;    //           
}
void FootPrint(MapType maze,PosType curpos)       //        
{
	maze[curpos.row][curpos.col] = Foot;        
}
PosType NextPos(PosType curpos,int di)              //           
{
	switch(di)
	{
	case 1: curpos.row+=1; break;// 1
	case 2: curpos.col-=1; break;// 2
	case 3: curpos.row-=1; break;// 3
	case 4: curpos.col+=1; break;// 4
	}
	return curpos;
}
void MarkPrint(MapType maze,PosType curpos)         //                
{
	maze[curpos.row][curpos.col] = Mark;
}

bool MazePath(MapType maze,PosType start,PosType end)//（  ）    
{
	bool res = false;                           //    res      
	PosType curpos = start;                    //         
	int curstep = 1;                              //        1
	SeqStack st;                                     //     
	MElemType e;                                     //      
	Init_Stack(st);                                   //    
	do{
		if(MazePass(maze,curpos))                 //       ，          
		{
			FootPrint(maze,curpos);               //    
			e.di = 1, e.seat = curpos,e.ord = curstep++;
			Stack_Push(st,e);                       //     
			if(curpos.row == end.row && curpos.col == end.col)
			{
				res = true;
				break;
			}                             //    
			curpos = NextPos(curpos,1);      //      
		}
		else
		{
			if(!Stack_Empty(st))              //        
			{
				Stack_Pop(st,e);
				while(e.di == 4 && !Stack_Empty(st))
				{
					MarkPrint(maze,e.seat);        
					Stack_Pop(st,e);             //          ，     
				}
				if(e.di < 4)
				{
					e.di+=1;                  //         
					Stack_Push(st,e);            //      
					curpos = NextPos(e.seat,e.di);   //              
				}
			}
		}
	}while(!Stack_Empty(st));      //      ，      
	Destroy_Stack(st);             
	return res;
}
void PrintMap(MapType maze)         //    
{
	for(int i = 0;i

미로 에 대한 상세 한 설명 입 니 다. 도움 이 되 셨 으 면 좋 겠 습 니 다.뒤에 내 테스트 파일 을 추가 합 니 다.

#include"AfxStd.h"
#include"Maze.h"

int main()
{
	MapType maze ={                        //        
		{1,1,1,1,1,1,1,1,1,1},
		{1,0,1,1,1,1,1,1,1,1},
		{1,0,0,0,0,0,0,0,0,1},
		{1,0,0,0,1,1,1,1,0,1},
		{1,0,0,0,1,1,1,1,0,1},
		{1,0,1,1,1,1,0,0,0,1},
		{1,0,1,1,1,1,1,1,1,1},
		{1,0,0,0,0,0,0,1,1,1},
		{1,0,1,1,1,1,0,0,0,1},
		{1,1,1,1,1,1,1,1,1,1},
	};
	PosType start={1,1},end={8,8};
	PrintMap(maze);                     //      
	MazePath(maze,start,end);
	PrintMap(maze);                      //      
	return 0;
}