单链表(使用邻接表)
邻接表,一种特殊的单链表,可以用来存储图和树
邻接表的表示方法:
e[i]存储数据, ne[i]存储next节点,idx表示用到了哪个节点
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
//head指向头节点,所以表示的是头节点的下标
//e[i]表示节点i的值
//ne[i]表示节点i的next指针是多少
//idx存储当前已经用到了那个节点
int e[N],ne[N],idx,head;
//创建邻接表(单链表的一种)
void init()
{
head = -1;//初始时head 指向 空节点-1
idx = 0;//记录邻接表中最后插入的节点
}
//将x插入到头节点
void add_to_head(int x)
{
e[idx] = x ,ne[idx] = head ,head = idx++;//head 指向 新元素idx
}
//将x插入到下标为k的点后面
void add(int k , int x)
{
e[idx] = x ,ne[idx] = ne[k] ,ne[k] = idx++;
}
//删除第k个节点后面的节点
void remove(int k)
{
ne[k] = ne[ne[k]];
}
int main()
{
init();
int m;
cin>>m;
while (m -- )
{
char op;
int k,x;
cin>>op;
if(op == 'H')
{
cin>>x;
add_to_head(x);
}
else if(op == 'I')
{
cin>>k>>x;
add(k-1 , x);
}
else
{
cin>>k;
if(k==0) head = ne[head];//题目说如果k=0就删除头节点
else remove(k-1);
}
}
for (int i = head; i != -1; i = ne[i] ) cout << e[i]<<' ';
cout << endl;
}
☆ * . ☆
. ∧_∧ ∩ * ☆
* ☆ ( ・∀・)/ .
. ⊂ ノ* ☆
☆ * (つ ノ .☆
(ノ