c语言算法 - 贪婪算法 - 二分覆盖

程序13-3 箱子函数的定义

void Undirected::CreateBins(int b, int n)
{// 创建b个空箱子和n个节点
node=new NodeType [n+1];
bin=new int [b+1];
// 将箱子置空
for (int i=1; i <=b; i++)
bin[i]=0;
}
void Undirected::InsertBins(int b, int v)
{// 若b不为０，则将v 插入箱子b
if (!b) return; // b为0，不插入
node[v].left=b; // 添加在左端
if (bin[b]) node[bin[b]].left=v;
node[v].right=bin[b];
bin[b]=v;
}
void Undirected::MoveBins(int bMax, int ToBin, int v)
{// 将顶点v 从其当前所在箱子移动到To B i n .
// v的左、右节点
int l=node[v].left;
int r=node[v].right;
// 从当前箱子中删除
if (r) node[r].left=node[v].left;
if (l > bMax || bin[l] !=v) // 不是最左节点
node[l].right=r;
else bin[l]=r; // 箱子l的最左边
// 添加到箱子To B i n
I n s e r t B i n s ( ToBin, v);
}

函数C r e a t e B i n s动态分配两个数组： n o d e和b i n，n o d e [i ]表示顶点i, bin[i ]指向其N e w值为i的双向链表的顶点, f o r循环将所有双向链表置为空。如果b≠0，函数InsertBins 将顶点v 插入箱子b 中。因为b 是顶点v 的New 值，b=0意味着顶点v 不能覆盖B中当前还未被覆盖的任何顶点，所以，在建立覆盖时这个箱子没有用处，故可以将其舍去。当b≠0时，顶点n 加入New 值为b 的双向链表箱子的最前面，这种加入方式需要将node[v] 加入bin[b] 中第一个节点的左边。由于表的最左节点应指向它所属的箱子，因此将它的node[v].left 置为b。若箱子不空，则当前第一个节点的left 指针被置为指向新节点。node[v] 的右指针被置为b i n [ b ]，其值可能为0或指向上一个首节点的指针。最后，b i n [ b ]被更新为指向表中新的第一个节点。MoveBins 将顶点v 从它在双向链表中的当前位置移到New 值为ToBin 的位置上。其中存在bMa x，使得对所有的箱子b i n[ j ]都有：如j>bMa x，则b i n [ j ]为空。代码首先确定n o d e [ v ]在当前双向链表中的左右节点，接着从双链表中取出n o d e [ v ]，并利用I n s e r t B i n s函数将其重新插入到b i n [ To B i n ]中。