检测到严重错误 c0000374。 MergeSort.exe 已触发断点
Critical error detected c0000374. MergeSort.exe has triggered a breakpoint
我试图在 C 中实现归并排序。
但是当我测试代码时，当我尝试将数组拆分为左右数组时，我在合并排序函数中遇到了这个 error c0000374。
代码如下
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);
}
想请问我这个问题是什么原因造成的，如何解决
这是我左右拆分数组的方式不对，还是与数组的初始化有关
代码中存在多个导致未定义行为的问题：
[主要：未定义行为]在merge_sort函数中，循环for (int r = mid; r < n; r++) right[r] = entries[r];访问[=指向的数组14=] 超越结束。你应该写：
for (int r = mid; r < n; r++)
right[r - mid] = entries[r];
这个错误很适合解释观察到的行为，因为它破坏了 malloc() 内部数据，导致对 malloc() 的后续调用崩溃。
[重大：内存泄漏] 你不释放 left，也不释放 right。事实上，甚至不需要分配数组左右部分的副本。
[主要：未定义的行为] 在 merge 函数中，您不测试 i 是否小于 nL，在访问 L[i] 或 R[j] 之前，j 也不小于 nR。测试 data 成员是否不是 NULL 是不够的，访问超出数组末尾的元素具有未定义的行为。
[轻微：排序不稳定] L[i].data < R[i].data 可能无法保留具有相同 data 值的条目的顺序。您应该使用 L[i].data <= R[i].data 来实现稳定排序。
[提示] 定义 typedef char *String; 是个坏主意。不要将指针隐藏在 typedef 后面，这会造成混淆并容易出错。
这是修改后的版本：
#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;
}
虽然小数组不需要，并且由于有基于问题代码的答案，这里有一个稍微优化的自上而下合并排序，它通过使用一对相互递归函数 (...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;
}
我试图在 C 中实现归并排序。
但是当我测试代码时，当我尝试将数组拆分为左右数组时，我在合并排序函数中遇到了这个 error c0000374。
代码如下
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);
}
想请问我这个问题是什么原因造成的，如何解决
这是我左右拆分数组的方式不对，还是与数组的初始化有关
代码中存在多个导致未定义行为的问题：
[主要：未定义行为]在
merge_sort函数中，循环for (int r = mid; r < n; r++) right[r] = entries[r];访问[=指向的数组14=] 超越结束。你应该写：for (int r = mid; r < n; r++) right[r - mid] = entries[r];这个错误很适合解释观察到的行为，因为它破坏了
malloc()内部数据，导致对malloc()的后续调用崩溃。[重大：内存泄漏] 你不释放
left，也不释放right。事实上，甚至不需要分配数组左右部分的副本。[主要：未定义的行为] 在
merge函数中，您不测试i是否小于nL，在访问L[i]或R[j]之前，j也不小于nR。测试data成员是否不是NULL是不够的，访问超出数组末尾的元素具有未定义的行为。[轻微：排序不稳定]
L[i].data < R[i].data可能无法保留具有相同data值的条目的顺序。您应该使用L[i].data <= R[i].data来实现稳定排序。[提示] 定义
typedef char *String;是个坏主意。不要将指针隐藏在 typedef 后面，这会造成混淆并容易出错。
这是修改后的版本：
#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;
}
虽然小数组不需要，并且由于有基于问题代码的答案，这里有一个稍微优化的自上而下合并排序，它通过使用一对相互递归函数 (...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;
}