一、可优化的地方
上一节实现的代码从运行效率上看，有两个重大缺陷：
1、每次递归调用前，需要将当前的状态矩阵拷贝一份，然后删除和当前行相交的所有行和列，得到新的矩阵，当矩阵非常大时，拷贝操作所需的时间和空间都很大。
2、在实际情况中，矩阵M一般是稀疏矩阵，0的个数远远多于1的个数，如果我们能只处理含1的单元格的话，将大大提高运行的时空效率。
二、优化所用到的数据结构
以下优化算法是Knuth提出来的，其主要思想是用十字链表存储矩阵中的所有1.具体叙述如下
1、首先定义一个通用的十字链表节点类
[cpp] struct CNode
{
CNode* Left; //左节点指针
CNode* Right; //右节点指针
CNode* Up; //上节点指针,对列节点，则为本列最后一个元素的指针
CNode* Down; //下节点指针,对列节点，则为本列第一个元素的指针
int name; //对普通节点，为所在子集的编号,即行号;
//对列节点，为列编号
};
struct CNode
{
CNode* Left; //左节点指针
CNode* Right; //右节点指针
CNode* Up; //上节点指针,对列节点，则为本列最后一个元素的指针
CNode* Down; //下节点指针,对列节点，则为本列第一个元素的指针
int name; //对普通节点，为所在子集的编号,即行号;
//对列节点，为列编号
};
2、然后从上面的节点类派生出一个列标题类，这个列标题多了一个size数据域，用于存储本列元素的个数，即
struct CColumnHead:public CNode
{
int size; //本列元素的个数
};
3、数据节点类，存储原矩阵里的每个1，
[cpp] struct CGrid:public CNode
{
CColumnHead* columnHead; //列头节点的指针
};
struct CGrid:public CNode
{
CColumnHead* columnHead; //列头节点的指针
};4、建立一个头节点，指向列标题双向链表，以及存放可行解的变量。
[cpp] set
CColumnHead* master; //列头链表的头节点
set
CColumnHead* master; //列头链表的头节点
三、核心函数
算法的核心是两个函数。
1、cover函数
cover函数，输入是一个列号c，函数流程的伪代码为
(1)将列c整个的从列头链表中摘除
(2)从列c的第一个数据节点开始向下遍历列c的所有数据节点r，都每个r都执行如下操作：
a、从r 的右侧开始向右遍历r 所在行的其他节点cell,对每个cell执行如下操作
b、设cell的所在列号为n，将cell从其所在列n中摘除，列标题n的size域的值减1
总体来说cover函数的目的是将和这个列相关的所有节点从矩阵中删除。
2、cover的执行实例
下面看一个实例，假设
矩阵的当前状态为，括号中的数字表示该列的含1个数,h为列头链表的头节点，开始指向第一列
[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
h-> 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 ——原始矩阵
现在要将列1及其相关节点从矩阵中摘除，则具体过程是
(1)将列1从矩阵中整体摘除，此时h指向列2，矩阵的状态为
[cpp] -> 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 矩阵2——摘除列1之后的矩阵
注：列1虽然从矩阵中整体摘除，但它的自身信息并未发生变化，列1的原始信息仍然为
[cpp] 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 可见，和列1相关的行有A和B
下一步的任务就是将行A和B的其他节点从矩阵2中删除，
(2) 首先在矩阵2中遍历行A的所有数据节点（从第一列的右侧向右开始遍历），显然，A和列4、列7中有交点，于是删除这两个节点，第4列和第7列的计数器值减1，
这样整个行A就被从矩阵2中移走，现在得到的矩阵为
[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