c - Valgrind 给我 Invalid write of size 4 Address 0x4037268 is not stack'd, malloc'd or (recently) free'd

Question

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

Answer 1

您的两个函数(即 sort 和 merge)都隐式假设正在排序/合并的区间的右端包含在正在排序的范围内。这是不寻常的:更典型的方法是包含间隔的左侧，但排除右侧。例如，sort 的调用可能如下所示:

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

这不适用于您的实现:它需要如下所示的调用:

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

请检查您调用sort的方式；通过包含右区间应该可以解决问题。