UC知道用栈实现汉诺塔问题
来源：百度知道 编辑：UC知道 时间：2024/06/28 07:49:50
最近在看数据结构的书，看到关于栈这里，对用栈解决汉诺塔问题百思不得其解，望高手指点一二。现将书上代码贴到下面：
enum TOHop { DOMOVE, DOTOH };
class TOHobj
{
public:
TOHop op;
int num;
Pole start, goal, tmp;
// DOTOH operation
TOHobj(int n, Pole s, Pole g, Pole t)
{
op = DOTOH;
num = n;
start = s;
goal = g;
tmp = t;
}
//DOMOVE operation
TOHobj(Pole s, Pole g)
{
op = DOMOVE;
start = s;
goal = g;
}
};
void TOH(int n, Pole start, Pole goal, Pole tmp, Stack <TOHobj*>& S)
{
S.push(new TOHobj(n, start, goal, tmp));
TOHobj* t;
while (S.pop(t))
{
if (t->op == DOMOVE)
move(t->start, t->goal);
else if (t->num > 0)
{
int num = t>num;
Pole tmp = t->tmp; Pole goal = t-
enum TOHop { DOMOVE, DOTOH };
class TOHobj
{
public:
TOHop op;
int num;
Pole start, goal, tmp;
// DOTOH operation
TOHobj(int n, Pole s, Pole g, Pole t)
{
op = DOTOH;
num = n;
start = s;
goal = g;
tmp = t;
}
//DOMOVE operation
TOHobj(Pole s, Pole g)
{
op = DOMOVE;
start = s;
goal = g;
}
};
void TOH(int n, Pole start, Pole goal, Pole tmp, Stack <TOHobj*>& S)
{
S.push(new TOHobj(n, start, goal, tmp));
TOHobj* t;
while (S.pop(t))
{
if (t->op == DOMOVE)
move(t->start, t->goal);
else if (t->num > 0)
{
int num = t>num;
Pole tmp = t->tmp; Pole goal = t-
递归的时候本来要用到栈的，只不过是系统自动调用栈罢了
呵呵。递归一般是用系统提供的栈。（当然也可以用自己建的）
栈是算是一个容器。并不算一种算法。
当然上面用的方法依然是递归。
这个东西一下也不好讲，还是用递归给你讲吧，先想这个棵树Tn，先把最下面的n要搬走，就得把上面的n－1个先搬走，这个n－1个也形成一个树T(n－1),然后又把这n－1个搬到n上面又形成一个T(n－1)的树，这个你就可以画出来，把n做做根，一个T(n－1)做左子树，一个T(n－1)做右子树，这个一直下去可以发现这树的深度为n的完全二叉树，而这个搬过程就是先序历遍这二叉树的过程，搬了次数也就是这树的结点的个数，2^n－1次，如果这个可以看到，只有2n－1个无素在栈中。