精确覆盖问题学习笔记（四）――算法优化 (二)

[cpp] h->2(2) 3(2) 4(1) 5(2) 6(2) 7(3)
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1

h->2(2) 3(2) 4(1) 5(2) 6(2) 7(3)
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1 矩阵4 - 移走行B之后的状态

从上面的过程可知，cover并未切断被删除元素与其他元素的横向和纵向联系，这样就被恢复矩阵的状态打下了基础。

3、uncpver函数

uncover 函数的输入也是一个列号c，它的功能与cover相反，是将列c插入到矩阵中，也就是将矩阵恢复到执行

cover(c)以前的状态。

uncover的处理流程也正好和cover相反。

函数流程的伪代码为

(1)从列c的最后一个数据节点开始，向上遍历列c的所有数据节点r，都每个r都执行如下操作：

a、从r的左侧开始向左遍历其 所在行的其他节点cell,对每个cell执行如下操作

b、设cell的所在列号为n，将cell加入到列n中，列标题n的size域的值加1。

(2)将列c整个加入到从列头链表中

4、uncover的执行实例

设现在的矩阵状态为

[cpp] 2(2) 3(2) 4(1) 5(2) 6(2) 7(3)
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1

2(2) 3(2) 4(1) 5(2) 6(2) 7(3)
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1要插入的列号为1，且列1的信息为

[cpp] view plaincopyprint 1(2)
A 1
B 1
C 0
D 0
E 0
F 0

1(2)
A 1
B 1
C 0
D 0
E 0
F 0 行A和B的信息为

2 3 4 5 6 7
A 0 0 1 0 0 1
B 0 0 1 0 0 0

那么uncover的具体执行过程是

(1)首先将列4的最后一行B恢复到矩阵中，即将B的节点4恢复到矩阵中，且列4的计数器加1，矩阵状态为

[cpp] h-> 2(2) 3(2) 4(2) 5(2) 6(2) 7(3)
B 0 0 1 0 0 0
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1

h-> 2(2) 3(2) 4(2) 5(2) 6(2) 7(3)
B 0 0 1 0 0 0
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1 (2)然后将行A恢复到矩阵中，A的最后一个节点是7，所以先恢复列7的状态，矩阵为

[cpp] -> 2(2) 3(2) 4(2) 5(2) 6(2) 7(4)
A 0 0 0 0 0 1
B 0 0 1 0 0 0
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1

h-> 2(2) 3(2) 4(2) 5(2) 6(2) 7(4)
A 0 0 0 0 0 1
B 0 0 1 0 0 0
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1 然后将节点4恢复到矩阵中，矩阵的状态为

[cpp] h-> 2(2) 3(2) 4(3) 5(2) 6(2) 7(4)
A 0 0 1 0 0 1
B 0 0 1 0 0 0
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1

h-> 2(2) 3(2) 4(3) 5(2) 6(2) 7(4)
A 0 0 1 0 0 1
B 0 0 1 0 0 0
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1 (3)最后将列1插入到矩阵中，矩阵为

[cpp]
1(2) 2(2) 3(2) 4(3) 5(2) 6(2) 7(4)
A 1 0 0 1 0 0 1
B 1 0 0 1 0 0 0
C 0 0 0 1 1 0 1
D 0 0 1 0 1 1 0
E 0 1 1 0 0 1 1
F 0 1 0 0 0 0 1

1(2) 2(2) 3(2) 4(3) 5(2) 6(2) 7(4)
A 1 0 0 1 0 0 1
B 1 0 0 1 0 0 0
C 0 0 0 1 1 0 1
D