数据结构课程设计：重言式判别算法与逻辑表达式解析

重言式判定是计算机科学中的一个重要概念，特别是在形式逻辑和自动推理领域。在这个课程设计报告中，学生汪国志，年级10，专业软件工程，在中南民族大学计算机科学学院进行了一项关于重言式判别的项目。其目标是通过实际操作和编程实践，加深对数据结构的理解，并将理论知识应用于解决实际问题。 课程的核心任务是设计一个程序，能够接收用户输入的逻辑表达式，这些表达式可能包含"|"（或）、"&"（与）和"~"（非）运算符，遵循一定的运算优先级规则，同时允许使用括号进行调整。输入的逻辑变元用大写字母表示，表达式中的空格不影响处理。系统需判断表达式是否为重言式（总是为真），矛盾式（总是为假），或者可满足式（对于某些变量取值组合，表达式结果为真，其他情况下为假）。 设计的关键在于构建数据结构和算法。首先，采用了二叉树的数据结构来表示逻辑表达式，利用递归性质，将输入的字符串转换为二叉树的节点。每个节点可能代表一个变量、运算符或一个子表达式，这与二叉树的中序遍历顺序相契合。为了处理运算符的优先级，使用了堆栈数据结构，根据运算符的优先级进行压栈和弹栈操作。 设计过程分为四个模块： 1. **树与堆栈的创建**：函数`create`用于构建逻辑表达式对应的二叉树，`creatstack`负责初始化堆栈。`creattree`函数则将字符数组转换为二叉树的根节点。 2. **树与堆栈的操作**：`value_tree`函数用于计算二叉树的值，即执行逻辑运算；`push`和`pop`函数分别用于将运算符和节点压入和弹出堆栈，以处理运算符优先级和括号的影响。 3. **逻辑表达式处理**：在第二模块的基础上，设计算法实现对输入逻辑表达式的解析和求值。当遇到运算符时，根据堆栈中的运算符进行相应的逻辑操作，然后继续遍历表达式。 4. **结果输出**：程序需要根据逻辑表达式的性质，输出“True forever”、“False forever”或“Satisfactible”，以及变量名序列。如果用户给出变量值，还需要计算并显示该表达式的具体结果。 通过这个项目，学生不仅提升了数据结构（如二叉树和堆栈）的运用能力，还锻炼了解决复杂逻辑问题的算法设计技巧，以及程序调试和交互的能力。这有助于巩固理论知识，为今后在软件工程领域的工作打下坚实基础。