数据结构(邹永林版)实验报告3-栈和队列

1实验三栈和队列【实验目的】1、掌握栈的结构特性及其入栈，出栈操作；2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。3、理解掌握递归调用程序设计思想。【实验学时】4学时【实验预习】回答以下问题：1、栈的顺序存储表示2、单链队列的存储表示3、循环队列的顺序存储表示【实验内容和要求】1、按照要求完成程序exp3_1.c，实现顺序栈的相关操作。以下具有返回值的函数，若操作完成，返回OK，操作失败返回ERROR。函数需返回的其他数据，使用函数参数返回。调试及测试数据并给出结果：初始化栈；连续进栈3，5，7，9，13；获取当前栈顶元素；返回当前栈长度；判断当前栈是否为空；栈内元素依次出栈；判断当前栈是否为空；清空栈；利用栈实现数制转换，测试整数8和255；判断表达式括号是否匹配，测试以下三个表达式：表达式1：1*(2+3)/4；表达式2：((3+4)*7-(8-9)；表达式3：((1+2)*(3+4)-(5+6)*3))2exp3_1.c部分代码如下：#includestdio.h#includemalloc.h#includestring.h#defineERROR0#defineOK1#defineSTACK_INT_SIZE10/*存储空间初始分配量*/#defineSTACKINCREMENT5/*存储空间分配增量*/typedefintElemType;/*定义元素的类型*//*（1）---补充栈的顺序存储分配表示，采用定长和可变长度存储均可*/typedefstruct{ElemType*base;ElemType*top;intstacksize;}SqStack;intInitStack(SqStack*S);/*构造空栈*/intPush(SqStack*S,ElemTypee);/*入栈*/intPop(SqStack*S,ElemType*e);/*出栈*/intPopSq(SqStack*S);intGetTop(SqStack*S,ElemType*e);/*获取栈顶元素*/intClearStack(SqStack*S);/*清空栈*/intStackEmpty(SqStack*S);/*判断栈是否为空*/intStackLength(SqStack*S);/*求栈的长度*/voidconversion();/*十进制转换为二进制*/voidCorrect();/*判断表达式括号是否匹配*//*（2）---初始化栈函数*/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*//*（3）---入栈函数*/3intPush(SqStack*S,ElemTypee){if(S-top-S-base=S-stacksize){S-base=(ElemType*)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(ElemType));if(!S-base){returnERROR;}S-top=S-base+S-stacksize;S-stacksize+=STACKINCREMENT;}*S-top++=e;returnOK;}/*Push*//*（4）---出栈函数*/intPop(SqStack*S,ElemType*e){if(S-top==S-base){returnERROR;}--S-top;*e=*S-top;returnOK;}/*Pop*/intPopSq(SqStack*S){if(S-top==S-base){returnERROR;}--S-top;returnOK;}/*（5）---返回栈顶元素函数*/intGetTop(SqStack*S,ElemType*e){if(S-top==S-base){4returnERROR;}*e=*(S-top-1);returnOK;}/*GetTop*//*（6）---清空栈函数*/intClearStack(SqStack*S){if(InitStack(S)){printf(InitSuccess!);returnOK;}else{printf(InitFail!);returnERROR;}}/*ClearStack*//*（8）---判断栈是否为空*/intStackEmpty(SqStack*S){if(S-base==S-top)returnOK;elsereturnERROR;}/*StackEmpty*//*（9）---返回栈的长度函数*/intStackLength(SqStack*S){returnS-top-S-base;}/*StackLength*//*（10）---十进制整数转换为二进制并输出函数*/voidConversion(){inte;SqStacksq;InitStack(&sq);intcount;printf(inputcount:);5scanf(%d,&count);while(count!=0){Push(&sq,count%2);count=count/2;}while(Pop(&sq,&e)){printf(%d,e);}}/*Conversion*//*（11）---判断表达式括弧是否匹配（假设只有一种小括弧）函数*/voidCorrect(){SqStacksqs;InitStack(&sqs);chara[100],c;inti=0;printf(input:);while((c=getchar())!='\n'){a[i++]=c;}for(i=0;istrlen(a);i++){if(a[i]=='(')Push(&sqs,a[i]);if(a[i]==')'){PopSq(&sqs);}}if(StackEmpty(&sqs)){printf(OK!);}else{printf(error!);}}/*Correct*//*定义菜单字符串数组*/6intmenu_select(){char*menu[]={\n***************MENU******************\n,1.InitSatck\n,/*初始化顺序栈*/2.PushElement\n,/*入栈*/3.GetTopElement\n,/*获得栈顶元素*/4.ReturnStackLength\n,/*返回栈的长度*/5.StackIsEmpty\n,/*判断是否栈空*/6.PopElement\n,/*出栈*/7.ClearStack\n,/*清空栈*/8.Conversion\n,/*利用栈进行数制转换*/9.Correct\n,/*利用栈进行括号匹配*/0.Quit\n,/*退出*/\n***************MENU******************\n};chars[3];/*以字符形式保存选择号*/intc,i;/*定义整形变量*/for(i=0;i11;i++)/*输出主菜单数组*/printf(%s,menu[i]);do{printf(\nEnteryouchoice(0~9):);/*在菜单窗口外显示提示信息*/scanf(%s,s);/*输入选择项*/c=atoi(s);/*将输入的字符串转化为整形数*/}while(c0||c9);/*选择项不在0~9之间重输*/returnc;/*返回选择项，主程序根据该数调用相应的函数*/}intmain(){SqStackss;inte;InitStack(&ss);for(;;){switch(menu_select()){case1:printf(\n1-InitSatck:\n);if(InitStack(&ss))printf(InitOK!\n);elseprintf(InitERROR!\n);7break;case2:printf(\n2-PushElement:\n);printf(inputdata(Terminatedbyinputingacharacter):);while(scanf(%d,&e)==1){if(Push(&ss,e))printf(Push%dOK!\n,e);elseprintf(Push%dERROR!\n,e);printf(inputdata:(Terminatedbyinputingacharacter));}getchar();break;case3:printf(\n3-GetTopElement:\n);if(GetTop(&ss,&e))printf(Topis%d,e);elseprintf(StackisEmpty!);break;case4:printf(\n4-ReturnStackLength:\n);printf(StackLengthis%d,StackLength(&ss));break;case5:printf(\n5-StackIsEmpty:\n);if(StackEmpty(&ss)){printf(StackisEmpty!);}else{printf(StackisnotEmpty!);}break;case6:printf(\n6-PopElement:\n);if(StackEmpty(&ss)){printf(StackisEmpty!);}else{8printf(AllelementsofStack:);while(Pop(&ss,&e)){printf(%d,e);}}break;case7:printf(\n7-ClearStack:\n);ClearStack(&ss);printf(ClearStackOK!);break;case8:printf(\n8-Conversion:\n);Conversion();break;case9:printf(\n9-Correct:\n);getchar();Correct();break;case0:exit(0);}}return0;}2、按照要求完成程序exp3_2.c，实现循环队列的相关操作。以下具有返回值的函数，若操作完成，返回OK，操作失败返回ERROR。函数需返回的其他数据，使用函数参数返回。调试及测试数据并给出结果：初始化队列；返回当前队列长度；连续入队2，4，6，8，10；获取当前队头元素；返回当前队列长度；判断当前队列是否为空；队列元素依次出队；判断当前队列是否为空；exp3_2.c部分代码如下：#includestdio.h#includemalloc.h9#defineERROR0#defineOK1#defineMAXQSIZE100typedefintQElemType;/*定义元素的类型*//*（1）---循环队列顺序存储表示*/typedefstruct{QElemType*base;intfront;intrear;}SqQueue;/*（2）---构造一个空循环队列*/intInitQueue(SqQueue*Q){Q-base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!Q-base){returnERROR;}Q-front=Q-rear=0;returnOK;}/*InitQueue*//*（3）---返回循环队列的长度*/intQueueLength(SqQueue*Q){returnQ-rear-Q-front;}/*QueueLentgh*//*（4）---入队操作*/intEn