数据结构报告—重言式判别.doc

promote the extension of strictly administering the party grass-roots, but also the educational practice of the mass line of the party and three-three special education results achieved further inherited and expanded. To realize two a learning education is a necessary solution to the present problems of party construction. Strengthen problem consciousness and insisted on problem-oriented, is full of strictly administering the party since the partys 18 a distinctive feature, a successful experience. Secretary Wang noted that some party members still have political awareness, lack of political responsibility issues, party awareness and consciousness of the problem belief does not really believe, slim does not actually fix problems, outspoken, and jump on the assessment of the partys policies, and so on. Bi Lifu Secretary pointed out that a quarter of the economic situation is very serious, there is pressure on environment, seasonal factors and other objective reasons, but mainly subjective problem, is the problem of party members and cadres. Some depressed, negative slack, not responsible, . Double six, one, and two took the lead, build energy burst, Hongshan district, economic prosperity, eco-livable, civilized and harmonious island. It certainly can not be separated from the whole area 646 grass-roots party organizations and 14,146 members of broad participation and support. Through the two study and education, so that every cell of the party health, every organization is strong, so that all members of the vanguard and exemplary role, all the fighting bastion role of grass-roots party organizations into full play so that we can cross the Rapids, overcome all difficulties and the smooth realization of the Thirteen-Five goal. Second, basic learning, focus on learning education must understand the learning content and learning styles Foundation learning these four words are important information inside is very large, capture profound work truth in life. For example, I often say that the good Carpenter NAO Carpenter, why do some carpenters made furniture to have everybody likes it, Carpenter we are not willing to look for him? are apparently two people high and low technology, dig into the deep is firmer when both of his apprentices are not solid, there is no good that way. Luban art of story primary school are learn had, first after six mark test practice conduct, and practice cultivation, and practice perseverance, and practice patience, then with seven days seven night mill axe theory armed, and unity action, seriously learning XI General Secretary on reform development stable, and Interior diplomatic defense, and rule party ruling army of important thought, seriously learning to XI comrade for General Secretary of Central ruling acting political new concept new thought new strategy, seriously learning XI General Secretary study in Inner Mongolia important speech spirit, Guide party members and a deep understanding of a series of important speeches rich connotation and core ideas, which began so thoroughly Marxist positions实习报告题目：重言式判别班级：计算机学院 姓名：卢魏旭 学号： 完成日期：2012年11月一、 需求分析试写一个程序，通过真值表判断一个逻辑表达式属于哪一类的表达式基本要求：1） 逻辑表达式从终端输入，长度不超过一行，逻辑运算符包括“|”，“&”和“”，分别表示或，与和非，运算优先程度递增，但可以由括号改变，即括号内的运算符优先。逻辑变元为大写字母，表达式中任意地方都可以含有空格符。2） 若是重言式或者矛盾式，可以只显示“True forever”或者“False forever”，否者显示“Statisfactible”，与用户交互，若用户对表达式中变元取定一组值，程序就求出并显示逻辑表达式的值。3） 附加要求，可以根据用户要求，列出该逻辑表达式的真值表。测试数据：1) (A|A)&(B|B)2) (A&A)&C3) A|B|C|D|E|A二、 概要设计为实现上述程序功能，以二叉树的结构来存储逻辑表达式，通过一个辅助栈来完成建树过程二叉树的抽象数据类型定义为：ADT Bitree数据对象 D：D是具有相同特性的数据元素的集合数据关系 R：基本操作:creatbitree(&B,&S1,&S2,*a)初始条件：树B，栈S1，S2存在操作结果:通过两个辅助的栈S1，S2将元素a值建在二叉树内showtree(B)初始条件：二叉树B存在操作结果：先序遍历二叉树，输出每一个节点中的信息（用于检测）voluation($B,c,value)初始条件：二叉树B存在操作结果：通过先序遍历二叉树，对树中变量为c的结点赋值value excel(B,i,c,v,*x)初始条件：二叉树存在操作结果：通过递归的算法在一维数组v中记录各个变量各种赋值情况（所有赋值情况的真值结果记录）此外以栈的存储结构做辅助栈的抽象数据类型定义为：ADT Bstack数据对象:D=a|ai-ElemSet,i=1,2,3n数据关系:R1=|ai-1,ai -D,i=1,2,3n基本操作：creatstack(&S)操作结果：建立一个空栈SPushstack(&S,&B)初始条件：栈S存在操作结果：将一个二叉树的结点入栈Popstack(&S，&B)初始条件：栈S存在操作结果：从栈中取出一个二叉树的结点showstack(S)初始条件：栈S存在操作结果：访问栈内结点，查看元素信息Gettop(S)初始条件：栈S存在操作结果：返回栈顶元素三、 详细设计#include#include#include#includetypedef struct BiTnodechar data;int value;struct BiTnode *lchild,*rchild;*Bitree;typedef struct BstackBitree *top;Bitree *base;void creatstack(Bstack &S)S.base=(Bitree*)malloc(sizeof(BiTnode);S.top=S.base;void Pushstack(Bstack &S,Bitree &B)*S.top=B;S.top+;void Popstack(Bstack &S,Bitree &B)S.top-;B=*S.top;Bitree Gettop(Bstack S)return *(S.top-1);int Judge(char c) /判断字符是运算符还是操作符if(c=A&c=a&c;break;case &:c=;break;case :c=;break;case (:c=;break;case #:c=;break; break;case &:switch(c2) case |:c=;break;case &:c=;break;case :c=;break;case (:c=;break;case #:c=;break; break;case :switch(c2) case |:c=;break;case &:c=;break;case :c=;break;case (:c=;break;case #:c=;break; break;case (:switch(c2) case |:c=;break;case &:c=;break;case :c=;break;case (:c=;break;case &:c=;break;case :c=;break;case (:c=;break;case ):c=;break;case #:c=;break; break;case #:switch(c2) case |:c=;break;case &:c=;break;case :c=;break;case (:c=data);int creatBiTree(Bitree &B,Bstack &S1,Bstack &S2,char *a) /S1为a操作符栈，为运算数栈 建立二叉树过程类似于算术表达式求值int i=0,len=0,flag=1; char c;Bitree b1;b1=(Bitree)malloc(sizeof(BiTnode);b1-data=#;b1-value=0;b1-lchild=NULL;b1-rchild=NULL;Pushstack(S1,b1); /先在运算符栈里存放一个data值为“#”的结点做标记while(ai)len+;i+;i=0;c=a0;while(c!=#|Gettop(S1)-data!=#)c=ai;if(c= ) /若有空格，直接忽略掉i+;continue;if(i=len)c=#;Bitree b;b=(Bitree)malloc(sizeof(BiTnode); 建立一个树的结点b-data=c;b-value=0;b-lchild=NULL;b-rchild=NULL;if(Judge(c)Pushstack(S2,b); /若是操作数的结点则进栈i+;continue;elsechar c1=compare(Gettop(S1)-data,c);if(c1=-1)flag=0;break;switch(c1)case :printf(执行D“:printf(执行D“”: n); /如果栈顶运算符优先级高，则先建立二叉树char c2=Gettop(S1)-data;Bitree a0,a1; /先取一个运算符和一个操作数，将操作数连接在运算符的右孩子上Popstack(S1,a0);Popstack(S2,a1);a0-rchild=a1;if(c2!=) /如果不是“”运算符，再取一个结点连接在运算符结点的左孩子上Bitree a2;Popstack(S2,a2);a0-lchild=a2;Pushstack(S2,a0);elsePushstack(S2,a0);if(flag) /表达式输入无误则继续进行B=Gettop(S2);return 1;elsereturn 0;void caculate(Bitree B) /采用后序遍历判断逻辑表达式的真值if(B)caculate(B-lchild);caculate(B-rchild);switch(B-data)case |:B-value=B-lchild-value|B-rchild-value;break;case &:B-value=B-lchild-value&B-rchild-value;break;case :B-value=!B-rchild-value;break;case 0:B-value=0;break;case 1:B-value=1;break;void showtree(Bitree B) /先序遍历二叉树if(B)printf(%c ,B-data);showtree(B-lchild);showtree(B-rchild);void voluation(Bitree B,char c,int value)/采用先序遍历为二叉树的变量赋值if(B)if(B-data=c)B-value=value;voluation(B-lchild,c,value);voluation(B-rchild,c,value);void show(char *a)int i=0;while(ai)if(ai= )i+;continue;printf(%c,ai);i+;void excel(Bitree B,int i,char *c,int v,int *x) /采用递归算法为所有的变量赋值，用数组v记录下每一种变量复制后逻辑表达式的真值if(ci!=0)voluation(B,ci,0);i+;excel(B,i,c,v,x);i-;voluation(B,ci,1);i+;excel(B,i,c,v,x);elsecaculate(B);v*x=B-value;(*x)-;int search(char *a,char *ch) /查找表达式中的变量，放入ch数组中int i=0,k=0,flag=1;while(ai) if(ai=A&aivalue);void change(int *b,int x,int sum) /将十进制转换为二进制while(x!=0)bsum=(x%2);x=x/2;sum-;void TrueExcel(char *a,char *ch,int j,int *v2,int *v1) /输出真值表int i=0;while(chi!=0)printf(%c ,chi);i+;printf(|);show(a);printf(n);for(int l=0,m=pow(2,(double)j)-1;lpow(2,(double)j);l+,m-)change(v2,l,j-1);for(int k=0;kj;k+)if(v2k=-1)printf(0 );elseprintf(%d ,v2k);printf(| %dn,v1m);void main()int j=0,i=0,n,v1200,v2200,flag=0;Bitree b;Bstack S1,S2;creatstack(S1);creatstack(S2);char a100,ch10;/a记录表达式,ch记录变量值for(int k=0;k10;k+)/初始化变量数组chk=0;for(int m=0;m200;m+)/初始化真值表数组v2m=-1;v1m=-1;gets(a);/输入表达式j=search(a,ch);/获取所有变量的个数yn=pow(2,(double)j)-1;/要赋值的次数flag=creatBiTree(b,S1,S2,a);/根据表达式建立二叉树if(flag)excel(b,0,ch,v1,&n);/计算所有变量赋值的真值switch(Judge2(v1)case T:printf(表达式为永真式n);break;case F:printf(表达式为永假式n);break;case O:printf(表达式为不确定式n);selfvoluation(b,ch,a);break;elseprintf(表达式输入有误n);TrueExcel(a,ch,j,v2,v1);system(PAUSE);四、 调试分析1、 本程序实现了逻辑表达式的求值，判断，以及真值表的输出，程序的难点在于逻辑表达式的二叉树建立，以及其判断，二叉树的建立creatbitree()依靠两个工作栈实现的，形式类似于算术表达式的求值，不过这里是建树，存放变量的结点作为叶子结点，存放运算符的结点作为根结点，这是自底向上的算符优先法，第二个难点在于对所有的变量的所有情况赋值，这里采用了简单的递归算法，这个算法我自己做的时候花了很长时间来想，excel()递归时候，对每个变量有0和1两种赋值情况，每当递归到最顶层时，调用caculate()算法计算一次真值，然后将值存放到函数携带的一维数组中去。2、 本程序中最核心的算法应该是caculate()算法，采用的是后序遍历的方法，通过根节点的运算符结合左右孩子结点中变量所携带的value值计算真值，并将结果写入到根结点里去，最终一棵树的真值将会存放在树的根结点里（最顶层的那个结点里）。3、 本程序中另一个亮点就是真值表的输出，根据excel()函数中得到的真值数组v，然后将对应的变量值输出来，这里巧妙的采用将十进制转二进制的方法把各种赋值情况列出来，比较新颖，详情见测试结果。4、 讨论时间复杂度，这里面涉及到递归的算法，无论是先序还是后序遍历，时间复杂度都是O(n),5、 本程序中，采用二叉树的形式记录逻辑表达式，便于管理和赋值，充分利用了递归的思想以及先序遍历，后序遍历的优点。程序的思路清晰，不过就是代码有点冗余，算法可能有点复杂了。6、 经验与体会：在本次程序实习中，起步最难，建立二叉树比较陌生，刚开始，对树的概念不是很清晰，不知道以何种方式建树，后面是参照算术表达式求值的方法来建的，总算是学会了一些方法，调试过程很长，花了很多时间在上面，尤其是那个递归求值，和真值表输出，是自己不断探索与尝试想出来的，也算是一种进步与收获。五、 用户手册1、 本程序的运行环境为DOS操作系统，执行文件为：重言式判别.exe。2、 进入演示程序后即显示文本方式的界面3、 键入逻辑表达式，要求变量均为大写，可以输入0和1，输入时确保逻辑表达式是正确的，若像这种（A|B）表达式也是不允许的，因为外面的括号是多余的，本程序没有此判断功能，所以输入的表达式不能有多余的符号。4、 输入表达式后，程序会给出判断类型，如果是不确定行，则与询问用户是否自行赋值，待用户决定后作出相应判断，最后会输出该逻辑表达式的真值表以供用户参考。六、 测试结果如图所示七、 附录源程序文件名清单：重言式判别.c+ /主程序八、 验收过程1、 验收时间：周一晚上机时间，6：009：00；2、 验收地点：一教115机房；3、 验收教师：王立波；4、 流程概要：1） 这次验收中，老师没有怎么询问，基本上就是我在按照程序运行的流程讲了每一个算法的功能，同时强化了自己的理解，期间，老师对我的真值表的输出算法比较感兴趣，向其解释了为什么用到了十进制转二进制的办法，个人觉得这是一个取巧的算法，老师比较满意。2） 解答完毕后，老师给出了相应的打分。3） 验收结束。涉及重大决策事项、重要人事任免、重大项目安排和大额度资金使用等，具有决策、行政执法、行政许可、部门管理等决策、审批、自由裁量、事务管理决定权的领导岗位。To sum up, is divided into 9 main parts: 1. with regard to persisting and developing socialism with Chinese characteristics. 18 since the XIOn more than one occasion, General Secretary of the historical origin and development process of socialism with Chinese characteristics, the road of socialism with Chinese characteristics, System Info, system, uphold and develop the understanding of socialism with Chinese characteristics is determined to have been profoundly expounded, further strengthened the party and the people adhere to and develop the confidence and determination of the socialism with Chinese characteristics. XI General Secretarys speech in this regard include the peoples yearning for a better life, that is our goal, closely focus on the development of socialism with Chinese characteristics study and publicize the spirit of party 18, the unwaveringly adhere to the development of socialism with Chinese characteristics, the persistence and good use of Mao Ze-Dongs thought of soul. 2. with regard to the Chinese dream of realizing the great rejuvenation of the Chinese nation. 18 closing soon, the new Central collective leadership when they visited the exhibition of the road to recovery, XI, General Secretary of the solemn declaration the great rejuvenation of the Chinese nation, the greatest dream of the Chinese nation in modern times. Zhihou, on more than one occasion, General Secretary expounded the scientific connotation of Chinese dream, realize the Chinese dream must take the road, carry forward the spirit and cohesion of Chinese forces, gradually formed the China dream, a strategic thought. And practice with the Chinese dream, reflects the history of the new session of the CPC Central Committee, and conforms to the development trend and the people hope, embodies the greatest common divisor and the consensus of Chinese people at home and