/************************************************************************/
/* 数据结构:栈应用:求解迷宫问题 */
/* 挑灯看剑-shuchangs@126.com 2010-10 */
/* 云歌国际(Cloud Singers International) www.cocoral.com */
/************************************************************************/
#include <stdio.h>
#include <malloc.h>
#include "core.h"
/************************************************************************/
/* 以下是栈基本操作:进栈、出栈、打印栈 */
/************************************************************************/
//定义当前位置(迷宫足迹)数据结构
typedef struct CURRENTPOSITION
{
struct CURRENTPOSITION* up, * down, * left, * right; //四邻情况
int visited; //是否被访问:1表示被访问,0表示未被访问
int data; //数据域
int x, y; //位置坐标
}CurPos;
//结点数据结构
typedef struct NODE
{
struct CURRENTPOSITION data; //使用迷宫中的足迹数据结构作为数据域
struct NODE* next;
struct NODE* prior;
}Node, * NodePointer;
//栈元数据结构
typedef struct STACK
{
int len;
struct NODE* top;
struct NODE* base;
}Stack, * StackPointer;
void main()
{
//*************函数原型******************
Status StackIn(StackPointer SP, struct CURRENTPOSITION e);
//void autoStack(StackPointer SP, int n);
void StackPrint(Stack S, char tag);
Status StackOut(StackPointer SP, NodePointer NP);
void mazeExperiment();
//*************函数原型******************
//迷宫实验
mazeExperiment();
}
//进栈操作,结点作为栈顶元素入栈
Status StackIn(StackPointer SP, struct CURRENTPOSITION e)
{
static Status StackIsEmpty(Stack S);//函数原型
Status status = ERROR;
NodePointer p = NULL;//遍历指针,非游离指针
NodePointer NP = (NodePointer) malloc(sizeof(Node));
NP->data = e;
//进行预处理
if (!StackIsEmpty(*SP))
{
//将结点追加为栈顶元素
p = SP->top; //p指向栈顶
p->next = NP;
NP->prior = p;
NP->next = NULL;
SP->top = NP;
SP->len += 1; //长度加1
//puts("进栈成功!");
status = OK;
}
else
{
SP->base = SP->top = NP;
NP->next = NP->prior = NULL;
SP->len = 1; //长度为1
//puts("进栈成功!");
status = OK;
}
return status;
}
static Status StackIsEmpty(Stack S)
{
if (S.len == 0 || S.base == NULL || S.top == NULL)
return TRUE;
else
return FALSE;
}
//出栈操作,并用结点返回该值
Status StackOut(StackPointer SP, NodePointer NP)
{
Status status = ERROR;
NodePointer p = SP->top; //p指向栈顶
if (!StackIsEmpty(*SP))
{
if (SP->len == 1)
{
SP->base = SP->top = NULL;
SP->len = 0; //长度为0
NP->data = p->data;
NP->next = p->next;
NP->prior = p->prior;
//puts("出栈成功!");
status = OK;
}
else
{
p->prior->next = NULL;
SP->top = p->prior;
SP->len -= 1; //长度减1
NP->data = p->data;
NP->next = p->next;
NP->prior = p->prior;
//puts("出栈成功!");
status = OK;
}
}
else
{
//puts("出栈失败!栈为空!");
status = ERROR;
}
free(p); //p为游离结点,最后释放p内存
return status;
}
//栈打印操作,tag参数IN SET{'B','T'}
void StackPrint(Stack S, char tag)
{
static Status StackIsEmpty(Stack S);//函数原型
NodePointer p = NULL;
COUNT i = 1;
COUNT n = S.len;
printf("栈长度:%d\n", n);
if (!StackIsEmpty(S)) //如果线性链表非空
{
switch (tag)
{
case 'B':
p = S.base;
puts("打印结点信息(栈底到栈顶):");
for (i = 1; i <= n; i++)
{
printf("[%d] foot[%d][%d] = %d\n", i, p->data.x, p->data.y,
p->data.data);
p = p->next;
}
break;
case 'T':
p = S.top;
puts("打印结点信息(栈顶到栈底):");
for (i = n; i >= 1; i--)
{
printf("[%d] foot[%d][%d] = %d\n", i, p->data.x, p->data.y,
p->data.data);
p = p->prior;
}
break;
default:
puts("打印失败!");
break;
}
}
else //如果栈为空
{
puts("打印失败!栈为空!");
}
free(p);//p为游离结点,最后释放p内存
}
//下接版面 《数据结构:栈应用:求解迷宫问题2》
分享到:
相关推荐
实验内容:迷宫问题 三.实验目的:掌握栈和队列的概念及工作原理,运用其原理完成实验题目中的内容。 四.实验要求:为了使学生更好的掌握与理解课堂上老师所讲的概念与原理,实验前每个学生要认真预习所做的实验...
使用栈结构完成迷宫求解算法演示,设计了GUI界面使算法演示更加直观
很好的一个迷宫求解程序。此程序用0和1来随机产生一个迷宫,然后用栈的基本操作来实现迷宫的求解。很适合用于数据结构栈应用的课程设计。
本程序根据栈的特点来模拟迷宫求解的方法,这种迷宫求解的方法应用了栈的基本特点,属于栈的最基本应用,本程序只做了简单路径的求解,没有做最短路径的求解。
《数据结构》-李春葆 实验报告-栈与队列的应用-求解迷宫路径问题
(1)首先实现一个以链表作存储结构的栈类型 (2)然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出,其中:(i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向。 如:对于下列数据的...
迷宫问题 数据结构 湖南大学
改算法值得自习体会 涉及到栈和队列的综合应用
迷宫求解——栈的简单应用 要熟练得掌握一种数据结构,要经过大量的练习,而将数据结构应用于实际用用中则是一种非常好的锻炼方式。 此次便是应用java来实现 迷宫求解 这个经典的程序设计问题。
基本要求:首先实现一个以链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出,其中:(i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向。如:对于下列数据的...
求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前探索,若...因此,在求迷宫通路的算法中应用“栈”也就是自然而然的事了。
(2) 利用链表作为栈的存储结构,设计实现一个求解迷宫的非递归程序。 二、实验内容: 【问题描述】 以一个m×n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对信任意设定的迷宫,求出一条...
主要练习对栈的灵活应用,通过对迷宫可行路径的搜寻来实现对栈的应用
(2) 利用链表作为栈的存储结构,设计实现一个求解迷宫的非递归程序。 二、实验内容: 【问题描述】 以一个m×n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从...
数据结构中,关于迷宫问题的源代码(C语言)。课程作业是解决迷宫求解的问题,从入口出发,顺某一方向向前探索,若能走通,则继续往前走;否则沿原路退回,换一个方向再继续探索,直至所有可能的通路都探索到为止。...
迷宫问题是栈应用的一个典型例子。求解过程可采用回溯法。回溯法是一种不断试探且及时纠正错误的搜索方法。从入口出发,按某一方向向前探索,若能走通(未走过的),即某处可以到达,则到达新点,否则试探下一方向;...
(2) 利用链表作为栈的存储结构,设计实现一个求解迷宫的非递归程序。 二、实验内容: 【问题描述】 以一个m×n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对信任意设定的迷宫,求出一条...
有链表、栈的一些应用例子。多项式的相加、括号匹配的检验、以及迷宫求解
1)利用栈深度优先进行迷宫求解。 2)利用队列宽度优先进行迷宫求解。 三、实验要求: 1,用数组表示迷宫 2,建立栈,利用栈实现深度优先搜索 3,建立队列,利用队列实现宽度优先搜索 实验三 稀疏矩阵运算(4...