观数据结构写代码（13）栈的应用（四） 迷宫求解

看数据结构写代码（13）栈的应用（四） 迷宫求解

这是一个 用 穷举法 解 迷宫问题 的一个示例，但在 效率 和 解的 最短路径上 就稍显不足了。

这 两个问题，留在 以后 空闲 时刻 解答。

欢迎指出代码不足

下面上代码：

// Maze.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <stdlib.h>

struct Postion
{
	int x;
	int y;
};

typedef int Direction;


struct ElementType
{
	Postion pos;
	Direction direction; 
};


enum E_State
{
	E_State_Error = 0,
	E_State_Ok = 1,
};
//链表节点node
struct lStackNode
{
	ElementType data;
	lStackNode * next;
};

//链栈
struct linkStack
{
	lStackNode * bottom;
	lStackNode * top;
	int len;
};


lStackNode * makeNode(ElementType data){
	lStackNode * pNode = (lStackNode *)malloc(sizeof(lStackNode));
	if (pNode != NULL)
	{
		pNode->data = data;
		pNode->next = NULL;
	}
	return pNode;
}

E_State stackInit(linkStack * lStack){
	//分配头节点
	lStackNode * pNode = (lStackNode *) malloc(sizeof(lStackNode));
	if (pNode == NULL)
	{
		return E_State_Error;
	}
	pNode->next = NULL;
	//栈顶和栈底指向同一个节点时为空.
	lStack->bottom = lStack->top = pNode;
	lStack->len = 0;
	return E_State_Ok;
}

void stackClear(linkStack * stack){
	lStackNode * next = stack->bottom->next;
	while (next != NULL)
	{
		lStackNode * freeNode = next;
		/*又粗心了。。。
		free(freeNode);
		next = next->next;*/
		next = next->next;
		free(freeNode);
	}
	stack->top = stack->bottom;
	//忘记 了
	//错误
	stack->bottom->next = NULL;
	stack->len = 0;
}

void stackDestory(linkStack * stack){
	stackClear(stack);
	free(stack->top);
	stack->top = stack->bottom = NULL;
}

E_State stackGetTop(linkStack stack,ElementType * topData){
	//链表的栈顶 指向 栈顶元素
	if (stack.top != stack.bottom)
	{
		*topData = stack.top->data;
		return E_State_Ok;
	}
	else
	{
		return E_State_Error;
	}
}

int stackLen(linkStack stack){
	return stack.len;
}

bool stackEmpty(linkStack stack){
	return stack.top == stack.bottom ? true : false;
}

E_State stackPush(linkStack * stack,ElementType data){
	lStackNode * node = makeNode(data);
	if (node != NULL)
	{
		stack->top->next = node;
		stack->top = node;
		stack->len++;
	}
	else{
		return E_State_Error;
	}
}

E_State stackPop(linkStack * stack,ElementType * data){
	if (stack->top != stack->bottom)
	{
		//首先指向第一个元素.
		lStackNode * next = stack->bottom;
		*data = stack->top->data;
		//找到栈顶元素的前驱
		while (next->next != stack->top)
		{
			next = next->next;
		}
		free(stack->top);
		next->next = NULL;
		stack->top = next;
		//忘记加了
		stack->len--;
		return E_State_Ok;
	}
	else{
		return E_State_Error;
	}
}

int mazeData[10][10] = {
	{0,0,0,0,0,0,0,0,0,0},
	{0,1,1,0,1,1,1,0,1,0},
	{0,1,1,0,1,1,1,0,1,0},
	{0,1,1,1,1,0,0,1,1,0},
	{0,1,0,0,0,1,1,1,1,0},
	{0,1,1,1,0,1,1,1,1,0},
	{0,1,0,1,1,1,0,1,1,0},
	{0,1,0,0,0,1,0,0,1,0},
	{0,0,1,1,1,1,1,1,1,0},
	{0,0,0,0,0,0,0,0,0,0},
};

//pos坐标的节点 是否 可通过
bool isPass(Postion pos){
	int pass = mazeData[pos.x][pos.y];
	//节点不是障碍物，并且 是没有通过的节点
	return pass == 1 ? true : false;
}

//获取下一个坐标
Postion getNextPos(Postion pos,Direction di){
	int addArray[][2] = {{0,1},{1,0},{0,-1},{-1,0}};
	Postion nextPos;
	nextPos.x = pos.x + addArray[di][0];
	nextPos.y = pos.y + addArray[di][1];
	return nextPos;
}

void footPos(Postion pos,int curStep){
	mazeData[pos.x][pos.y] = curStep;
}

void delPos(Postion pos){
	mazeData[pos.x][pos.y] = -1;
}

int mazePath(Postion startPos,Postion endPos){
	linkStack stack;
	ElementType data;
	int curStep = 2;
	stackInit(&stack);
	do
	{
		if (isPass(startPos))
		{
			footPos(startPos,curStep);
			curStep++;
			data.pos.x = startPos.x;
			data.pos.y = startPos.y;
			data.direction = 0;
			stackPush(&stack,data);
			if (startPos.x == endPos.x && startPos.y == endPos.y)
			{
				stackDestory(&stack);
				return 1;
			}
			else{
				startPos = getNextPos(startPos,0);
			}
		}
		else{
			if (!stackEmpty(stack))
			{
				stackPop(&stack,&data);
				curStep--;
				while (data.direction == 3 && !stackEmpty(stack))
				{
					//错误忘记 删除了..
					delPos(data.pos);
					stackPop(&stack,&data);
					curStep --;
					//startPos.x = data.pos.x;
					//startPos.y = data.pos.y;
				}
				if (data.direction < 3)
				{
					data.direction++; // 换下一个方向探索
					stackPush(&stack,data);
					curStep++;
					startPos = getNextPos(data.pos,data.direction);
				}
			}
		}

	} while (!stackEmpty(stack));
	stackDestory(&stack);
	return 0;
}

// 输出解
void PrintMaze()
{ 
	int i,j;
	int x = 10,y = 10;
	for(i=0;i<x;i++)
	{
		for(j=0;j<y;j++)
			printf("%3d",mazeData[i][j]);
		printf("\n");
	}
	printf("\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
	printf("初始迷宫如下：\n");
	PrintMaze();
	Postion startPos;
	Postion endPos;
	printf("请输入起始位置 坐标x,y （从0行,0列算起）:");
	scanf("%d%d",&startPos.x,&startPos.y);
	printf("请输入终止位置 坐标x,y （从0行,0列算起）:");
	scanf("%d%d",&endPos.x,&endPos.y);
	int result = mazePath(startPos,endPos);
	if (result == 1)
	{
		printf("迷宫解如下：（起始地址为2)\n");
		PrintMaze();
	}
	else
	{
		printf("迷宫从 (%d,%d) 至 (%d,%d) 无解\n",startPos.x,startPos.y,endPos.x,endPos.y);
		PrintMaze();
	}
	return 0;
}

初始迷宫 中 0代表 墙，1 代表 通路。