c++ - 使用指针合并两个排序数组的问题

Question

我正在尝试使用指针合并两个已排序的数组。第三个循环将食物工作到第一个 arr[5]，但随后显示垃圾值。是排序技术错误还是我错误地使用了指针？

#include<iostream>
using namespace std;


int main() {
    int arr1[] = { 1,3,4,6 };
    int arr2[] = { 2,3,4,5 };
    int n1 = 4;
    int n2 = 4;
    int arr3[10];
    int* endptr = &arr1[0];
    int* endptr2 = &arr2[0];
    int* endptr3 = arr3;
    int k = 0;

   
    while (endptr < &arr1[n1-1] &&endptr2  < &arr2[n2-1]) {
        if (endptr[0] < endptr2[0]) {
            endptr3[k++] = endptr[0];
            endptr++;
        }
            
        else {
            endptr3[k++] = endptr2[0];
            endptr2++;
        }
    }
    while (endptr < &arr1[n1 - 1]) {
        endptr3[k++] = endptr[0];
        endptr++;
    }

    while (endptr2 < &arr2[n2 - 1]) {
        endptr3[k++] = endptr[0];
        endptr2++;
    }
    cout << arr3[5];
}

我得到了前 6 个元素的结果，然后得到了垃圾值。

Answer 1

您使用指针的方式会对您的思维过程产生负面影响。

让我们将其抽象为一个函数以帮助使其更清晰:

void merge(
  int * first1, int * last1,  // elements of array1
  int * first2, int * last2,  // elements of array2
  int * dest )                // where to put sorted data

这是 C++ 算法使用的“迭代器”习惯用法。 first指向第一个元素。 last指向最后一个元素过去。 (我们假设 dest 指向足够的空间来包含结果。)所以:

int array1[] = { 1,3,4,6 };
int array2[] = { 2,3,4,5,7 };
int array3[9];  // enough room for array1+array2

merge( 
  array1, array1+4,  // first array has 4 elements
  array2, array2+5,  // second array has 5 elements
  array3 );          // destination array has 4+5=9 elements

C++ 实际上为我们提供了几个函数来获取指向您所拥有的任何底层序列容器的第一个和最后一个指针:

merge(
  std::begin(array1), std::end(array1),
  std::begin(array2), std::end(array2),
  std::begin(array3) );

现在我们可以重新考虑我们的合并算法。

void merge(...)
{
  // while both array1 and array2 have elements:
  while ((first1 != last1) and (first2 != last2))
  {
    if (*first2 < *first1)
      *dest++ = *first2++;
    else
      *dest++ = *first1++;
  }

  // if array1 has any leftover elements:
  while (first1 != last1)
    *dest++ = *first1++;

  // if array2 has any leftover elements:
  while (first2 != last2)
    *dest++ = *first2++;
}

特别注意:

• 我们可以通过比较first来轻松检查数组是否有元素。和last直接指点。当first == last ，没有元素，因为 last是源数组末尾的一位。
• 比较很简单。我们可以将其写为 if (first2[0] < first1[0])但这比仅使用 * 不太惯用。运算符。
• 复制值就像取消引用并在赋值两侧递增一样简单。
• 合并的三个循环都针对一个简单的“还剩下元素吗？”进行工作。检查一下。

还要注意我们如何将测试条件保持为严格的小于比较。这对泛型编程有影响(例如，以非递增顺序进行合并排序)，但今天我就先这样......