Что означает оператор AND применительно к указателям в связанном списке?

Я пытаюсь понять код C, написанный для обнаружения и удаления цикла в связанном списке (взято из здесь). Хотя все остальное для меня имеет смысл, я не могу понять, что происходит внутри оператора while. В частности, как ведет себя логическое И применительно к структурам указателей?

while (slow_p && fast_p && fast_p->next) 

Здесь мы использовали подход зайца и черепахи, в котором мы используем два указателя, один быстрый и один медленный.

/* Link list node */
struct Node 
{ 
    int data; 
    struct Node* next; 
}; 

/* Function to remove loop. Used by detectAndRemoveLoop() */
void removeLoop(struct Node *, struct Node *); 

/* This function detects and removes loop in the list 
  If loop was there in the list then it returns 1, 
  otherwise returns 0 */

int detectAndRemoveLoop(struct Node *list) 
{ 
    struct Node  *slow_p = list, *fast_p = list;

while (slow_p && fast_p && fast_p->next) 
{ 
    slow_p = slow_p->next; 
    fast_p  = fast_p->next->next; 

    /* If slow_p and fast_p meet at some point then there 
       is a loop */
    if (slow_p == fast_p) 
    { 
        removeLoop(slow_p, list); 

        /* Return 1 to indicate that loop is found */
        return 1; 
    } 
} 

/* Return 0 to indeciate that ther is no loop*/
return 0; 

}


person MaxFrost    schedule 22.06.2019    source источник
comment
Условие проверяет три указателя на наличие нулей. Он терпит неудачу на первом нулевом значении. Условие не будет продолжать оценку после того, как обнаружит значение null.   -  person user14063792468    schedule 22.06.2019
comment
Но когда внутри связанного списка существует цикл, будет ли какой-либо узел указывать на нуль? Я имею в виду, когда останавливается цикл while. Но спасибо за объяснение условия.   -  person MaxFrost    schedule 22.06.2019


Ответы (1)


У вас есть условие, которое гарантирует, что цикл прерывается и завершается, если любой из трех указателей равен NULL. Нулевой указатель всегда оценивается как логическое значение false в C. См. https://en.wikipedia.org/wiki/Null_pointer#Null_pointer.

Однако с текущей логикой вполне вероятно, что ни один из указателей не будет NULL, если в вашем списке существует цикл, потому что мы обнаруживаем цикл и выходим из него. Указатель fast_p может быть NULL только тогда, когда в вашем списке нет цикла, и вы только что закончили обход всего списка, пытаясь найти его.

введите здесь описание изображения

Последовательность выполнения происходит следующим образом

  1. slow_p будет на узле 2, а fast_p будет на узле 3.
  2. slow_p будет в узле 3, а fast_p будет в узле 5.
  3. slow_p будет в узле 4, а fast_p пройдет циклический узел и снова окажется в узле 3.
  4. slow_p будет в узле 5, а fast_p будет в узле 5.

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

person Inian    schedule 22.06.2019
comment
Спасибо за ваше объяснение. Пожалуйста, простите меня за отсутствие надлежащих основ, но даже когда оба указателя приземляются на один и тот же узел, будут ли они указывать на NULL? Когда вы говорите, что они указывают на NULL? - person MaxFrost; 22.06.2019
comment
@MaxFrost: см. мое обновление, разъясняющее ваш вопрос. - person Inian; 22.06.2019