链表与邻接表

一、链表

数组模拟双向链表

struct Node{
	int value;
	int prev, next;
}node[SIZE];
int head, tail, tot;

void initialize()
{
	tot = 2;    //控制节点存储位置
	head = 1,tail = 2;
	node[head].next = tail;
	node[tail].prev = head;
	return ;
}
void insert(int p, int val)
{
	// 在p点后向链表中插入一个节点
	q = ++tot;  // 向节点数组中申请空间
	node[q].value = val;
	// 交接
	node[node[p].next].prev = q;  
	node[q].next = node[p].next;
	node[p].next = q;
	return ;
}
void remove(int p)
{
	// 移除p节点
	node[node[p].prev].next = node[p].next;
	node[node[p].next].prev = node[p].prev;
	return ;
}
void clear()
{
	memset(node, 0, sizeof(node));
	head = tail = tot = 0;
	return ;
}

二、二叉平衡树

pass

三、邻接表

• 邻接表：带有索引数组的多个数据链表构成的结构集合；
• 在这样的结构中存储的数据被分成若干类，每一类的数据构成一个链表；
• 每一类数据有一个代表元素，成为该类数据对应链表的“表头”；
• 所有“表头”构成一个表头数组，作为一个可以随机访问的索引；
  
  如上图所示，在插入新节点时，通过表头数组直接索引到对应数据类的链表处，并在链表表头处插入数据。

图论应用

// 加入有向边(x,y),权值z
void add(int x,int y,int z)
{
	ver[++tot] = y, edge[tot] = z;// 记录真实数据
	next[tot] = head[x],head[x] = tot;  // 在表头x处插入
	// 通过head[x]索引对应的边，首先将上次head[x]更换next数组值，再次将当前边终点位置更新head[x]
	return ;
}
// 访问从x出发的所有边
for(int i = head[x];i;i = next[i]){
	int y = ver[i],z = edge[i];
}

注解：
head与 next数组存储 ver数组的下标，相当于指针，其中用 0表示空；ver数组存储每条边的终点，是真实数据；