Понимание функции, вызываемой по ссылке в списках - PullRequest
Новая
       16

Понимание функции, вызываемой по ссылке в списках

0 голосов
/ 27 января 2019

Я хотел бы знать, почему приведенный ниже код работает хорошо.

Он должен рекурсивно, учитывая список, ставить -1 перед четными числами.

Ex,Вход: 4-> 7-> 1-> 10-> NULL Выход: -1-> 10-> 1-> 7 -> - 1-> 4-> NULL

Я не понимаю, какфункция, будучи рекурсивной, может отслеживать возможную * голову, которая изменяется каждый раз, из-за того, что функция вызывала себя по ссылке.

В конце концов, я не понимаю, каквывод может быть правильным, учитывая те (для меня) неправильное представление о том, как работает рекурсивная функция по ссылке.

Вот код со следующими объявлениями: 

typedef struct El {
    int info;
    struct El *next;}ElementoLista;
typedef ElementoLista *ListaDiElementi;

void inserisci(ListaDiElementi *head) { 
    if((*head) != NULL && ((*head)->info)%2 == 0) {
        inserisci(&(*head)->next);
        ListaDiElementi aux = malloc(sizeof(ElementoLista));
        aux->info = -1;
        aux->next = *head;
        *head = aux;
    } else {    
        if((*head) != NULL) {               
            inserisci(&(*head)->next); 
        }  
    }  
}

1 Ответ

0 голосов
/ 27 января 2019

Я думаю, что ваши проблемы с кодом связаны с тем, что код написан «немного плохо», то есть менее ясно, чем могло бы быть.Я вижу три проблемы.

1) «typedef of pointer» затрудняет понимание того, какие типы задействованы.Особенно, когда неясно, что конкретный тип является указателем.Такое имя, как ListaDiElementi, не дает (по крайней мере, мне) понять, что это указатель.Лучшее имя может быть ElementoLista_ptr, но в целом лучше избегать указателя typedef.

2) Аргумент функции называется head.Это сбивает с толку, потому что мы обычно думаем о head как указатель на первый элемент списка.Но это не то, что здесь происходит.Аргумент действительно является двойным указателем, и, кроме того, он не указывает на первый элемент.Он указывает на next указателей.

3) Конструкция if скрывает логику программы.

Итак, давайте перепишем код, чтобы избавиться от вышеперечисленного, сохраняя при этом ту же функциональность: 

typedef struct El {
    int info;
    struct El *next;
} ElementoLista;

void inserisci(ElementoLista **pNext) { 
    if ((*pNext) == NULL) return;

    inserisci(&(*pNext)->next);

    if(((*pNext)->info)%2 == 0) {
        ElementoLista* aux = malloc(sizeof(ElementoLista));
        aux->info = -1;
        aux->next = *pNext;
        *pNext = aux;
    }  
}

С этим кодом легче понять, что код продолжает вызывать его саморекурсивно, пока не достигнет конца.На обратном пути, то есть, когда функция вызывает return, код проверяет, нужно ли вставлять узел «-1».

Тот же код с некоторыми комментариями для объяснения: 

typedef struct El {
    int info;
    struct El *next;} ElementoLista;

// pNext is a pointer to the "next pointer" of the previous node
// Consequently (*pNext) is a pointer to the current node
void inserisci(ElementoLista **pNext) { 
    // Return if we have reached the end of the list
    if ((*pNext) == NULL) return;

    // Keep calling until the end is reached
    inserisci(&(*pNext)->next);

    // On the "way back" (i.e. as the recursive calls return) check
    // if we need to insert a "-1" node
    if(((*pNext)->info)%2 == 0) {
        // We need a new node
        ElementoLista* aux = malloc(sizeof(ElementoLista));
        aux->info = -1;

        // Make the new node point to current node
        aux->next = *pNext;

        // Update the next pointer to point to the new node
        *pNext = aux;
    }  
}

Когда вы понимаете эту упрощенную версию кода, вы также должны понимать оригинальную версию.

...