结构之美：单链表的头结点与头指针

转自：结构之美：单链表的头结点与头指针


    当链表的每个结点只包含一个指针域时，我们称此链表为单链表。

    关于单链表的存取，有时候我们在单链表的第一个结点（有效元素）之前附设一个结点，称之为头结点；指向头结点的指针，称之为头指针；对单链表的存取必须从头指针开始进行，由于单链表的最后一个数据元素没有直接后继，则指针为NULL。


对于头结点，数据域可以不存储任何信息，也可存储如链表长度等附加信息。
下面是带头结点的单链表与空表的比较图。

头指针与头结点不同，头结点即第一个结点，头指针是指向第一个结点的指针。链表中可以没有头结点，但不能没有头指针。
以下是头指针与头结点的关系：

1//定义结点的结构体
2typedef struct LNode{
3    int data;
4    struct LNode *next;
5}LNode,*LinkList;
则定义LinkList L;时，L为链表的头指针。
L=(LinkList) malloc (sizeof(LNode)); //创建一个结点
此处返回给L的是一个指针，并且赋给了头指针。
L->next=null; //这里说明我创建了一个头结点，即同时运用了头指针和头结点。

小结

关于头指针：
  • 在线性表的链式存储结构中，头指针是指链表指向第一个结点的指针，若链表有头结点，则头指针就是指向链表头结点的指针。
  • 头指针具有标识作用，故常用头指针冠以链表的名字。
  • 无论链表是否为空，头指针均不为空。头指针是链表的必要元素。
关于头结点：
  • 头结点是为了操作的统一与方便而设立的，放在第一个元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。
  • 有了头结点后，对在第一个元素结点前插入结点和删除第一个结点，其操作与对其它结点的操作统一了。
  • 首元结点也就是第一个元素的结点，它是头结点后边的第一个结点。
  • 头结点不是链表所必需的。

延伸阅读

此文章所在专题列表如下：
  1. 结构之美：定义一个线性表
  2. 结构之美：线性表的查找、插入与删除操作
  3. 结构之美：线性表的链式存储结构——链表
  4. 结构之美：单链表的初始化、创建与遍历
  5. 结构之美：单链表的头结点与头指针
  6. 结构之美：使用头插法创建单链表
  7. 结构之美：使用尾插法创建单链表
  8. 结构之美：单链表的销毁删除
  9. 结构之美：查找单链表指定位置结点的数据
  10. 结构之美：在单链表指定位置插入数据
  11. 结构之美：删除单链表指定位置的数据
  12. 结构之美：单链表逆序
  13. 结构之美：判断单链表中是否有环
  14. 结构之美：获取单链表倒数第N个结点值
  15. 单循环链表的初始化、创建、删除、查找与遍历
  16. 结构之美：双向循环链表的结构与定义
本文地址：http://www.nowamagic.net/librarys/veda/detail/1805，欢迎访问原出处。



时间：