检测到严重错误c0000374。MergeSort.exe已触发断点。

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

我试图用C语言实现合并排序。

但是当我测试代码的时候，我遇到了这样的情况 error c0000374 在我的合并排序函数中，当我试图将数组分割成左数组右数组时，出现了这样的问题。

enter image description here

代码如下。

typedef struct EntryStruct {
    int data;
    char *name;
} Entry;

typedef char *String;

void merge(Entry *output, Entry *L, int nL, Entry *R, int nR) {
    int i = 0;
    int j = 0;
    int k = 0;
    while (k < nL + nR) {
        if ((L[i].data != NULL && L[i].data < R[i].data) || R[j].data == NULL) {
            output[k] = L[i];
            i++;
        } else {
            output[k] = R[j];
            j++;
        }
        k++;
    }
}

void merge_sort(Entry *entries, int n) {
    if (n > 1) {
        int mid = n / 2;
        Entry *temp = (Entry *)malloc(n * sizeof(Entry));
        Entry *left = (Entry *)malloc(mid * sizeof(Entry));
        Entry *right = (Entry *)malloc((n - mid) * sizeof(Entry));

        for (int l = 0; l < mid; l++)
            left[l] = entries[l];

        for (int r = mid; r < n; r++)
            right[r] = entries[r];

        merge_sort(left, mid);
        merge_sort(right, n - mid);
        merge(temp, left, mid, right, n - mid);
        for (int i = 0 ; i < n; i++) {
            entries[i] = temp[i];
        }
        free(temp);
    }
}

Entry Entry_create(int data, String name) {
    Entry node;
    node.name = (String)malloc(strlen(name) + 1);
    strcpy(node.name, name);
    node.data = data;
    return node;
}

void printArrByName(Entry *arr, int s) {
    for (int i = 0; i < s; i++) {
        printf("%s\n", arr[i].name);
    }
}

int main(void) {
    Entry *arr = malloc(5 * sizeof(*arr));
    arr[0] = Entry_create(5, "abc");
    arr[1] = Entry_create(6, "def");
    arr[2] = Entry_create(2, "ghijk");
    arr[3] = Entry_create(3, "ksdljf");
    arr[4] = Entry_create(1, "lsdfjl");
    merge_sort(arr, 5);
    printArrByName(arr, 5);
    free(arr);
}

我想问一下，在我的情况下，这个问题的原因是什么，如何解决。

是由于我将数组分成左右数组的方式不对，还是数组的初始化有问题。

c arrays initialization breakpoints mergesort
2个回答
2
投票

代码中存在多个问题，导致未定义的行为。

  • [主要：未定义行为] 在 merge_sort 函数，循环 for (int r = mid; r < n; r++) right[r] = entries[r]; 指向的数组进行访问。right 超出终点。你应该写。

    for (int r = mid; r < n; r++)
    right[r - mid] = entries[r];

    这个错误是解释观察到的行为的一个很好的候选者，因为它破坏了... malloc() 内部数据，导致后续对 malloc() 崩溃。

  • [主要：内存泄漏] 你不自由 left，也不 right. 事实上，分配数组左右两部分的副本根本没有必要。

  • [主要：未定义行为] 在 merge 函数，您不需要测试 i 小于 nL，也不 j 小于 nR 在进入 L[i] 或 R[j]. 测试是否 data 成员不是 NULL 不够，访问一个数组末端以外的元素有未定义的行为。

  • [未成年人：不稳定的排序] L[i].data < R[i].data 的条目可能不会保留具有相同的 data 值。您应该使用 L[i].data <= R[i].data 来实现稳定的排序。

  • [提示] 定义 typedef char *String; 是个坏主意。不要把指针隐藏在 typedefs 后面，这很混乱，容易出错。

这里是一个修改的版本。

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

typedef struct EntryStruct {
    int data;
    char *name;
} Entry;

#ifdef _MSC_VER
// define strdup on legacy systems
char *strdup(const char *s) {
    size_t len = strlen(s);
    char *p = (char *)malloc(len + 1);
    if (p)
        memcpy(p, s, len + 1);
    return p;
}
#endif

void merge(Entry *output, Entry *L, int nL, Entry *R, int nR) {
    int i = 0;
    int j = 0;
    int k = 0;
    while (k < nL + nR) {
        if (i < nL && (j >= nR || L[i].data <= R[j].data)) {
            output[k] = L[i];
            i++;
        } else {
            output[k] = R[j];
            j++;
        }
        k++;
    }
}

void merge_sort(Entry *entries, int n) {
    if (n > 1) {
        int mid = n / 2;
        Entry *temp;
        Entry *left = entries;
        Entry *right = entries + mid;

        merge_sort(left, mid);
        merge_sort(right, n - mid);
        temp = (Entry *)malloc(n * sizeof(Entry));
        merge(temp, left, mid, right, n - mid);
        for (int i = 0; i < n; i++) {
            entries[i] = temp[i];
        }
        free(temp);
    }
}

Entry Entry_create(int data, const char *name) {
    Entry node;
    node.name = strdup(name);
    node.data = data;
    return node;
}

void printArrByName(Entry *arr, int n) {
    for (int i = 0; i < n; i++) {
        printf("%s\n", arr[i].name);
    }
}

int main(void) {
    Entry *arr = malloc(5 * sizeof(*arr));
    arr[0] = Entry_create(5, "abc");
    arr[1] = Entry_create(6, "def");
    arr[2] = Entry_create(2, "ghijk");
    arr[3] = Entry_create(3, "ksdljf");
    arr[4] = Entry_create(1, "lsdfjl");
    merge_sort(arr, 5);
    printArrByName(arr, 5);
    for (int i = 0; i < 5; i++)
        free(arr[i].name);
    free(arr);
    return 0;
}
1
投票

虽然对于小数组来说不需要，而且由于有基于问题代码的答案，这里有一个经过优化的自上而下的合并排序，通过使用一对相互递归的函数(...a2a, ...a2b)来避免回传。一个入口函数对临时数组进行一次性分配。在我的系统中，对一个400万结构的数组进行排序只需要不到0.5秒。

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

typedef struct EntryStruct {
    int data;
    char *name;
} Entry;

/* prototypes for mutually recursive functions */
void merge_sort_a2a(Entry *a, Entry *b, int ll, int ee);
void merge_sort_a2b(Entry *a, Entry *b, int ll, int ee);

void merge(Entry *a, Entry *b, int ll, int rr, int ee)
{
int o = ll;                             /* b[]       index */
int l = ll;                             /* a[] left  index */
int r = rr;                             /* a[] right index */
    while(1){
        if(a[l].data <= a[r].data){     /* if a[l] <= a[r] */
            b[o++] = a[l++];            /*  copy a[l] */
            if(l < rr)                  /*   if not end of left run */
                continue;               /*    continue (back to while) */
            while(r < ee)               /*   else copy rest of right run */
                b[o++] = a[r++];
            break;                      /*    and return */
        } else {                        /* else a[l] > a[r] */
            b[o++] = a[r++];            /*  copy a[r] */
            if(r < ee)                  /*   if not end of right run */
                continue;               /*    continue (back to while) */
            while(l < rr)               /*   else copy rest of left run */
                b[o++] = a[l++];
            break;                      /*    and return */
        }
    }
}

void merge_sort_a2a(Entry *a, Entry *b, int ll, int ee)
{
int rr;
    if(ee - ll < 2){            /* if 1 element */
        return;                 /*  return */
    }
    rr = ll + (ee-ll)/2;        /* mid point, start of right run */
    merge_sort_a2b(a, b, ll, rr);
    merge_sort_a2b(a, b, rr, ee);
    merge(b, a, ll, rr, ee);
}

void merge_sort_a2b(Entry *a, Entry *b, int ll, int ee)
{
int rr;
    if(ee - ll < 2){            /* if 1 element */
        b[ll] = a[ll];          /*  copy to b */
        return;
    }
    rr = ll + (ee-ll)/2;        /* mid point, start of right run */
    merge_sort_a2a(a, b, ll, rr);
    merge_sort_a2a(a, b, rr, ee);
    merge(a, b, ll, rr, ee);
}

void merge_sort(Entry *a, int n) {
    if(n < 2)
        return;
    Entry *b = malloc(n * sizeof(Entry));
    merge_sort_a2a(a, b, 0, n);
    free(b);
}

Entry Entry_create(int data, const char *name) {
    Entry node;
    node.name = _strdup(name);      /* _strdup is ISO name */
    node.data = data;
    return node;
}

void printArrByName(Entry *arr, int n) {
    for (int i = 0; i < n; i++) {
        printf("%s\n", arr[i].name);
    }
}

int main(void) {
    Entry *arr = malloc(5 * sizeof(*arr));
    arr[0] = Entry_create(5, "abc");
    arr[1] = Entry_create(6, "def");
    arr[2] = Entry_create(2, "ghijk");
    arr[3] = Entry_create(3, "ksdljf");
    arr[4] = Entry_create(1, "lsdfjl");
    merge_sort(arr, 5);
    printArrByName(arr, 5);
    for (int i = 0; i < 5; i++)
        free(arr[i].name);
    free(arr);
    return 0;
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.