精确覆盖问题学习笔记(五)――优化算法的实现代码 - c++编程基础

[cpp] /文件node.h
#pragma once

struct CNode
{
CNode* Left; //左节点指针
CNode* Right; //右节点指针

CNode* Up; //上节点指针,对列节点，则为本列最后一个元素的指针
CNode* Down; //下节点指针,对列节点，则为本列第一个元素的指针

int name; //对普通节点，为所在子集的编号,即行号;
//对列节点，为列编号
};

struct CColumnHead:public CNode
{
int size; //本列元素的个数
};

struct CGrid:public CNode
{
CColumnHead* columnHead; //列头节点的指针

};

//文件node.h
#pragma once

struct CNode
{
CNode* Left; //左节点指针
CNode* Right; //右节点指针

CNode* Up; //上节点指针,对列节点，则为本列最后一个元素的指针
CNode* Down; //下节点指针,对列节点，则为本列第一个元素的指针

int name; //对普通节点，为所在子集的编号,即行号;
//对列节点，为列编号
};

struct CColumnHead:public CNode
{
int size; //本列元素的个数
};

struct CGrid:public CNode
{
CColumnHead* columnHead; //列头节点的指针

};
[cpp] //文件ExactCover.h
#pragma once
#include
#include
#include
#include
using namespace std;
#include "node.h"

class CExactCover
{
public:
CExactCover(const vector >& matrix); //从矩阵中读入数据，建立链表
~CExactCover(void);

private:
const CColumnHead* getColumn(int name)const;
const CColumnHead* selectColumn()const; //选择含1个数最少的列
void cover(const CColumnHead *c); //将某一列及其相关的节点从矩阵中删除
void uncover(const CColumnHead *c); //将某一列及其相关的节点重新加入到矩阵中
void CreateHead(const vector >& matrix); //建立头节点链表
void CreateRows(const vector >& matrix); //建立数据节点

bool search(); //求解算法
void print(const vector >& matrix,ostream &os) const; //输出可行解private:setm_solution; //解集
CColumnHead* m_master; //列头链表的头节点
};

//文件ExactCover.h
#pragma once
#include
#include
#include
#include
using namespace std;
#include "node.h"

class CExactCover
{
public:
CExactCover(const vector >& matrix); //从矩阵中读入数据，建立链表
~CExactCover(void);

private:
const CColumnHead* getColumn(int name)const;
const CColumnHead* selectColumn()const; //选择含1个数最少的列
void cover(const CColumnHead *c); //将某一列及其相关的节点从矩阵中删除
void uncover(const CColumnHead *c); //将某一列及其相关的节点重新加入到矩阵中
void CreateHead(const vector >& matrix); //建立头节点链表
void CreateRows(const vector >& matrix); //建立数据节点

bool search(); //求解算法
void print(const vector >& matrix,ostream &os) const; //输出可行解private:setm_solution; //解集
CColumnHead* m_master; //列头链表的头节点
};
[cpp] //文件ExactCover.cpp
#include
#include
#include
using namespace std;
#include "ExactCover.h"
void CExactCover::CreateHead( const vector >& matrix )
{
m_master = new CColumnHead;
m_master->size = 0;
m_master->Left = m_master;
m_master->Right = m_master;

CColumnHead* prev = m_master;

const int elementNum = matrix[0].size();
for (int i = 0
; i < elementNum
;++i
)
{
CColumnHead* c=new CColumnHead;
c->name = i+1;
c->size = 0;

prev->Right = c;
c->Left = prev;

c->Right = m_master;
m_master->Left = c;

c->Up = c;
c->Down = c;

prev = c;
++m_master->size;
}
}

void CExactCover::CreateRows( const vector >& matrix )
{
const int subsetNum=matrix.size();
const int elementNum = matrix[0].size();

for (int i=0;i {
CGrid* head=NULL;
CGrid* prev=NULL;
int num=0;
for(int j=0;j

精确覆盖问题学习笔记(五)――优化算法的实现代码 (一)