专栏首页marsggbo链表、头指针、头结点

链表、头指针、头结点

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

图1 线性链表的逻辑状态

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

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

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

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

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

图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语言中可描述如下:

//-----线性表的双向链表存储结构----- 
typedef struct DuLNode{  
    ElemType   data;  
 struct DuLNode  *prior;  
 struct DuLNode  *next;  
}DuLNode, *DuLinkList;  

和单链的循环表类似,双向链表也可以有循环表,如图5(c)所示,链表中存有两个环,图5(b)所示为只有一个表头结点的空表。在双向链表中,若d为指向表中某一个结点的指针(即d为DuLinkList型变量),则显然有

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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 显卡,显卡驱动,nvcc, cuda driver,cudatoolkit,cudnn区别?

    在使用深度学习框架的过程中一定会经常碰到这些东西,虽然anaconda有时会帮助我们自动地解决这些设置,但是有些特殊的库却还是需要我们手动配置环境,但是我对标题...

    marsggbo
  • Django bootstrap按钮点击后激活active

    现在有个需求,就是在导航栏上有若干个按钮,我想实现的功能是当点击某个按钮后修改文字颜色,这样网站会更人性化。现总结方法如下:

    marsggbo
  • python混账的编码问题解决之道

    下面的代码作用是修改文件的编码格式。代码很简单,但是也很牛逼(在我看来),这是在segment上找到的解决办法,废话不多说,直接上代码。 import cod...

    marsggbo
  • 源码分析Dubbo tps过滤器器实现原理

    本文将重点分析一下dubbo限流的另外一个方式,tps过滤器。 @Activate(group = Constants.PROVIDER, value = Co...

    丁威
  • 如何指定Spark1作业中Driver和Executor使用指定范围内端口

    在CDH集群中提交Spark作业,大家也都知道Spark的Driver和Executor之间通讯端口是随机的,Spark会随选择1024和65535(含)之间的...

    Fayson
  • Python Day18 Django

    这样,下次再访问时通过获取cookie中的"sessionid"的值就可以得到所对应的session-data

    py3study
  • 使用Spring Boot实现博客统计服务

    作为一个后端开发,在微服务,server mesh等概念满天飞的时代,持续学习能力是不能丢的,因此楼主最近也研究好多RPC,NETTY,Spring Boot等...

    haifeiWu
  • python测试开发django-61.权限认证(permission)

    用户登录后,才有操作当前用户的权限,不能操作其它人的用户,这就是需要用到权限认证,要不然你登录自己的用户,去操作别人用户的相关数据,就很危险了。

    上海-悠悠
  • [翻译]VelocityLayoutServlet (VLS) 综观

    这一个基本的VelocityViewServlet的一个扩展。它为基于Velocity Tools 的工程项目提供了一个简单的布局控制和定制的错误显示屏幕。Ve...

    LeoXu
  • Spring Cloud 入门教程7、服务网关(Zuul)

    服务网关也就是API网关,服务网关可以作为服务的统一入口,提供身份校验、动态路由、负载均衡、安全管理、统计、监控、流量管理、灰度发布、压力测试等功能

    KenTalk

扫码关注云+社区

领取腾讯云代金券