• 自动秒收录
  • 软件:1973
  • 资讯:57995|
  • 收录网站:278291|

IT精英团

C' Chain Chain '念念不忘@有回音的双向链表

C' Chain Chain '念念不忘@有回音的双向链表

浏览次数:
评论次数:
编辑: 景同
信息来源: ITPUB
更新日期: 2022-09-24 01:07:00
摘要

1.前言写过一篇与单链表相关的博文(https://blog.51cto.com/gkcode/5681771),实际应用中,双向循环链表的功能更强大。单链表中,查询一个已知结点的后驱结点的时间复杂

  • 正文开始
  • 相关阅读
  • 推荐作品

10月10-1010日,我写了一篇关于单链表的博文(https://blog.51cto.com/gkcode/5681771)。在实际应用中,双向循环链表的功能更加强大。

在单链表中,查询一个已知节点的后驱动节点的时间复杂度为O(1)。由于节点本身不存储与前任节点相关的地址信息,需要扫描前任节点一次,所以时间复杂度为O(n)。

双向链表在可以存储前任节点地址的节点类型上增加一个指针位,如下图所示:

8.png

这样查询已知节点的后驱动节点或前驱动节点的时间复杂度为O(1),缺点是耗费空间。

在权衡算法性能时,会优先考虑时间复杂度的优劣,往往会采取空间换时间的策略。

节点类型定义:

typedef int数据类型;

//节点

结构链接节点{

//数据成员

数据类型数据;

//后驱动节点的地址

LinkNode * next

//前任节点的地址

LinkNode * pre

//构造函数

LinkNode(数据类型数据){

this-data=数据;

this-next=NULL;

this-pre=NULL;

}

};

在00-1010双向链表中,除了存储头节点的头指针变量外,一般还会添加一个存储尾节点的尾指针变量。这样,链表就可以从头到尾或者从头到尾遍历。

为了操作方便,初始化链表时会提供一个空白的头节点作为标识节点。

在双向链表中,如果尾节点的后指针位存储头节点的地址,头节点的前指针位存储尾节点的地址,从而形成一个端到端的闭环,则这个链表称为双向循环链表。

9.png

双向链表需要为节点上的数据提供日常维护操作,例如:

初始化链表。创建一个链接列表。找到。后插,前插。删除。算法的整体思路类似于单链表,因为节点中多了一个前驱节点信息,给各种操作带来方便的同时,需要注意的细节也更多了。

下面将介绍双向链表中的几个重要函数。

00-1010如果是双向循环链表,初始化时:

和headtail指向空白头节点。头的前节点和尾的后节点也指向空白的头节点。这个过程也可以在创建链表时实现。11.png

类链接列表{

private:

//头指针

LinkNode * head

//尾部指针

LinkNode * tail

//链表的长度

int长度;

公共:

//构造函数

LinkList() {

this-init linklist();

}

//初始化链表

void initLinkList() {

//头指针存储空白头节点的地址。

this-head=new link node();

//尾指针和头指针在同一位置

这个尾巴=这个头;

//尾节点的后驱动节点是头节点。

this-tail-next=this-head;

//头节点的前置节点是尾节点。

这个-头-

>pre=this->tail; } //……其它函数

2.2 创建链表

可以使用头部插入或尾部插入算法创建链表,本文仅介绍尾部插入创建算法,头部创建算法可自行了解。如下演示使用尾部创建法构建以数列{7,3}为数据的链表。

  • 创建值为7的新结点n

10.png

  • 设置新结点n的前驱结点为原尾结点。
n->pre=tail;

12.png

  • 设置新结点n的后驱结点为原尾结点的后驱结点。
n->next=tail->next;

13.png

  • 设置原尾结点的后驱结点为新结点n
tail->next=n;

14.png

  • 新结点n成为新的尾结点。
tail=n;

15.png

  • 设置头结点的前驱结点为新的尾结点。
head->pre=tail;

16.png

重复上述流程,最终完成链表的创建过程。

17.png

是否可以无视上述创建流程中的顺序?

全局而言,顺序基本是要遵循上述的要求,原则是新结点->尾结点->头结点

  • 新结点:先设置新结点的前驱和后驱结点的地址。新结点的相应存储位都是空白的,先设置前驱还是后驱不影响结果。
  • 尾结点:修改原尾结点的后驱结点地址为新结点,原尾结点的使命完成后,再指定新结点为新的尾结点。
  • 头结点:修改头结点的前驱地址为新尾结点。

编码实现:

//尾部插入方式创建链表void createFromTail(int n) {	LinkNode *newNode,*p,*tail;	//头结点地址	p=this->head;    //尾结点地址    tail=this->tail;    for(int i=; i<n; i++) {        //构建一个新结点        newNode=new LinkNode();        cout<<"请输入结点数据"<<endl;        cin>>newNode->data;        //原来的尾结点成为新结点的前驱结点        newNode->pre=tail;        //新结点的后驱结点为原来的尾结点的后驱结点         newNode->next=tail->next;        //原尾结点的后驱结点为新结点        tail->next=newNode; 				        //新结点成为新的尾结点        tail=newNode;        //头结点的前驱为新尾结点        head->pre=tail;     }    this->head=p;    this->tail=tail;}

测试尾部创建:

int main(int argc, char** argv) {	LinkList list {};	list.createFromTail(2);	//没删除之前	cout<<"显示创建结果:"<<endl;	LinkNode *head= list.getHead();	cout<<"从头结点向尾结点方向搜索:"<<endl;	cout<<head->next->data<<endl;	cout<<head->next->next->data<<endl;	LinkNode *tail=list.getTail();	cout<<"从尾结点向头结点方向搜索 :"<<endl;	cout<<tail->data<<endl;	cout<<tail->pre->data<<endl; 	head=tail->next;	cout<<"从尾结点的后驱信息位得到头结点信息 :"<<endl;	cout<<head->next->data<<endl;	cout<<head->next->next->data<<endl;	return ;	}

执行结果:

18.png

2.3 查找

双向循环链表的头尾是相连的,其查询方案可以有多种变化:

  • 按位置查找: 按位置查找建议从头结点开始。
  • 按值查找: 按值查找可以从头结点或从尾结点开始。
  • 查询所有: 查询所有可以从头结点也可以从尾结点开始。

2.3.1 按位置查找

设空白头结点编号为,从头结点向尾结点扫描过程中,给扫描到的结点依次编号,当查询到和指定参数相同的编号时停止。

//按位置查询结点(从头部扫描到尾部) LinkNode * findNodeByIndex(int index) {    int j=;    LinkNode *p=this->head;    if(index==j)        //如果 index 值为 0 ,返回空白头结点        return p;    //第一个数据结点	    p=p->next;    //设置第一个数据结点的编号为 1 ,当然这不是绝对,可以根据自己的需要设置编号    j=1;    while(p!=this->head && j<index) {        p=p->next;        j++;    }    if(j==index)return p;    else return NULL;}

2.3.2 按值查找

按值查找可以有 2 种方案:

  • 头结点向尾结点方向查找。
//按值查询结点LinkNode * findNodeByVal(dataType val) {    //从第一个数据结点开始查找    LinkNode *p=this->head->next;    //当 p 再次指向头结点结束查找,这也空白结点存在的意义    while(p!=this->head && p->data!=val ) {        p=p->next;    }    if(p!=this->head) {        return p;    } else {        return NULL;    }}
  • 尾结点向头结点方向查找。
LinkNode * findNodeByValFromTail(dataType val) {    //从尾结点开始查找    LinkNode *p=this->tail;    while(p!=this->head && p->data!=val ) {        //向头结点方向        p=p->pre;    }    if(p!=this->head) {        return p;    } else {        return NULL;    }}

2.3.3 查询所有

  • 从头结点向尾结点方向查询所有结点。
void showSelf() {    if(this->head==NULL)return;    //得到第一个数据结点    LinkNode *p=this->head->next;    while(p!=this->head) {        cout<<p->data<<"\t";        p=p->next;    }}
  • 从尾结点向头结点方向查询所有结点。
void showSelf_() {    if(this->tail==NULL)return;    LinkNode *p=this->tail;    while(p!=this->head) {        cout<<p->data<<"\t";        p=p->pre;    }}

2.4 插入

插入有前插入和后插入 2 种方案,于双向链表而言,其时间复杂度都为O(1)

2.4.1 后插入

把新结点插入到已知结点的后面,称为后插入,其插入流程如下所示:

  • 找到已知结点p,创建新结点n

19.png

  • 设置n结点的前驱结点为已知结点p,设置其后驱结点为已知结点p的后驱结点。
n->pre=p;n->next=p->next;

21.png

  • 设置p结点的后驱结点为n结点。
p->next=n;

22.png

  • 设置结点n为其后驱结点的前驱结点。
n->next->pre=n;

23.png

编码实现:

//后插入int instertAfter(dataType val,dataType data) {    //按值查找到结点    LinkNode *p=this->findNodeByVal(val);    if (p==NULL) {        //结点不存在,返回 false        return false;    }    //创建新结点    LinkNode *n=new LinkNode();    n->data=data;    //设置 p 结点为新结点的前驱结点     n->pre=p;    //新结点的后驱结点为已知结点 p 的后驱结点    n->next=p->next;    //已知结点的后驱结点为新结点    p->next=n;      //已知结点的原后驱结点的前驱结点为新结点    n->next->pre=n;    return true;}

测试后插入:

int main(int argc, char** argv) {	LinkList list {};	//创建 7,3 两个结点    list.createFromTail(2);    //在结点 7 后面插入值为 9 的结点	list.instertAfter(7,9);	list.showSelf();    return ;}

执行结果:

24.png

2.4.2 前插入

把新结点插入到已知结点的前面,称为前插入,因结点有前驱结点的地址信息,双向链表的前或后插入都较方便。

  • 找到已知结点p,创建新结点n

25.png

  • 设置结点n的前驱结点为p的前驱结点,设置其后驱结点为p结点。
n->pre=p->pre;n-next=p;

26.png

  • 设置p结点的前驱结点的后驱结点为n
p->pre->next=n;或n->pre->next=n;

27.png

  • 设置p结点的前驱结点为n结点。
p->pre=n;

28.png

编码实现:

//前插入int insertBefore(dataType val,dataType data) {    //按值查找到结点    LinkNode *p=this->findNodeByVal(val);    if (p==NULL)        return false;    //查找前驱结点    LinkNode *p1=this->head;    while(p1->next!=p) {        p1=p1->next;    }    //构建新结点    LinkNode *n=new LinkNode();    n->data=data;    //新结点的后驱为 p 结点    n->next=p;    //新结点的前驱为 p 的前驱    n->pre=p->pre;    //p 的前驱结点的后驱结点为 n    p->pre->next=n;    //p 的前驱结点为 n    p->pre=n;    return true;}

测试前插入:

int main(int argc, char** argv) {	LinkList list {};	//创建 7,3 两个结点	list.createFromTail(2);    //在值为 7 的结点前面插入值为 9 的结点	list.insertBefore(7,9);	list.showSelf();    return ;}

执行结果:

29.png

2.5 删除

2.5.1 删除结点

删除已知结点的基本操作流程:

  • 查找到要删除的结点p

30.png

  • 找到结点p的前驱结点,设置其后驱结点为p的后驱结点。
p->pre->next=p->next;

31.png

  • 找到p结点的后驱结点,设置其前驱结点为p结点的前驱结点。删除p结点。
p->next->pre=p->pre;delete p;

32.png

编码实现:

int delNode(dataType data) {    //按值查找到要删除的结点    LinkNode *p= this->findNodeByVal(data);    if (p==NULL)return false;		    //设置 p 的前驱结点的后驱结点     p->pre->next=p->next;    p->next->pre=p->pre;    delete p;    return true;}

测试删除操作:

LinkList list {};//创建 {7,3,9} 3个结点list.createFromTail(3);//LinkNode *res= list.findNodeByValFromTail(4);list.delNode(3);list.showSelf();

执行结果:

33.png

2.5.2 删除所有结点

编码实现:

void delAll() {    LinkNode *p=this->head->next;    //临时结点    LinkNode *p1;    while(p!=this->head) {        //保留删除结点的后驱结点        p1=p->next;        delete p;        p=p1;    }    this->head=NULL;}

3. 算法案例

界定数列的要求:对于一个无序数列,首先在数列中找出一个基数,然后以基数为分界点,把小于基数的数字放在基数前面,反之放在后面。

3.1 演示流程

使用双向循环链表实现界定数列的流程。

  • 已知的无序数列:

1.png

  • 选择基数。这里选择第一个数字 7 作为基数。保存在临时变量 tmp中。声明 2 个变量 leftright,分别指向第一个数据和最后一个数据。

2.png

  • 从 right位置开始扫描整个数列,如果 right位置的数字大于 tmp中的值,则继续向左移动right指针直到遇到比 tmp中值小的数字,然后保存到 left位置。

3.png

  • left指针的工作要求:当所处位置的数字比tmp值小时,则向右边移动直到遇到比tmp值大的数字,然后保存至right

4.png

  • 重复上述过程,直到 leftright指针重合。

5.png

  • 最后把tmp中的值复制到leftright指针最后所指向的位置。最终实现以数字7界定整个数列。

6.png

3.2 算法实现

使用双向链表实现上述需求:

  • 初始化链表,并以尾部插入方式(保证数列的逻辑顺序和物理顺序一致)创建数列{7,3,1,9,12,5,8}
int main(int argc, char** argv) {	LinkList list {};		list.createFromTail(7);	//没删除之前	cout<<"显示创建结果:"<<endl; 	list.showSelf();	return ;}

执行后结果:

7.png

  • 编写界定算法。
void  baseNumBound() {    //第一个数据结点的数据作为界定数字    int tmp=this->head->next->data;    //左指针,指向第一个数据结点    LinkNode *left=this->head->next;    //右指针,指向尾结点    LinkNode *right=this->tail;    while(left!=right) {        while(left!=right && right->data>tmp) {            //右指针向左移动            right=right->pre;        }        left->data=right->data;        while(left!=right && left->data<tmp) {            //左指针向右移动            left=left->next;        }        right->data=left->data;    }    left->data=tmp;}

测试代码:

int main(int argc, char** argv) {	LinkList list {};	list.createFromTail(7);	//没删除之前	cout<<"显示链表的创建结果:"<<endl;	list.showSelf();	list.baseNumBound();	cout<<"\n显示界定后的数列:"<<endl;	list.showSelf();	return ;}

执行结果:
34.png

使用双向循环链表,实现界定数列简单、明了。

4. 总结

双向链表的结点多了一个前驱指针位,对其内部数据的维护提供了大大的便利。对于程序而言,已知数据越多,算法也将会有更大灵活伸缩空间。


标签:结点 前驱 链表
如何?NET核心Web APi类库内嵌运行?
« 上一篇 2022-09-24
  • 如何?NET核心Web APi类库内嵌运行?
    0阅读 0条评论 个赞
    话题我们知道在.NETFramework中可以嵌入运行WebAPi,那么在.NETCore(.NET6+称之为.NET)中如何内嵌运行WebApi呢,在实际项目中这种场景非常常见,那么我们本……
  • 尝试阅读和理解linux shell脚本
    0阅读 0条评论 个赞
    从头一二去阅读语法和命令说明,对于脚本小白来说比较枯燥,难以坚持,所以这里选择对一份完整的shell脚本代码来逐行逐段解读,希望可以一渡小白,帮助我们快速进入脚本的大门_。司机要开车了:#!/bin/……
  • NET通过代码部署多域Https(SSL)
    0阅读 0条评论 个赞
    在上一个文章中,传送门,给大家介绍了怎么在配置文件中使用Kestrel部署Https,正好今天有小伙伴稳问到:可以通过代码的方式实现Kestrel的Https的部署吗?答案是肯定的,我们这次……
  • SQL Server死锁
    0阅读 0条评论 个赞
    SQLServer死锁多个事务之间互相等待对方的资源,导致这些事务永久等待注意是永久等待,而非长事务死锁的4个条件互斥条件(Mutualexclusion):资源不能被共享,只能由一个进程使用。请……
  • 如何找到性能最差的SQL Server查询
    0阅读 0条评论 个赞
    我经常会被反复问到这样的问题:”我有一个性能很差的SQLServer。我如何找出最差性能的查询?“。因此在今天的文章里会给你一些让你很容易找到问题答案的信息向导。问SQLServer!SQLSe……
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表
  • 基于ASP.NET核心6.0的简洁架构
    0阅读 0条评论 个赞
    背景最近尝试录制了一个系列视频:《ASP.NETCore6.0+Vue.js3实战开发》,本节是视频内部整洁架构的理论和实战的文字稿。因为在录制之前,我通常会编写完整的文字内容作为视频文案,这……
  • 谈ASP.NET核心认证与授权
    0阅读 0条评论 个赞
    使用asp.netcore开发应用系统过程中,基本上都会涉及到用户身份的认证,及授权访问控制,因此了解认证和授权流程也相当重要,下面通过分析asp.netcore框架中的认证和授权的源码来分析……
  • 将SQL Server数据库迁移到Azure SQL
    0阅读 0条评论 个赞
    最近有个维护的项目需要把SQLServer2012的数据库迁移到AzureSQL上去,迁移过程可谓一波三折,故在此分享这次迁移中碰到的点点滴滴,希望对朋友们有所帮助。AzureSQL……
  • python入门系列(十)学习Python文件处理
    0阅读 0条评论 个赞
    文件处理在Python中处理文件的关键函数是open()函数。有四种不同的方法(模式)来打开一个文件"r"-读取-默认值。打开一个文件进行读取,如果文件不存在则出错。"a"-Append……
  • 记录一次数据库满CPU的故障排除过程
    0阅读 0条评论 个赞
    1前言近期随着数据量的增长,数据库CPU使用率100%报警频繁起来。第一个想到的就是慢Sql,我们对未合理运用索引的表加入索引后,问题依然没有得到解决,深入排查时,发现在orderbyida……
  • SQL SERVER存储过程学习笔记
    6阅读 0条评论 个赞
    将常用的或很复杂的工作,预先用SQL语句写好并用一个指定的名称存储起来,那么以后要叫数据库提供与已定义好的存储过程的功能相同的服务时,只需调用execute,即可自动完成命令。存储过程的优点1.存储……
  • 【高并发】从源码角度深入分析线程池如何优雅退出
    0阅读 0条评论 个赞
    大家好,我是冰河~~在【高并发专题】中,我们从源码角度深度分析了线程池中那些重要的接口和抽象类、深度解析了线程池是如何创建的,ThreadPoolExecutor类有哪些属性和内部类,以及它们对线程池……
  • 谈谈我是如何学习SQL Server的
    0阅读 0条评论 个赞
    谈谈我是如何学习SQLServer的相信很多人都想做大牛,但是你们知道这些大牛是怎样炼成的吗?我的一个同事做了差不多10年的.NET开发,算得上是大牛了吧?如果他遇到他熟悉的项目很快就能手到拿来,立……
  • springboot集成docsify实现可移植文档
    0阅读 0条评论 个赞
    需求分析文档可以和项目一起进行版本管理文档可以在线访问文档可以与springboot项目集成,不需要分开部署MarkDown支持文档跟随,打包jar也可以访问技术选型对于网上已有的方案,大致分为如下几……
  • Python自学教程7:字典类型有什么用
    0阅读 0条评论 个赞
    字典是Python中的一个重要操作,如果字典玩得顺,很多其他的数据类型就可以一通百通。Python字典的定义字典使用一对大括号进行定义,键值对之间使用逗号隔开,键和值使用冒号分隔。键必须是不可变类型,……
  • 【MySQL】DDL因正在等待表元数据锁定卡住
    0阅读 0条评论 个赞
    在数据库空闲时间,对表做碎片整理:1altertablemy_abcengine=innodb;发现会话被阻塞,显示状态是:1Waitingfortablemetadatalock手动断开alte……
  • 人工智能OPS的莫拉维克悖论
    3阅读 0条评论 个赞
    莫拉维克的悖论是人工智能和机器人研究人员观察到,与传统假设相反,推理需要很少的计算,但感觉运动和感知技能需要大量的计算资源。该原则由HansMoravec、RodneyBrooks、Marvin……
  • 中国台湾的建设:有效登陆中国台湾的六脉神剑
    0阅读 0条评论 个赞
    在数字化时代,数字化体系的建设需要的是系统化的规划和产品化的迭代的模式,基于企业核心业务能力体系,做中台化的持续建设与落地,则是一种不错的选择。所以,企业业务中台的建设和落地,是关系到企业数字化战略成……
  • 大促销活动如何抵御高流量DDoS攻击?
    0阅读 0条评论 个赞
    大促活动如何抵御大流量DDoS攻击?每一次活动大促带来的迅猛流量,对技术人而言都是一次严峻考验。如果在活动期间遭受黑产恶意DDoS攻击,无疑是雪上加霜。电商的特性是业务常态下通常不会遭受大流量DD……
  • 教你如何构建JAVA分布式爬虫
    0阅读 0条评论 个赞
    在工作中,我们经常需要去获取一些数据,但是这些数据可能需要从第三方平台才可以获取到。这个时候,爬虫系统就可以帮助我们来完成这些事情。提到爬虫系统,很多人都会想到使用python。但实际上,语言只……
  • SQL Server联接方式
    0阅读 0条评论 个赞
    0.参考文献MicrosoftSQLServer企业级平台管理实践看懂SqlServer查询计划1.测试数据准备参考:SqlServer中的表访问方式TableScan,IndexScan……
  • 码头工人日常工作的常用命令
    0阅读 0条评论 个赞
    容器生命周期管理Docker创建新容器并运行[run]语法:dockerrun[OPTIONS]IMAGE[COMMAND][ARG...]OPTIONS说明:-astdin:指定标准输入……
  • Java开发学习(29)——Maven依赖转移、可选依赖和排除依赖分析
    0阅读 0条评论 个赞
    现在的项目一般是拆分成一个个独立的模块,当在其他项目中想要使用独立出来的这些模块,只需要在其pom.xml使用标签来进行jar包的引入即可。其实就是依赖……
  • Java接口自动测试框架系列(1)自动测试框架
    0阅读 0条评论 个赞
    一、什么是自动化测试自动化测试是把以人为驱动的测试行为转化为机器执行的一种过程。通常,在设计了测试用例并通过评审之后,由测试人员根据测试用例一步步执行测试,得到实际结果与期望结果的比较。为了节省人力、……
  • 高手面试一个人 问4个问题就够了
    0阅读 0条评论 个赞
    作者|Mr.K编辑|Emma来源|技术领导力(ID:jishulingdaoli)金九银十求职季又要来了。据统计,今年的应届毕业生已破千万,加上社会面存量人才,相信今年的人才季的热度,不会低于今年……
最近发布资讯
更多