1.1.算法描述
Even算法的过程描述如下
（1）求出最大的活动整数m
（2）交换m和其箭头所掼向的与其相信的整数。
（3）交换所有满足p>m的整数的p的方向。
1.2.算法分析
由于每个数字还带有方向这个属性，因些需要使用自己定义数据类型。本算法中用一个结构来表示，结构有两个域，一个代表值，一个代码方向。
算法最大的难点在于，一是判断当前元素是否活动，二是需要找到最大的活动的元素。
通过试验生成过程，可以发现，其中最活跃的元素就是最大的那个元素，因为每交换一个比它小的元素，它都会由不活动状态变成活动状态。因此，在算法的实现上，要格外关注最大的那个元素。事实上，整个算法主要是在将最大的那个元素进行移动。也对最大的那个元素的位置进行了标识。
判断当前元素是否活动，有三种情况是不活动的：
1. 该元素在第一位，并且指向左边。
2. 该元素在最后一位，并且指向右边。
3. 该元素在中间，并且指向的元素比它要大。
通过这三个条件，就可判断当前元素是否活动的。
考虑扩展性，可排列的元素可以不从0开始，也可以不连续。因为排列归根结底是对元素的下标进行排列。因些可考虑让用户自己定义打印算法。
1
#ifndef U8
2#define U8 unsigned char
3#endif // U8
4
5#define DIR_LEFT 0 // 箭头向左
6#define DIR_RIGHT 1 // 箭头向右
7
8// 用于输出 一个排列
9typedef void(*AdjustCallback)(void *const, int size);
10
11// 一个排列列的元素，它包括数字和这个数字上箭头的方向
12typedef struct Item
13
{
14
int num;
15 U8 direct;
16
};
17
18// 默认输出排列的函数
19void def_printarray(void *const array, int size)
20{
21 if(array == NULL)
22 return;
23 for(int i=0;i<size;i++)
24
{
25 cout<<((Item **)array)[i]->num<<' ';
26
}
27 cout<<endl;
28}
29
30// 用Even方法生成排列的类
31class Even
32{
33private:
34 Item **array; // 一队排列数
35 int size; // 排列数，表明是几排列。如5排列
36private:
37 void initarray(); // 初始化排列
38 void deletearray(); // 删除排列的元素
39 void printarray(); // 打印排列元素
40 U8 isMaxActive(Item *item); // 判断最大的元素是否活动
41 U8 isItemActive(int index); // 判断当前元素是否活动
42 U8 forward(int index); // 数列元素的一次交换，它是将当前元素与前面（或后面）的元素进行交换，具体根据箭头来判断
43 void swap(Item **p1, Item **p2); // 具体的交换操作
44 int getMaxActiveIndex(); // 获取数列中，最大的活动的元素
45 void adjustPrimar(int index); // 将比当前元素大的元素的方向换向
46public:
47 Even();
48 Even(int size);
49 virtual ~Even();
50 void gen(); // 产生排列的主函数
51 inline int getsize()const;
52 inline void setsize(int size);
53
54 AdjustCallback _printarray; // 打印数列的回调函数，支持用户自定义
55};
56
57Even::Even()
58{
59 array = NULL;
60 size = 0;
61 _printarray = &def_printarray;
62}
63
64Even::Even(int size)
65{
66 array = NULL;
67 this->size = size;
68 _printarray = &def_printarray;
69}
70
71Even::~Even()
72{
73 //
74}
75
76int Even::getsize()const
77{
78 return size;
79}
80
81void Even::setsize(int size)
82{
83 deletearray();
84 this->size = size;
85}
86
87void Even::printarray()
88{
89 if(array == NULL)
90 return;
91 for(int i=0;i<size;i++)
92 {
93 cout<<array[i]->num<<' ';
94 }
95 cout<<endl;
96}
97
98void Even::deletearray()
99{
100 if(array == NULL)
101 return;
102
103 for(int i=0;i<size;i++)
104 delete array[i];
105 delete []array;
106 array = NULL;
107}
108
109void Even::initarray()
110{
111 if(size <= 0)
112 return;
113
114 deletearray();
115
116 array = new Item* [size];
117 Item *curr;
118
119 //
120 for(int i=0;i<size;i++)
121 {
122 curr = new Item; //(Item *)malloc(sizeof(curr));
123 curr->num = i;
124 curr->direct = 0; //<-
125 array[i] = curr;
126 }
127}
128
129void Even::gen()
130{
131 if(size <= 0)
132 return;
133 initarray();
134
135 Item &max = *(array[size - 1]);
136 int currindex = size - 1;
137 int activeindex = -1;
138 U8 dir;
139
140 //printarray();
141 _printarray(array, size);
142 do{
143 //
144 while(isMaxActive(&max))
145 {
146 //exchange
147 dir = forward(currindex);
148 //printarray();
149 _printarray(array, size);
150 // adjust
151 if(dir == DIR_LEFT)
152 currindex--;
153 else currindex++;
154 }
155
156 //
157 activeindex = getMaxActiveIndex();
158 if(activeindex == -1)
159 break;
160
161 dir = forward(activeindex);
162
163 //
164 if(dir == DIR_LEFT)
165 activeindex--;
166 else activeindex++;
167 adjustPrimar(activeindex);
168 //printarray();
169 _printarray(array, size);
170
171 }while(activeindex != -1);
172}
173
174U8 Even::isMaxActive(Item *item)
175{
176 return (item->direct == DIR_LEFT && (item != array[0])) ||
177 (item->direct == DIR_RIGHT && (item != array[size - 1]));
178}
179
180U8 Even::isItemActive(int index)
181{
182 if(index == 0 && array[index]->direct == DIR_LEFT)
183 return 0;
184 else if(index == size-1 && array[index]->direct == DIR_RIGHT)
185 return 0;
186 if(array[index]->direct==DIR_LEFT && array[index] > array[index-1])
187 return 1;
188 if(array[index]->direct==DIR_RIGHT && array[index] > array[index+1])
189 return 1;
190 return 0;
191}
192U8 Even::forward(int index)
193{
194 Item *item = array[index];
195 if(item->direct == DIR_LEFT && index > 0)
196 {
197 swap(&array[index], &array[index - 1]);
198 return DIR_LEFT;
199 }
200 else if(item->direct == DIR_RIGHT && index < size - 1)
201 {
202 swap(&array[index], &array[index + 1]);
203 return DIR_RIGHT;
204 }
205 return 0;
206}
207
208void Even::swap(Item **p1, Item **p2)
209{
210 Item *tmp = *p2;
211 *p2 = *p1;
212 *p1 = tmp;
213}
214
215int Even::getMaxActiveIndex()
216{
217 int index = -1;
218 Item *currmax = NULL;
219 for(int i=0;i<size;i++)
220 {
221 if(isItemActive(i) && (currmax == NULL || currmax->num < array[i]->num))
222 {
223 index = i;
224 currmax = array[i];
225 }
226 }
227 return index;
228}
229
230void Even::adjustPrimar(int index)
231{
232 for(int i=0;i<size;i++)
233 {
234 if(i==index) continue;
235 if(array[i]->num > array[index]->num)
236 array[i]->direct = (array[i]->direct == DIR_LEFT? DIR_RIGHT:DIR_LEFT);
237 }
238}
239
240void test1();
241void test2();
242void my_printarray(void *const array, int size);
243
244int main(int argc, char *argv[])
245{
246/* int size, selcount;
247 cin>>size;
248 if (size <= 2)
249 return -1;
250
251 Even e;
252 e.setsize(size);
253 e.gen();
254 */
255// test1();
256 test2();
257 system("PAUSE");
258 return 0;
259}
260
261void test1()
262{
263 cout<<"请输入排列的阶数：";
264 int size, selcount;
265 cin>>size;
266 if (size <= 2)
267 return;
268
269 Even e;
270 e.setsize(size);
271 e.gen();
272}
273
274int arrTarget[] = {12, 9, 55, 34, 1};
275void test2()
276{
277 cout<<"原数列为：";
278 for(int i=0;i<sizeof(arrTarget)/sizeof(int);i++)
279 cout<<arrTarget[i]<<",";
280 cout<<endl;
281
282 Even e;
283 e.setsize(5);
284 e._printarray = &my_printarray;
285 e.gen();
286 cout<<endl;
287}
288
289void my_printarray(void *const array, int size)
290{
291 int index;
292 for(int i=0;i<size;i++)
293 {
294 index = ((Item **)array)[i]->num;
295 cout<<arrTarget[index]<<' ';
296 }
297 cout<<endl;
298}
#ifndef U82
#define U8 unsigned char3
#endif // U84
5
#define DIR_LEFT 0 // 箭头向左6
#define DIR_RIGHT 1 // 箭头向右7
8
// 用于输出 一个排列9
typedef void(*AdjustCallback)(void *const, int size);10
11
// 一个排列列的元素，它包括数字和这个数字上箭头的方向12
typedef struct Item13
{
14
int num;15
U8 direct; 16
};17
18
// 默认输出排列的函数19
void def_printarray(void *const array, int size)20
{21
if(array == NULL)22
return;23
for(int i=0;i<size;i++)24
{
25
cout<<((Item **)array)[i]->num<<' ';26
}27
cout<<endl;28
}29
30
// 用Even方法生成排列的类31
class Even32
{33
private:34
Item **array; // 一队排列数35
int size; // 排列数，表明是几排列。如5排列36
private:37
void initarray(); // 初始化排列38
void deletearray(); // 删除排列的元素39
void printarray(); // 打印排列元素40
U8 isMaxActive(Item *item); // 判断最大的元素是否活动41
U8 isItemActive(int index); // 判断当前元素是否活动42
U8 forward(int index); // 数列元素的一次交换，它是将当前元素与前面（或后面）的元素进行交换，具体根据箭头来判断43
void swap(Item **p1, Item **p2); // 具体的交换操作44
int getMaxActiveIndex(); // 获取数列中，最大的活动的元素45
void adjustPrimar(int index); // 将比当前元素大的元素的方向换向46
public:47
Even();48
Even(int size);49
virtual ~Even();50
void gen(); // 产生排列的主函数51
inline int getsize()const;52
inline void setsize(int size);53
54
AdjustCallback _printarray; // 打印数列的回调函数，支持用户自定义55
};56
57
Even::Even()58
{59
array = NULL;60
size = 0;61
_printarray = &def_printarray;62
}63
64
Even::Even(int size)65
{66
array = NULL;67
this->size = size;68
_printarray = &def_printarray;69
}70
71
Even::~Even()72
{73
//74
}75
76
int Even::getsize()const 77
{78
return size;79
}80
81
void Even::setsize(int size)82
{83
deletearray();84
this->size = size;85
} 86
87
void Even::printarray()88
{89
if(array == NULL)90
return;91
for(int i=0;i<size;i++)92
{93
cout<<array[i]->num<<' ';94
}95
cout<<endl;96
}97
98
void Even::deletearray()99
{100
if(array == NULL)101
return;102
103
for(int i=0;i<size;i++)104
delete array[i];105
delete []array;106
array = NULL;107
}108
109
void Even::initarray()110
{111
if(size <= 0)112
return;113
114
deletearray();115
116
array = new Item* [size];117
Item *curr;118
119
// 120
for(int i=0;i<size;i++)121
{122
curr = new Item; //(Item *)malloc(sizeof(curr));123
curr->num = i;124
curr->direct = 0; //<-125
array[i] = curr;126
}127
}128
129
void Even::gen()130
{131
if(size <= 0)132
return;133
initarray();134
135
Item &max = *(array[size - 1]);136
int currindex = size - 1;137
int activeindex = -1;138
U8 dir;139
140
//printarray();141
_printarray(array, size);142
do{143
// 144
while(isMaxActive(&max))145
{146
//exchange147
dir = forward(currindex);148
//printarray();149
_printarray(array, size);150
// adjust151
if(dir == DIR_LEFT)152
currindex--;153
else currindex++;154
}155
156
// 157
activeindex = getMaxActiveIndex();158
if(activeindex == -1)159
break;160
161
dir = forward(activeindex);162
163
// 164
if(dir == DIR_LEFT)165
activeindex--;166
else activeindex++;167
adjustPrimar(activeindex);168
//printarray();169
_printarray(array, size);170
171
}while(activeindex != -1);172
}173
174
U8 Even::isMaxActive(Item *item)175
{176
return (item->direct == DIR_LEFT && (item != array[0])) ||177
(item->direct == DIR_RIGHT && (item != array[size - 1])); 178
}179
180
U8 Even::isItemActive(int index)181
{182
if(index == 0 && array[index]->direct == DIR_LEFT)183
return 0;184
else if(index == size-1 && array[index]->direct == DIR_RIGHT)185
return 0;186
if(array[index]->direct==DIR_LEFT && array[index] > array[index-1])187
return 1;188
if(array[index]->direct==DIR_RIGHT && array[index] > array[index+1])189
return 1;190
return 0;191
}192
U8 Even::forward(int index)193
{194
Item *item = array[index];195
if(item->direct == DIR_LEFT && index > 0)196
{197
swap(&array[index], &array[index - 1]);198
return DIR_LEFT;199
}200
else if(item->direct == DIR_RIGHT && index < size - 1)201
{202
swap(&array[index], &array[index + 1]);203
return DIR_RIGHT;204
}205
return 0;206
}207
208
void Even::swap(Item **p1, Item **p2)209
{210
Item *tmp = *p2;211
*p2 = *p1;212
*p1 = tmp;213
}214
215
int Even::getMaxActiveIndex()216
{217
int index = -1;218
Item *currmax = NULL;219
for(int i=0;i<size;i++)220
{221
if(isItemActive(i) && (currmax == NULL || currmax->num < array[i]->num))222
{223
index = i;224
currmax = array[i];225
}226
}227
return index;228
}229
230
void Even::adjustPrimar(int index)231
{232
for(int i=0;i<size;i++)233
{234
if(i==index) continue;235
if(array[i]->num > array[index]->num)236
array[i]->direct = (array[i]->direct == DIR_LEFT? DIR_RIGHT:DIR_LEFT);237
}238
}239
240
void test1();241
void test2();242
void my_printarray(void *const array, int size);243
244
int main(int argc, char *argv[])245
{246
/* int size, selcount;247
cin>>size;248
if (size <= 2)249
return -1;250
251
Even e;252
e.setsize(size);253
e.gen();254
*/255
// test1();256
test2();257
system("PAUSE"); 258
return 0;259
}260
261
void test1()262
{263
cout<<"请输入排列的阶数：";264
int size, selcount;265
cin>>size;266
if (size <= 2)267
return;268
269
Even e;270
e.setsize(size);271
e.gen(); 272
}273
274
int arrTarget[] = {12, 9, 55, 34, 1};275
void test2()276
{277
cout<<"原数列为：";278
for(int i=0;i<sizeof(arrTarget)/sizeof(int);i++)279
cout<<arrTarget[i]<<",";280
cout<<endl;281
282
Even e;283
e.setsize(5);284
e._printarray = &my_printarray;285
e.gen();286
cout<<endl;287
}288
289
void my_printarray(void *const array, int size)290
{291
int index;292
for(int i=0;i<size;i++)293
{294
index = ((Item **)array)[i]->num;295
cout<<arrTarget[index]<<' ';296
}297
cout<<endl;298
}