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 回答