实验报告--实验3栈的实验(二选一)

《实验报告--实验3栈的实验(二选一)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、成劣卩忌•匕工窓大學ChengduI'niversityofInformationTechnology实验报告实验课程：数据结构实验项目：栈的实验（二选一）指导教师：徐虹学生姓名：张少龙学生学号：2014051151班级：计科应用143班2014年12月10日成都信息工程大学计算机学院问题描述1.编程实现汉诺塔问题的递归算法和非递归算法，并统计各白的执行时间2.表达式求值验证某算术表达式的正确性，若止确，则计算该算术表达式的值。二、解决方法当盘子的个数为n时，移动的次数应等于25・1（有兴趣的可以自己证明试试看）。后來一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了

2、。首先把三根柱了按顺序排成品字型，把所有的圆盘按从人到小的顺序放在柱了A上，根据圆盘的数罐确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放ABC；若n为奇数，按顺时针方向依次摆放ACBo⑴按顺时针方向把鬪盘1从现在的柱了移动到下一根柱了，即当n为偶数时，若圆盘1在柱子A,则把它移动到B；若圆盘1在柱子B,则把它移动到C；若圆盘1在柱子C,则把它移动到Ao⑵接着，把期外两根柱了上可以移动的圆盘移动到新的柱了上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空吋，移动较小的圆盘。这一步没有明确规定移动哪个圆盘,你可能以为会有多种可能性，-其实不然，可实施的行动是唯一的。⑶反复进行⑴

3、⑵操作，最后就能按规定完成汉诺塔的移动。所以结果非常简单，就是按照移动规则向一个方向移动金片：如3阶汉诺塔的移动：A-C,A->B,C->B,A-C,B~A,B->C,A-C三、四种方法的算法汉诺塔递归算法:四、实验中遇到的问题及心得五、完整源程序（带注解）#include#defineMAXSTACK10//栈的最人深度intMOVENUM=1;//表示口前移动的步数structhanoi{//汉诺塔定义intn;charx,y,z;};voidmove(charx,intn,chary){//移动步骤说明printftMovedisk%dfrom%cto%cr

4、T,M0VENUM++,n,x,y):voidreverse_hanoi(intn,charx,chary,charz){//递归if(1=n)move(x,1,z);else{reverse_hanoi(n-1,x,z,y):move(x,n,z);reverse_hanoi(n-1,y,x,z);}}voidpush(structhanoi*p,inttop,charx,chary,charz,intn){p[top+1].n=n-1;p[top+1].x=x;讥top+1].y=y;p[top+1].z=z;}voidunreversehanoi(structhanoi*p){/

5、/非递归inttop=0;while(top>=0){while(p[topj.n>1){//向左走到尽头push(p,top,p[top].x,p[top]・z,p[top]・y,p[top]・n);top++;}if(p[top].n==1){〃叶子结点move(p[top]・x,1,p[top]・z);top一；}if(top>=0){//向右走一步move(p[topl•x,p[top]・n,p[top]・z);top―;push(p,top,p[top+l].y,p[top+l]・x,p[top+l].z,p[top+l]・n);top卄；}}}intmainO{struct

6、hanoip[MAXSTACK];intn;printfC输入汉诺塔个数：“)；scanf_s&n);printfC递归算法:%d",n);//递归reverse_hanoi(n,Jx,'y‘，f);printf("非递归算法：%d",n);〃非递归MOVENUM二1;讥o]・n二n;pLO].x二，x',p[0].y二，y',pLOj.z二，z';unreverse_hanoi(p);return0;