數(shù)據(jù)結(jié)構(gòu) 棧的操作實(shí)例詳解

更新時(shí)間：2017年06月27日 16:56:04 投稿：lqh

這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu) 順序棧的定義、初始化、空棧判斷、入棧、出棧操作的相關(guān)資料,需要的朋友可以參考下

數(shù)據(jù)結(jié)構(gòu) 棧的操作實(shí)例詳解

說(shuō)明：

往前學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，想運(yùn)行一個(gè)完整的順序棧的程序都運(yùn)行不了，因?yàn)闀?shū)上給的都是一部分一部分的算法，并沒(méi)有提供一個(gè)完整可運(yùn)行的程序，聽(tīng)了實(shí)驗(yàn)課，自己折騰了一下，總算可以寫(xiě)一個(gè)比較完整的順序棧操作的小程序，對(duì)于棧也慢慢開(kāi)始有了感覺(jué)。下面我會(huì)把整個(gè)程序拆開(kāi)來(lái)做說(shuō)明，只要把這些代碼放在一個(gè)文件中，用編譯器就可以直接編譯運(yùn)行了。

一、實(shí)現(xiàn)

1.程序功能

關(guān)于棧操作的經(jīng)典程序，首當(dāng)要提及進(jìn)制數(shù)轉(zhuǎn)換的問(wèn)題，利用棧的操作，就可以十分快速地完成數(shù)的進(jìn)制轉(zhuǎn)換。

2.預(yù)定義、頭文件導(dǎo)入和類型別名

代碼如下：

#include<stdio.h>
#include<stdlib.h>
#define OVERFLOW -1
#define ERROR 0
#define FALSE 0
#define TRUE 1
#define OK 1
 
typedef int ElemType;
typedef int Status;

除了兩個(gè)頭文件的導(dǎo)入是必須的之外，下面做兩點(diǎn)說(shuō)明：

（1）其余的常量定義都是可選的，為的就是在下面的代碼書(shū)寫(xiě)過(guò)程中可以盡量使用英文來(lái)表達(dá)程序的意思，而不是在代碼的實(shí)現(xiàn)過(guò)程中直接使用數(shù)字，依個(gè)人喜歡，也可以直接使用數(shù)字；

（2）使用typedef做類型的別名也僅僅是為了程序中代碼的意思更加清晰明了而已，實(shí)際也可以不這樣使用；

3.順序棧的定義

代碼如下：

typedef struct{
  ElemType *elem;   //存儲(chǔ)空間的基址
  int top;      //棧頂元素的下一個(gè)元素，簡(jiǎn)稱棧頂位標(biāo)
  int size;      //當(dāng)前分配的存儲(chǔ)容量，作用看入棧操作就可以知道
  int increment;   //擴(kuò)容時(shí)，增加的存儲(chǔ)容量，作用看入棧操作就可以知道
} SqStack;         //順序棧名稱

4.棧的初始化

代碼如下：

Status InitStack_Sq(SqStack &S, int size, int inc){   //接受3個(gè)參數(shù)，&S是對(duì)結(jié)構(gòu)體的引用
  S.elem = (ElemType*)malloc(size*sizeof(ElemType)); //分配存儲(chǔ)空間
  if(S.elem == NULL) return OVERFLOW;   //判斷上一步分配存儲(chǔ)空間是否成功
  S.top = 0;      //置S為空棧，S.top為0即表示棧為空棧
  S.size = size;    //棧的空間初始容量值
  S.increment = inc;  //棧的空間初始增量值（如果需要擴(kuò)容）
  return OK;    //上面的執(zhí)行正常，返回OK
}

5.空棧的判斷

代碼如下：

Status StackEmpty_Sq(SqStack S){
  if(S.top == 0)
    return TRUE;
  else
    return FALSE;
}
//空棧的決斷是，如果棧為空就返回1，否則就返回0，當(dāng)然可以不這樣規(guī)定；
//至于為什么要做空棧的判斷，自然是有原因的，下面再看程序的代碼時(shí)就可以知道了。

6.入棧

代碼如下：

Status Push_Sq(SqStack &S, ElemType e){  //將元素e壓入棧，這里e只是一個(gè)形參而已
  ElemType *newbase;    //定義中間變量
  if(S.top>= S.size){    //S.top如果指向最后一個(gè)不存儲(chǔ)元素的地址時(shí)，即S.top大于
    newbase = (ElemType*)realloc(S.elem, //等于S.size時(shí)，就表示棧滿了
  (S.size + S.increment)*sizeof(ElemType)); //通過(guò)realloc動(dòng)態(tài)擴(kuò)容
   
  if(NULL == newbase) return OVERFLOW; //判斷擴(kuò)容是否成功
  S.elem = newbase;   //擴(kuò)容成功后才將中間變量的值指向S.elem，防止擴(kuò)容失敗時(shí)，
  S.size = S.size + S.increment;   //S.elem指向一個(gè)不是原來(lái)的位置
  }
  S.elem[S.top] = e;  //將e元素入棧
  S.top++;       //使S.top加1，表示指向的是棧頂位標(biāo)
  return OK;      //上面操作正常后返回1
}

7.出棧

代碼如下：

Status Pop_Sq(SqStack &S, ElemType &e){  //棧頂元素出棧，賦給元素e
  if(0 == S.top) return ERROR;  
  e = S.elem[--S.top];  //e出棧，并將S.top減1
  return OK;
}

8.進(jìn)制轉(zhuǎn)換的函數(shù)

其實(shí)上面的步驟操作都是為了創(chuàng)建一個(gè)順序棧和定義順序棧的操作而已，并對(duì)可能出現(xiàn)的各種情況做一些相應(yīng)的舉措，完畢后，下面就要使用上面創(chuàng)建的順序棧以及棧的操作接口了，即在數(shù)制轉(zhuǎn)換函數(shù)（這里是十進(jìn)制轉(zhuǎn)八進(jìn)制）中使用上面的操作接口，代碼如下：

void Converstion(int N){
  SqStack S;
  ElemType e;
  InitStack_Sq(S, 10, 5);  //棧S的初始容量置為10，每次擴(kuò)容容量為5
   
  while(N != 0){
    Push_Sq(S, N%8);  //將N除以8的余數(shù)入棧
    N /= 8;      //N取值為其除以8的商
  }             //理論基礎(chǔ)為除8取余法
   
  while(StackEmpty_Sq(S) == FALSE){
    Pop_Sq(S, e);  //依次輸出棧中的余數(shù)，并賦給元素e
    printf("%d", e); //打印元素
  }

9.main函數(shù)

進(jìn)制轉(zhuǎn)換函數(shù)調(diào)用棧操作的接口函數(shù)，以實(shí)現(xiàn)在數(shù)制轉(zhuǎn)換過(guò)程中棧的操作；main函數(shù)調(diào)用數(shù)制轉(zhuǎn)換函數(shù)，以實(shí)現(xiàn)數(shù)制的轉(zhuǎn)換，代碼如下：

int main(void){
  printf("Enter a number:");scanf("%d",&num);
  Converstion(num);
  printf("\n");
}

二、執(zhí)行

有了上面的代碼后，就可以在編譯器中編譯執(zhí)行了，這里我是用c free 5來(lái)進(jìn)行程序代碼的編譯：

（1）輸入的數(shù)為1348時(shí)的結(jié)果：

（2）輸入的數(shù)為2526時(shí)的結(jié)果：

三、完整的代碼

下面把代碼都放在一起：

#include<stdio.h>
#include<stdlib.h>
#define OVERFLOW -1
#define ERROR 0
#define FALSE 0
#define TRUE 1
#define OK 1
 
typedef int ElemType;
typedef int Status;
 
typedef struct{
  ElemType *elem;
  int top;
  int size;
  int increment;
} SqStack;
 
Status InitStack_Sq(SqStack &S, int size, int inc){
  S.elem = (ElemType*)malloc(size*sizeof(ElemType));
  if(S.elem == NULL) return OVERFLOW;
  S.top = 0;
  S.size = size;
  S.increment = inc;
  return OK;
}
 
Status StackEmpty_Sq(SqStack S){
  if(S.top == 0)
    return TRUE;
  else
    return FALSE;
}
 
Status Push_Sq(SqStack &S, ElemType e){
  ElemType *newbase;
  if(S.top>= S.size){
    newbase = (ElemType*)realloc(S.elem,
  (S.size + S.increment)*sizeof(ElemType));
   
  if(NULL == newbase) return OVERFLOW;
  S.elem = newbase;
  S.size = S.size + S.increment;
  }
  S.elem[S.top] = e;
  S.top++;
  return OK;
}
 
Status Pop_Sq(SqStack &S, ElemType &e){
  if(0 == S.top) return ERROR;
  e = S.elem[--S.top];
  return OK;
}
 
void Converstion(int N){
  SqStack S;
  ElemType e;
  InitStack_Sq(S, 10, 5);
   
  while(N != 0){
    Push_Sq(S, N%8);
    N /= 8;
  }
   
  while(StackEmpty_Sq(S) == FALSE){
    Pop_Sq(S, e);
    printf("%d", e);
  }
}
 
int main(void){
  int num;
  printf("Enter a number:");scanf("%d",&num);
  Converstion(num);
  printf("\n");
}

您可能感興趣的文章: