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

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

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

/* 挑灯看剑[e-mail] 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》