首页 / 操作系统 / Linux / C语言 迷宫问题（堆栈及其应用）

首先我们来看看堆栈这个数据结构，像朱老师曾经说的那样堆栈是一个单腔生物，想想一个场景，有一个笔直的路，最远端是死胡同。我们现在让车一个一个的进去，那要出来的的时候必须是后进去的先出来（push和pop操作）。对于堆栈这样的数据结构有这些操作：
            1.堆栈的初始化和销毁；
            2.堆栈清空；
            3.判断堆栈是否为空；
            4.返回栈顶元素；
            5.得到堆栈内元素的个数；
            6.压栈与出栈；
 
            堆栈的应用方面非常广泛，例如：数值转换，括号匹配，行编辑程序，迷宫问题和表达式等。
            无论是那种应用，都要记住堆栈的最大的功能是：记忆！！！
            下面是堆栈的代码，我这个里面没有判断堆栈是否为满，如果堆栈元素等于申请个数时，堆栈会追加10个元素，这个可以修改。让对内存的申请达到合适的数量。如果要用堆栈时，把头文件预处理就行了。将C语言梳理一下，分布在以下10个章节中：

1. Linux-C成长之路（一）：Linux下C编程概要 http://www.linuxidc.com/Linux/2014-05/101242.htm
2. Linux-C成长之路（二）：基本数据类型 http://www.linuxidc.com/Linux/2014-05/101242p2.htm
3. Linux-C成长之路（三）：基本IO函数操作 http://www.linuxidc.com/Linux/2014-05/101242p3.htm
4. Linux-C成长之路（四）：运算符 http://www.linuxidc.com/Linux/2014-05/101242p4.htm
5. Linux-C成长之路（五）：控制流 http://www.linuxidc.com/Linux/2014-05/101242p5.htm
6. Linux-C成长之路（六）：函数要义 http://www.linuxidc.com/Linux/2014-05/101242p6.htm
7. Linux-C成长之路（七）：数组与指针 http://www.linuxidc.com/Linux/2014-05/101242p7.htm
8. Linux-C成长之路（八）：存储类，动态内存 http://www.linuxidc.com/Linux/2014-05/101242p8.htm
9. Linux-C成长之路（九）：复合数据类型 http://www.linuxidc.com/Linux/2014-05/101242p9.htm
10. Linux-C成长之路（十）：其他高级议题

C++ Primer Plus 第6版 中文版 清晰有书签PDF+源代码 http://www.linuxidc.com/Linux/2014-05/101227.htm
           
一.  STACK.H 
#ifndef _STACK_H_
 
#define _STACK_H_
  #include<malloc.h>
 
#include<stdlib.h>
  #define TRUE  1
 
#define FALSE  0
 
#define STACKINCREMENT  10
  typedef struct STACK
 
{
 
USER_TYPE *top;
 //栈顶指针
 
USER_TYPE *base;
 //栈底指针
 
int maxRoom;
 
}STACK;
  typedef unsigned char Boolean;
  STACK *initStack（int maxRoom）;
 //初始化堆栈
 
void destroyStack（STACK **sta）;
 //销毁堆栈
 
Boolean isStackEmpty（STACK sta）;
 //判断堆栈是否为空
 
void clearStack（STACK *sta）;
 //清空堆栈信息
 
int stackLength（STACK sta）;
 //返回堆栈内元素个数
 
Boolean getStackTop（STACK sta, USER_TYPE *element）;
 //得到栈顶元素
 
Boolean push（STACK *sta, USER_TYPE element）;
 //入栈
 
Boolean pop（STACK *sta, USER_TYPE *element）;
 //出栈
  Boolean pop（STACK *sta, USER_TYPE *element）
 
{
 
Boolean OK = TRUE;
  if（isStackEmpty（*sta） == FALSE）
 
{
 
*element = *（sta->top - 1）;
 
sta->top--;
 
}
 
else
 
{
 
OK = FALSE;
 
}
 
return OK;
 
}
  Boolean push（STACK *sta, USER_TYPE element）
 
{
 
Boolean OK = TRUE;
 
if（ （sta->top - sta->base） >= sta->maxRoom）
 
{
 
sta->base = （USER_TYPE *）realloc（sta->base,
 
（sta->maxRoom + STACKINCREMENT） * sizeof（USER_TYPE））;
 
if（sta->base == NULL）
 
{
 
exit（1）;
 //存储分配失败
 
}
 
sta->top = sta->base + sta->maxRoom;
 
sta->maxRoom += STACKINCREMENT;
 
}
  *sta->top = element;
 
sta->top++;
 
return OK;
 
}
  Boolean getStackTop（STACK sta, USER_TYPE *element）
 
{
 
Boolean OK = TRUE;
  if（isStackEmpty（sta） == FALSE）
 
{
 
*element = *（sta.top - 1）;
 
}
 
else
 
{
 
OK = FALSE;
 
}
  return OK;
 
}
   
int stackLength（STACK sta）
 
{
 
return sta.top - sta.base;
 
}
  void clearStack（STACK *sta）
 
{
 
sta->top = sta->base;
 
}
  Boolean isStackEmpty（STACK sta）
 
{
 
return sta.top == sta.base;
 
}
   
void destroyStack（STACK **sta）
 
{
 
if（（*sta）->base）
 
free（（*sta）->base）; 
（*sta）->top = NULL;
 
free（*sta）;
 
}
  STACK *initStack（int maxRoom）
 
{
 
STACK *stack;
 
stack = （STACK *）malloc（sizeof（STACK））;
  if（stack == NULL）
 
{
 
exit（1）;
 
}
 
else
 
{
 
stack->maxRoom = maxRoom;
 
stack->base = （USER_TYPE *）malloc（sizeof（USER_TYPE） * maxRoom）;
 
if（stack->base == NULL）
 
{
 
exit（0）;
 
}
 
stack->top = stack->base;
 
}
  return stack;
 
}
  #endif更多详情见请继续阅读下一页的精彩内容： http://www.linuxidc.com/Linux/2014-07/104455p2.htm