开发者社区> marsggbo> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

链表、头指针、头结点

简介:  图1为线性表(ZHAO, QIAN, SUN, LI, ZHOU, WU, ZHENG, WANG)的逻辑状态。头指针 指示链表中第一个结点(即第一个数据元素的存储映像)的存储位置。同时,由于最后一个数据元素没有直接后继,则线性链表中最后一个结点的指针为“空”(NULL)。
+关注继续查看

 图1为线性表(ZHAO, QIAN, SUN, LI, ZHOU, WU, ZHENG, WANG)的逻辑状态。头指针 指示链表中第一个结点(即第一个数据元素的存储映像)的存储位置。同时,由于最后一个数据元素没有直接后继,则线性链表中最后一个结点的指针为“空”(NULL)。

图2.6

图1 线性链表的逻辑状态

由上述描述可见,单链表可由头指针来唯一确定,在C语言中可用“结构指针”来描述。

  1. //-----线性表的单链表存储结构-----  
  2. typedef struct LNode{  
  3.     ElemType   data;  
  4.     struct LNode  *next;  
  5. }LNode, *LinkList;  

有时在单链表的第一个结点之前附设一个结点,称之为头结点  头结点的数据域可以不存储任何信息,也可以存储如线性表长度等类的附加信息,头结点的指针域存储指向第一个结点的指针(即第一个元素结点的存储位置)。如图2(a)所示,此时,单链表的头指针指向头结点。若线性表为空,则头结点的指针域为“空”,如图2(b)所示。

图2.7图2 带头结点的单链表   (a)非空表;(b)空表

    循环链表 是另一种形式的链式存储结构。它的特点是表中最后一个节点的指针域指向头结点,整个链表形成一个环。由此,从表中任一结点出发均可找到表中其他结点,如图3所示为单链的循环链表 。

图2.12 图3 单链循环表 (a)非空表;(b)空表

循环链表的操作和线性链表基本一致,差别仅在于算法中的循环条件不是p或p->next 是否为空,而是它们是否等于头指针,但有的时候,若在循环链表中设立尾指针而不设头指针(如图4(a)所示),可使某些操作简化。例如将两个线性表合并成一个表时,仅需将一个表的尾表和另一个表的头表相接。当线性表以图2.4(a)的循环链表作存储结构时,这个操作仅需改变两个指针值即可,运算时间为O (1)。合并后的表如图4(b)所示。

图2.13图4 仅设尾指针的循环链表 (a)两个链表;(b)合并后的表

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

  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型变量),则显然有

d->next->prior=d->prior->next=d

图2.14

图5 双向链表示例 (a)结点结构;(b)空的双向循环链表;(c)非空的双向循环链表

http://blog.csdn.net/zhenyusoso/article/details/6092843

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
链表
链表
0 0
链表必刷题二
链表必刷题二
0 0
链表是啥?如何搞定它?
链表是啥?如何搞定它?
0 0
玩转C链表
链表是C语言编程中常用的数据结构,比如我们要建一个整数链表,一般可能这么定义: 1 2 3 4 struct int_node {         int val;         struct int_node *next; }; 为了实现链表的插入、删除、遍历...
588 0
链表的回文结构
题目描述 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。 给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。
628 0
带头结点的链表的逆置
版权声明:本文为博主原创文章,转载请注明出处。 https://blog.
518 0
C链表
结构指针的应用,链表处理 1,链表的概念 链表是将若干数据项按一定规则连接起来的[数据类型]表,链表中的每一个数据称为一个节点,既链表是由称为节点的元素组成的,节点多少根据需要确定. 链表连接规则: 前一个节点指向下一个节点,只要通过前一个节点才能找到下一个节点,每个节点都包括下面2...
441 0
+关注
marsggbo
AutoML
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载