Понимание двойного указателя в двусвязном списке в 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() был создан, не должен ли «список» иметь только элементы после того, который мы искали? Указатель был изменен, как получилось, когда мы возвращаемся из поиска(), указатель восстанавливается в первый элемент, и весь список печатается?

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

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

Answer 1

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

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

и те, сделать печать:

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

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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

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

Answer 6

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

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

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

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