数据结构迷宫算法源码+实验报告

c++实现的走迷宫算法，实验报告中对算法做了详细说明。

#include
#include
#include
#define MAXSIZE 100
using namespace std;
int sign[MAXSIZE][MAXSIZE];//标记矩阵，当相应块走过后，值变为1
typedef struct
{
	int x;
	int y;
}PosType;

typedef struct
{
	int ord;
    PosType seat;
	int di;
}SElemType;

typedef struct
{
	int m;
	int n;
	int map[MAXSIZE][MAXSIZE];
}MazeType;

class Stack
{
public:
	SElemType data[MAXSIZE];
	int top;
	Stack（void）
	{
		top=-1;
	}
	void push（SElemType e）
	{
		top++;
		data[top].ord=e.ord;
		data[top].di=e.di;
		data[top].seat=e.seat;
	}
	void pop（SElemType &e）
	{
		e.di=data[top].di;
		e.ord=data[top].ord;
		e.seat=data[top].seat;
		top--;
	}
	int empty（）
	{
		if（top==-1）
			return 1;
		else
			return 0;
	}

};

void FootPrint（PosType ps）
{
	sign[ps.x][ps.y]=1;
}

int Pass（MazeType mazemapPosType ps）
{
	if（mazemap.map[ps.x][ps.y]==0&&sign[ps.x][ps.y]==0）
		return 1;
	else 
		return 0;
}

PosType NextPos（PosType psint di）
{
	PosType temp;
	switch（di）
	{
	case 1:
		temp.x=ps.x+1;
		temp.y=ps.y;
		break;
	case 2:
		temp.x=ps.x;
		temp.y=ps.y-1;
		break;
	case 3:
		temp.x=ps.x-1;
		temp.y=ps.y;
		break;
	case 4:
		temp.x=ps.x;
		temp.y=ps.y+1;
		break;
	}
	return temp;
}
int MazePath（MazeType  &mazemapPosType startPosType end）
{
	Stack st;
	SElemType e;
	PosType curpos=start;
	int curstep=1;
	for（int i=0;i		for（int j=0;j			sign[i][j]=0;
	do
	{
		if（Pass（mazemapcurpos））
		{
			FootPrint（curpos）;
			e.ord=curstep;
			e.seat=curpos;
			e.di=1;
			st.push（e）;
			if（curpos.x==end.x&&curpos.y==end.y）
			{
				for（int i=0;i<=st.top;i++）
				{
					mazemap.map[st.data[i].seat.x][st.data[i].seat.y]=3;
				//	cout<<“（“<				}
				return 1;
			}
			curpos=NextPos（curpos1）;
			curstep++;
		}
		else
		{
			if（!st.empty（））
			{
				st.pop（e）;
				while（e.di==4&&!st.empty（））
				{
					FootPrint（e.seat）;
					st.pop（e）;
				}
				if（e.di<4）
				{
					e.di++;
					st.push（e）;
	//				cout<<“（“<<（e.seat）.x<<““<<（e.seat）.y<<“）“<					curpos=NextPos（e.seate.di）;
				}
			}
		}

	}while（!st.empty（））;
	return 0;
}

void printmaze（MazeType mazemapPosType startPosType end）
{
	for（int i=0;i	{
		cout<<“\t\t“;
		for（int j=0;j		{			
			if（1==mazemap.map[i][j]）
				cout<<“墙“;
			else if（i==start.x&&j==start.y）
				cout<<“口“;
			else if（i==end.x&&j==end.y）
				cout<<“口“;
			else if（3==mazemap.map[i][j]）
				cout<<“口“;
			else 
				cout<<“  “;
		}
		cout<	}
}

void usermaze（）
{
	MazeType usermap;
	PosType m_startm_end;
	cout<<“输入迷宫宽度:“<	cin>>usermap.n;
	cout<<“输入迷宫高度:“<	cin>>usermap.m;	
	for（int i=0;i	{
		cout<<“输入第“<		for（int j=0;j		{
			cin>>usermap.map[i][j];
		}
	}
	cout<<“输入迷宫入口横坐标:“<	cin>>m_start

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       6056  2008-12-31 15:04  数据结构作业\maze.cpp

     文件     160768  2009-01-02 18:21  数据结构作业\实习报告.doc

     目录          0  2008-12-31 16:27  数据结构作业

     文件     565327  2008-12-31 15:04  数据结构作业\maze.exe

----------- ---------  ---------- -----  ----

               732151                    4