c++ - R G B元素数组交换

Question

我正在尝试创建这个 C++ 程序来执行下面的描述。我很确定问题出在递归中，但不确定如何解决。我猜它只是不断迭代到无穷大和崩溃。我什至没有得到输出。我想我可以只比较以前和当前的指针，并根据词典编排执行 3 件式临时交换。我会使用一个指针来遍历数组并在每次交换后递减它，然后以该 ptr 作为参数递归调用。没用，我在这里，请帮助我 :)。如果有一个更简单的解决方案也可以工作，但更愿意了解我在这段代码中出错的地方。

#include <string>
#include <iostream>
using namespace std;

// Given an array of strictly the characters 'R', 'G', and
// 'B', segregate the values of the array so that all the
// Rs come first, the Gs come second, and the Bs come last.
// You can only swap elements of the array.

char* RGBorder(char* c_a)
{

    size_t sz = sizeof(c_a)/sizeof(*c_a);
    char* ptr_ca = c_a;
    char* prv_ptr = ptr_ca;
    ptr_ca++;
    char temp;

    while(*ptr_ca)
    {
        switch(*ptr_ca)
        {
            case 'R' :
                if( *prv_ptr < *ptr_ca ) {
                    temp = *prv_ptr; *prv_ptr = *ptr_ca; *ptr_ca = temp;
                } else if( *prv_ptr == *ptr_ca ) {
                    continue;
                } else { ptr_ca--; RGBorder(ptr_ca); }

            case 'G' :
                if( *prv_ptr < *ptr_ca ) {
                    temp = *prv_ptr; *prv_ptr = *ptr_ca; *ptr_ca = temp;
                } else if( *prv_ptr == *ptr_ca ) {
                    continue;
                } else { ptr_ca--; RGBorder(ptr_ca); }
            default:
                ptr_ca++;
                continue;
        }
        ptr_ca++;
        cout << *ptr_ca;
    }

    return c_a;
}

int main()
{
    char ca[] =  {'G', 'B', 'R', 'R', 'B', 'R', 'G'};
    char *oca =RGBorder(ca);
    char *pca = oca;
    while(*pca)
    {
        cout << *pca << endl;
        pca++;
    }
}

Answer 1

您的代码有很多问题。

1) 您使用字符指针调用函数 RGBorder，然后尝试使用此方法获取字符数:

size_t sz = sizeof(c_a)/sizeof(*c_a);

这不会得到字符数。相反，这只会让你

sizeof(char *) / sizeof(char)

通常是 4 或 8。使用 char 数组调用函数的唯一方法是提供一个以 null 结尾的数组(因此您可以使用 strlen)，或者您必须传递数组中的字符数作为单独的参数:

char *RGBorder(char *c_a, int size)

---

2) 我没有仔细阅读您的代码，但有更简单的方法可以在数组中进行三向分区。一种流行的算法是基于 Dutch National Flag 的算法。问题。

由于您希望数组按 RGB 顺序排列，您知道 G 系列将始终位于序列的中间(某处)， R 在序列的左边，B 总是在序列的右边。

所以目标是简单地将 R 交换到中间的左侧，将 B 交换到中间的右侧。所以基本上你想要一个循环，在需要时逐渐改变“中间”，同时在检测到 R 和 B 时将它们交换到适当的位置。

下面的代码说明了这一点:

#include <algorithm>

char *RGBorder(char *c_a, int num)
{
    int middle = 0;  // assume we only want the middle element
    int low = 0;     // before the G's
    int high = num - 1;  // after the G's

    while (middle <= high)
    {
        if ( c_a[middle] == 'R' )  // if we see an 'R' in the middle, it needs to go before the middle
        {
            std::swap(c_a[middle], c_a[low]);  // swap it to a place before middle
            ++middle;  // middle has creeped up one spot
            ++low;     // so has the point where we will swap when we do this again
        }
        else
        if (c_a[middle] == 'B')  // if we see a 'B' as the middle element, it needs to go after the middle
        {
            std::swap(c_a[middle], c_a[high]); // place it as far back as you can
            --high;  // decrease the back position for next swap that comes here
        }
        else
           ++middle;  // it is a 'G', do nothing
    }
    return c_a;
}

Live Example

---

这是另一个使用 std::partition 的解决方案.

#include <algorithm>
#include <iostream>

char *RGBorder(char *c_a, int num)
{
    auto iter = std::partition(c_a, c_a + num, [](char ch) {return ch == 'R';});
    std::partition(iter, c_a + num, [](char ch) {return ch == 'G';});
    return c_a;
}

Live Example

基本上，第一次调用 std::partition 会将 R 放在数组的前面。由于 std::partition 将迭代器(在本例中为 char *)返回到分区发生位置的末尾，因此我们将其用作第二个中的起始位置调用 std::partition，在这里我们划分 G 值。

请注意，std::partition 也通过交换来实现其目标。

---

鉴于此解决方案，我们可以通过使用循环将其概括为 n 路分区。假设我们想要按 RGBA 顺序放置事物(4 个值而不是 3 个)。

#include <algorithm>
#include <iostream>
#include <cstring>

char *RGBorder(char *c_a, int num, char *order, int num2)
{
    auto iter = c_a;
    for (int i = 0; i < num2 - 1; ++i)
        iter = std::partition(iter, c_a + num, [&](char ch) {return ch == order[i];});
    return c_a;
}


int main()
{
    char ca[] = "AGBRRBARGGARRBGAGRARAA";
    std::cout << RGBorder(ca, strlen(ca), "RGBA", 4);
}

输出:

RRRRRRRGGGGGBBBAAAAAAA