数据结构实验2顺序栈的建立及基本操作课件.ppt

《数据结构实验2顺序栈的建立及基本操作课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本课程实验要求书写实验报告，报告内容包括：(1)学生姓名、学号、班级；(2)实验题目；(3)实验目的；(4)实验内容及代码;(5)实验心得。实验课成绩=考勤成绩(10%)+实验报告成绩(20%)实验报告：共收4份实验报告数据结构实验实验二顺序栈的建立及基本操作实验目的了解顺序栈的结构特点及有关概念掌握顺序栈建立及基本操作算法实验二顺序栈的建立及基本操作实验内容实现顺序栈初始化实现顺序栈的基本操作:进栈、获取栈顶元素、出栈、输出栈中元素顺序存储结构：顺序栈顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设

2、一个位置指针top(栈顶指针)来动态地指示栈顶元素在顺序栈中的位置.实验要点及说明：顺序栈的存储结构定义#defineSTACK_INIT_SIZE100;//存储空间初始分配量#defineSTACKINCREMENT10;//存储空间分配增量typedefintstatus;typedefstruct{int *base;//栈底指针，顺序栈中始终始终指向栈底位置int*top;//栈顶指针int stacksize;//栈当前可使用的最大容量}sqstack;实验要点及说明：实验要点及说明：栈是一种只允许在表的一端进行插入或删除操作的线性表，对栈元素的操作应符合先进后出的原

3、则。只允许插入、删除操作的一端称为栈顶，另一端称为栈底。插入操作称为进栈或入栈删除操作称为退栈或出栈，当栈中没有任何元素时称为空栈。顺序栈的存储结构定义栈不存在：base=NULL栈空：top=base栈满：top-base>=stacksizetop指向栈顶元素的下一个位置实验要点及说明：顺序栈基本操作的实现——初始化statusinitstack(sqstack&s){//构造一个空栈由指针S指出s.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));if(!s.base)exit(OVERFLOW);//存储分配失败s.top=s.

4、base;s.stacksize=STACK_INIT_SIZE;returnOK;}//initStack实验要点及说明：AACBABAtop核心语句：top=L;顺序栈中的PUSH函数statuspush(ElemTypex){if(top>M){上溢}elsev[top++]=x;}Push(B);Push(C);Push(D);toptoptoptop低地址LPush(A);高地址MBCD顺序栈基本操作的实现——入栈例如用栈存放(A，B，C，D)注意遵循“后进先出”原则顺序栈基本操作的实现——入栈例如用栈存放(A，B，C，D)注意遵循“后进先出”原则实验要点及说明：顺序栈

5、基本操作的实现——入栈statuspush(sqstack&s,inte){//元素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;//插入新的栈顶元素，指针top增1returnOK;}

6、//pushT(n)=O(1)实验要点及说明：BAtoptopCABDCBAtopDCBAtop低地址L高地址MD核心语句：Pop();Pop();Printf(Pop());顺序栈中的POP函数statusPop(){if(top=L){下溢}else{y=v[--top];return(y);}}顺序栈基本操作的实现——出栈例如从栈中取出B注意遵循“后进先出”原则Atop实验要点及说明：顺序栈基本操作的实现——出栈statuspop(sqstack&s,int&e){//若栈不空，删除栈顶元素用e返回其值，并返回OK，否则返回ERROR，栈中下一元素所在位置成为新的栈顶if（

7、s.top==s.base）returnERROR;//栈空e=*--s.top;//删除栈顶元素，指针top减1returnOK;}//popT(n)=O(1)实验要点及说明：e=*(s.top-1);*s.top--;顺序栈基本操作的实现——获取栈顶元素statusgettop(sqstack&s,int&e){//若栈不空，用e返回栈顶元素，并返回OK，则返ERRORif（s.top==s.base）returnERROR;//栈空e=*(s.top-1);//取栈顶元素，