數據結構 棧的操作實例詳解
說明：
往前學習數據結構，想運行一個完整的順序棧的程序都運行不了，因為書上給的都是一部分一部分的算法，并沒有提供一個完整可運行的程序，聽了實驗課，自己折騰了一下，總算可以寫一個比較完整的順序棧操作的小程序，對于棧也慢慢開始有了感覺。下面我會把整個程序拆開來做說明，只要把這些代碼放在一個文件中，用編譯器就可以直接編譯運行了。
一、實現
1.程序功能
關于棧操作的經典程序，首當要提及進制數轉換的問題，利用棧的操作，就可以十分快速地完成數的進制轉換。
2.預定義、頭文件導入和類型別名
代碼如下：
#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;
除了兩個頭文件的導入是必須的之外，下面做兩點說明：
（1）其余的常量定義都是可選的，為的就是在下面的代碼書寫過程中可以盡量使用英文來表達程序的意思，而不是在代碼的實現過程中直接使用數字，依個人喜歡，也可以直接使用數字；
（2）使用typedef做類型的別名也僅僅是為了程序中代碼的意思更加清晰明了而已，實際也可以不這樣使用；
3.順序棧的定義
代碼如下：
typedef struct{ ElemType *elem; //存儲空間的基址 int top; //棧頂元素的下一個元素，簡稱棧頂位標 int size; //當前分配的存儲容量，作用看入棧操作就可以知道 int increment; //擴容時，增加的存儲容量，作用看入棧操作就可以知道} SqStack; //順序棧名稱4.棧的初始化
代碼如下：
Status InitStack_Sq(SqStack &S, int size, int inc){ //接受3個參數，&S是對結構體的引用 S.elem = (ElemType*)malloc(size*sizeof(ElemType)); //分配存儲空間 if(S.elem == NULL) return OVERFLOW; //判斷上一步分配存儲空間是否成功 S.top = 0; //置S為空棧，S.top為0即表示棧為空棧 S.size = size; //棧的空間初始容量值 S.increment = inc; //棧的空間初始增量值（如果需要擴容） return OK; //上面的執行正常，返回OK}5.空棧的判斷
代碼如下：
Status StackEmpty_Sq(SqStack S){ if(S.top == 0) return TRUE; else return FALSE;}//空棧的決斷是，如果棧為空就返回1，否則就返回0，當然可以不這樣規定；//至于為什么要做空棧的判斷，自然是有原因的，下面再看程序的代碼時就可以知道了。6.入棧
代碼如下：
Status Push_Sq(SqStack &S, ElemType e){ //將元素e壓入棧，這里e只是一個形參而已 ElemType *newbase; //定義中間變量 if(S.top>= S.size){ //S.top如果指向最后一個不存儲元素的地址時，即S.top大于 newbase = (ElemType*)realloc(S.elem, //等于S.size時，就表示棧滿了 (S.size + S.increment)*sizeof(ElemType)); //通過realloc動態擴容 if(NULL == newbase) return OVERFLOW; //判斷擴容是否成功 S.elem = newbase; //擴容成功后才將中間變量的值指向S.elem，防止擴容失敗時， S.size = S.size + S.increment; //S.elem指向一個不是原來的位置 } S.elem[S.top] = e; //將e元素入棧 S.top++; //使S.top加1，表示指向的是棧頂位標 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.進制轉換的函數
其實上面的步驟操作都是為了創建一個順序棧和定義順序棧的操作而已，并對可能出現的各種情況做一些相應的舉措，完畢后，下面就要使用上面創建的順序棧以及棧的操作接口了，即在數制轉換函數（這里是十進制轉八進制）中使用上面的操作接口，代碼如下：
void Converstion(int N){ SqStack S; ElemType e; InitStack_Sq(S, 10, 5); //棧S的初始容量置為10，每次擴容容量為5 while(N != 0){ Push_Sq(S, N%8); //將N除以8的余數入棧 N /= 8; //N取值為其除以8的商 } //理論基礎為除8取余法 while(StackEmpty_Sq(S) == FALSE){ Pop_Sq(S, e); //依次輸出棧中的余數，并賦給元素e printf("%d", e); //打印元素 }9.main函數
進制轉換函數調用棧操作的接口函數，以實現在數制轉換過程中棧的操作；main函數調用數制轉換函數，以實現數制的轉換，代碼如下：
int main(void){ printf("Enter a number:");scanf("%d",&num); Converstion(num); printf("/n");}二、執行
有了上面的代碼后，就可以在編譯器中編譯執行了，這里我是用c free 5來進行程序代碼的編譯：
（1）輸入的數為1348時的結果：
（2）輸入的數為2526時的結果：
三、完整的代碼
下面把代碼都放在一起：
#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");}新聞熱點
疑難解答
圖片精選
