c - 在 C 中进行合并排序时不断获取垃圾值

Question

我正在研究一个通用的合并排序算法。现在的问题是，当我打印所谓的“排序”数组的内容时，我不断得到垃圾值。

归并排序算法：

void merge(void *a, int n, int size, int (*fcmp)(const void *, const void *)){
    int i, j, k, mid=n/2;
    void * temp = (void *)malloc(n*size);

    for(i=0, j=mid, k=0; k<n; k++){
        if((i<mid)&&(j>=  n)){
            memcpy(temp+(k*size), a+i*size, size);
            i++;
        }
        else if((i<mid)&&(fcmp(a + i*size, a+j*size) <= 0)){
            memcpy(temp+(k*size), a+j*size, size);
            j++;
        }
    }

    for(i=0, j=0; j<n; i++, j++)
        memcpy(a+(j*size),temp+(i*size),size);
    free(temp);
}

void genmsort(void *a, int n, int size, int (*fcmp)(const void *, const void *)){
    if(n>1){
        genmsort(a, n/2, size, (int(*)(const void *, const void *)) compnode);
        genmsort(a+(n/2)*size, n-n/2, size, (int(*)(const void *, const void *)) compnode);
        merge(a, n, size, (int(*)(const void *, const void *)) compnode);
    }
}

复合节点函数：

int compnode(node *a, node *b){
    return (strcmp(a->name, b->name));
}

初始化函数：

void init_node(node a[], int n){
int i;
    for(i=0; i<n; i++){
        a[i].stdno=i+1;
        sprintf(a[i].name, "%li", a[i].stdno);
    }
    srand(8);
    for(i=0; i<n; i++)
        genswap(a+i, a+(rand()%n), sizeof(node));
}

主要功能：

int main(){
    int n=10;
    clock_t t1, t2;

    node *b;
    b=(node *)malloc(n*sizeof(node));
    init_node(b, n);

    t1=clock();
    genmsort(b, n, sizeof(node), (int(*)(const void *, const void *)) compnode);

    t2=clock();
    free(b);
}

这里有什么问题？对于冗长的代码，我很抱歉，但我希望你能理解它。我非常感谢您的帮助，因为我已经被这段代码困住了一段时间。

Answer 1

辅助问题

从评论转录到问题。

看在怜悯的份上，理智地写作compnode()，这样你就不必经历可怕的演员阵容！编写它以获取两个const void *参数并在代码中转换它们（这将是一个无操作）：

int compnode(const void *v1, const void *v2)
{
    const node *a = v1;
    const node *b = v2;
    return strcmp(a->name, b->name);
}

另外，不要使用 GCC 的扩展。如果您对编写可移植代码有任何自负，这是一个坏习惯。a+(n/2)*size根据 C 标准，将参数写入何处void *a是未定义的行为。在添加之前，您必须转换为char *（或除 之外的其他类型void *）。

在genmnode()中，您应该传递fcmp给递归函数和merge()函数，而不是compnode()直接传递。

甘尼库斯问道：

你是什​​么意思通过fcmp而不是compnode？

WhozCraig解释说：

[它] 意味着您将自定义比较器函数作为fcmp参数传递给“通用”排序函数。在该函数中，您盲目地传递compnode给递归调用。您应该fcmp改为传递给那些递归调用，或者您的“通用”意识形态刚刚消失了。

主要问题

主要问题在于您的merge()功能。接口是最不寻常的。通常，您传递两个要合并的数组，以及每个数组的大小。你选择通过一个阵列并做一些花哨的步法。主 for 循环中的代码搞砸了一切。

void merge(void *a, int n, int size, int (*fcmp)(const void *, const void *)){
    int i, j, k, mid=n/2;
    void * temp = (void *)malloc(n*size);

    for(i=0, j=mid, k=0; k<n; k++){
        if((i<mid)&&(j>=  n)){
            memcpy(temp+(k*size), a+i*size, size);
            i++;
        }
        else if((i<mid)&&(fcmp(a + i*size, a+j*size) <= 0)){
            memcpy(temp+(k*size), a+j*size, size);
            j++;
        }
    }

    for(i=0, j=0; j<n; i++, j++)
        memcpy(a+(j*size),temp+(i*size),size);
    free(temp);
}

尾随循环应该是一个单一的memcpy()操作，但那里的东西会起作用。

你有一个数组，a，总共有n给定大小的元素。它必须被视为两个子数组，一个是元素 [0..mid)，LHS，另一个是元素 [mid..n)，RHS。范围包括下限，不包括上限。

循环内的第一个条件是“如果 LHS 中有一个元素，而 RHS 中没有任何元素，则将 LHS 元素复制到输出”。第二个条件表示“如果 LHS 中还有一个元素（并且通过消除，RHS 中也有一个元素），并且 LHS 比较小于 RHS，则将 RHS 元素复制到输出”。

编写合并过程有不同且最终等效的方法，但通常最容易理解的是：

while (item left in LHS and item left in RHS)
{
    if (item in LHS is smaller than item in RHS)
        copy LHS to result
    else
        copy RHS to result
}
while (item left in LHS)
    copy item to result
while (item left in RHS)
    copy item to result

实现的循环并不接近实现该逻辑或其等价物之一。

---

工作代码

这是我的代码诊断版本。memset()顶部的应该merge()无关紧要；您应该复制temp并覆盖所有 X。在实践中，你不是。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node node;
struct node
{
    long stdno;
    char name[20];
};

static
void genswap(void *v1, void *v2, size_t size)
{
    char v3[size];
    memmove(v3, v1, size);
    memmove(v1, v2, size);
    memmove(v2, v3, size);
}

static
void print_node(const char *tag, node a[], int n)
{
    printf("%s\n", tag);
    for (int i = 0; i < n; i++)
        printf("%2d: %p %2ld %s\n", i, &a[i], a[i].stdno, a[i].name);
}

static
void merge(void *a, int n, int size, int (*fcmp)(const void *, const void *))
{
    int i, j, k, mid = n/2;
    void *temp = (void *)malloc(n*size);
    memset(temp, 'X', n*size);

    printf("-->> %s\n", __func__);
    print_node("Before Merge", (node *)a, n);
    for (i = 0, j = mid, k = 0; k < n; k++)
    {
        if ((i < mid) && (j >= n))
        {
            memcpy(temp+(k*size), a+i*size, size);
            i++;
        }
        else if ((i < mid) && (fcmp(a + i*size, a+j*size) <= 0))
        {
            memcpy(temp+(k*size), a+j*size, size);
            j++;
        }
    }
    print_node("Mid Merge", (node *)temp, n);

    for (i = 0, j = 0; j < n; i++, j++)
        memcpy(a+(j*size), temp+(i*size), size);
    free(temp);
    print_node("After Merge", (node *)a, n);
    printf("<<-- %s\n", __func__);
}

static
void genmsort(void *a, int n, int size, int (*fcmp)(const void *, const void *))
{
    if (n > 1)
    {
        genmsort(a, n/2, size, fcmp);
        genmsort(a+(n/2)*size, n-n/2, size, fcmp);
        merge(a, n, size, fcmp);
    }
}

static
int compnode(const void *v1, const void *v2)
{
    const node *a = v1;
    const node *b = v2;
    printf("%s: (%ld:%s) vs (%ld:%s)\n", __func__, a->stdno, a->name, b->stdno, b->name);
    return(strcmp(a->name, b->name));
}

static
void init_node(node a[], int n)
{
    for (int i = 0; i < n; i++)
    {
        a[i].stdno = i+1;
        sprintf(a[i].name, "%li", a[i].stdno);
    }
    srand(8);
    for (int i = 0; i < n; i++)
        genswap(a+i, a+(rand()%n), sizeof(node));
}

int main(void)
{
    int n = 10;
    node *b = (node *)malloc(n*sizeof(node));

    init_node(b, n);
    print_node("Before:", b, n);
    genmsort(b, n, sizeof(node), compnode);
    print_node("After:", b, n);
    free(b);

    return 0;
}

Answer 2

这段代码中的东西的纬度是丰富的。有些是阻碍，但最终它是您的合并功能。典型的合并算法在每次迭代时将一个项目移动到目标缓冲区，直到一个列表或另一个列表用尽。一旦发生这种情况，剩余列表中的剩余项目将被批量复制到位并且算法终止。

你有一个根本性的缺陷，我们现在将介绍它。您的主循环k一直运行到n，至少这是正确的。但是，请查看 if-else-if 条件中的第一个表达式：

    if((i<mid)&&(j>=  n))
    {
        memcpy(temp+(k*size), a+i*size, size);
        i++;
    }
    else if((i<mid)&&(fcmp(a + i*size, a+j*size) <= 0))
    {
        memcpy(temp+(k*size), a+j*size, size);
        j++;
    }

他们都有，i<mid所以这可以简化为：

    if (i<mid)
    {
        if (j>=n)
        {
            memcpy(temp+(k*size), a+i*size, size);
            i++;
        }
        else if (fcmp(a + i*size, a+j*size) <= 0))
        {
            memcpy(temp+(k*size), a+j*size, size);
            j++;
        }
    }

这意味着如果您的i-side在您的-side之前已经用尽，那么您从那时起什么也不j做，只是递增直到达到. 拆分列表的 -side 的其余部分被完全忽略。然后，在函数结束时，将未初始化的数据复制到原始数组的顶部。knj

有些事情要考虑。首先，输入您的比较器功能要求并坚持下去。比较器有责任遵守回调请求者的要求；不是相反。

typedef int (*fn_cmp)(const void*, const void*);

并通过实现对该标准的回调来正确使用它。

// compare two nodes.
int compare_node(const void* lhs, const void* rhs)
{
    const node* lhn = lhs;
    const node* rhn = rhs;
    return (strcmp(lhn->name, rhn->name));
}

这也使您的通用合并排序更加清晰：

// generic mergesort algorithm
void genmsort(void *src, unsigned int len, unsigned int size, fn_cmp fcmp)
{
    if (len < 2)
        return;

    unsigned int mid = len/2;
    genmsort(src, mid, size, fcmp);
    genmsort((unsigned char*)src+(mid*size), len - mid, size, fcmp);
    merge(src, mid, len-mid, size, fcmp);
}

除了可读性之外，以下内容与您的最大区别是添加了第二个长度参数（这个有效merge的事实被认为是一个奖励）。您的代码从最初传入的单个长度推断出这个值；在计算递归分区大小时，您在代码中完全独立的位置执行的操作这些相同的大小也需要在此处传递，原因有多种，包括一致性和可用性）。

请考虑以下问题。如果可以更好地注释这个算法，或者让它更清晰，我不知道如何：

// merges two lists back to back in a single sequence.
void merge(void *src,
           unsigned int alen, // note parition size.
           unsigned int blen, // and again here.
           unsigned int size,
           fn_cmp fcmp)
{
    void *bsrc = (unsigned char*)src + alen * size;
    void *dst = malloc((alen + blen)*size);
    unsigned int a = 0, b = 0, k = 0;

    for (k=0; k<(alen+blen); ++k)
    {
        // still got a's ?
        if (a < alen)
        {
            // still got b's ?
            if (b < blen)
            {
                // get "lesser" of the two.
                if (fcmp((const unsigned char*)src + a*size,
                         (const unsigned char*)bsrc + b*size) <= 0)
                {
                    // a is less. move it in.
                    memcpy((unsigned char *)dst + k*size,
                           (const unsigned char*)src + a++*size, size);
                }
                else
                {   // b is less. move it in.
                    memcpy((unsigned char *)dst + k*size,
                           (const unsigned char*)bsrc + b++*size, size);
                }
            }
            else
            {   // no more b's. move the rest of the a's
                // into the target and leave.
                memcpy((unsigned char *)dst + k*size,
                       (const unsigned char*)src + a*size, (alen - a)*size);
                k += (alen-a);
            }
        }
        else
        {   // else no a's. move the rest of the b's into
            //  the target and leave.
            memcpy((unsigned char *)dst + k*size,
                   (const unsigned char*)bsrc + b*size, (blen - b)*size);
            k += (blen-b);
        }
    }

    // copy final output.
    memcpy(src, dst, (alen+blen)*size);
    free(dst);
}

最后，此代码不需要任何编译器扩展，例如void*您在代码中大量利用的违反标准的增量。我强烈建议您远离此类扩展。

---

以下是用于验证上述算法及其接口的完整测试程序。仔细阅读。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#include <time.h>

// simple node definition.
typedef struct node
{
    char name[32];
    int id;
} node;

// compare two nodes.
int compare_node_names(const void* lhs, const void* rhs)
{
    const node* lhn = lhs;
    const node* rhn = rhs;
    return (strcmp(lhn->name, rhn->name));
}

// compare two nodes.
int compare_node_ids(const void* lhs, const void* rhs)
{
    const node* lhn = lhs;
    const node* rhn = rhs;
    return (lhn->id  - rhn->id);
}

// comparator requirements.
typedef int (*fn_cmp)(const void*, const void*);

// merges two lists back to back in a single sequence.
void merge(void *src,
           unsigned int alen, // note parition size.
           unsigned int blen, // and again here.
           unsigned int size,
           fn_cmp fcmp)
{
    void *bsrc = (unsigned char*)src + alen * size;
    void *dst = malloc((alen + blen)*size);
    unsigned int a = 0, b = 0, k = 0;

    for (k=0; k<(alen+blen); ++k)
    {
        // still got a's ?
        if (a < alen)
        {
            // still got b's ?
            if (b < blen)
            {
                // get "lesser" of the two.
                if (fcmp((const unsigned char*)src + a*size,
                         (const unsigned char*)bsrc + b*size) <= 0)
                {
                    // a is less. move it in.
                    memcpy((unsigned char *)dst + k*size,
                           (const unsigned char*)src + a++*size, size);
                }
                else
                {   // b is less. move it in.
                    memcpy((unsigned char *)dst + k*size,
                           (const unsigned char*)bsrc + b++*size, size);
                }
            }
            else
            {   // no more b's. move the rest of the a's
                // into the target and leave.
                memcpy((unsigned char *)dst + k*size,
                       (const unsigned char*)src + a*size, (alen - a)*size);
                k += (alen-a);
            }
        }
        else
        {   // else no a's. move the rest of the b's into
            //  the target and leave.
            memcpy((unsigned char *)dst + k*size,
                   (const unsigned char*)bsrc + b*size, (blen - b)*size);
            k += (blen-b);
        }
    }

    // copy final output.
    memcpy(src, dst, (alen+blen)*size);
    free(dst);
}

// generic mergesort algorithm
void genmsort(void *src, unsigned int len, unsigned int size, fn_cmp fcmp)
{
    if (len < 2)
        return;

    unsigned int mid = len/2;
    genmsort(src, mid, size, fcmp);
    genmsort((unsigned char*)src+(mid*size), len - mid, size, fcmp);
    merge(src, mid, len-mid, size, fcmp);
}

int main()
{
    static const unsigned int N = 50;
    node *data = malloc(N * sizeof(*data));
    int i=0;

    srand((unsigned)time(NULL));
    for (i=0;i<N;++i)
    {
        data[i].id = i+1;
        sprintf(data[i].name, "String%.3d", 1 + rand() % 999);
    }

    // sort on names.
    genmsort(data, N, sizeof(data[0]), compare_node_names);
    for (i=0;i<N;++i)
        printf("%s : %u\n", data[i].name, data[i].id);
    printf("\n");

    // use a different comparator, this time by id.
    genmsort(data, N, sizeof(data[0]), compare_node_ids);
    for (i=0;i<N;++i)
        printf("%s : %u\n", data[i].name, data[i].id);
    printf("\n");

    free(data);

    return 0;
}

输出

String053 : 49
String097 : 38
String104 : 46
String122 : 41
String129 : 8
String139 : 3
String168 : 30
String184 : 22
String222 : 16
String230 : 28
String249 : 4
String265 : 34
String285 : 44
String295 : 20
String298 : 47
String300 : 19
String321 : 2
String375 : 37
String396 : 50
String408 : 13
String430 : 31
String466 : 35
String483 : 24
String484 : 27
String491 : 25
String494 : 39
String507 : 10
String513 : 7
String514 : 11
String539 : 5
String556 : 29
String570 : 43
String583 : 33
String584 : 42
String620 : 15
String632 : 12
String671 : 21
String705 : 23
String710 : 14
String714 : 45
String724 : 18
String733 : 9
String755 : 48
String805 : 36
String814 : 6
String847 : 32
String876 : 40
String893 : 26
String906 : 17
String972 : 1

String972 : 1
String321 : 2
String139 : 3
String249 : 4
String539 : 5
String814 : 6
String513 : 7
String129 : 8
String733 : 9
String507 : 10
String514 : 11
String632 : 12
String408 : 13
String710 : 14
String620 : 15
String222 : 16
String906 : 17
String724 : 18
String300 : 19
String295 : 20
String671 : 21
String184 : 22
String705 : 23
String483 : 24
String491 : 25
String893 : 26
String484 : 27
String230 : 28
String556 : 29
String168 : 30
String430 : 31
String847 : 32
String583 : 33
String265 : 34
String466 : 35
String805 : 36
String375 : 37
String097 : 38
String494 : 39
String876 : 40
String122 : 41
String584 : 42
String570 : 43
String285 : 44
String714 : 45
String104 : 46
String298 : 47
String755 : 48
String053 : 49
String396 : 50