动态数组合并排序算法中的段错误问题

Question

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

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:%d\t", 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:%d\t", l->index);
   struct dynarray *r;
   create_dynarray(&r, n);  
   printf("index of right:%d\n", 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 结构有关。 Ps。调用 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("%d\t", *(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:%d\t", 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:%d\t", l->index);
   struct dynarray *r;
   create_dynarray(&r, n);  
   printf("index of right:%d\n", 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

create_dynarray函数内部

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

应改为：

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

做你真正想做的事（为数组分配一个内存 size dynarray * 大小的元素）。

Answer 2

除了您问题下方的评论中提到的分配不足（例如需要 *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 并防止 "comparison between signed and unsigned integer expressions")

如我的评论所述，您在 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 算法所需的更改）

动态数组合并排序算法中的段错误问题

Seg fault issue in mergesort algorithm with dynamic array

c

algorithm

mergesort

pointers

dynamic-arrays