链表、头指针、头结点

链表 头指针 头结点链表 头指针 头结点 图 1 为线性表 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG 的逻辑状态 头指针头指针 指示链表中第一个结点 即第一个数据元素的存储映像 的存储位置 同时 由于最后一个数 据元素没有直接后继 则线性链表中最后一个结点的指针为 空 NULL 图 线性链表的逻辑状态 由上述描述可见 单链表可由头指针来唯一确定 在 C 语言中可用 结构指针 来描述 cpp cpp view plaincopy 1 线性表的单链表存储结构 2 typedef struct LNode 3 ElemType data 4 struct LNode next 5 LNode LinkList 有时在单链表的第一个结点之前附设一个结点 称之为头结点头结点 头结点的数据域可以不 存储任何信息 也可以存储如线性表长度等类的附加信息 头结点的指针域存储指向第一个结 点的指针 即第一个元素结点的存储位置 如图 a 所示 此时 单链表的头指针指向头 结点 若线性表为空 则头结点的指针域为 空 如图 b 所示 图 2 带头结点的单链表 a 非空表 b 空表 循环链表循环链表 是另一种形式的链式存储结构 它的特点是表中最后一个节点的指针域指向头结 点 整个链表形成一个环 由此 从表中任一结点出发均可找到表中其他结点 如图 3 所示为 单链的循环链表 图 单链循环表 a 非空表 b 空表 循环链表的操作和线性链表基本一致 差别仅在于算法中的循环条件不是 p 或 p next 是否为空 而是它们是否等于头指针 但有的时候 若在循环链表中设立尾指针而不设头指针 如图 4 a 所示 可使某些操作简化 例如将两个线性表合并成 一个表时 仅需将一个表 的尾表和另一个表的头表相接 当线性表以图 2 4 a 的循环链表作存储结构时 这个操作仅需 改变两个指针值即可 运算时间为 O 1 合并后的表如图 4 b 所示 图 4 仅设尾指针的循环链表 a 两个链表 b 合并后的表 以上讨论的链式存储结构的节点中只有一个指示直接后继的指针域 由 此 从某个结点出 发只能顺指针往后寻查其他结点 若要寻查节点的直接前趋 则需从表头指针出发 换句话说 在单链表中 NextElem 的执行时间为 O 1 而 PriorElem 的执行时间为 O n 为克服单链表 这种单向性的缺点 可利用双向链表双向链表 顾名思义 在双向链表的结点中有两个指针域 其一 指向直接后继 另一指向直接前趋 在 C 语言中可描述如下 cpp cpp view plaincopy 1 线性表的双向链表存储结构 2 typedef struct DuLNode 3 ElemType data 4 struct DuLNode prior 5 struct DuLNode next 6 DuLNode DuLinkList 和单链的循环表类似 双向链表也可以有循环表 如图 5 c 所示 链表中存有两个环 图 5 b 所 示为只有一个表头结点的空表 在双向链表中 若 d 为指向表中某一个结点的指针 即 d 为 DuLinkList 型变量 则显然有