链表增加了尾，混乱

Visual Studio 2008中ç链表增加了尾，混乱

什么我不明白这个链表是if语句的其他部分增加了尾。

当头和尾部被分配了node_temp的内存地址时，尾部和头部都指向相同的内存位置。

但是，在其他部分，头部实际上仍指向尾部。有什么我无法解释，也不了解其他部分？

我希望有人能为我解释得更好。

static struct convert_temp 
{ 
    size_t cel; 
    size_t fah; 
    struct convert_temp *next; 
} *head = NULL, *tail = NULL; 

/** Add the new converted temperatures on the list */ 
void add(size_t cel, size_t fah) 
{ 
    struct convert_temp *node_temp = NULL; /* contain temp data */ 

    node_temp = malloc(sizeof(*node_temp)); 

    if(node_temp == NULL) 
    { 
     fprintf(stderr, "Cannot allocate memory [ %s ] : [ %d ]\n", 
      __FUNCTION__, __LINE__); 
     exit(0); 
    } 

    /* Assign data */ 
    node_temp->cel = cel; 
    node_temp->fah = fah; 
    node_temp->next = NULL; 

    if(head == NULL) 
    { 
     /* The list is at the beginning */ 
     head = node_temp; /* Head is the first node = same node */ 
     tail = node_temp; /* Tail is also the last node = same node */ 
    } 
    else 
    { 
     /* Append to the tail */ 
     tail->next = node_temp; 
     /* Point the tail at the end */ 
     tail = node_temp; 
    } 
}

来源

2009-12-21 ant2009

通过它与调试器。 – 2009-12-21 14:03:14

第一次将一个元素（我们称之为A）添加到列表中时，head为空，您将通过if部分。这意味着在添加第一个元素时，head和尾部都设置为指向A。

现在让我们添加另一个元素B。这一次，head不为零，因此它会经过else部分，将tail设置为指向B，但将head指向A。

这是预期，你现在有head指向A，A指着B，B指向没有（空），tail指向B。

让我们一步一步来。

Initial state: head -+-> null 
         | 
       tail -+ 

Insert item A: head -+-> A ---> null 
         | 
       tail -+ 

Insert item B: head ---> A -+-> B ---> null 
          | 
       tail --------+ 

Insert item C: head ---> A ---> B -+-> C ---> null 
            | 
       tail ---------------+

可以在（已经指向NULL用于其下一个节点），每个级（比初始其他），当前尾部被设置为指向所述新节点那么尾指针被更新为指向看到新的最后一个节点。

事实上，让我们通过甚至更细节C的加入（逐行），所以你可以看到每行代码是做（我已经改名node_temp到node只是为了帮助格式）：

Starting state:    head ---> A -+-> B ---> null 
              | 
           tail --------+ 

node = malloc(sizeof(*node)); node ---> C ----------> ? 
(allocate node C)    head ---> A -+-> B ---> null 
              | 
           tail --------+ 

node->next = NULL;    node ---> C --------+ 
(ignore payload cel/fah       | 
    for now since it's not  head ---> A -+-> B -+-> null 
    relevant to the list     | 
       structure)  tail --------+ 

tail->next = node;    node ---------------+ 
(first in else clause)       | 
           head ---> A -+-> B -+-> C ---> null 
              | 
           tail --------+ 

tail = node;     node ---------------+ 
(second in else clause)       | 
           head ---> A ---> B -+-> C ---> null 
                | 
           tail ---------------+

然后最终node消失，因为它是一个局部变量，你有你的最终状态：

       head ---> A ---> B -+-> C ---> NULL 
                | 
           tail ---------------+

保持的优势单链表中的指针是为了避免在尝试将项目添加到结尾时必须遍历整个列表以找到结尾。

遍历整个列表使末尾插入一个O(n)时间操作（花费的时间取决于列表中的项目数）。 tail指针的使用使得该操作的时间（相同的时间量，而不管列表大小）。

顺便说一句，一个双向链表有一个tail指针一个额外的用途 - 它提供了快速从列表中开始的结束开始遍历，使用tail能力，代替head的prev指针和next指针。

来源

2009-12-21 14:04:37 paxdiablo

优秀的答案。如果你不明白的话，总要画出你的指针！ – Roalt 2009-12-21 14:11:24

+1：我记得链接列表的最好解释之一。（我希望我的老师在我十一年级的时候给我这样的解释）;）） – 2009-12-21 15:28:59

其他部分只是更新列表的tail，因为当您追加到链接列表时，头部不会更改。

这是一个优化，保持缓存的尾部元素的指针，所以你不必从每个追加的头部遍历整个列表。

来源

2009-12-21 14:03:48 unwind

这不是头仍然指向尾巴。头部指向前尾巴。当列表只包含一个元素时，它是头部和尾部。当添加新节点时，尾指针被更新。头指针仍然指向第一个节点，这是正确的。

来源

2009-12-21 14:09:49

第一次调用add时，head和tail会指向一个新创建的内存块。所有后续的添加调用都将落到else部分，这只会改变尾部指针，基本上修改旧的tail-> next指向新的内存块，然后更新尾部以指向这个新的内存块。

这是一种有效的追加方式。如果只使用head，那么每次添加一个新的node_temp时，都必须从头开始遍历所有下一个指针，直到到达先前添加的node_temp（其下一个指针将为NULL），然后添加新节点。这将是一个O（n）算法，而不是上面的O（1）。

来源

2009-12-21 14:10:14 Richard

链表增加了尾，混乱

回答

相关问题