Я пытаюсь реализовать алгоритм сортировки слиянием, используя динамическую c структуру массива в 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;
}
Возможно, я запутался в том, как размер моего динамического c массива определен и как я должен обращаться с ним в моих функциях. Вот компилируемый пример, чтобы помочь вам понять проблему. Это довольно долго, но большинство функций можно игнорировать, так как они являются служебными функциями и, кажется, работают хорошо. Проблема находится в функции слияния, но я боюсь, что это может быть связано с тем, как я определил мою dynarray структуру. Ps. строка, вызывающая dynarray_merge(param, l , r, size);, прокомментирована, потому что я работаю над проблемами, находящимися в dynarray_mergesort(dynarray *param); Ps2: функции printf, вызываемые внутри dynarray_mergesort(dynarray *param);, используются в качестве отладочной информации.
#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);
}