【数据结构】动态顺序栈的增删改查

太过爱你忘了你带给我的痛 2022-08-25 08:29 196阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    
    #define INITIAL_STACK_SIZE 100
    #define INCREASE_STACK_SIZE 10   // 大于一个元素的内存大小
    
    typedef int ElemType;
    
    typedef struct Stack
    {
    	ElemType *top;
    	ElemType *base;
    	int stacksize;   // 记录栈的大小
    }Stack,*Pstack;
    
    void InitStack(Pstack L);
    void Push(Pstack L,ElemType i);
    ElemType Pop(Pstack L);
    void DestroyStack(Pstack L);
    bool StackEmpty(Pstack L);
    int StackLength(Pstack L);
    ElemType GetTop(Pstack L);
    void StackTraverse(Pstack L);
    
    void main ()
    {
    	int size;
    
    	Stack stack;
    	Pstack L = &stack;
    	InitStack(L);
    
    	printf("请输入栈大小: ");
    	scanf("%d",&size);
    
    	for (int i = 1; i <= size; i++)
    	{
    		Push(L,i);
    	}
    
    	StackTraverse(L);
    
    	if (StackEmpty)
    	{
    		printf("栈顶元素为：%d\n",GetTop(L));
    		Pop(L);
    		printf("弹栈 弹出栈顶元素：\n");
    		StackTraverse(L);
    
    		printf("栈内的元素个数为：%d\n",StackLength(L));
    	}
    
    	DestroyStack(L);
    
    	L = NULL;
    }
    
    
    void InitStack(Pstack L)
    {
    	L->base = (ElemType *)malloc(INITIAL_STACK_SIZE * sizeof(ElemType));
    
    	if (! L->base)
    		exit(-1);
    	L->top = L->base;
    	L->stacksize = INITIAL_STACK_SIZE;
    }
    
    void Push(Pstack L,ElemType i)
    {
    	if (L->top - L->base >= L->stacksize){
    		L->base =  (ElemType *)realloc(L->base,(INITIAL_STACK_SIZE+INCREASE_STACK_SIZE)* sizeof(ElemType));
    		L->top = L->base + L->stacksize;
    		L->stacksize += INCREASE_STACK_SIZE;
    	}
    
    	*(L->top++) = i;
    }
    
    ElemType Pop(Pstack L)
    {
    	if (L->top != L->base) // 栈不为空
    	{
    		i = * -- L->top;
    	}
    
    	return i;
    }
    
    void DestroyStack(Pstack L)
    {
    	for (ElemType * p = L->base; p < L->top; p++)
    	{
    		*p = 0;
    	}
    	L->top = L->base = NULL;
    }
    
    bool StackEmpty(Pstack L)
    {
    	if (L->base != L->top)
    		return false;
    	else
    		return true;
    }
    
    int StackLength(Pstack L)
    {
    	int num = 0;
    
    	for (ElemType * p = L->base; p < L->top; p++)
    	{
    		num++;
    	}
    
    	return num;
    }
    
    ElemType GetTop(Pstack L)
    {
    	ElemType e = * (L->top-1);
    
    	return e;
    }
    
    void StackTraverse(Pstack L)
    {
    	ElemType * p = L->base;
    
    	while (p != L->top)
    	{
    		printf("%d\t",*p++);
    	}
    
    	printf("\n");
    }