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

《《数据结构》实验二 栈和队列.docx》由会员分享，可在线阅读，更多相关《《数据结构》实验二 栈和队列.docx（11页珍藏版）》请在课桌文档上搜索。

1、第HF工生战数据结构实验指导及报告书2022/2022学年第二学期姓名：学号：班级：指导教师：计算机科学与工程学院2022实验二栈和队列一、实验目的1、掌握栈的结构特性及其入栈，出栈操作；2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。二、实验内容和要求1、阅读下面程序，将函数PUSh和函数Pop补充完整。要求输入元素序列12345e,运行结果如下所示。# include# indude# defineERRORO# defineOK1# defineSTACK.INT_SIZE1*存储空间初始分配量*/# defineSTACKINCREMENT5*存储空间分配增量*

2、/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(SqStac

3、k*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;/*C

4、reateStack*/voidPrintStack(SqStack*S)ElemTypee;while(Pop(S,&e)/*Pop_and_Print*/intmain()SqStackss;CreateStack(&ss);PrintStack(&ss);return0;).算法分析：输入元素序列12345,为什么输出序列为54321?体现了栈的什么特tt?ftincludeftinclude#defineERROR0ttdefineOK1defineSTACK_INT_SIZE10*存储空间初始分配量*/defineSTACKINCREMENT5*存储空间分配增量*/typedefin

5、tElemType;*定义元素的类型*/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=

6、(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-b

7、ase+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)/*Po

8、pandPrint*/intmain()SqStackss;CreateStack(&ss);Pop(&ss,&e);PrintStack(&ss);return0;2、在第1题的程序中，编写一个十进制转换为二进制的数制转换算法函数（要求利用栈来实现），并验证其正确性。实现代码#include#include#defineERROR0defineOK1defineSTACKINlT一SlZE10*存点?储云空？间？初？始?分口？配？量?*/defineSTACKINCREMENT5/*存A?储的0空？间？分0?配?增？量，？*/typedefintSElemType;/*定i义。？元素?的i?

9、类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);conver

10、sion();)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,SE

11、lemType&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,SElem

12、Type&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# include# include# defineM20# defineelemtypechartypedefstruct(elemtypestackM;inttop;Jstacknode;void init( stacknode void p

13、ush( 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;itop=0)elsereturn0;)输入：2+(c-d)*6-(f-7)*a)6运行结果：输入：a-(c-d)*6(s3-)2运行结果：程序的基本功能：以下为选做实验：4、设计算法，将一个表达式转换为后缀表达式，并按照后缀表达式进行计算，得出表达式得结果。.实现代码5、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点（不设队头指针），试编写相应的置空队列、入队列、出队列的算法。实现代码：三、实验小结四、教师评语