R G B元素数组交换 [英] R G B element array swap
问题描述
我正在尝试创建此c ++程序以执行以下描述.我可以肯定问题在于递归，但不确定如何解决.我猜想它只是不断迭代到无穷大并崩溃.我什至没有输出.我以为我可以比较以前的指针和当前的指针，并根据词典顺序执行一个三段式的临时交换.我将使用指针遍历数组，并在每次交换后将其递减，然后以该ptr作为参数进行递归调用.没有工作，我在这里，请帮我:).如果有一个更简单的解决方案也可以使用，但更希望了解该代码在哪里出了错.
I'm trying to create this c++ program to perform the description below. I am pretty certain the issue is in the recursive, but uncertain how to fix it. I'm guessing it just keeps iterating through to infinity and crashes. I do not even get an output. I figured I could just compare the previous and current pointer and perform a 3-piece temp swap based on lexicography. I would use a pointer to iterate through the array and decrement it after each swap, then recursively call with that ptr as the parameter. Didn't work, I'm here, help me please :). If there is a simpler solution that would work too, but prefer to understand where I went wrong with this code.
#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++;
}
}
推荐答案
您的代码有很多问题.
1)您使用字符指针调用函数RGBorder，然后尝试使用以下方法获取字符数:
1) You call the function RGBorder with a character pointer, and then attempt to get the number of characters using this:
size_t sz = sizeof(c_a)/sizeof(*c_a);
这不会让您获得字符数.相反，这只会使您获得
This will not get you the number of characters. Instead this will simply get you the
sizeof(char *) / sizeof(char)
通常为4或8.使用char数组调用函数的唯一方法是提供一个以空值结尾的数组(因此可以使用strlen)，或者必须在数组作为单独的参数:
which is usually 4 or 8. The only way to call your function using a char array is either provide a null-terminated array (thus you can use strlen), or you have to pass the number of characters in the array as a separate argument:
char *RGBorder(char *c_a, int size)
2)我没有遍历您的代码，但是有更简单的方法可以在数组中进行三向分区.一种流行的算法是基于荷兰国旗问题的算法.
2) I didn't go through your code, but there are easier ways to do a 3-way partition in an array. One popular algorithm to do this is one based on the Dutch National Flag problem.
由于要按RGB顺序排列数组，因此知道G系列将始终位于序列的中间(某处)，其中R位于序列的左侧，而
Since you want the array in RGB order, you know that the series of G will always come in the middle (somewhere) of the sequence, with R on the left of the sequence, and B always on the right of the sequence.
所以目标是简单地将R交换到中间的左侧，将B交换到中间的右侧.因此，基本上，您需要一个循环，在需要时逐渐更改中间"，同时在检测到R和B时将它们交换到适当的位置.
So the goal is to simply swap R to the left of the middle, and B to the right of the middle. So basically you want a loop that incrementally changes the "middle" when needed, while swapping R's and B's to their appropriate position when they're detected.
以下代码对此进行了说明:
The following code illustrates this:
#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;
}
这是另一个使用 std :: partition 的解决方案.
Here is another solution that uses 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;
}
基本上，第一次调用std::partition会将R放置在数组的前面.由于std::partition将迭代器(在本例中为char *)返回到发生分区的末尾，因此我们将其用作第二次调用std::partition的开始位置，在此我们将G值分区
Basically, the first call to std::partition places the R's to the front of the array. Since std::partition returns an iterator (in this case, a char *) to the end of where the partition occurs, we use that as a starting position in the second call to std::partition, where we partition the G values.
请注意，std::partition也通过交换来实现其目标.
Note that std::partition also accomplishes its goal by swapping.
鉴于此解决方案，我们可以使用循环将其推广到n路分区.假设我们要按RGBA顺序放置东西(4个值而不是3个值).
Given this solution, we can generalize this for an n-way partition by using a loop. Assume we want to place things in RGBA order (4 values instead of 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
这篇关于R G B元素数组交换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
