汉诺塔的非递归实现方法

数据结构国庆作业——

汉诺塔的非递归实现方法

版本一是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;
}