简介这份课程设计资料围绕「重言式判别程序」展开面向正在学习数据结构与算法、需要完成同类课设的计算机专业学生。它以二叉树表示布尔表达式叶子节点存放变量或真假常量非叶子节点对应与、或、非等逻辑运算符再借助后序遍历配合栈暂存中间结果自底向上完成求值据此判断表达式是否恒真并涉及表达式输入交互与测试用例设计。压缩包共4个文件、约38KB由2份doc文档与2个c源程序组成文档承担项目概述、设计思路、算法描述与测试结果说明源程序对应判别功能的具体实现篇幅精简但结构完整便于对照阅读与本地编译调试。目前已有383人学习下载。读者可从中获得一套可运行的判别思路、二叉树建树与遍历的落地写法、栈在表达式求值中的使用方式以及课程设计文档的写作框架适合用来对照梳理自己的实现方案或查漏补缺。1. 一个 2^n 的坑重言式判别程序到底在判什么答辩现场见过这样一幕程序在 3 个变元上跑得飞快老师随手写了个 5 变元的式子屏幕就卡住了追问复杂度答不上来。重言式判别程序这道课程设计题看着简单——输入一个命题公式判断它是否在所有赋值下都为真——真写起来难点全在公式怎么在内存里立住、2^n 种赋值怎么落地、判完拿什么证明自己没判错。这套数据结构课程设计资料围着这三件事展开二叉链表把中缀公式立成表达式树位掩码跑真值表再用等价变换做第二路交叉验证配套的实验报告与文档资料可以直接对着改。刚学完树与栈的学生能照着抄想补表达式解析基本功的开发者也能拿去练手。2. 命题公式进内存二叉链表表示与中缀转后缀建树2.1 为什么不能对着字符串边扫边求值最简单的写法是拿到p (q | !r)这种串从左往右扫遇到运算符就算。这种写法在只有一个运算符时没问题一旦嵌套括号和五种优先级混在一起就得在求值过程中反复回退、重新定位子表达式代码会迅速退化成一大坨if嵌套而且没法复用——每换一个公式都要重新解一遍结构。课程设计在这里考的是抽象把公式从一维字符串变成二维的树。表达式树的每个内部节点是一个运算符叶子是命题变元。这么一转换求值就退化成一次后序遍历判定逻辑和解析逻辑彻底分开。后面无论换成真值表法还是等价变换法动的是遍历函数解析那一层不用碰。这也是我把这份资料的实现路线定成先建树、再判的原因。树一旦建好调试时可以直接把树按括号形式打印出来公式有没有解析错一眼就能看出来比对着字符串猜强得多。2.2 节点结构与优先级表节点只需要五个运算符加一个变元类型。用枚举区分避免在结构体里塞字符串比较typedef enum { VAR, NOT, AND, OR, IMP, IFF } NodeType; typedef struct Node { NodeType type; char name; /* 仅 VAR 使用: p q r ... */ struct Node *l, *r; /* NOT 只用 l */ } Node;优先级和结合性单独抽成两个函数别散落在解析代码里。这是后面最容易被改坏的地方集中在一处改一次就够了运算符含义优先级结合性元数!否定5右1合取4左2|析取3左2-蕴含2右2-等价1右2static int prec(const char *op) { if (!strcmp(op, !)) return 5; if (!strcmp(op, )) return 4; if (!strcmp(op, |)) return 3; if (!strcmp(op, -)) return 2; if (!strcmp(op, -)) return 1; return 0; } /* 只有这三个是右结合, 其余左结合 */ static int right_assoc(const char *op) { return !strcmp(op, !) || !strcmp(op, -) || !strcmp(op, -); }提示蕴含的右结合是这道题最高频的翻车点。p - q - r在数学上约定为p - (q - r)如果你按左结合解析成(p - q) - r真值表会多出一堆反例而且很难看出是解析层错了。2.3 调度场算法中缀转后缀有了优先级表中缀转后缀就是标准的调度场算法。先做分词把-和-这种双字符、三字符运算符识别成一个 token避免后面在字符级别反复判断typedef enum { TK_VAR, TK_OP, TK_LP, TK_RP } TokKind; typedef struct { TokKind kind; char op[4]; /* ! | - - */ char name; /* TK_VAR 时有效 */ } Token; static int tokenize(const char *s, Token out[], int cap) { int n 0; while (*s) { if (*s ) { s; continue; } if (n cap) return -1; Token t; memset(t, 0, sizeof t); if (isalpha((unsigned char)*s)) { t.kind TK_VAR; t.name *s; } else if (*s () { t.kind TK_LP; s; } else if (*s )) { t.kind TK_RP; s; } else if (*s ! || *s || *s |) { t.kind TK_OP; t.op[0] *s; t.op[1] \0; } else if (*s - s[1] ) { t.kind TK_OP; strcpy(t.op, -); s 2; } else if (*s s[1] - s[2] ) { t.kind TK_OP; strcpy(t.op, -); s 3; } else return -1; /* 非法字符 */ out[n] t; } return n; }分词之后转后缀。弹栈条件要区分左右结合左结合用栈顶优先级 当前右结合用栈顶优先级 当前。这一行写反蕴含和等价就全错。static int to_postfix(Token in[], int n, Token out[]) { Token st[256]; int top 0, k 0; for (int i 0; i n; i) { Token t in[i]; if (t.kind TK_VAR) { out[k] t; continue; } if (t.kind TK_LP) { st[top] t; continue; } if (t.kind TK_RP) { while (top st[top-1].kind ! TK_LP) out[k] st[--top]; top--; /* 丢掉左括号 */ continue; } while (top st[top-1].kind TK_OP (prec(st[top-1].op) prec(t.op) || (prec(st[top-1].op) prec(t.op) !right_assoc(t.op)))) out[k] st[--top]; st[top] t; } while (top) out[k] st[--top]; return k; }to_postfix的容量按 256 写死是因为课程设计里公式长度一般不会超过这个量级真要做通用版本把固定数组换成动态扩容即可逻辑不用动。2.4 建树与变元索引绑定后缀序列到树只有一条规则遇变元压栈遇运算符弹。关键在于按元数弹——!弹一个其余弹两个。这里的nd-r st[--top]必须先弹右再弹左顺序搞反整棵树左右颠倒p - q会变成q - p真值表看着差不多对其实全错。static Node *build_tree(Token post[], int n) { Node *st[256]; int top 0; for (int i 0; i n; i) { Node *nd calloc(1, sizeof(Node)); nd-type (post[i].kind TK_VAR) ? VAR : (post[i].op[0] !) ? NOT : (post[i].op[0] ) ? AND : (post[i].op[0] |) ? OR : (post[i].op[1] ) ? IMP : IFF; if (post[i].kind TK_VAR) { nd-name post[i].name; st[top] nd; continue; } if (nd-type NOT) { nd-l st[--top]; /* 一元: 只弹一个 */ } else { nd-r st[--top]; /* 后弹的是右子树 */ nd-l st[--top]; } st[top] nd; } return st[--top]; }树建好之后还要再做一次遍历把所有出现过的变元收集起来并编上号。编号顺序决定了真值表每一列对应哪一位必须和打印、求值共用同一份映射否则反例打印出来代回公式会对不上。这一步在 5.4 会详细讲怎么翻车。static char var_name[32]; static int var_index[128]; /* 初始化为 -1 */ static int var_cnt 0; static void collect_vars(Node *t) { if (!t) return; if (t-type VAR) { if (var_index[(int)t-name] 0) { var_index[(int)t-name] var_cnt; var_name[var_cnt] t-name; } return; } collect_vars(t-l); collect_vars(t-r); }这里用 128 长度的数组直接按字符做下标省掉一次查找代价是只支持 ASCII 变量名。对本场景够用写进报告里说明约束即可。3. 真值表判定2^n 次赋值枚举与后序求值3.1 位掩码代替递归枚举最直观的枚举是写一个长度为 n 的数组递归填 0/1填满一行求一次值。这种写法在报告里好看但常数大、递归深、还要额外维护一个数组。换个角度n 个变元的每一种赋值本质就是 0 到 2^n−1 之间的一个整数。整数m的第j位就是第j个变元的取值。这样一行赋值就是一个unsigned既不用数组也不用递归循环一行就完事。int is_tautology(Node *root, int n) { unsigned total 1u n; /* 必须是无符号, 见 5.1 */ for (unsigned m 0; m total; m) if (!eval(root, m)) return 0; /* 找到一行假, 立即返回 */ return 1; }判定重言式只需要有没有一行是假所以找到第一个反例就能返回不必跑满全表。对非重言式这一条剪枝往往能把耗时砍掉一个数量级对重言式则没有帮助必须老老实实跑完 2^n 行。3.2 后序求值函数求值就是一次递归后序遍历。变元从掩码里取位其余按真值表算。注意这里用位运算|而不是逻辑||两者在 0/1 输入下结果相同但位运算没有短路分支代码更直白static int eval(const Node *t, unsigned mask) { switch (t-type) { case VAR: return (int)((mask var_index[(int)t-name]) 1u); case NOT: return !eval(t-l, mask); case AND: return eval(t-l, mask) eval(t-r, mask); case OR: return eval(t-l, mask) | eval(t-r, mask); case IMP: return (!eval(t-l, mask)) | eval(t-r, mask); case IFF: return eval(t-l, mask) eval(t-r, mask); } return 0; }蕴含那一行是!A | B别写成A | !B。等价用是合法的因为两边都规约到 0/1相等即同真同假。3.3 打印真值表与定位反例答辩时老师最爱问的一句是你这个结论凭什么。光输出一个是重言式没有说服力把整张真值表打出来或者至少把反例那一行打出来才是能自证的做法。void print_table(Node *root, int n) { for (int j 0; j n; j) printf(%c , var_name[j]); printf(| F\n); for (unsigned m 0; m (1u n); m) { for (int j 0; j n; j) printf(%d , (m j) 1u); /* 位序与表头一致 */ printf(| %d\n, eval(root, m)); } }反例单独抽一个函数输出成能直接抄回公式的形式比如p1 q0 r1这样拿手算复核最快void print_cex(Node *root, int n) { for (unsigned m 0; m (1u n); m) { if (eval(root, m)) continue; printf(反例: ); for (int j 0; j n; j) printf(%c%u , var_name[j], (m j) 1u); printf(\n); return; } printf(无反例, 该式为重言式\n); }注意表头和位序必须都走var_name[j]。任何一处改成按字母排序反例就会代回去不成立这种 bug 排查起来最耗时间。3.4 复杂度、剪枝与变量数上限时间复杂度 O(2^n · |F|)|F| 是公式树节点数通常十几到几十。空间复杂度 O(|F|)因为只有一棵树和几个栈。真实的上限在哪n20 时约 104 万行每行几十次函数调用单机一秒内能跑完可以接受n24 就是 1600 万行开始进入十几秒区间n30 直接没戏。所以入口处必须对 n 做限制超过 20 就在报告里写明本实现适用于变元数 ≤ 20 的公式而不是让程序跑到用户以为死机。这一点在 5.1 会展开。还有一层剪枝值得写进报告部分赋值剪枝。如果某个变元取定之后公式的结构已经不可能为真比如某个合取项已经确定是假剩下的变元就不用枚举了。实现上要在求值函数里引入三值逻辑真/假/未知复杂度会上升不少课程设计里属于加分项不是必做项。我的建议是先把完整版跑通、对拍通过再谈这个。4. 等价变换法把公式化成 CNF 再判恒真4.1 真值表不够用时补一条符号推导的路真值表是枚举验证等价变换是符号推导。两条路的输入输出完全一样实现却毫不相干这恰好构成了最好的交叉验证两边结论不一致说明至少有一边写错了而且大概率是边界情况——比如蕴含方向反了、否定内推漏了一层。另一个现实理由是变量数。真值表在 n 变大时指数爆炸等价变换虽然最坏情况也会指数膨胀但对结构化很强的公式比如嵌套的p | !p往往几步就化简完了。两手准备报告里也好写对比分析。下面这段用 Python 写定位是对拍工具不参与主程序。用元组表示语法树(var,p)、(not,a)、(and,a,b)、(or,a,b)、(imp,a,b)、(iff,a,b)。4.2 消去 ↔ 与 →第一步把所有非基本联结词消掉只留!|。规则写死成表原式等价于A - B(A - B) (B - A)A - B!A | B!!AA!(A B)!A | !B!(A | B)!A !Bdef eliminate(e): op e[0] if op var: return e if op not: return (not, eliminate(e[1])) if op imp: a, b eliminate(e[1]), eliminate(e[2]) return (or, (not, a), b) if op iff: a, b eliminate(e[1]), eliminate(e[2]) return (and, (or, (not, a), b), (or, (not, b), a)) return (op, eliminate(e[1]), eliminate(e[2]))注意iff展开成两个方向别只写一个。少写一半的后果是原本的重言式被判成非重言式而真值表那边是对的一对拍立刻暴露。4.3 推到 NNF 再做分配消去之后进入否定范式NNF否定只出现在变元前面。做法是带着一个是否取反的标志往下递归遇到not就翻转标志遇到and/or且标志为真就按德摩根换联结词。def nnf(e, negFalse): op e[0] if op var: return (not, e) if neg else e if op not: return nnf(e[1], not neg) if op and: if neg: return (or, nnf(e[1], True), nnf(e[2], True)) return (and, nnf(e[1], False), nnf(e[2], False)) if op or: if neg: return (and, nnf(e[1], True), nnf(e[2], True)) return (or, nnf(e[1], False), nnf(e[2], False))NNF 到手后做分配律把|分配到里面去得到合取范式。这里用递归重写每次分配完再对新产生的子树继续化简直到不动为止def cnf(e): op e[0] if op in (var, not): return e if op and: return (and, cnf(e[1]), cnf(e[2])) a, b cnf(e[1]), cnf(e[2]) if a[0] and: return cnf((and, (or, a[1], b), (or, a[2], b))) if b[0] and: return cnf((and, (or, a, b[1]), (or, a, b[2]))) return (or, a, b)这段是整条路里最容易爆栈的地方。(p1 q1) | (p2 q2) | ...这种形式分配下去子句数是指数级的。实际用的时候要加节点计数超过阈值就抛出异常退回真值表。课程设计报告里把这条退化策略写进去比硬扛着不写要诚实得多。4.4 子句互补检查与判定CNF 拆开就是一堆子句的合取每个子句是文字的析取。一个子句恒真当且仅当它同时含有某个变元和它的否定——p | !p | 任何东西永远是 1。整个公式是重言式当且仅当每一个子句都恒真。def clauses(e): if e[0] and: return clauses(e[1]) clauses(e[2]) out, stack [], [e] while stack: x stack.pop() if x[0] or: stack.append(x[1]); stack.append(x[2]) else: out.append(x) # (var,n) 或 (not,(var,n)) return [out] def is_tautology_cnf(e): for cl in clauses(cnf(nnf(eliminate(e)))): seen, ok set(), False for lit in cl: key lit[1][1] if lit[0] not else lit[1] pol (lit[0] not) if (key, not pol) in seen: ok True break seen.add((key, pol)) if not ok: return False return Truekey取变元名pol记极性。查的是相反极性是否已出现所以查(key, not pol)而不是(key, pol)。这一处写错判定结果会整体反转而且在小公式上未必能立刻看出来。4.5 拿随机公式对拍两条路单测几个手写公式不够。真正能压出 bug 的是随机生成 双路对拍随机造公式同时喂给 C 的真值表程序和 Python 的 CNF 程序结果不一致就把公式打出来。import random def rand_formula(vs, depth): if depth 0 or random.random() 0.3: return (var, random.choice(vs)) k random.choice([not, and, or, imp, iff]) if k not: return (not, rand_formula(vs, depth - 1)) return (k, rand_formula(vs, depth - 1), rand_formula(vs, depth - 1))变量池取[p,q,r]深度取 3 到 4跑几百轮。三变量的公式里重言式比例不低正好能覆盖两条路的真分支深度加上去之后反例变多覆盖假分支。两边都跑到才算对拍有效。提示对拍脚本不要放进提交的源码包里它是开发期工具。报告里可以用一段说明提到做过随机对拍、覆盖了多少组比贴一堆截图更有说服力。5. 避坑与排查五条踩过的血泪记录5.1 小公式全对变元一多就卡死现象3 个变元秒出结果加到 5 个变元时程序停住任务管理器里 CPU 占满等十几秒才出结果加到 8 个变元直接被人当成死循环。原因两个问题叠在一起。一是1 n用的是有符号intn 超过 30 时左移溢出成负数循环边界变成未定义行为二是非重言式也跑满全表没有在找到第一个反例时返回。多数人只改了第二点n 一大照样出问题。解决枚举上限统一用1u ntotal声明成unsignedis_tautology里第一处!eval(...)直接return 0入口处加if (n 20) { 提示并退出 }。三处一起改才是完整方案。我后来还在报告里补了一张不同 n 下的实测耗时表答辩时被问复杂度直接指过去。5.2 蕴含的结合方向反了现象p - q - r在真值表里出现反例p1 q0 r0手算却认为是重言式把公式改成显式加括号的p - (q - r)后结果正确。原因调度场算法的弹栈条件写成了prec(栈顶) prec(当前)对右结合的-也生效导致先算左边解析成(p - q) - r。这个 bug 只在连续出现两个及以上同优先级运算符时触发单运算符的测试用例全过。解决把结合性判断单独抽成right_assoc()弹栈条件改成优先级更高或优先级相同且当前运算符左结合。!--三个标右结合。改完加一条专项用例p - q - r - s四种变元全枚举和手算的 16 行逐行对。5.3 否定被当成二元运算符现象!p q的真值表里p1 q1一行算出 0正确结果应该是 1。把公式换成(!p) q又是对的。原因建树函数对所有运算符一视同仁弹两个操作数。遇到!时把栈里相邻的两个节点都弹了出来!作用到了整个p q上。因为!优先级最高后缀序列里它紧跟在p后面弹两个刚好把p和更早的东西凑一对不报错但语义全错。解决建树时按元数分派NOT只弹一个操作数。同时检查分词阶段!是否被正确识别成运算符而不是变元。补一条用例!p q与!(p q)对比两者真值表必须不同相同就说明还有问题。5.4 反例代回去不成立现象程序打印反例: p1 q0把这个赋值手工代进公式算出来是 1和程序结论相反。换个公式又正常。原因var_index是按树的遍历顺序编号的打印表头时却按字母顺序排了一列两边错位。三变量时p q r恰好和遍历顺序一致四变量以上就不一定了。解决表头、位序、反例打印三处全部统一走var_name[]数组任何一处都不再单独排序。顺手加了个自检print_table输出后随机取一行用打印出来的赋值字符串重新解析求值和原结果比对不一致就报错。这个自检后来救过我好几次。5.5 等价变换把内存吃爆现象CNF 程序在含多个析取项的公式上跑了几秒后抛RecursionError或者内存直接涨到几个 G 被系统杀掉。原因先做分配律再做化简中间式在分配过程中指数膨胀。(a1 b1) | (a2 b2) | (a3 b3)分下去就是 8 个子句每多一层翻一倍十几层就上百万节点。解决三步。第一把双重否定、吸收律A | (A B) A这些化简规则提前到分配之前能砍掉大量冗余第二给cnf加一个全局节点计数器超过阈值比如 20 万抛异常由调用方捕获后退回真值表第三在报告里明确写清等价变换法适用于子句数可控的公式超出范围自动降级。坦白边界比假装没有边界更靠谱。6. 进阶位并行真值表与自动对拍真值表法最耗的是那 2^n 次独立求值。其实相邻的几十行赋值高度相似完全可以打包一起算——把 64 行塞进一个uint64_t每个节点维护一个 64 位掩码表示该子式在这 64 种赋值下的真假。|~一次处理 64 行指令级并行白送。/* 变元 j 在 64 行里的真值模式: 每 2^j 位翻转一次 */ static uint64_t var_pattern(int j) { uint64_t v 0; for (int i 0; i 64; i) if ((i j) 1) v | 1ull i; return v; } static uint64_t eval_bits(const Node *t) { switch (t-type) { case VAR: return var_pattern(var_index[(int)t-name]); case NOT: return ~eval_bits(t-l); case AND: return eval_bits(t-l) eval_bits(t-r); case OR: return eval_bits(t-l) | eval_bits(t-r); case IMP: return (~eval_bits(t-l)) | eval_bits(t-r); case IFF: return ~(eval_bits(t-l) ^ eval_bits(t-r)); } return 0; }判定改成分批推进每组 64 行算一次结果等于~0ull说明这 64 行全真继续下一批出现任何一位 0 就说明有反例定位到具体是哪一位就能还原赋值。n ≤ 6 时一批搞定n 20 时是 16384 批比逐行求值快一个量级左右。注意var_pattern只对 j 6 有效超过 6 位的模式要按批偏移重新生成这一点在实现时容易漏。配合前面的 Python 对拍脚本随机生成几百条公式C 版真值表、C 版位并行、Python 版 CNF 三条路互相比对任意两条不一致就打印公式。这套组合拳跑下来解析层和判定层的边界情况基本都能压出来。方法时间复杂度适用变量数主要风险逐行真值表O(2^n·|F|)≤ 20大 n 时慢但不会错位并行真值表O(2^n·|F|/64)≤ 24位模式生成易错等价变换 CNF最坏指数结构化公式中间式膨胀血泪教训是别信看起来对。我现在的习惯是每加一个运算符、每改一次弹栈条件都强制把那条专项用例重跑一遍再跑一轮随机对拍两边都不报错才算过。这三条路互为黑匣子任何一条出问题另外两条立刻能指出来。希望帮到你。本文还有配套的精品资源点击获取