3

我已经有几年没有上过任何编程课程了，所以请原谅任何初学者的错误/做某事的方法。我喜欢对未来的建议。使用下面的代码，我试图检查两个数组的值（已经排序）并将它们放入一个组合数组中。我的解决方案，无论多么低效/草率，是使用 for 循环来比较每个数组在 j 处的索引的内容，然后将较低的值分配给 combineArray 的索引 i，将较高的值分配给索引 i+1。我将 i 增加 2 以避免覆盖前一个循环的索引。

int sortedArray1 [5] = {11, 33, 55, 77, 99};
int sortedArray2 [5] = {22, 44, 66, 88, 00};
combinedSize = 10;
int *combinedArray;
combinedArray = new int[combinedSize];
    for(int i = 0; i <= combinedSize; i+=2)
{
    for(int j = 0; j <= 5; j++)
    {
        if(sortedArray1[j] < sortedArray2[j])
        {
            combinedArray[i] = sortedArray1[j];
            combinedArray[i+1] = sortedArray2[j];
        }
        else if(sortedArray1[j] > sortedArray2[j])
        {
            combinedArray[i] = sortedArray2[j];
            combinedArray[i+1] = sortedArray1[j];
        }
        else if(sortedArray1[j] = sortedArray2[j])
        {
            combinedArray[i] = sortedArray1[j];
            combinedArray[i+1] = sortedArray2[j];
        }
    }
}

for(int i = 0; i < combinedSize; i++)
{
    cout << combinedArray[i];
    cout << " ";
}

我的结果是这样的

Sorted Array 1 contents: 11 33 55 77 99
Sorted Array 2 contents: 0 22 44 66 88
5 77 5 77 5 77 5 77 5 77 Press any key to continue . . .

在我缺乏经验的头脑中，排序的实现看起来不错，所以我不确定为什么我会得到这个糟糕的输出。建议会很棒。

4

6 回答 6

3

那这个呢：

int i=0,j=0,k=0;
while(i<5 && j<5)
     {
        if(sortedArray1[i] < sortedArray2[j])
         {
           combinedArray[k]=sortedArray1[i];
            i++;
          }
       else
         {
           combinedArray[k]=sortedArray2[j];
           j++;
          }
      k++;
     }
   while(i<5)
     {
           combinedArray[k]=sortedArray1[i];
           i++;k++;
          }
   while(j<5)
     {
           combinedArray[k]=sortedArray2[j];
           j++;  k++;

          }
于 2012-09-23T04:10:54.590 回答
3

首先，在如何使用 C++ 方面存在一些直接的问题：

  • 您使用=而不是==进行相等性检查（因此导致不希望的值分配和 if 条件在不应该返回 true 时返回）；
  • 您的外循环上边界定义为i <= 10，而正确的边界检查将是i < 10;
  • 在函数结束时出现内存泄漏，因为您未能取消分配内存。最后你需要一个delete [] combinedArray。

其次，您的外循环遍历目标数组的所有值，并且在每个步骤中使用一个内循环遍历源数组的所有值。那不是你想要的。你想要的是一个循环j=0，从源数组开始计数j<5并遍历源数组。然后将目标数组中的位置确定为2*j和2*j+1，并且不需要内部循环。

第三，正如评论中所解释的，排序列表合并的正确实现需要两个独立的计数器j1和j2. 但是，您当前的输入是硬连线到代码中的，如果您替换00为100，您当前的算法（在进行上述更正之后）实际上将适用于给定的输入。

最后，但不太重要的是，我想知道为什么您的目标数组使用new. 只要您处理的是小数组，您就可以像源数组一样在堆栈上分配它。但是，如果您在堆上分配它，最好使用 a std::unique_ptr<>，可能与std::array<>. 然后，您将免费获得取消分配，而不必考虑delete []在函数末尾添加语句。

于 2012-09-23T04:26:58.660 回答
1

甚至在查看实现之前，检查算法并用笔和纸写下来。弹出的第一件事是您假设结果中的前两个元素将来自每个源数组。不一定是这种情况，考虑两个数组，其中一个中的所有元素都小于另一个中的所有元素以及预期的结果：

int a[] = { 1, 2, 3 };
int b[] = { 4, 5, 6 };

如果要对结果进行排序，则前三个元素都来自第一个数组。考虑到这一点，想想你对数据的真正了解。特别是，两个数组都已排序，这意味着第一个元素将小于相应数组中的其余元素。这意味着较小的元素是较小的头部。通过将该元素放入结果中，您可以将问题减少到更小的集合。你有a' = { 2, 3 },b = { 4, 5, 6 }和res = { 1 }一个新的问题是找到res知道a'和b排序的第二个元素。

在纸上弄清楚您需要做什么，然后将其映射到代码应该是直截了当的。

于 2012-09-23T04:29:13.290 回答
1

因此，我修改了您的代码以使其正常工作。实际上，为两个排序数组设置两个指针/索引是个好主意。这样您就可以在将相应的指针添加到您的 combineArray 后更新它。如果您不理解此代码的任何部分，请告诉我。谢谢。

    int sortedArray1 [5] = {11, 33, 55, 77, 99};
    int sortedArray2 [5] = {0, 22, 44, 66, 88}; 
    int combinedSize = 10;
    int *combinedArray;
    combinedArray = new int[combinedSize];
    int j = 0;
    int k = 0;
    for(int i = 0; i < combinedSize; i++)
    {
            if (j < 5 && k < 5) {
                    if (sortedArray1[j] < sortedArray2[k]) {
                            combinedArray[i] = sortedArray1[j];
                            j++;
                    } else {                  
                            combinedArray[i] = sortedArray2[k];
                            k++;
                    }                         
            } 
            else if (j < 5) {
                    combinedArray[i] = sortedArray1[j];
                    j++;
            }                         
            else {
                    combinedArray[i] = sortedArray2[k];
                    k++;
            }                         
    }

    for(int i = 0; i < combinedSize; i++)
    {
        cout << combinedArray[i];
        cout << " ";
    }
    cout<<endl;
于 2012-09-23T07:30:56.890 回答
0

的else if(sortedArray1[j] = sortedArray2[j])，你的意思是else if(sortedArray1[j] == sortedArray2[j])？

前一个会将 sortedArray2[j] 的值分配给 sortedArray1[j] - 这就是你得到的原因5 77 5 77...

但是5从哪里来？两者都没有5 sortedArray，但我发现for(int j = 0; j <= 5; j++)一定有问题。大小N数组的最高索引N-1不是N在 C/C++ 中（但不是在 Basic 中）.. 所以j<5用作条件，否则您可能会遇到一些难以解释或预测的情况..

毕竟，您的算法本身存在问题，每次外循环循环时，它都会最后比较两个数组中的最后一个元素，这使得输出重复两个数字。

因此，您还需要更正您的算法，请参阅合并排序。

于 2012-09-23T04:08:17.340 回答
0

稍微不同的方法，恕我直言，它更干净：

//A is the first array, m its length
//B is the second array, n its length
printSortedAndMerged(int A[], int m, int B[], int n){
    int c[n+m];
    int i=0, j=0;

    for(int k=0; k < n+m; k++){

        if(i < m && j < n){
            if(A[i] < B[j]){
                c[k] = A[i];
                i++;
            }
            else{
                c[k] = B[j];
                j++;
            }
            continue; //jump to next iteration
        }

        if(i < m){ // && ~(j < n)
        //we already completely traversed B[]
            c[k] = A[i];
            i++;
            continue;
        }

        if(j < n){ // %% ~(i < m)
        //we already completely traversed A[]
            c[k] = B[j];
            j++;
            continue;
        }

        //we should never reach this
        cout << "Wow, something wrong happened!" << endl;
}//for

for(int i=0; i<n+m; i++){
    cout << c[i] << endl;
}
}

希望能帮助到你。

于 2015-04-07T21:18:09.533 回答