Question

大家看数据结构中 头插法和尾插法，，为什么尾插法要设置最后一个节点为空，而头插法不用？？？？？？？？

list tailcreat(list *&l)
{
list *p,*q;
l=(struct list *)malloc(sizeof(list));
l->next=NULL;
q=l;
for(int i=0;i<10;i++)
{
p=(list *)malloc(sizeof(list));
p->data=i;
q->next=p;
q=p;
}
p->next=NULL;
}
linlist tcreat(linlist &l)
{
linlist p;
l=(list *)malloc(sizeof(list));
l->next=NULL;
for(int i=0;i<10;i++)
{
p=( list *)malloc(sizeof(list));
p->data=i;
p->next=l->next;
l->next=p;
}
}

Answer 1

首先说头插法是在链表的开始插入节点，所以他必有后继 所以要设置其起后继指针为插入前的头结点。
而 尾插法是在链表的尾部插入节点所以修改原链表的尾部的后继指针为新节点 而新节点以是尾部无后继结点 所以尾插法的节点后继为NULL

追问

起后继指针为插入前的头结点？？那么建立的新表不就没有头结点了吗？？

追答

那要看你的链表是哪种类型的 有的头是一个独立的头 那样你插入的时候就是插入在独立的头的后面这样仅当链表为空时 头插法插入的结点尾部是NULL 其他情况下都不是NULL。这链表的好处是每次插入节点不用修改对头指针的指向。
另一中没有独立的头 那就是说链表至少有一个节点 这样每次头插入法插入的节点都是 链表的头节点 每次插入都要修改 对头指针的指向。

追问

但是我这个头插法建立的链表没有设置尾部为空啊？？

追答

你新创建的节点 的尾部默认是NULL

l=(struct list *)malloc(sizeof(list));
l->next=NULL;
当存在后继结点时
l->next=p;
这时就不为空了

追问

我想说的是每次定义的心节点插在l的后面（p->next=l->next;l->next=p;），l没有移动，前面定义的p不会被覆盖吗？

追答

恩 其实你这个链表就是有独立头节点L
你看这句 p->next=l->next;你每次的新节点都会获得原先头节点后第一个节点的地址
并把它放到新节点的后继指针上 所以每次新插入节点 是先将原来链表的第一个节点（头结点除外）先连接到新节点的后面 再将新节点连接到头结点的后面 所以不会被覆盖

Answer 2

尾插法每次插入的节点为链表的当前的最后一个节点，无后继，故为null，
头插法插入的节点是插入当前链表的头部，即其后继为当前链表的首元结点，故须指向该首元结点，所以不能为空

追问

p->next=l->next;
l->next=p;
这个函数是将p插入头结点之后啊？?尾部 不就不为空了？？？？？？

追答

p->next=l->next;
l->next=p;

这两条语句是头插法，所以不为空，你的头插法和尾插法概念理解反了

Answer 3

循环前：
只有一个头结点l

循环第一次：
p->next=l->next=NULL; //头插法，因此第一次循环的节点p作为链表的最后一个节点的p->next=NULL
l->next=p; //l的下一个节点为p

循环第二次：
p->next=l->next; //注意此时l->next是第一次插入的节点p，l->next作为本次插入节点的下一个节点,即相当于在前面插入了一个节点
l->next=p;

注意：
每次插入节点类似于这种情形：每次在头节点 l 和链表的第一个节点(l->next) 之间插入一个新节点p