数组模拟链表(单链表,双链表)-程序员宅基地

技术标签: c++  链表  数据结构  

结构体+指针实现链表

struct Node {
    int val;
    Node* next;
};

每次创建一个新链表,就要调用new,new Node()这个操作非常慢,在笔试中一般不采用,会超时。

这里介绍用数组模拟链表,也称静态链表。

单链表:邻接表,用来存储图和树。

双链表:优化某些问题。

1.数组模拟单链表

e[N]数组来存储每个节点的值,用ne[N]数组来存储每个节点的next指针是多少。e数组和ne数组是由下标关联起来。空节点的下标用-1表示。

 初始化单链表

//head 表示头节点的next指向,即ne[头节点]
//e[i] 表示节点i的值
//ne[i] 表示节点i的next指针是多少
//idx 存储当前已经用到哪个点

//初始化链表
void init()
{
    head = -1;  //头节点指向空
    idx = 0;
}

插入操作

  • 插到头节点的位置

将节点nx插入到head与n0节点中间。

插入操作后

//将x插入到头节点
void add_to_head(int x)  //x为节点x存储的值
{
    e[idx] = x;  //设置x节点的值
    ne[idx] = head; //step1: x节点的next指向head的指向
    head = idx;  //step2-3: head指向x节点
    idx ++;  //当前可用节点后移
}

初始化链表+在头节点处插入一个值为6的节点,代码详细过程

  •  插到任意位置
//将x插入到节点k后面
void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++;
}

删除操作

删除n2节点,让n1的next指向n2的next指向(即n3)。

//删除节点k的下一个节点
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

2. 数组模拟双链表

l[N]来表示某节点左边指向的一个节点,用r[N]来表示某节点右边指向的一个节点。

初始化双链表

//初始化
void init()
{
    l[1] = 0;  //节点1的左边是节点0
    r[0] = 1;  //节点0的右边是节点1
    idx = 2;
}

插入操作

在节点k的右边插入一个新节点。

step2和step3先后顺序不能变,如果先修改n1的右指针,那么待会儿n1的右指针就不再指向n2,要修改n2的左指针就不能通过step2的方法了。

//在节点k的右边插入一个点
void add(int k, int x)
{
    e[idx] = x;
    l[idx] = k;  //step1,该节点的左指针指向k
    r[idx] = r[k];  //step1,该节点的右指针指向k的右节点
    l[r[k]] = idx;  //step2,节点k的右节点的左指针指向该节点
    r[k] = idx;  //step3,节点k的右指针指向该节点
    idx ++;
}

在节点k的左边插入一个数,即在节点k左节点的右边插入一个数,调用add(l[k],x)即可。

初始化链表+在节点0右边插入一个值为6的节点。

 删除操作

删除节点k。

//删除节点k
void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/rhyme1213/article/details/128756907

智能推荐

Live555学习之(五)------live555ProxyServer.cpp的学习_live555proxyserver http-程序员宅基地

文章浏览阅读965次。live555ProxyServer.cpp在live/proxyServer目录下,这个程序展示了如何利用live555来做一个代理服务器转发rtsp视频(例如,IPCamera的视频)。  首先来看一下main函数 1 int main(int argc, char** argv) 2 { 3 // Increase the maximum size of vid_live555proxyserver http

February——703. 数据流中的第 K 大元素&堆的总结以及API的使用_kth/api-程序员宅基地

文章浏览阅读103次。聊今天这个题目之前先聊聊一个数据结构:堆。堆又分为最大堆和最小堆。父节点的值总是大于或者等于任何一个子节点的值时为最大堆。父节点的值总是小于或者等用户任何一个子节点的值时为最小堆。其实说白了就是一个完全二叉树的数据结构。如下图所示,左边是最大堆,右边是最小堆。最大堆和最小堆的应用和优先队列差不多,每次都能弹出一个最大值或者最小值,当然在python中也有相应API。接下来堆API的方法大致说明一下:#导入堆import heapq#将list转化堆heapq.heapify(x)..._kth/api

TensorFlow Official ResNet-程序员宅基地

文章浏览阅读810次。项目地址:https://github.com/tensorflow/models/tree/master/official/resnet首先将models文件夹加入Python Path中,否则会报错ImportError: No module named official.resnetexport PYTHONPATH=$PYTHONPATH:models...

View 绘制流程_cchildview绘制-程序员宅基地

文章浏览阅读384次。本文为 Android 开源项目源码解析 公共技术点中的 View 绘制流程 部分分析者:lightSkyView 绘制机制1. View 树的绘图流程当 Activity 接收到焦点的时候,它会被请求绘制布局,该请求由Android framework 处理.绘制是从根节点开始,对布局树进行 measure 和 draw 。整个 View 树的绘图流程在ViewRoo_cchildview绘制

恒源云(GPUSHARE)_CIFAR-10数据集实战:构建ResNet18神经网络_resblk-程序员宅基地

文章浏览阅读121次。文章来源 | 恒源云社区原文地址 | 数据集实战原文作者 | Mathor实不相瞒,小编我对平台社区内的大佬Mathor很崇拜!这不,今天又来给大家分享大佬论文笔记了,赶紧看看接下来的内容是否有你们需要的知识点吧!正文开始:如果不了解ResNet的同学可以先看我的这篇博客ResNet论文阅读首先实现一个Residual Blockimport torchfrom torch import nnfrom torch.nn import functional as Fclass Res_resblk

JS中几种获取对象宽度和高度的区别_object列表高度-程序员宅基地

文章浏览阅读2k次。在JS中有多种获取高度和宽度的方式,今天整理一下1、clientWidth / clintHeightclientWidth = 元素的宽度 + 元素的paddingLeft + 元素的paddingRightclientHeight = 元素的高度 + 元素的paddingTop + 元素的paddingBottom注意:如果该元素上存在上下滑动滚动条,则clientWidth..._object列表高度

随便推点

Firewalld防火墙(二)_网站服务器和网关服务器均通过ssh来远程管理,将ssh默认端口改为12345-程序员宅基地

文章浏览阅读130次。Firewalld防火墙(二)一、 实验1、 要求(1) 网关服务器连接互联网(centos03)网卡ens32地址为192.168.100.30,为公网IP地址,分配到firewall的external区域;连接内网(centos04)网卡ens34地址为192.168.10.10,分配到firewall的trusted区域;连接服务器(centos05)网卡ens35地址为192.168.20.10,分配到firewall的dmz区域。(2..._网站服务器和网关服务器均通过ssh来远程管理,将ssh默认端口改为12345

升压电路(Boost)的设计原理、参数计算及MATLAB仿真_boost电路matlab仿真-程序员宅基地

文章浏览阅读2.4w次,点赞44次,收藏351次。升压(Boost)变换电路是一种输出电压大于等于输入电压的单管非隔离直流变换电路。升压变换电路是降压变换电路对偶拓扑结构,升压变换器由电流源(电压源串联较大电阻组成)、并联开关、电压源负载(并联电容)组成。通过控制开关管的占空比,进而控制输出电压的大小。_boost电路matlab仿真

Spring的<context:annotation-config>和<annotation-driven>-程序员宅基地

文章浏览阅读81次。<context:annotation-config> 相对于注册AutowiredAnnotationBeanPostProcessor、CommonAnnotationBeanPostProcessor、PersistenceAnnotationBeanPostProcessor以及RequiredAnnotationBeanPostProcessor这4个Bea..._

FileProvider-程序员宅基地

文章浏览阅读3.3k次,点赞3次,收藏6次。FileProvider我对FileProvider的理解 如下:android7.0开始,不再允许在app之间,使用file://的方式传递File,否则会抛出FileUriExposedException异常1,可以使用FileProvider,content://解决这个问题 2,也可以把targetSdkVersion小于24(&amp;gt;7.0),但我相信不会有人这样做...

Python3 压缩与解压缩(zlib / gzip / bz2 / lzma / zipfile / tarfile)_zlib解压 python3-程序员宅基地

文章浏览阅读6.8k次,点赞2次,收藏13次。Python3 压缩与解压缩(zlib / gzip / bz2 / lzma / zipfile / tarfile)文件的归档 (各种格式的压缩 / 解压缩)实际使用中仅需要使用shutil模块的压缩和解压函数就可以了, 如果想尝试其他功能, zipfile(暴力破解), tarfile(命令行)也是值得推荐的_zlib解压 python3

Tomcat环境变量配置_# tomcat environment-程序员宅基地

文章浏览阅读215次。计算机——属性——高级系统设置——环境变量——系统变量添加CATALINA_HOME变量,值就是Tomcat的根目录_# tomcat environment