c - C中的链表——搜索方法

Question

与上次一样，假设我们有双向链表的节点

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

typedef struct Node {
    int value;
    struct Node* next;
    struct Node* prev;
} Node;

typedef struct LinkedList {
    Node *first;
    Node *last;
} LinkedList;

void initList(LinkedList* l) {
    l->first = NULL;
    l->last = NULL;
}

我的任务是编写搜索方法，该方法应该找到具有给定值的节点

Node* search(LinkedList *list, int value) { ... }

好吧，我的尝试如下

Node* search(LinkedList *list, int value) {

    Node *node = malloc(sizeof(Node));
    if (node == NULL)
        return NULL;

    node->value = value;
    node->prev = NULL;
    node->next = list->first;

    while((node->value != value) && (node->next != NULL)){
        node->prev = node->next;
        node->next = (node->next)->next;
    }

    return node;
}

根据实现测试(这不是我的工作:-)

void test_search_exist() {
    printf("Test 3: ");

    LinkedList l;
    initList(&l);

    Node n1, n2;
    n1.value = 1;
    n1.next = &n2;
    n1.prev = NULL;
    n2.value = 2;
    n2.next = NULL;
    n2.prev = &n1;
    l.first = &n1;
    l.last = &n2;

    Node *i = search(&l, 2);

    if (i == &n2) {
        printf("OK\n");
    }else{
        printf("FAIL\n");
    }
}

void test_search_not_exist(){
    printf("Test 4: ");

    LinkedList l;
    initList(&l);

    Node n1, n2;
    n1.value = 1;
    n1.next = &n2;
    n1.prev = NULL;
    n2.value = 2;
    n2.next = NULL;
    n2.prev = &n1;
    l.first = &n1;
    l.last = &n2;

    Node *i = search(&l, 3);

    if (i == NULL) {
        printf("OK\n");
    }else{
        printf("FAIL\n");
    }
}

我的代码因现有或不存在的节点而中断。那么是否有任何逻辑错误或其他什么？

Answer 1

首先:不要在搜索中分配。数据成员已经存在，因为您之前创建了它们。 第二:遍历列表并检查每个节点的值。

Node* search(LinkedList *list, int value) 
{
    Node *node = list->first;
    Node *found = NULL;

    while(node != NULL)
    {
        if(node->value == value)
        {
            found = node;
            break;
        }

        node = node->next;
    }

    return found;
}

更具体地说明您所犯的错误:

您分配了一个节点，然后用第一个节点的指针填充它，但使用您要搜索的值。然后，您开始循环列表，条件是当 node->value 等于您要搜索的值时停止。由于节点->值是用您正在搜索的值初始化的，因此这种比较将始终为假(因为它是相同的)，循环将终止并且您会得到一个错误的结果。

除此之外，您的原始代码会导致内存泄漏，因为您分配了一个新节点，但没有释放它。