当前位置: 首页 > news >正文

链表单向链表跳跃链表

单向链表  link list

t数组的局限:编译期就需要知道大小; 内存连续,插入困难

    // 链表节点类 包含一个信息 和指向下一个 节点的指针clas IntLLNode{public:IntLLNode(){// 默认构造函数   没有info信息nextPtr_ = 0;// 空指针}IntLLNode(int data, IntLLNode* in = 0){// 第二个构造函数info_    = data;nextPtr_ = in;}public:int info_;          // 包含一个信息          对用户很重要IntLLNode* nextPtr_;// 指向下一个 节点的指针  用于将节点连接起来组成链表}// 定义一个 节点指针IntLLNode* pt = new IntLLNode(10);//新建一个节点 其地址 赋给一个指向 IntLLNode 的指针 pt////   [pt]  ----> |  10 | 也就是 pt->info_   也就是 (*pt).info_//               |  \  | 也就是 pt->nextPtr_ 也就是 (*pt).nextPtr_ // 再定义一个节点pt->nextPtr  = new IntLLNode(30);//新建一个节点 其地址 赋给一个指向 IntLLNode 的指针 pt->nextPtr_////   [pt]  ----> |  10 |  //               |     |  -----> | 30 | 也就是 pt->nextPtr_->info_//                               | \  | 也就是 pt->nextPtr_->nextPtr_// 再定义一个节点pt->nextPtr_->nextPtr_  = new IntLLNode(50);//新建一个节点 其地址 赋给一个指向 IntLLNode 的指针 pt->nextPtr_->nextPtr_////   [pt]  ----> |  10 |  //               |     |  -----> | 30 |  //                               |    | ------> | 50 | 也就是  pt->nextPtr_->nextPtr_->info_//                                              |  \ | 也就是  pt->nextPtr_->nextPtr_->nextPtr_

使用 头结点和尾节点来存储链表结构

 //************************  intSLList.h  **************************// 单链表 实现类 #ifndef INT_LINKED_LIST#define INT_LINKED_LIST// 单个节点// 定义一个 节点指针// IntLLNode* pt = new IntLLNode(10);//新建一个节点 其地址 赋给一个指向 IntLLNode 的指针 pt////   [pt]  ----> |  10 | 也就是 pt->info_   也就是 (*pt).info_//               |  \  | 也就是 pt->nextPtr_ 也就是 (*pt).nextPtr_  class IntSLLNode {public:IntSLLNode() {// 默认构造函数   没有info信息next = 0;// 空指针}IntSLLNode(int data, IntSLLNode *ptr = 0) {// 第二个构造函数info = data; next = ptr;}public:    int info;         // 包含一个信息          对用户很重要IntSLLNode *next; // 指向下一个 节点的指针  用于将节点连接起来组成链表};// 链表 类  保存了一个 头节点 和 一个尾节点 class IntSLList {public:IntSLList() {// 默认构造函数  这里定义和实现 head = tail = 0;// 节点 和 一个尾节点 指针赋值为 空 }~IntSLList();// 默认析构函数  只有定义 实现在 cpp文件中 int isEmpty() {//为空链表是否 return head == 0;}void addToHead(int);   // 从头部添加 节点 void addToTail(int);   // 从尾部添加 节点 int  deleteFromHead(); // 从头部删除 节点 并返回该节点的信息 int  deleteFromTail(); // 从尾部删除 节点 并返回该节点的信息 void deleteNode(int);//删除 bool isInList(int) const;void printAll() const;//打印所有的节点的信息   private:IntSLLNode *head, *tail;// 保存了一个 头节点 和 一个尾节点};

#endif

实现类cpp intSLList.cpp

头部插入节点   head 和 tail  仅仅是保存了 一个(节点)存储的地址

   head ---> | 5 |  |   | ---> | 7 ||   | --->  |  4 | <-------- tail|    |新建一个节点                                 | 9 |  head ---> | 5 |  |   |            |   | ---> | 7 ||   | --->  |  4 | <-------- tail|    |   新节点指向 head 指向的地址   new IntSLLNode9, head);| 9 |  head ---> | 5 |  |   | ------->   |   | ---> | 7 ||   | --->  |  4 | <-------- tail原头结点指向新节点  head = new IntSLLNode(9,head);head --->  |   | | 9 |  |   | -------> | 5 |  |   | ---> | 7 ||   | --->  |  4 | <-------- tail

|   |

尾部插入一个节点

 head ---> | 5 |  |   | ---> | 7 ||   | --->  |  4 | <-------- tail|    |尾部新建一个节点     new IntSLLNode(9);                             head ---> | 5 |  |   | ---> | 7 ||   | --->  |  4 | <-------- tail|    |                 | 9 |   | \ |                                 tail指向的节点 指向这个新节点   tail->next = new IntSLLNode(9)head ---> | 5 |  |   | ---> | 7 ||   | --->  |  4 | <-------- tail|    | -------->   | 9 |   | \ | 尾节点tail 指向新的 尾节点   tail = tail->next;head ---> | 5 |  |   | ---> | 7 ||   | --->  |  4 | |    | -------->  | 9 |   <-------- tail| \ |                                 

双向向链表  link list  节点同时包含 指向前驱节点的指针 也包含 指向后继节点的指针

双向向链表

跳跃链表

跳跃链表

标准库中的链表 list #include

 //一些成员函数assign(iterator first, iterator last) 删除所有节点,在first到last插入元素assign(size_type n, el) 删除所有节点,向其中插入n个elback()  尾节点元素front() 第一个节点元素clear() 删除所有节点empty() 判断是否为空erase() 删除一个节点insert() 插入一个元素pop_back() 删除最后一个节点pop_front() 删除第一个节点push_back() 在表尾插入push_front() 在表头插入sort()       排序swap()      与另一个链表互换unique()   从有序链表中删除重复的元素

测试代码

#include <iostream>
#include <list>//链表 
#include <algorithm>// 算法 
#include <deque>//队列 
#include <functional>using namespace std;// 打印链表每一个元素 
template<class T>
void printList(const list<T>& lst, char *s) {cout << s << ":  ";for (typename list<T>::const_iterator i = lst.begin(); i != lst.end(); ++i)cout << *i << ' ';cout << endl;
}int main() {list<int> lst1;// 创建空链表                     printList(lst1,"lst1");     // lst1 is emptylist<int> lst2(3,7);            printList(lst2,"lst2");     // lst2 = (7 7 7)for (int j = 1; j <= 5; j++)// lst1 = (1 2 3 4 5)lst1.push_back(j);//尾后插入元素 list<int>::iterator i1 = lst1.begin(), i2 = i1, i3;i2++; i2++; i2++;list<int> lst3(++i1,i2);        printList(lst3,"lst3");     // lst3 = (2 3)list<int> lst4(lst1);printList(lst4,"lst4");     // lst4 = (1 2 3 4 5)i1 = lst4.begin();lst4.splice(++i1,lst2);         printList(lst2,"lst2");     // lst2 is emptyprintList(lst4,"lst4");     // lst4 = (1 7 7 7 2 3 4 5)lst2 = lst1;printList(lst2,"lst2");     // lst2 = (1 2 3 4 5)i2 = lst2.begin();lst4.splice(i1,lst2,++i2);      printList(lst2,"lst2");     // lst2 = (1 3 4 5)printList(lst4,"lst4");     // lst4 = (1 7 7 7 2 2 3 4 5)i2 = lst2.begin();i3 = i2;lst4.splice(i1,lst2,i2,++i3);printList(lst2,"lst2");     // lst2 = (3 4 5)printList(lst4,"lst4");     // lst4 = (1 7 7 7 2 1 2 3 4 5)lst4.remove(1);         printList(lst4,"lst4");     // lst4 = (7 7 7 2 2 3 4 5)lst4.sort();                            printList(lst4,"lst4");     // lst4 = (2 2 3 4 5 7 7 7)lst4.unique();                          printList(lst4,"lst4");     // lst4 = (2 3 4 5 7)lst1.merge(lst2);                        printList(lst1,"lst1");     // lst1 = (1 2 3 3 4 4 5 5),printList(lst2,"lst2");     // lst2 is emptylst3.reverse();                         printList(lst3,"lst3");     // lst3 = (3 2)     lst4.reverse();printList(lst4,"lst4");     // lst4 = (7 5 4 3 2)lst3.merge(lst4,greater<int>());  printList(lst3,"lst3");     // lst3 = (7 5 4 3 3 2 2)printList(lst4,"lst4");     // lst4 is emptylst3.remove_if(bind2nd(not_equal_to<int>(),3));printList(lst3,"lst3");     // lst3 = (3 3)lst3.unique(not_equal_to<int>());printList(lst3,"lst3");     // lst3 = (3 3)return 0;
}

相关文章:

链表单向链表跳跃链表

单向链表 link list t数组的局限&#xff1a;编译期就需要知道大小&#xff1b; 内存连续&#xff0c;插入困难 // 链表节点类 包含一个信息 和指向下一个 节点的指针clas IntLLNode{public:IntLLNode(){// 默认构造函数 没有info信息nextPtr_ 0;// 空指针}IntLLNode(int …...

博客无限滚动加载(html、css、js)实现

介绍 这是一个简单实现了类似博客瀑布流加载功能的页面&#xff0c;使用html、css、js实现。简单易懂&#xff0c;值得学习借鉴。&#x1f44d; 演示地址&#xff1a;https://i_dog.gitee.io/easy-web-projects/infinite_scroll_blog/index.html 代码 index.html <!DOCT…...

腾讯云南京服务器性能如何?南京服务器测速IP地址

腾讯云服务器南京地域怎么样&#xff1f;南京地域很不错&#xff0c;正好处于中间的位置&#xff0c;南方北方用户均可以选择&#xff0c;网络延迟更低速度更快&#xff0c;并且目前南京地域有活动&#xff0c;南京地域可用区可选南京一区、南京二区和南京三区&#xff0c;腾讯…...

MySQL和Oracle中,语法的不同点以及如何在xml中书写日期比较大小

众所周知mysql和oracle的语法有点相识&#xff0c;又有点不同。 在MySQL和Oracle中&#xff0c;语法的不同点有以下几个方面&#xff1a; 数据类型&#xff1a;MySQL和Oracle支持的数据类型有所不同&#xff0c;比如MySQL支持的数据类型包括&#xff1a;整型、浮点型、字符型、…...

谈谈Redis分布式锁

目录 一、回顾分布式锁 &#xff08;一&#xff09;理解分布式锁的定义 &#xff08;二&#xff09;分布式锁的约束条件 &#xff08;三&#xff09;分布式锁常见实现方式 基于数据库的分布式锁 基于缓存的分布式锁 基于分布式一致性算法的分布式锁 基于文件系统的分布…...

Redis的java客户端-RedisTemplate光速入门

一.创建springboot项目 二.引入2个依赖 <!-- redis依赖-->这个已经引入了&#xff0c;因为创建的时候勾选了<dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId><…...

格点数据可视化(美国站点的日降雨数据)

获取美国站点的日降雨量的格点数据&#xff0c;并且可视化 导入模块 from datetime import datetime, timedelta from urllib.request import urlopenimport cartopy.crs as ccrs import cartopy.feature as cfeature import matplotlib.colors as mcolors import matplotli…...

YoloV8改进策略:LSKNet加入到YoloV8中,打造更适合小目标的YoloV8

文章目录 摘要论文:LSKNet:大选择核网络在遥感目标检测中的应用1、简介2、相关工作2.1、遥感目标检测框架2.2、大核网络2.3、注意力/选择机制3、方法3.1、LSKNet架构3.2、大核卷积3.3、空间核选择4、实验4.1、数据集4.2、实现细节4.3、消融实验4.4、主要结果4.5、分析5、结论…...

力扣-303.区域和检索-数组不可变

Idea 需计算数组nums在下标right 和 left-1 的前缀和&#xff0c;然后计算两个前缀和的差即可。 需要注意的是&#xff0c;当left为0的时候&#xff0c;如果还是left-1则会发生数组访问越界错误。 AC Code class NumArray { public:vector<int> sum;NumArray(vector<…...

web:[极客大挑战 2019]LoveSQL

题目 打开页面显示如下 查看源代码&#xff0c;查到一个check.php&#xff0c;还是get传参 尝试账号密码输入 题目名为sql&#xff0c;用万能密码 1or 11# 或 admin or 11 给了一段乱码&#xff0c;也不是flag 查看字段数 /check.php?usernameadmin order by 3%23&pass…...

数据结构—快速排序(续)

引言&#xff1a;在上一篇中我们详细介绍了快速排序和改进&#xff0c;并给出了其中的一种实现方式-挖坑法 但其实快速排序有多种实现方式&#xff0c;这篇文章再来介绍其中的另外两种-左右指针法和前后指针法。有了上一篇挖坑法的启示&#xff0c;下面的两种实现会容易许多。 …...

Snapdragon Profiler分析Android GPU

Snapdragon Profiler&#xff08;骁龙分析器&#xff09;是一款性能分析软件&#xff0c;在Windows、 Mac、和 Linux平台上都可以运行&#xff0c;主要是用来分析使用了高通骁龙处理器的Android设备。 Snapdragon Profiler通过USB连接这些Android设备&#xff0c;开发者可以用…...

Cannot download sources:IDEA源码无法下载

问题 Swagger的相关包&#xff0c;无法看到注释&#xff1b; 在class文件的页面&#xff0c;点击下载源码&#xff0c;源码下载不了&#xff0c;IDEA报下面的错误。 报错 Cannot download sources Sources not found for: io.swagger.core.v3:swagger-annotations:2.2.9 解决…...

从零开始学习 Java:简单易懂的入门指南之IO字符流(三十一)

IO流之字符流 1. 字符流1.1 字符输入流【Reader】1.2 FileReader类构造方法读取字符数据 1.3 字符输出流【Writer】1.4 FileWriter类构造方法基本写出数据关闭和刷新写出其他数据 2. IO异常的处理JDK7前处理JDK7的处理JDK9的改进 3. 综合练习练习1&#xff1a;拷贝文件夹练习2&…...

监狱工具管理系统-监狱劳动工具管理系统

监狱劳动工具管理系统(智工具DW-S308)是依托互3D技术、云计算、大数据、RFID技术、数据库技术、AI、视频分析技术对工具进行统一管理、分析的信息化、智能化、规范化的系统。 当前各级监狱工器具管理更多的是借助于传统的人工管理方法和手段&#xff0c;数据的采集和录入一直以…...

蓄水池算法

题目&#xff1a; 假设有一组数据流元素有 N 个&#xff08;事先不知道 N 具体值&#xff09;&#xff0c;我们希望选择 n 个样本&#xff08;N > n&#xff09;&#xff0c;使用怎样的策略进行抽样可以使得数据流中每个元素被选择的概率恰为 n / N 结论&#xff1a; 创建大…...

作业 day4

完成父子进程通信...

erlang练习题(四)

题目一 传入列表 L1[K|]、L2[V|]、L3[{K,V}|_]&#xff0c;L1和L2一一对应&#xff0c;L1为键列表&#xff0c;L2为值列表&#xff0c;L3为随机kv列表&#xff0c; 将L1和L2对应位合并成KV列表L4&#xff0c;再将L3和L4相加&#xff0c;相同key的value相加 如&#xff1a;L…...

YoloV5实时推理最短的代码

YoloV5实时推理最简单代码 import cv2 import torch# 加载YOLOv5模型 model torch.hub.load(ultralytics/yolov5, yolov5s)# 使用CPU或GPU进行推理 device cuda if torch.cuda.is_available() else cpu model.to(device)# 打开摄像头&#xff08;默认摄像头&#xff09; cap…...

Tensorflow、Pytorch和Ray(张量,计算图)

1.深度学习框架&#xff08;Tensorflow、Pytorch&#xff09; 1.1由来 可以追溯到2016年&#xff0c;当年最著名的事件是alphago战胜人类围棋巅峰柯洁&#xff0c;在那之后&#xff0c;学界普遍认为人工智能已经可以在一些领域超过人类&#xff0c;未来也必将可以在更多领域超过…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!

目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...