Понимание двойного указателя в двусвязном списке в C

Question

Завтра у меня экзамен, и я пытался понять этот пример двусвязного списка, который преподаватель разместил на сайте класса, но мне трудно понять его немного ...

Вот код:

#include <stdio.h>
#include <stdlib.h>

typedef struct dl {
    int key;
    float value;
    struct dl *next;
    struct dl *prev;
} DL;

DL *insert(int c, float f, DL *l) {
    DL *new = (DL*) malloc(sizeof(DL));
    if (new == NULL) exit(-1);
    new->key=c; new->value=f; 
    if (l==NULL) {
        new->next=NULL; new->prev=NULL;
    }
    else if (l->key < c) {
        while((l->next != NULL) && (l->next->key < c)) { l=l->next; }
        new->next=l->next; l->next=new; new->prev=l;
        if (new->next != NULL) {
            new->next->prev=new;
        }
    }
    else {
        while((l->prev != NULL) && (l->prev->key > c)) { l=l->prev; }
        new->prev=l->prev; l->prev=new; new->next=l;
        if(new->prev != NULL) {
            new->prev->next=new;
        }
    }
    return new;
}

int search(int c, float *f, DL **lptr) {
    if (*lptr == NULL) return 0;
    if (c < (*lptr)->key) {
        while(((*lptr)->prev!=NULL)&&((*lptr)->prev->key >= c)) {
            (*lptr)=(*lptr)->prev;
        }
    }
    else if (c > (*lptr)->key) {
                while(((*lptr)->next!=NULL)&&((*lptr)->next->key <= c)) {
                        (*lptr)=(*lptr)->next;
                }
    }
    if ((*lptr)->key == c) {
        *f = (*lptr)->value;
        return 1;
    }
    return 0;
}

void printList(DL *l) {
    if (l == NULL) return;
    while (l->prev != NULL) { l=l->prev; };
    while(l != NULL) {
        printf("%d,%f\n",l->key,l->value);
        l=l->next;
    }
}

int main(void) {
    DL *list=NULL;
    float f;
    list=insert(3,5.6,list); list=insert(4,5.3,list);
    list=insert(7,3.6,list); list=insert(1,7.7,list);
    list=insert(9,2.3,list); list=insert(0,9.0,list);
    printList(list);
    if (search(3,&f,&list)) {
        printf("Found %f.\n",f);
    }
    else {
        printf("Not found.\n");
    }
    printList(list);
    return 0;
}

Вот вывод:

0,9.000000
1,7.700000
3,5.600000
4,5.300000
7,3.600000
9,2.300000
Found 5.600000.
0,9.000000
1,7.700000
3,5.600000
4,5.300000
7,3.600000
9,2.300000

Чего я не понимаю, так это функции поиска. Передаваемый список является указателем на DL, верно? И мы ищем число, для которого мы продолжаем делать (* lptr) = (* lptr) -> next (или prev), чтобы перебрать весь список. Чего я не понимаю, так это того, что второй вызов printList () печатает весь список ... После того, как был выполнен вызов search (), разве «список» не должен иметь элементы только после того, который мы искали? Указатель был изменен, почему, когда мы возвращаемся из search (), указатель восстанавливается до первого элемента и выводится весь список?

Это то, что я не получаю, если я изменю функцию search () и добавлю (* lptr) = NULL в первой строке, второй вызов printList () ничего не напечатает потому что указатель был изменен, теперь он равен NULL, печатать нечего. Почему (* lptr) = (* lptr) -> next не имеет аналогичного эффекта? Указатель также изменяется на следующий, не должен ли второй вызов printList () распечатать только оставшиеся элементы в списке?

EDIT:
Каждый ответ кажется правильным, и я собираюсь отсортировать его по «старому» и принять «самый быстрый», не сердитесь, мне нужно иметь некоторые критерии. Я мог бы продолжить и посмотреть, какие ответы предоставили лучшее понимание проблемы, но это не имеет значения, потому что я уже знаю все, что было сказано. Я был достаточно глуп, чтобы даже не смотреть на функцию printList (), и предполагал, что все в порядке, я также предполагал, что ошибка была где-то в функции search (). Но я знал, что был прав, я знал, что указатель меняется, и список не может распечатать все, но теперь я понимаю, почему ...

Answer 1

printList перематывает список перед печатью.

while (l->prev != NULL) { l=l->prev; };

Если бы у него не было вышеуказанной строки, он просто напечатал бы вещи после найденного элемента.

Answer 2

Эта строка возвращает указатель назад:

while (l->prev != NULL) { l=l->prev; };

И те делают печать:

while(l != NULL) {
    printf("%d,%f\n",l->key,l->value);
    l=l->next;
}

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

Answer 3

Насколько я могу прочитать (и, как заметил rmeador, это довольно ужасный код), вызов search действительно изменяет указатель list для указания на найденный элемент.

Хитрость заключается в функции printList. Первое, что он делает (кроме проверки на NULL), это:

while (l->prev != NULL) { l=l->prev; };

Таким образом, он в основном следует за указателем prev назад к началу списка, поэтому фактическая печать начинается с начала списка, даже если передается указатель на его середину или конец.

Answer 4

Он возвращает указатель внутри отпечатка:

while (l->prev != NULL) { l=l->prev; };

Помните, что список связан дважды. Поиск не меняет список, только то, на какую часть его «списка» в данный момент указывает.

Answer 5

Чего я не понимаю, так почему второй вызов printList () печатает весь список ... После поиска () вызов был сделан, не должен только "список" есть элементы после того, как мы искал? Указатель был изменен, как получится, когда мы вернемся из поиска () указатель восстанавливается до первого элемент и весь список напечатан?

На самом деле у вас есть не указатель на список, а указатель на элемент в списке. Первое, что делает функция printList, это делает цикл по предыдущим ссылкам, чтобы найти первый элемент списка.

Answer 6

В функции printList () вы возвращаетесь из найденного элемента, используя l = l->prev. Затем вы печатаете все содержимое.