stack.h

数据结构中栈算法的简单应用,通过程序模拟迷宫的生成和寻找出口的动态演示过程

typedef struct Node
{
   Point point1;
   Point point2;
   int isinWay;
   int isthrough;
   int di;
   struct Node *Next;
}Node,*LinkList;

LinkList Stack;Node SavePop;
Rect inst;
int /*w=0,*/h=2;

bool IsEqual(Rect rect1,Rect rect2)
{
    if(rect1.point1.x==rect2.point1.x&&rect1.point1.y==rect2.point1.y&&rect1.point2.x==rect2.point2.x&&rect1.point2.y==rect2.point2.y)
	return true;
	else return false;
}

void Push(LinkList S,Rect rect[][10]);
bool Pop(LinkList S);

bool StackEmpty(LinkList S)
{
   if(S->Next==NULL)
	   return true;
   else return false;
}

int k=1,l=1;
bool Pass(Rect rect[10][10])
{
   if(inst.di==0)
   {
      l++;
	  if(rect[k][l].isthrough==1&&rect[k][l].isinway==0)
	  {
		  Push(Stack,rect);
		  inst=rect[k][l];
		  return true;
	  }
	  else
	  {
		  inst.di++;
		  l--;
	  }
   }
   if(inst.di==1)
   {
      k++;
	  if(rect[k][l].isthrough==1&&rect[k][l].isinway==0)
	  {
		  Push(Stack,rect);
		  inst=rect[k][l];
		  return true;
	  }
	  else
	  {
		  inst.di++;
		  k--;
	  }
   }
   if(inst.di==2)
   {
      l--;
	  if(rect[k][l].isthrough==1&&rect[k][l].isinway==0)
	  {
		  Push(Stack,rect);
		  inst=rect[k][l];
		  return true;
	  }
	  else
	  {
		  inst.di++;
		  l++;
	  }
   }
   if(inst.di==3)
   {
      k--;
	  if(rect[k][l].isthrough==1&&rect[k][l].isinway==0)
	  {
		  Push(Stack,rect);
		  inst=rect[k][l];
		  return true;
	  }
	  else
	  {
		  inst.di++;
		  k++;
	  }
   }
   return false;
}

void InitList(LinkList *L)
{
  *L=(Node *)malloc(sizeof(Node));
  (*L)->Next=NULL;
}

bool Constract(CDC * pdc, Rect rect[10][10])
{
	Rect EndEx=rect[8][8];
	InitList(&Stack);
	memset(&inst, 0, sizeof(inst));
	k=1;
	l=1;
	Push(Stack,rect);
	inst = rect[1][1];
	
	do
	{
		if(Pass(rect))
		{
			Sleep(500);
			::MessageBeep(MB_OK);
			CBrush bru(RGB(0,255,0));
			CBrush * brold = (CBrush*)pdc->SelectObject(&bru);
			pdc->RoundRect(inst.point1.x+5,inst.point1.y+5,inst.point2.x-5,inst.point2.y-5,5,5);
			pdc->SelectObject(&brold);
		  
			if(IsEqual(inst,EndEx))
				break;
//			  return true;
		}
		else
		{
			CBrush bru(RGB(255,0,0));
			CBrush * brold = (CBrush*)pdc->SelectObject(&bru);
			Sleep(500);
			::MessageBeep(MB_ICONQUESTION);
			pdc->RoundRect(inst.point1.x+5,inst.point1.y+5,inst.point2.x-5,inst.point2.y-5,5,5);
			pdc->SelectObject(&brold);

			if (!Pop(Stack))//出栈
				break;
		 
			inst.di=SavePop.di;
			if(inst.di==0)
				l--;
			else if(inst.di==1)
				k--;
			else if(inst.di==2)
				l++;
			else if(inst.di==3)
				k++;
			inst.isinway=SavePop.isinWay;
			inst.isthrough=SavePop.isthrough;
			inst.point1=SavePop.point1;
			inst.point2=SavePop.point2;
		} 
	}while(!StackEmpty(Stack));
	free(Stack);

	if ((k == 8) && (l == 8))
		return true;
	else
		return false;
}

void Push(LinkList S,Rect rect[][10])
{
    LinkList temp;
	inst.isinway=1;
	temp=(LinkList)malloc(sizeof(Node));
	temp->di=inst.di;
	temp->isinWay=inst.isinway;
	temp->isthrough=inst.isthrough;
	temp->point1=inst.point1;
	temp->point2=inst.point2;
	temp->Next=S->Next;
	S->Next=temp;
	
	rect[k][l].isinway=1;
}

bool Pop(LinkList S)
{
	LinkList temp;
	temp=S->Next;
	if (temp != NULL)
	{
		S->Next=temp->Next;
		SavePop.di=temp->di;
		SavePop.isinWay=temp->isinWay;
		SavePop.isthrough=temp->isthrough;
		SavePop.point1=temp->point1;
		SavePop.point2=temp->point2;

		free(temp);
		return true;
	}
		return false;
}