even.cpp

采用EVEN方法实现排列 生成{1

#include<iostream>
using std::cout;
using std::cin;
using std::endl;

#include<new>

int check(int *, int);
void exchange(int &, int &);
void result(int *, int);
void update(int *, int *, int *, int);
const int left = 1;
const int right = 0;

int main()
{
	int counter;
	int max = 0;
	int flag = 0;

	cout <<"请输入待排列的元素的个数，即n = ";
	cin >>counter;

	int *array1 = new int[counter + 1];
	int *array2 = new int[counter + 1];
	int *direction = new int[counter + 1];//这个数组用来标明方向
	for(int i = 1; i < counter + 1; i++)
		array1[i] = i;

	array2[1] = 0;
	for(int j = 2; j < counter + 1; j++)//如果元素是活动的就赋值为1，如果不是活动的赋值为0
		array2[j] = 1;
	
	for(int k = 1; k < counter + 1; k++)
		 direction[k] = left;

	result(array1, counter);


	cout<<"排列结果为:\n";
	//检验元素是否为活动的
	while(check(array2, counter) == 1){
		max = 0;
		flag = 0;

		for (int p = 1; p < counter + 1; p++)
			if (array2[array1[p]] == 1 && array1[p] > max)
			{
				max = array1[p];
				flag = p;
			}
			switch(direction[max])
			{
			case left:
				exchange(array1[flag - 1], array1[flag]);
				break;
			case right:
				exchange(array1[flag + 1], array1[flag]);
				break;
			}

			for(int q = 1; q < counter + 1; q++)
				if(array1[q] > max)
				{
					if(direction[array1[q]] == left)
						direction[array1[q]] = right;
					else
						direction[array1[q]] = left;
				}
			update(array1, array2, direction, counter);


	result(array1, counter);
	}

	return 0;
}

int check(int *a, int count)//检验是否结束
{
	for(int x = 1; x < count + 1; x++)
		if(a[x] == 1)
			return 1;
	return 0;
}

void exchange(int &a1, int &a2)
{
	int temp;
	temp = a1;
	a1 = a2;
	a2 = temp;
}

void result(int *a, int count)
{
	for(int y = 1; y < count + 1; y++)
	cout << a[y] <<' ';
	cout<<endl;
}

void update(int *a, int *b, int *direct, int count)
{
	if(direct[a[1]] == left)
		b[a[1]] = 0;
	else 
		if(a[1] > a[2])
			b[a[1]] = 1;
		else 
			b[a[1]] = 0;
	for (int i = 2;i < count;i++)
		switch(direct[a[i]])
	{
		case left:
			if(a[i] > a[i - 1])
				b[a[i]] = 1;
			else
				b[a[i]] = 0;
			break;
		case right:
			if(a[i] > a[i + 1])
				b[a[i]] = 1;
			else
				b[a[i]] = 0;
			break;
	}
	if(direct[a[count]] == right)
		b[a[count]] = 0;
	else if(a[count] > a[count - 1])
		b[a[count]] = 1;
	else 
		b[a[count]] = 0;
}