前一段时间,我试图编程一个合并排序。在某个时候,我得到了一个错误,我能够解决,但仍然保存代码,因为有一些奇怪的,我不明白。代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int elem;
void mergesort(elem * arr, unsigned n){
if(n != 1){
if(n == 2){
if(arr[0] > arr[1]){
int change = arr[0];
arr[0] = arr[1];
arr[1] = change;
}
}else{
unsigned i = 0, j = 0, mit = (n+1)>>2, fin = n>>2;
elem * arr_2 = (elem *)malloc(sizeof(elem) * n), * mit_arr = arr+mit;
mergesort(arr, mit);
mergesort(mit_arr, fin);
while(i < mit || j < fin){
if(arr[i] <= mit_arr[j]){
arr_2[j+i] = arr[i];
i++;
}else{
arr_2[j+i] = mit_arr[j];
j++;
}
}
for(i=0; i<n; i++)
arr[i] = arr_2[i];
free(arr_2);
}
}
}
int main(){
unsigned a = 10;
int i;
elem * arr = (elem*)malloc(sizeof(elem) * a);
arr[0] = 12;
arr[1] = 3;
arr[2] = -3;
arr[3] = 22;
arr[4] = 12;
arr[5] = 11;
arr[6] = 4;
arr[7] = 9;
arr[8] = 10;
arr[9] = 2;
printf("something\n"); // 1
mergesort(arr, a);
printf("\n");
for(i=0; i<a; i++){
printf("%d, ", arr[i]);
}
printf("\n");
free(arr);
return 0;
}
问题是,尽管代码没有按照我的要求运行,而且看起来没有错误,但如果我注解掉标记为1(printf("something\\n");
)的行,则会出现错误“malloc(): corrupted top size
“。实际上,我不知道为什么会发生这样的事情,所以我来到这里,看看是否有人能给出解释。
我试着用gdb
调试程序,得到了同样的错误,但有更多的信息:
Program received signal SIGABRT, Aborted.
__GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50
50 ../sysdeps/unix/sysv/linux/raise.c: No such file or directory.
但还是不知道发生了什么。
1条答案
按热度按时间eagi6jfj1#
你的代码有几个主要的问题,这些问题你应该能够通过检查你的函数使用的值是否是你所期望的来测试自己。
这里是第一个问题,你已经计算出数组前半部分的长度为
(n+1)>>2
,然后你假设数组剩余部分的长度为n>>2
,这是不正确的,将一个值右移2个二进制位等于除以4。使用“普通”的数学方法比试图变得聪明要好得多。这样可以减少出错的机会,并使代码更容易阅读。
另一个问题是合并,你已经运行while循环直到
i
和j
都超出范围,但是在你的循环中,保证至少在一次迭代中,其中一个值会超出范围。合并数组的一个更好的方法是使用三个循环。第一个循环运行直到数组中的任意一个被合并,剩下的两个循环将复制另一个数组的剩余部分。