C 语言中的泛型合并排序错误 [已关闭]

Error in generic merge sort in c language [closed]

提问人:איתמר לבן 提问时间:11/2/2023 最后编辑:chqrlieאיתמר לבן 更新时间:11/22/2023 访问量:38

问:


编辑问题以包括所需的行为、特定问题或错误以及重现问题所需的最短代码。这将有助于其他人回答这个问题。

13小时前关闭。

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

#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);
C 合并排序

评论


答:

0赞 chqrlie 11/22/2023 #1

子数组的索引范围存在混淆:

  • 在注释中,您指定第一个子数组是 arr[l..m] 和第二个子数组是 arr[m+1..r],但在代码中,你假设左边部分的长度是 和 是数组最后一个元素之后的索引,这与 C 中从零开始的索引一致。m - lr

  • 太多的教科书使用这种容易出错的约定,这需要混淆/调整。不要将其用于 C、C++、C#、java、javascript、typescript、Python 中的实现......+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);
}