汉诺塔的动态演示（c++）

#include<iostream> #include<string> using namespace std; #include <stdlib.h> #define MAX 10000 ///////////////////////////////////////////////////////////////////////////////////// // 两个类: Tower类（栈）Hanoi类（包含三个Tower类对象组成） // // 程序中大部份功能函数封装在这两个类中 包括：递归算法Hanoi::Move() // // 图形显示Hanoi::Outlin() 移动演示Hanoi::MoveShow() 等 // // 塔的盘子是字符串由（'=',' '）组成 方法 Tower::disc(); // ///////////////////////////////////////////////////////////////////////////////////// /////塔////类////开////始//// struct Stack//链栈 { string data;//存放盘子 Stack *next; }; class Tower { int floor;//塔的层数 int broad;//塔的底座宽度 public: Stack *top; //栈顶指针（游戏模式需要访问） int Top;//记录当前层数 Tower(int store)//构造函数 { floor=store; if(floor<6)broad=4+2*floor;//塔的层数与塔的底座宽度的关系 else broad=2+2*floor; Top=0; string bro; for(int i=0;i<broad/2;i++) { bro=bro+"[]";//底座 【】【】【】【】【】【】 } Stack *temp=new Stack; temp->data=bro; temp->next=top; top=temp; } string OutFloor(int i) //显示第temp层的数据 { Stack *toptemp=top; for(int j=0;j<Top-i;j++) { toptemp=toptemp->next; } return toptemp->data; } void push(string disc)//放入盘子 { Stack *temp=new Stack; temp->data=disc; temp->next=top; top=temp; Top++; } string pop()//取出盘子 { Stack *temp; string x; if(top==NULL) return NULL; else { x=top->data; temp=top; top=top->next; free(temp); Top--; return x; } } string disc(int space)//盘子(由'='和' '组成) { string dis; for(int i=0;i<space;i++) // { // ________ ________ ________ dis=dis+' '; // | ==== | | ==== | | ==== | } // | ====== | | ====== | | ====== | for(int j=space;i<broad-space;i++)// |========| |========| |========| { // dis=dis+'='; // } // for(int k=broad-space;k<broad;k++)// { // dis=dis+' '; // } return dis; } }; /////塔////类////结////束//// //////汉////诺/////塔////类////开////始//// class Hanoi //汉诺塔类 三个塔组成 { int Store;//汉诺塔的层数 int broad;//塔的底座宽度 Tower *A;// Tower *B;// 定义三座塔 指针方便释放内存 Tower *C;// ///汉///诺////塔////的///递///归///算///法///开///始/// int step;//移动步数 int STEP[MAX];//存放移动步骤 void move(int A,int C) { step++; STEP[step]=A*10+C;//规定：12 A->B,13 A->C; 21 B->A,23 B->C; 31 C->A,32 C->B } void Move(int n,int A,int B,int C) //递归 （这里的A，B，C是相对的，不等同外面定义的A塔，B塔，C塔） { if(n==1)//递归的终止条件 { move(A,C);//将A塔上的最后一个盘子盘子直接移动到C塔 } else { Move(n-1,A,C,B);//将A塔上的n-1个盘子通过C塔移动到B塔 move(A,C); //将A塔上的最后一个盘子盘子直接移动到C塔 Move(n-1,B,A,C);//将B塔上的n-1个盘子通过A塔移动到C塔 } } ///汉///诺////塔////的///递///归///算///法///结///束/// public: Hanoi(int store)//构造函数 { Store=store; if(Store<6)broad=4+2*Store;//塔的层数与塔的底座宽度的关系 else broad=2+2*Store; A=new Tower(store); for(int i=1;i<=Store;i++) { A->push(A->disc(i)); } B=new Tower(store); C=new Tower(store); step=0; Move(Store,1,2,3); } void OutStep()//输出步骤 { int StepTemp; cout<<"\n\t移动方法："<<endl; for(StepTemp=1;StepTemp<=step;StepTemp++) { cout<<"\n\t"<<"第"<<StepTemp<<"步："<<STEP[StepTemp]/10<<"-->"<<STEP[StepTemp]%10<<"\t"; } } void Outlin()//绘图显示当前状态 { int i=Store; //层数(依层画) string space; for(int j=0;j<broad;j++) // { // ==== ==== !!异常调试!! space=space+" "; // ====== ====== ====== } // [][][][] [][][][] [][][][] cout<<"\n\n"<<endl; // while(i>=0) { cout<<"\t"; // if(A->Top>=i)cout<<A->OutFloor(i); // else cout<<space; // ==== ==== ==== i=4 cout<<"\t"; // ====== ====== ====== i=3 if(B->Top>=i)cout<<B->OutFloor(i); // ======== ======== ======== i=2 else cout<<space; // ========== ========== ========== i=1 cout<<"\t"; // [][][][][][] [][][][][][] [][][][][][] i=0 if(C->Top>=i)cout<<C->OutFloor(i); // else cout<<space; // cout<<"\n"; // i--; } } void MoveShow() //演示 { int Step=1; string ans; Outlin(); do { cout<<"\n\t第"<<Step<<"步："<<STEP[Step]/10<<"-->"<<STEP[Step]%10<<endl; switch(STEP[Step]) { case 12: B->push(A->pop());//将A 塔上的盘子移动到B盘上 以下同理 break; case 13: C->push(A->pop()); break; case 21: A->push(B->pop()); break; case 23: C->push(B->pop()); break; case 31: A->push(C->pop()); break; case 32: B->push(C->pop()); } Outlin(); if(Step<step)system("pause"); Step++; }while(Step<=step); cout<<"\n 演示完毕！(输入任意字符退出)\n\n"; cin>>ans; } void GameMove()//游戏模式 { int from,go; Outlin(); do { cout<<"\n\t请输入移动哪个塔（1，2，3）："; cin>>from; while(from>3||from<1) { cout<<"-_-!"; cin>>from; } cout<<"\n\t请输入移到哪个塔（1，2，3）："; cin>>go; while(go>3||go<1||go==from) { cout<<"-_-!"; cin>>go; } int temp=from*10+go; switch(temp) { case 12: if(A->top->data<B->top->data)B->push(A->pop());//将A 塔上的盘子移动到B盘上 以下同理 else cout<<"ERROR!"; break; case 13: if(A->top->data<C->top->data)C->push(A->pop()); else cout<<"ERROR!"; break; case 21: if(B->top->data<A->top->data)A->push(B->pop()); else cout<<"ERROR!"; break; case 23: if(B->top->data<C->top->data)C->push(B->pop()); else cout<<"ERROR!"; break; case 31: if(C->top->data<A->top->data)A->push(C->pop()); else cout<<"ERROR!"; break; case 32: if(C->top->data<B->top->data)B->push(C->pop()); else cout<<"ERROR!"; } Outlin(); }while(C->Top!=Store); cout<<"你太强了！！\n"<<endl; system("pause"); } }; //////汉////诺/////塔////类////结////束//// ////////////MAIN/////函数//////开始////////////// void Arithmetic();//算法思想 Hanoi *hanoi;//定义汉诺威对象 void main() { int cord1,cord2; do { system("cls"); cout<<"\n\n\n\t\t\t 汉诺塔问题的动态演示 \n"; cout<<"\t\t\t ------------------- 李兆龙 钱伟 90622S\n"; cout<<"\n\t\t\t 1.建立汉诺塔\n"; cout<<"\n\t\t\t 2.算法思想\n"; cout<<"\n\t\t\t 3.结束程序\n"; cout<<"