Acwing数据结构：单链表

server/2024/11/9 17:08:04/

单链表

主要思想：使用数组实现链表(而不用结构体，结构体代码更长，后续图论也是基于数组实现），即静态链表。因为动态链表使用new申请空间需要较多的时间，而算法要求的是以较少的时间完成任务。

单链表：最主要用单链表写邻接表，用邻接表存储图或者树；
双链表：优化某些问题

单链表：头指针head指向第一个结点，初始为-1.数组e[]存储结点的值，数组ne[]存储对应结点的下一个结点的下标，形成一个链条。本质是用数组下标来操作对应结点。

需要背过的板子：

const int N=100010;//head表示头节点的下标
//e[i]表示节点i的值
//ne[i]表示节点i的next指针是多少
//idx存储当前已经用到了哪个点
int head,e[N],ne[N],idx=0;void init(){head=-1;//空idx=0;//当前可以从0号点开始用
}//在链表头插入一个x
void add_to_head(int x){e[idx] = x;//存值ne[idx] = head;//next指向head指的head = idx;//head指向idx的位置idx ++;//idx后移
}//将x插入到下标为k的点的后面
void add(int k,int x){e[idx] = x;ne[idx] = ne[k];ne[k] = idx;idx ++;
}//将下标是k的点后面的一个点删掉
void remove(int k){ne[k] = ne[ne[k]];
}

我们通过一个题目来实战一下。

实现一个单链表，链表初始为空，支持三种操作：
1.向链表头插入一个数；
2.删除第 k 个插入的数后面的一个数；
3.在第 k个插入的数后插入一个数。
现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。

在这里插入图片描述
输入样例：

10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6

输出样例：

6 4 6 5

实现思路：

设置数组e[]存储节点值，数组ne[]存储对应节点下一个节点的下标；
设置头指针head指向第一个节点，初始值为-1；
设置指针idx表示当前操作位置，初始为0即指向数组的第一个位置，单增；

样例模拟如下图所示：
![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/4cf43f5fa64949b2b0734c7dbeb2f177.png

代码实现：

#include <iostream>using namespace std;const int N=100010;//head表示头节点的下标
//e[i]表示节点i的值
//ne[i]表示节点i的next指针是多少
//idx存储当前已经用到了哪个点
int head,e[N],ne[N],idx=0;void init(){head=-1;//空idx=0;//当前可以从0号点开始用
}//在链表头插入一个x
void add_to_head(int x){e[idx] = x;//存值ne[idx] = head;//next指向head指的head = idx;//head指向idx的位置idx ++;//idx后移
}//将x插入到下标为k的点的后面
void add(int k,int x){e[idx] = x;ne[idx] = ne[k];ne[k] = idx;idx ++;
}//将下标是k的点后面的一个点删掉
void remove(int k){//当让在这特判进行删除头节点也可以//if(k==-1) head=ne[head];ne[k] = ne[ne[k]];
}int main(){int m;cin >> m;init();while(m--){char s; cin >> s;int k,x;if(s == 'H'){cin >> x;add_to_head(x);}else if(s == 'D'){cin >> k;if(k == 0) head = ne[head];//删除头节点//特判可以放在删除函数中~remove(k-1);//函数中传的是下标，为k-1}else if(s == 'I'){cin >> k >> x;add(k-1,x);//函数中传的是下标，为k-1}}for(int i = head;i !=-1 ;i = ne[i]) cout<<e[i]<<' ';//遍历输出也背住cout<<endl;return 0;
}