logicoptimize.cpp

卡诺图在变量数目很多时

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <iostream.h>
#define Max_Length 65        //输入项的字符长度不超过Max_Length
#define Max_Num 100          //输入项数不超过Max_Num
#define Max_Level 10         //合并的字符长度，即合并后'-'的个数
#include <time.h>
#include <string.h>

static int nLength,nNum,nLevel;
char (*fp)[Max_Length];
//*******************************************************
//**   定义一个ImplicantTerm的类，表示覆盖项的一些操作  *
//*******************************************************
class ImplicantTerm
{
public:
	char term[Max_Length]; 
	int nState,nLevel;
	int nTermNums[Max_Num];
	
public:
	ImplicantTerm()     //构造函数，每项初始化为0
	{
		for(int i=0;i<nLength;i++)
			term[i]='0';
		nState=0;
		for(i=0;i<Max_Num;i++)
			nTermNums[i]=0;
	}

	void SetTerm(char ch[Max_Length])   
	{
		for(int i=0;i<nLength;i++)
			    term[i]=ch[i];

	}
	void ChangeValue(int pos,char value)
	{
		term[pos]=value;
	}

};

ImplicantTerm *table[Max_Level],PITerm[Max_Num],FinalPI[100];
int piPos=0;


//***************************************************
//**   从LogicInput.txt读取数据,存入fp矩阵中        *
//***************************************************
void get_data()
{
    
	FILE * src;
	char ch;
	int i=0,j=0;

    char *file,*file1="LogicInput_9.txt",*file2="LogicInput_12.txt",*file3="LogicInput_40.txt",*file4="LogicInput_64.txt";
	printf("Please Choose The File to Be Optimized:\n");
	printf("**************************************************\n");
	printf("*  please input '1' to choose LogicInput_9.txt   *\n");
	printf("*  please input '2' to choose LogicInput_12.txt  *\n");
	printf("*  please input '3' to choose LogicInput_40.txt  *\n");
	printf("*  please input '4' to choose LogicInput_64.txt  *\n");
	printf("**************************************************\n");
	printf("Input your Number: ");

	while(i==0)
	{
		i=1;
		ch=getchar();
		while(ch==10) //输入的是空字符，则再次输入
		{
	
			printf("Input your Number: ");
			ch=getchar();
		}
		
		switch (ch)
		{
			case '1':
				file=file1;
			break;
			case '2':
				file=file2;
			break;
			case '3':
				file=file3;
			break;
			case '4':
				file=file4;
			break;
			default: 
				printf("You Have Chose Wrong Number, Please Input Again!\n");
				i=0;
				break;
		}
	}

  i=0;

	if((src=fopen(file,"r"))==NULL)  //打开LogicInput.txt
// 	if((src=fopen("LogicInput.txt","r"))==NULL)  //打开LogicInput.txt
		{
		 printf("LogicInput.txt文件无法打开!\n");
 		 exit(1);
		}

	while(!feof(src))
	{
		ch=getc(src);
		if(ch=='.')
		{
			ch=getc(src);
			if(ch=='i')
			{
				getc(src);
				nLength=getc(src)-'0';
				ch=getc(src);
				if(ch>='0'&&ch<='9')
					nLength=nLength*10+(ch-'0');
					
			}
			else if(ch=='p')
			{
				getc(src);
				nNum=getc(src)-'0';
				ch=getc(src);
				if(ch>='0'&&ch<='9')
					nNum=nNum*10+(ch-'0');
				fp = new char [nNum][Max_Length];
			}			
	    	
		}
		else if(ch=='0'||ch=='1')
		{
			fp[i][j]=ch;
			j++;
			if(j==nLength)
				{
					i++;
					j=0;
				}
		}

	}

	cout<<"nLength="<<nLength<<" nNum="<<nNum<<endl;
}

//*************************
//**   Expand             *
//*************************
int Expand(int th,int num) //合并第th级的蕴涵项，结果存放到第th+1级蕴涵项表
{
	int sameNum=0,flag,pos=0;
	int i,j,k,m;
	ImplicantTerm *mt=new ImplicantTerm [Max_Num]; //为第th+1个表分配空间
	for(i=0;i<num;i++)              //搜索合并
	{
		for(j=i+1;j<num;j++)
		{
			for(k=0;k<nLength;k++)   //查找table[th][i]与table[th][j]两覆盖不同项的个数，确定是否相邻
			{
				if(table[th][i].term[k]!=table[th][j].term[k])
				{
					sameNum++;
				    flag=k;
				}
			}
			if(sameNum==1) //如果相邻
			{
				if(th==0)
				{
					for(m=0;m<nLength;m++)
					{
						mt[pos].term[m]=table[th][i].term[m];
					}
				    mt[pos].nTermNums[i]=1;
			    	mt[pos].nTermNums[j]=1;

				}
				else
				{
					for(m=0;m<nLength;m++)
					{
						mt[pos].term[m]=table[th][i].term[m];
					}
					for(m=0;m<nNum;m++)
					{
						if(table[th][i].nTermNums[m]==1||table[th][j].nTermNums[m]==1)
							mt[pos].nTermNums[m]=1;
					}
				}
				table[th][i].nState++;  
			    table[th][j].nState++;
			    mt[pos].ChangeValue(flag,'-');
			    sameNum=0;
			    pos++;
			}
			sameNum=0;
		}
	
	}
    //去掉重复的覆盖项
	if(th!=0)    
	{
		for(i=0;i<pos;i++)
			for(j=i+1;j<pos;j++)
			{
				for(k=0;k<nLength;k++)   //查找mt[i]与mt[j]两覆盖，确定是否相同
				{
					if(mt[i].term[k]==mt[j].term[k])
						sameNum++;
				}
				if(sameNum==nLength)
				{
					for(m=j;m<pos;m++)
						mt[m]=mt[m+1];
					j--;
					pos--;
				}
				sameNum=0;
		}
	}
	//将未被覆盖的项加入PIterm[]中,即均为质蕴涵项
	for(i=0;i<num;i++)
		if(table[th][i].nState==0)
		{
			PITerm[piPos]=table[th][i];
			PITerm[piPos].nLevel=th;
			piPos++;
		}

    table[th+1]=mt;
	
	return pos;
}

int epiPos=0,epiPosPre;

int PICompare(ImplicantTerm p1,ImplicantTerm p2)//返回0，p1包含p2;返回1，p1被p2包含;返回2，p1，p2互相不包含;
{
	int i,num1=0,num2=0;
	for(i=0;i<nNum;i++)
	{
		if(p1.nTermNums[i]==1&&p2.nTermNums[i]!=1)
			num1++;
		else if(p1.nTermNums[i]!=1&&p2.nTermNums[i]==1)
			num2++;
	}
	if(num1!=0&&num2==0)
		return 0;
	else if((num1==0&&num2!=0)||(num1==0&&num2==0))
		return 1;
	else
		return 2;
}

void ColumCover()
{
	int i,j,k,sameNum=0,IsCycle=1,empty=1;
	bool notEssential=0;
	for(i=0;i<piPos;i++)  // 第i个质蕴涵项开始
	{
		if(!PITerm[i].nState)
		{
			for(k=0;k<nNum;k++)  //查找第i项中所包含的最小项
				{
					if(PITerm[i].nTermNums[k]==1) 
					{
						notEssential=0;
						for(j=0;j<piPos;j++) //该最小项是否是被唯一覆盖
						{
							if(PITerm[j].nState==0&&PITerm[j].nTermNums[k]==1&&j!=i)
								notEssential=1;

						}//执行完毕后check是不是质蕴涵项

						if(notEssential==0) //如果有质蕴涵项
						{
							FinalPI[epiPos]=PITerm[i]; 
							PITerm[i].nState=1;
							for(k=0;k<nNum;k++)  //去掉所有被包含了的最小项,标记为'2'
								if(FinalPI[epiPos].nTermNums[k]==1)
								{
									for(j=0;j<piPos;j++)
										if(PITerm[j].nTermNums[k]==1)
											PITerm[j].nTermNums[k]=2;
								}
							i++;
							k=0;
							epiPos++;
							IsCycle=0;
						}
					}
				}	       
		}
	}

	if(IsCycle==1)//如果是循环表
	{
		i=0;
		while(PITerm[i].nState!=0)
			i++;

		
		FinalPI[epiPos]=PITerm[i]; 	
		PITerm[i].nState=1;
		for(k=0;k<nNum;k++)  //去掉所有被包含了的最小项,标记为'2'
			if(FinalPI[epiPos].nTermNums[k]==1)
			{
				for(j=0;j<piPos;j++)
					if(PITerm[j].nState==0&&PITerm[j].nTermNums[k]==1)
						PITerm[j].nTermNums[k]=2;
			}
			epiPos++;	
	}

//清理重复项和被包含项.
	for(i=0;i<piPos;i++)
	{
		if(PITerm[i].nState==0)
		{
			for(k=0;k<nNum;k++)
				if(PITerm[i].nTermNums[k]==1)
					empty=0;
			if(empty==1)	
				PITerm[i].nState=1;

			for(j=i+1;j<piPos;j++)
				if(PITerm[j].nState==0)
					switch (PICompare(PITerm[i],PITerm[j]))
					{
						case 0: PITerm[j].nState=1;
							break;
						case 1: PITerm[i].nState=1;
							break;
						case 2: break;
					}
		}
	}
}
//***********************
//**   OutPut()函数     *
//*********************** 

void OutPut()
{
	FILE * dst;
 	if((dst=fopen("LogicOutput.txt","w"))==NULL)   //打开LogicOutput.txt，如果不存在，则建立一个
		{
		printf("LogicOutput.txt文件无法创建!\n");
 		 exit(1);
		} 
   char *p, buffer1[] = "The Logic Function Has Been Optimized :\n",buffer2[]= " Minimal Term Covered:";
   int i=0,j,k;
   for( p = buffer1; (i != EOF) && (*p != '\0'); p++ )
      i = putc( *p, dst);

   for(i=0;i<epiPos;i++)                  //将FinalPI[]中的数据写到LogicOutput.txt中
   {
	   	if(i<9)
		{
			putc('0',dst);
			putc(i+1+'0',dst);
			putc(':',dst);
			putc(' ',dst);

		}
		else
		{
			putc((i+1)/10+'0',dst);
			putc((i+1)%10+'0',dst);
			putc(':',dst);
			putc(' ',dst);
		}
	   for(j=0;j<nLength;j++)
		   putc(FinalPI[i].term[j],dst); 
	   for( p = buffer2; (j != EOF) && (*p != '\0'); p++)
		   j=putc( *p, dst );
	   for(k=0;k<nNum;k++)
		{
			if(FinalPI[i].nTermNums[k]!=0)
			{
				if(k<9)
				{
					putc(k+1+'0',dst);
					putc(',',dst);
				}
				else
				{
			        putc((k+1)/10+'0',dst);
			        putc((k+1)%10+'0',dst);
			        putc(',',dst);
		        }
		        
			}	
		}
	   putc('\n',dst);
   }


	   /////////////

 	fclose(dst);
}

//***********************
//**   主函数main()     *
//*********************** 
void main()
{
	clock_t start, finish;
	
	int	numpre,numnow;
	get_data();

	start = clock( );  //由于要等待输入，等待时间不能记为优化所需时间，所以系统起始时间从这儿开始计算
	ImplicantTerm *MT=new ImplicantTerm [nNum];

	for(int i=0;i<nNum;i++)
	{
		MT[i].SetTerm(fp[i]);
		MT[i].nTermNums[i]=1;
	}

	cout<<endl<<"All Implicant to Be Optimized:"<<endl;
	for(i=0;i<nNum;i++)
	{	if(i<9)
			cout<<0<<i+1<<":    ";
		else cout<<i+1<<":    ";
		for(int k=0;k<nLength;k++)
			cout<<MT[i].term[k];
		cout<<endl;
	}
	cout<<endl;

	table[0]=MT;  //生成第一个表

//合并覆盖，numpre代表上一次合并后的覆盖项项数；numnow代表这次合并后的覆盖项项数；
	i=0;
	numpre=nNum;
	numnow=Expand(i,numpre);
	i++;
	while(numpre!=numnow)
	{
	    numpre=numnow;
		numnow=Expand(i,numpre);
		i++;
	}

    cout<<"OutPut All Prime Implicant:"<<endl;
	for(i=0;i<piPos;i++)
		{
		    if(i<9)
				cout<<0<<i+1<<": ";
		    else cout<<i+1<<": ";
			for(int k=0;k<nLength;k++)
				cout<<PITerm[i].term[k];
			cout<<" 被覆盖最小项的序号：";
			for(k=0;k<nNum;k++)
			{
				if(PITerm[i].nTermNums[k]==1)
					cout<<k+1<<" ";
			}
			cout<<" level="<<PITerm[i].nLevel<<endl;
		}
    cout<<endl;

//列覆盖，当全部被覆盖后结束
	int j=0;
	while(j<piPos)
	{
		j=0;
		for(i=0;i<piPos;i++)
		{
			if(PITerm[i].nState==0)
			{
				ColumCover();
				j=0;
			}
		    else j++;
		}

	}

//最终优化的结果输出
	cout<<endl<<"OutPut The Last Optimized Logic Expression:"<<endl;
	for(i=0;i<epiPos;i++)
	{
		if(i<9)
			cout<<0<<i+1<<": ";
		else cout<<i+1<<": ";
		for(int j=0;j<nLength;j++)
			cout<<FinalPI[i].term[j];
		cout<<" 被覆盖最小项的序号：";
		for(int k=0;k<nNum;k++)
		{
			if(FinalPI[i].nTermNums[k]!=0)
				cout<<k+1<<" ";
		}
		cout<<endl;
	}
	OutPut();
	finish=clock();

	printf("\nRun Time：%f ms\n\n", double(finish-start));
	getchar();
	getchar();

}