静态链表

静态链表：需要预先分配一个较大的空间，但在作为线性表的插入和删除操作时不需移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。

静态链表的实现原理是 hash，即通过建立一个结构体数组，并令数组的下标直接表示结点的地址，来达到直接访问数组中的元素就能访问结点的效果。

• 由于结点的访问十分方便，因此静态链表不需要头结点

若结点的地址是比较小的整数，就可以直接使用静态链表

通用解题步骤

1. 定义链表

struct Node {
	int address;
	typename data;
	int next;
	xxx; //某个结点的性质
} nodes[maxn];

• 预留了一个 xxx来适应不同的题目（例如可以设置为结点是否为链表上的一个结点）

2. 初始化：一般是对 xxx 初始化，将其定义为正常情况下达不到的数字（一般是小于所有能达到的数字）

for (int i = 0; i < maxn; i++) {
	nodes[i].xxx = -1;
}

3. 标记：题目一般是会给出一条链表的首结点的地址，这一步我们对结点的 xxx 进行标记，同时计数

int p = head, count = 0;
while (p != -1) {
	xxx = 1;
	count++;
	p = nodes[p].next;
}

4. 排序：使用静态链表的采用直接地址映射的方式，这使得有效结点的下标并不连续，因此可以将有效结点移到数组左端

bool cmp(Node a, Node b) {
	if (a.xxx == -1 || b == -1) {
		return a.xxx > b.xxx;
	} else {
		// 升序
		return a.data < b.data;
	}
}

5. 经过了 4 的排序，链表中的有效结点都已经在数组的左端了，并且按照数组的 data 进行排序，可以根据题目处理了