时间戳

首页 > 解决方案 > 在链表中查找或创建元素，而不丢失头部

c - 在链表中查找或创建元素，而不丢失头部

问题描述

我需要使用包含数据元素、id 元素和函数中的下一个元素的结构的静态链表。我的函数是用一个 id 调用的，如果链表中有一个具有这个 id 的元素，我必须返回它以供以后使用。如果没有，我必须在列表末尾创建它并返回它。这是使用名为 lstforc 的函数执行的

问题是，当我将链表提供给具有新 ID 的 lstforc 函数时，它似乎没有将元素附加到链表的末尾。

我自己尝试了几种解决方案，但要么元素没有添加到列表的末尾，要么元素被添加，但我失去了链表的头部。

这是我的链表结构：

typedef struct          s_list_fd
{
    int                 fd;
    char                *mem;
    struct s_list_fd    *next;
}                       t_list_fd;

这是程序中多次调用的函数，在这里我初始化了我的静态链表：

int         get_next_line(int id)
{
    static t_list_fd    *mfd_s = NULL;
    t_list_fd           *mfd_c;

    print_list(mfd_s);
    if (!(mfd_c = ft_lstforc_fd(&mfd_s, id)))
        return (-1);
        //I have to use mfd_c later in the program
    return (0);
}

这是我的函数，要么返回好的元素，要么创建一个具有正确 id 的新元素（不要在末尾添加元素）：

t_list_fd   *ft_lstforc_fd(t_list_fd **lst, int id)
{
    t_list_fd *tmp;

    tmp = *lst;
    while (tmp)
    {
        if (tmp->id == id)
            return (tmp);
        tmp = (*lst)->next;
    }
    if (!(tmp = (t_list_fd *)malloc(sizeof(t_list_fd))))
        return (NULL);
    tmp->id = id;
    tmp->mem = NULL;
    tmp->next = NULL;
    return (tmp);
}

这是相同的功能（在末尾添加元素，但丢失了链表头）：

t_list_fd   *ft_lstforc_fd(t_list_fd **lst, int id)
{
    while (*lst)
    {
        if ((*lst)->id == id)
            return (*lst);
        *lst = (*lst)->next;
    }
    if (!(*lst = (t_list_fd *)malloc(sizeof(t_list_fd))))
        return (NULL);
    (*lst)->id = id;
    (*lst)->mem = NULL;
    (*lst)->next = NULL;
    return (*lst);
}

标签： clinked-list

解决方案

您的第二个函数几乎很好，但是您没有利用lst指向节点指针的指针这一事实。您只能访问它，*lst并且*lst始终mfd_s在get_next_line. 这就是为什么你认为你失去了头：你将新节点附加到原始头上，从而失去了所有其他节点。

当您遍历列表时，您会做两件事：检查现有 id 并尝试找到列表的末尾，即您要在其中附加新节点的位置。id 已正确检查。为了找到列表的末尾，您必须更新lst，而不是*lst。改变

    *lst = (*lst)->next;

到

    lst = &(*lst)->next;

那不一样吗？不，考虑一个空列表。现在你想追加一个节点。首先，lst == &mfd_s分配给*lst将更新列表头。附加另一个具有不同 ID 的节点。您从 开始lst == &mfd_s，但lst在 while 循环中更新，因此它现在指向第一个节点的下一个指针。分配给*lst将更新下一个指针，而不是头部。

这是一种有用的技术，因为额外的间接级别意味着头节点不是特殊情况。（这就是修复第一个函数所必须做的：使添加第一个节点成为特殊情况，在其中更新*lst，然后处理另一种情况，但保留一个prev指针，以便在用尽列表后，您知道最后一个vistied 节点是，next你应该更新它。）

推荐阅读