威海经区建设局网站,素材下载平台网站源码,宁波外贸网站设计,外贸soho是什么意思0x13 链表与邻接表
数组是一种支持随机访问#xff0c;但不支持在任意位置插入和删除元素的数据结构。与之相对应#xff0c;链表支持在任意位置插入或删除元素#xff0c;但只能按顺序依次访问其中元素。我们可以使用一个struct来表示链表的节点#xff0c;其中可以存储任…0x13 链表与邻接表
数组是一种支持随机访问但不支持在任意位置插入和删除元素的数据结构。与之相对应链表支持在任意位置插入或删除元素但只能按顺序依次访问其中元素。我们可以使用一个struct来表示链表的节点其中可以存储任意数据。另外用prev和next两个指针指向前后两个相邻的节点构成一个常见的双向链表。为了避免在左右两端或者空链表中访问越界我们通常建立额外的两个节点head和tail代表链表头尾把实际数据节点存储在head和tail之间来减少链表边界处的判断减低编程复杂度。
struct node{int value;node *prev,*next;
};
node *head,*tail;void initialize()
{headnew node();tailnew node();head-nexttail;tail-prevhead;
}struct node{int val;int pre,next;
}nd[SIZE];
int head,tail,tot;void initialize()
{tot2;head1;tail2;nd[head].nexttail;nd[tail].prehead;
}1.邻接表
在与链表相关的数据结构中邻接表是相当重要的一种。它是图与树一般化存储方式还能用于实现我们将在下一节中介绍的开散列Hash表。实际上邻接表可以看成“带有索引数组的多个数据链表”构成的结构集合。在这样的结构中存储的数据被分为若干类每一类的数据构成一个链表。每一类还有一个代表元素称为该类对应链表的“表头”。所有的表头构成一个表头数组作为一个可以随机访问的索引从而可以通过表头数组定位到某一类数据对应的链表。
一个有n个点m条边的有向图可以如此存储
int tot;//边的总数
int ver[SIZE],edge[SIZE],next[SIZE],head[SIZE];
//分别记录每个边的终点每个边的权值把此边加入链表后的下一个边的序号头结点指向的第一个边的序号//加入有向边xy权值为z
void add(int x,int y,int z)
{ver[tot]y,edge[tot]z;next[tot]head[x],head[x]tot;
}//访问从x出发的所有边
for(int ihead[x];i;inext[i])
{int yver[i],zedge[i];
}例如插入6条边顺序为(1,2),(2,3),(2,5),(3,5),(5,4),(5,1)。 对于无向图我们可以把每条无向边看做两条有向边即可。我们可以利用第0x01学到的“成对变换”的位运算性质程序开始时令tot1这样无向边便存储在ver和edge数组下标“2和3”“4和5”…的位置上。通过对下标异或的操作就可以直接定位到反向边。如果ver[i]是第i条边的终点那么ver[i xor 1]则是第i条边的起点。
