链表、头指针、头结点

《链表、头指针、头结点》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、链表、头指针、头结点图1为线性表（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG）的逻辑状态。头指针指示链表中第一个结点（即第一个数据元素的存储映像）的存储位置。同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为“空”（NULL）。图１线性链表的逻辑状态由上述描述可见，单链表可由头指针来唯一确定，在C语言中可用“结构指针”来描述。[cpp]viewplaincopy1.//-----线性表的单链表存储结构-----  2.typedef struct LNode{  3.    ElemType   dat

2、a;  4.    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)两个链

4、表；(b)合并后的表 以上讨论的链式存储结构的节点中只有一个指示直接后继的指针域，由此，从某个结点出发只能顺指针往后寻查其他结点。若要寻查节点的直接前趋，则需从表头指针出发。换句话说，在单链表中，NextElem的执行时间为O(1)，而PriorElem的执行时间为O(n)。为克服单链表这种单向性的缺点，可利用双向链表。顾名思义，在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。在C语言中可描述如下：[cpp]viewplaincopy1.//-----线性表的双向链表存储结构-----  2.typedef struct DuLNo

5、de{  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

6、)非空的双向循环链表