1

Good morning

before the code, i dont want you guys to give me code for me to use, as i would not learn why it would done like that. I want to learn why this code fails and how to properly use memory allocation so im not to fail again in the future.

The problem i've encountered is related to a function in my code whose objective is, given a 2D dynamic array of chars (Matrix) and another dynamic array of words (List), to find all paths on the Matrix were the words on the list reside, and then store those paths in another dynamic array (Paths). My problem is not on how to find those paths, but on how to store them, as all my attempts on an solution have met with memory reallocation errors.

this is the function in question:

notes:

this code finds a path, stores it into temp and then it SHOULD allocate memory to copy temp to path and then repeat. Without the allocation part of the code, and with a few printfs, the code does show all paths correctly. But showing and storing are 2 different things

int ** path - the dyn array for the paths

int ** num_caminhos - the number of paths

char * palavra - the word to currently search for

int ID - the ID of the word, for later reference

void pesquisa(int ** path, int *num_caminhos, char **matriz, int num_colunas, int num_linhas, char * palavra, int l, int c, int li, int ci, int * temp, int d, int ID){
if (matriz[l][c]==palavra[d]){
    if ((l-1)>=0 && palavra[d+1]==matriz[l-1][c]){
        temp[5+d]=1;
        pesquisa(path, num_caminhos, matriz,num_colunas, num_linhas, palavra, l-1, c, li, ci, temp, d+1, ID);}
    if ((l-1)>=0 && (c+1)<num_colunas && palavra[d+1]==matriz[l-1][c+1]){
        temp[5+d]=2;
        pesquisa(path, num_caminhos, matriz,num_colunas, num_linhas, palavra, l-1, c+1, li, ci, temp, d+1, ID);}
    if (((c+1)<num_colunas) && (palavra[d+1]==matriz[l][c+1])){
        temp[5+d]=3;
        pesquisa(path, num_caminhos, matriz,num_colunas, num_linhas, palavra, l, c+1, li, ci, temp, d+1, ID);}
    if ((l+1)<num_linhas && (c+1)<num_colunas && palavra[d+1]==matriz[l+1][c+1]){
        temp[5+d]=4;
        pesquisa(path, num_caminhos, matriz,num_colunas, num_linhas, palavra, l+1, c+1, li, ci, temp, d+1, ID);}
    if ((l+1)<num_linhas && palavra[d+1]==matriz[l+1][c]){
        temp[5+d]=5;
        pesquisa(path, num_caminhos, matriz,num_colunas, num_linhas, palavra, l+1, c, li, ci, temp, d+1, ID);}
    if ((l+1)<num_linhas && (c-1)>=0 && palavra[d+1]==matriz[l+1][c-1]){
        temp[5+d]=6;    
        pesquisa(path, num_caminhos, matriz,num_colunas, num_linhas, palavra, l+1, c-1, li, ci, temp, d+1, ID);}
    if ((c-1)>=0  && palavra[d+1]==matriz[l][c-1]){
        temp[5+d]=7;
        pesquisa(path, num_caminhos, matriz,num_colunas, num_linhas, palavra, l, c-1, li, ci, temp, d+1, ID);}
    if ((l-1)>=0 && (c-1)>=0 && palavra[d+1]==matriz[l-1][c-1]){
        temp[5+d]=8;
        pesquisa(path, num_caminhos, matriz,num_colunas, num_linhas, palavra, l-1, c-1, li, ci, temp, d+1, ID);}
}
if ((d==strlen(palavra)-1) && (palavra[0]==matriz[li][ci])){
    path=realloc(path, ((*num_caminhos)+1)*sizeof(int *));
    path[*num_caminhos]=malloc((strlen(palavra)+5)*sizeof(int));
    temp[0]=ID;
    temp[1]=li;
    temp[2]=ci;
    temp[3]=l;
    temp[4]=c;
    for (int i=0; i<5+d; i++){
        path[*num_caminhos][i]=temp[i];
    }
    *num_caminhos=*num_caminhos+1;
    return;
}

}

sorry if the code shows a bit too many "amateur" mistakes :P. I tend to correct them as i learn more. Just a last detail tough, i am sadly forced to use dyn memory allocation as its part of the objective of this code.

Rodrigo Sousa Couto Soares
  • 11
  • 3
  • When you're reallocating dynamically-allocated arrays, how the array was originally allocated is important. Note also that a one-dimensional array of pointers to a bunch of individually allocated one-dimensional arrays isn't a two-dimensional array. See https://stackoverflow.com/questions/42094465/correctly-allocating-multi-dimensional-arrays for **true** two-dimensional arrays. – Andrew Henle Nov 27 '18 at 12:50
  • I think the main issue here is how to replace the recursion with a readable loop, then avoid code repetition. Once that part is cleaned up you, you can worry about dynamic allocation. – Lundin Nov 27 '18 at 12:57
  • @AndrewHenle your sugestion was very constructive, however i am to blame here, as what i actually use is an array of pointer to a bunch of individual arrays OF diferent sizes, wich sadly would not work well on a true Two-dimensional array as you sugested. your link did help however, in clarifying some matters. – Rodrigo Sousa Couto Soares Nov 27 '18 at 17:09
  • @Lundin i dont see how one would turn this recursion into a loop, as this is best compared to a labyrinth path search. When it finds a solution, returns it and then it only goes part of the way back so to continue searching – Rodrigo Sousa Couto Soares Nov 27 '18 at 17:11

0 Answers0