一、用数组模拟单链表
邻接表：单链表的集合
- 单链表
#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;
void init() //初始化
{
head = -1; //链表是空的
idx = 0; //从0号点开始分配
}
void add_to_head() //将x插入到头节点
{
e[idx] = x; //e[idx]就是当前可用的第一个节点
ne[idx] = head; //head的next指针之前是指向第一个值，现在要让x的next指针指向以前的第一个值
head = idx++; //让head的next值指向idx
}
void add(int k, int x) //将x插入到地址为k的数的后面
{
e[idx] = x;
ne[idx] = ne[k]; //x的next指针指向k的next指针的值
ne[k] = idx++; //k的next指针指向x
}
void remove(int k) //将下标是k的点后面的点删除
{
ne[k] = ne[ne[k]]; //k的next指针指向（k的next指针指向的地址）的next指针
}
int main()
{
}
二、用数组模拟双链表
- 双链表：优化某些问题
#include <iostream>
using namespace std;
const int N = 100010;
//e[i]表示节点i的值
//l[i]表示i点的前一个数的地址
// r[i]表示i点的后一个数的地址
//idx表示当前已经用到了哪个节点
int e[N], l[N], r[N], idx;
void init() //初始化
{
//0表示左端点，1表示右端点
r[0] = 1, l[1] = 0; //0的右边是1,1的左边是0
idx = 2; //0和1已经被占用表示左右两侧的哨兵节点
}
void addr(int k, int x) //在下标是k的点的右边插入x
{
e[idx] = x;
r[idx] = r[k]; //x指向的下一个数就是原来k指向的下一个数
l[idx] = k; //x指向的上一个数是k
l[r[k]] = idx; //k指向的原来的下一个数的左边是x
r[k] = idx; //k指向的下一个数是x
idx++;
}
void addl(int k, int x) //在下标是k的点的左边插入x
{
addr(l[k], x); //相当于在（k的左边的数）的右边插入x
}
void remove(int k) //删除下标为k的点
{
r[l[k]] = r[k]; //k的左边的数的右边直接等于k右边
l[r[k]] = l[k]; //k的右边的数的左边直接等于k左边
}
int main()
{
}
三、配套练习