C++基础语法:STL之容器(4)--序列容器中的list(一)

前言

       "打牢基础,万事不愁" .C++的基础语法的学习

引入


        序列容器的学习.以<C++ Prime Plus> 6th Edition(以下称"本书")内容理解

        本书中容器内容不多只有几页.最好是有数据结构方面的知识积累,如果没有在学的同时补上.

        序列容器回顾:序列容器内元素按严格线性顺序排列,至少是正向迭代器(含以上).序列容器包括deque(双端队列),forward_list(单链表),list(双向链表),queue(队列),priority_queue(优先队列),stack(栈),vector(动态数组),array(替代数组的容器

list(双向链表) 

        list所占篇幅相对其他容器类算比较大的,而且有专属的api介绍.

        list双向链表,和单链表比较起来,在结点上多了个指向前面一个元素的指针.

        本书内容解读 

        第1部分:  list模板类(在list头文件中声明)表示双向链表。除了第一个和最后一个元素外,每个元素都与前后的元素相链接,这意味着可以双向遍历链表。list和vector之间关键的区别在于,list在链表中任一位置进行插入和删除的时间都是固定的(vector模板提供了除结尾处外的线性时间的插入和删除,在结尾处,它提供了固定时间的插入和删除)。因此,vector强调的是通过随机访问进行快速访问,而list强调的是元素的快速插入和删除 (本书原话)

         ----蓝色部分是list应用场景,切记

         ----代码和解读:

        注意:下列代码为了练手,试图重现逻辑,不保证准确.          

template<class T>
class list{enum{MAX=10}int lsize;                //list最大元素数量int items;                //list内当前的元素个数class Node{               //声明结点类public:                   //结点数据向外部类公开T t;Node *front;Node *next;Node(T val):t(val),front(0),next(0){}Node(){}              //默认构造函数,为初始化时使用}Node* first;Node* last;
public:list(int num=MAX);        //构造函数   void add(Node* n,T& t);   //添加元素t到结点n后面T remove(Node* n);        //删除地址为n的结点
}

        1>构造函数,建立初始的list

        说明:first按照"头结点"定义,数据域为空的结点,初始化时没有元素,所以last也指向头结点.

template<class T>
list::list(int num=MAX):lsize(num){ //初始化list,没有元素时的情况items=0;                        //初始时元素个数为0Node *newNode=new Node;         //创建数据域为空的结点first=newNode;                  //头结点指向空结点;last=newNode;                   //末结点指向空结点;//  last->next=first;               //如果加上这句,末结点后面的结点指向头结点,形成环状list//这里不加,仍然是一根链条似的list,加了变复杂用处也不大,不加
}

        2>添加元素

        把结点地址作为参数,作为插入元素的条件,向序列要求函数中的迭代器靠拢.

template<class T>
void list<T>::add(Node* n,T& t){Node* newNode=new Node(t);    //生成新结点,传入数据
/*新结点后面是谁*/newNode->next=n->next;n->next->front=newNode;
/*新结点在谁后面*/n->next=newNode;newNode->front=n;
/*第一次插入后,新结点成为尾结点,并在头结点后面*/if(items==0){                //第一次插入时情况:区分first和lastnewNode->next=nullptr;   //新结点后面指空last=newNode;            //新结点成了尾结点first->next=newNode;     //first当上了头结点newNode->front=first;    //两个方向说明first当上了头结点}            
//  if(n==first)
//      first->next=newNode;     //插入在头结点之后,前面代码已符合不用重复if(n==last)                 last=newNode;            //如果在末尾插入,尾结点指向新结点仍是尾结点items++;                     //list元素个数加1
}

        3>删除某个位置的结点 

template<class T>
T list<T>::remove(Node* n){Node* tmp=n;                //标识要删除的结点/*把要删除的结点从list里面剥离出来*/n->next->front=n->front;    //该结点后面结点的front指向该结点前面那个结点n->front->next=n->next;     //该结点前面那个结点的next指向该结点后面if(n==last)                 //如果删除的是尾结点last=n->front;         //尾结点指向删除结点的前一个结点T t=tmp->t;                 //标识结点的数据取出来delete tmp;                 //删除标识结点items--;                    //删除结点,元素个数减1return t;                   //返回原结点内数据
}        

================================内容分割线=================================

做几个小分析:

        1.构造函数用了两个,如果只有下面这个,建立空结点不知道能不能成功,笔者未尝试.

          在C语言中,声明一个结构体并且malloc,好像不用给数据也没错,C++的检查更严格.

Node(T val):t(val),front(0),next(0){}

        2.关于环状list

          如果采用"环状"list,那么后面的代码中last不能指空,而要指向first.其他算法可能会有区别

           在插入,删除或者查找中,环状list未必能达到好的效果.考虑到一种场景:list很长,查询数据时查一半不找了,往回查找走,这时考虑用环状list.如图:

     有兴趣可以尝试做个环状list,再写个查找算法.

     不过数据多了有更好的选择,比如二叉树等,所以感觉实用性不大.

        3. 头结点  

        头结点实际上是"人造"的.他的用途是方便元素在头部插入和删除.是否选择用头结点在于程序员.如果不做头结点,让头部插入的结点成为首个结点,那么代码要做一些修改,代码要多一点.

        4.第一次插入时的描述

        以下是函数add里的部分代码:

/*第一次插入后,新结点成为尾结点,并在头结点后面*/if(items==0){                //第一次插入时情况:区分first和lastnewNode->next=nullptr;   //新结点后面指空last=newNode;            //新结点成了尾结点first->next=newNode;     //first当上了头结点newNode->front=first;    //两个方向说明first当上了头结点}

        参照本书P614,链队列的"入队"算法enque,开始时first和last都指向同一个空结点,将第一次插入和其他次插入分开,才可以在逻辑上区分first和last,保证后面的程序正确. 

        5.程序中的"一般"和"特别"

        add中的部分代码 

//  if(n==first)
//      first->next=newNode;     //插入在头结点之后,前面代码已符合不用重复if(n==last)                 last=newNode;            //如果在末尾插入,尾结点指向新结点仍是尾结点

        当写完add后,如果想在头结点后插入元素,代入first,发现逻辑仍成立,所以注释部分属于多余描述;而当在末尾结点插入元素,代入last,函数执行完毕后发现尾结点位置没变,所以给了if做补充. 

        函数代入的形参可以被看作是所有可能的组合 ,表示"一般"性.当一般性不能满足所有情况,需要用"特殊"的描述做补充,这也是程序调试的重要性所在.

        6.尾结点last为什么有时候需要有时候不需要?

        对比以前的数据结构单链表C++基础语法:链表和数据结构-CSDN博客和链队列,他们一个没有尾结点,一个有尾结点,list也有尾结点.而链队列和list的共同特征是需要在"尾部"插入和删除元素,因此定义了尾结点last并实现了他.而使用"头插法"的单链表既没有"尾部"的概念,也没有"尾结点"存在.与此相对应的,头结点(指向首个元素的结点)是必须存在的,因为靠他遍历到容器内所有数据.

        同时定义了list的最大元素个数items,但并没有使用他,所以本例的链表可以无限长 

        结论:容器里的属性是根据需要定义并实现的

        7.迭代器

        此前迭代器让人挠头,迭代器类里的属性复刻了容器里的数据(因为容器里都是数据集合,所以属性是容器集合的指针),所以迭代器实际上是对数据的二重访问和修改.提升了"同一性"(每个容器里都有个迭代器类).在容器类里对元素的增删改搬到迭代器里去了,然后做接口被容器类对象访问.

        迭代器做参数,先转化成对应的指针即可.本例的指针做参数和迭代器做参数已非常接近 

        8.函数的"冗余"

        在序列函数中,有push_front()函数,为了在容器头部插入数据,有了add()函数也一样可以实现.为什么要这样做呢?

        原因和"迭代器"一样,他是为了同属于序列容器"同一性"提供的api,而且也容易实现,把参数传给add()就行了. 

================================内容分割线================================ 

         第2部分:与vector相似,list也是可反转容器。与vector不同的是,list不支持数组表示法和随机访问。与矢量迭代器不同,从容器中插入或删除元素之后,链表迭代器指向元素将不变。我们来解释一下这句话。例如,假设有一个指向vector容器第5个元素的迭代器,并在容器的起始处插入一 个元素。此时,必须移动其他所有元素,以便腾出位置,因此插入后,第5个元素包含的值将是以前第4个元素的值。因此,迭代器指向的位置不变,但数据不同。然后,在链表中插入新元素并不会移动已有的元素,而只是修改链接信息。指向某个元素的迭代器仍然指向该元素,但它链接的元素可能与以前不同。

        ----解读:这段比较容易理解:如果支持随机访问,那么两次访问到的数据不能改变.而list(包括其他链表)在插入和删除后,原数据的位置发生改变,再次用位置访问到的数据和之前不一样了,所以不能随机查找,而只能通过遍历来搜寻.

小结

        list双向链表的一些理解.

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/380412.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

css前端面试题

1.什么是css盒子模型&#xff1f; 盒子模型包含了元素内容&#xff08;content&#xff09;、内边距&#xff08;padding&#xff09;、边框&#xff08;border&#xff09;、外边距&#xff08;margin&#xff09;几个要素。 标准盒子模型和IE盒子模型的区别在于其对元素的w…

食家巷香豆烤馍:传统美味,唇齿留香

你是否在寻找一种能唤醒童年记忆的美食&#xff1f;是否又在渴望一种既能充饥又能享受的美味&#xff1f;那么&#xff0c;食家巷的香豆烤馍&#xff0c;一定能满足你的味蕾。 香豆烤馍&#xff0c;以优质的原料、精致的制作和独特的口味&#xff0c;让食家巷香豆烤馍在众…

[React 进阶系列] useSyncExternalStore hook

[React 进阶系列] useSyncExternalStore hook 前情提要&#xff0c;包括 yup 的实现在这里&#xff1a;yup 基础使用以及 jest 测试 简单的提一下&#xff0c;需要实现的功能是&#xff1a; yup schema 需要访问外部的 storage外部的 storage 是可变的React 内部也需要访问同…

数据库第二次作业

1.建立数据库 2.插入数据 3.完成查询 &#xff08;1&#xff09;、显示所有职工的基本信息。 &#xff08;2&#xff09;、查询所有职工所属部门的部门号&#xff0c;不显示重复的部门号。 &#xff08;3&#xff09;、求出所有职工的人数。 &#xff08;4&#xff09;、列…

iPhone手机上备忘录怎么设置字数显示

在日常生活和工作中&#xff0c;我经常会使用iPhone的备忘录功能来记录一些重要的想法、待办事项或临时笔记。备忘录的便捷性让我可以随时捕捉灵感&#xff0c;但有时候&#xff0c;我也会苦恼于不知道自己记录了多少内容&#xff0c;尤其是在需要控制字数的时候。 想象一下&a…

NAS新品“翻车”后,绿联科技要上市了

在消费电子市场回暖的东风中&#xff0c;又一消费电子知名企业登陆A股。 近日&#xff0c;深圳市绿联科技股份有限公司&#xff08;下称“绿联科技”&#xff09;开启申购&#xff0c;将在创业板上市。本次上市&#xff0c;绿联科技的发行价为21.21元/股&#xff0c;发行数量为…

鸿蒙OpenHarmony Native API【HiLog】

HiLog Overview Description: HiLog模块实现日志打印功能。 开发者可以通过使用这些接口实现日志相关功能&#xff0c;输出日志时可以指定日志类型、所属业务领域、日志TAG标识、日志级别等。 syscap SystemCapability.HiviewDFX.HiLog Since: 8 Summary Files File …

几种基本数据结构

目录 前言 线性结构 链式结构 单链表 双链表​编辑 树形结构 前言 在我们编写程序时&#xff0c;经常会出现需要存储数据的情况&#xff0c;而数据的存储是有讲究的&#xff0c;数据不是在我们的内存中胡乱存储&#xff0c;为了保证数据在进行修改和查找时更加方便&#…

高德api获取天气(详细步骤)

1.登录高德开放平台&#xff0c;点击创建新应用&#xff0c;输入应用名称&#xff0c;选择应用类型&#xff0c;然后点击创建 2.点击添加key&#xff0c;按照以下步骤&#xff1a; 3.然后提交后点开就能看到你的key 4.以下就是示例代码&#xff1a; <!-- 高德获取天气坐标…

扩展PyTorch视觉模型

扩展PyTorch视觉模型 目录 扩展PyTorch视觉模型 一、概述 二、扩展基本视觉模型的原因 1. 性能提升 2. 功能扩展 3. 资源管理 三、扩展PyTorch视觉模型的方法 1.修改现有架构 2.应用模型集成技术 3.量化和压缩模型 四、高级技巧与实践 1.自定义训练循环 2.深度模型…

Visio绘制的CBAM结构图,无水印,可修改,能导出高清图片,可用于论文写作

Visio绘制的CBAM网络结构图,可导出高清图片&#xff0c;可修改&#xff0c;无水印。 方便用于小论文写作&#xff0c;方便用于毕业设计。 Visio版本为2021版&#xff0c;可用更高版本打开。 下载地址&#xff1a;cbam 图片展示&#xff1a;

超算网络体系架构-资源层-平台层-服务层-应用层

目录 超算网络体系架构 我国超算基础设施 超算互联网相关标准研制方面 技术架构 资源层 基础资源 芯片多样 体系异构 高效存储 高速互连 资源池化 可隔离 可计量 互联网络 高带宽 低时延 高安全 平台层 算力接入 资源管理 算力调度 用户管理 交易管理 模…

CVE-2024-24549 Apache Tomcat - Denial of Service

https://lists.apache.org/thread/4c50rmomhbbsdgfjsgwlb51xdwfjdcvg Apache Tomcat输入验证错误漏洞&#xff0c;HTTP/2请求的输入验证不正确&#xff0c;会导致拒绝服务&#xff0c;可以借助该漏洞攻击服务器。 https://mvnrepository.com/artifact/org.apache.tomcat.embed/…

【云原生】Prometheus整合Alertmanager告警规则使用详解

目录 一、前言 二、Altermanager概述 2.1 什么是Altermanager 2.2 Altermanager使用场景 三、Altermanager架构与原理 3.1 Altermanager使用步骤 3.2 Altermanager工作机制 3.3 Altermanager在Prometheus中的位置 四、Altermanager部署与接入Prometheus 4.1 Altermana…

nodejs安装+踩坑报错解决

下载Node.js安装包 官网下载地址&#xff1a;http://nodejs.cn/download/&#xff0c;根据自己电脑选择32位还是64位&#xff0c; 下载地址 选择合适的版本下载 X86是32位的&#xff0c;X64是64位的&#xff0c;我们一般是下载win版X64的msi文件的是点击可以直接启动安装程序的…

深入Redis集群部署:从安装配置到测试验证的完整指南

&#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f427;Linux基础知识(初学)&#xff1a;点击&#xff01; &#x1f427;Linux高级管理防护和群集专栏&#xff1a;点击&#xff01; &#x1f510;Linux中firewalld防火墙&#xff1a;点击&#xff01; ⏰️创作…

恶补,先验分布,后验分布 ,似然估计

恶补&#xff0c;打一遍增加印象 先验分布后验分布&#xff0c;似然估计 声明&#xff1a;仅记录个人学习&#xff0c;并无其他用途。 先验分布 后验分布&#xff0c; 似然估计 隔壁小哥的故事&#xff1a; 隔壁小哥要去15公里外的一个公园里玩&#xff0c;小哥可以选择步行…

SimMIM:一个类BERT的计算机视觉的预训练框架

1、前言 呃…好久没有写博客了&#xff0c;主要是最近时间比较少。今天来做一期视频博客的内容。本文主要讲SimMIM&#xff0c;它是一个将计算机视觉&#xff08;图像&#xff09;进行自监督训练的框架。 原论文&#xff1a;SimMIM&#xff1a;用于掩码图像建模的简单框架 (a…

IDEA的常见代码模板的使用

《IDEA破解、配置、使用技巧与实战教程》系列文章目录 第一章 IDEA破解与HelloWorld的实战编写 第二章 IDEA的详细设置 第三章 IDEA的工程与模块管理 第四章 IDEA的常见代码模板的使用 第五章 IDEA中常用的快捷键 第六章 IDEA的断点调试&#xff08;Debug&#xff09; 第七章 …

数据实时获取方案之Flink CDC

目录 一、方案描述二、Flink CDC1.1 什么是CDC1.2 什么是Flink CDC1.3 其它CDC1.4 FlinkCDC所支持的数据库情况 二、使用Pipeline连接器实时获取数据2.1 环境介绍2.2 相关版本信息2.3 详细步骤2.3.1 实时获取MySQL数据并发送到Kafka2.3.2 实时获取MySQL数据并同步到Doris数据库…