マージ領域アルゴリズム
6907 ワード
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
void print_vec(const std::vector<int> &ivec)
{
int i = 0;
for (std::vector<int>::const_iterator cit = ivec.begin();
cit != ivec.end(); ++cit) {
cout << *cit << "\t";
++i;
if (i % 5 == 0) {
cout << endl;
}
}
cout << endl;
}
void delete_repeated_element(const std::vector<int> &ivec1, const std::vector<int> &ivec2,
std::vector<int> &ivec3, std::vector<int> &ivec4)
{
int current_value;
int before_value;
int after_value;
for (vector<int>::const_iterator cit = ivec1.begin(); cit != ivec1.end(); ++cit) {
current_value = *cit;
if (cit == ivec1.begin()) {
before_value = *(ivec1.end() - 1);
} else {
before_value = *(cit - 1);
}
if (cit == ivec1.end() - 1) {
after_value = *(ivec1.begin());
} else {
after_value = *(cit + 1);
}
if (find(ivec2.begin(), ivec2.end(), current_value) != ivec2.end()
&& find(ivec2.begin(), ivec2.end(), before_value) != ivec2.end()
&& find(ivec2.begin(), ivec2.end(), after_value) != ivec2.end()) {
//cout << before_value << "\t" << current_value << "\t" << after_value;
} else {
ivec3.push_back(*cit);
}
}
for (vector<int>::const_iterator cit = ivec2.begin(); cit != ivec2.end(); ++cit) {
current_value = *cit;
if (cit == ivec2.begin()) {
before_value = *(ivec2.end() - 1);
} else {
before_value = *(cit - 1);
}
if (cit == ivec2.end() - 1) {
after_value = *(ivec2.begin());
} else {
after_value = *(cit + 1);
}
if (find(ivec1.begin(), ivec1.end(), current_value) != ivec1.end()
&& find(ivec1.begin(), ivec1.end(), before_value) != ivec1.end()
&& find(ivec1.begin(), ivec1.end(), after_value) != ivec1.end()) {
//cout << before_value << "\t" << current_value << "\t" << after_value;
} else {
ivec4.push_back(*cit);
}
}
}
void re_sort_element(const std::vector<int> &ivec3, const std::vector<int> &ivec4,
std::vector<int> &ivec5, std::vector<int> &ivec6)
{
std::vector<int>::const_iterator ivec3_cit1;
std::vector<int>::const_iterator ivec3_cit2;
int flag = 1;
for (vector<int>::const_iterator cit = ivec3.begin(); cit != ivec3.end(); ++cit) {
if ( find(ivec4.begin(), ivec4.end(), *cit) != ivec4.end()) {
if (flag == 1) {
ivec3_cit1 = cit;
flag = 2;
} else {
ivec3_cit2 = cit;
}
} else {
continue;
}
}
if (flag != 2) {
return;
}
for (vector<int>::const_iterator cit = ivec3_cit2; cit != ivec3.end(); ++cit) {
ivec5.push_back(*cit);
}
for (vector<int>::const_iterator cit = ivec3.begin(); cit != ivec3_cit2; ++cit) {
ivec5.push_back(*cit);
}
std::vector<int>::const_iterator ivec4_cit1;
std::vector<int>::const_iterator ivec4_cit2;
flag = 1;
for (vector<int>::const_iterator cit = ivec4.begin(); cit != ivec4.end(); ++cit) {
if ( find(ivec3.begin(), ivec3.end(), *cit) != ivec3.end()) {
if (flag == 1) {
ivec4_cit1 = cit;
flag = 2;
} else {
ivec4_cit2 = cit;
}
} else {
continue;
}
}
if (flag != 2) {
return;
}
for (vector<int>::const_iterator cit = ivec4_cit2; cit != ivec4.end(); ++cit) {
ivec6.push_back(*cit);
}
for (vector<int>::const_iterator cit = ivec4.begin(); cit != ivec4_cit2; ++cit) {
ivec6.push_back(*cit);
}
if (!ivec5.empty() && ! ivec6.empty()) {
if (ivec5.front() == ivec6.front()) {
reverse(ivec6.begin(), ivec6.end());
}
}
}
void join_two_part(const std::vector<int> &ivec5, const std::vector<int> &ivec6,
std::vector<int> &ivec7)
{
for (vector<int>::const_iterator cit = ivec5.begin(); cit != ivec5.end(); ++cit) {
ivec7.push_back(*cit);
}
for (vector<int>::const_iterator cit = ivec6.begin()+1; cit != ivec6.end()-1; ++cit) {
ivec7.push_back(*cit);
}
}
int main()
{
cout << "Hello world Begin!" << endl;
/*
*********************************************
zone1:
1 2 3 4 5
11 12 13 14 15
*********************************************
zone2:
11 12 13 14 15
6 7 8 9 10
*********************************************
zone1+zone2
1 2 3 4 5
11 12 13 14 15
6 7 8 9 10
*********************************************
zone+zone2(finally)
1 2 3 4 5
11 15
6 7 8 9 10
*********************************************
*/
int a1[] = { 1, 2, 3, 4, 5, 15, 14, 13, 12, 11 };
int a2[] = { 15, 14, 13, 12, 11, 6, 7, 8, 9, 10 };
vector<int> ivec1(a1, a1+sizeof(a1)/sizeof(int));
vector<int> ivec2(a2, a2+sizeof(a1)/sizeof(int));
print_vec(ivec1);
print_vec(ivec2);
vector<int> ivec3;
vector<int> ivec4;
delete_repeated_element(ivec1, ivec2, ivec3, ivec4);
print_vec(ivec3);
print_vec(ivec4);
vector<int> ivec5;
vector<int> ivec6;
re_sort_element(ivec3, ivec4, ivec5, ivec6);
print_vec(ivec5);
print_vec(ivec6);
vector<int> ivec7;
join_two_part(ivec5, ivec6, ivec7);
print_vec(ivec7);
cout << "Hello world End!" << endl;
return 0;
}
Hello world Begin!
1 2 3 4 5
15 14 13 12 11
15 14 13 12 11
6 7 8 9 10
1 2 3 4 5
15 11
15 11 6 7 8
9 10
11 1 2 3 4
5 15
15 10 9 8 7
6 11
11 1 2 3 4
5 15 10 9 8
7 6
Hello world End!
Process returned 0 (0x0) execution time : 0.022 s
Press any key to continue.