کد:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
static int num;
/* This forms a linked list of nodes. Yummy. */
struct imp {
int value; /* Algorithm relies on value having 0-bit where mask is zero */
int mask; /* 0 where the value does not matter */
int used; /* This is marked true when an implicant is combined with another */
struct imp *next; /* This points to the next implicant in the linked list */
};
static void printImp(struct imp *imp);
static int countBits(int n);
static int numVars(int X[]);
static void addImp(struct imp *imp, int value, int mask);
static void mungeList(struct imp **imp_list, struct imp **imp_list2, int i);
static void erase_list(struct imp *imp_list);
static void printHeader();
static int is_one_bit(const int n);
int PI(int X[]) {
int i,j;
struct imp **imp_list;
struct imp **imp_list2; // Used for temp list of combined implicants
struct imp needed_imps; // Final list of implicants in compiled into here.
struct imp *i1; // Used as an iterator in various places.
struct imp **i2; // Used as an iterator in various places.
printHeader();
if(X[0] == 0) {
printf("0\n");
return 0;
}
num = numVars(X);
/* Initialize the imp_lists */
imp_list = (struct imp**)malloc(sizeof(void*)*(num+1));
imp_list2 = (struct imp**)malloc(sizeof(void*)*(num+1));
for(i=0;i<num+1;i++) {
imp_list[i] = (struct imp*)malloc(sizeof(struct imp));
imp_list2[i] = (struct imp*)malloc(sizeof(struct imp));
}
needed_imps.next = NULL;
for(i=0;i<=num;i++) {
i1 = imp_list[i];
i1->value = 0xBEEF;
i1->next = NULL;
i1 = imp_list2[i];
i1->value = 0xBEEF;
i1->next = NULL;
}
/* Sort implicants into linked lists based on the number of one-bits
in the binary representation of their value */
for(i=1;i<=X[0];i++) {
addImp(imp_list[countBits(X[i])], X[i], -1);
}
/************************************************** *************************/
/* Loop over the different numbers of zero bits in the masks */
for(j=0;j<=num;j++) { /* num+1 times since we have to take in account if all of the cells are true. */
/* Combine all of the terms into a second set of lists */
for(i=0;i<num;i++)
mungeList(imp_list, imp_list2, i);
/* Look for the items that were not used and add them to needed_imps */
for(i=0;i<=num;i++) {
for(i1 = imp_list[i]->next; i1; i1 = i1->next) {
if (!(i1->used)) {
addImp(&needed_imps, i1->value, i1->mask);
}
}
}
/* Remove the old list1 */
for(i=0;i<=num;i++)
erase_list(imp_list[i]);
/* swap the two lists */
i2 = imp_list;
imp_list = imp_list2;
imp_list2 = i2;
} /* . . . . rinse and repeat. */
/************************************************** *************************/
j=0;
for(i1 = needed_imps.next; i1; i1 = i1->next) {
printImp(i1);
printf("\n");
j++;
}
// Free all of the dynamicly allocated memory
for(i=0;i<=num;i++)
erase_list(imp_list[i]);
for(i=0;i<=num;i++)
erase_list(imp_list2[i]);
erase_list(&needed_imps);
free(imp_list);
free(imp_list2);
return j;
}
/* If an implicant with value and mask is in imp, this function will
return 1. Otherwise, it returns 0. */
static int search(struct imp *imp, const int value, const int mask) {
while((imp = imp->next))
if (imp->value == value && imp->mask == mask)
return 1;
return 0;
}
/* This prints out an implicant to stdout */
static void printImp(struct imp *imp) {
int i;
int outs=0;
for(i=num-1;i>=0;i--)
if ((imp->mask & (1<<i))) {
if(imp->value & (1<<i))
printf("%c",num-i+'a'-1);
else
printf("%c'",num-i+'a'-1);
outs++;
}
if (outs==0)
printf("1");
}
/* This frees all the nodes in a list (except for the head node )*/
static void erase_list(struct imp *imp_list) {
struct imp *i;
while(imp_list->next) {
i = imp_list->next->next;
free(imp_list->next);
imp_list->next = i;
}
}
/* This attempts to combine terms of imp_list[i] and imp_list[i+1] and
stores the combined terms in imp_list2[num_bits(combined term)] */
static void mungeList(struct imp **imp_list, struct imp **imp_list2, int i) {
int d;
struct imp *i1, *i2;
for(i1 = imp_list[i]->next; i1; i1 = i1->next) {
for(i2 = imp_list[i+1]->next;i2; i2 = i2->next) {
d = i1->value ^ i2->value;
if ((i1->mask == i2->mask)
&& (is_one_bit(d))) {
i1->used = 1;
i2->used = 1;
addImp(imp_list2[i],i1->value,i1->mask-d);
}
}
}
}
/* Prepends an implicant to a implicant list that has a specified
value and mask only if it has not already been added. */
static void addImp(struct imp *imp, int value, int mask) {
struct imp *new_imp;
if (!search(imp,value,mask)) {
new_imp= (struct imp*)malloc(sizeof(struct imp));
new_imp->value = value;
new_imp->mask = mask;
new_imp->next = imp->next;
new_imp->used = 0;
imp->next = new_imp;
}
}
/* Returns 1 is argument contains only one true bit */
static int is_one_bit(int n) {
if(n==0)
return 0;
if(n==1)
return 1;
while (((n >>=1) &1)==0)
;
if(n==1)
return 1;
return 0;
}
/* Returns the number of 1 bits in a number */
static int countBits(int n) {
int total=0;
while(n) {
total += n & 1;
n >>=1;
}
return total;
}
/* Returns the number of variables needed to represent the maximum
term of X */
static int numVars(int X[]) {
int i;
int max = 0;
int num=1;
for(i=1;i<=X[0];i++)
if(X[i]>max)
max = X[i];
while(max/=2)
num++;
return num;
}
static void printHeader() {
printf("Nathan Conrad\n");
printf("ITCS2181 Programming assignment 1\n");
printf("Due 3/27/03, 10pm\n");
}