C语言数据结构 栈的基础操作
实现了栈的基本操作,包括入栈出栈,以及书上没有写的销毁栈等操作,并对代码进行了详细的注释
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)是限定仅在表尾进行插入或删除操作的线性表**栈顶(top)和栈底(bottom)相等,代表为空栈***///SElemType是某个确定的、将由用户自行定义的、含某个关系运算的数据对象typedef int SElemType;//函数结果状态代码#define TRUE 1 #define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1 //不可行#define MY_OVERFLOW -2 //溢出/**********栈的顺序存储表示**********/#define STACK_INIT_SIZE 100 //存储空间初始分配量#define STACKINCREMENT 10 //存储空间分配增量typedef struct{ SElemType *base; //在栈构造之前和销毁之后,base的值为NULL SElemType *top; //栈顶指针 int stacksize; //当前已分配}SqStack;/**********基本操作的函数原型说明**********///构造一个空栈SStatus InitStack(SqStack &S); //销毁栈S,S不再存在Status DestroyStack(SqStack &S);//把S置为空栈Status ClearStack(SqStack &S);//若栈S为空栈,则返回TURE,否则返回FALSEStatus StackEmpty(SqStack S); //返回S的元素个数,即栈的长度int StackLength(SqStack S);//若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERRORStatus GetTop(SqStack S, SElemType &e); //插入元素e为新的栈顶元素Status Push(SqStack &S, SElemType e);//若栈不空,则删除S的栈顶元素,用e新栈顶的值,并返回OK;否则返回ERROR;Status Pop(SqStack &S, SElemType &e);//从栈底到栈顶依次对栈中每个元素调用函数visit();一旦visit()失败,则操作失败Status StackTraverse(SqStack S, Status(* visit)(SElemType));//visit()函数Status visit(SElemType e);//测试函数Status TestMyStack();#endif MYSTACK_H_
MyStack.c
#include "MyStack.h"Status InitStack(SqStack &S){ //构造一个空栈S S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if(!S.base){ //存储分配失败 printf("InitStack: malloc err\n"); exit(MY_OVERFLOW); } S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;}//InitStackStatus DestroyStack(SqStack &S){ if(!S.base){ printf("DestroyStack: Stack does not exist\n"); exit(MY_OVERFLOW); }//在调用malloc的时候,系统会记住你申请的这块连续空间的起始地址以及这块空间的大小,//释放free的时候,只要把这个起始地址告诉系统,系统自然就知道要释放多大的空间。 free(S.base); S.top = NULL; S.base = NULL; S.stacksize = 0; return OK;}//DestroyStackStatus ClearStack(SqStack &S){ if(!S.base){ printf("ClearStack: Stack does not exist\n"); exit(MY_OVERFLOW); } S.top = S.base; return OK; }//ClearStackStatus StackEmpty(SqStack S){ if(S.top == S.base){ return TRUE; } else{ return FALSE; }}//StackEmptyint StackLength(SqStack S){ return S.top - S.base;}//StackLengthStatus 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;}//GetTopStatus 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){ printf("Push: realloc error\n"); } S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = e; //*S.top = e; S.top++; return OK;}//PushStatus Pop(SqStack &S, SElemType &e){ //若栈不空,则删除S的栈顶元素,用e返回新栈顶的值,并返回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;}//PopStatus StackTraverse(SqStack S, Status(* visit)(SElemType)){ while(S.top > S.base){ visit(*S.base++); } printf("\n"); return OK; }//StackTraverseStatus visit(SElemType e){ printf("%d ",e) ; return OK;}//visitStatus 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,栈的长度为%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//主函数int main(){ TestMyStack(); system("pause"); return 0;}
运行结果
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!