main.cpp

一个我的数据结构解题集合

#include <iostream>
#include <stdlib.h>
#include <assert.h>
#include "Stack.h"
#include "IoUtils.h"

using namespace std;

typedef Stack<int> Rail;	// 铁轨栈类型

/* 在cout打印铁路栈的内容
 */
inline
void print(const Rail& rail) {
	int i = rail.size();
	while (--i >= 0)
		cout << rail[i] << ' ';
	cout << endl;
} // print(const Rail&)


/* 将车厢从from移动到to
 */
inline
void transfer(Rail& from, Rail& to) {
	to.push( from.top() );
	from.pop();
} // transfer(Rail&, Rail&)


/* 输入火车车厢数目n, 输出所有可能, 
 * 输出所有可能的出栈序列, 返回其数目
 */
int ArrangeTrain(int n) {

	assert(n > 0);

	Rail rail[3];			// 3个铁轨栈
	Stack<bool> is_left;	// 记录本节点是否为左子节点（回溯信息）
	int cnt = 0;

	for (int i = 1; i <= n; ++i) rail[0].push(i);	// 初始化原始火车序列

	do {
		// 生成输出
		while ( !rail[0].isEmpty() || !rail[1].isEmpty() ) {	// 存在左子树或右子树
			while ( !rail[0].isEmpty() ) {		// 若存在左子树，向左走到底
				transfer(rail[0], rail[1]);		// 向左走
				is_left.push(true);				// 本节点为左子节点
			}
			if ( !rail[1].isEmpty() ) {			// 存在右子树
				transfer(rail[1], rail[2]);		// 向右走
				is_left.push(false);			// 本节点为右子节点
			}
		}

		++cnt;				// 计数
		print(rail[2]);		// 打印输出

		// 回溯
		while ( !is_left.isEmpty() ) {
			if ( is_left.top() ) {		// 本节点为左子节点
				transfer(rail[1], rail[0]);		// 回溯
				is_left.pop();
				if ( !rail[1].isEmpty() ) {		// 存在右子节点
					transfer(rail[1], rail[2]);	// 向右走
					is_left.push(false);
					break;						// 继续遍历
				}
			} else {					// 本节点为右子节点
				transfer(rail[2], rail[1]);
				is_left.pop();
			}
		}
	} while ( !is_left.isEmpty() );		// 若栈空，遍历结束

	return cnt;
} // ArrangeTrain(int)

int main() {
	cout << "请输入火车车厢的数目: ";
	int n = getPositiveInteger();

	cout << "所有可能出栈序列为: \n";
	n = ArrangeTrain(n);

	cout << "序列个数为: " << n << endl;

	system("pause");

	return 0;
}