检测到堆损坏 - 使用字符串实现归并排序

Question

之前我自己实现了 "classical" 合并排序，它对一个 int 数组进行排序。关注代码：

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

void merge(int a[], int b[], int c[], int m, int n)
{
    int   i = 0, j = 0, k = 0;

    while (i < m && j < n)
        if (a[i] < b[j])
            c[k++] = a[i++];
        else
            c[k++] = b[j++];
    while (i < m)
        c[k++] = a[i++];
    while (j < n)
        c[k++] = b[j++];
}

void mergesort_pot2(int key[], int n)
{
    int    j, k, *w;

    w = calloc(n, sizeof(int));
    for (k = 1; k < n; k *= 2) {
        for (j = 0; j < n - k; j += 2 * k)
            merge(key + j, key + j + k, w + j, k, k);
        for (j = 0; j < n; ++j)
            key[j] = w[j];
    }
    free(w);
}

void mergesort(int key[], int n)
{
    int i, cnt = 0, *x, v, b = 0, vv = 0, bb;

    while (n - cnt > 0)
    {
        for (i = 1; i < n - cnt; i *= 2);
        if (i > n - cnt)
            i /= 2;

        x = calloc(i, sizeof(int));                     

        v = 0;
        while (v < i)
            x[v++] = key[b++];

        mergesort_pot2(x, i);                           

        bb = 0;
        while (bb < i)                                  
            key[vv++] = x[bb++];

        free(x);                                        
        cnt += i;                                       
    }
}

int main(void)
{
    int   i, key[] = { 4, 3, 1, 67, 55, 8, 0, 4,
        -5, 37, 7, 4, 2, 9, 1, -1, 100};

    printf("Before mergesort:\n");
    for (i = 0; i < 17; ++i)
        printf("%4d", key[i]);
    putchar('\n');

    mergesort(key, 17);

    printf("After mergesort:\n");
    for (i = 0; i < 17; ++i)
        printf("%4d", key[i]);
    putchar('\n');
    return 0;
}

现在，作为练习，我修改了该代码以使其适用于 char* 数组，但我在某处存在堆错误。我尝试使用 Dr. Memory 对其进行调试，但它使我的 visual studio 2013 无法正常运行，但这是另一回事了。

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

#define LENGTH      5

void merge(char *a[], char *b[], char *c[], int m, int n)
{
    int   i = 0, j = 0, k = 0;

    while (i < m && j < n)
        if (strcmp(a[i], b[j]) < 0)
            c[k++] = a[i++];
        else
            c[k++] = b[j++];
    while (i < m)
        c[k++] = a[i++];
    while (j < n)
        c[k++] = b[j++];
}

void mergesort_pot2(char *key[], int n)
{
    int    j, k;
    char **w;
    int i;

    w = calloc(n, sizeof(char *));
    for (i = 0; i < n; ++i)
        w[i] = calloc(strlen(key[i]), sizeof(char));

    for (k = 1; k < n; k *= 2) {
        for (j = 0; j < n - k; j += 2 * k)
            merge(key + j, key + j + k, w + j, k, k);
        for (j = 0; j < n; ++j)
            key[j] = w[j];
    }
    for (i = 0; i < n; ++i)
        free(w[i]);
    free(w);
}

void mergesort(char *key[], int n)
{
    int i, cnt = 0, v, b = 0, vv = 0, bb;
    char **x;
    int y;

    while (n - cnt > 0)
    {
        for (i = 1; i < n - cnt; i *= 2);
        if (i > n - cnt)
            i /= 2;

        x = calloc(i, sizeof(char *));

        for (y = 0; y < i; ++y)
            x[y] = calloc(strlen(key[y]), sizeof(char));                     
        v = 0;
        while (v < i)
            strcpy(x[v++], key[b++]);

        mergesort_pot2(x, i);                           

        bb = 0;
        while (bb < i)                                  
            strcpy(key[vv++], x[bb++]);

        for (y = 0; y < i; ++y)
            free(x[y]);
        free(x);                                        

        cnt += i;
    }
}

int main(void)
{
    int   i;
    char *key[LENGTH] = { "Hi", "this", "is", "a", "test" };

    printf("Before mergesort:\n");
    for (i = 0; i < LENGTH; ++i)
        printf("%s ", key[i]);
    putchar('\n');

    mergesort(key, LENGTH);

    printf("After mergesort:\n");
    for (i = 0; i < LENGTH; ++i)
        printf("%s ", key[i]);
    putchar('\n');
    return 0;
}

Answer 1

void mergesort_pot2(char *key[], int n)
{
    int    j, k;
    char **w;

    w = calloc(n, sizeof(char*));
    for (k = 1; k < n; k *= 2) {
        for (j = 0; j < n - k; j += 2 * k)
            merge(key + j, key + j + k, w + j, k, k);
        for (j = 0; j < n; ++j)
            key[j] = w[j];
    }
    free(w);
}

void mergesort(char *key[], int n)
{
    int i, cnt = 0, v, b = 0, vv = 0, bb;
    char **x;

    while (n - cnt > 0)
    {
        for (i = 1; i < n - cnt; i *= 2);
        if (i > n - cnt)
            i /= 2;

        x = calloc(i, sizeof(char *));

        v = 0;
        while (v < i)
            x[v++] = key[b++];

        mergesort_pot2(x, i);                           

        bb = 0;
        while (bb < i)                                  
            key[vv++]= x[bb++];

        free(x);                                        

        cnt += i;
    }
}

检测到堆损坏 - 使用字符串实现归并排序

Heap corruption detected - implementation of mergesort with strings

c

string

sorting

mergesort

heap-corruption