跳到主要内容

链表与邻接表

1.1单链表​

思路​

  1. 向链表头插入一个数；
  2. 删除第 k 个插入的数后面的数；
  3. 在第 k 个插入的数后插入一个数。

代码​

使用数组来模拟链表

const int N = 1e5 + 10;
int e[N], ne[N], head, idx;
//e[i]表示结点i的value
//ne[i]表示结点i的next
//head表示头结点下标
//idx表示当前使用的结点下标

链表初始化

//初始化
void init()
{
	head = -1;
	idx = 0;
}

在头部插入一个节点

void add_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx++;
}

移除节点k的下一个节点

void remove(int k)
{
    ne[k] = ne[ne[k]];
}

在节点k的下一个节点插入值x

void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;
}

遍历链表

for (int i = head; ~i; i = ne[i])//i!=-1  ~i
    cout << e[i] << ' ';

1.2双链表​

思路​

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

代码​

使用数组模拟双链表

const int N = 100010;
int e[N], l[N], r[N], idx;

双向链表初始化

void init() {
	r[0] = 1, l[1] = 0;
	idx = 2;
}

在节点k的下一个位置插入一个数x

//在节点k的下一个位置插入一个数x
void add(int k, int x) {
	e[idx] = x;
	r[idx] = r[k];
	l[idx] = k;
	l[r[k]] = idx;
	r[k] = idx;
	idx++;
}

删除k节点

//删除k节点
void remove(int k)
{
	r[l[k]]=r[k];
	l[r[k]]=l[k];
}

链表的输出

for(int i=r[0];i!=1;i=r[i])
    cout<<e[i]<<" ";
0%