5

免責事項：これは宿題です。私はそれを試みていますが、誰かが私のためにそれをすることを期待したり、望んでいません。私が間違っているところのほんの少しのポインタ（hehe）をいただければ幸いです。

宿題ではint*、10個の要素を保持する配列を作成してから、それに100万intを挿入しようとする必要があります。挿入するたびに、配列のサイズを変更する必要があるかどうかがチェックされます。サイズを変更する必要がある場合は、サイズを大きくして、もう1つの要素を保持できるようにします。

10,000個の要素を挿入すると正常に機能しますが、100,000個の要素を挿入すると、次のエラーが発生します。

*** glibc detected *** ./set2: realloc(): invalid old size: 0x00000000024dc010 ***

これは私が実行しているコードです。読みやすいようにコメントしました。

void main()
{
    //begin with a size of 10
    int currentsize = 10;
    int* arr = malloc(currentsize * sizeof(int));       
    int i;

    //initalize with all elements set to INT_MAX
    for(i = 0; i < currentsize; i++) {
        arr[i] = INT_MAX;
    }


    // insert random elements
    for(i = 0; i < 100000; i++) {
        currentsize = add(rand() % 100,arr,currentsize);
    }

    free(arr);
}

/*
    Method resizes array if needed, and returns the new size of the array
    Also inserts the element into the array
*/
int add(int x, int* arr, int size)
{
    //find the first available location 
    int newSize = size;
    int i;
    for(i = 0; i < size; i++) {
        if (arr[i] == INT_MAX)
            break;
    }

    if (i >= size) {
        //need to realloc
        newSize++;
        arr = realloc(arr, newSize * sizeof(int) );     
    }

    arr[i] = x;

    return newSize;
}
4

2 に答える 2

5

このエラーは、reallocを適切に使用arrして関数を変更したことが原因である可能性がありますaddが、この変更された値は、がadd戻ったときに失われます。したがって、への次の呼び出しaddは、古い、現在は悪い値を受け取ります。

forまた、なぜループを使用して検索しているのか理解できません。最後の要素に追加したいのに、なぜ検索するのですか？配列を再割り当てし、新しい値を新しいスロットに差し込むだけです。

ちなみに、あなたの先生は、各メンバーの再割り当てが漸近的な実行時の問題を引き起こすことをあなたに見せようとしていると確信しています。のほとんどの実装は、このアルゴリズムを使用しreallocて多くのコピーを実行します。これが、実際のプログラムが配列サイズを固定量ではなく1倍（多くの場合1.5または2）大きくする理由です。

通常のイディオムは、構造体の可変サイズ配列を抽象化することです。

typedef struct array_s {
  int *elts;
  int size;
} VARIABLE_ARRAY;

void init(VARIABLE_ARRAY *a)
{
  a->size = 10;
  a->elts = malloc(a->size * sizeof a->elts[0]);
  // CHECK FOR NULL RETURN FROM malloc() HERE
}

void ensure_size(VARIABLE_ARRAY *a, size_t size) 
{
  if (a->size < size) {

    // RESET size HERE TO INCREASE BY FACTOR OF OLD SIZE
    // size = 2 * a->size;

    a->elts = realloc(size * sizeof a->elts[0]);
    a->size = size;

    // CHECK FOR NULL RETURN FROM realloc() HERE
  }
}

// Set the i'th position of array a. If there wasn't
// enough space, expand the array so there is.
void set(VARIABLE_ARRAY *a, int i, int val)
{
  ensure_size(a, i + 1);
  a->elts[i] = val;
}

void test(void)
{
  VARIABLE_ARRAY a;

  init(&a);

  for (int i = 0; i < 100000; i++) {
    set(&a, i, rand());
  }

  ...

}
于 2012-07-10T03:52:21.963 に答える
1

内部で変更できるように、（ポインターへの）ポインターとしてarr渡しますadd()add()

int add(int x, int** arr, int size)
{
   // ...
   *arr = realloc(*arr, newSize * sizeof(int) );
}

そしてそれを呼び出す....

currentsize = add(rand() % 100, &arr, currentsize);

あなたのコード (および私が提案した変更) はエラー チェックを行っていないことに注意してください。mallocとの戻り値reallocを確認する必要がありますNULL。

于 2012-07-10T03:55:57.060 に答える