QM算法求最小蕴含项

这个算法既可以用链表写，也可以用数组写。前者很省空间，但是删除元素、查找元素的时候很费时间，于是使用数组写。在输入小项和蕴含项的个数之后，用一个整型数组记录这些项的数值，调用函数将这些数字转换成二进制字符串，并将这些项初始化为0，即还未组合。

#include
#include
#include
using namespace std;

struct Node
{
	int flag[2];
	char a[10];
	bool tag;
};

void binary（char *a int nint j）
{
	int s=n/2;
	int r=n%2;
	for（int i=0;i	{
	    a[j-i-1]=r+48;
		r=s%2;
		s=s/2;
	}
}

void combine（char *a char *b char *c int j）
{
	for（int i=0;i	{
		if（a[i]==b[i]）
			c[i]=a[i];
		else
			c[i]=‘-‘;
	}
}

int implicant（char *achar *bint j）
{
	int l=0;
	for（int i=0;i	{
		if（a[i]!=b[i]）
			l++;
	}
    if（l==1）
       return 1;
	else return 0;
}
int issame（char *a char *b int j）
{
	int l=0;
      for（int i=0;i	  {
        if（a[i]!=b[i]）
           l++;
	  }
	  if（l==0）return 1;
	  else return 0;
}
int contain（char *achar *bint j）
{
	int l=0;
	for（int i=0;i	{
		if（a[i]!=b[i]&&a[i]!=‘-‘&&b[i]!=‘-‘）
			l++;
	}
	if（l==0）
		return 1;
	else
		return 0;
}

int main（）
{
	int jieshu;
	char **diagram;
	cout<<“输入变量个数（10以内）:    “;
	cin>>jieshu;
	if（jieshu>10）
	{
		cout<<“输入变量个数错误！“;
		exit（1）;
	}
	int num1;
	int num2;
	int total;
	cout<<“输入小项个数:    “;
	cin>>num1;
	cout<<“输入蕴含项个数：   “;
	cin>>num2;
	total=num1+num2;
	diagram=new char *[num1];
	for（int i=0;i	{
		diagram[i]=new char[jieshu];
	}
	int *aa=new int[total];
    Node *x=new Node[2000];
    cout<	cout<<“依次输入小项:  “<	for（int i=0;i	{
		cin>>aa[i];
		if（aa[i]>pow（double（2）jieshu）-1）
		{
			cout<<“输入小项错误！“;
		    exit（1）;
		}
		binary（diagram[i]aa[i]jieshu）;
		binary（x[i].aaa[i]jieshu）;
		x[i].flag[0]=1;
		x[i].flag[1]=0;
		x[i].tag=0;
	}
	cout<	cout<<“依次输入蕴含项:   “<	for（int i=num1;i	{
		cin>>aa[i];
		if（aa[i]>pow（double（2）jieshu）-1）
		{
			cout<<“输入蕴含项错误！“;
		    exit（1）;
		}
		binary（x[i].aaa[i]jieshu）;
		x[i].flag[0]=1;
		x[i].flag[1]=0;
		x[i].tag=0;
	}
	int mn;
	m=total;
	n=0;
	int g=1;
	while（g==1）
	{
		int count=0;
         for（int i=0;i			 if（x[i].flag[0]==1&&x[i].flag[1]==n）
				 for（int j=i+1;j				     if（x[j].flag[0]==1&&x[j].flag[1]==n）
					 {
						 if（implicant（x[j].ax[i].ajieshu））
						 {
							 combine（x[j].ax[i].ax[m+count].ajieshu）;
							 x[i].tag=1;
							 x[j].tag=1;
							 x[m+count].flag[0]=1;
							 x[m+count].flag[1]=n+1;
							 x[m+count].tag=0;
                             count++;
						 }
					 }
           n++;
           for（int i=0;i		   {
			   if（x[i].tag==1）
				   x[i].flag[0]=0;
		   }
		   m=m+count;
           int i;
		   for（i=0;i		   {
			   if（x[i].flag[0]==1&&x[i].flag[1]==n）
			   {
				   for（int j=i+1;j					   if（x[j].flag[0]==1&&x[j].flag[1]==n）
						   if（implicant（x[i].ax[j].ajieshu））
						   {
							   g=2;
							   break;
						   }
			   }
				   if（g==2）
				   { 
					   g=1;
					   break;
				   }
		   }
			   if（i==m） g=0;

             

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2014-03-28 16:50  QM2\
     目录           0  2014-03-30 01:17  QM2\Debug\
     文件       48128  2014-03-30 01:17  QM2\Debug\QM.exe
     文件      378676  2014-03-30 01:17  QM2\Debug\QM.ilk
     文件      584704  2014-03-30 01:17  QM2\Debug\QM.pdb
     目录           0  2014-03-30 01:17  QM2\QM\
     文件     2231296  2014-03-30 01:24  QM2\QM.ncb
     文件         872  2014-03-18 23:54  QM2\QM.sln
     文件       15872  2014-03-30 01:24  QM2\QM.suo
     目录           0  2014-03-30 01:17  QM2\QM\Debug\
     文件        8874  2014-03-30 01:17  QM2\QM\Debug\BuildLog.htm
     文件          65  2014-03-30 01:17  QM2\QM\Debug\mt.dep
     文件         663  2014-03-30 01:17  QM2\QM\Debug\QM.exe.embed.manifest
     文件         728  2014-03-30 01:17  QM2\QM\Debug\QM.exe.embed.manifest.res
     文件         621  2014-03-30 01:17  QM2\QM\Debug\QM.exe.intermediate.manifest
     文件      158720  2014-03-30 01:17  QM2\QM\Debug\vc90.idb
     文件      208896  2014-03-30 01:17  QM2\QM\Debug\vc90.pdb
     文件       59753  2014-03-30 01:17  QM2\QM\Debug\yunhan.obj
     文件        3908  2014-03-19 00:04  QM2\QM\QM.vcproj
     文件        1433  2014-03-30 01:24  QM2\QM\QM.vcproj.suy-PC.suy.user
     文件        5586  2014-03-30 01:17  QM2\QM\yunhan.cpp