《山东理工大学计算机学院 课程设计》由会员分享,可在线阅读,更多相关《山东理工大学计算机学院 课程设计(20页珍藏版)》请在金锄头文库上搜索。
1、1山东理工大学计算机学院山东理工大学计算机学院课课程程设设计计(数据结构)班级* 姓名* 学号* 指导教师*二零一零年七月七日2课程设计任务书及成绩评定课程设计任务书及成绩评定 课程名称重言式的判定 、题目的目的和要求、题目的目的和要求巩固和加深对数据结构的理解,通过上机实验、调试程序,加深对课本知 识的理解,最终使学生能够熟练应用数据结构的知识写程序。 (1)通过本课程的学习,能熟练掌握几种基本数据结构的基本操作。 (2)能针对给定题目,选择相应的数据结构,分析并设计算法,进而给 出问题的正确求解过程并编写代码实现。 、设计进度及完成情况日期内容6.286.29选取参考书,查阅有关文献资料,
2、完成资料搜集 和系统分析工作。6.307.2创建相关数据结构,录入源程序。7.57.7调试程序并记录调试中的问题,初步完成课程设 计报告。7.87.10上交课程设计报告并进行课程设计答辩,要求每 个同学针对自己的设计回答指导教师3-4个问题。 考核结束后将课程设计报告和源程序的电子版交 班长统一刻光盘上交。、主要参考文献及资料、主要参考文献及资料1 严蔚敏 数据结构(C 语言版)清华大学出版社 19992 严蔚敏 数据结构题集(C 语言版)清华大学出版社 19993 谭浩强C 语言程序设计清华大学出版社4 与所用编程环境相配套的 C 语言或 C+相关的资料3、成绩评定:、成绩评定:设计成绩:(
3、教师填写)指导老师:(签字)二年月日1目目录录第一章 概述1第二章 问题描述2-3第三章 概要设计3-5第四章 程序流程图6第五章 详细设计及实现代码6-15第六章 调试过程中的问题及系统测试情况16第七章 结束语172第一章 概述课程设计是实践性教学中的一个重要环节,它以某一课程为基础,可以涉及和课程相关的各个方面,是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用,理解和掌握课程的相关知识。 数据结构是一门重要的专业基础课,是计算机理论和应用的核心基础课程。数据结构课程设计,要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面
4、,加深对课程基本内容的理解。同时,在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。选择题目:重言式的判定选择题目:重言式的判定一、问题描述1.一个逻辑表达式如果对于其变元的任一种取值均为真,则成为重言式;反之,如果对于其变元的任一种取值都为假,则称为矛盾式,然而,更多的情况下,既非重言式,也非矛盾式。写一个程序通过真值表判别一个逻辑表达式属于上述哪一类。 基本要求如下:(1)逻辑表达式从终端输入,长度不超过一行。逻辑运算符包括“” 、 “” 和“” ,分别表示或、与和非,运算优先程度递增,但可有括号改变,即括号 内的运算优先。 逻辑变元为大写字母。 表达式中任何地方
5、都可以含有多个空格符。(2)若是重言式或矛盾式,可以只显示“True Forever”或“False Forever” , 否则显示“Statisfactible”以及变量名序列,与用户交互。若用户对表达式变元 取定一组值,程序就求出并显示逻辑表达式的值。 (3)本程序先使用栈将逻辑表达式的变量进行存储,然后将栈中的元素作为 二叉树的结点结构,然后根据优先级读取表达式建立二叉树,并通过逐个判断根 实现对重言式的判别。 2. 程序执行的命令 (1)输入逻辑表达式 (2)判断表达式是重言式还是矛盾式 (3)若既不是 重言式也不式矛盾式,则对变元取定值,并显示逻辑表达式的值 (4)结束 3测试数据(
6、1) (A|A)预计输出结果True ForeverFalse ForeverTrue ForeverFalse ForeverStatisfactibleStatisfactible二. 概要设计1为实现上述程序功能,需要两个抽象数据类型,如下:/根据表达式建立的二叉树的结点定义;(1)typedef struct btdnodechar data;struct btdnode *lchild;struct btdnode*rchild;*bitree;/对操作符栈和变量堆栈的操作;void creatstack(sqstack if(!st.base) exit(0);st.top=st.
7、base;st.stacksize=stack_size_normal;void push(sqstack zigen-rchild=r;/分树的链接if(ll-rchild=NULL;if(int(r-data)=65r-rchild=NULL;2.本程序主要分为六个模块 (1)主程序模块 void main () 初始化 While 接受命令 处理命令 if (choice=0)退出 (2)对栈的操作模块。 (3)二叉树的建立模块,采用自底向上根据运算符地优先级来建立子树 函数,读取逻辑表达式。 (4)逻辑运算符的优先级判别模块。 (5)重言式的识别函数模块。 (6)求值模块。3.各个模块
8、之间的调用关系具体如下图:主函数模块 void main()对操作符栈 和变量栈的 操 作 模 块 creatstack() pop() push() geittop()逻辑运算 符的优先 级判别模 块 youxianji()二叉树的 建立模块 creattree ()重言式的 判别模块 judge()用 户 为 变 量 赋 值模块 user()求值模 块 Valuetre e()6三. 详细设计#include#include#include#include#include#define stack_size_normal 100#define bianliang_max 20#define
9、 str_max 60int zuhebianliang_max;/变量的取值组合数组定义;int N;/变量个数;/根据表达式建立的二叉树的结点定义;typedef struct btdnodechar data;struct btdnode *lchild;struct btdnode*rchild;*bitree;/识别表达式使用的堆栈定义,它存放的都是树的结构;typedef struct lnode_optrstruct btdnode *base;/栈中的元素都是树的结点结构;struct btdnode *top;int stacksize;sqstack;/用于产生变量的各种取
10、值组合;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(ll-rchild=NULL;if(int(r-data)=65r-rchild=NULL;/逻辑运算符的优先级判别;char y
11、ouxianji(char lie,char hang)inti,j;char bijiao77= ,|,10push(logic,logic_di);while(*s!=NULL)if(int(*s)=65push(variable,variables);else if(int(*s)90|int(*s)data)case data=*s;push(logic,logics);break;case =:/脱括号并接受下一个字符;pop(logic,kuohao);break;case :pop(logic,theta);/弹出逻辑运算符pop(variable,a);/弹出变量b=NULL;
12、if(theta-data!=)pop(variable,b);/建树的函数调用k=k+1;11create(theta,b,a);push(variable,theta);/将临时的根作为新的变量压入变 量栈中;if(*s!=#if(!logics)exit(0);logics-data=*s;push(logic,logics);elses=s-1;break;s+;tree=theta;/根据变量的取值组合并利用逻辑表达式的性质对树进行求值int value_tree(bitree tree)if(!tree) return 0;/遇到空的结点;else if(tree-data!=|e
13、lse if(int(tree-data)data)90)/找到的是运算符;switch(tree-data)case |: return(value_tree(tree-lchild)|value_tree(tree-rchild);case case : return(!value_tree(tree-rchild);12/用户设定变量的一种取值;void user()int i;coutzuhei-65;void main()char strstr_max,stringstr_max,*pstr;int loop=20,choice,i=0,choose,sum;bitree Tree;
14、while(loop)pstr=str;i=0;intSUM=0,l;/用于累加变量的每种组合的逻辑表达式的结果;可以作为逻辑表达式 类别判别的根据coutN;sum=int(pow(2,N); /变量组合的总数;coutstr;/重言式的正确读取;for(;*pstr!=NULL;pstr+)if(*pstr!= ) stringi+=*pstr;13stringi=#;stringi+1=0;coutchoose;switch(choose)case 1:/对变量的不同组合依次调用重言式二叉树的求值函数;并判别重言式的类 别;creattree(string,Tree);/建立重言式的二叉
15、树;for(loop=0;loop0if(choice=0)exit(0);loop-;15四调试分析(1)提示运行有误,漏掉标点,打错字符,关键字使用不当等,对各种语法的不 熟练。尽量的掌握数据结构中学到的知识体系,咨询老师,注意自己的无谓的失误。(2)在逻辑符号的优先级判别处出现失误,导致出现了错误结果,后发现即时改 正。(3)模块设计包括结构体模块,操作算法模块和主函数模块,操作算法模块主要包 括了栈和树的函数,虽然都放在一个大类中,但是比较方便。五 测试结果执行命令 2 键入逻辑表达式(A|A)&(B|B) 执行命令 1 判断出该逻辑表达式是重言式 执行命令 2 输入逻辑表达式(A&A)&C 执行命令 1 判断出该逻辑表达式是矛盾式 执行命令 2 键入逻辑表达式(A|B)&(A|B) 执行命令 1 判断出该逻辑表达式既不是重言式也不是矛盾式16六 结束语在设计中我们基本能按照规范的方法和步骤进行,首先对现有的系统进行调查,并查阅有关资料,最后确定设计方案,然后设计并制作,