|
#2
xufen3402009-09-03 13:50
//你写的stack太复杂，我简化一下了，结果可以在当前目录out.txt察看。
#include <fstream> #include <vector> #include <iostream> using namespace std; /*stack*/ ofstream fout("out.txt"); template<typename T> class stack{ private: vector<T> elems; public: void push(T const&); void pop(); T top() const; bool empty() const{ return elems.empty(); }; vector<T>& getelems(){ return this->elems;}; friend ostream& operator<<(ostream& out,stack<T>& x); }; template <class T> ostream& operator<<(ostream& out,stack<T>& x) { for(int i=0;i<x.getelems().size();i++){ out<<x.getelems()[i]; out<<endl; } return out; } template<typename T> void stack<T>::push(T const& elem) { elems.push_back(elem); } template<typename T> void stack<T>::pop() { if(elems.empty()){ throw out_of_range("stack<>::pop():empty stack"); } elems.pop_back(); } template<typename T> T stack<T>::top() const { if(elems.empty()){ throw out_of_range("stack<>::top():empty stack"); } return elems.back(); } /*判断x，y， 更改3个stack*/ void Move(int n,char x,char y,stack<int>& stack1,stack<int>& stack2,stack<int>& stack3) { fout<<"把"<<n<<"号从"<<x<<"挪动到"<<y<<endl; switch(x){ case 'a': stack1.pop(); break; case 'b': stack2.pop(); break; case 'c': stack3.pop(); break; } switch(y){ case 'a': stack1.push(n); break; case 'b': stack2.push(n); break; case 'c': stack3.push(n); break; } fout<<"第一个塔："<<endl<<stack1<<endl; fout<<"第二个塔："<<endl<<stack2; fout<<"第三个塔："<<endl<<stack3<<endl; } void Hannoi(int n,char a,char b,char c,stack<int>& stack1,stack<int>& stack2,stack<int>& stack3) { if(n==1) Move(1,a,c,stack1,stack2,stack3); else { Hannoi(n-1,a,c,b,stack1,stack2,stack3); Move(n,a,c,stack1,stack2,stack3); Hannoi(n-1,b,a,c,stack1,stack2,stack3); } } int main() { stack<int> stack1;//第一个 stack<int> stack2;//第二个 stack<int> stack3;//第二个 for(int i=7;i>0;i--) stack1.push(i);//7个号码压入 fout<<"以下是7层汉诺塔的解法:"<<endl; Hannoi(7,'a','b','c',stack1,stack2,stack3); cout<<"输出完毕！"<<endl; return 0; } |
书上例题用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 编辑 ]
