资源描述：
《数据结构编程-汉诺塔》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构课程Project3汉诺塔Type：IndividualProgrammer:Tester:ReportWriter:Dateofcompletion:2010/11/10第一章:绪论问题背景描述汉诺塔游戏是这样的：有三个桩（桩1，桩2和桩3）和N个半径不同的盘子。初始所有的盘子按半径从小到大堆叠在桩1上，半径最小的盘子在最上面。规则：每次只可以移动一个桩上最顶端的盘子到另一个桩上，而且不可以把大盘子堆在小盘子上。问题是要把所有盘子移动到桩3上。每次用两个整数a(1<=a<=3)和b(1<=b<=3)表示一次移
2、动，表示移动桩a最顶端的盘子到桩b上。如果桩a上至少有一个盘子，而且桩a顶端的盘子可以在不违反规则的情况下移动到桩b上，那么这次移动才是一个有效的移动。基本要求：输入：每次输入包含几个测试样例。输入的第一行包含一个整数T(1<=T<=55)，表示测试样例的个数。后面紧跟T个测试样例。每个测试样例第一行有两个整数，n(1<=n<=10)和m(1<=m<=12000)，表示有n个盘子，m次移动。后面m行表示具体的移动步骤。输出：对每个测试样例，输出一行表示该测试样例最后的移动结果。（1）如果所有的盘子移动到桩3之前，第p次
3、（从1开始记）移动是无效的移动，输出-p，忽略后面的移动步骤。（1）如果经过p次移动后，所有的盘子都已经移动到桩3，则输出p，并忽略后面的移动步骤。（2）其他情况输出0intmain(void)主函数，打开输入输出文件，将各测试样例送入func()执行voidfunc(intn,intm)操作函数，处理一个测试样例构造一个三元堆栈数组表示三个桩将n个盘子从大到小放入桩1依次进行m次移动，被移栈弹出的盘子压入目的栈有效或无效移动判断，输出结果销毁堆栈voiddestroy()关闭输入输出文件第二章:算法详述FILE*fp
4、_in输入文件指针FILE*fp_out输出文件指针定义堆栈typedefstruct{int*base;栈底指针int*top;栈顶指针intstacksize;栈所占的存储空间大小}stack；stackstake[3];一个三元栈顶数组，表示三个桩intT测试样例的个数intn每个测试样例的盘子数intm每个测试样例移动的次数intfrom被移桩号intto目的桩号intplate被移盘子号（从小到大依次为1到n）inttopplate目的桩原来的顶层盘号intlaw移动合法性判断intmain(void){fo
5、ri:=1toTdobegin{输入m,n送入func()执行}}voidfunc(intn,intm){为三个桩构造三个空栈forj:=nto1dobegin{stake[0]=push(stake[0],j);}fork:=1tomdobegin{fscanf(fp_in,"%d%d",&from,&to)plate:=getplate(stake[from-1])得到移出的盘子号if(被移桩无盘子)thenfprintf(fp_out,"-%d",k)跳出循环，忽略以后步骤stake[from-1]:=pop
6、(stake[from-1])该桩弹出顶端的盘子topplate:=getplate(stake[to-1])得到目的桩原来的顶层盘子号stake[to-1]=:push(stake[to-1],plate)将盘子移入该桩if(被移动盘子比原来桩顶盘子大)thenfprintf(fp_out,"-%d",k)跳出循环，忽略以后步骤elseif(桩3的盘子数为n)thenfprintf(fp_out,"%d",k)跳出循环，忽略以后步骤}if(k<=m)thenfor(i=k+1;i<=m;i++){fscanf
7、(fp_in,"%d%d",&from,&to);}以免影响后面的读入elseif(桩3的盘子数不为n且每次移动合法)thenfprintf(fp_out,"%d",0)销毁三个堆栈}第三章:测试结果输入In_1In_2In_3In_4323121323231213322313123222412132331231213323231213232412133223231312322241312321223121323期望输出3-303-33-30-43实际输出3-303-33-30-43测试结果passpasspass
8、pass补充说明：1.in_1使用老师所给的参考输入，初步测试程序是否正确。2.in_2所有盘子移动到桩3后面步骤忽略。3.in_3有非法移动忽略后继步骤。4.in_4被移桩无盘子的一种无效情况。第四章:分析与调试程序中所用算法的时间与空间复杂度分析本算法的时间复杂的要视测试样例的情况而定，平均为O(T*m);空间复杂度使用了一个
