C 数组合并算法产生不正确的结果：FirstArray 合并问题

Question

在 C 中合并两个数组而不创建新变量

我正在解决一个 C 编程挑战，我需要合并两个数组，而不创建一个新变量来存储合并的数组。相反，我想扩展一个已经提供的数组并将所有值放入其中。

这是我的代码：

#include <stdio.h>

void printArray(int array[], int size){

        for(int i=0; i<size; i++){
            printf("%d, ", array[i]);
        }

        printf("\n");
}

void mergeArray(int *firstArray, int secondArray[], int firstSize, int secondSize){

    int firstIndex = firstSize -1;
    int secondIndex = secondSize -1;
    int mergeSize = firstSize + secondSize;
    int mergeIndex = mergeSize -1;

    while (firstIndex >=0 && secondIndex >=0){

        if(firstArray[firstIndex] > secondArray[secondIndex]){
            firstArray[mergeIndex] = firstArray[firstIndex];
            firstIndex--;
        } else if(firstArray[firstIndex] < secondArray[secondIndex]) {
            firstArray[mergeIndex] = secondArray[secondIndex];
            secondIndex--;
        } else {
            firstIndex--;
            secondIndex--;
        }

            mergeIndex--;       
    }

}

int main(){
    int firstArray[] = {1, 5, 7, 9, 10};
    int secondArray[] = {2, 4, 6, 8, 12};

    int firstSize = sizeof(firstArray) / sizeof(firstArray[0]);
    int secondSize = sizeof(secondArray) / sizeof(secondArray[0]);
    int mergeSize = firstSize + secondSize;

    printArray(firstArray, firstSize);
    printArray(secondArray, secondSize);

    mergeArray(firstArray, secondArray, firstSize, secondSize);
    printArray(firstArray, mergeSize);
    
    return 0;
}

期望的输出为：1,2,4,5,6,7,8,9,10,12 我得到的实际输出是：1,5,10,12,6,7,8,9,10,12

我尝试对其进行调试，但无法确定问题所在。似乎代码中的某个地方， SecondArray 中的值正在意外更改。谁能帮我找出问题所在吗？ 抱歉，如果我的英语不好，这不是我的母语

Answer 1

相反，我想扩展已经提供的数组

这在 C 中是不可能的。数组具有固定大小，如使用初始化程序显式或隐式定义中给出的那样。所以你当前的代码无法工作，因为它写出界限。

您可以使用

malloc

分配动态内存。它可以像数组一样使用。您可以使用

realloc

调整大小。

除了你的合并算法有问题。

1. 如果要合并的数组包含相同的值，则代码将忽略该值。

2. 一旦

   firstIndex

   和

   secondIndex

   之一变为负值，循环就会停止。因此，代码永远不会将“另一个”数组的其余部分复制到目标。

Answer 2

首先，关于函数

mergeArray

本身。

指定数组大小的参数应具有无符号类型

size_t

而不是有符号类型

int

。

由于第二个数组在函数内未更改，因此应使用限定符

const

进行声明。

此外，指定数组大小的参数应遵循相应的数组声明。

函数声明应该是这样的

void mergeArray( int firstArray[], size_t firstSize, const int secondArray[], size_t secondSize );

这些 if 语句

    if(firstArray[firstIndex] > secondArray[secondIndex]){
        firstArray[mergeIndex] = firstArray[firstIndex];
        firstIndex--;
    } else if(firstArray[firstIndex] < secondArray[secondIndex]) {
        firstArray[mergeIndex] = secondArray[secondIndex];
        secondIndex--;
    } else {
        firstIndex--;
        secondIndex--;
    }

错了。例如，如果两个数组的元素彼此相等，则两个元素都不会存储在

mergeIndex

的当前索引值中。

第二个数组中的元素数量也可以大于第一个数组中的元素数量。在这种情况下，您需要将第二个数组的剩余元素复制到第一个数组中的相应位置。

其次，数组定义后不能再扩大。您的数组

firstArray

没有足够的元素来容纳数组

secondArray

的元素值。

您首先需要声明足够大的数组

firstArray

，或者使用能够存储两个数组的元素的第三个数组。

这是一个演示程序。带有更新的函数

mergeArray

#include <stdio.h>
#include <string.h>

void printArray( const int array[], size_t size ) 
{

    while ( size-- )
    {
        printf( "%d, ", *array++ );
    }

    putchar( '\n' );
}

void mergeArray( int firstArray[], size_t firstSize, const int secondArray[], size_t secondSize ) {

    size_t mergeSize = firstSize + secondSize;

    while ( firstSize && secondSize )
    {
        if (secondArray[secondSize - 1] < firstArray[firstSize - 1] )
        {
            firstArray[--mergeSize] = firstArray[--firstSize];
        }
        else 
        {
            firstArray[--mergeSize] = secondArray[--secondSize];
        }
    }

    while ( secondSize )
    {
        firstArray[--mergeSize] = secondArray[--secondSize];
    }
}

int main( void )
{
    int firstArray[] = { 1, 5, 7, 9, 10 };
    int secondArray[] = { 2, 4, 6, 8, 12 };
    int mergedArray[sizeof( firstArray ) / sizeof( firstArray[0] ) +
        sizeof( secondArray ) / sizeof( secondArray[0] )];

    size_t firstSize = sizeof( firstArray ) / sizeof( firstArray[0] );
    size_t secondSize = sizeof( secondArray ) / sizeof( secondArray[0] );
    size_t mergeSize = firstSize + secondSize;

    printArray( firstArray, firstSize );
    printArray( secondArray, secondSize );

    memcpy( mergedArray, firstArray, firstSize * sizeof( int ) );

    mergeArray( mergedArray, firstSize, secondArray, secondSize );

    printArray( mergedArray, mergeSize );
}

程序输出为

1  5  7  9  10
2  4  6  8  12
1  2  4  5  6  7  8  9  10  12