I'm trying to merge sort an array of structs, I've had many different seg faults but at the moment its happening in the arrayCopy
function:
void arrayCopy(item10array dest[], item10array src[], const int lenght, const int leftShift) {
for (int i = 0; i < lenght; i++) {
structCopy(dest[i], src[leftShift + i]);
}
}
I have changed small things until I pushed the seg fault into the function arrayCopy
, I dont understand what is causing the error.
typedef struct
{
char Nome[50]; //vem do ficheiro ruas.txt
unsigned int int_arr[6];
char char_arr[6];
} Arteria;
typedef struct
{
Arteria arteria;
int cont;
} item10array;
void structCopy(item10array dest, item10array src) {
strcpy(dest.arteria.Nome, src.arteria.Nome);
for (int j = 0; j < 6; j++) {
dest.arteria.int_arr[j] = src.arteria.int_arr[j];
dest.arteria.char_arr[j] = src.arteria.char_arr[j];
}
dest.cont = src.cont;
}
void arrayCopy(item10array dest[], item10array src[], const int lenght, const int leftShift) {
for (int i = 0; i < lenght; i++) {
structCopy(dest[i], src[leftShift + i]);
}
}
void mergeSorted(item10array *array, const int l, const int m, const int r) {
int left_lenght = m - l + 1;
int right_lenght = r - m;
item10array temp_left[left_lenght];
item10array temp_right[right_lenght];
int i, j, k;
arrayCopy(temp_left, array, left_lenght, l);
arrayCopy(temp_right, array, right_lenght, m + 1);
for (i = 0, j = 0, k = l; k <= r; k++) {
if ((i < left_lenght) && (j >= right_lenght || temp_left[i].cont <= temp_right[j].cont)) {
structCopy(array[k], temp_left[i]);
i++;
} else {
structCopy(array[k], temp_right[j]);
j++;
}
}
}
void sortRecursion(item10array *arrray, int l, int r) {
//isto é desnecessario mas dá me paz de alma
if (r <= 1)
return;
if (l < r) {
//encontrar o meio do array
int m = l + (r - l) / 2;
sortRecursion(arrray, l, m);
sortRecursion(arrray, m + 1, r);
mergeSorted(arrray, l, m, r);
}
}
void sortItem10(item10array *rua, int lenght) {
sortRecursion(rua, 0, lenght - 1);
}
void item10letra(Arteria *origin_ptr) {
item10array rua[345] = {{"0", 0, 0, 0}};
for (int i = 0; i < 345; i++) {
rua[i].arteria = origin_ptr[i];
}
char letra;
int cont = 0;
int lenght = sizeof(item10array) * 345;
for (int i = 0; i < 345; i++) {
rua[i].arteria = origin_ptr[i];
}
for (int i = 0; i < 345; i++) {
for (int j = 0; j < 6 && rua[i].arteria.char_arr[j] != 0; j++) {
if (rua[i].arteria.char_arr[j] == letra) {
cont++;
}
}
rua[i].cont = cont;
}
sortItem10(rua, lenght);
}
Some things aren't named in English, that's because I'm also not named in English.
Thanks.
As posted, structCopy
does not do anything useful because the src
and dest
structures are passed by value, so assigning the members of src
to those of dest
only modifies the function argument and has no effect on the structure arrays passed to arrayCopy
.
Structures can be copied simply by assignment. Here is a modified version of arrayCopy
:
void arrayCopy(item10array dest[], const item10array src[],
int length, int leftShift) {
for (int i = 0; i < length; i++) {
dest[i] = src[leftShift + i];
}
}
The problem in your sort program is elsewhere:
the length
computed in sortRecursion
is incorrect: int length = sizeof(item10array) * 345;
is bogus as you multiply the size of the array in bytes by its hardcoded number of elements instead of dividing by the size of an array element:
int length = sizeof(item10array) / sizeof(item10array[0]);
also char letra;
is not initialized to counting the occurrences of the letter in the artery names is meaningless.
note also that using r
as the index of the last element in the slice is also confusing. It is more idiomatic in C to use the index of the element past the end of the slice to avoid error prone +1
/ -1
adjustments.
Here is a modified version of your code:
typedef struct {
char Nome[50]; //vem do ficheiro ruas.txt
unsigned int int_arr[6];
char char_arr[6];
} Arteria;
typedef struct {
Arteria arteria;
int cont;
} item10array;
void arrayCopy(item10array dest[], const item10array src[],
int length, int leftShift) {
for (int i = 0; i < length; i++) {
dest[i] = src[leftShift + i];
}
}
void mergeSorted(item10array *array, int l, int m, int r) {
int left_length = m - l;
int i, j, k;
item10array temp_left[left_length];
// only save the left part, elements in the right part are
// never overwritten before they are copied.
arrayCopy(temp_left, array, left_length, l);
for (i = 0, j = m, k = l; k < r; k++) {
if (i < left_length
&& (j >= r || temp_left[i].cont <= array[j].cont)) {
array[k] = temp_left[i++];
} else {
array[k] = array[j++]);
}
}
}
void sortRecursion(item10array *array, int l, int r) {
if (r - l > 1) {
// encontrar o meio do array
int m = l + (r - l) / 2;
sortRecursion(array, l, m);
sortRecursion(array, m, r);
mergeSorted(array, l, m, r);
}
}
void sortItem10(item10array *rua, int length) {
sortRecursion(rua, 0, length);
}
void item10letra(Arteria *origin_ptr) {
item10array rua[345] = {{"0", 0, 0, 0}};
int length = sizeof(item10array) / sizeof(item10array[0]);
char letra = 'a';
for (int i = 0; i < length; i++) {
int cont = 0;
rua[i].arteria = origin_ptr[i];
for (int j = 0; j < 6 && rua[i].arteria.char_arr[j] != 0; j++) {
if (rua[i].arteria.char_arr[j] == letra) {
cont++;
}
}
rua[i].cont = cont;
}
sortItem10(rua, length);
}