C语言 指向结构的指针数组的合并排序

mdfafbf1  于 2022-12-03  发布在  其他
关注(0)|答案(1)|浏览(182)

我正在尝试为包含指向不同结构体的指针的数组编写一个通用的合并排序。我正在编写一个编译器不会给予任何错误的代码,但是排序函数还没有给出正确的输出。两个结构体和两个比较函数的定义如下:

typedef struct Query {int day, rank;} Query;  

typedef struct Event {int day, frame; char action;} Event;

int compEvents (const void *a, const void *b) {
  return (*(Event**)a)->day - (*(Event**)b)->day;
}

int compQueries (const void *a, const void *b) {
  return (*(Query**)a)->day - (*(Query**)b)->day;
}

如果我使用qsort,一切都正常,输出也是正确的:

qsort (queries, size, sizeof(Query*), compQueries);

如果我对每种类型使用不同的合并排序,并且不使用比较函数,那么一切都可以正常工作:

void queryMerge(Query **arr, int left, int mid, int right) {
  Query **temp = newQueryArray(right-left+1);
  int i = left, j = mid + 1, t = 0;   
  while (i <= mid && j <= right) {
    if (arr[i]->day < arr[j]->day) temp[t++] = arr[i++];
    else temp[t++] = arr[j++];
  }
  while (i <= mid) temp[t++] = arr[i++];
  while (j <= right) temp[t++] = arr[j++];
  for (int i = left; i <= right; i++) arr[i] = temp[i-left];
  free(temp);
}

void querySort(Query **arr, int left, int right) { 
  if (left < right) {
    int mid = left + (right - left)/2;
    querySort(arr, left, mid);
    querySort(arr, mid+1, right);
    queryMerge(arr, left, mid, right);
  }
}

void eventMerge(Event **arr, int left, int mid, int right) {
  Event **temp = newEventArray(right-left+1);
  int i = left, j = mid + 1, t = 0;   
  while (i <= mid && j <= right) {
    if (arr[i]->day < arr[j]->day) temp[t++] = arr[i++];
    else temp[t++] = arr[j++];
  }
  while (i <= mid) temp[t++] = arr[i++];
  while (j <= right) temp[t++] = arr[j++];
  for (int i = left; i <= right; i++) arr[i] = temp[i-left];
  free(temp);
}

void eventSort(Event **arr, int left, int right) { 
  if (left < right) {
    int mid = left + (right - left)/2;
    eventSort(arr, left, mid);
    eventSort(arr, mid+1, right);
    eventMerge(arr, left, mid, right);
  }
}

然而,如果我尝试使用一个通用的mergesort,它可以像qsort一样对两种类型都有效,那么它就不能正常工作,尽管编译器和valgrind对此没有任何抱怨:

void merge(void *arr, int left, int mid, int right, int width, int (*comp)(const void*, const void*)) {
  void *temp = malloc((right - left + 1) * width);
  int i = left, j = mid + 1, t = 0;   
  while (i <= mid && j <= right) {
    if (comp((char*)arr + i*width, (char*)arr + j*width)) {
      memcpy((char*)temp + t*width, (char*)arr + i*width, width);
      i++; t++;
    } else {
      memcpy((char*)temp + t*width, (char*)arr + j*width, width);
      j++; t++;
    }
  }
  while (i <= mid) {
    memcpy((char*)temp + t*width, (char*)arr + i*width, width);
    i++; t++;
  }
  while (j <= right) {
    memcpy((char*)temp + t*width, (char*)arr + j*width, width);
    j++; t++;
  }
  for (int i = left; i <= right; i++) {
    memcpy((char*)arr + i*width, (char*)temp + (i - left)*width, width);
  }
  free(temp);
}

void mergeSort(void *arr, int left, int right, int width, int (*comp)(const void*, const void*)) { 
  if (left < right) {
    int mid = left + (right - left)/2;
    mergeSort(arr, left, mid, width, comp);
    mergeSort(arr, mid+1, right, width, comp);
    merge(arr, left, mid, right, width, comp);
  }
}

这是它的叫法:

mergeSort(queries, 0, size-1, sizeof(Query*), compQueries);

我尝试了不同的方法来得到正确的空指针,但我仍然不确定。有什么想法吗?

hrysbysz

hrysbysz1#

您对比较函数的使用已中断:

if (comp((char*)arr + i*width, (char*)arr + j*width)))

与相同

if (comp((char*)arr + i*width, (char*)arr + j*width)) != 0)

而您需要

if (comp((char*)arr + i*width, (char*)arr + j*width)) < 0)

在你的代码中,你会忽略哪个更大,但前提是它们是相同的。因此,你根本不排序。
添加<0修复了排序。
注意:您的特定函数使用正确的比较结果:

if (arr[i]->day < arr[j]->day)

相关问题