博客
順序棧的各種基本運算
實驗內容與要求：
編寫一個程序，實現順序棧的各種基本運算，并在基礎上完成以下功能:
1) 初始化順序棧；
2) 判斷順序棧是否為空；
3) 依次進棧元素a,b,c,d,e；
4) 判斷順序棧是否為空；
5) 輸出棧長度；
6) 輸出從棧頂到棧底的元素；
7) 讀出棧頂元素；
8) 刪除棧頂元素；
9) 輸出從棧頂到棧底的元素；
10) 判斷順序棧是否為空；
11) 釋放棧。
代碼如下：
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define NULL 0
#define OVERFLOW -2
typedef int Status;
typedef char SElemType;
Status visit(SElemType e);
#define STACK_INIT_SIZE 100 // 棧存儲空間的初始分配量
#define STACKINCREMENT 10 // 存儲空間分配增量
typedef struct {
SElemType *base; // 存儲數據元素的數組
SElemType *top; // 棧頂指針
int stacksize; // 當前分配的棧空間大小,以sizeof(SElemType)為單位
}SqStack;
Status InitStack (SqStack &S) {
// 構造一個空棧S
S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if (!S.base) exit (OVERFLOW);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}// InitStack
Status DestroyStack (SqStack &S) {
// 銷毀棧S
free(S.base);
S.base=NULL;
S.top=NULL;
S.stacksize=0;
return OK;
}// DestroyStack
Status StackEmpty (SqStack S) {
// 判斷棧S是否為空
if(S.top==S.base)
return TRUE;
else
return FALSE;
}// StackEmpty
Status Push (SqStack &S, SElemType e) {
// 插入元素e為新的棧頂元素
if (S.top - S.base >= S.stacksize) {
// 棧滿，追加存儲空間
S.base = (SElemType *) realloc(S.base,
(S.stacksize + STACKINCREMENT) * sizeof (SElemType));
if (!S.base) exit (OVERFLOW); //存儲分配失敗
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}// Push
int StackLength (SqStack S) {
// 返回S的元素個數，即棧的長度
return S.top-S.base;
}// StackLength
Status GetTop (SqStack S, SElemType &e) {
// 若棧不空，則用e返回S的棧頂元素
if(S.top==S.base) return ERROR;
e = *(S.top-1);
return OK;
}// GetTop
Status Pop (SqStack &S, SElemType &e) {
// 若棧不空，則刪除S的棧頂元素
if(S.top==S.base) return ERROR;
e= * --S.top;
return OK;
}// Pop
Status StackTraverse (SqStack S, Status( *visit)(SElemType)) {
// 遍歷棧
while(S.top!=S.base)
visit(*--S.top);
return OK;
}// StackTraverse
void main() {
// 主函數
SElemType e;
SqStack S;
printf("(1)初始化順序棧。\n");
InitStack(S);
printf("(2)判斷順序棧是否為空:\n");
StackEmpty(S);
printf("(3)依次進棧元素a,b,c,d,e:\n");
Push(S,'a');
Push(S,'b');
Push(S,'c');
Push(S,'d');
Push(S,'e');
printf("(4)判斷順序棧是否為空:\n");
StackEmpty(S);
printf("(5)輸出棧長度:%d\n",StackLength(S));
printf("(6)輸出從棧頂到棧底的元素:\n");
StackTraverse(S,visit);
printf("(7)讀出棧頂元素:%d\n",GetTop(S,e));
printf("(8)刪除棧頂元素:%d\n",Pop(S,e));
printf("(9)輸出從棧頂到棧底的元素:\n");
StackTraverse(S,visit);
printf("(10)判斷順序棧是否為空\n");
StackEmpty(S);
printf("(11)釋放棧。");
DestroyStack(S);
}
