数据结构-线性表-头指针&头结点

落日映苍穹つ 2022-09-17 06:28 244阅读 0赞

链表中第一个结点的存储位置叫做**头指针**，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后继指针指向的位置。

这里有个地方要注意，就是对头指针概念的理解，这个很重要。

**“链表中第一个结点的存储位置叫做头指针”，如果链表有头结点，那么头指针就是指向头结点数据域的指针**。

画一个图吧。

![Center][]

这个图看起来很清晰了。比如说**头结点**，我们就可以这么描述了：

*  **[头结点][Link 1]是为了操作的统一与方便而设立的，放在第一个元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。**
 *  **有了头结点后，对在第一个元素结点前插入结点和删除第一个结点，其操作与对其它结点的操作统一了。**
 *  **首元结点也就是第一个元素的结点，它是头结点后边的第一个结点。**
 *  **头结点不是链表所必需的。**

是的，对于 **头指针**，我们也可以有相应的理解了。

*  **在线性表的链式存储结构中，头指针是指链表指向第一个结点的指针，若链表有头结点，则头指针就是指向链表头结点的指针。**
 *  **头指针具有标识作用，故常用头指针冠以链表的名字。**
 *  **无论链表是否为空，头指针均不为空。[头指针][Link 2]是链表的必要元素。**

单链表也可以没有头结点。如果没有头结点的话，那么单链表就会变成这样：

![Center 1][]

说了这么多，既然头结点可有可无，那到底是该有还是不该有呢?

总得来说，一般使用线性表，都是指有头结点得情况。

下面简单总结了两个使用头结点优点：

**头结点是在链表的开始结点之前附加一个结点。它具有两个优点:  
　⒈由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理;  
　⒉无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。**

**方便在第1个位置进行插入、删除操作时，同其他位置一样。**

**加了头结点之后，插入、删除都是在后继指针next上进行操作，不用动头指针；**

**若不加头结点的话，在第1个位置插入或者删除第1个元素时，需要动的是头指针。**

**例如：在进行删除操作时，L为头指针，p指针指向被删结点，q指针指向被删结点的前驱，对于非空的单链表：  
1.带头结点时  
删除第1个结点（q指向的是头结点）：q->next=p->next; free(p);  
删除第i个结点（i不等于1）：q->next=p->next;free(p);  
2.不带头结点时  
删除第1个结点时（q为空）：L=p->next; free(p);  
删除第i个结点（i不等于1）：q->next=p->next;free(p);  
结论：带头结点时，不论删除哪个位置上的结点，用到的代码都一样；**

**不带头结点时，删除第1个元素和删除其它位置上的元素用到的代码不同，相对比较麻烦。**

[Center]: /images/20220828/3596c797f6c44dfd8e12ea81cee93397.png
[Link 1]: http://www.nowamagic.net/librarys/veda/tag/%E5%A4%B4%E7%BB%93%E7%82%B9
[Link 2]: http://www.nowamagic.net/librarys/veda/tag/%E5%A4%B4%E6%8C%87%E9%92%88
[Center 1]: /images/20220828/d352091d7eea46b198a672a17db5533e.png