0 
void merge(int left, int mid, int right)
{
  // sublist sizes
  int left_size = mid - left + 1;
  int right_size = right - mid;

  // counts
  int i, j, k;

  // create left and right arrays
  B left_list = malloc(left_size*sizeof(B));
  B right_list = malloc(right_size*sizeof(B));

  for (i = 0; i < left_size; i++)
    left_list[i] = list[left + i];

  for (j = 0; j < right_size; j++)
    right_list[j] = list[mid + j + 1];

  // reset counts
  i = 0; j = 0;

  for (k = left; k <= right; k++)
  {
    if (j == right_size)
      list[k] = left_list[i++];
    else if (i == left_size)
      list[k] = right_list[j++];
    // here we call the given comparision function
    else if (compar(&left_list[i], &right_list[j]) < 0)
      list[k] = left_list[i++];
    else
      list[k] = right_list[j++];
  }
}

void sort(int left, int right)
{
  if (left < right)
  {
    // find the pivot point
    int mid = (left + right) / 2;

    // recursive step
    sort(left, mid, compar);
    sort(mid + 1, right, compar);

    // merge resulting sublists
    merge(left, mid, right, compar);
  }
}

valgrind でプログラムをテストしようとしたところ、以下のようになりました。

==8679== Invalid write of size 4
==8679==    at 0x8048A30: merge (program.c:96)
==8679==    by 0x8048BF5: sort (program.c:116)
==8679==    by 0x8048C21: user_interface (program.c:124)
==8679==    by 0x8048E99: main (program.c:175)
==8679==  Address 0x4037268 is not stack'd, malloc'd or (recently) free'd
4

1 に答える 1

1

両方の関数 (sortとmerge、つまり) は、並べ替え/マージされる間隔の右端が並べ替えられる範囲に含まれているという暗黙の前提を作成します。これは珍しいことです。より一般的なアプローチは、間隔の左側を含め、右側を除外することです。たとえば、 の呼び出しは次のsortようになります。

#define MAX 100
...
int list[MAX];
...
void sort(0, MAX, myComparator);

これは実装では機能しません。次のような呼び出しが必要です。

void sort(0, MAX-1 /* <<== Here */, myComparator);

呼び方を確認してくださいsort。包括的な正しい間隔を渡すと、問題が解決するはずです。

于 2012-11-19T02:24:06.270 に答える