1、 计算机科学学院计算机科学学院 课程设计报告课程设计报告 课课 程程 数据结构 题题 目目 重言式判别 年年 级级 专专 业业 软件工程 学学 生生 学学 号号 指导教师指导教师 2012 年 11 月 7 日 数据结构课程设计数据结构课程设计 2 重言式判别重言式判别 一、一、目的目的 巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最 终使学生能够熟练应用数据结构的知识写程序。 （1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。 （2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确 求解过程并编写代码实现。 二、二、需求分析需求
2、分析 （1）逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括“|” ， “ typedef struct btdnode*bitree; /识别表达式使用的堆栈定义,它存放的都是树的结构，鉴于逻辑符号的优先不同，我们需要 用到堆栈; typedef struct lnode_optrsqstack; 数据结构课程设计数据结构课程设计 3 2、算法的设计 本设计从总体上划分可分为四个模块， 第一个模块为树与堆栈的创建。 void create(bitree 当逻辑表达式读完后-子根 root 就是 一棵完整的二叉树。用穷举法得出所有可能组合，对二叉树进行先序遍历，对存放在上面的 表达式进行求
3、值。并用两个栈分别存放运算符和变量，来判别是否为重言式。 四、四、详细设计详细设计 设计抽象数据类型对应的类定义。 （如用 C 实现则没有这项） typedef struct btdnode char data; struct btdnode *lchild; struct btdnode *rchild; *bitree; 数据结构课程设计数据结构课程设计 5 /识别表达式使用的堆栈定义,它存放的都是树的结构; typedef struct lnode_optr struct btdnode *base; /栈中的元素都是树的结点结构； struct btdnode *top; int st
4、acksize; sqstack; 设计每个 成员函数； void creatzuhe(int n)/用于产生变量的各种取值组合; int i,num=0,j=0,e; int tempbianliang_max; for(i=0;i=0) e=tempj-; zuhenum+=e; /自底向上地根据运算符地优先级来建立分子树函数;当逻辑表达式读完后-子根 zigen 就是一 棵完整的二叉树 int k=0;/建树的标志，k1 表示第一次建立分子树，要对左右孩子的指针域处理 void create(bitree zigen-rchild=r;/分树的链接 if(l l-rchild=NULL;
5、 if(int(r-data)=65 r-rchild=NULL; 数据结构课程设计数据结构课程设计 6 /逻辑运算符的优先级判别； char youxianji(char lie,char hang) int i,j; char bijiao77= ,|, for(i=0;i=65 push(variable,variables); else if(int(*s)90|int(*s)data) case data=*s; push(logic,logics); break; case =:/脱括号并接受下一个字符; pop(logic,kuohao);break; case :pop(log
6、ic,theta);/弹出逻辑运算符 pop(variable,a);/弹出变量 b=NULL; if(theta-data!=) pop(variable,b); /建树的函数调用 k=k+1; create(theta,b,a); push(variable,theta);/将临时的根作为新的变量压入变量栈中; if(*s!=# if(!logics) exit(0); logics-data=*s; push(logic,logics); else s=s-1; break; 数据结构课程设计数据结构课程设计 8 s+; tree=theta; /根据变量的取值组合并利用逻辑表达式的性质对树进行求值 i
