C 语言实现布尔函数化简 (Quine-McCluskey 算法)

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

// 定义最大变量数和最大项数 #define MAX_VAR_NUM 10 #define MAX_TERM_NUM (1 << MAX_VAR_NUM)

// 定义素蕴包含的最大项数 #define MAX_PRIME_NUM MAX_TERM_NUM

// 定义相邻项比较结果枚举 enum CompareResult { SAME = 0, DIFF_BY_ONE = 1, DIFF_BY_MORE_THAN_ONE = 2 };

// 定义布尔类型 typedef enum { FALSE = 0, TRUE = 1 } BOOL;

// 定义素蕴结构体 typedef struct { BOOL values[MAX_VAR_NUM]; // 素蕴取值 BOOL covered; // 素蕴是否被覆盖 } PrimeImplicant;

// 定义函数输入和输出结构体 typedef struct { int var_num; // 变量数 int term_num; // 总项数 char** terms; // 所有项的表达式 char* output; // 化简后的表达式 } Function;

// 定义辅助函数，比较两个项是否相邻 BOOL is_adjacent(char* term1, char* term2) { int diff_count = 0; int len = strlen(term1); for (int i = 0; i < len; i++) { if (term1[i] != term2[i]) { diff_count++; if (diff_count > 1) { // 相差大于1个元素，不是相邻项 return FALSE; } } } return TRUE; }

// 定义辅助函数，比较两个素蕴是否相等 BOOL is_equal(PrimeImplicant* pi1, PrimeImplicant* pi2) { for (int i = 0; i < pi1->var_num; i++) { if (pi1->values[i] != pi2->values[i]) { return FALSE; } } return TRUE; }

// 定义辅助函数，比较两个素蕴是否相邻 enum CompareResult compare_primes(PrimeImplicant* pi1, PrimeImplicant* pi2) { BOOL has_diff = FALSE; int diff_idx = -1; for (int i = 0; i < pi1->var_num; i++) { if (pi1->values[i] != pi2->values[i]) { if (has_diff) { // 相差多个元素，直接认为不是相邻项 return DIFF_BY_MORE_THAN_ONE; } else { has_diff = TRUE; diff_idx = i; } } } if (!has_diff) { // 两个素蕴相等 return SAME; } // 两个素蕴相差一个元素 return DIFF_BY_ONE; }

// 定义辅助函数，将一个项转换成素蕴 PrimeImplicant* term_to_pi(char* term) { PrimeImplicant* pi = malloc(sizeof(PrimeImplicant)); int len = strlen(term); for (int i = 0; i < len; i++) { pi->values[i] = (term[i] != '-'); } pi->covered = FALSE; return pi; }

// 定义辅助函数，将一个素蕴转换成表达式 char* pi_to_term(PrimeImplicant* pi) { char* term = malloc((pi->var_num + 1) * sizeof(char)); for (int i = 0; i < pi->var_num; i++) { if (pi->values[i]) { term[i] = '1'; } else { term[i] = '0'; } } term[pi->var_num] = '\0'; return term; }

// 定义辅助函数，将一个素蕴加入素蕴集中 void add_prime(PrimeImplicant** primes, int* prime_count, PrimeImplicant* new_prime) { for (int i = 0; i < *prime_count; i++) { if (is_equal(primes[i], new_prime)) { // 素蕴已存在，不必重复添加 return; } } primes[*prime_count] = new_prime; (*prime_count)++; }

// 定义函数，对输入函数进行化简 void simplify_function(Function* func) { // 创建初始素蕴集合 PrimeImplicant* init_primes[MAX_PRIME_NUM]; int init_prime_count = 0; for (int i = 0; i < func->term_num; i++) { add_prime(init_primes, &init_prime_count, term_to_pi(func->terms[i])); }

// 计算最终素蕴集合
PrimeImplicant* primes[MAX_PRIME_NUM];
int prime_count = 0;
BOOL is_done = FALSE;
while (!is_done) {
    // 根据上一轮的基础素蕴和满足条件的表达式生成当前轮全部的素蕴
    for (int i = 0; i < prime_count; i++) {
        for (int j = i + 1; j < prime_count; j++) {
            enum CompareResult result = compare_primes(primes[i], primes[j]);
            if (result == DIFF_BY_ONE) {
                // 相差一个元素，则可以合并生成新的素蕴
                PrimeImplicant* new_prime = malloc(sizeof(PrimeImplicant));
                memcpy(new_prime->values, primes[i]->values, sizeof(BOOL) * primes[i]->var_num);
                new_prime->values[j] = TRUE;
                new_prime->covered = FALSE;
                add_prime(primes, &prime_count, new_prime);
            }
        }
    }

    // 检查是否已全部覆盖
    is_done = TRUE;
    for (int i = 0; i < func->term_num; i++) {
        BOOL is_covered = FALSE;
        for (int j = 0; j < prime_count; j++) {
            if (!primes[j]->covered && is_adjacent(func->terms[i], pi_to_term(primes[j]))) {
                // 该素蕴可以覆盖该项
                primes[j]->covered = TRUE;
                is_covered = TRUE;
                break;
            }
        }
        if (!is_covered) {
            // 还存在未被覆盖的项
            is_done = FALSE;
        }
    }
}

// 将最终素蕴生成表达式
char** final_terms = malloc(sizeof(char*) * prime_count);
int final_term_count = 0;
for (int i = 0; i < prime_count; i++) {
    if (!primes[i]->covered) {
        final_terms[final_term_count] = pi_to_term(primes[i]);
        final_term_count++;
    }
}

// 按字典序排序
for (int i = 0; i < final_term_count; i++) {
    for (int j = i + 1; j < final_term_count; j++) {
        if (strcmp(final_terms[i], final_terms[j]) > 0) {
            char* temp = final_terms[i];
            final_terms[i] = final_terms[j];
            final_terms[j] = temp;
        }
    }
}

// 将表达式拼接成最终输出结果
int output_len = final_term_count + final_term_count * func->var_num;
func->output = malloc((output_len + 1) * sizeof(char));
int out_idx = 0;
for (int i = 0; i < final_term_count; i++) {
    if (i > 0) {
        func->output[out_idx++] = '+';
    }
    for (int j = 0; j < func->var_num; j++) {
        if (final_terms[i][j] == '0') {
            func->output[out_idx++] = '-';
        } else {
            func->output[out_idx++] = 'A' + j;
        }
    }
}
func->output[out_idx] = '\0';

}

// 测试代码 int main() { // 定义测试数据 Function test_func = { .var_num = 4, .term_num = 8, .terms = (char**)malloc(sizeof(char*) * 8), .output = NULL }; test_func.terms[0] = "1000"; test_func.terms[1] = "1001"; test_func.terms[2] = "1010"; test_func.terms[3] = "1011"; test_func.terms[4] = "1100"; test_func.terms[5] = "1101"; test_func.terms[6] = "1110"; test_func.terms[7] = "1111";

// 测试化简
simplify_function(&test_func);

// 输出结果
printf("原表达式：\n");
for (int i = 0; i < test_func.term_num; i++) {
    printf("%s ", test_func.terms[i]);
}
printf("\n化简后表达式：%s\n", test_func.output);

return 0;