C语言 具有动态数组的合并排序算法中的 Seg 错误问题

Question

我正在尝试使用 c 中的动态数组结构实现合并排序算法，但是当我调用函数来拆分原始数组而不是获取两个子数组时，我收到 seg 错误错误。 我很确定它与我如何定义结构的大小有关，但我无法克服它。以下是我如何定义我的结构以及如何创建和初始化它：

typedef struct dynarray
{
void **memory;
size_t allocated; //total size of the array
size_t used;  //used size of the array
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;
}

这就是我定义合并排序函数的方式

//function used to slice the dynarray in two subarrays and call merge function
void* dynarray_mergesort(dynarray *param){
if(dynarray_length(param)>1){    
param->index = 0;
printf("index of first:%dt", param->index);
size_t size = param->used;   
size_t m = size/2;
size_t n = size - size/2;
struct dynarray *l; 
create_dynarray(&l, m);
printf("index of left:%dt", l->index);
struct dynarray *r;
create_dynarray(&r, n);  
printf("index of right:%dn", r->index);
for(int i = 0 ; i < m; i++){
add_elem(l, param->memory[i]);
}for(int j = m; j < n; j++){
add_elem(r, param->memory[j]);
}
puts("first");
print_array(l);
puts("second");
print_array(r);
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,j,k; 
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++];
}while(j < size-size/2){
param->memory[k++] = r->memory[j++];
}
return param;
}
//function used to mergesort the array
void* dynarray_merge(dynarray *param, dynarray *l, dynarray *r, int size){
int i,j,k; 
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++];
}while(j < size-size/2){
param->memory[k++] = r->memory[j++];
}
return param;
}

可能我对如何定义动态数组的大小以及如何在我的函数中处理它感到困惑。下面是一个可编译的示例，可帮助您了解问题。它很长，但大多数函数都可以忽略，因为它们是实用程序函数并且它们似乎工作得很好。问题出在 mergesort 函数中，但恐怕它可能与我如何定义我的dynarray结构有关。 附言调用dynarray_merge(param, l , r, size);的行被评论，因为我正在处理位于dynarray_mergesort(dynarray *param);中的问题 Ps2：dynarray_mergesort(dynarray *param);内部调用的printf函数用作调试信息。

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

typedef struct dynarray
{
void **memory;
size_t allocated;
size_t used;
int index;
} dynarray;
//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];
}

//print arrays, useful to test 
void print_array(dynarray *array)
{  
for(int i = 0; i < dynarray_length(array); i++) {
printf("%dt", *(int *)get_i_elem(array, i));
//puts("");
}
}
//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;
}
//function used to slice the dynarray in two subarrays and call merge function
void* dynarray_mergesort(dynarray *param){
if(dynarray_length(param)>1){    
param->index = 0;
printf("index of first:%dt", param->index);
size_t size = param->used;   
size_t m = size/2;
size_t n = size - size/2;
struct dynarray *l; 
create_dynarray(&l, m);
printf("index of left:%dt", l->index);
struct dynarray *r;
create_dynarray(&r, n);  
printf("index of right:%dn", r->index);
for(int i = 0 ; i < m; i++){
add_elem(l, param->memory[i]);
}for(int j = m; j < n; j++){
add_elem(r, param->memory[j]);
}
puts("first");
print_array(l);
puts("second");
print_array(r);
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,j,k; 
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++];
}while(j < size-size/2){
param->memory[k++] = r->memory[j++];
}
return param;
}
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);
dynarray_mergesort(a);   
print_array(a);
}

Answer 1

除了问题下方评论中提到的分配不足(例如需要*array = calloc(size, sizeof **array);(，您还有一个简单的错误导致您的 SegFault(您还有其他错误(。您以dynarray_mergesort的形式存储size变量中的字节数，而不是指针数。因此dynarray_mergesort，当您声明size_t size = param->used;大小值是sizeof(void*)的倍数时(例如sizeof(a_pointer)( 乘以您实际使用的指针数。这会导致m和n的值不正确。

要解决此问题，您只需执行以下操作：

size_t size = param->used / sizeof(void*);

您的循环限制在以下方面有另一个错误：

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

m = size/2;和n = size - size/2;的地方.你实际上需要你的m -> size限制，例如：

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

(注意：上面i和j的正确类型都size_t对应于m和n，并防止"有符号和无符号整数表达式之间的比较"(

正如我在评论中指出的，您在dynarray_merge中存在未初始化的值问题。您需要初始化i和k，例如

int i=0, j=0, k=0; 

在尝试之前：

i++;
k++;

通过这些更改，您的代码可以毫无问题地运行到最后(除了泄漏内存(：

$ ./bin/dynarraymergeorig
index of first:0        index of left:-1        index of right:-1
first
18      14
second
20      16      12
index of first:0        index of left:-1        index of right:-1
first
18
second
14
index of first:0        index of left:-1        index of right:-1
first
20
second
16      12
index of first:0        index of left:-1        index of right:-1
first
16
second
12
18

您仍然在合并列表时遇到问题(留给您进一步调查(，但您的 SegFault 问题已解决。如果您有其他问题，请告诉我。(修复留给您的merge算法所需的更改除外(

Answer 2

create_dynarray函数的内部

*array = calloc(size, sizeof(array));

应改为：

*array = calloc(size, sizeof(**array))

做你实际想做的事情(为数组分配一个内存，size dynarray *大小的元素(。