算法随笔(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