stackexercise.h

迷宫.控制台应用程序.适合出学c语言又想提高c语言的朋友

#ifndef STACK_EXERCISES_H
#define STACK_EXERCISES_H

#include "main.h"
#include "iostream"
using namespace std;
//栈中的数据成员
typedef struct
{
	SPos sPos;				//坐标
	int iDirect;			//方向 0:西 1:北　2:东　 3:南
	int iOrder;				//从入口到出口的路径序号
}SStackDataType;
//栈节点
typedef struct SStackNode
{
	SStackDataType stackData;
	SStackNode *pNext;
}SStackNode;
//栈
typedef struct SStack
{
	SStackNode *pTop;
	SStackNode *pBase;
	int iStackSize;				//栈的大小，即占内存空间大小,以元素为单位
}SStack;


//======================================================================= 
//函数名：	StackDataMoving
//参数:              
//返回值：	NULL
//说明：	栈的数据类型对象赋值函数
//======================================================================= 
void StackDataMoving( SStackDataType *pDesData,SStackDataType *pSrdData );

//======================================================================= 
//函数名：	InitStack
//参数:		SStack &stack
//返回值：	true || false
//说明：	初始化栈函数
//			成功返回 true，否则返回 false
//======================================================================= 
bool InitStack( SStack &stack );

//======================================================================= 
//函数名：	DestroyStack
//参数:		SStack &stack
//返回值：	NULL
//说明：	销毁栈函数
//======================================================================= 
void DestroyStack( SStack &stack );

//======================================================================= 
//函数名：	ClearStack
//参数:		SStack &stack
//返回值：	NULL
//说明：	清空栈函数
//======================================================================= 
void ClearStack( SStack &stack );

//======================================================================= 
//函数名：	StackEmpty
//参数:		SStack &stack
//返回值：	true || false
//说明：	判断栈空函数
//			如果栈空返回 true，否则返回 false
//======================================================================= 
bool StackEmpty( SStack &stack );

//======================================================================= 
//函数名：	GetStackLength
//参数:		const SStack &stack
//返回值：	int iStackSize
//说明：	获得栈的元素个数函数
//			返回栈的元素个数,即栈的长度
//======================================================================= 
int GetStackLength( const SStack &stack );

//======================================================================= 
//函数名：	StackDataTop
//参数:		const SStack &stack
//			SStackDataType &stackData
//返回值：	true || false
//说明：	获得栈顶数据函数
//			如果栈不为空返回 true，否则返回 false
//======================================================================= 
bool StackDataTop( const SStack &stack,SStackDataType &stackData );

//======================================================================= 
//函数名：	GetStackTopData
//参数:		const SStack &stack
//返回值：	SStackDataType stackData
//说明：	获得栈中元素个数函数
//			返回栈中元素个数,即栈的长度
//======================================================================= 
bool StackTraverse( SStack &stack, void (*pVisit)() );

//======================================================================= 
//函数名：	Push
//参数:		SStack stack; 
//			SStackDataType stackData
//返回值：	true || false 
//说明：	压栈处理函数
//			成功返回 true，否则返回 false
//======================================================================= 
bool Push( SStack &stack, SStackDataType stackData );


//======================================================================= 
//函数名：	Pop
//参数:		SStack stack; 
//			SStackDataType &stackData	返还它在栈中数据成员
//返回值：	true || false 
//说明：	出栈处理函数
//			成功返回 true，否则返回 false
//======================================================================= 
bool Pop( SStack &stack, SStackDataType &stackData );
 

 
//======================================================================= 
//函数名：	StackTokcatS
//参数:		SStack stack; 
 //返回值：	true || false 
//说明：	将栈内所有元素次序颠倒，构成新的栈。
//======================================================================= 
bool StackTokcatS( SStack &stack );
 
//======================================================================= 
//函数名：	Pass
//参数:		 
//返回值：	true || false 
//说明：	判断当前点是否可以通过
//			成功返回 true，否则返回 false
//======================================================================= 
bool Pass( SMazeMap *pMazeMap,SPos *pCurPos );
 
//======================================================================= 
//函数名：	FootPrint
//参数:		 
//返回值：	NULL
//说明：	留下足迹
//======================================================================= 
void FootPrint( SMazeMap *pMazeMap,SPos *pCurPos );
 
//======================================================================= 
//函数名：	MarkPrint
//参数:		 
//返回值：	NULL
//说明：	标记不能通过
//======================================================================= 
void MarkPrint( SMazeMap *pMazeMap,SPos *pCurPos );
//======================================================================= 
//函数名：	GetNextPos
//参数:		SPos *pCurPos
//			int iDir=DIR_W     //默认方向向西
 //返回值：	true || false 
//说明：	下一个位置
//======================================================================= 
//void NextPos( SMazeMap *pMazeMap,SPos *pCurPos, int iDir=DIR_W );
void NextPos( SPos *pCurPos, int iDir=DIR_W );
 

//======================================================================= 
//函数名：	MazePath
//参数:		SStack &stack					//迷宫路径存放到的位置
//			SMazeMap *pMazeMap				//原始迷宫地图
//			SPos *pStartPos					//迷宫的入口位置
//			SPos *pEndPos					//迷宫的出口位置
//返回值：	true || false
//说明：	迷宫路径 
//			成功返回 true，否则返回 false
//======================================================================= 
bool MazePath(SStack &stack,SMazeMap *pMazeMap );

//======================================================================= 
//函数名：	MazeMapHelp
//参数:		SMazeMap *pMazeMap				//原始迷宫地图
//返回值：	true || false 
//说明：	迷宫路径帮助
//			在给出的原始迷宫地图中标出路径帮助路径，显示出来。
//			用户按下 P/p 键提供路径帮助。
//			成功返回 true，否则返回 false
//======================================================================= 
SStack* MazePathHelp(SMazeMap *pMazeMap );

// StackExercises_20080411_01_0001.cpp : Defines the entry point for the console application.
//

 
//
//cpp
 
bool StackTokcatS( SStack &stack )
{
	if( !StackEmpty( stack ) )
	{
 		SStack *pS1=new SStack;
		SStack *pS2=new SStack;
		SStackDataType stackData;
 		InitStack( *pS1 );
 		InitStack( *pS2 );
		while( !StackEmpty( stack ) )
		{
			Pop( stack, stackData );
			Push( *pS1, stackData );
		}
		while( !StackEmpty( *pS1 ) )
		{
			Pop( *pS1, stackData );
			Push( *pS2, stackData );
		}
		while( !StackEmpty( *pS2 ) )
		{
			Pop( *pS2, stackData );
			Push( stack, stackData );
		}
		DestroyStack( *pS1 );
		DestroyStack( *pS2 );
		return true;
	}
	return false;
}
SStack* MazePathHelp(SMazeMap *pMazeMap )
{
	static SStack stack;
	if( MazePath( stack, pMazeMap ) )
	{
		cout<<"寻找路径成功！"<<endl;
/* 		if( StackTokcatS( stack ) )
		{
			return &stack;
		}*/
	}
	else
	{
		cout<<"寻找路径失败！"<<endl;
	}
	return NULL;
}
void testShowDirect(int iDir)
{
/*	static int iCount=0;
	switch( iDir )
	{
	case 1:
		cout<<"西 " ;
		break;
 	case 2:
		cout<<"北 " ;
		break;
	case 3:
		cout<<"东 " ;
		break;
	case 4:
	case 0:
		cout<<"南 " ;
		break;
	}
	iCount++;
	if( iCount % 20 == 0 )
	{
		iCount=0;
		cout<<endl;
	}*/
}
bool MazePath(SStack &stack,SMazeMap *pMazeMap )
{
	SPos *pStartPos = &pMazeMap->spBegin;
	SPos *pEndPos = &pMazeMap->spEnd;
	InitStack( stack );
 	int iCurStep=1;
//	SPos *pCurPos = pStartPos;
	//??
	SStackDataType stackData;
	stackData.iOrder=1;
	stackData.iDirect=1;
	stackData.sPos.iRow= pStartPos->iRow;
	stackData.sPos.iCol= pStartPos->iCol-1;
  	Push( stack, stackData );
	//
	testShowDirect( stackData.iDirect );
	do
	{ 
		if( Pass( pMazeMap, &stackData.sPos ) )
		{
			iCurStep++;
			FootPrint( pMazeMap, &stackData.sPos );
 			stackData.iDirect = DIR_W;
			stackData.iOrder = iCurStep;
 			Push( stack, stackData );
			//
			testShowDirect( stackData.iDirect );
 			if(  ( stackData.sPos.iRow == pEndPos->iRow ) && \
				( stackData.sPos.iCol == pEndPos->iCol ) )
			{
				pMazeMap->cMazeMap[pEndPos->iRow][pEndPos->iCol]=MAZE_EXIT;
				return true;
			}
			NextPos( &stackData.sPos, DIR_W );
		}// if
		else //当前位置不能通过
		{
			if( !StackEmpty( stack ) )
			{
 				Pop( stack, stackData );
				//
				testShowDirect( (stackData.iDirect+2)%4 );
				iCurStep--;
 				while( stackData.iDirect == 4 && !StackEmpty( stack ) )
				{
					MarkPrint( pMazeMap,&stackData.sPos );
					Pop( stack, stackData );
					//
					testShowDirect( (stackData.iDirect+2)%4 );
					iCurStep--;
				}
				if( stackData.iDirect < 4 )
				{
 					stackData.iDirect++;
					Push( stack, stackData );
					iCurStep++;
					testShowDirect( stackData.iDirect );
					NextPos( &stackData.sPos, stackData.iDirect );
				}//if
			}//if
		}//else
	}while( !StackEmpty( stack ) );
	return false;
}
bool Pass( SMazeMap *pMazeMap,SPos *pCurPos )
{
	if( pMazeMap->cMazeMap[pCurPos->iRow][pCurPos->iCol] != MAZE_BAR && \
		pMazeMap->cMazeMap[pCurPos->iRow][pCurPos->iCol] != MAZE_PASS_PATH )
	{
		if( pMazeMap->cMazeMap[pCurPos->iRow][pCurPos->iCol] != MAZE_DEAD_PATH )
		{
  			return true;
		}
	}
	return false;
	
}
void NextPos( SPos *pCurPos, int iDir )
{
  	switch( iDir )
	{
	case DIR_W:
		pCurPos->iCol--;
		break;
	case DIR_N:
		pCurPos->iRow--;
		break;
	case DIR_E:
		pCurPos->iCol++;
		break;
	case DIR_S:
		pCurPos->iRow++;
		break;
	}
}
void MarkPrint( SMazeMap *pMazeMap,SPos *pCurPos )
{
	pMazeMap->cMazeMap[pCurPos->iRow][pCurPos->iCol] = MAZE_DEAD_PATH;
}
void FootPrint( SMazeMap *pMazeMap,SPos *pCurPos )
{
	pMazeMap->cMazeMap[pCurPos->iRow][pCurPos->iCol] = MAZE_PASS_PATH;
}




void StackDataMoving( SStackDataType *pDesData,SStackDataType *pSrdData )
{
//	pDesData->iNumber = pSrdData->iNumber;
 	pDesData->iDirect = pSrdData->iDirect;
 	pDesData->iOrder = pSrdData->iOrder;
 	pDesData->sPos.iRow = pSrdData->sPos.iRow;
 	pDesData->sPos.iCol = pSrdData->sPos.iCol;
}
bool Pop( SStack &stack, SStackDataType &stackData )
{
	if( !StackEmpty( stack ) )
	{
		SStackNode *pTopNode=stack.pTop;
		StackDataMoving( &stackData, &(stack.pTop->stackData) );
		stack.pTop = stack.pTop->pNext;
		stack.iStackSize -= sizeof(SStackNode);
		delete pTopNode;
		return true;
	}
	return false;
}
bool Push( SStack &stack, SStackDataType stackData )
{
 	SStackNode * pNewNode = new SStackNode;
	if( pNewNode != NULL )
	{
		StackDataMoving(&(pNewNode->stackData), &stackData);
		pNewNode->pNext = stack.pTop;
		stack.pTop = pNewNode;
		stack.iStackSize += sizeof(SStackNode);
		return true;	
	}
	return false;
}
bool StackDataTop( SStack &stack,SStackDataType &stackData )
{
	if( !StackEmpty( stack ) )
	{
	 	StackDataMoving(&stackData, &(stack.pTop->stackData));
		return true;
	}
	return false;
}
int GetStackLength( const SStack &stack )
{
	return stack.iStackSize;
}
bool InitStack( SStack &stack )
{
 	SStackNode * pHeadNode = new SStackNode;
	if( pHeadNode != NULL )
	{
// 		pHeadNode->stackData.iNumber=0;
		pHeadNode->pNext = NULL;
		stack.pTop = pHeadNode;
		stack.pBase = pHeadNode;
		stack.iStackSize = 0;					//忽略头节点所占的内存
		return true;
	}
	return false;
}
void DestroyStack( SStack &stack )
{//不知道对象可不可以直接用　delete 删除
	if( stack.pTop != NULL )
	{
		SStackNode *pCurNode;
		while( !StackEmpty( stack ) )
		{
			pCurNode = stack.pTop->pNext;
			delete stack.pTop;
			stack.pTop = pCurNode;
		}
		stack.iStackSize = 0;
		delete stack.pTop;
		delete stack.pBase;
	}
}
void ClearStack( SStack &stack )
{
	if( stack.pTop != NULL )
	{
		SStackNode *pCurNode;
		while( !StackEmpty( stack ) )
		{
			pCurNode = stack.pTop->pNext;
			delete stack.pTop;
			stack.pTop = pCurNode;
		}
		stack.iStackSize = 0;
	}
}

 bool StackEmpty( SStack &stack )
{
 	if( stack.pTop != stack.pBase )
	{
		return false;
	}
	return true;
}
 
#endif