+Ȧ

我的数据结构课程设计源码

#include<iostream.h>
#define m 6			//行
#define n 8			//列
#define MAXSIZE 100
int maze [m+2][n+2];//迷宫矩阵
typedef struct {
	int x;
	int y;
}item;
item move[8]={0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1};	//试探方向

typedef struct{
	int x,y,d;
}DataType;//栈的元素：行，列，方向
typedef struct{
	DataType data[MAXSIZE];
	int top;
	}SeqStack;	//栈的定义
SeqStack *Init_SeqStack(){
	SeqStack *s;
	s=new SeqStack;
	if(!s){cout<<"空间不足！！"<<endl;return NULL;}
	else {s->top=-1;return s;}
}//初始化
int Empty_SeqStack(SeqStack *s){
	if(s->top==-1)return 1;
	else return 0;
}//空栈判别
void Push_SeqStack(SeqStack *s,DataType x){
	if(s->top==MAXSIZE-1)cout<<"栈已满，不能入栈！"<<endl;
	else{s->top++;s->data[s->top]=x;return ;}
}//入栈
void Pop_SeqStack(SeqStack *s,DataType *x){
	if(Empty_SeqStack(s))cout<<"栈为空栈，不能出栈！"<<endl;
	else{*x=s->data[s->top];s->top--;}
}//出栈
SeqStack* path(int maze[m+2][n+2],item move[8]){
	SeqStack *s;s=Init_SeqStack();
	DataType temp;
	int x,y,d,i,j;
	temp.x=1;
	temp.y=1;
	temp.d=-1;
	Push_SeqStack(s,temp);
	while(!Empty_SeqStack(s))
	{Pop_SeqStack(s,&temp);
	 x=temp.x;
	 y=temp.y;
	 d=temp.d+1;
	 while(d<8)
	 {i=x+move[d].x;
	  j=y+move[d].y;
		if(maze[i][j]==0)
		{
		  temp.x=x;temp.y=y;temp.d=d;
		  Push_SeqStack(s,temp);
		  x=i;y=j;
		  maze[x][y]=-1;
		  if(x==m&&y==n)return s;
			else d=0;
		}
		else d++;
	 }
	}
	return NULL;
}
void main()
{ for(int i=0;i<m+2;i++)
	 for(int j=0;j<n+2;j++)
		 maze[i][j]=1;
	 cout<<"请输入迷宫矩阵中0的位置：（如果输入的数值超出了迷宫的范围，表示输入完毕!）"<<endl;
	 int e,f;cin>>e>>f;
	 while(e>0&&e<=m&&f>0&&f<=n){maze[e][f]=0;cin>>e>>f;}	 
	SeqStack* s;
	s=path(maze,move);
	if(!s)cout<<"走出迷宫没有路径！"<<endl;
		else
		{cout<<"走出迷宫的路径为："<<endl;
		DataType temp;
		SeqStack* t;t=Init_SeqStack();
		while(!Empty_SeqStack(s)){Pop_SeqStack(s,&temp);Push_SeqStack(t,temp);}
		while(!Empty_SeqStack(t)){Pop_SeqStack(t,&temp);cout<<temp.x<<","<<temp.y<<","<<temp.d<<endl;}
		}
}