数据结构栈和队列实验报告

第1页共17页南京信息工程大学实验（实习）报告实验（实习）名称栈和队列日期2017.11.8得分指导老师崔萌萌系计算机系专业软件工程年级2016班次(1)姓名学号一、实验目的1、学习栈的顺序存储和实现，会进行栈的基本操作2、掌握递归3、学习队列的顺序存储、链式存储，会进行队列的基本操作4、掌握循环队列的表示和基本操作二、实验内容1、用栈解决以下问题：（1）对于输入的任意一个非负十进制数，显示输出与其等值的八进制数，写出程序。（2）表达式求值，写出程序。2、用递归写出以下程序：（1）求n！。（2）汉诺塔程序，并截图显示3、4、5个盘子的移动步骤,写出移动6个盘子的移动次数。第2页共17页3、编程实现：（1）创建队列，将asdfghjkl依次入队。（2）将队列asdfghjkl依次出队。4、编程实现创建一个最多6个元素的循环队列、将ABCDEF依次入队，判断循环队列是否队满。三、实验步骤1.栈的使用1.1用栈实现进制的转换：代码如下：#includestdio.h#includestackusingnamespacestd;intmain(){stackints;//栈s;intn,radix;printf(请输入要转换的十进制非负整数：);scanf(%d,&n);printf(请输入目标进制：);scanf(%d,&radix);第3页共17页printf(转换为%d进制：,radix);while(n){s.push(n%radix);n/=radix;}while(!s.empty()){//非空printf(%d,s.top());s.pop();}printf(\n);return0;}运行结果如下：2.2求表达式的值代码如下：#includestdio.h#includestdlib.h#includestring.h#includemath.h#definetrue1#definefalse0#defineOPSETSIZE8typedefintStatus;第4页共17页unsignedcharPrior[8][8]={//运算符优先级表//'+''-''*''/''('')''#''^'/*'+'*/'','','','','','','','',/*'-'*/'','','','','','','','',/*'*'*/'','','','','','','','',/*'/'*/'','','','','','','','',/*'('*/'','','','','','=','','',/*')'*/'','','','','','','','',/*'#'*/'','','','','','','=','',/*'^'*/'','','','','','','',''};typedefstructStackChar{//StackChar类型的结点SCcharc;structStackChar*next;}SC;typedefstructStackFloat{//StackFloat类型的结点SFfloatf;structStackFloat*next;}SF;SC*Push(SC*s,charc)//SC类型的指针Push，返回p{SC*p=(SC*)malloc(sizeof(SC));p-c=c;p-next=s;returnp;}SF*Push(SF*s,floatf)//SF类型的指针Push，返回p{第5页共17页SF*p=(SF*)malloc(sizeof(SF));p-f=f;p-next=s;returnp;}SC*Pop(SC*s)//SC类型的指针Pop{SC*q=s;s=s-next;free(q);returns;}SF*Pop(SF*s)//SF类型的指针Pop{SF*q=s;s=s-next;free(q);returns;}floatOperate(floata,unsignedchartheta,floatb)//计算函数Operate{switch(theta){case'+':returna+b;case'-':returna-b;case'*':returna*b;case'/':returna/b;case'^':returnpow(a,b);default:return0;第6页共17页}}charOPSET[OPSETSIZE]={'+','-','*','/','(',')','#','^'};StatusIn(charTest,char*TestOp){intFind=false;for(inti=0;iOPSETSIZE;i++){if(Test==TestOp[i])Find=true;}returnFind;}StatusReturnOpOrd(charop,char*TestOp){for(inti=0;iOPSETSIZE;i++){if(op==TestOp[i])returni;}}charprecede(charAop,charBop){returnPrior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)];}floatEvaluateExpression(char*MyExpression)//表达式的运算符优先算法{//OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合SC*OPTR=NULL;//运算符栈，字符元素SF*OPND=NULL;//运算数栈，实数元素第7页共17页charTempData[20];floatData,a,b;chartheta,*c,Dr[]={'#','\0'};OPTR=Push(OPTR,'#');c=strcat(MyExpression,Dr);strcpy(TempData,\0);//字符串拷贝函数while(*c!='#'||OPTR-c!='#'){if(!In(*c,OPSET)){Dr[0]=*c;strcat(TempData,Dr);//字符串连接函数c++;if(In(*c,OPSET)){Data=atof(TempData);//字符串转换函数(double)OPND=Push(OPND,Data);strcpy(TempData,\0);}}else{//不是运算符则进栈switch(precede(OPTR-c,*c)){case''://栈顶元素优先级低OPTR=Push(OPTR,*c);c++;break;case'='://去括号并接收下一字符OPTR=Pop(OPTR);c++;break;case''://退栈并将运算结果入栈theta=OPTR-c;OPTR=Pop(OPTR);b=OPND-f;OPND=Pop(OPND);a=OPND-f;OPND=Pop(OPND);OPND=Push(OPND,Operate(a,theta,b));break;}}第8页共17页}returnOPND-f;}intmain(){chars[128];printf(请输入表达式:\n);scanf(%s,s);printf(该表达式的值为:\n);printf(%s=,s);printf(%g\n,EvaluateExpression(s));//%greturn0;}运行结果如下：2.递归的使用2.1求n！：代码如下：#includestdio.hintFact(intn){if(0==n)return1;elsereturnn*Fact(n-1);}第9页共17页intmain(){intn;scanf(%d,&n);printf(%d的阶乘为：,n);printf(%d,Fact(n));return0;}运行结果如下：2.2哈诺塔：代码如下：#includestdio.hintHanoi(intn,chara,charb,charc){if(1==n)printf(%c-%d-%c,a,1,c);else{Hanoi(n-1,a,c,b);printf(%c-%d-%c,a,n,c);Hanoi(n-1,b,a,c);}return0;}第10页共17页intmain(){intn;chara='A',b='B',c='C';printf(请输入汉诺塔的层数:);scanf(%d,&n);Hanoi(n,a,b,c);printf(\n);return0;}运行结果如下：n=3时n=4时n=5时n=6时由3,4,5可推知n层哈诺塔需要移动12n次；n=6时,需要移动63次。第11页共17页3.队列的出队和入队代码如下：#includestdio.h#includestdlib.h#includestring.h#defineOK1#defineERROR0#defineOVERFLOW-1typedefcharElemType;//defaultElemType=chartypedefintStatus;//ReturnValue/*队列节点的申明*/typedefstructnode{ElemTypedata;structnode*next;}QNode,*QuePtr;/*链式队列*/typedefstruct{QuePtrfront;//队头指针QuePtrrear;//队尾指针，指向队尾元素的下一位}LinkQueue;StatusInitQueue(LinkQueue*q)//初始化队列{q-front=q-rear=(QuePtr)malloc(sizeof(QNode));q-front-next=NULL;returnOK;}StatusEnQueue(LinkQueue*q,ElemTypee)//将元素e入队列{QuePtrtemp=(QuePtr)malloc(sizeof(QNode));//创建新结点if(!temp)returnOVERFLOW;temp-data=e;//初始化新结点的数据为etemp-next=NULL;//队列只能从队尾插入所以下一个结点初始化为NULLq-rear-next=temp;第12页共17页q-rear=temp;//将指向队尾的指针指向新结点returnOK;}StatusCreateQueue(LinkQueue*q/*,chara[]*/)//创建队列{InitQueue(q);intk;printf(请输入队列元素个数：);scanf(%d,&k);printf(请输入队列元素:\n);for(inti=0;ik;++i){chara;getchar();scanf(%c,&a);EnQueue(q,a);}//for(inti=0;istrlen(a);++i)//EnQueue(q,a[i]);returnOK;}StatusDeQueue(LinkQueue*q,ElemType*e)//队头的结点出队{if(q-front==q-rear)returnERROR;QuePtrtemp=q-front-next;//初始化temp为要出队的结点的指针if(q-front-next==q-rear)q-rear=q-front;*e=temp-data;//将出队的数据元素存入*eq-front-next=temp-next;//下一个结点成为队头free(temp);//删除要出队的结点returnOK；}boolIsEmpty(LinkQueue*q)//判断队列是否为空{第13页共17页if(q-front==q-rear)returntrue;returnfalse;}intGetQueueLength(LinkQueue*q)//返回队列的长度{Q