数据结构编程-汉诺塔

数据结构课程

Project3

汉诺塔

Type：Individual

Programmer:

Tester:

ReportWriter:

Dateofcompletion:2022/11/10

第一章：绪论

问题背景描述

汉诺塔游戏是这样的：有三个桩(桩1,桩2和桩3)和N个半

径不同的盘子。初始所有的盘子按半径从小到大堆叠在桩1上，半径

最小的盘子在最上面。规则：每次只可以挪移一个桩上最顶端的盘子

到另一个桩上，而且不可以把大盘子堆在小盘子上。问题是要把所有

盘子挪移到桩3上。

每次用两个整数a(1<=a<=3)和b(1<=b<=3)表示一次移

动，表示挪移桩a最顶端的盘子到桩b上。如果桩a上至少有一个盘

子，而且桩a顶端的盘子可以在不违反规则的情况下挪移到桩b上，

那末这次挪移才是一个有效的挪移。

基本要求：

输入：

每次输入包含几个测试样例。

输入的第一行包含一个整数，表示测试样例的

个数。后面紧跟个测试样例。

每一个测试样例第一行有两个整数，和

,表示有个盘子，次挪移。后面行表示具体的移

动步骤。

输出：

对每一个测试样例，输出一行表示该测试样例最后的挪移结果。

()如果所有的盘子挪移到桩之前，第次(从开始记)

挪移是无效的挪移，输出，忽略后面的挪移步骤。

()如果经过次挪移后，所有的盘子都已经挪移到桩，则

输出，并忽略后面的挪移步骤。

()其他情况输出

intmain(void)

主函数，打开输入输出文件，将各测试样例送入func()执行

voidfunc(intn,intm)

操作函数，处理一个测试样例

构造一个三元堆栈数组表示三个桩

将n个盘子从大到小放入桩1

挨次进行m次挪移，被移栈弹出的盘子压入目的栈

有效或者无效挪移判断，输出结果

销毁堆栈

voiddestroy()

关闭输入输出文件

第二章：算法详述

FILE*fpjn输入文件指针

FILE*fp_out输出文件指针

定义堆栈

typedefstruct{

int*base;栈底指针

int*top;栈顶指针

intstacksize;栈所占的存储空间大小

}stack；

stackstake[3];一个三元栈顶数组，表示三个桩

intT测试样例的个数

intn每一个测试样例的盘子数

intm每一个测试样例挪移的次数

intfrom被移桩号

intto目的桩号

intplate被移盘子号（从小到大挨次为1到n）

inttopplate目的桩原来的顶层盘号

intlaw挪移合法性判断

intmain(void){

fori:=1toTdo

begin

(

输入m,n

送入func()执行

voidfunc(intn,intm){

为三个桩构造三个空栈

forj:=nto1do

begin

(

stake[O]=push(stake[O],j);

fork:=1tomdo

begin

plate:=getplate(stake[from-1])得到移出的盘子号

网被移桩无盘子)then

跳出循环，忽略以后步骤

stake[from-1]:=pop(stake[from-1])该桩弹出顶端的盘子

topplate:=getplate(stake[to-1])得到目的桩原来的顶层盘子号

stake[to-1]=:push(stake[to-1],plate)将盘子移入该桩

网被挪移盘子比原来桩顶盘子大)then

跳出循环，忽略以后步骤

elseif(桩3的盘子数为n)then

跳出循环，忽略以后步骤

)

if(k<=m)then

for(i=k+1;i<=m;i++){

｝以免影响后面的读入

elseif（桩3的盘子数不为n且每次挪移合法）then

销毁三个堆栈

）

第三章：测试结果

输入

ln_1ln_2ln_3ln_4

3

3

223

232

2412

1224

1213

1313

1323

2312

2324

2332

3112

1212

2313

1323

1232

3212

1323

2313

3223

1323

13

12

12

32

32

33

3-4

期望输出-3-3

-33

00

33

3-4

实际输出-3-3

-33

00

测试结果passpasspasspass

补充说明：1.in」使用老师所给的参考输入，初步测试程序是否正确。

2.in_2所有盘子挪移到桩3后面步骤忽略。

3.in_3有非法挪移忽略后继步骤。

4.in_4被移桩无盘子的一种无效情况。

第四章：分析与调试

程序中所用算法的时间与空间复杂度分析

本算法的时间复杂的要视测试样例的情况而定，平均为

O(T*m);

空间复杂度使用了一个三元堆栈数组，每一个堆栈动态分配

10个顺序的存储空间(存放int型数据)，相对链栈在盘子较少时存

储空间会有所浪费

程序调试中遇到的问题与收获

1.通过这个汉诺塔挪移步骤测试熟悉了堆栈这种数据结

构的定义和使用。

可能对于输出要求中第三种情况”其他情况输出”的

理解有一定偏差，我把从空桩移出盘子的情况定义为无

效挪移，而不是其他情况，其他情况仅包括所有部都合

法但所有挪移都执行后未能实现将所有盘子移到桩

3.刚开始对算法的设计上有些问题，无效挪移同样没有完

成任务，不加变量law的判断，将既输出-p,又输出0,

显然不对。

4.在三个堆栈的定义方面刚开始没用数组，而用了switch

语句，比较繁琐。

代码有待提高的地方。

1.在堆栈操作函数定义部份，对于如空栈的弹出，超存储空间

的压入等特殊情况的处理较粗糙，认为输入的数据足够正

常。

2.算法上对于不合法的输入数据（如实际输入的测试样例数不

等于T等）无法修正，执行后将出错。

附件：源代码(C)

#include<stdio.h>

#include<stdlib.h>

#defineSTACKSIZE10/*动态分配堆栈存储量*/

FILE*fp_in=NULL;/*输入文件指针*/

FILE*fp_out=NULL;/*输出文件指针*/

typedefstruct{

int*base;

int*top;

intstacksize;

}stack;/*定义堆栈*/

stackinitstack(stackstake){

stake.base=((int*)malloc(STACKSIZE*sizeof(int)));

if(!stake.base)exit(0);

stake.top=stake.base;

stake.stacksize=STACKSIZE;

returnstake;

)r堆栈初始化*/

stackpush(stackstake,intplate){

*stake.top++=plate;

returnstake;

)/*将plate压入堆栈*/

stackpop(stackstake){

if(stake.top!=stake.base)-stake.top;

returnstake;

)/*将栈顶元素弹出*/

intgetplate(stackstake){

if(stake.top==stake.base)return0;

elsereturn*(stake.top-1);

)/*若栈不空则返回栈顶元素，否则返回0*/

voiddestroysk(stackstake){

free(stake.base);

)/*销毁栈7

voidfunc(intn,intm){/*操作函数，处理一个测试样例*/

intj=n,k=1,i,from,to,plate,topplate,law=1;

stackstake[3];/*定义一个栈顶数组*/

for(i=0;i<3;i++){

stake[i]=initstack(stake[i]);

}/*为三个桩构造三个空栈*/

for(j=n;j>=1;j-){/*将n个盘子从大到小放入桩1*/

stake[O]=push(stake[O],j);

)

for(k=1;k<=m;k++){/*挨次进行m次挪移*/

plate=getplate(stake[from-1]);/*移出的盘子号*/

stake[from-1]=pop(stake[frorr)-1]);/*该桩弹出顶端的盘子*/

if(plate==0){

break;「如果待移的桩无盘子，无效挪移，输出**/

)

topplate=getplate(stake[to-1]);/*目的桩原来的顶层盘子号*/

if(plate>=topplate&&topplate!=0){

law=O;

break;"如果被移盘子号比目的桩原顶层盘大，无效挪移，输出-k*/

)

stake[to-1]=push(stake[to-1],plate);/*将盘子移入该桩*/

if((stake[2].top-stake[2].base)==n){

break;广成功将桩1所有盘子移到桩3,输出k7

)

)

if(k<=m){/*如果某部挪移无效或者已成功，忽略后面步骤

for(i=k+1;i