歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> 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

Copyright © Linux教程網 All Rights Reserved