在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） - ＆gt; next （或prev）来遍历整个列表。我不明白的是为什么第二次调用printList（）会打印整个列表......在进行search（）调用之后，列表应该只有我们要查找的元素之后的元素，对吗？指针已更改，但是当我们从search（）返回时，指针恢复到第一个元素，并且打印了整个列表？

这就是我不明白的地方，因为如果我更改search（）函数并在第一行添加（* lptr）= NULL，则第二次调用printList（）将不打印任何内容，因为指针已更改，现在为空，没有什么可打印的东西。为什么（* lptr）=（* lptr） - ＆gt; next没有类似的效果呢？指针也被更改为下一个，难道第二个printList（）调用不应该只打印列表中剩余的元素吗？

编辑： 每个答案都似乎是正确的，我将按“最古老”的顺序排序并接受“最快”的答案，请不要生气，我需要一些标准。我可以继续查看哪个答案对该问题提供了更好的见解，但这是无关紧要的，因为我已经知道所有被说过的东西。我只是太愚蠢了，没有看printList（）函数并且认为它没问题，我还假定错误出现在search（）函数中。但我知道我是正确的，我知道指针正在更改，列表无法打印所有内容，但是我现在明白了......

- rfgamaral

---

你的讲师写了这么丑陋的代码，应该感到羞耻。这不是教授学生最佳实践的方式...我几乎看不懂那个混乱的代码。 - rmeador

@rmeador 我同意，尽管这是一个很好的例子，展示了你可能在实际开发中遇到的烦人代码。 - BaroqueBobcat

我怀疑这不是出于你提到的原因而这样做的，bobcat。 - Vinko Vrsalovic

我从未说过是教练编写了代码，我只是说他把它放在了网站上。我有一种感觉这不是他的作品，但这并不重要... - rfgamaral

Answer 1

printList 函数在打印列表前会将其倒回。

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

如果没有上面的那行代码，它只会打印找到元素后面的内容。

- BaroqueBobcat

Answer 2

这行代码返回指针：

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

这些是打印机:

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

有一个更好的方法可以做到这一点，只需添加一个或两个额外的字段，它们将始终指向列表的开头和结尾。

- Artem Barger

---

如果您添加开头和结尾指针，那么您将失去使用链表的大部分优点。如果您添加或删除第一个或最后一个元素，则必须遍历整个列表并更新指针。 - Guffa

让我问一下，你为什么要这样做？你添加这些指针是为了不这样做。 - Artem Barger

Answer 3

据我所读（就像rmeador评论的那样，这是相当糟糕的代码），search调用确实修改了list指针，使其指向找到的元素。

关键在于printList函数。它除了检查是否为NULL之外，第一件事情就是：

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

所以它基本上是沿着prev指针返回到列表的开头，因此即使传递了指向列表中间或末尾的指针，实际打印也始于列表的开头。

- jalf

Answer 4

他在打印函数中回溯指针：

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

请记住，该列表是双向链接的。搜索不会改变列表，只会改变“list”当前指向的部分。

- Daniel C. Sobral

Answer 5

在printList()函数中，您正在使用l = l->prev从找到的元素返回。然后您打印所有内容。

- Naveen

Answer 6

我不理解的是，为什么第二次调用printList()会打印整个列表...在执行search()调用之后，"list"只应包含我们查找过的元素之后的元素，指针已经更改了，为什么当我们从search()返回时，指针恢复到第一个元素并打印整个列表呢？

你所拥有的实际上不是指向列表的指针，而是指向列表中元素的指针。printList函数首先要做的是通过prev引用回循环找到列表的第一个元素。

- Guffa