c_数据结构_栈的实现

傷城~ 2021-12-20 11:07 249阅读 0赞

#include<stdio.h>
    #include<stdlib.h>
    #define STACK_INIT_SIZE 100
    #define STACKINCREMENT 10  //stackincrement
    #define OVERFLOW -2
    #define OK 1
    #define ERROR 0
    typedef struct{
        int *base;
        int *top;
        int stacksize;
    
    }SqStack;
    
    //构建空栈
    int InitStack(SqStack &S){
        S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));
        if(!S.base)exit(OVERFLOW);
        S.top=S.base;      //构建空栈
        S.stacksize=STACK_INIT_SIZE;
        printf("\n空栈创建成功！！\n\n");
        return OK;
    }
    
    //插入元素为栈顶元素
        
    int Push(SqStack &S,int e){
        //插入数据为依次插入
        printf("\n请输入插入的数据：");
        scanf("%d",&e);
        if(S.top-S.base>S.stacksize){
            S.base=(int *)realloc(S.base,S.stacksize+STACKINCREMENT*sizeof(int));//栈满 ，加空间
            if(!S.base)exit(OVERFLOW);
            S.top=S.base+S.stacksize;
            S.stacksize+=STACKINCREMENT;
        }
        *S.top++=e;//存入数据
        printf("\n数据插入成功！！");
        return OK;
    }
    //删除栈顶元素
    int Pop(SqStack &S,int &e){
        //删除元素为最后一个数
        if(S.top==S.base){
            printf("\n栈为空！！无法继续删除！！");
            return ERROR;
        }
        e=*--S.top;
        printf("\n删除的元素为：%d",e);
        printf("\n\n删除成功！！");
        return OK;
    }
    // 判断是否为空栈
    int StackEmpty(SqStack S){
        if(S.top==S.base) return OK;
        else return ERROR;
    
    }
    
    //获取栈顶元素
    int GetTop(SqStack S,int &e){
        if(S.top==S.base) {
            printf("栈为空！！");
            return ERROR;
        }
        e=*(S.top-1);
        printf("\n存储的栈顶元素为：%d",e);
        return OK;
    }
    
    //查找元素
    /*
    int GetElem_Sk(SqStack &S,int i,int &e){
        printf("请输入查找元素的位置：");
        scanf("%d",&i);
    
        if(i<1||i>(S.top-S.base)){
            printf("元素不在栈空间内！！");
            return ERROR;
        }
        e=*(S.base++);
        printf("查找的元素为：%d",e);
        return OK;
    }
    */
    //创建栈，并可存入数据
    int creatlist(SqStack &S){
        int i,n;
        printf("请用户存入数据\n\n请选择存入数据个数：");
        scanf("%d",&n);
        while(n<=0){
            printf("\n存入个数小于了“1”，请重新存入：");
            scanf("%d",&n);
        }
    /*    if(n>(S.top-S.base)){
            printf("-----------");
            S.base=(int *)realloc(S.base,S.stacksize+STACKINCREMENT*sizeof(int));
            if(!S.base)exit(OVERFLOW);
            S.top=S.base+S.stacksize;
            S.stacksize+=STACKINCREMENT;
        }*/
        printf("\n请输入%d个数据：\n\n",n);
    
        for(i=1;i<=n;i++){
            printf("请输入第%d个元素(请回车结束):",i);
            ++S.top;
            scanf("%d",S.top-1);
        }    
        printf("\n存入数据成功！！\n");
        return OK;
    }
    
    //清空栈
    int clear(SqStack &S){
        S.top=S.base;
        printf("栈清空成功！！\n");
    //    creatlist(S);
        return OK;
    }
    //打印栈中元素
    int pr(SqStack S){
        if(S.top==S.base){
            printf("\n\n栈为空！！");
            return ERROR;
        }
        int *p;
        p = S.top;
        printf("栈中元素有：\n");
        while(p>S.base)    {
            p--;
            printf("\n%d",*p);
        }
        return OK;
    }
     //操作菜单
    void OperateMenu(){      
    
        printf("\n\n--------------请选择元素处理方式---------\n\n");
        printf("注：此程序为栈的实现，故只能对序列尾进行元素的插入和删除\n\n");
        printf("0> 退出\n\n");
        printf("1>: 栈尾插入元素\n\n");
        printf("2>: 删除栈尾元素\n\n");
        printf("3>: 打印元素\n\n");
        printf("4>: 获取栈顶元素（存入的最后一个元素）\n\n");
        printf("5>: 清空原栈\n\n");
        printf("6>:批量输入\n\n");
        printf("请选择对元素的处理：");
    }
    void main(){
        int w=0,k,boo=1,e=0;
        SqStack S;
        printf("注：此测试过程输入值应全为数字\n\n");
        printf("请用户选择创建栈或退出程序：\n\n");
        printf("创建栈请输入：'1'\n\n");
        printf("退出请选择'0'或 其它！！\n\n");
        printf("请选择：");
        scanf("%d",&w);
        if(w==1){
            InitStack(S);    
    //      creatlist(S);
            OperateMenu();
            scanf("%d",&k);
            while(k){
                switch(k){
                    case 0:break;
                    case 1:Push(S,e);
                        break;    
                    case 2:Pop(S,e);
                        break;
                    case 3:boo=pr(S);
                        if(boo)
                            printf("\n\n打印成功！！");
                        else
                            printf("打印失败！！");
                        break;
                    case 4:boo=GetTop(S,e);
                        if(boo)
                            printf("\n\n获取成功！！");
                        else
                            printf("获取失败！！");
                        break;
                    case 5:clear(S);
                        break;
                    case 6:creatlist(S);break;
    
                }
                OperateMenu();
                scanf("%d",&k);
            }
        
        }
    
    }

转载于:https://www.cnblogs.com/Vera-y/p/9971239.html