还是汉诺塔的问题
书上例题用Stack这个堆栈类来保存每次移动后三个塔内里的情况，但没写出显示出来的代码。我记得原来论坛里有人做了一个汉诺塔的游戏，不知道他用的是不是堆栈,保存搜没搜出来。
我尝试写出每次移动后输出塔内里情况，按下面的例子，用5调用TowersOfHanoi第一的输出应该为:
**
***
****
*****
因为第一个塔就出错了，所以来不及考虑其它两个塔的输出，不过暂时也没有思路，在同一排同时输出三个塔里的情况。
我写的输出代码 输出了两次1塔里的情况,也就是移动的第三次出错，不知道是错在哪里了.
去掉输出，运行是不会出错的.
#include <iostream.h>
class NoMem
{
public:
NoMem(){}
};
void OutOfBounds()
{
throw NoMem();
}
template <class T>
class Stack
{
public:
Stack(int MaxStackSize=10);
~Stack(){delete []stack;}
bool IsEmpty()const {return top==-1;}
bool IsFull()const {return top==MaxTop;}
T Top()const;
Stack<T>& Add(const T& x);
Stack<T>& Delete(T& x);
int Length(){return top+1;}
void Output(ostream& out) const;
Stack<T>& Divide(Stack<T>& x);
Stack<T>& Merge(Stack<T>& x);
friend istream& operator>>(istream& in,Stack<T>& x);
private:
int top;
int MaxTop;
T *stack;
};
template <class T>
Stack<T>& Stack<T>::Merge(Stack<T>& x)
{
int n=top+x.top+2;
if (MaxTop<n)
{
delete []stack;
stack=new T[n];
}
int xi=0;
for(int i=top+1;i<n;i++)
{
stack[i]=x.stack[xi++];
top++;
}
delete []x.stack;
x.stack=new T[20];
x.top=-1;
return *this;
}
template <class T>
Stack<T>& Stack<T>::Divide(Stack<T>& x)
{
int n=x.top+1;
for(int i=0;i<n/2;i++)
{
stack[i]=x.stack[i];
top++;
}
x.top=0;
for( ;i<n;i++)
{
x.stack[x.top++]=x.stack[i];
}
x.top--;
return *this;
}
template <class T>
istream& operator>>(istream& in,Stack<T>& x)
{
T t;
cin>>t;
x.Add(t);
return in;
}
template <class T>
void Stack<T>::Output(ostream& out) const
{
int n=top+1;
for(int i=0;i<n;i++)
out<<stack[i] ;
cout<<endl;
}
template <class T>
ostream& operator<<(ostream& out,Stack<T>& x)
{
x.Output(out);
return out;
}
template <class T>
Stack<T>::Stack(int MaxStackSize)
{
MaxTop=MaxStackSize-1;
stack=new T[MaxStackSize];
top=-1;
}
template <class T>
T Stack<T>::Top()const
{
if(IsEmpty()) throw OutOfBounds();
else return stack[top];
}
template <class T>
Stack<T>& Stack<T>::Add(const T& x)
{
stack[++top]=x;
return *this;
}
template <class T>
Stack<T>& Stack<T>::Delete(T& x)
{
if(IsEmpty()) throw OutOfBounds();
x=stack[top--];
return *this;
}
void TowersOfHanoi(int);
class Hanoi
{
friend void TowersOfHanoi(int);
public:
void TowerOfHanoi(int n,int x,int y,int z);
private:
Stack<int> *S[4];
};
void Hanoi::TowerOfHanoi(int n,int x,int y,int z)
{
int d;
if(n>0)
{
TowerOfHanoi(n-1,x,z,y);
S[x]->Delete(d);
S[y]->Add(d);
int l=S[x]->Length();// 从这里
int t=S[x]->Top();
for(int i=0;i<l;i++)
{
for(int j=0;j<t;j++)
cout<<"*";
cout<<endl;
t++;
}
cout<<endl;
// 到这里是我写的输入代码，如果去掉运行还是蛮正常
TowerOfHanoi(n-1,z,y,x);
}
}
void TowersOfHanoi(int n)
{
Hanoi X;
X.S[1]=new Stack<int> (n);
X.S[2]=new Stack<int> (n);
X.S[3]=new Stack<int> (n);
for(int d=n;d>0;d--)
X.S[1]->Add(d);
X.TowerOfHanoi(n,1,2,3);
}
void main()
{
TowersOfHanoi(5);
}
[ 本帖最后由 mfkblue 于 2009-9-3 00:27 编辑 ]
