栈的顺序存储结构顺序栈

《栈的顺序存储结构顺序栈》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3．2栈的顺序存储结构---顺序栈栈的顺序存储结构简称顺序栈，它是运算受限的顺序表。顺序栈的存储结构是：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。3．2．1顺序栈的类型定义类似于顺序表，用一维数组描述顺序栈中的数据元素的存储区域，并预设一个数组的最大空间。描述顺序栈的通常的习惯做法是以top=0表示空栈，鉴于C语言中数组的下标约定是从0开始，则当以C作描述语言时，如此设定会带来很大不便；另一方面，由于栈在使用过程中所需最大空间的大小很难估计，因

2、此，一般来说，在初始化设空栈时不应限定栈的最大容量。一个较合理的做法是：先为栈分配一个基本容量，然后在应用过程中，当栈的空间不够使用时再逐段扩大。为此，可设定两个常量：STACKCSL（存储空间初始分配量）和STACKZL（存储空间分配增量）。下面给出顺序栈的类型定义：#include"stdlib.h"#defineSTACKCSL64/*顺序栈存储空间初始分配量*/#defineSTACKZL8/*顺序栈存储空间分配增量*/typedefintElemType;/*栈元素的数据类型定义，它可以是任意的，

3、具体问题时只需根据需要修改本定义语句即可*/typedefstruct{ElemType*top;/*栈顶指针*/ElemType*bottom;/*栈底指针*/intstacksize;/*当前已分配的存储空间，以栈元素为单位*/}seqstack;/*顺序栈类型定义*/seqstack*seqs;/*seqs是顺序栈类型指针*/其中，stacksize指示栈的当前可使用的最大容量，初始化栈时，stacksize的值等于STACKCSL，以后根据需要按分配增量STACKZL增长。bottom是栈底指针，在

4、顺序栈中，它始终指向栈底的位置，如果bottom的值等于NULL，就意味着栈结构不存在。top是栈顶指针，其初值指向栈底，也就是说top=bottom可作为栈空的标记。每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减一。所以，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。图3.2表示了栈顶指针top和顺序栈中数据元素之间的对应关系。┋┋185┋┋8513/13┋┋　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　top　　　　　　　　　　　　

5、　　　　　　　　　　　　　　　　　　　　　　　　　　top　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　top　　　　　　　　　　　　　　　　　　　　　　　　　　　bottom　　　　　bottom　　　　　bottom　　　　　　　　　(a)空栈(b)元素5、8、1进栈(c)元素1出栈top┋┋485┋34859┋┋485toptoptopbottombottombottom(d)元素4、3进栈(e)元素3

6、出栈（f）栈满图3.2栈顶指针与数据元素的关系3．2．2基本运算的实现上述顺序栈的类型定义以及本小节将介绍的基本运算操作均放在文件“seqstack.c”中，使用时需要用命令：#include"seqstack.c"将其包含到具体的应用程序中去。由于顺序栈的插入、删除只在栈顶进行，因此顺序栈的基本操作比顺序表要简单得多。在顺序栈上可以实现初始化栈、进栈、出栈、判栈空、取栈顶元素等几种基本运算，具体算法如下：1．初始化栈该算法用于建立一个容量为STACKCSL13/13的空顺序栈ss。建立时首先使用mallo

7、c函数进行内存储区的分配，并将所分配的存储区的起始地址赋给栈底指针bottom。如果bottom不为空，说明分配成功，否则说明分配失败。成功时进行置空栈的操作，失败则退出。具体算法如下：算法3.1voidinitstack(seqstack*ss)/*初始化一个顺序栈ss*/{ss->bottom=(ElemType*)malloc(STACKCSL*sizeof(ElemType));if(!ss->bottom){printf(“初始化栈失败”);return;};ss->top=ss->bottom;

8、ss->stacksize=STACKCSL;printf("初始化栈成功！");}2.进栈该算法用于向顺序栈ss的栈顶插入一个元素x。算法首先判断栈是否已满，如果栈不满，就直接进行插入操作，否则就使用realloc函数为该顺序栈再多分配增量STACKZL个元素的存储空间。如果分配成功，则修改栈顶指针top的位置和栈的容量stacksize，然后将元素x插入在栈顶位置。具体算法如下：算法3.2Voidpush(s