首页 > 其他分享 >信友队集训营--1--链表

信友队集训营--1--链表

时间:2024-08-03 09:50:17浏览次数:15  
标签:idx -- next 链表 插入 集训营 节点

算法随笔(1): 信友队集训营--1--链表

链表

单向链表

计算机常见的两种存储结构分别是顺序存储链式存储

顺序存储(以数组方式呈现)

优点有:操作方便,随机存取,查找元素的时间复杂度为O(1)

缺点有:需要预设空间,过大浪费,过小越界。插入或删除元素不方便,需要O(N)的复杂度

链式存储(以链表方式呈现)

优点有:存储空间是动态分配的,只要计算机内存还有,就不会溢出。插入、删除元素方便,时间复杂度均为O(1)

缺点有:查找元素不方便,需要O(N)的时间复杂度

链表中节点的联系

为了表示每个元素与后继元素的逻辑关系,以便构成“一个节点链着一个节点”的链表,每个节点除了存储元素本身的信息外,还要存储其后继节点的地址,这样通过地址能形成链接。

即每个节点包含两个部分:存储元素本身的数据域存储下一个节点地址的指针域(如下图)

单链表

链表中的第一个节点称为头结点,最后一个节点,称为尾节点,头结点一板不存储数据,尾节点的指针为空(NULL)

链表一般分为:单向链表,循环链表,双向链表,而这种就是单向链表

单链表的建立

了解了链表的相关概念后,要如何建立并使用一个单链表呢?

第一步:定义结构体存储节点信息

struct uuu{
   int data;
   uuu *next;
};

第二步:创建头结点和尾节点

头结点起带头作用,尾节点用于新增节点

c++中使用new运算符来动态申请空间,格式:数据类型 指针变量 = new 数据类型;

uuu *head,*tail;
head=new uuu;//申请空间
head->next=NULL
tail=head;

第三步:创建多个新节点,并依次链接到链表的尾节点之后

long long n;
uuu *p;
for(long long i=1;i<=n;i++)
{
    p=new uuu;
    cin>>p->data;
    p->next=NULL;
    tail->next=p;
    tail=p;
}

单链表的操作--打印

p->next=NULL;
while(p!=NULL)
{
    cout<<p->data<<" ";
    p=p->next;
}

单链表的操作--查找

查找链表中值为x的点

p=head->next;
while(p->data!=x && p->next!=NULL)
{
    p=p->next;
}

单链表的操作--删除

删除节点p的下一个节点

p->next=p->next->next;

单链表的操作--插入

在单链表的p节点之后插入一个节点

s->next=p->next;
p->next=s;

循环链表

单向循环链表是另一种形式的链式存储结构。它的特点是表中最后一个节点的指针域指向头结点,整个链表形成一个环

tail->next=head;

双向链表

双向链表中的每一个节点都有两个指针域和若干个数据域,其中一个指向前面,一个指向后面。优点是:访问、插入、删除更方便。但是就是要以空间复杂度来换时间复杂度

双向链表的建立

struct uuu{
    long long data;
    uuu *pre,*next;
};

双向链表的操作--删除

p->pre->next=p->next;
p->next-pre=p->pre;

双向链表的操作--插入

在p节点后插入一个s节点

s->next=p->next;
p->next->pre=s;
s->pre=p;
p->next=s;

练习

用数组模拟实现双链表

·双链表的一个节点包括节点的值、节点的left指针、节点的right指针。

·left指针存储该节点的左侧节点的下标;right指针存储该节点的右侧节点的下标。

·数组e、数组l、数组r通过下标相等,每三个关联作为一个完整的节点即e[2],l[2],r]2];e[3],l[3],r[3];e[4],l[4],r[4]……

1.初始化

首先,进行初始化:
将下标为0的位置设为左端点,将下标为1的位置十位右端点,两端点不存储e值,idx表示即将使用到的数组下标

void init()//初始化
{
    r[0]=1;//右指针
    l[1]=0;//左指针
    idx=2;
}

插入操作

假如要在位置k的右边插入第idx个数字x,操作如下:

e[idx]=x;//赋值
r[idx]=r[k];//将x的右指针指向位置k的下一个
l[idx]=k;//将
l[r[k]]=idx;
r[k]=idx;

删除操作

加入要删除位置为k的元素,操作如下:

r[l[k]]=r[k];
l[r[k]]=l[k];

最终练习

【题目描述】

实现一个双链表,双链表初始为空,支持5种操作:

在最左侧插入一个数;

在最右侧插入一个数;

将第k个插入的数删除;

在第k个插入的数左侧插入一个数;

在第k个插入的数右侧插入一个数;

现在要对该链表进行M次操作,

进行完所有操作后,从左往右输出整个链表。

【题目解析】

思路1

用 STL模板库中自带的list容器进行模拟

TLE 80分

就算是开了O2优化,也只有80分

为什么呢,主要问题就出现在第三、四、五个操作上,需要O(n)的复杂度来查找,那么怎么优化呢,用我们上面讲的数组的方法就行

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int l[N],r[N],e[N],idx;
void add(int k,int x)//插入
{
	e[idx]=x;
	r[idx]=r[k];
	l[idx]=k;
	l[r[k]]=idx;
	r[k]=idx;
	idx++;
}
void del(int k)//删除
{
	r[l[k]]=r[k];
	l[r[k]]=l[k];
}
int main()
{
	int m;
	l[1]=0;
	r[0]=1;
	idx=2;
	cin>>m;
	while(m--)
	{
		string a;
		cin>>a;
		int x,k;
		if(a=="L")
		{
			cin>>x; 
			add(0,x);
		}
		else if(a=="R")
		{
			cin>>x;
			add(l[1],x);
		}
		else if(a=="D")
		{
			cin>>k;
			del(k+1);
		}
		else if(a=="IL")
		{
			cin>>k>>x;
			add(l[k+1],x); 
		}
		else if(a=="IR")
		{
			cin>>k>>x;
			add(k+1,x);
		}
	}
	for(int i=r[0];i!=1;i=r[i])
    {
        cout<<e[i]<<" ";
    }
}

标签:idx,--,next,链表,插入,集训营,节点
From: https://www.cnblogs.com/sfs-sf/p/18340072

相关文章

  • [lnsyoj2233]咏叹
    题意给定\(n\)行\(n\)列的网格地图\(g\),包含空地(.)和障碍(#),其中包括玩家(P)和敌人(E)。敌人会按照玩家\(k\)回合前的操作进行移动。记移动到边界外或障碍上为移动失败,移动失败后,此移动不作数。求玩家没有移动失败,且在\(m\)轮内,使敌人移动失败恰好\(hp\)次的移动序列的方案数......
  • 标识符
    2.2标识符目录2.2标识符2.2.1命名规则一、标识符的含义二、命名规则(硬性要求)三、命名规范(非硬性要求)2.2.2驼峰命名法一、概念二、小驼峰命名法三、大驼峰命名法2.2.1命名规则一、标识符的含义标识符的含义是指在程序中,我们自己定义的内容;譬如,类的名字,方法名称以及......
  • 关键字和保留字
    2.1关键字和保留字下面列出了Java关键字。这些保留字不能用于常量、变量、和任何标识符的名称。类别关键字说明访问控制private私有的protected受保护的public公共的default默认类、方法和变量修饰符abstract声明抽象class类extend......
  • Burp Suite Professional 2024.7 for macOS x64 & ARM64 - 领先的 Web 渗透测试软件
    BurpSuiteProfessional2024.7formacOSx64&ARM64-领先的Web渗透测试软件世界排名第一的Web渗透测试工具包请访问原文链接:https://sysin.org/blog/burp-suite-pro-mac/,查看最新版。原创作品,转载请保留出处。BurpSuiteProfessionalTheworld’s#1webpenetrati......
  • Burp Suite Professional 2024.7 for Windows x64 - 领先的 Web 渗透测试软件
    BurpSuiteProfessional2024.7forWindowsx64-领先的Web渗透测试软件世界排名第一的Web渗透测试工具包请访问原文链接:https://sysin.org/blog/burp-suite-pro-win/,查看最新版。原创作品,转载请保留出处。BurpSuiteProfessionalTheworld’s#1webpenetrationtes......
  • VMware NSX 4.1.2.5 发布,新增功能概览 (32 个已知问题修复)
    VMwareNSX4.1.2.5发布,新增功能概览(32个已知问题修复)VMwareNSX4.1.2.5下载-网络安全虚拟化平台构建具有网络连接和安全性的云智能网络,跨多种云环境支持一致的策略、运维和自动化。请访问原文链接:https://sysin.org/blog/vmware-nsx-4/,查看最新版。原创作品,转载请保......
  • 分支结构
    分支结构目录分支结构一、分支结构分类单一分支双分支多分支switch语句二、应用场景三、设计原则一、分支结构分类单一分支单一分支结构是最简单的分支结构,它只有一个条件判断,当条件为真(True)时执行一段代码,否则不执行任何操作。例如,使用if语句实现:if(条件){//条......
  • m3u8下载工具N_m3u8DL-CLI的图形界面增强版
    摘自:https://zhuanlan.zhihu.com/p/672615148 简介(仅windows)N_m3u8DL-CLI是个非常方便的开源免费m3u8下载工具,自带一个叫SimpleGUI的简单图形界面。但是这个图形界面工具,太过简单,连任务列表都没有。所以,这里二次开发,增加了任务列表功能。新增的所有功能,请在项目页面查看详......
  • SmolLM: 一个超快速、超高性能的小模型集合
    简介本文将介绍SmolLM。它集合了一系列最尖端的135M、360M、1.7B参数量的小模型,这些模型均在一个全新的高质量数据集上训练。本文将介绍数据整理、模型评测、使用方法等相关过程。引言近期,人们对能在本地设备上运行的小语言模型的兴趣日渐增长。这一趋势不仅激发了相关业者......
  • 定制直播软件,分布式锁的演进你了解多少?
    定制直播软件,分布式锁的演进你了解多少?分布式锁的演进基本原理我们可以同时去一个地方“占坑”,如果占到,就执行逻辑。否则就必须等待,直到释放锁。“占坑”可以去redis,可以去数据库,可以去任何大家都能访问的地方。等待可以自旋的方式。阶段一 publicMap<String,L......