qmv.c

Quine-McCluskey 算法 C语言实现, (链表) 自己学校的编程实验作业, 自己编的

/*================================================================================================*/
/*  Quine-McCluskey-Verfahren */
/*  Gruppen 16  Li,Bo         */

/* 2. Symbolische Konstanten und globale Variablen */

#include <stdio.h>
#include <stdlib.h>


#define MAX_VARIABLEN 10
#define MAX_DATEI 30
#define MAX_MINTERM 100


int anzahl_minterme=0, anzahl_variablen;


/*  Zeigerdef. auf MINTERM liegt im Aufgabe 1.1 */ 


/*================================================================================================*/
/* 1. Listentypen */

typedef struct komposition
{
	short int nr;
	struct komposition *next;
}KOMPOSITION;


typedef struct minterm
{
	short int bit[MAX_VARIABLEN];
	short int verwendet;
	KOMPOSITION *komp_head;
	struct minterm *next;
}MINTERM;


/*Aufgabe 2.2*/
MINTERM *einlesen_head=NULL, *primterm_head=NULL, *min_head=NULL;



/* Funktionsprototypen */
MINTERM *create_minterm_list_element(MINTERM);

void add_minterm_list_element(MINTERM *, MINTERM **);

void delete_minterm_list_element(MINTERM *, MINTERM **);

KOMPOSITION *create_komp_list_element(int);

void add_komp_list_element(KOMPOSITION *, KOMPOSITION **);

void delete_komp_list_element(KOMPOSITION *, KOMPOSITION **);


/* Funktion */

MINTERM *create_minterm_list_element(MINTERM term)
{
	MINTERM *neu;
	neu=(MINTERM *)malloc(sizeof(MINTERM));
	if (neu==NULL)
	{
		printf("create_minterm_list_element: malloc failed\n");
		exit(1);
	}
	else
	{
		term.verwendet=0;
		term.komp_head=NULL;     // MUSS VERNULL SEIN
		*neu=term;
	}
	neu->next=NULL;
	return neu;	
}



void add_minterm_list_element(MINTERM *neu, MINTERM **head)
{
	MINTERM *ptr;
	if (*head==NULL)
	{
		*head=neu;
	}
	else
	{
		for (ptr=*head; ptr->next!=NULL; ptr=ptr->next)
			/*Leeranweisung*/;
			ptr->next=neu;
	}

}

	
	




void delete_minterm_list_element(MINTERM *b, MINTERM **head)
{
	MINTERM *ptr; 
	if(b == *head) 
	{
		/* Entfernen des 1. Listenelementes */
		*head=b->next;
	} 
	else 
	{
		/* Suchen des Listenelementes */
		for(ptr=*head; (ptr!=NULL) && (ptr->next!=b); ptr=ptr->next)
			/* Leeranweisung */ ;
			if(ptr==NULL) 
			{
			printf("delete_minterm_list_element: can't find list_\
				element\n");
			exit(3);
			} 
			else 
			{
				ptr->next = ptr->next->next;
			}
	}
	/* Freigabe des Speicherbereichs */
//	free(b);
	return;
}


KOMPOSITION *create_komp_list_element(int nr)
{
	KOMPOSITION *neu;
	neu=(KOMPOSITION *)malloc(sizeof(KOMPOSITION));
	if (neu==NULL)
	{
		printf("create_komp_list_element: malloc failed\n");
		exit(1);
	}
	else
	{
		neu->nr=nr;
	}
	neu->next=NULL;
	return neu;	
}



void add_komp_list_element(KOMPOSITION *neu, KOMPOSITION **head)
{
	KOMPOSITION *ptr;
	if (*head==NULL)
	{
		*head=neu;
	}
	else
	{
		for (ptr=*head; ptr->next!=NULL; ptr=ptr->next)
			/*Leeranweisung*/;
			ptr->next=neu;
	}
}




void delete_komp_list_element(KOMPOSITION *b, KOMPOSITION **head)
{
	KOMPOSITION *ptr; 
	if(b == *head) 
	{
		/* Entfernen des 1. Listenelementes */
		*head = b->next;
	} 
	else 
	{
		/* Suchen des Listenelementes */
		for(ptr = *head; (ptr != NULL) && (ptr->next != b);ptr = ptr->next)
			/* Leeranweisung */ ;
			if(ptr == NULL) 
			{
			printf("delete_komp_list_element: can't find list_\
				element\n");
			exit(3);
			} 
			else 
			{
				ptr->next = ptr->next->next;
			}
	}
	/* Freigabe des Speicherbereichs */
//	free(b);
	return;
}




/*================================================================================================*/
/* 3. Funktion daten_einlesen */

MINTERM minterm_umwandeln(char kette[]) 
{
	int v;
	MINTERM neu_term;
	for (v=0;v<anzahl_variablen;v++)
	{
		if (kette[v]>='a' && kette[v]<='z')
			neu_term.bit[v]=0;
		
	    else if (kette[v]>='A' && kette[v]<='Z')
			neu_term.bit[v]=1;
	}

	return neu_term;
}


void daten_einlesen(void)
{
	char datei_name[MAX_DATEI];
	FILE *fp;
	char ch;
	int i,n;
	char zeichenkette[MAX_VARIABLEN];
	MINTERM *term;
	KOMPOSITION *komp;
	
	printf("Geben sie Name der Datei ein. z.B. test.txt(Hinweis:nicht mehr als %i Zeichen!)\n",MAX_DATEI);
	gets(datei_name); //scanf("%s",datei_name);
	
	if ((fp=fopen(datei_name,"r"))==NULL)
	{
		printf("cannot open this file\n");
		exit(0);
	}
	
	printf("Inhalt der %s ist: \n", datei_name);
	ch=fgetc(fp);
	i=0;
	n=0;
	while (ch!=EOF)
	{
		if (ch!='+')
		{
			zeichenkette[i]=ch;
		    anzahl_variablen=++i;
		}
		else
		{
			
			term=create_minterm_list_element(minterm_umwandeln(zeichenkette));

			add_minterm_list_element(term, &einlesen_head);

			komp=create_komp_list_element(n++);			

			add_komp_list_element(komp, &term->komp_head);

			i=0;
		}

		putchar(ch);
		ch=fgetc(fp);

	}
	
	term=create_minterm_list_element(minterm_umwandeln(zeichenkette));
	
	add_minterm_list_element(term, &einlesen_head);
	
	komp=create_komp_list_element(n);
	
	add_komp_list_element(komp, &term->komp_head);
	
	anzahl_minterme=n+1;

	printf("\n\n");
	
}



/*================================================================================================*/

/* 4. Funktion liste_ausgaben() */

void komp_ausgeben(KOMPOSITION *komp_head)
{
	KOMPOSITION *ptr;
	
	for(ptr=komp_head;ptr!=NULL;ptr=ptr->next)  //wenn ptr->next!=NULL ,dann Letzt komp verloren.
	{
		printf("%d",ptr->nr);
		if(ptr->next!=NULL)
		{
			printf(",  ");
		}
		
	}
	
}


void liste_ausgeben(MINTERM *head, char *liste)
{
	MINTERM *ptr;
	int i;
	
	printf("%s\n",liste);
	
	for(ptr=head;ptr!=NULL;ptr=ptr->next)
	{
		for(i=0;i<anzahl_variablen;i++)
		{
			if(ptr->bit[i]==2)
			{
				printf("-");
			}
			else
			{
				printf("%d",ptr->bit[i]);      
			}                    
		}
		
		printf("   :   ");
		
		printf("<");
		komp_ausgeben(ptr->komp_head);
		printf(">\n");
		
	} 
	return;
}



/*================================================================================================*/
/* 5. Minimierung I */       

int verschmelzung_moeglich(MINTERM *m1, MINTERM *m2)
{
	int i, stelle,x=0,z1=0,z2=0;
	
	for(i=0;i<anzahl_variablen;i++)
	{
		if(m1->bit[i]!=m2->bit[i])
		{
			stelle=i;
			x++;
		}
	}
	if(x!=1)
	{
		stelle=-1;
	}
	
	return stelle;
}


void term_komp_einfuegen(MINTERM *ziel, MINTERM quelle1)   //Vereinfacher
{
	KOMPOSITION *ptr1,*ziel1;
	for(ptr1=quelle1.komp_head;ptr1!=NULL;ptr1=ptr1->next)
	{
		for(ziel1=ziel->komp_head;ziel1!=NULL;ziel1=ziel1->next)
			/*Leeranweisung*/;
		ziel1=create_komp_list_element(ptr1->nr);
		add_komp_list_element(ziel1, &ziel->komp_head);
	}
}



void komp_einfuegen(MINTERM *ziel, MINTERM quelle1, MINTERM quelle2)
{
	KOMPOSITION *ptr1,*ziel1,*ptr2,*ziel2;
	for(ptr1=quelle1.komp_head;ptr1!=NULL;ptr1=ptr1->next)
	{
		for(ziel1=ziel->komp_head;ziel1!=NULL;ziel1=ziel1->next)
			/*Leeranweisung*/;
		ziel1=create_komp_list_element(ptr1->nr);
		add_komp_list_element(ziel1, &ziel->komp_head);


	}

	for(ptr2=quelle2.komp_head;ptr2!=NULL;ptr2=ptr2->next)
	{
		for(ziel2=ziel->komp_head;ziel2!=NULL;ziel2=ziel2->next)
			/*Leeranweisung*/;
		ziel2=create_komp_list_element(ptr2->nr);
		add_komp_list_element(ziel2, &ziel->komp_head);
	}
	
	/*
	KOMPOSITION *ptr;
	for(ptr=quelle1.komp_head;ptr->next!=NULL;ptr=ptr->next)
		Leeranweisung; 
		ptr->next=quelle2.komp_head;  
		call by refrenc, so quelle1.komp_head=ptr=ziel->komp_head auch veraendert. Fehler!!!
	*/

    /*
	ziel->komp_head=quelle1.komp_head;
	add_komp_list_element(quelle2.komp_head, &(ziel->komp_head));
    Fehler!!! quelle1.komp_head aendert immer!!!
	*/
}



void doppelte_minterme_entfernen(MINTERM **head)
{
	MINTERM *m1, *m2;
	int i;

	int n=0,x=0,y=0;
	for(m1=*head;m1!=NULL;m1=m1->next)
	{
		for(m2=m1->next;m2!=NULL;m2=m2->next)
		{
			for(i=0;i<anzahl_variablen;i++)
			{
				if(m1->bit[i]!=m2->bit[i])
					n++;
			}
			/* Kann man Einfacher 
			for(komp1=m1->komp_head;komp1!=NULL;komp1=komp1->next)
			{
				x++;
				for(komp2=m2->komp_head;komp2!=NULL;komp2=komp2->next)
				{
					if(komp1->nr==komp2->nr)
						y++;
				}
			}x=0;
			y=0;
			*/
			if(n==0)
			{
				delete_minterm_list_element(m2,head);
				//delete_minterm_list_element(m1,head);
			}
			n=0;
		}
		
		
	}
}






void terme_verschmelzen(MINTERM **head)
{
	MINTERM *ptr1, *ptr2, *term, *hilfs, neu, *temp_head=NULL, neu_primterm, *primterm; 
	int stelle,i,x;
	
	while(*head!=NULL)
	{
		for(ptr1=*head;ptr1!=NULL;ptr1=ptr1->next)
		{
			for(ptr2=ptr1->next;ptr2!=NULL;ptr2=ptr2->next)
			{
				if((stelle=verschmelzung_moeglich(ptr1,ptr2))>=0)
				{
					/*Verschmelzung der Terme*/
					for (i=0;i<anzahl_variablen;++i)
						neu.bit[i]=ptr1->bit[i];
					neu.bit[stelle]=2;
					term=create_minterm_list_element(neu);
					komp_einfuegen(term,*ptr1,*ptr2);
					add_minterm_list_element(term, &temp_head);
					
					ptr1->verwendet=1;
					ptr2->verwendet=1;
					
					
					//liste_ausgeben(term,"Einer Minterm ist:");
					
				}
			}
			if(!ptr1->verwendet)
			{
				/*zur Primtermliste hinzufuegen*/
				for (x=0;x<anzahl_variablen;++x)
					neu_primterm.bit[x]=ptr1->bit[x];
				primterm=create_minterm_list_element(neu_primterm);
				term_komp_einfuegen(primterm, *ptr1);

				add_minterm_list_element(primterm,&primterm_head);
								
				delete_minterm_list_element(ptr1, head);
			}
			
			
		}
		/*Listenkoepfe vertauschen und ueberflussige Liste entfernen*/
		hilfs=*head;
		*head=temp_head;

		temp_head=NULL; //Achtung! Aufgabe Fehler! wenn temp_head=hilfs dann next spalt mit
		                //0000 anfangen wird!!!

		doppelte_minterme_entfernen(head);
	}
}






/*================================================================================================*/
/* 6. Minimierung II */

void kernprimimplikanten_suchen(MINTERM **quelle, MINTERM **ziel)
{
	MINTERM *term, *kernterm, neu_ziel, *neu;
	KOMPOSITION *komp;
	int nr, i=0, x, anzahl_gleich_nr[MAX_MINTERM]={0};
	for(nr=0;nr<anzahl_minterme;nr++)
	{
		for(term=*quelle;term!=NULL;term=term->next)
		{
			for(komp=term->komp_head;komp!=NULL;komp=komp->next)
			{
				if(komp->nr==nr)
				{
					anzahl_gleich_nr[nr]++;
					kernterm=term;
				}
			}
		}
		if(anzahl_gleich_nr[nr]==1)
		{

			for (x=0;x<anzahl_variablen;++x)
				neu_ziel.bit[x]=kernterm->bit[x];
			neu=create_minterm_list_element(neu_ziel);
			term_komp_einfuegen(neu, *kernterm);			
			add_minterm_list_element(neu, ziel);
			delete_minterm_list_element(kernterm, quelle);

		}
	}
}




KOMPOSITION *suche_komp(KOMPOSITION *head, int nr)
{
	KOMPOSITION *ptr,*komp;

	ptr=head;

	while(ptr->nr!=nr)
	{
		ptr=ptr->next;
		if(ptr==NULL) break;
	}

	komp=ptr;

/*	for(ptr=head;ptr!=NULL;ptr=ptr->next)
	{
		if(ptr->nr==nr)
		{
			komp=ptr;			
		}
		else
		{
			komp=NULL;
		}
	}
 Immer NULL return                     */

	return komp;
}


void komp_ueberdeckung_beseitigen(MINTERM *min, MINTERM **primterm)
{
	MINTERM *term, *minterm;
	KOMPOSITION *komp;
	for(term=*primterm;term!=NULL;term=term->next)
	{
		for(komp=term->komp_head;komp!=NULL;komp=komp->next)
		{
			for(minterm=min;minterm!=NULL;minterm=minterm->next)
			{
				if(suche_komp(minterm->komp_head, komp->nr))
				{
					delete_komp_list_element(komp, &term->komp_head);
					break; //wenn DELETE machen, dann nochmal DELETE vermeiden muessen. 
				}
				
			}
			
		}
	}
}





void reduktion(MINTERM **head)
{
	MINTERM *p1,*p2;
	KOMPOSITION *komp;
	int wahrheit;

	for (p1=*head; p1!=NULL; p1=p1->next)
	{
		for(p2=*head; p2!=NULL; p2=p2->next)
		{
			if(p2!=p1)
			{
				for(komp=p1->komp_head; komp!=NULL; komp=komp->next)
				{
					wahrheit=(suche_komp(p2->komp_head,komp->nr))? 1:0;
					if(!wahrheit)
						break;        // wenn es ungleiche nr gibt, verendet man Schleife.
				}

				if(wahrheit)
				{
					delete_minterm_list_element(p1,head);
					break;
				}
			}
		}
	}
}




void liste_anhaengen(MINTERM **quelle, MINTERM **ziel)
{
	MINTERM *ptr;
	for(ptr=*quelle;ptr!=NULL;ptr=ptr->next)
	{
		add_minterm_list_element(ptr, ziel);
	}
}







/*================================================================================================*/
/* 7. Ausgabe */
void ausgabe (MINTERM *head)
{
	MINTERM *p;
	int i,j=0,n;
	char ergebnis[MAX_MINTERM]={0};

	for (p=head; p!=NULL; p=p->next)
	{
		for (i=0; i<anzahl_variablen; i++)
		{
			switch(p->bit[i])
			{
			case 0 : {ergebnis[j]='a'+i; j++;} break;
			case 1 : {ergebnis[j]='A'+i; j++;} break;
			}
		}
		ergebnis[j]='+';
		j++;
	}

	for (n=0; n<j-1; n++)   // letzt'+' nicht mehr ausdruck
	{
		printf("%c",ergebnis[n]);
	}

	printf("\n\n\n");
}



void ausgabe_in_datei (MINTERM *head)
{
	char datei_name[MAX_DATEI];
	MINTERM *p;
	int i,j=0,n;
	char ergebnis[MAX_MINTERM]={0}, ch;
	FILE *fp;
	
	printf("Entscheiden Sie, ob das Ergebnis in eine Datei geschriben werden soll.(Y/N)\n");
	
	if((ch=getchar())=='y' || (ch=getchar())=='Y')
	{
		for (p=head; p!=NULL; p=p->next)
		{
			for (i=0; i<anzahl_variablen; i++)
			{
				switch(p->bit[i])
				{
				case 0 : {ergebnis[j]='a'+i; j++;} break;
				case 1 : {ergebnis[j]='A'+i; j++;} break;
				}
			}
			ergebnis[j]='+';
			j++;
		}

		printf("Geben sie Name der Datei ein. z.B. test.txt(Hinweis:nicht mehr als %i Zeichen!)\n",MAX_DATEI);
		
		scanf("%s",datei_name); // "gets" geht es nicht!!!
		
		if ((fp=fopen(datei_name,"w"))==NULL)
		{
			printf("cannot create file\n");
			exit(0);
		}
		for (n=0; n<j-1; n++)   // letzt'+' nicht mehr ausdruck
		{
			fprintf(fp,"%c",ergebnis[n]);
		}		
	}
	
    else            //if ((ch=getchar())=='n' || (ch=getchar())=='N')
	{
		printf("\nEnde\n\n");
	}
}


void liste_leeren(MINTERM **head)
{
	free(*head);
}


/*================================================================================================*/
/* 8. Funktion main() */
int main(void)
{
	daten_einlesen();

	liste_ausgeben(einlesen_head, "eingelesene Daten:");

	terme_verschmelzen(&einlesen_head);

	liste_ausgeben(primterm_head, "\nprimtermliste:");

	kernprimimplikanten_suchen(&primterm_head, &min_head);

	komp_ueberdeckung_beseitigen(min_head, &primterm_head);

	liste_ausgeben(primterm_head, "\nPrimtermliste (ohne Ueberdeckung durch Kernprimimplikanten):");

	reduktion(&primterm_head);

	liste_ausgeben(primterm_head, "\ndominante Primterme:");

	liste_anhaengen(&primterm_head, &min_head);

	liste_ausgeben(min_head, "\nDNF-Liste:");

	printf("\nMinimierte DNF:\n");

	ausgabe(min_head);
	
	ausgabe_in_datei(min_head);

	liste_leeren(&min_head);

	liste_leeren(&primterm_head);

	return 0;
}