Catalog
  1. 1. 数据结构国庆作业——
汉诺塔的非递归实现方法

数据结构国庆作业——

汉诺塔的非递归实现方法

版本一是STL版本;

#include<stack>
void move(int n, char from, char to) {
cout << "from " << from << " move " << n << " to " << to << endl;
}

struct hanoinode {
int n;
char from, pass, to;
};
void hanoi(int n, char from, char pass, char to) {
stack <hanoinode> s;
hanoinode par_outer = { n,from,pass,to };
while (!(par_outer.n == 0 && s.empty())) {
hanoinode par_inner = par_outer;
while (par_inner.n > 0) {
s.push(par_inner);
par_inner.n--;
swap(par_inner.pass, par_inner.to);
}
par_outer = s.top();
s.pop();
move(par_outer.n, par_outer.from, par_outer.to);
par_outer.n--;
swap(par_outer.from, par_outer.pass);
}
}
int main() {
int n;
cin >> n;
hanoi(n, 'a', 'b', 'c');
return 0;

版本二是顺序栈版

#define STACK_INIT_SIZE 100
#define INCREASEMENT 10
int cnt = 0;
struct hanoinode {
int n;
char from, pass, to;
};

typedef struct {
hanoinode *base;
hanoinode *top;
int stacksize;
}Sqstack;

bool Initstack(Sqstack &S) {
S.base = (hanoinode *)malloc(sizeof(hanoinode)*STACK_INIT_SIZE);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return 1;
}

bool push(Sqstack &S, hanoinode e) {
if (S.top - S.base == S.stacksize) {
S.base = (hanoinode *)realloc(S.base, (S.stacksize + INCREASEMENT) * sizeof(hanoinode));
S.top = S.base + S.stacksize;
S.stacksize += INCREASEMENT;
}
*S.top++ = e;
return 1;
}
void move(int n, char from, char to) {
cout << "from " << from << " move " << n << " to " << to << endl;
cnt++;
}


hanoinode GetTop(Sqstack S) {
//if (S.top == S.base) return 0;
hanoinode e;
e = *--S.top;
return e;
}
bool Pop(Sqstack &S) {
if (S.top == S.base) return 0;
hanoinode e;
e = *--S.top;
return 1;
}
void hanoi(int n, char from, char pass, char to) {
Sqstack s;
Initstack(s);
hanoinode par_outer = { n,from,pass,to };
while (!(par_outer.n == 0 && s.top == s.base)) {
hanoinode par_inner = par_outer;
while (par_inner.n > 0) {
push(s, par_inner);
par_inner.n--;
swap(par_inner.pass, par_inner.to);
}

par_outer = GetTop(s);
Pop(s);
move(par_outer.n, par_outer.from, par_outer.to);
par_outer.n--;
swap(par_outer.from, par_outer.pass);
}
}
int main() {
int n;
cin >> n;
hanoi(n, 'a', 'b', 'c');
cout << endl <<"共进行了" << cnt << "次";
return 0;
}
Author: superzhaoyang
Link: http://yoursite.com/2019/09/30/汉诺塔的非递归实现方法/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付宝

Comment