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