您好,登錄后才能下訂單哦!
C語(yǔ)言數(shù)據(jù)結(jié)構(gòu) 棧的基礎(chǔ)操作
實(shí)現(xiàn)了棧的基本操作,包括入棧出棧,以及書上沒(méi)有寫的銷毀棧等操作,并對(duì)代碼進(jìn)行了詳細(xì)的注釋
MyStack.h
/* * Include.h * * Created on: 2016.11.23 * Author: Jack Cui */ #ifndef MYSTACK_H_ #define MYSTACK_H_ #include <stdlib.h> #include <stdio.h> #include <malloc.h> /*棧(Stack)是限定僅在表尾進(jìn)行插入或刪除操作的線性表 **棧頂(top)和棧底(bottom)相等,代表為空棧 ** */ //SElemType是某個(gè)確定的、將由用戶自行定義的、含某個(gè)關(guān)系運(yùn)算的數(shù)據(jù)對(duì)象 typedef int SElemType; //函數(shù)結(jié)果狀態(tài)代碼 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 //不可行 #define MY_OVERFLOW -2 //溢出 /**********棧的順序存儲(chǔ)表示**********/ #define STACK_INIT_SIZE 100 //存儲(chǔ)空間初始分配量 #define STACKINCREMENT 10 //存儲(chǔ)空間分配增量 typedef struct{ SElemType *base; //在棧構(gòu)造之前和銷毀之后,base的值為NULL SElemType *top; //棧頂指針 int stacksize; //當(dāng)前已分配 }SqStack; /**********基本操作的函數(shù)原型說(shuō)明**********/ //構(gòu)造一個(gè)空棧S Status InitStack(SqStack &S); //銷毀棧S,S不再存在 Status DestroyStack(SqStack &S); //把S置為空棧 Status ClearStack(SqStack &S); //若棧S為空棧,則返回TURE,否則返回FALSE Status StackEmpty(SqStack S); //返回S的元素個(gè)數(shù),即棧的長(zhǎng)度 int StackLength(SqStack S); //若棧不空,則用e返回S的棧頂元素,并返回OK;否則返回ERROR Status GetTop(SqStack S, SElemType &e); //插入元素e為新的棧頂元素 Status Push(SqStack &S, SElemType e); //若棧不空,則刪除S的棧頂元素,用e新棧頂?shù)闹?,并返回OK;否則返回ERROR; Status Pop(SqStack &S, SElemType &e); //從棧底到棧頂依次對(duì)棧中每個(gè)元素調(diào)用函數(shù)visit();一旦visit()失敗,則操作失敗 Status StackTraverse(SqStack S, Status(* visit)(SElemType)); //visit()函數(shù) Status visit(SElemType e); //測(cè)試函數(shù) Status TestMyStack(); #endif MYSTACK_H_
MyStack.c
#include "MyStack.h" Status InitStack(SqStack &S){ //構(gòu)造一個(gè)空棧S S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if(!S.base){ //存儲(chǔ)分配失敗 printf("InitStack: malloc err\n"); exit(MY_OVERFLOW); } S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; }//InitStack Status DestroyStack(SqStack &S){ if(!S.base){ printf("DestroyStack: Stack does not exist\n"); exit(MY_OVERFLOW); } //在調(diào)用malloc的時(shí)候,系統(tǒng)會(huì)記住你申請(qǐng)的這塊連續(xù)空間的起始地址以及這塊空間的大小, //釋放free的時(shí)候,只要把這個(gè)起始地址告訴系統(tǒng),系統(tǒng)自然就知道要釋放多大的空間。 free(S.base); S.top = NULL; S.base = NULL; S.stacksize = 0; return OK; }//DestroyStack Status ClearStack(SqStack &S){ if(!S.base){ printf("ClearStack: Stack does not exist\n"); exit(MY_OVERFLOW); } S.top = S.base; return OK; }//ClearStack Status StackEmpty(SqStack S){ if(S.top == S.base){ return TRUE; } else{ return FALSE; } }//StackEmpty int StackLength(SqStack S){ return S.top - S.base; }//StackLength Status GetTop(SqStack S, SElemType &e){ ////若棧不空,則用e返回S的棧頂元素,并返回OK;否則返回ERROR if(S.top == S.base){ printf("GetTop: Stack is empty\n"); return ERROR; } e = *(S.top - 1); return OK; }//GetTop Status Push(SqStack &S, SElemType e){ //插入元素e為新的棧頂元素 if(S.top - S.base >= S.stacksize){ //棧滿,追加存儲(chǔ)空間 S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType)); if(!S.base){ printf("Push: realloc error\n"); } S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = e; //*S.top = e; S.top++; return OK; }//Push Status Pop(SqStack &S, SElemType &e){ //若棧不空,則刪除S的棧頂元素,用e返回新棧頂?shù)闹?,并返回OK,否則返回ERROR; if(S.top == S.base){ printf("Pop: Stack is empty\n"); return ERROR; } e = *--S.top; //S.top--; e = *S.top; return OK; }//Pop Status StackTraverse(SqStack S, Status(* visit)(SElemType)){ while(S.top > S.base){ visit(*S.base++); } printf("\n"); return OK; }//StackTraverse Status visit(SElemType e){ printf("%d ",e) ; return OK; }//visit Status TestMyStack(){ SElemType j; SqStack s; SElemType e; if(InitStack(s) == OK) for(j = 1; j <= 12; j++) { Push(s,j); } printf("棧中的元素依次為:"); StackTraverse(s,visit); Pop(s, e); printf("彈出的棧頂元素 e=%d\n", e); printf("??辗瘢?d(1:是 0:否)\n", StackEmpty(s)); GetTop(s, e); printf("棧頂元素 e=%d,棧的長(zhǎng)度為%d\n", e, StackLength(s)); ClearStack(s); printf("清棧后,棧是否為空:%d(1:空 0:否)\n",StackEmpty(s)); DestroyStack(s); printf("銷毀棧后,s.top = %u s.base= %u s.stacksize=%d\n",s.top,s.base,s.stacksize); return 0; }//TestMyStack //主函數(shù) int main(){ TestMyStack(); system("pause"); return 0; }
運(yùn)行結(jié)果
感謝閱讀,希望能幫助到大家,謝謝大家對(duì)本站的支持!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。