头结点和头指针

在链表的实现中，头结点和头指针是两个不同的概念。

头结点是一种特殊的结点，它不存储数据，仅用于方便链表的操作。头结点通常放在链表的最前面，是链表的第一个结点。头结点中一般包含链表的一些基本信息，比如链表长度、首结点位置等等。

头指针指向头结点的指针，它的作用是记录链表的起始位置。如果没有头结点，那么头指针指向的就是链表的第一个结点。但是为了方便链表的操作，通常都会添加一个头结点，这样头指针就指向头结点，而不是实际的数据结点。这样做的好处是，链表的插入、删除等操作可以统一处理，不需要针对链表首结点和其他结点分别处理。

下面以一个简单的单链表为例，来解释头结点和头指针的概念。

假设有如下链表：

+----+      +----+      +----+      +----+      +----+
|    |----->|    |----->|    |----->|    |----->|    |
+----+      +----+      +----+      +----+      +----+
 head        1st         2nd         3rd        4th

其中，head为头指针，指向头结点，1st为头结点，不存储数据，仅用于方便操作。 2nd、3rd、4th为链表中的实际数据结点。

在代码实现中，我们通常使用下列方式来定义头结点和头指针：

typedefstructNode *PtrToNode;structNode {
    ElementType Data;
    PtrToNode Next;
};

typedef PtrToNode List;
typedef PtrToNode Position;

List MakeEmpty() {
    List L = (List)malloc(sizeof(struct Node));
    L->Next = NULL;
    return L;
}

其中，List类型实际上是一个指向struct Node类型的指针，Position类型也是一个指向struct Node类型的指针。MakeEmpty函数中，创建了一个头结点，并将其Next指针初始化为NULL，然后返回头指针。这样，我们就可以通过头指针方便地操作链表了。