【数据结构】顺序栈（栈底栈顶指针版）代码实现c

淩亂°似流年 2021-09-20 14:28 382阅读 0赞

顺序栈有两种描述

typedef struct {
        ElemType data[MaxSize];
        int top;　　　　//存放栈顶元素在数组中的下标
    }SqStack;

typedef struct{
        ElemType *base;
        ElemType *top;
        int MaxSize;    //当前已分配的空间
    }SqStack;

今天拿出来的是第二种，第一种会在之后的时间里面补上  
可以实现的算法有

Status InitStack(SqStack &S); 
    //构造一个空栈 
    Status DestroyStack(SqStack &S); 
    //销毁栈，销毁后栈不存在 
    Status ClearStack(SqStack &S); 
    //清空栈 
    Status StackEmpty(SqStack S); 
    //若s为空栈，返回true，否则返回false 
    Status StackLength(SqStack S); 
    //返回栈的长度 
    Status GetTop(SqStack S,SElemType &e); 
    //若栈不空，用e返回栈顶元素，并返回OK，否则返回ERROR 
    Status Push(SqStack &S,SElemType e); 
    //插入元素e为新的栈顶元素 
    Status Pop(SqStack &S,SElemType &e);  
    //若栈不空，删除s的栈顶元素，用e返回其值，并返回OK，否则返回false 
    Status Print(SqStack S);
    //输出该栈

下面是源代码以及运行效果.jpg

#include <iostream>
    #include <stdio.h>
    #include <malloc.h>
    
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2 
    #define STACK_INIT_SIZE 100
    #define STACKINCREMENT 10
    
    typedef float SElemType;
    typedef int Status;
    typedef struct{ 
    	SElemType *base;	//构造之前销毁之后，base的值应该为NULL 
    	SElemType *top; 	//栈顶指针 
    	int stacksize;		//当前已分配的存储空间 ，以元素为单位 
    }SqStack;
    
    Status InitStack(SqStack &S); 
    //构造一个空栈 
    Status DestroyStack(SqStack &S); 
    //销毁栈，销毁后栈不存在 
    Status ClearStack(SqStack &S); 
    //清空栈 
    Status StackEmpty(SqStack S); 
    //若s为空栈，返回true，否则返回false 
    Status StackLength(SqStack S); 
    //返回栈的长度 
    Status GetTop(SqStack S,SElemType &e); 
    //若栈不空，用e返回栈顶元素，并返回OK，否则返回ERROR 
    Status Push(SqStack &S,SElemType e); 
    //插入元素e为新的栈顶元素 
    Status Pop(SqStack &S,SElemType &e);  
    //若栈不空，删除s的栈顶元素，用e返回其值，并返回OK，否则返回false 
    Status Print(SqStack S);
    //输出该栈
    
    int main(void){ 
    	SqStack S;
    	SElemType e;
    	int n,i;
    	InitStack(S);
    	
    	printf("要在栈中输入几个元素：");
    	scanf("%d",&n);
    	printf("请输入这几个元素：");
    	for(i=0;i<n;i++)
    	{ 
    		scanf("%f",S.top);
    		S.top++;
    	}
    	printf("栈中的元素为：");
    	Print(S);
    	
    	printf("请输入在栈顶插入的元素：");
    	scanf("%f",&e);
    	Push(S,e);
    	printf("插入后的栈为：");
    	Print(S);
    	
    	Pop(S,e); 
        printf("\n删除栈顶的元素为：%.2f",e);
        printf("\n删除后的栈为：");
        Print(S);
        
        StackLength(S); //返回栈的长度 
        ClearStack(S); //清空栈 
        StackEmpty(S); //查看栈是否为空 
        DestroyStack(S); //销毁栈 
    	return 0;
    } 
    
    //构造空栈S
    Status InitStack(SqStack &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; 
    } 
    //返回栈顶元素
    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,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType)); 
    		//判断分配存储失败与否 
    		if(!S.base)
    		{ 
    			exit(OVERFLOW);
    		}
    		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;
    	}
    	//将删除的元素取出。因为指针在栈顶元素的下一个位置上，所以被取出的元素（当前top）不会被看做是栈元素 
    	e=*(--S.top);
    	return OK;
    } 
    //从栈底到栈顶输出元素 
    Status Print(SqStack S){ 
    	SElemType *p;
    	if(S.base==S.top)
    	{ 
    		return ERROR;
    	}
    	else
    	{ 
    		p=S.base;
    		while(p!=S.top)
    		{ 
    			printf("%.2f ",*p++);
    		} 
    		printf("\n");
    		return OK;
    	}	
    }
    //销毁栈 
    Status DestroyStack(SqStack &S){ 
    	free(S.base); 
    	S.base=NULL;
    	S.top=NULL;
    	S.stacksize=0;
    	if(S.base==NULL)
    	{ 
    		printf("销毁成功！");
    		return OK;
    	}
    	else 
    	{ 
    	printf("销毁失败！"); 
    	return ERROR;
    	}
    }
    //清空栈 
    Status ClearStack(SqStack &S){ 
    	S.top=S.base;
    	return OK;
    }
    
    Status StackEmpty(SqStack S){ 
    	if(S.top==S.base)
    	{ 
    		printf("该栈是空栈！\n");
    		return OK;
    	}
    	else
    	{ 
    		printf("该栈不是空栈！\n");
    		return ERROR;
    	}
    }
    Status StackLength(SqStack S){ 
    	printf("该栈的长度是：%d\n",S.top-S.base);
    	return OK;
    }

效果图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyMjA5Mw_size_16_color_FFFFFF_t_70]  
各位程序员们，加油！  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyMjA5Mw_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyMjA5Mw_size_16_color_FFFFFF_t_70]: /images/20210920/1f874d569e69413f8d1b9d75129f1257.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyMjA5Mw_size_16_color_FFFFFF_t_70 1]: /images/20210920/f5d39b4dac3c489e9c7d344a7532f014.png