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

抱歉直截了当地说，但那段代码一团糟。我不是说错误，对于初学者来说，这些错误是可以原谅的。我的意思是格式化。一行中的多个语句使得阅读和调试代码变得非常困难。没有直接内在含义的短变量名让人很难理解代码应该做什么。 using namespace std; 也是非常糟糕的做法，但我可以想象你是被教授这门课程的人教的。

第一题

你的 case 没有 break，因此你执行 R 的所有情况，G 和 default 都执行 [=14] =].此外，您的代码永远不会到达循环的最后两行，因为您之前 continue 在每种情况下都已退出。

第二题

你有一个无限循环。在这两个 case 中，您有两种情况会陷入无限循环：

在 else if( *prv_ptr == *ptr_ca ) 分支中，您只需 continue; 而不更改指针。
在 else 分支中执行 ptr_ca--;，但随后在 default 中再次调用 ptr_ca++;。
（注意即使使用 breaks 你仍然会在循环结束时调用 ptr_ca++;。）

在这两种情况下，指针都不会改变，因此一旦您遇到任何这些情况，您的循环将永远不会退出。

可能是第三题

我只能猜测，因为从名称上看并不明显，但似乎 prv_ptr 应该保存循环中的最后一个指针？如果是这样，那么您永远不更新该指针似乎是错误的。无论哪种方式，正确的变量名称都会使该指针的确切用途更加清楚。（附带说明，一致使用 const 可以帮助识别此类问题。如果您有一个不是 const 的变量，但从未更新过，您要么忘记添加 const 要么忘记更新了。）

如何修复

格式化您的代码：

不要使用 using namespace std;。
每行一条语句。
为您的变量命名，以便轻松识别什么是什么。（这不是 1993 年，真的，我宁愿 thisIsThePointerHoldingTheCharacterThatDoesTheThing 而不是 ptr_xy。）

修复上述问题（添加 breaks，确保你的循环确实退出）。

然后调试你的代码。用调试器。虽然它运行。使用断点并逐行单步执行，在代码执行时检查指针的值。花哨的东西。

祝你好运！

Answer 2

你的代码有很多问题。

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 交换到中间的右侧。所以基本上你想要一个循环，在需要时逐渐改变 "middle"，同时在检测到 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 returns 迭代器（在本例中为 char *）到分区发生位置的末尾，我们将其用作第二次调用 [=25= 的起始位置]，我们在其中划分 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

Answer 3

只需计算 'R'、'G' 和 'B' 字母的数量，然后从头开始填充数组。更容易，没有递归。

R G B元素数组交换

R G B element array swap

c++

arrays

compare-and-swap