为什么在链表中插入节点后返回指针?

Question

我不明白为什么我们必须在一个节点被添加到链表后返回指向头节点的指针。

struct node *append(int v) {
    struct node *ptr;
    struct node *t;
    ptr=head;
    while (ptr->next != tail) ptr = ptr->next;
    t=(struct node *) malloc(sizeof *t);
    t->value=v;
    t->next = tail;
    ptr->next = t;
    return ptr; // why return ptr?
}

Answer 1

这取决于您的问题的上下文。通常在链表问题中，你必须返回列表的头，这样你就可以保持数据结构的一致性，但我从你的代码中推断，头是一个全局变量。

除非调用该函数的代码需要知道创建的新节点的位置，否则不需要返回该节点，因为head是一个全局变量(如果我的假设是正确的)。

除此之外，我建议修改你的函数，因为我看到你在这里缺少一些情况(如果列表是空的，你必须改变头，例如?)

Answer 2

首先函数无效。当列表为空并添加第一个元素时，head可以等于NULL。因此，使用函数码中与ptr->next对应的表达式head->next会导致内存访问冲突。

我认为把NULL命名为tail也不是个好主意。我会明确地使用NULL。否则代码会使读者感到困惑。

然而，函数可以像下面这样

struct node * append( int v ) 
{
    struct node *t = ( struct node * )malloc( sizeof( *t ) );
    t->value = v;
    t->next  = tail;
    if ( head == tail )
    {
        head = t;
    }
    else
    {
        struct node *current = head;
        while ( current->next != tail ) current = current->next;
        current->next = t;
    }
    return t;
}

至于你的问题，那么我也不明白为什么函数返回ptr而不是t。它应该返回t。在这种情况下，函数将更正确和有效，因为当第一个元素被附加到空列表时，它将返回头部，当下一个非第一个值被附加到列表时，头部将是某个节点(不一定是头部本身)，while循环没有迭代，因为第一个表达式ptr->next将等于NULL。

函数应该返回最后一个附加的节点，正如我所展示的实现。

我确信这只是函数设计中的一个错误:)

如果不在函数中使用全局变量head，而是将其声明为函数参数，那么这个缺点将更加明显。例如

struct node * append( struct node *head, int v ) 
{
    struct node *t = ( struct node * )malloc( sizeof( *t ) );
    t->value = v;
    t->next  = tail;
    if ( head == tail )
    {
        head = t;
    }
    else
    {
        struct node *current = head;
        while ( current->next != tail ) current = current->next;
        current->next = t;
    }
    return t;
}

在这种情况下，main中的函数调用可以像下面这样查找

struct node *head = NULL;
struct node *current;
int i;
head = append( head, 0 );
for ( i = 1, current = head; i < 10; i++ ) current = append( current, i ); 

在这种情况下，append的调用将是非常有效的，因为在函数内，while循环甚至不会进行一次迭代。

Answer 3

当链表为空时，通常使用NULL头来实现。在这种情况下，当头部是一个局部变量时，或者当它是一个全局变量并且您希望使用同一个函数拥有多个列表时，您必须返回列表的头部。当添加一个节点时，头部可能已经改变，即使添加了尾部，在列表为空的情况下，有一个新的头部。

但另一种方法是总是在头部有一个节点，就在这里表示头部，并在头部之后添加/读取/删除节点，以便处理列表中的数据。在这种情况下，返回头部是无用的，因为头部永远不会改变。

对于节点n: n->next == NULL，您可以检测列表的尾部，当列表为空时使用等于NULL的头部，如以下代码所示:

// add at the tail of the list:
struct node * add_to_list_tail(struct node * head,int v) {
  struct node *t;
  t=(struct node *) malloc(sizeof(struct node));
  t->value = v;
  t->next = NULL; // next is set to NULL because it is the new tail
  if(head == NULL) {
    // in the case the list is empty
    head = t; // t become the new head, because the list was empty
  } else {
    // in the case the list isn't empty
    struct node * n = head;
    // the following loop will stop when n->next == NULL, and n will point to the tail
    while(n->next != NULL) {
      n = n->next;
    }
    n->next = t;
  }      
  return head;
}
// add at the head of the list:
struct node * add_to_list(struct node * head,int v) {
    struct node *t;
    t=(struct node *) malloc(sizeof(struct node));
    t->value = v;
    t->next = head; // make t become the new head
    return t; // return t because it is the new head
}
int main() {
  struct node * head = NULL;
  head = add_to_list(head,1);
  head = add_to_list(head,2);
  head = add_to_list_tail(head,3);
}

如果不想返回头指针，也可以传递指向头指针的指针，作为操作列表的函数的形参。一个简短的示例代码:

void add_to_list(struct node ** head,int v) {
    struct node *t;
    t=(struct node *) malloc(sizeof(struct node));
    t->value = v;
    // make t become the new head:
    t->next = *head;
    *head = t;
}
int main() {
  struct node * head = NULL;
  // we pass &head, the adress of variable head, as parameter:
  add_to_list(&head,1);
  add_to_list(&head,2);
  struct node * n = head;
  while(n != NULL) {
    printf("nvalue: %d",n->value);
    n = n->next;
  }
}