QM算法进行布尔代数化简

#include

using namespace std;

#define MAXSIZE 100





struct Minterm
{
	int *Min;
	int num;
	int flag1;
	int flag2;
	Minterm *next;
};

struct link
{
	Minterm *head;
	int count;
};
int comparison（Minterm aMinterm bint var）;
bool equ（Minterm aMinterm bint var）;
link* QM（Minterm *dint varint count）
{
	
	link *l=new link[var+1];
	link *vec=new link;
	vec->head=NULL;
	vec->count=0;
	for（int i=0;i<=var;i++）
	{l[i].head=NULL;l[i].count=0;}
	//将最小项按含1的个数分类，用链表保存。
	for（int i=0;i		for（int j=0;j	{	
		if（d[i].num==j） 
		{
			if（l[j].head==NULL） 
				{
					l[j].head=new Minterm;
					l[j].head->Min=new int[var];
					for（int x=0;x					l[j].head->Min[x]=d[i].Min[x];
					l[j].head->flag2=d[i].flag2;
					l[j].head->next=NULL;
					l[j].count++;
			}
			else 
			{
				
				Minterm *h=new Minterm;
				h->Min=new int[var];
				for（int x=0;x				h->Min[x]=d[i].Min[x];
				h->flag2=d[i].flag2;
				h->next=NULL;
				Minterm *h1=l[j].head;
				while（h1->next!=NULL） 
				h1=h1->next;
				h1->next=h;	
				l[j].count++;
			}	
		}
	}
	//合并最小项
	while（1）
	{
		link *l1=new link[var+1];
		bool f1=false;
		for（int i=0;i<=var;i++）
		{
			l1[i].head=NULL;
			l1[i].count=0;
		}
		for（int i=0;i		{
			Minterm *p=l[i].head*q=l[i+1].head;
			while（p!=NULL）
			{
				q=l[i+1].head;
				int c;
				while（q!=NULL）
				{
					//判断pq是否可合并
					c=comparison（*p*qvar）;
					if（c!=-1） 
					{	
						p->flag2=1;q->flag2=1;
						Minterm *k1=new Minterm[1]*t1;
						k1->Min=new int[var];
						k1->flag2=0;
						k1->next=NULL;
						for（int j=0;j						{
							//将合并的结果保存
							if（j!=c）
							k1->Min[j]=q->Min[j];
							else {k1->Min[j]=-1;}
						}
						if（l1[i].head==NULL） l1[i].head=k1;
						else 
						{t1=l1[i].head;
						while（t1->next!=NULL） t1=t1->next;
						t1->next=k1;
						}
						l1[i].count++;
					}
					q=q->next;
				}
				//若p->flag!=1说明p已不可被合并，为本原蕴含项，保存至vec
					if（p->flag2!=1） 
					{
						p->flag2=-1;
						if（vec->head==NULL）
						{
							vec->head=new Minterm;
							vec->head->Min=new int[var];
							for（int x=0;x							vec->head->Min[x]=p->Min[x];
							vec->head->next=NULL;
							vec->count++;
						}
						else 
						{
							int f=0;
							Minterm *h=new Minterm;
							h->Min=new int[var];
							for（int x=0;x								h->Min[x]=p->Min[x];
							h->next=NULL;
							Minterm *h1=vec->head;
							while（h1!=NULL） 
							{	if（equ（*h1*hvar）==true） 
								{f=1;break;} 
								else 
								if（h1->next!=NULL） h1=h1->next;
								else break;
							}
							if（f==0）
							{
								h1->next=h;
								vec->count++;
							}
						}

					}
					p=p->next;
				}
				
		//处理未照顾到的最后一项
			if（i==var-1）
				{p=l1[var].head;
					while（p!=NULL）
				{
					if（p->flag2==0） 
					{
							int f=0;