C語言數據結構之棧簡單操作

2020-01-26 14:02:59

字體：大中小

來源：轉載

供稿：網友

C語言數據結構之棧簡單操作

實驗：

編寫一個程序實現順序棧的各種基本運算，并在此基礎上設計一個主程序，完成如下功能：

（1）初始化順序棧
（2）插入元素
（3）刪除棧頂元素
（4）取棧頂元素
（5）遍歷順序棧
（6）置空順序棧

分析:

棧的順序存儲結構簡稱為順序棧,它是運算受限的順序表。

對于順序棧，入棧時，首先判斷棧是否為滿，棧滿的條件為：p->top= =MAXNUM-1，棧滿時，不能入棧; 否則出現空間溢出，引起錯誤，這種現象稱為上溢。

出棧和讀棧頂元素操作，先判棧是否為空，為空時不能操作，否則產生錯誤。通常棧空作為一種控制轉移的條件。

注意：

（1）順序棧中元素用向量存放
（2）棧底位置是固定不變的，可設置在向量兩端的任意一個端點
（3）棧頂位置是隨著進棧和退棧操作而變化的，用一個整型量top（通常稱top為棧頂指針）來指示當前棧頂位置

順序棧的實現：

#include <stdio.h> #include <malloc.h>  typedef int SElemType; typedef int Status; #define INIT_SIZE 100 #define STACKINCREMENT 10 #define Ok 1 #define Error 0 #define True 1 #define False 0 typedef struct {   SElemType *base;   SElemType *top;   int stacksize; }SqStack;  //初始化棧 Status InitStack(SqStack *s) {   s->base = (SElemType *)malloc(INIT_SIZE * sizeof(SElemType));   if(!s->base)   {     puts("存儲空間分配失敗！");     return Error;   }   s->top = s->base;   s->stacksize = INIT_SIZE;   return Ok; }  //清空棧 Status ClearStack(SqStack *s)  {   s->top = s->base;   return Ok;  }  //棧是否為空 Status StackEmpty(SqStack *s)  {   if(s->top == s->base)    return True;   else    return False;  }  //銷毀棧 Status Destroy(SqStack *s) {   free(s->base);   s->base = NULL;   s->top = NULL;   s->stacksize=0;   return Ok; }  //獲得棧頂元素 Status GetTop(SqStack *s, SElemType &e) {   if(s->top == s->base) return Error;   e = *(s->top - 1);   return Ok; }  //壓棧 Status Push(SqStack *s, SElemType e) {   if(s->top - s->base >= s->stacksize)//棧滿   {     s->base = (SElemType *)realloc(s->base, (s->stacksize + STACKINCREMENT) * sizeof(SElemType));     if(!s->base)     {       puts("存儲空間分配失敗！");       return Error;     }     s->top = s->base + s->stacksize;//修改棧頂位置     s->stacksize += STACKINCREMENT;//修改棧長度    }   *s->top++ = e;   return Ok; }  //彈棧 Status Pop(SqStack *s, SElemType *e) {   if(s->top == s->base) return Error;   --s->top;   *e = *(s->top);   return Ok; }  //遍歷棧 Status StackTraverse(SqStack *s,Status(*visit)(SElemType))  {    SElemType *b = s->base;//此處不能直接用base或top移動，即不能改變原棧的結構    SElemType *t = s->top;   while(t > b)    visit(*b++);   printf("/n");   return Ok;  }  Status visit(SElemType c)  {   printf("%d ",c);   return Ok;  }

測試代碼：

int main() {   SqStack a;   SqStack *s = &a;   SElemType e;   InitStack(s);   int n;   puts("請輸入要進棧的個數：");   scanf("%d", &n);   while(n--)   {     int m;     scanf("%d", &m);     Push(s, m);   }   StackTraverse(s, visit);   puts("");   puts("8進棧后：");   Push(s, 8);   StackTraverse(s, visit);   puts("");   Pop(s, &e);   printf("出棧的元素是：%d/n", e);   printf("元素出棧后事實上并沒有清除，依然存在于內存空間，所謂的出棧只是指針移動，出棧的元素是%d/n", *s->top);//判斷出棧后元素是否還存在于內存中   Destroy(s);   return 0; }

運行結果：