添加到链表C的后面

Question

我试图创建一个函数，它采用一个结构体，然后将该结构体添加到链表的后面。我已经知道怎么在前面加，但是我不知道怎么在后面加。

这是我添加到前面的函数:

MusicRec * addToFront(MusicRec * theList, MusicRec * toBeAdded)
{
toBeAdded->next = theList;
theList = toBeAdded;
return(theList);
}

我假设添加到列表的后面与添加到前面非常相似，我只是似乎无法获得逻辑

Answer 1

您需要首先遍历列表到末尾，然后添加新的链接，如下所示:

MusicRec *addToBack(MusicRec *theList, MusicRec *toBeAdded)
{
    MusicRec *ptr = theList;
    if (!ptr) return toBeAdded;
    while (ptr->next)
        ptr = ptr->next;
    ptr->next = toBeAdded;
    return theList;
}

Answer 2

一些递归方法:

幼稚，O(n)堆栈内存:

node *add_tail(node *list, node *added)
{
   if (list == NULL)
     return added;
   list->next = add_tail(list->next, added);
   return list;
}

包装器加尾部递归函数(可优化为循环):

void add_tail_rec(node **list, node *add)
{
   if (*list == NULL)
     *list = add;
   else
     add_tail_rec(&(*list)->next, add);
}
node *add_tail(node *list, node *add)
{
   add_tail_rec(&list, add);
   return list;
}

用假头节点代替指针对指针:

void add_tail_rec(node *list, node *add)
{
   if (list->next == NULL)
     list->next = add;
   else
     add_tail_rec(list->next, add);
}
node *add_tail(node *list, node *add)
{
   node fake;
   fake.next = list;
   add_tail_rec(&fake, add);
   return fake.next;
}

没有假头节点或指针到指针，但空测试的副本提升到包装器:

void add_tail_rec(node *list, node *add)
{
   if (list->next == NULL)
     list->next = add;
   else
     add_tail_rec(list->next, add);
}
node *add_tail(node *list, node *add)
{
   if (list == NULL)
      return add;
   add_tail_rec(list, add);
   return list;
}

在跟踪插入位置的递归函数中使用额外的上下文参数。使用这个技巧，递归部分返回一个值:该值始终只是list !包装器可以使用三元表达式返回add或list(添加了项)。

node *add_tail_rec(node *list, node *add, node *where)
{
   return where->next == NULL 
          ? (where->next = add, list) 
          : add_tail_rec(list, add, where->next);
}
node *add_tail(node *list, node *add)
{
   return list == NULL ? add : add_tail_rec(list, add, list);
}