称为头指针，当HEAD=NULL（或0）时称为空表。
对于线性链表，可以从头指针开始，沿各结点的指针扫描到链表中的所有结点。
从头指针开始，依次输出各结点值。
上面讨论的线性链表又称为线性单链表。在这种链表中，每一个结点只有一个指针域，由这个指针只能找到后件结点，但不能找到前件结点。因此，在这种线性链表中，只能顺指针向链尾方向进行扫描，这对于某些问题的处理会带来不便，因为在这种链接方式下，由某一个结点出发，只能找到它的后件，而为了找出它的前件，必须从头指针开始重新寻找。
为了弥补线性链表的这个缺点，在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针（Llink），用以指向其前件结点；另一个称为右指针（Rlink），用以指向其后件结点。这样的线性链表称为双向链表，其逻辑状态如下图所示。
2．带链的栈 略
3．带链的队列 略
考点13 线性链表的基本运算
线性链表的运算主要有以下几种：
① 在线性链表中包含指定元素的结点前插入一个新元素。 ② 在线性链表中删除包含指定元素的结点。
③ 将两个线性链表按要求合并成一个线性链表。 ④ 将一个线性链表按要求进行分解。 ⑤ 逆转线性链表。 ⑥ 复制线性链表。 ⑦ 线性链表的排序。 ⑧ 线性链表的查找。
主要讨论查找、插入和删除。 查找：
插入：把元素b插入到链表中。
插入前：
插入后：
删除：
删除前：
删除后：
考点14 循环链表及其基本运算 了解
循环链表的结构与前面所讨论的线性链表相比，具有以下两个特点：
? 在循环链表中增加了一个表头结点，其数据域可根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。
? 循环链表中最后一个结点的指针域不为空，而是指向表头结点，即循环链表中所有结点的指针构成了一个环状链。
循环链表的示意图如下图所示。图1是一个非空的循环链表，图2是一个空的循环链表。
在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点，而线性单链表做不到这一点。
另外，由于在循环链表中设置了一个表头结点，因此，在任何情况下，循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。
循环链表的插入和删除的方法与线性链表基本相同，但由循环链表的特点可以看出，在对循环链表进行插入和删除的过程中，实现了空表与非空表的运算统一。
六、树与二叉树
考点15 树的基本概念
树型结构是一类重要的非线性数据结构。其中以树和二叉树
最为常用。直观来说，树是以分支关系定义的层次结构。
树（tree）是一种简单的非线性结构。在这种数据结构中，所有数据元素之间的关系具有明显的层次特性。
下图表示了一棵树。从图中可以看出，在用图形表示这种数据结构时，很像自然界中的树，只不过是一棵例长的树，因此，这种数据结构就用“树”来命名。
在树的图形表示中，一般认为在用直线连接起来的两端结点中，上端结点是前件，下端结点是后件，这样表示前后件关系的箭头就可以省略。
在现实世界中，能用树这种数据结构表示的例子有很多。如下图为学校的行政关系图。
基本特征及术语：重点
1、父结点与根结点
在树结构中，每一个结点只有一个前件，称为父结点。
没有前件的结点只有一个，称为根结点，简称为根。
如：上面一般的树图中，根结点为：R
2、子结点与叶子结点
在树结构中，每一个结点可以拥有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点，简称为叶子。
如：上面一般的树图中，叶子结点为：
C、E、X、S、M、F、G、L
3、结点的度
在树结构中，一个结点所拥有的后件个数称为该节点的度。 如：上面一般的树图中，结点K、T的度分别为2和3。 叶子结点的度为0，根结点的度为4。
4、树的度
在树中，所有结点中的最大的度称为树的度。 如：上面一般的树图中，树的度为4。
5、树的层次结构中的分层原则
树是一种层次结构，它有明显的层次关系。在树结构中，一般按如下原则分层：
①根结点在第一层；
②同一层上所有结点的所有子结点都在下一层。