在链表中搜索事件

Question

我正在尝试搜索可能包含事件 (int) 的单链表。我需要跟踪正在处理的当前节点和它之前的两个节点（需要处理）。

代码：

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

typedef struct node {
    int eventnum;
    int eventfq;
    struct node *next;
} node;

void insertevent(node **list, int event);
void srchevent(node *list, int xevent, node **current, node **previous, node **pprevious);

int main() {
    node *list = NULL;
    int i = 0;
    for(i = 0; i < 10; i++) {
        insertevent(&list, i);
    }
}

void insertevent(node **list, int event) {
    node *newnode = (node *)malloc(sizeof(node));
    node *current, *previous, *pprevious;
    srchevent(*list, event, &current, &previous, &pprevious);
}

void srchevent(node *list, int xevent, node **current, node **previous, node **pprevious) {
    *pprevious = *previous = NULL;
    *current = list;

    printf("current:\naddr:%d\nval:%d\n\n", &current, current);
    printf("previous:\naddr:%d\nval:%d\n\n", &previous, previous);
    printf("pprevious:\naddr:%d\nval:%d\n\n", &pprevious, pprevious);
    (*previous)->next = current;

    /* nothing past here executes */
    printf("current:\naddr:%d\nval:%d\n\n", &current, current);
    printf("previous:\naddr:%d\nval:%d\n\n", &previous, previous);
    printf("pprevious:\naddr:%d\nval:%d\n\n", &pprevious, pprevious);
    (*pprevious)->next = *current;
}

输出：

adding 0
current:
addr:6422216
val:6422248

previous:
addr:6422220
val:6422244

pprevious:
addr:6422224
val:6422240

此代码应将 10 个节点插入到列表中（插入功能尚未实现）。但是，执行在第 34 行 ((*previous)->next = *current;) 处结束。我不明白为什么分配前一个的下一个值会导致程序结束。

注意：srchevent(...) 的结构和参数无法更改。

Answer 1

在函数中使用双指针可能会很慢并且会出现问题。最好使用单指针并在末尾设置 return 值。

因为您将顶部的所有三个 return 值都设置为 NULL（例如 *previous = NULL），以下将出现段错误：

(*previous)->next = *current;

换句话说，您正在尝试取消引用空指针。 pprevious 也是如此。如果您使用 -g 选项编译，并使用 gdb，它会发现错误并给您一条消息。

注意next每个节点已经在链表中设置好了，所以你应该不需要需要set/change它。

此外，逻辑可以简化[这可能是问题的一部分]。

这是重构后的版本：

void
srchevent(node *list, int xevent,
    node **current, node **previous, node **pprevious)
{
    node *cur;
    node *prev = NULL;
    node *pprev = NULL;

    for (cur = list;  cur != NULL;  cur = cur->next) {
        if (cur->eventnum == xevent)
            break;
        pprev = prev;
        prev = cur;
    }

    *current = cur;
    *previous = prev;
    *pprevious = pprev;
}

在链表中搜索事件

Searching for Event in Linked List

c

pointers

singly-linked-list