3

我明天要考试，我试图理解教师在课堂网站上放置的这个双向链表示例，但我很难理解它......

这是代码：

#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() 调用不应该只打印列表中的剩余元素吗？

编辑：
每个答案似乎都是正确的，我将按“最旧”对其进行排序并接受“最快”的答案，不要生气，我需要一些标准。我可以继续看看哪个答案可以更好地了解这个问题，但这无关紧要，因为我已经知道所说的一切。我只是愚蠢到甚至不看 printList() 函数并认为它没问题，我还认为错误出现在 search() 函数的某个地方。但我知道我是对的，我知道指针正在改变并且列表无法打印所有内容，但我现在明白为什么......

4

6 回答 6

5

printList在打印之前倒回列表。

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

如果它没有上面的行，它只会打印找到的元素之后的东西。

于 2009-07-16T15:29:22.983 回答
4

此行返回指针：

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

那些做印刷的：

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

并且有更好的方法来做到这一点，只需添加额外的字段或什至两个始终指向列表开头和结尾的字段。

于 2009-07-16T15:29:16.230 回答
2

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

诀窍是 printList 函数。它做的第一件事（除了检查 NULL）是这样的：

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

所以它基本上跟随prev指针回到列表的开头，所以实际的打印从列表的开头开始，即使它传递了一个指向它中间或结尾的指针。

于 2009-07-16T15:37:54.120 回答
1

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

于 2009-07-16T15:30:46.040 回答
1

我不明白为什么第二次调用 printList() 会打印整个列表...在进行了 search() 调用之后，“列表”不应该只有我们寻找的元素之后的元素吗？指针被改变了，为什么当我们从 search() 返回时指针恢复到第一个元素并打印整个列表？

您所拥有的实际上并不是指向列表的指针，而是指向列表中元素的指针。printList 函数执行的第一件事是循环返回 prev 引用以查找列表的第一个元素。

于 2009-07-16T15:30:49.457 回答
1

他回溯打印内的指针：

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

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

于 2009-07-16T15:31:27.130 回答