Рекурсивная функция передает указатель NULL, когда аргумент не равен NULL - PullRequest
Новая
       12

Рекурсивная функция передает указатель NULL, когда аргумент не равен NULL

1 голос
/ 06 ноября 2011

Следующая программа предназначена для хранения слов в алфавитном порядке в дереве двоичного поиска с использованием функции strcmp.Проблема, подробно описанная в программе, заключается в том, что при рекурсивном вызове функции в последней части функции не передается указатель. 

typedef struct NodT{
   char word[30];
   struct NodT *left, *right;
} NOD;

void reset_field(NOD *nod){
    int i;
    for(i=0; i<30; i++){
        nod->word[i]='\0';
    }
}

void enter_recursively(NOD *nod, char *word){
    if(nod==NULL){
        nod= (NOD *) malloc(sizeof(NOD));
       nod->left=NULL;
       nod->right=NULL;
       reset_field(nod);
       strcpy(nod->word, word);
       return;
   }

   if(nod->word[0]=='\0'){
       strcpy(nod->word, word);
       return;
   }

   if(strcmp(nod->word, word)==0) return;

   if(strcmp(nod->word, word)<0){
       enter_recursively(nod->right, word);//the problem seems to be here
       printf("right\n");
   }
   else{
       enter_recursively(nod->left, word);//...and here
       printf("left\n");
   }
   //the NULL pointer is being sent over, which is peculiar
}

Дело в том, что, когда я передаю указатели (оставленныесправа от структуры к рекурсивной функции в условиях if-else она принимает значение NULL с другой стороны, чего не должно быть, поскольку они не равны NULL после выделения первого слова в корне и второго ввправо или влево в зависимости от strcmp, расположение при использовании malloc для создания нового пространства для хранения слова.

ОБНОВЛЕНИЕ: новый скрипт с использованием двойных указателей: 

typedef struct NodT{
    int key;
    char word[30];
    struct NodT *left, *right;
} NOD;

void enter_recursively(NOD **nod, char *word){
        printf("N: %p\n", nod);
    printf("NL: %p\n", (**nod).left);
    printf("NR: %p\n", (**nod).right);
        if(nod==NULL){
            nod=malloc(sizeof(NOD));        
            (**nod).left=NULL;
            (**nod).right=NULL;
            strcpy((**nod).word, word);
            return;
        }
        if((**nod).word[0]=='\0'){
            strcpy((**nod).word, word);
            return;
        }

    if(strcmp((**nod).word, word)==0) return;

        if(strcmp((**nod).word, word)<0){
            enter_recursively((**nod).right, word);
        }
        else{
            enter_recursively((**nod).left, word);
        }

Я получаю сегментациювина, и я не знаю почему.

Ответы [ 2 ]

3 голосов
/ 06 ноября 2011

Проблема в том, что * nod изменен, но не возвращен: Измените 

void enter_recursively(NOD *nod, char *word)

на 

void enter_recursively(NOD **nod, char *word)

, чтобы вернуть допустимый указатель.Внутри функции используйте * nod вместо nod, это правильный путь.

Когда вы передаете в функцию только NOD *, выделенная память не сохраняется должным образом.Это как если вы хотите изменить значение int внутри функции, вы передаете ее адрес вместо значения.

Кроме того, всегда проверяйте нулевые указатели перед их использованием.Вы можете получить ядро.

Окончательный код выглядит так: 

void enter_recursively(NOD **nod, char *word){
    if (*nod==NULL){
        *nod=malloc(sizeof(NOD));        
        (*nod)->left=NULL;
        (*nod)->right=NULL;
        strcpy((*nod)->word, word);
        return;
    }
    if((*nod)->word[0]=='\0'){
        strcpy((*nod)->word, word);
        return;
    }

    if(strcmp((*nod)->word, word)==0) return;

    if(strcmp((*nod)->word, word)<0){
        enter_recursively(&(*nod)->right, word);
    }
    else{
        enter_recursively(&(*nod)->left, word);
    }
0 голосов
/ 06 ноября 2011

Ваша функция enter_recursively () выделяет узел, может быть, даже назначает ему, но не имеет возможности передать его обратно вызывающей стороне.Найдите способ вернуть что-то полезное для вызывающей стороны.

ОБНОВЛЕНИЕ: для полноты: это другой способ передачи информации от ребенка обратно его родителю: (через возвращаемое значение) 

NOD * enter_recursively(NOD *ptr, char *word){
    int rc;

    if (ptr==NULL){
       ptr = malloc(sizeof *ptr);
       ptr->left = NULL;
       ptr->right = NULL;
       strcpy(ptr->word, word);
       return ptr;
   }

   rc = strcmp(ptr->word, word);
   if (rc==0) return ptr;

   if (rc < 0){
       ptr->right = enter_recursively(ptr->right, word);
       fprintf(stderr, "right\n");
   }
   else {
       ptr->left = enter_recursively(ptr->left, word);
       fprintf(stderr, "left\n");
   }
   return ptr; /* not reached */
}
...