數(shù)據(jù)結構 棧的操作實例詳解
數(shù)據(jù)結構 棧的操作實例詳解
說明：
往前學習數(shù)據(jù)結構，想運行一個完整的順序棧的程序都運行不了，因為書上給的都是一部分一部分的算法，并沒有提供一個完整可運行的程序，聽了實驗課，自己折騰了一下，總算可以寫一個比較完整的順序棧操作的小程序，對于棧也慢慢開始有了感覺。下面我會把整個程序拆開來做說明，只要把這些代碼放在一個文件中，用編譯器就可以直接編譯運行了。
一、實現(xiàn)
1.程序功能
關于棧操作的經典程序，首當要提及進制數(shù)轉換的問題，利用棧的操作，就可以十分快速地完成數(shù)的進制轉換。
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）其余的常量定義都是可選的，為的就是在下面的代碼書寫過程中可以盡量使用英文來表達程序的意思，而不是在代碼的實現(xiàn)過程中直接使用數(shù)字，依個人喜歡，也可以直接使用數(shù)字；
（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個參數(shù)，&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; //上面的執(zhí)行正常，返回OK
}
5.空棧的判斷
代碼如下：
Status StackEmpty_Sq(SqStack S){
if(S.top == 0)
return TRUE;
else
return FALSE;
}
//空棧的決斷是，如果棧為空就返回1，否則就返回0，當然可以不這樣規(guī)定；
//至于為什么要做空棧的判斷，自然是有原因的，下面再看程序的代碼時就可以知道了。
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動態(tài)擴容
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.進制轉換的函數(shù)
其實上面的步驟操作都是為了創(chuàng)建一個順序棧和定義順序棧的操作而已，并對可能出現(xiàn)的各種情況做一些相應的舉措，完畢后，下面就要使用上面創(chuàng)建的順序棧以及棧的操作接口了，即在數(shù)制轉換函數(shù)（這里是十進制轉八進制）中使用上面的操作接口，代碼如下：
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的余數(shù)入棧
N /= 8; //N取值為其除以8的商
} //理論基礎為除8取余法
while(StackEmpty_Sq(S) == FALSE){
Pop_Sq(S, e); //依次輸出棧中的余數(shù)，并賦給元素e
printf("%d", e); //打印元素
}
9.main函數(shù)
進制轉換函數(shù)調用棧操作的接口函數(shù)，以實現(xiàn)在數(shù)制轉換過程中棧的操作；main函數(shù)調用數(shù)制轉換函數(shù)，以實現(xiàn)數(shù)制的轉換，代碼如下：
int main(void){
printf("Enter a number:");scanf("%d",&num);
Converstion(num);
printf("\n");
}
二、執(zhí)行
有了上面的代碼后，就可以在編譯器中編譯執(zhí)行了，這里我是用c free 5來進行程序代碼的編譯：
（1）輸入的數(shù)為1348時的結果：
（2）輸入的數(shù)為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");
}
相關文章
這篇文章主要給大家介紹了關于C++之assert推薦用法及注意事項的相關資料,assert 是一個預處理宏,用于在運行時檢查表達式是否為真,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2024-07-07
這篇文章主要為大家詳細介紹了C語言之包含min函數(shù)的棧，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
這篇文章主要給大家介紹了關于C++生成格式化的標準字符串的相關資料，文中通過示例代碼介紹的非常詳細，對大家學習或者使用C++具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧2019-09-09
C語言中的一維數(shù)組與二維數(shù)組的實現(xiàn)
數(shù)組可以幫我們巧妙解決生活中的問題,使我們的代碼簡潔，本文主要介紹了C語言中的一維數(shù)組與二維數(shù)組，具有一定的參考價值，感興趣的可以了解一下2023-12-12
這篇文章主要介紹了如何利用OpenCV實現(xiàn)綠幕視頻背景替換功能，文中的示例代碼講解詳細，對我們學習OpenCV有一定的幫助，感興趣的可以學習一下2022-01-01
這篇文章主要講解了普里姆算法（Prim算法），圖論中的一種算法，可在加權連通圖里搜索最小生成樹,需要的朋友可以參考下2015-07-07
怎么實現(xiàn)類的成員函數(shù)作為回調函數(shù)
不使用成員函數(shù)，為了訪問類的成員變量，可以使用友元操作符(friend)，在C++中將該函數(shù)說明為類的友元即可2013-10-10
這篇文章主要為大家詳細介紹了C語言實現(xiàn)掃雷項目，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-07-07
這篇文章主要介紹了c++ 如何排查內存泄漏，幫助大家更好的理解和學習使用c++，感興趣的朋友可以了解下,希望能夠給你帶來幫助2021-10-10
這篇文章主要介紹了C++ 實現(xiàn)輸入含空格的字符串，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-12-12