數(shù)據(jù)結(jié)構(gòu)課程報(bào)告漢諾塔.doc

目 錄1 課題需求32 概要設(shè)計(jì)32.1 遞歸32.2 非遞歸43 詳細(xì)設(shè)計(jì)和實(shí)現(xiàn)44 調(diào)試與測(cè)試134.1 啟動(dòng)窗口134.2 遞歸實(shí)現(xiàn)134.3 非遞歸實(shí)現(xiàn)154.4 退出165 致謝176 參考文獻(xiàn)182 概要設(shè)計(jì)漢諾塔是一個(gè)經(jīng)典的問題，曾被稱為“世界末日問題”。此次程序設(shè)計(jì)全面討論了解決此問題的方案，詳細(xì)研究，了解，解決問題的算法設(shè)計(jì)，給出了具體算法，最后由手工輸入測(cè)試數(shù)，運(yùn)用遞歸與非遞歸算法得出結(jié)果。2.1 遞歸若只有一個(gè)圓盤的話直接將圓盤移至C桿；若為N個(gè)圓盤的話將N-1個(gè)圓盤當(dāng)作整體借助C桿移至B桿，將N號(hào)盤移至C桿，再借助A桿重復(fù)上面的操作即可將圓盤移至C桿。2.2 非遞歸看出二叉樹實(shí)現(xiàn)，假設(shè)A一開始有n個(gè)圓盤，前n-1個(gè)A通過C移到B上看出左孩子，第n個(gè)移到C看出根，將B中n-1通過A移到C看成右孩子，建立完全二叉樹。主要借助二叉樹的非遞歸中序遍歷方法實(shí)現(xiàn)，利用棧堆來實(shí)現(xiàn)。3 詳細(xì)設(shè)計(jì)和實(shí)現(xiàn)DiGui.cpp文件：#include/遞歸法解決漢諾塔問題void HanNuoTaDiGui(int n,char a,char b,char c)if(n2)cout 圓盤n : 從a移到cendl;return;HanNuoTaDiGui(n-1,a,c,b);/n-1個(gè)圓盤移到bcout 圓盤n : 從a移到cendl;HanNuoTaDiGui(n-1,b,a,c);munu.cpp文件：/目錄菜單#includevoid munu()cout*endl;cout*endlendl;cout 漢諾塔 endlendl;cout*endl;cout*endl;cout請(qǐng)選擇實(shí)現(xiàn)的方法：endl;cout 1 代表遞歸方法。endl;cout 2 代表非遞歸方法。endl;cout 0 代表退出。endl;主程序：#include#include /from指要轉(zhuǎn)移的盤子的柱子，pass指經(jīng)過的中間柱子，aim指目的盤子所在的柱子struct Tree/樹結(jié)點(diǎn)int n;char from;char pass;char aim;/構(gòu)造函數(shù)Tree(int m,char a,char b,char c)n=m;from=a;pass=b;aim=c;Tree()/判斷是否為空結(jié)點(diǎn)bool IsNullNode()if(n1)return true;return false;/棧，用來存放盤子class Stack Tree *data;int top;int maxSize;public:Stack(int sz);Stack();bool IsEmpty();/判斷是否為空棧bool IsFull();/判斷是否為滿棧bool Push(Tree x);/進(jìn)棧bool Push(int m,char a,char b,char c);/進(jìn)棧bool Pop(Tree &x);/出棧bool GetTop(Tree &x);/取棧頂;Stack:Stack(int sz)/構(gòu)造函數(shù)maxSize=sz;data=new TreemaxSize;top=-1;Stack:Stack()/析構(gòu)函數(shù)delete data;/判斷是否為空棧bool Stack:IsEmpty()if(top=-1)return true;return false;/判斷是否為滿棧bool Stack:IsFull()if(top=maxSize-1)return true;return false;/出棧bool Stack:Pop(Tree &x)if(IsEmpty()return false;x=datatop-;return true;bool Stack:Push(Tree x)if(IsFull()return false;data+top=x;return true; bool Stack:Push(int m,char a,char b,char c)if(IsFull()return false;top+;datatop.n=m;datatop.aim=c;datatop.from=a;datatop.pass=b;return true;bool Stack:GetTop(Tree &x)if(IsEmpty()return false;x=datatop;return true;/from指要轉(zhuǎn)移的盤子，aim指目的盤子，pass指經(jīng)過上午中間盤子void HanNuoTa(int n,char a,char b,char c)Stack s(n+1);Tree p;int i=1;s.Push(n,a,b,c);while(!s.IsEmpty()s.GetTop(p);while(!p.IsNullNode()s.Push(p.n-1,p.from,p.aim,p.pass);/左孩子 進(jìn)棧s.GetTop(p);s.Pop(p);/退棧if(!s.IsEmpty()/棧不空s.Pop(p);/退棧cout第i+次t圓盤p.n p.fromp.aimendl;/輸出s.Push(p.n-1,p.pass,p.from,p.aim);/右孩子void HanNuoTaDiGui(int n,char a,char b,char c);void munu();void main()system(color 1f); /*設(shè)置系統(tǒng)顏色，本系統(tǒng)為藍(lán)底亮白色字*/munu();while(true)int n,num;coutn;switch(n)case 0:goto loop;case 1:/1代表遞歸方法coutnum;HanNuoTaDiGui(num,A,B,C);munu();break;case 2:/2代表非遞歸方法coutnum;HanNuoTa(num,A,B,C);munu();break;default:cout您的選擇不符合要求，請(qǐng)重新輸入！endl;break;loop:cout歡迎再次使用本程序！endl;4 調(diào)試與測(cè)試4.1 啟動(dòng)窗口4.2 遞歸實(shí)現(xiàn)輸入圓盤個(gè)數(shù)為5（也可以是其他數(shù)，但不要太大，時(shí)間花銷大）4.3 非遞歸實(shí)現(xiàn)輸入圓盤個(gè)數(shù)為5（也可以是其他數(shù)，但不要太大，時(shí)間花銷大）4.4 退出5 致謝*6 參考文獻(xiàn)1 殷人昆.數(shù)據(jù)結(jié)構(gòu) 用