在mergesort算法中得到奇怪的结果[C]

问题描述 投票：0回答：1

我一直在C中基于动态数组结构实现mergesort算法。我一步一步地遵循了伪代码，但是我没有讲到重点。这是我定义结构以及创建和初始化结构的方法：

typedef struct dynarray {
    void **memory;
    size_t allocated;
    size_t used;
    int index;
} dynarray;

//creates a new, empty, dynarray
void create_dynarray(dynarray **array, size_t size) {
    *array = calloc(size, sizeof **array);
    (*array)->memory = NULL;
    (*array)->allocated = 0;
    (*array)->used = 0;
    (*array)->index = -1;
}

这是mergesort的实现：

//function used to slice the dynarray in two subarrays and call merge function
void *dynarray_mergesort(dynarray *param) {
    if (dynarray_length(param) > 1) {
        size_t size = param->used / sizeof(void*);  
        size_t m = size / 2;
        size_t n = size - size / 2;
        struct dynarray *l; 
        create_dynarray(&l, m);
        struct dynarray *r;
        create_dynarray(&r, n);  

        for (size_t i = 0 ; i < m; i++) {
            add_elem(l, param->memory[i]);
        }
        for (size_t j = m; j < size; j++) {
            add_elem(r, param->memory[j]);
        }

        dynarray_mergesort(l);
        dynarray_mergesort(r);
        dynarray_merge(param, l, r, size);
    }  
    return param;
}

//function used to mergesort the array
void *dynarray_merge(dynarray *param, dynarray *l, dynarray *r, int size) {
    int i = 0,j = 0, k = 0; 
    while (i < size/2 && j < size - size / 2) {
        if (l->memory[i] < r->memory[j]) {
            param->memory[k] = l->memory[i];  
            i++;
            k++;
        } else {     
            param->memory[k] = r->memory[j];
            j++;
            k++;      
        }
    }
    while (i < size / 2) {
        param->memory[k] = l->memory[i];
        i++;
        k++;
    }
    while (j < size - size / 2) {
        param->memory[k] = r->memory[j];
        j++;
        k++;
    }
    return param;
}

[当我在诸如[18, 14, 20, 16, 12]的数组上调用函数时，我得到相同的相同数组。我尝试添加一些printf()在mergesort函数中，我发现它似乎可以正确分割数组。因此，问题必须出在dynarray_merge()函数中。我检查第一个数组中的一个元素是否大于另一个数组中的一个元素的方式对我来说似乎是正确的，所以我完全陷入了困境。

我正在发布我的代码的可编译示例，以更好地向您展示我的意思。

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

typedef struct dynarray {
    void **memory;
    size_t allocated;
    size_t used;
    int index;
} dynarray;

//creates a new, empty, dynarray
void create_dynarray(dynarray **array, size_t size) {
    *array = calloc(size, sizeof **array);
    (*array)->memory = NULL;
    (*array)->allocated = 0;
    (*array)->used = 0;
    (*array)->index = -1;
}

//adds a new element at the bottom of dynarray
void add_elem(dynarray *array, void *data) {
    size_t toallocate;
    size_t size = sizeof(void *);
    if ((array->allocated - array->used) < size) { // if M - N ...
        toallocate = array->allocated == 0 ? size : (array->allocated * 2);
        array->memory = realloc(array->memory, toallocate);
        array->allocated = toallocate;
    }

    array->memory[++array->index] = data;
    array->used = array->used + size;
}

//get length of the dynarray
int dynarray_length(dynarray *array) {
    return array->index + 1;
}

//retrieves an element in a specific position of the dynarray
void *get_i_elem(dynarray *array, int index) {
    if (index < 0 || index > array->index)
        return NULL;

    return array->memory[index];
}

//function used to mergesort the array
void *dynarray_merge(dynarray *param, dynarray *l, dynarray *r, int size) {
    int i = 0,j = 0, k = 0;    
    while (i < size/2 && j < size - size / 2) {
        if (l->memory[i] < r->memory[j]) {
            param->memory[k] = l->memory[i];  
            i++;
            k++;
        } else {
            param->memory[k] = r->memory[j];
            j++;
            k++;    
        }
    }
    while (i < size / 2) {
        param->memory[k] = l->memory[i];
        i++;
        k++;
    }
    while (j < size - size / 2) {
        param->memory[k] = r->memory[j];
        j++;
        k++;
    }
    return param;
}

//function used to slice the dynarray in two subarrays and call merge function
void *dynarray_mergesort(dynarray *param) {
    if (dynarray_length(param) > 1) {
        size_t size = param->used / sizeof(void*);  
        size_t m = size / 2;
        size_t n = size - size / 2;
        struct dynarray *l; 
        create_dynarray(&l, m);
        struct dynarray *r;
        create_dynarray(&r, n);  

        for (size_t i = 0 ; i < m; i++) {
            add_elem(l, param->memory[i]);
        }
        for (size_t j = m; j < size; j++) {
            add_elem(r, param->memory[j]);
        }

        dynarray_mergesort(l);
        dynarray_mergesort(r);
        dynarray_merge(param, l, r, size);
    }  
    return param;
}

//print arrays, useful to test 
void print_array(dynarray *array) {
    for (int i = 0; i < dynarray_length(array); i++) {
        printf("%d\t", *(int *)get_i_elem(array, i));
        //puts("");
    }
}

int main() {
    struct dynarray *a;
    create_dynarray(&a, 5);
    int arr[5] = { 18, 14, 20, 16, 12};
    int *ap = malloc(sizeof(int));
    int *bp = malloc(sizeof(int));
    int *cp = malloc(sizeof(int));
    int *dp = malloc(sizeof(int));
    int *ep = malloc(sizeof(int));
    *ap = arr[0];
    *bp = arr[1];
    *cp = arr[2];
    *dp = arr[3];
    *ep = arr[4];
    add_elem(a, ap);
    add_elem(a, bp);
    add_elem(a, cp);
    add_elem(a, dp);
    add_elem(a, ep);
    printf("\nbefore mergesort\n");
    print_array(a);
    puts("");
    printf("\nafter mergesort\n");
    dynarray_mergesort(a);
    print_array(a);
}
c algorithm mergesort dynamic-arrays
1个回答
3
投票

问题是您如何比较元素：

if (l->memory[i] < r->memory[j]) ...

这里，您正在比较指针，而不是指向的值。您可以从malloc中的main调用中获得这些指针，这为您提供了升序的地址。

您对动态数组的实现将void *用作元素的类型，因此可以将其用于任何类型的元素。您的合并排序不知道使用哪种类型，因此不知道如何比较。

您可以像qsort一样为排序函数提供回调函数：

typedef int VoidPointerCmp(const void *a, const void *b);

然后将此函数传递给您的两个合并排序函数：

void *dynarray_mergesort(dynarray *param, , VoidPointerCmp *cmp) ...

并像这样比较您的物品：

if (cmp(l->memory[i], r->memory[j]) < 0) ...

一个合适的整数比较函数可能看起来像这样：

int int_cmp(const void *pa, const void *pb)
{
    const int *a = pa;
    const int *b = pb;

    if (*a < *b) return -1;
    if (*a > *b) return 1;
    return 0;
}

在main中，致电：

dynarray_mergesort(a, int_cmp);

一些注意事项：

  • 您为每个条目分配内存。这不是必需的。您可以使void指针指向现有数组的元素：

    for (int i = 0; i < 5; i++) add_elem(a, &arr[i]);

    排序不会影响原始数组arr。

  • 您不会释放分配的内存或破坏动态数组。您可能应该为动态数组编写一个析构函数，并在使用它们之后清理临时数组l和r。

  • 我认为您没有正确使用used字段。您可能不需要它：具有分配的数组大小和当前长度就足够了。 （您可以将索引替换为长度。）

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.