main.cpp

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

#include <limits.h>
#include <stdlib.h>
#include <iostream.h>

const int MAX_VERTEX_NUM = 20;

/* 用邻接矩阵表示的AOV图
 */
struct AOVGraph {
	int vexnum;
	int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
};


int FullTopologicalSort(AOVGraph g, int i, bool sorted[], int output, int arr[]) {
	// 有向图g用邻接矩阵存储
	// 输出它的所有拓扑排序序列
	// 递归函数

	// 参数:
	// g 图，传入时已经被拷贝
	// i 当前层的开始位置
	// sorted 标示第i列是否已被排序
	// output 当前已输出的元素的数目
	// arr 输出数组，部分排序的结果记录于此，最后输出到cout
	// 返回值 指示下一个应当传入的i (下一个开始位置)

	if (output == g.vexnum) {	// 排序已经完成，输出
		for (int j = 0; j < g.vexnum; ++j)
			cout << arr[j]+1 << " ";
		cout << endl;
		return g.vexnum;
	}
	for (; i < g.vexnum; ++i) {
		if (sorted[i]) continue;	// 已经排过序了
		bool flag = false;			// 记录本列是否全为零
		for (int j = 0; j < g.vexnum; ++j) {
			if (g.matrix[j][i] != 0) {
				flag = true;
				break;
			}
		}
		if (!flag) {	// 本列全为零
			arr[output++] = i;	// 输出列号i
			for (int k = 0; k < g.vexnum; ++k) {	// 第i行置零
				g.matrix[i][k] = 0;		// 由于g已经被拷贝，不会影响上一层的g
			}
			sorted[i] = true;			// 标示本列已排序
			for (int p = 0; p < g.vexnum;) {	// 递归排序余下的结点
				p = FullTopologicalSort(g, p, sorted, output, arr);
			}
			sorted[i] = false;			// 回溯：重新标示本列为未排序
			return i+1;					// 返回下一个应该传入的i (下一个开始位置)
		}
	}
	return g.vexnum;					// 本层搜索结束
} // FullTopologicalSort

AOVGraph CreateAOVGraph() {
	// 构造AOV图，供演示用，产生一个固定的
	// (上课的图幻灯片graphnew.ppt，第55页，幻灯片上左边矩阵第2行有错误)
	

	AOVGraph g = { 7, 
		{
			0, 1, 1, 0, 0, 0, 0,		0,0,0,0,0,0,0,0,0,0,0,0,0,
			0, 0, 0, 1, 1, 1, 0,		0,0,0,0,0,0,0,0,0,0,0,0,0,
			0, 0, 0, 0, 1, 0, 1,		0,0,0,0,0,0,0,0,0,0,0,0,0,
			0, 0, 0, 0, 0, 0, 0,		0,0,0,0,0,0,0,0,0,0,0,0,0,
			0, 0, 0, 0, 0, 0, 1,		0,0,0,0,0,0,0,0,0,0,0,0,0,
			0, 0, 0, 0, 0, 0, 1,		0,0,0,0,0,0,0,0,0,0,0,0,0,
			0, 0, 0, 0, 0, 0, 0,		0,0,0,0,0,0,0,0,0,0,0,0,0,
		}
	};

	return g;

} // CreateAOVGraph

int main() {

	cout << "求出一个AOV图的所有合理的拓扑排序的序列\n"
		    "采用上课的图幻灯片graphnew.ppt，第55页的那个图，\n"
			"幻灯片上左边矩阵第2行有错误，此处已更正\n"
		 << endl;


	cout << "所有序列为: " << endl;
	bool sorted[MAX_VERTEX_NUM] = {0};
	int array[MAX_VERTEX_NUM] = {0};
	FullTopologicalSort(CreateAOVGraph(), 0, sorted, 0, array);

	system("pause");
	return 0;
}