数据结构：栈应用_求解迷宫问题2

chemingliang

浏览: 134780 次
性别:
来自: 北京

最近访客更多访客>>

mbcqss

feiyue81

jimlaren

qsjiangs

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

C/C++

数据结构 J#UP

/************************************************************************/

/* 数据结构：栈应用：求解迷宫问题 */

/* 挑灯看剑-shuchangs@126.com 2010-10 */

/* 云歌国际（Cloud Singers International） www.cocoral.com */

/************************************************************************/

//上接版面《数据结构：栈应用_求解迷宫问题1》

/************************************************************************/

/* 以下为迷宫求解问题 */

/************************************************************************/

void mazeExperiment()

{

void printMatrix(int (*mtx)[9], int m, int n);

void printMzePath(Stack S, int (*mtx)[9], int m, int n);

static Status visa(CurPos* foot, char direction);

static void step(CurPos* END, CurPos* foot, Stack* stack, Node* node);

//定义迷宫矩阵，1表示通行，0表示禁止

//约定迷宫矩阵四壁均为禁止

int mtx[9][9] =

{

{0,0,0,0,0,0,0,0,0},

{0,1,1,0,1,1,0,1,0},

{0,1,1,1,1,0,1,1,0},

{0,1,0,0,0,1,1,1,0},

{0,1,1,0,0,1,0,1,0},

{0,1,0,1,1,1,0,1,0},

{0,1,1,1,1,0,0,1,0},

{0,0,0,0,0,0,0,0,0}

};

Stack stack =

{

0, NULL, NULL

}; //定义一个空栈

Node node =

{

NULL, NULL, NULL

}; //用来返回出栈元素

CurPos* foot, * start, * end;//定义足迹指针，开始指针和结束指针

CurPos footprint[9][9];//定义一个足迹矩阵

int m = 9;//足迹矩阵行数

int n = 9;//足迹矩阵列数

COUNT i, j;//足迹坐标

//初始化足迹矩阵

for (i = 0; i <= m - 1; i++)

{

for (j = 0; j <= n - 1; j++)

{

footprint[i][j].data = mtx[i][j];

footprint[i][j].visited = FALSE;

footprint[i][j].x = i;

footprint[i][j].y = j;

if (i == 0 && j == 0) //左上顶点

{

footprint[i][j].up = NULL;

footprint[i][j].down = &footprint[i + 1][j];

footprint[i][j].left = NULL;

footprint[i][j].right = &footprint[i][j + 1];

}

else if (i == 0 && j == n - 1) //右上顶点

{

footprint[i][j].up = NULL;

footprint[i][j].down = &footprint[i + 1][j];

footprint[i][j].left = &footprint[i][j - 1];

footprint[i][j].right = NULL;

}

else if (i == m - 1 && j == 0) //左下顶点

{

footprint[i][j].up = &footprint[i - 1][j];

footprint[i][j].down = NULL;

footprint[i][j].left = NULL;

footprint[i][j].right = &footprint[i][j + 1];

}

else if (i == m - 1 && j == n - 1) //右下顶点

{

footprint[i][j].up = &footprint[i - 1][j];

footprint[i][j].down = NULL;

footprint[i][j].left = &footprint[i][j - 1];

footprint[i][j].right = NULL;

}

else if (i == 0 && j != 0 && j != n - 1) //上边框

{

footprint[i][j].up = NULL;

footprint[i][j].down = &footprint[i + 1][j];

footprint[i][j].left = &footprint[i][j - 1];

footprint[i][j].right = &footprint[i][j + 1];

}

else if (i == m - 1 && j != 0 && j != n - 1) //下边框

{

footprint[i][j].up = &footprint[i - 1][j];

footprint[i][j].down = NULL;

footprint[i][j].left = &footprint[i][j - 1];

footprint[i][j].right = &footprint[i][j + 1];

}

else if (j == 0 && i != 0 && i != m - 1) //左边框

{

footprint[i][j].up = &footprint[i - 1][j];

footprint[i][j].down = &footprint[i + 1][j];

footprint[i][j].left = NULL;

footprint[i][j].right = &footprint[i][j + 1];

}

else if (j == n - 1 && i != 0 && i != m - 1) //右边框

{

footprint[i][j].up = &footprint[i - 1][j];

footprint[i][j].down = &footprint[i + 1][j];

footprint[i][j].left = &footprint[i][j - 1];

footprint[i][j].right = NULL;

}

else //中间元素

{

footprint[i][j].up = &footprint[i - 1][j];

footprint[i][j].down = &footprint[i + 1][j];

footprint[i][j].left = &footprint[i][j - 1];

footprint[i][j].right = &footprint[i][j + 1];

}

start = &footprint[1][1]; //定义起始指针和结束指针，并初始化

end = &footprint[7][7];

foot = start; //令足迹指针初始指向起始指针

foot->visited = 1; //令访问标记为已访问

StackIn(&stack, *foot); //当前足迹入栈

printMzePath(stack, mtx, 9, 9);

//迷宫遍历规则：每个格子紧挨四个格子，定义为上-下，左-右，按照从右开始、顺时针方向遍历格子

step(end, foot, &stack, &node); //调用回调函数

StackPrint(stack, 'B'); //打印栈（迷宫路径）

printMzePath(stack, mtx, 9, 9);

}

static void step(CurPos* END, CurPos* foot, Stack* stack, Node* rtnNode)

{

if (foot == END)

{

puts("迷宫求解结束！");

}

else if (stack->len == 0)

{

puts("迷宫求解失败！");

}

else if (visa(foot, 'R')) //如果右侧可行，先遍历右方向

{

foot->visited = 1; //当前足迹已访问

StackIn(stack, *foot); //当前足迹入栈

//StackPrint(*stack, 'B');

foot = foot->right; //向右前进一步

step(END, foot, stack, rtnNode);

}

else if (visa(foot, 'D'))

{

foot->visited = 1;

StackIn(stack, *foot);

//StackPrint(*stack, 'B');

foot = foot->down;

step(END, foot, stack, rtnNode);

}

else if (visa(foot, 'L'))

{

foot->visited = 1;

StackIn(stack, *foot);

//StackPrint(*stack, 'B');

foot = foot->left;

step(END, foot, stack, rtnNode);

}

else if (visa(foot, 'U'))

{

foot->visited = 1;

StackIn(stack, *foot);

//StackPrint(*stack, 'B');

foot = foot->up;

step(END, foot, stack, rtnNode);

}

else

{

foot->visited = 1;

StackOut(stack, rtnNode); //出栈一位，删除栈顶

foot = &(rtnNode->data); //foot指针退回到删除结点位置

//printf("删除结点 foot[%d][%d] = %d\n", foot->x, foot->y,foot->data);

//StackPrint(*stack, 'B');

step(END, foot, stack, rtnNode);

}

static Status visa(CurPos* foot, char direction)

{

Status status = FALSE;

switch (direction)

{

case 'L':

//如果左结点的值可通行，且未被访问

if (foot->left->data == 1 && foot->left->visited == 0)

status = TRUE;

break;

case 'R':

if (foot->right->data == 1 && foot->right->visited == 0)

status = TRUE;

break;

case 'U':

if (foot->up->data == 1 && foot->up->visited == 0)

status = TRUE;

break;

case 'D':

if (foot->down->data == 1 && foot->down->visited == 0)

status = TRUE;

break;

default:

break;

}

return status;

}

void printMatrix(int (*mtx)[9], int m, int n)

{

COUNT i, j;

printf("矩阵信息：%d行，%d列！\n", m, n);

for (i = 0; i < m; i++)

{

printf("row=%d ", i);

for (j = 0; j < n; j++)

{

printf(" %d ", *(*(mtx + i) + j));

}

printf("\n");

}

//下接版面《数据结构：栈应用：求解迷宫问题3》

分享到：

数据结构：栈应用_求解迷宫问题3 | 数据结构：栈应用_求解迷宫问题1

2010-10-11 20:27
浏览 1240
评论(0)
分类:编程语言
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论