动态顺序栈 C语言

深藏阁楼爱情的钟 2022-12-12 15:06 181阅读 0赞

## 数据结构C语言动态顺序栈的实现和表达 ##

动态顺序表相比于静态顺序表只是在定义上多个需要用malloc申请空间，并且释放；在结构上比静态增加了能增加最大容纳长度的函数。

#include <stdio.h>
    #include <stdlib.h> 
    #define Initsize 10 //静态顺序栈存储的最大空间 
    #define OVERFLOW 1 //定义栈的溢出 
    
    typedef struct 
    { 
    	int *base;//栈低指针 
    	int *top;//栈顶指针 
    	int MaxSize;//栈当前最大容量 
    }SqStack;
    
    void InitStack(SqStack &S)//栈的初始化 
    { 
    	S.base = (int*)malloc(sizeof(int)*Initsize);//申请一篇连续地址的空间 ，并使该空间的首地址返回给S.base 
    	S.MaxSize = Initsize;//栈的最大容量赋值 
    	if(S.base == NULL)//判断有没有申请到 
    		exit(OVERFLOW);
    	S.top = S.base; //栈的初始化，栈低和栈顶指向的统一位置 
    }
    
    int Push(SqStack &S,int e)//进栈 
    { 
    	if(S.top-S.base==S.MaxSize)//判断栈是否为满 
    	{ 
    		printf("栈满！\n");
    		return 0;
    	}
    	*S.top++ = e;//压入栈的值 
    	return 0; 
    }
    
    int Length(SqStack S)//栈长 
    { 
    	return S.top-S.base;
    }
    
    int Pop(SqStack &S)//使栈顶元素出栈，并返回栈顶元素，且栈长减一 
    { 
    	if(Length(S))
    	{ 
    		printf("空栈！\n");
    		return 0; 
    	} 
    	S.top--;//栈顶减一 
    	return *S.top;//输出栈顶元素 
    }
    
    void IncreaseSize(SqStack &S,int len)//动态增加栈长 
    { 
    	int a = Length(S),//定义一个变量a等于栈长 
    		i;//循环变量 
    	printf("%d ",Length(S)); 
    	int *p;
    	p = S.base;//定义一个指针p指向栈低首元素 
    	S.base = (int*)malloc(sizeof(int)*(Initsize+len));//对栈重新申请一个更大的连续空间 
    	S.MaxSize = Initsize + len;//使栈的最大容量变大 
    	S.top = S.base;
    	for(i=0;i<a;i++)//利用循环，使老的栈区数据依次写入新的栈区中 
    		*S.top++ = p[i];	
    	printf("%d ",Length(S)); 
    	free(p);//最后把老的栈给释放了 
    }
    
    int main()
    { 
    	SqStack S;
    	InitStack(S);//初始化栈 
    	int i;
    	for(i=1;i<110;i=i+10)//利用循环使数据以此进入栈中 
    		Push(S,i);//进栈 
    	printf("当前栈长：%d\n",Length(S));//栈长 
    	printf("栈顶元素：%d\n",Pop(S));
    	printf("将栈顶元素导出后栈长：%d\n",Length(S));
    	IncreaseSize(S,1);//增加栈长 
    	free(S.base);
    	return 0;
    }

（完）