《数据结构》实验二 栈和队列.docx

第H'F工生战数据结构实验指导及报告书2022/2022学年第二学期姓名：学号：班级：指导教师：计算机科学与工程学院2022实验二栈和队列一、实验目的1、掌握栈的结构特性及其入栈，出栈操作；2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。二、实验内容和要求1、阅读下面程序，将函数PUSh和函数Pop补充完整。要求输入元素序列12345e,运行结果如下所示。# include<stdio.h># indude<malloc.h># defineERRORO# defineOK1# defineSTACK.INT_SIZE1*存储空间初始分配量*/# defineSTACKINCREMENT5*存储空间分配增量*/typedefintElemType;/*定义元素的类型*/typedefstructElemType*base;ElemType*top;intstacksize;/*当前己分配的存储空间*/SqStack;intInitStack(SqStack*S);/*构造空栈*/intpush(SqStack*S,ElemType*e);/*入蔻*/intPOP(SqStaCk*S,ElemType*e);/*出栈*/intCreateStack(SqStack*S);/*创建栈*/voidPrintStack(SqStack*S);/*出栈并输出栈中元素*/intInitStack(SqStack*S)S->base=(ElemType*)malloc(STACK.INT.SIZE*sizeof(ElemType);if(!S->base)returnERROR;S->top=S->base;S->stacksize=STACK_INT_SIZE;returnOK;/*InitStack*/intPush(SqStack*S,ElemTypee)*Push*/intPop(SqStack*S,ElemType*e)*Pop*/intCreateStackfSqStack*S)inte;if(InitStack(S)else(returnERROR;)Push(S,e);returnOK;/*CreateStack*/voidPrintStack(SqStack*S)ElemTypee;while(Pop(S,&e)/*Pop_and_Print*/intmain()SqStackss;CreateStack(&ss);PrintStack(&ss);return0;).算法分析：输入元素序列12345,为什么输出序列为54321?体现了栈的什么特tt?ftinclude<stdio.h>ftinclude<malloc.h>#defineERROR0ttdefineOK1defineSTACK_INT_SIZE10*存储空间初始分配量*/defineSTACKINCREMENT5*存储空间分配增量*/typedefintElemType;*定义元素的类型*/typedefstructElcmType*base;ElcmTypc*top;intstacksize;/*当前已分配的存储空间*/SqStack;intInitStack(SqStack*S);/*构造空栈*/intPush(SqStack*S,ElemType*e);/*入栈*/intPop(SqStack*S,ElemType*e);/*出栈*/intCreateStack(SqStack*S);/*创建栈*/voidPrintStack(SqStack*S);/*出栈并输出栈中元素*/intInitStack(SqStack*S)S->base=(ElemType*)malloc(STACK_INT_SIZE*sizeof(ElemType);if(!S->base)returnERROR;S->to=S->base;S->stacksize=STACK_INT_SIZE;returnOK;)*InitStack*/intPush(SqStack*S,ElemTypee)if(S->top-S->base>=S->stacksize)S->base=(ElemType*)realloc(S->base,(S->stacksize+STCKINCREMENT)*sizeof(ElemType);if(!S->base)returnERROR;S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;)*S->top+=e;returnOK;*Push*/intPop(SqStack*S,ElcmTypc*c)if(S->to=S->base)returnERROR;e=-S->top;returnOK;/*Po*/intCreateStack(SqStack*S)inte;if(InitStack(三)elsereturnERROR;1Push(S,e);returnOK;/*CreateStack*/voidPrintStack(SqStack*S)ElcmTypGe;while(Pop(S,&e)/*PopandPrint*/intmain()SqStackss;CreateStack(&ss);Pop(&ss,&e);PrintStack(&ss);return0;2、在第1题的程序中，编写一个十进制转换为二进制的数制转换算法函数（要求利用栈来实现），并验证其正确性。实现代码#include<stdio.h>#include<malloc.h>#defineERROR0defineOK1defineSTACKINlT一SlZE10*存点?储云"空？间？初？始°?分口？配？量?*/defineSTACKINCREMENT5/*存A?储的0空？间？分0?配?增？量，？*/typedefintSElemType;/*定i§义。？元素?的i?类Cr0型-a*/typedefstruct(SEIemTyPe*base;SElemType*top;intstacksize：SqStack;intInitStack(SqStack&S);intCreateStack(SqStack*S);intGetTop(SqStackS,SElemType&e);intPush(SqStack&S,SElemTypee)：intPop(SqStack&S,SElcmType&e);voidconversion()；voidmain()(inte;SqStackS;CreateStack(三);GetTop(S,e);Push(S,e);conversion();)intInitStack(SqStack&S)(S.base=(SElemType*)malIoc(STCKINITSIZE*sizeof(SElemType);if(!S.base)returnERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;)intCreateStack(SqStack&S)(inte;if(InitStack(三)printf();elseprintf();returnERROR;）；printf(while(scanf(,&e)Push(S,e);returnOK;)intGetTop(SqStackS,SElemType&e)(if(S.top=S.base)returnERROR;e=*(S.top-1);returnOK;)intPush(SqStack&S,SElemTypee)(if(S.top-S.base>=S.stacksize)(S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base)returnERROR;S.top=S.base+S.stacksize;S.stacksize+=STCKINCREMENT;)intPop(SqStack&S,SElemType&e)(if(S.top=S.base)returnERROR：e=*-S.top;returnOK;)voidConversionOintn,e;SqStackS;printf();scanf(,n);while(n)(Push(S,n);n=n2;Pop(S,e);printf(,e)：3、阅读并运行程序，并分析程序功能。# include<stdio.h># include<malloc.h># include<string.h># defineM20# defineelemtypechartypedefstruct(elemtypestackM;inttop;Jstacknode;void init( stacknode void push( stacknode void pop( stacknodevoid init( stacknode (st- > top= 0;)void push( stacknode (if (st-> top= = M)else* st);* st, elemtype x);* st);st, elemtype x)st->top=st->top+1;st->stackst->top=x;voidpop(stacknode*st)st->top=st->top-1;)intmain()(charsM;inti;stacknode*sp;sp=malloc(sizeof(stacknode);init(sp);gets(s);for(i=0;i<strlen(s);i+)if(si='(1)push(sp,si);if(si=')')PP(sp)；)if(sp->top=0)elsereturn0;)输入：2+(c-d)*6-(f-7)*a)6运行结果：输入：a-(c-d)*6(s3-)2运行结果：程序的基本功能：以下为选做实验：4、设计算法，将一个表达式转换为后缀表达式，并按照后缀表达式进行计算，得出表达式得结果。.实现代码5、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点（不设队头指针），试编写相应的置空队列、入队列、出队列的算法。实现代码：三、实验小结四、教师评语