迷宫问题_数据结构C++课程设计_带报告

数据结构的课程设计，迷宫问题，用C++实现的，附带报告

#include 
#include 
#define M 8
#define N 11
typedef struct{
	int xyd;
}DataType;//堆栈数据域
struct SeqStack
{
 int MAXNUM;//栈的最大长度
 int t;//栈顶指针
 DataType *s;//基指针
 };
typedef struct SeqStack *PSeqStack;
int isEmptyStack_seq（PSeqStack pastack）//判断栈是否为空
{
	return（pastack->t==-1）;//t为栈顶
}
PSeqStack creatEmptyStack_seq（int m）//建立空栈
{
    PSeqStack pastack = （PSeqStack）malloc（sizeof（struct SeqStack））;
	//开辟SeqStack的长度的地址空间，并返回这段空间的首地址
  	if （pastack!=NULL）{
     pastack->s = （DataType*）malloc（sizeof（DataType）*m）;//如果不为空，开辟m长度空间给*S
 	 if （pastack->s）{
       pastack->MAXNUM=m;
       pastack ->t = -1;
       return （pastack）;
      }//开辟成功，则MAXNUM等于m，栈顶元素为空
   	else free （pastack）;
    }
    printf（“Out of space!!\n“）;
    return NULL;
}
void  push_seq（ PSeqStack pastack DataType x ）
/* 在栈中压入一元素x */
{  if（ pastack->t >= pastack->MAXNUM - 1  ）
      printf（ “Overflow! \n“ ）;
  else
	{  pastack->t = pastack->t + 1;//栈顶长度增1
	   pastack->s[pastack->t] = x;
	 }
}

void  pop_seq（ PSeqStack pastack ）
/* 删除栈顶元素 */
{  	if （pastack->t == -1 ）
	printf（ “Underflow!\n“ ）;
    else
	pastack->t = pastack->t - 1;
	}
DataType  top_seq（ PSeqStack pastack ）
/* 当pastack所指的栈不为空栈时，求栈顶元素的值 */
{ 	if （pastack->t == -1 ）
	printf（ “It is empty!\n“ ）;
    else
    return （pastack->s[pastack->t]）;
}

void mazePath（int *maze[]int *direction[]int x1int y1int x2int y2）
/* 迷宫maze[M][N]中求从入口maze[x1][y1]到出口maze[x2][y2]的一条路径 */
/* 其中 1<=x1x2<=M-2  1<=y1y2<=N-2 */
{ int ijk; 
int gh;
PSeqStack  st;
DataType element;
st=creatEmptyStack_seq（M*N）;
maze[x1][y1] = 2;  							/* 从入口开始进入作标记 */
element.x = x1;	  
element.y = y1;
element.d = -1;
push_seq（stelement）;   						/* 入口点进栈 */
while （! isEmptyStack_seq（st））   				/* 走不通时一步步回退 */
{
	element = top_seq（st）;
    pop_seq（st）;
    i = element.x;
    j = element.y;
    k = element.d + 1;
    while （k<=3）  							/* 依次试探每个方向 */
	{ 
		g = i + direction[k][0];
        h = j + direction[k][1];
        if （g==x2 && h==y2 && maze[g][h]==0）  	/* 走到出口点 */
		{ element.x = i;	  
	      element.y = j;
          element.d = k;
		  push_seq（stelement）;
		  element.x = g;	  
	      element.y = h;
          element.d = k;
          push_seq（stelement）;
		  printf（“The revers path is:\n“）;   			/* 打印路径上的每一点 */
            while（!isEmptyStack_seq（st））
			{
              element=top_seq（st）;
              pop_seq（st）;
             printf（“the node is: %d %d \n“element.xelement.y）;
			}
            return;
		}
        if （maze[g][h]==0） 					/* 走到没走过的点 */
		{ maze[g][h] = 2;   					/* 作标记 */
          element.x = i;	  
	      element.y = j;
          element.d = k;
          push_seq（stelement）;  				/* 进栈 */
          i = g;     							/* 下一点转换成当前点 */
          j = h;
          k = -1;
		}	   
      k = k + 1;
	}
}
printf（“The path has not been found.\n“）; 	/* 栈退完未找到路径 */
}
void main（）
{
	int maze[M][N]={
	

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2014-03-25 21:15  数据结构_迷宫问题\
     文件       84992  2014-03-25 21:15  数据结构_迷宫问题\课程设计报告.doc
     目录           0  2014-03-25 21:14  数据结构_迷宫问题\迷宫问题\
     目录           0  2014-03-25 21:14  数据结构_迷宫问题\迷宫问题\Debug\
     文件       50176  2011-06-21 21:14  数据结构_迷宫问题\迷宫问题\Debug\vc60.idb
     文件       53248  2010-07-05 16:03  数据结构_迷宫问题\迷宫问题\Debug\vc60.pdb
     文件      176217  2010-07-05 16:05  数据结构_迷宫问题\迷宫问题\Debug\迷宫问题.exe
     文件      176636  2010-07-05 16:05  数据结构_迷宫问题\迷宫问题\Debug\迷宫问题.ilk
     文件        9545  2010-07-05 16:05  数据结构_迷宫问题\迷宫问题\Debug\迷宫问题.obj
     文件      220224  2010-07-05 10:42  数据结构_迷宫问题\迷宫问题\Debug\迷宫问题.pch
     文件      427008  2010-07-05 16:03  数据结构_迷宫问题\迷宫问题\Debug\迷宫问题.pdb
     文件        3662  2010-07-05 16:03  数据结构_迷宫问题\迷宫问题\迷宫问题.cpp
     文件        3427  2010-07-05 14:58  数据结构_迷宫问题\迷宫问题\迷宫问题.dsp
     文件         524  2010-07-05 16:09  数据结构_迷宫问题\迷宫问题\迷宫问题.dsw
     文件       58368  2011-06-21 21:14  数据结构_迷宫问题\迷宫问题\迷宫问题.ncb
     文件       48640  2011-06-21 21:14  数据结构_迷宫问题\迷宫问题\迷宫问题.opt
     文件         762  2010-07-05 16:05  数据结构_迷宫问题\迷宫问题\迷宫问题.plg