数据结构编程-汉诺塔

《数据结构编程-汉诺塔》由会员分享，可在线阅读，更多相关《数据结构编程-汉诺塔（10页珍藏版）》请在装配图网上搜索。

1、数据结构课程Project 3汉诺塔Type：IndividualProgrammer: Tester:Report Writer: Date of completion:2010/11/10第一章: 绪论问题背景描述汉诺塔游戏是这样的：有三个桩（桩1，桩2和桩3）和N个半径不同的盘子。初始所有的盘子按半径从小到大堆叠在桩1上，半径最小的盘子在最上面。规则：每次只可以移动一个桩上最顶端的盘子到另一个桩上，而且不可以把大盘子堆在小盘子上。问题是要把所有盘子移动到桩3上。每次用两个整数a (1 = a = 3) 和 b (1 = b = 3)表示一次移动，表示移动桩a最顶端的盘子到桩b上。如果桩a

2、上至少有一个盘子，而且桩a顶端的盘子可以在不违反规则的情况下移动到桩b上，那么这次移动才是一个有效的移动。基本要求：输入：每次输入包含几个测试样例。输入的第一行包含一个整数T (1 = T = 55)，表示测试样例的个数。后面紧跟T个测试样例。每个测试样例第一行有两个整数，n (1 = n = 10) 和 m (1 = m = 12000)，表示有n个盘子，m次移动。后面m行表示具体的移动步骤。输出：对每个测试样例，输出一行表示该测试样例最后的移动结果。（1） 如果所有的盘子移动到桩3之前，第p次（从1开始记）移动是无效的移动，输出-p，忽略后面的移动步骤。（2） 如果经过p次移动后，所有的盘

3、子都已经移动到桩3，则输出p，并忽略后面的移动步骤。（3） 其他情况输出0int main(void) 主函数，打开输入输出文件，将各测试样例送入func( )执行void func(int n,int m)操作函数，处理一个测试样例构造一个三元堆栈数组表示三个桩将n个盘子从大到小放入桩1依次进行m次移动，被移栈弹出的盘子压入目的栈有效或无效移动判断，输出结果销毁堆栈void destroy() 关闭输入输出文件第二章: 算法详述FILE *fp_in 输入文件指针FILE *fp_out 输出文件指针定义堆栈typedef struct int *base; 栈底指针 int *top; 栈

4、顶指针int stacksize; 栈所占的存储空间大小stack；stack stake3; 一个三元栈顶数组，表示三个桩int T 测试样例的个数int n 每个测试样例的盘子数int m 每个测试样例移动的次数int from 被移桩号int to 目的桩号 int plate 被移盘子号（从小到大依次为1到n）int topplate 目的桩原来的顶层盘号int law 移动合法性判断int main(void)for i:=1 to T dobegin输入m,n送入func( )执行void func(int n,int m) 为三个桩构造三个空栈for j:=n to 1 dobe

5、ginstake0=push(stake0,j);for k:=1 to m do begin fscanf(fp_in, %d%d,&from,&to)plate:=getplate(stakefrom-1) 得到移出的盘子号if(被移桩无盘子) thenfprintf(fp_out, -%dn,k)跳出循环，忽略以后步骤 stakefrom-1:=pop(stakefrom-1) 该桩弹出顶端的盘子topplate:=getplate(staketo-1) 得到目的桩原来的顶层盘子号 staketo-1=:push(staketo-1,plate) 将盘子移入该桩if(被移动盘子比原来桩顶

6、盘子大) thenfprintf(fp_out, -%dn,k)跳出循环，忽略以后步骤else if(桩3的盘子数为n) thenfprintf(fp_out, %dn,k)跳出循环，忽略以后步骤if(k=m) then for(i=k+1;i=m;i+)fscanf(fp_in, %d%d,&from,&to);以免影响后面的读入else if(桩3的盘子数不为n且每次移动合法) then fprintf(fp_out, %dn,0)销毁三个堆栈 第三章: 测试结果输入In_1In_2In_3In_432 31 21 32 32 31 21 33 22 31 31 23 222 41 21

7、32 33 12 31 21 33 232 31 21 32 32 41 21 33 22 32 31 31 23 222 41 31 23 21 22 31 21 32 3期望输出3-303-33-30-43实际输出3-303-33-30-43测试结果passpasspasspass补充说明：1.in_1使用老师所给的参考输入，初步测试程序是否正确。2.in_2所有盘子移动到桩3后面步骤忽略。3.in_3有非法移动忽略后继步骤。4.in_4被移桩无盘子的一种无效情况。第四章: 分析与调试程序中所用算法的时间与空间复杂度分析本算法的时间复杂的要视测试样例的情况而定，平均为O(T*m);空间复杂

8、度使用了一个三元堆栈数组，每个堆栈动态分配10个顺序的存储空间（存放int型数据），相对链栈在盘子较少时存储空间会有所浪费程序调试中遇到的问题与收获1. 通过这个汉诺塔移动步骤测试熟悉了堆栈这种数据结构的定义和使用。2. 可能对于输出要求中第三种情况“其他情况输出0”的理解有一定偏差，我把从空桩移出盘子的情况定义为无效移动，而不是其他情况，其他情况仅包括所有部都合法但所有移动都执行后未能实现将所有盘子移到桩33. 刚开始对算法的设计上有些问题，无效移动同样没有完成任务，不加变量law的判断，将既输出-p，又输出0，显然不对。4. 在三个堆栈的定义方面刚开始没用数组，而用了switch语句，比较

9、繁琐。代码有待提高的地方。1. 在堆栈操作函数定义部分，对于如空栈的弹出，超存储空间的压入等特殊情况的处理较粗糙，认为输入的数据足够正常。2. 算法上对于不合法的输入数据（如实际输入的测试样例数不等于T等）无法修正，执行后将出错。附件: 源代码(C)#include#include#define STACKSIZE 10 /*动态分配堆栈存储量*/FILE *fp_in = NULL; /*输入文件指针*/FILE *fp_out = NULL; /*输出文件指针*/typedef struct int *base;int *top;int stacksize;stack; /*定义堆栈*/s

10、tack initstack(stack stake)stake.base=(int*)malloc(STACKSIZE*sizeof(int); if(!stake.base) exit(0);stake.top=stake.base;stake.stacksize=STACKSIZE;return stake; /*堆栈初始化*/stack push(stack stake,int plate) *stake.top+=plate;return stake; /*将plate压入堆栈*/stack pop(stack stake) if(stake.top!=stake.base) -st

11、ake.top;return stake; /*将栈顶元素弹出*/int getplate(stack stake)if(stake.top=stake.base) return 0; else return *(stake.top-1); /*若栈不空则返回栈顶元素，否则返回0*/void destroysk(stack stake)free(stake.base); /*销毁栈*/void func(int n,int m) /*操作函数，处理一个测试样例*/int j=n,k=1,i,from,to,plate,topplate,law=1; stack stake3; /*定义一个栈顶

12、数组*/for(i=0;i=1;j-) /*将n个盘子从大到小放入桩1*/ stake0=push(stake0,j);for(k=1;k=topplate&topplate!=0) fprintf(fp_out, -%dn,k);law=0;break; /*如果被移盘子号比目的桩原顶层盘大，无效移动，输出-k*/ staketo-1=push(staketo-1,plate); /*将盘子移入该桩*/if(stake2.top-stake2.base)=n) fprintf(fp_out, %dn,k);break; /*成功将桩1所有盘子移到桩3，输出k*/if(k=m) /*如果某部移

13、动无效或已成功，忽略后面步骤*/ for(i=k+1;i=m;i+) fscanf(fp_in, %d%d,&from,&to); else if(stake2.top-stake2.base)!=n&law) /*其他情况，输出0*/ fprintf(fp_out, %dn,0); for(i=0;i3;i+)destroysk(stakei); /*销毁三个堆栈*/ void destroy() /*关闭输入输出文件*/fclose(fp_in);fclose(fp_out); int main(void) /*主函数*/ int T,i=1,n,m;fp_in = fopen(p3_in.txt, r); /*打开输入文件*/ if(fp_in = NULL) exit(0); fp_out = fopen(p3_out.txt, w); /*打开输出文件*/if(fp_out = NULL)exit(0); fscanf(fp_in, %d, &T); /*输入测试样例个数*/ for(i=1;i=T;i+) /*实现所有测试样例的操作*/ fscanf(fp_in, %d%d, &n,&m);func(n,m); destroy();return 0;