- 浏览: 130967 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
fascism219:
哇!您这篇博客写的太好了,看了以后感觉很受用!我最近正在做CE ...
移植CESM1.2和运行CLM4.5问题汇总 -
deepfuture:
不错,用栈来实现递归,速度和效率较高,建议部分栈操作这块用内联 ...
数据结构:栈应用_求解汉诺塔(Hanoi)1
/************************************************************************/ /* 数据结构:栈应用:求解迷宫问题 */ /* 挑灯看剑-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,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》
发表评论
-
数据结构:栈应用_求解汉诺塔(Hanoi)2
2010-10-15 16:05 1155/****************************** ... -
数据结构:栈应用_求解汉诺塔(Hanoi)1
2010-10-15 16:02 2501/****************************** ... -
数据结构:栈应用_求解迷宫问题3
2010-10-11 20:31 1307/****************************** ... -
数据结构:栈应用_求解迷宫问题1
2010-10-11 20:24 1404/****************************** ... -
数据结构:栈基本操作
2010-10-11 20:18 930/****************************** ... -
数据结构:双向链表2
2010-10-11 20:15 786/****************************** ... -
数据结构:双向链表1
2010-10-11 20:01 786/****************************** ... -
数据结构:线性链表
2010-10-11 19:30 1069/****************************** ... -
数据结构:CORE头文件
2010-10-11 17:26 931/****************************** ... -
数据结构:动态线性顺序表
2010-10-11 17:22 994/****************************** ...
相关推荐
实验内容:迷宫问题 三.实验目的:掌握栈和队列的概念及工作原理,运用其原理完成实验题目中的内容。 四.实验要求:为了使学生更好的掌握与理解课堂上老师所讲的概念与原理,实验前每个学生要认真预习所做的实验...
使用栈结构完成迷宫求解算法演示,设计了GUI界面使算法演示更加直观
很好的一个迷宫求解程序。此程序用0和1来随机产生一个迷宫,然后用栈的基本操作来实现迷宫的求解。很适合用于数据结构栈应用的课程设计。
本程序根据栈的特点来模拟迷宫求解的方法,这种迷宫求解的方法应用了栈的基本特点,属于栈的最基本应用,本程序只做了简单路径的求解,没有做最短路径的求解。
《数据结构》-李春葆 实验报告-栈与队列的应用-求解迷宫路径问题
(2)然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出,其中:(i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向。 如:对于下列数据的迷宫,输出的一条通路为:(1,1,1),(1,2,2...
迷宫问题 数据结构 湖南大学
改算法值得自习体会 涉及到栈和队列的综合应用
迷宫求解——栈的简单应用 要熟练得掌握一种数据结构,要经过大量的练习,而将数据结构应用于实际用用中则是一种非常好的锻炼方式。 此次便是应用java来实现 迷宫求解 这个经典的程序设计问题。
基本要求:首先实现一个以链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出,其中:(i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向。如:对于下列数据的...
求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前探索,若...因此,在求迷宫通路的算法中应用“栈”也就是自然而然的事了。
主要练习对栈的灵活应用,通过对迷宫可行路径的搜寻来实现对栈的应用
(2) 利用链表作为栈的存储结构,设计实现一个求解迷宫的非递归程序。 二、实验内容: 【问题描述】 以一个m×n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对信任意设定的迷宫,求出一条...
(2) 利用链表作为栈的存储结构,设计实现一个求解迷宫的非递归程序。 二、实验内容: 【问题描述】 以一个m×n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从...
数据结构中,关于迷宫问题的源代码(C语言)。课程作业是解决迷宫求解的问题,从入口出发,顺某一方向向前探索,若能走通,则继续往前走;否则沿原路退回,换一个方向再继续探索,直至所有可能的通路都探索到为止。...
迷宫问题是栈应用的一个典型例子。求解过程可采用回溯法。回溯法是一种不断试探且及时纠正错误的搜索方法。从入口出发,按某一方向向前探索,若能走通(未走过的),即某处可以到达,则到达新点,否则试探下一方向;...
有链表、栈的一些应用例子。多项式的相加、括号匹配的检验、以及迷宫求解
《数据结构》 (严蔚敏版) 源代码 C语言实现 教材:数据结构题集 高等教育出版社 严蔚敏 吴伟民 米宁编著 实验一 线性表的应用(4学时) 一、实验目的:掌握线性表的基本结构和操作方法,培养学生灵活使用...
(2) 利用链表作为栈的存储结构,设计实现一个求解迷宫的非递归程序。 二、实验内容: 【问题描述】 以一个m×n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对信任意设定的迷宫,求出一条...