单链表的存储结构及数据类型定义

1.单链表的结点结构

单链表中的数据元素，称为结点（Node），结点的存储结构如下：

2.单链表的结构

（1）单链表的一般形式

将n个数据元素通过其对应结点的指针域按其逻辑关系链接成一个链表，链表中的每个结点只包含一个指针
域，这样的链表称为线性链表或单链表，其一般形式如图2-5所示。

（2）单链表存储实例

在单链表中，一般设置一个用于指向单链表的第一个结点的head指针，称为头指针。由于单链表的最后一个
结点没有直接后继，所以其指针域为“空”（NULL），用符号“∧”表示。
假设由A、B、C、D、E 等5个数据元素构成一个单链表，其中每个元素称为一个结点，该单链表的逻辑关系示
意图如图2-6所示。

图2-6 单链表的逻辑关系示意图

单链表的存储结构如图2-7所示。

图2-67 单链表的存储结构示意图

（3）带头节点的单链表

通常在单链表的第一个结点之前设立一个结点，称之为头结点。头结点的数据域可以不存储任何数据信息，也
可以存储一个线性表中不包括的元素值；头结点的指针域存储第一个结点的地址信息；由头指针指向头结点。
带头结点的单链表如图2-8所示。

3.单链表的存储结构（即数据类型）的定义

用C语言的结构体定义单链表的数据类型如下：