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);
    }
}

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

此代码中的内容范围很广。有些是阻碍，但最终它是您的合并功能。典型的合并算法在每次迭代中将一个 项目移动到目标缓冲区中，直到一个列表或另一个列表耗尽。一旦发生这种情况，剩余列表中的剩余项目将被批量复制到位并且算法终止。

您有一个根本性的缺陷，我们现在将解决这个问题。您的主循环运行 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 ever 在你的 j 之前筋疲力尽-side，从那时起你什么都不做，只是递增k直到它到达 n .其余j拆分列表的 -side 被完全忽略。然后，在该函数的末尾，您将未初始化的数据复制到原始数组的顶部。

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

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*你在你的代码中被严重利用了。我强烈建议您远离此类扩展。

---

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

#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