在数组中复制相同的以下元素

Question

我应该构建一个获取数组及其大小和 return 指针的函数到新数组（我需要使用 malloc 和 realloc 创建新数组）找到相同的数字并在行中复制它们例如数组：{1,8,8,70,2,2,2,5,5,2} 和大小 10 假设 return 指向该数组的指针 {1,8,8,8,8,70,2,2,2,2,2,2,5,5,5,5,2}。知道我的代码有什么问题吗？？

int * duplicateArray(int* arr, int n)

{
    int g = 1;
    int i,j=0;
    int *p = (int*)(calloc)(n, sizeof(int));
    assert(p);
    for (i = 0; i < n-1; i++)
    {
        if (arr[i] == arr[i + 1])
        {
             p= (int*)(realloc)(p, n+g * sizeof(int));
             n=n+g;
             assert(p);
             p[j] = arr[i];
             j++;
             p[j] = arr[i+1];
        }
        else
            p[j] = arr[i];
        j++;
    }
   return p;
}

Answer 1

您在不断重新分配内存时使用的方法效率低下。

此外，该函数应该 return 不仅是指向动态分配数组的指针，还应该是分配数组中元素的数量。否则函数的用户将不知道分配的数组中有多少元素。为整数动态分配数组使用标记值不是一个好主意。

我建议将任务分成两个独立的任务，分别对应两个独立的功能..

第一个函数将计算给定数组中重复元素的数量。

第二个函数将根据第一个函数的 returned 值动态创建一个指定大小的数组，并将源数组的元素复制到新创建的数组中。

这是一个演示程序

#include <stdio.h>
#include <stdlib.h>

size_t countRepeated( const int a[], size_t n )
{
    size_t repeated = 0;

    for ( size_t i = 0; i != n;  )
    {
        size_t m = 1;

        while ( ++i != n && a[i] == a[i-1] ) ++m;

        if ( m != 1 ) repeated += m;
    }

    return repeated;
}

int * copyWithDuplication( const int a[], size_t n, size_t m )
{
    int *result = m == 0 ? NULL : calloc( m, sizeof( int ) );

    if ( result )
    {
        for ( size_t i = 0, j = 0; j != m && i != n;  )
        {
            result[j++] = a[i++];

            size_t k = 1;

            while ( j != m && i != n && a[i] == a[i-1] )
            {
                result[j++] = a[i++];
                ++k;
            }                   

            if ( k != 1 )
            {
                while ( j != m && k-- ) result[j++] = a[i-1];
            }
        }
    }

    return result;
}

int main(void) 
{
    int a[] = { 1, 8, 8, 70, 2, 2, 2, 5, 5, 2 };
    const size_t N = sizeof( a ) / sizeof( *a );

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );

    size_t m = N + countRepeated( a, N );

    int *b = copyWithDuplication( a, N, m );

    if ( b )
    {
        for ( size_t i = 0; i < m; i++ )
        {
            printf( "%d ", b[i] );
        }
        putchar( '\n' );
    }

    free( b );

    return 0;
}

程序输出为

1 8 8 70 2 2 2 5 5 2 
1 8 8 8 8 70 2 2 2 2 2 2 5 5 5 5 2

还有一个更有趣的演示程序。

#include <stdio.h>
#include <stdlib.h>

size_t countRepeated( const int a[], size_t n )
{
    size_t repeated = 0;

    for ( size_t i = 0; i != n;  )
    {
        size_t m = 1;

        while ( ++i != n && a[i] == a[i-1] ) ++m;

        if ( m != 1 ) repeated += m;
    }

    return repeated;
}

int * copyWithDuplication( const int a[], size_t n, size_t m )
{
    int *result = m == 0 ? NULL : calloc( m, sizeof( int ) );

    if ( result )
    {
        for ( size_t i = 0, j = 0; j != m && i != n;  )
        {
            result[j++] = a[i++];

            size_t k = 1;

            while ( j != m && i != n && a[i] == a[i-1] )
            {
                result[j++] = a[i++];
                ++k;
            }                   

            if ( k != 1 )
            {
                while ( j != m && k-- ) result[j++] = a[i-1];
            }
        }
    }

    return result;
}

int main(void) 
{
    int a[] = { 1, 8, 8, 70, 2, 2, 2, 5, 5, 2 };
    const size_t N = sizeof( a ) / sizeof( *a );

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );

    size_t m = N + countRepeated( a, N );

    for ( size_t i = 0; i < m; i++ )
    {
        int *b = copyWithDuplication( a, N, i + 1 );

        if ( b )
        {
            for ( size_t j = 0; j < i + 1; j++ )
            {
                printf( "%d ", b[j] );
            }
            putchar( '\n' );
        }

        free( b );
    }

    return 0;
}

它的输出是

1 8 8 70 2 2 2 5 5 2 
1 
1 8 
1 8 8 
1 8 8 8 
1 8 8 8 8 
1 8 8 8 8 70 
1 8 8 8 8 70 2 
1 8 8 8 8 70 2 2 
1 8 8 8 8 70 2 2 2 
1 8 8 8 8 70 2 2 2 2 
1 8 8 8 8 70 2 2 2 2 2 
1 8 8 8 8 70 2 2 2 2 2 2 
1 8 8 8 8 70 2 2 2 2 2 2 5 
1 8 8 8 8 70 2 2 2 2 2 2 5 5 
1 8 8 8 8 70 2 2 2 2 2 2 5 5 5 
1 8 8 8 8 70 2 2 2 2 2 2 5 5 5 5 
1 8 8 8 8 70 2 2 2 2 2 2 5 5 5 5 2

Answer 2

Any clue what's wrong with my code??

如果参数 n 是 1，那么您的程序将为类型 int 的 1 元素分配一个数组，但不会向其中写入任何内容。它不会从输入缓冲区复制任何内容。

您正在越界访问输入 arr 和输出数组 p，这会导致 undefined behavior。循环

for (i = 0; i < n-1; i++)

不会从 0 计数到函数参数 n 减去 2，因为 n 在循环内递增。这会导致您的循环具有比预期更多的迭代次数，从而导致输入和输出数组都被越界访问。

此外，您的变量 g 似乎没有什么意义，因为它永远不会改变并且始终具有值 1.

function prototype

int * duplicateArray(int* arr, int n);

似乎没有意义，因为调用函数无法知道返回数组的大小。如果你使用函数原型

void duplicateArray ( const int *p_input_array, int num_input, int **pp_output_array, int *p_num_output );

相反，函数duplicateArray可以将新数组的地址写入*pp_output_array，并将数组中元素的数量写入*p_num_output。这样，调用函数将能够有效地接收两个 "return values" 而不是一个

这是我对函数 duplicateArray 和调用函数的实现：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

void duplicateArray( const int *p_input_array, int num_input, int **pp_output_array, int *p_num_output )
{
    int i = 0, j = 0;

    // In the most extreme case, the output array must be 2 times larger than
    // the input buffer, so we allocate double the size of the input buffer.
    int *p_output_array = (int*)malloc( num_input * 2 * sizeof(int) );
    assert( p_output_array != NULL );

    while ( i < num_input )
    {
        int num_repetitions;

        int k = p_input_array[i++];

        //count the number of repetitions
        for ( num_repetitions = 0; i < num_input && p_input_array[i] == k; num_repetitions++, i++ );

        if ( num_repetitions == 0 )
        {
            p_output_array[j++] = k;
        }
        else
        {
            for ( int l = 0; l < num_repetitions + 1; l++ )
            {
                p_output_array[j++] = k;
                p_output_array[j++] = k;
            }
        }
    }

    //shrink the array to the actually needed size
    p_output_array = (int*)realloc( p_output_array, j * sizeof(int) );
    assert( p_output_array != NULL );

    *pp_output_array = p_output_array;
    *p_num_output = j;
}

int main()
{
    int arr[] = { 1, 8, 8, 70, 2, 2, 2, 5, 5, 2 };
    int *p;
    int num;

    duplicateArray( arr, sizeof(arr)/sizeof(*arr), &p, &num );

    for ( int i = 0; i < num; i++ ) {
        printf( "%d\n", p[i] );
    }

    free( p );
}

在数组中复制相同的以下元素

duplicate same following elements in array

c

arrays

realloc

function-definition