Question

从表头插入节点建立单链表的算法如何写

Answer 1

何在指针q指向的结点后面插入结点。该过程的步骤如下：

（1）先创建一个新结点，并用指针p指向该结点。

（2）将q指向的结点的next域的值（即q的后继结点的指针）赋值给p指向结点的next域。

（3）将p的值赋值给q的next域。

通过以上3步就可以实现在链表中由指针q指向的结点后面插入p所指向的结点。可以通过图1-5形象地展示出这一过程。

图1-5 向链表插入结点过程
下面给出代码描述：

1.void insertList(LinkList *list,LinkList q,ElemType e) /*当链表为空时*/ 10. else 16.} 上面的这段代码描述了如何在指针q指向的结点后面插入结点的过程。其过程包括以下几步。

（1）首先生成一个新的结点，大小为sizeof(LNode)，用LinkList类型的变量p指向该结点。将该结点的数据域赋值为e。

（2）接下来判断链表是否为空。如果链表为空，则将p赋值给list，p的next域的值置为空。否则，将q指向的结点的next域的值赋值给p指向结点的next域，这样p指向的结点就与q指向结点的下一个结点连接到了一起。

（3）然后再将p的值赋值给q所指结点的next域，这样就将p指向的结点插入到了指针q指向结点的后面。

其实通过上面这段算法描述可以看出，应用这个算法同样可以创建一个链表。这是因为当最开始时链表为空，即list==NULL，该算法可自动为链表创建一个结点。在下面的创建其他结点的过程中，只要始终将指针q指向链表的最后一个结点，就可以创建出一个 链表。

注意：函数insertList()的参数中有一个LinkList *list，它是指向LinkList类型的指针变量，相当于指向LNode类型的指针的指针。这是因为在函数中要对list，也就是表头指针进行修改，而调用该函数时，实参是&list，而不是list。因此必须采取指针参数传递的办法，否则无法在被调函数中修改主函数中定义的变量的内容。以下的代码也有类似的情况。