数据结构 实验三 Hanoi塔算法 汉诺塔算法

沏尸/要实验报告

课程名称：程序设计与数据结构指导老师:_成绩：______________

实验名称：Hanoi塔算法实验类型:基础疝练型同组学生姓名：_____________

一、实验目的和要求(必填)二、实验内容和代码(必埴5―

三、代码缺陷及修正记录四、实验结果与分析(必填)

五、讨论、心得

Hanoi塔算法

一、实验目的和要求

1、掌握编程工具的使用；

2、掌握线性表数据结构在计算机上的实现；

3、掌握通过计算机编程解决问题的基本方法。

二、实验内容和代码

【实验内容】

1、编程实现Hanoi塔的求解算法，要求输出递归的函数、递归的层次和盘子移动的情况；

2、将前三次实验的内容整合到同一个工程下，在主控制台能够进入相应的实验。

【实验代码】

1、Hanoi塔算法：

Hanoi,h

typedefstructtag{

intsize;

tag*next;

}Stack,*stack;

voidhanoi(intn,chara,charb,charc);

intHanoiPage(void);

voidgotoxy(unsignedcharx,unsignedchary);

voidPop(stackS,int&e);

voidPush(stackS,inte);

intMove(chara,charb);

voidshow();

voidhanoi2(intn,chara,charb,charc);

voidpaint(stackS,intnum);

voidrelease(stackS);

stackA,B,C;

intn;

voidhanoi(intn,chara,charb,charc)

(

if(n==1){

Move(a,b);

show();

)

else

(

hanoi(n-1,a,c,b);

Move(a,b);

show();

hanoi(n-1,c,b,a);

voidshow(){

system(nclsn);

paint(A,0);

paint(B,1);

paint(C,2);

Sleep(800);

)

voidgotoxy(unsignedcharx,unsignedchary)

(

COORDcor;

HANDLEhout;

cor.X=x;

cor.Y=y;

hout=GetStdHandle(STD_OUTPUT_HANDLE);

SetConsoleCursorPosition(hout,cor);

)

voidPop(stackS,int&e){

stackptrl,ptr2;

ptrl=ptr2=S;

while(ptr2->next){

ptrl=ptr2;

ptr2=ptr2->next;

)

if(pS2){

e=ptr2->size;

ptrl->next=NULL;

free(ptr2);

)

else

e=NULL;

)

voidPush(stackS,inte){

stackptr=NULL;

stacktemp=NULL;

ptr=S;

while(ptr->next){

ptr=ptr->next;

)

temp=(stack)malloc(sizeof(Stack));

temp->size=e;

temp->next=NULL;

ptr->next=temp;

)

intMove(chara,charb){

inte;

if(a二二'A'&&b===B){

Pop(A,e);

Push(B,e);

elseif(a二='B'&&b==C'){

Pop(B,e);

Push(C,e);

elseif(a二二'C'&&b=二'A'){

Pop(C,e);

Push(A,e);

elseif(a=='C'&&b==B){

Pop(C,e);

Push(B,e);

)

elseif(a二=二二'A'){

Pop(B,e);

Push(A,e);

)

elseif(a二='A'&&b二二'C'){

Pop(A,e);

Push(C,e);

)

returne;

)

voidpaint(stackS,intnum){

gotoxy(5+20*num,n+4);

for(inti=0;i<10;i++)

prmtf(n_H);

stackptr=S->next;

intcount=1;

while(ptr){

gotoxy(9+20*num-ptr->size/2,n+4・count);

for(inti=0;i<ptr->size;i++)

printf(n«n);

ptr=ptr->next;

count++;

voidrelease(stackS){

stackptr,tail;

ptr=S->next;

S->next=NULL;

tail=NULL;

while(ptr){

tail=ptr->next;

free(ptr);

ptr=tail;

voidhanoi2(intn,chara,charb,charc){

staticintstep=1;

staticintcount=0;

intnum=1;

inte;

if(n==1){

e=Move(a,b);

printf("第％d步：%d号盘子:%c->%c\nn,++count,e,a,b);

)

else

(

printf("在第％(1层调用第％(1个递归进入第％d层\n\step,num,step+1);

step++；

num++;

hanoi2(n-1,a,c,b);

e=Move(a,b);

printf("第％d步：%d号盘子:%c->%c\nn,++count,e,a,b);

printf("在第％(1层调用第％(1个递归进入第％d层\n\step,num,step+1);

step++；

num++;

hanoi2(n-1,c,b,a);

)

if(step!=1)

printf("返回第％d层5"，--step);

else

printf("共移动％d步3”,count);

Hanoi,cpp

#include<stdio.h>

#include<Windows.h>

#include"hanoi.hH

intmain(void)

(

system(nclsn);

charchoice;

A=(stack)malloc(sizeof(Stack));

B=(stack)malloc(sizeof(Stack));

C=(stack)malloc(sizeof(Stack));

A->next=NULL;

B->next=NULL;

C->next=NULL;

while(true){

printf("请输入盘子数量：")；

scanLs("%d",&n);

getchar();

printf("请输入计算方式：1.字符显示2.演示(输入盘子数不大于6):\n");

choice=getchar();

getchar();

for(inti=n;i>0;i—){

Push(A,i);

}

switch(choice){

case2:

if(n>6){

printf("非法输入\n”)；

break;

)

show();

hanoi(n,A,C,B');

break;

caseT:

default:

printf("盘子移动情况如下:\nn);

hanoi2(n,A,C'B);

)

printf(u\n\nO：继续其他：退出\n“);

choice=getchar();

getchar();

switch(choice){

case'O':

release(A);

release(B);

release(C);

break;

default:

release(A);

release(B);

release(C);

return0;

)

)

return0;

2、整合程序主函数：

#include<stdio.h>

#include<Windows.h>

#include<stdlib.h>

#includenComplex.hn

#include"Hanoi.h"

#include"Polynomial.hH

intmain()

(

charKEY;

charchoice;

do{

printf(”请输入所需执行的程序：1.一元多项式的加减运算2.Hanoi塔算法3.复数的

四则运算:\n");

choice=getchar();

getchar();

switch(choice){

case3:

{inti;

Complexz,zl,z2;

floatzlr,zli,z2r,z2i;

printf("请分别输入复数zl的实部和虚部:")；

scanf_s(n%f%f,&zlr,&zli);

printf("请分别输入复数z2的实部和虚部

scanf_s("％f%f',&z2r,&z2i);

InitComplex(&zl,zlr,zli);

InitComplex(&z2,z2r,z2i);

printf(n\n复数zl=")；

OutComplex(zl);

printf(u\n复数z2二")；

OutComplex(z2);

Add(&z,zl,z2);

printf(n\n复数zl+z2=");

OutComplex(z);

Minus(&z,zl,z2);

printf(u\n复数zl-z2=")；

OutComplex(z);

Multiply(&z,zl,z2);

printf(n\n复数zl*z2=H);

OutComplex(z);

if(z2r!=0||z2i!=0){

Divide(&z,zl,z2);

printf("\n复数zl/z2=")；

OutComplex(z);

)

else{

printf(”\n被除数为0,不能做除法\n”)；

)

}system("pause^^);break;

case2:

(

system(nclsn);

charchoice;

A=(stack)malloc(sizeof(Stack));

B=(stack)malloc(sizeof(Stack));

C=(stack)malloc(sizeof(Stack));

A->next=NULL;

B->next=NULL;

C->next=NULL;

while(true){

printf(”请输入盘子数量：”)；

scanf_s(n%dn,&n);

getchar();

printff请输入计算方式：1.字符显示2.演示(输入盘子数不大于6):\n)

choice=getchar();

getchar();

for(inti=n;i>0;i-){

Push(A,i);

}

switch(choice){

case2:

if(n>6){

printf("非法输入\n");

break;

)

show();

hanoi(n,'A',C,B);

break;

caseT:

default:

printf("盘子移动情况如下：\n");

hanoi2(n,'A','C','B');

)

break;

)

}break;

case111:

{structPolynomial*pl,*p2;

printff请输入多项式A中x的系数及指数(输入00表示输入结束):\n");

pl=create();

printf("请输入多项式B中x的系数及指数(输入00表示输入结束):\n");

p2=create();

printf("\n");

printf("A(x)=");

print(pl);

printf("\n");

printf("B(x)=");

print(p2);

printf("\n\n");

printf("A(x)+B(x)=");

add(pl,p2);

printf("\n\n");

printf("A(x)-B(x)=");

sub(pl,p2);

printf("\n\n");

system("pausen);

}break;

}

printf("\n若要继续，请输入0；若要退出，请输入Q或q!\n");

KEY=getchar();

getchar();

}while(KEY!='Q'&&KEY!='q');

return0;

)

三、代码缺陷及修正记录

1、三个实验的整合部分，一开始是想建立一些main(x)函数(与main功能类似但不是main

函数)，这样到main函数中直接调用就可以，后来又考虑了switchcase的循环方式也可，

要使用的函数都在main之中，就使用了后者，可能不够完善，需要进一步的完善。

2、Hanoi塔算法实验中，一开始采用的递归方式不够科学，重复后不能正常继续或退出，运

行两次后就会发生异常情况，而后请教别人后修改递归方式，得到了正常运行结果且能正常

继续和退出。

3、Hanoi塔实验的动画演示部分，这是跟别人交流过后才会的，虽然不是实验要求，但通过

这个我对于动画演示以及#include"windows,h”的使用更加了解，也知道他的一些局限之处

只能用于windows之下。

四、实验结果与分析

1、Hanoi塔算法：

(1)当输入盘子数量为3时:

■JF:\360Downloads\VS2017平权用媚塔.exe□X

请输入盘「数最：3

请输入计算方式：1.字符显示2.演示(输入盘广数不大于6):

1

盘上移动情况如卜.：

在第1层调用第1个递归进入第2层

在第2层调用第1个递归进入第3层

第1步：1号盘子:A->C

返回第2层_

第2步：2号盘子:A->B

在第2层调用第2个递回进入第3层

笫3步：1号盘子:C->B

返回第2层

返回第1层

第4步:3号盘子:A->C

/E第1层调用第2个递归进入第2层

在第2层调用第1个递归进入第3层

第5步:1号盘子:B->A

返回第2层

第6步：2号盘子:B->C

在第2所调用第2个递归进入第3层

第7步：1号盘子：A->C

返回第2层

返回第1层

共移动7步

0：继续其他：退出

（2）当输入盘子数量为4时:

■F:\360Downloads\VS2017平独田僚妮坏Debug\J5Ugig.exe□X

0：继续其他：退出

0

请输入盘子数最：4

请输入计算方式：1.字符显示2.演示（输入盘了数不大「6）:

盘子移动情况如下:

在第1层调用第1个递回进入第2层

在第2层调用笫1个递归进入第3层

在第3层调用第1个递归进入第4层

第8步：1号盘子:A->B

返回第3层

第9步：2号盘子:A->C

在第3层调用第2个递回进入第4层

第10步：1号盘f：B->C

返回第3层

返I可第2层

第11步：3号盘「：A->B

在第2层调用第2个递归进入第3层

/E第3层调用第1个递!11进入第4层

第12步:1号盘f:C->A

返回第3层

第13步：2号盘子:C->B

在第3底调用第2个刚I进入第4层

第14步：1号盘子:A->B

返回第3层

返回第2层

返回第1层

第15步：4号盘子:A->C

在第1层调用第2个递归进入第2层

在第2层调用第1个递归进入第3层

I■F:\360Downloads\VS2017平常文的fiSVXJgiS\DebugMRjgtS.exe

□X

施第3层调用第1个递UI进入笫4片

第16步：1号盘子:B->C

返回第3层

第17步：2号盘f：B->A

在第3层调用第2个递归进入第4层

第18步：1号盘子：C->A

返回第3层

返回第2层

第19步：3号盘子:B->C

在第2层调用第2个递回进入第3层

在第3层调川第1个递归进入第4层

第20步:1号盘子:A->B

返回第3层

第21步：2号盘子:A->C

在第3层调用第2个递UI进入第4层

第22步：1号盘f：B->C

返回第3层

返回第2层

返回第1层

共移动22步

0：继续其他:退出

2、整合项目：

依次运行三个实验得到的结果:

■F:\360Downloads\VS2017平常文件存储\HANOI塔与一元多项式整合\Debug\HANOI塔.exe□X

请输入所需执行的程方：工一元多项式的加减运与2.Hanoi塔前汝3.复数的四则运算:

1

诂输入多项式A中x的系数及指数（输入0。表示输入结束）：

11

22

33

00

请输入多项式B中x的系数及指数（输入00表示输入结束）：

22

34

45

00

A（x）=lx1+2x2+3x3

B（x）=2x'2+3x'4+4x~5

k(x)+B(x)=lx1+4x2+3x3+3x4+4x'5

A(x)~B(x)=lx1+3x3-3x4-4x5

请按任意键继续...

若要继续,请输入0;若要退出•请输入Q或q!

■1F:\360Downloads\VS2017平常文峥储\HANOI塔与一元多演整合\Debug\HANOI塔.exe□

I请输入盘f数审:3

清输入计算方式：1.字符显示2.演示（输入盘r数不大「6）：

盘子移动情况如下：

隹第1层调用第1个递归进入第2层

在:第2层调用第1个递UI进入第3层

第