实验二栈和队列(基本操作)样本.doc

文档介绍：试验二栈和队列1、试验目标:熟悉栈特点(优异后出)及栈基础操作,如入栈、出栈等,掌握栈基础操作在栈次序存放结构和链式存放结构上实现;熟悉队列特点(优异先出)及队列基础操作,如入队、出队等,掌握队列基础操作在队列次序存放结构和链式存放结构上实现。2、试验要求:复习书本中相关栈和队列知识;用C语言完成算法和程序设计并上机调试经过;撰写试验汇报,给出算法思绪或步骤图和具体实现(源程序)、算法分析结果(包含时间复杂度、空间复杂度和算法优化设想)、输入数据及程序运行结果(必需时给出多个可能输入数据和运行结果)。3、试验内容[试验1]栈次序表示和实现试验内容和要求:编写一个程序实现次序栈多种基础运算,并在此基础上设计一个主程序,完成以下功效:(1)初始化次序栈(2)插入元素(3)删除栈顶元素(4)取栈顶元素(5)遍历次序栈(6)置空次序栈分析:栈次序存放结构简称为次序栈,它是运算受限次序表。对于次序栈,入栈时,首先判定栈是否为满,栈满条件为:p->top==MAXNUM-1,栈满时,不能入栈;不然出现空间溢出,引发错误,这种现象称为上溢。出栈和读栈顶元素操作,先判栈是否为空,为空时不能操作,不然产生错误。通常栈空作为一个控制转移条件。注意:(1)次序栈中元素用向量存放(2)栈底位置是固定不变,可设置在向量两端任意一个端点(3)栈顶位置是伴随进栈和退栈操作而改变,用一个整型量top(通常称top为栈顶指针)来指示目前栈顶位置#include<>#include<>typedefintSElemType;typedefintStatus;#defineINIT_SIZE100#defineSTACKINCREMENT10#defineOk1#defineError0#rue1#defineFalse0typedefstruct{ SElemType*base; SElemType*top; intstacksize;}SqStack;//初始化栈StatusInitStack(SqStack*s){ s->base=(SElemType*)malloc(INIT_SIZE*sizeof(SElemType)); if(!s->base) { puts("存放空间分配失败!"); returnError; } s->top=s->base; s->stacksize=INIT_SIZE; returnOk;}//清空栈StatusClearStack(SqStack*s){s->top=s->base;returnOk;}//栈是否为空StatusStackEmpty(SqStack*s){if(s->top==s->base)returnTrue;elsereturnFalse;}//销毁栈StatusDestroy(SqStack*s){ free(s->base); s->base=NULL; s->top=NULL; s->stacksize=0; returnOk;}//取得栈顶元素StatusGetTop(SqStack*s,SElemType&e){ if(s->top==s->base)returnError; e=*(s->top-1); returnOk;}//压栈StatusPush(SqStack*s,SElemTypee){ if(s->top-s->base>=s->stacksize) { s->base=(SElemType*)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!s->base) { puts("存放空间分配失败!"); returnError; } s->top=s->base+s->stacksize; s->stacksize+=STACKINCREMENT; } *s->top++=e; returnOk;}//弹栈StatusPop(SqStack*s,SElemType*e){ if(s->top==s->base)returnError; --s->top; *e=*(s->top); returnOk;}//遍历栈StatusStackTraverse(SqStack*s,Status(*visit)(SElemType)){SElemType*b=s->base;SElemType*t=s->top;while(t>b)visit(*b++);printf("\n");returnOk;}Statusvisit(SElemTypec){printf("%d",c);returnOk;}intmain(){ SqStacka; SqStack*s=&a; SElem