）称为头指针，头指针：在线性链表中，头指针（HEAD）很关键，不得丢失。最后一个结点的指针域：线性链表的最一个结点的指针域为空（用NULL或0来表示）空表的定义：当HEADNULL（或0）称为空表。单链表的缺点：只能找到后不能找到前件。2．双向链表为了克服单链表的缺点，把每个结点修改为由三部分组左指针数据元素右指针
双向链表克服了单向链表的只能找到后件不能找到前件的缺陷。如果是两指针：左指针（Lli
k）指向前件结点，右指针（Rli
k）指向后件结点。2．带链的栈
f在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点。这种带链的栈称为可利用栈当计算机系统需要存储结点时，退栈。当计算机系统释放存储结点时，入栈3．循环链表单链表的运算必须对于空表和对第一个结点的处理必须单独考虑，为了克服这个缺点，提出了循环链表的概念。循环链表与单链表的主要区别：第一，在循环链表中增加了表头结点，其数据域为任意或根据需要来设置，指针域为指向线性表的第一个元素的结点。第二，循环链表中的最后一个结点的指针不为空，而是指向表头的结点。1．6树与二叉树p31161树的基本概念树是一种简单的非线性结构，所有元素之间具有明显的层次特性。在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树的基本性质：（1）在二叉树的第k层上，最多有2k1k≥1个结点；（2）深度为m的二叉树最多有2m1个结点；（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；（4）具有
个结点的二叉树，其深度至少为log2
1其中log2
表示取log2
的整数部分；（5）具有
个结点的完全二叉树的深度为log2
1；（6）设完全二叉树共有
个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，
给结点进行编号（k12
），有以下结论：①若k1，则该结点为根结点，它没有父结点；若k1，则该结点的父结点编号为INTk2；②若2k≤
，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）；③若2k1≤
，r