链表增加了尾巴，混乱 [英] linked list adding to the tail, confusion
问题描述
Visual Studio 2008中ç
我不明白这个链表是加剧了if语句的else部分尾巴。
当头部和尾部被赋予node_temp到两个尾的存储器地址和头都指向同一个存储单元。
然而，在其他的部分是实际上仍然指向尾部的头部。这里只是我无法解释和不理解else部分？
我希望有人能为我解释一下更好。
静态结构convert_temp
{
为size_t CEL;
为size_t FAH;
结构convert_temp *接下来的;
} *头= NULL，*尾= NULL;/ **添加列表上的新的温度转换* /
无效的附加（为size_t CEL，为size_t FAH）
{
结构convert_temp * node_temp = NULL; / *包含温度数据* / node_temp =的malloc（sizeof的（* node_temp））; 如果（node_temp == NULL）
{
fprintf中（标准错误，无法分配内存[％S]：[％D]。\\ n
__FUNCTION__，__LINE__）;
出口（0）;
} / *分配数据* /
node_temp-＆GT; CEL = CEL;
node_temp-＆GT;白花= FAH;
node_temp-＆gt;接着= NULL; 如果（头== NULL）
{
/ *该列表是在开始* /
头= node_temp; / *头是第一个节点=同一节点* /
尾= node_temp; / *尾部也是最后一个节点=同一节点* /
}
其他
{
/ *追加到尾* /
tail-＆gt;接下来= node_temp;
/ *在终点尾* /
尾= node_temp;
}
}
第一次添加元素（让我们为 A 调用）到列表中，头为空，你去通过如果部分。这意味着，无论头和尾部都设置为指向 A 添加时第一个元素。
现在让我们添加另一个元素 B 。这一次，如此这般通过其他部分，设置头不为空尾来指向 B 但在离开头在 A 。
这是预料之中的，你现在有头指向 A ， A 指向 B ， B 指向没有（空）和尾指向 B 。
让我们一步一步来。
初始状态：头部 - + - ＆GT;空值
|
尾 - +将项目A：头部 - + - ＆GT; A ---＆GT;空值
|
尾 - +插入B项：头部 - ＆GT; A - + - ＆GT; B ---电＆GT;空值
|
尾部-------- +将项目C：头---＆GT; A ---＆GT;乙 - + - ＆GT; Ç---＆GT;空值
|
尾部--------------- +
可以在每个阶段（比初始其他），当前尾被设定为指向新节点（它已指向为NULL其下一个节点），那么尾指针被更新看到指向的新的的最后一个节点。
事实上，让我们通过在偶数的更多的细节（逐行），所以你可以看到code的每一行正在做（我已经改名<$的C添加C $ C> node_temp 到节点只是为了帮助格式化）：
启动状态：头---＆GT; A - + - ＆GT; B ---电＆GT;空值
|
尾部-------- +节点=的malloc（sizeof的（*节点））;节点---＆GT; ç----------＆GT; ？
（分配节点C）头---＆GT; A - + - ＆GT; B ---电＆GT;空值
|
尾部-------- +于节点＆gt;接着= NULL;节点---＆GT; Ç-------- +
（忽略载荷CEL / FAH |
现在因为它不是头---＆GT; A - + - ＆GT;乙 - + - ＆GT;空值
有关名单|
结构）尾-------- +tail-＆gt;接下来=节点;节点--------------- +
（第一else子句）|
头---＆GT; A - + - ＆GT;乙 - + - ＆GT; Ç---＆GT;空值
|
尾部-------- +尾=节点;节点--------------- +
（第二else子句）|
头---＆GT; A ---＆GT;乙 - + - ＆GT; Ç---＆GT;空值
|
尾部--------------- +
然后最终节点消失，因为它是一个局部变量，你有你的最终状态：
头---＆GT; A ---＆GT;乙 - + - ＆GT; Ç---＆GT;空值
|
尾部--------------- +
在一个单链表维护尾指针的优点是避免步在整个列表中查找，当你尝试添加结束一个项目的结束。
遍历整个列表，使插在最后一个 O（N）时操作（拍摄时间取决于项目的列表中的号码）。使用尾指针使，一个 O（1）时操作（同样的时间，不论名单大小）。
顺便说一句，一个双向链表有一个尾额外的使用指针 - 它给迅速从列表中的末尾开始穿越的能力开始，使用尾和替代头和 $ p $光伏指针接下来指针。
Visual Studio 2008 C
What I can't understand about this linked list is the adding to the tail in the else part of the if statement.
When the head and tails is assigned the memory address of the node_temp to both tail and head both point to the same memory location.
However, in the else part is the head in fact still pointing to the tail. There is just something I can't explain and don't understand about the else part?
I hope some one can explain better for me.
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;
}
}
The first time you add an element (let's call it A) to the list, head is null and you go through the if part. That means that both head and tail are set to point to A when adding that first element.
Now let's add another element B. This time, head is not null so it goes through the else part, setting tail to point to B but leaving head pointing at A.
This is as expected, you now have head pointing to A, A pointing to B, B pointing to nothing (null) and tail pointing to B.
Let's take it step by step.
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 ---------------+
You can see at each stage (other than the initial) that the current tail is set to point to the new node (which already points to NULL for its next node) then the tail pointer is updated to point to the new last node.
In fact, let's go through the addition of C in even more detail (line by line) so you can see what each line of code is doing (I've renamed node_temp to node just to help with formatting):
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 ---------------+
Then eventually node disappears since it's a local variable and you have your final state:
head ---> A ---> B -+-> C ---> NULL
|
tail ---------------+
The advantage of maintaining a tail pointer in a singly-linked list is to avoid having to step through the entire list to find the end when you're trying to add an item to the end.
Traversing the entire list makes insertion at the end an O(n) time operation (time taken is dependent on the number of items in the list). The use of the tail pointer makes that an O(1) time operation (same amount of time irrespective of the list size).
As an aside, a doubly linked list has an extra use for a tail pointer - it gives the ability to quickly begin a traversal from the end of the list to the start, using tail and the prev pointers in lieu of head and the next pointers.
这篇关于链表增加了尾巴，混乱的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
