c语言中泛型归并排序的错误

Question

我有一个通用的合并排序，应该可以正常工作 我想用它来对指向客户端的指针数组进行排序，如下所示 例如按名字 为此，我使用以下比较函数 所有这些都应该运行良好，并且不会发生错误，除了数组未排序，并且当我在比较和排序函数中打印时，我没有得到实际内容

#include "MergeSort.h"
#include "function_Header.h"

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(void *arr, int l, int m, int r, size_t size,
           int (*compar)(const void *, const void *))
{
    // merge(base, 0, m, nitems, size, compar);
    int i, j, k;
    int n1 = m - l;
    int n2 = r - m;

    /* create temp arrays */
    void *L = malloc(n1 * size);
    if (L == NULL)
    {
        printf("allocation failed!\n");
        return;
    }
    void *R = malloc(n2 * size);
    if (R == NULL)
    {
        printf("allocation failed!\n");
        return;
    }
    
    /* Copy data to temp arrays L[] and R[] */
    memcpy(L, (char *)arr + l * size, n1 * size);
    memcpy(R, (char *)arr + m * size, n2 * size);
    
    
    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray
    while (i < n1 && j < n2) {
        if (compar((char *)L + i * size, (char *)R + j * size) <= 0)
        {
            memcpy((char *)arr + k * size, (char *)L + i * size, size);
            i++;
        } else {
            memcpy((char *)arr + k * size, (char *)R + j * size, size);
            j++;
        }
        k++;
    }
    
    /* Copy the remaining elements of L[], if there are any */
    while (i < n1) { 
        memcpy((char *)arr + k * size, (char *)L + i * size, size);
        i++;
        k++;
    }
    
    /* Copy the remaining elements of R[], if there are any */
    while (j < n2) {
        memcpy((char *)arr + k * size, (char *)R + j * size, size);
        j++;
        k++;
    }
    free(L);
    free(R);
}

/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergesort(void *base, size_t nitems, size_t size,
               int (*compar)(const void *, const void *))
{
    // ((movement*)base)->date
    printf("n name %s\\n",((customer*)base)->f_name);
    if (nitems <= 1) return;
    size_t m = nitems / 2;
    mergesort(base, m, size, compar);
    if (nitems % 2 == 0)
        mergesort((char *)base + m * size, m, size, compar);
    else
        mergesort((char *)base + m * size, m + 1, size, compar);

    merge(base, 0, m, nitems, size, compar);
}

typedef struct {
    char *f_name;
    char *l_name;
    char phone[10];
    char id[10];
    int final_sum;
    int sum_mov;
    movement **arrr_mov;
} customer;

compare_customer_f_name(const void *elem1, const void *elem2) {
    printf("%s", ((customer *)elem2)->f_name);
    return strcmp(((customer *)elem1)->f_name, ((customer *)elem2)->f_name);
}

mergesort(customers, size, sizeof(customer), compare_customer_f_name);

Answer 1

子数组的索引范围存在混乱：

• 在注释中指定第一个子数组是arr[l..m]和第二个子数组是arr[m+1..r]但是在代码中你假设左侧部分的长度是

   m - l

  和

  r

  是数组最后一个元素之后的索引，这与 C 中从零开始的索引一致。

• 太多教科书使用这种容易出错的约定，这需要令人困惑的

  +1

  /

  -1

  调整。

• 对所有索引变量使用

  size_t

  。

这是修改后的版本：

#include "MergeSort.h"
#include "function_Header.h"

// Merges two subarrays of arr[].
// First subarray is arr[l..m(
// Second subarray is arr[m..r(
void merge(void *arr, size_t l, size_t m, size_t r, size_t size,
           int (*compar)(const void *, const void *))
{
    size_t i, j, k;
    size_t n1 = m - l;

    /* create temp array (no need to save the right part) */
    void *L = malloc(n1 * size);
    if (L == NULL) {
        printf("allocation failed!\n");
        return;
    }
    
    /* Copy data to temp arrays */
    memcpy(L, (char *)arr + l * size, n1 * size);
    
    /* Merge the temp arrays back into arr[l..r( */
    i = 0; // Initial index of left subarray
    j = m; // Initial index of right subarray
    k = l; // Initial index of merged subarray
    while (i < n1 && j < r) {
        if (compar((char *)L + i * size, (char *)arr + j * size) <= 0)
        {
            memcpy((char *)arr + k * size, (char *)L + i * size, size);
            i++;
        } else {
            memcpy((char *)arr + k * size, (char *)arr + j * size, size);
            j++;
        }
        k++;
    }
    
    /* Copy the remaining elements of L[], if there are any */
    if (i < n1) { 
        memcpy((char *)arr + k * size, (char *)L + i * size, (n1 - i) * size);
    }
    
    free(L);
}

void mergesort(void *base, size_t nitems, size_t size,
               int (*compar)(const void *, const void *))
{
    if (nitems <= 1)
        return;
    size_t m = nitems / 2;
    mergesort(base, m, size, compar);
    mergesort((char *)base + m * size, nitems - m, size, compar);
    merge(base, 0, m, nitems, size, compar);
}

typedef struct {
    char *f_name;
    char *l_name;
    char phone[10];
    char id[10];
    int final_sum;
    int sum_mov;
    movement **arrr_mov;
} customer;

compare_customer_f_name(const void *elem1, const void *elem2) {
    const customer *e1 = elem1;
    const customer *e2 = elem2;
    return strcmp(e1->f_name, e2->f_name);
}

void sort_customers_by_name(customer *customers, size_t nitems) {
    mergesort(customers, nitems, sizeof(customer), compare_customer_f_name);
}