数据结构线性表的基本操作

PAGE山东建筑大学计算机科学与技术学院课程设计说明书题目： 二叉树、树的遍历，重言式的判别课程： 数据结构院（部）： 专业： 班级： 学生姓名： 学号： 指导教师： 完成日期： 山东建筑大学计算机学院课程设计说明书PAGEI目录课程设计任务书一 I课程设计任务书二 II课程设计任务书三 错误!未定义书签。题目一 4一、问题描述 4二、基本要求 4三、算法思想 4四、数据结构 4五、模块划分 4六、源程序 5七、测试数据 5八、测试情况 10题目二 12一、问题描述 12二、基本要求 12三、算法思想 12四、数据结构 12五、模块划分 12六、源程序 13七、测试数据 16八、测试情况 17题目三 错误!未定义书签。一、问题描述 错误!未定义书签。二、基本要求 错误!未定义书签。三、算法思想 错误!未定义书签。四、数据结构 错误!未定义书签。五、模块划分 错误!未定义书签。六、源程序 错误!未定义书签。七、测试数据 错误!未定义书签。八、测试情况 错误!未定义书签。结论 27参考文献 28课程设计指导教师评语 29山东建筑大学计算机学院课程设计说明书PAGEI山东建筑大学计算机科学与技术学院课程设计任务书三设计题目重言式判别指导教师汤晓兵班级信计102学生刘扬已知技术参数和设计要求[问题描述]一个逻辑表达式如果对于其变元的任一种取值都为真，则称为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式；然后，更多的是既非重言式，也非矛盾式。试写一程序，通过真值表判别一个逻辑表达式属于上述哪一类。[基本要求]1．逻辑运算符包括“|”，“&”和“~”，分别表示或，与和非，运算优先程度递增，但可由括号改变，即括号内的运算优先。2．逻辑变元为26个大小写字母，还可以是确定的值1或0，分别表示逻辑真和假。3．表达式中任何地方都可以含有多个空格符。4．程序结果会显示表达式的真值表，所有变量名，和运算所耗时间（毫秒为单位）。设计内容与步骤[实现提示]识别逻辑表达式的符号形式并建立二叉树可以有两种策略：自底向上的算符优先法和自顶向下分割，先序遍历建立二叉树的方法。用递归实现。设计工作计划与进度安排课程设计按照教学要求需要两周时间完成，两周中每天（按每周5天）至少要上机6小时来调试程序。总共至少要上机调试程序60小时。设计考核要求考勤20%课程设计说明书50%程序实现30%指导教师（签字）：教研室主任（签字）题目一一、问题描述对任意给定的二叉树建立它的二叉链表存储结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。二、基本要求1对给定节点，建立二叉链表存储结构；2利用栈的上述五种基本运算实现先序、中序、后序三种遍历。3输出三种遍历结果三、算法思想以字符串的形式“根左子树右子树”创建一棵二叉树。利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。四、数据结构（1）二叉树定义如下：typedefstructBiTNode{chardata; intnum; structBiTNode*lchild,*rchild;}BiTNode,*BiTree;（2）栈定义如下：typedefstruct{BiTree*top;BiTree*base;intStackSize;}Stack;五、模块划分voidInitStack(Stack*S)初始化栈。intStackEmpty(StackS)判断栈空，若栈空返回1否则返回0。voidPush(Stack*S,BiTreep)压栈，将p压入栈顶。voidPop(Stack*S,BiTree*p)出栈，将栈顶元素出栈并付给p。BiTreeCreateBiTree(BiTree&T)创建二叉树T。voidPreOrderTraverse(BiTreeT)先序遍历二叉树并输出到屏幕。voidInOrderTraverse(BiTreeT)中序遍历二叉树并输出到屏幕。voidPostOrderTraverse(BiTreeT)后序遍历二叉树并输出到屏幕。voidmain()主函数，调用其他函数。六、源程序#defineL1#defineR0#definem100#include"stdio.h"#include"malloc.h"#definenull0typedefcharTElemType;typedefintStatus;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;typedefBiTreedatatype;typedefstruct{datatypes[m];inttop;}sqstack;typedefchartagtype;typedefstruct{datatypeptr;tagtypetag;}stacknode;typedefstruct{stacknodea[m];inttop;}sqstack2;StatusCreateBiTree(BiTree*T){charch;ch=getchar();if(ch=='#')(*T)=null;else{(*T)=(BiTree)malloc(sizeof(BiTNode));(*T)->data=ch;CreateBiTree(&(*T)->lchild);CreateBiTree(&(*T)->rchild);}return1;}voidStackInit1(sqstack*stack){inti;for(i=1;i<m;i++)(*stack).s[m]=null;(*stack).top=0;}StatusStackEmpty(sqstackstack){if(stack.top==0)return1;elsereturn0;}voidVisit(TElemTypee){printf("%c",e);}voidPush1(sqstack*stack,datatypex){if((*stack).top==m-1)printf("TheStackisoverflow!");else{(*stack).top=(*stack).top+1;(*stack).s[(*stack).top]=x;}}datatypePop1(sqstack*stack){datatypey;if((*stack).top==0)printf("TheStackisoverflow!");else{y=(*stack).s[(*stack).top];(*stack).top=(*stack).top-1;returny;}}voidPreOrderBiTree(datatypet){datatypep=t;sqstacks;StackInit1(&s);while(p!=null||!StackEmpty(s)){while(p!=null){Visit(p->data);Push1(&s,p);p=p->lchild;}if(!StackEmpty(s)){p=Pop1(&s);p=p->rchild;}/*endif*/}}voidInOrderBiTree(datatypet){datatypep=t;sqstacks;StackInit1(&s);while(p!=null||!StackEmpty(s)){while(p!=null){Push1(&s,p);p=p->lchild;}if(!StackEmpty(s)){p=Pop1(&s);Visit(p->data);p=p->rchild;}}}voidStackInit2(sqstack2*stack){(*stack).top=0;}StatusStackEmpty2(sqstack2stack){if(stack.top==0)return1;elsereturn0;}voidPush2(sqstack2*stack,stacknodex){if((*stack).top==m-1)printf("TheStackisoverflow!");else{(*stack).top=(*stack).top+1;(*stack).a[(*stack).top]=x;}}stacknodePop2(sqstack2*stack){stacknodey;if((*stack).top==0)printf("TheStackisoverflow!");else{y=(*stack).a[(*stack).top];(*stack).top=(*stack).top-1;returny;}}voidPostOrderBiTree(datatypet){datatypep=t;sqstack2s;stacknodex;StackInit2(&s);do{while(p!=null){x.ptr=p;x.tag=L;Push2(&s,x);p=p->lchild;}while(!StackEmpty2(s)&&s.a[s.top].tag==R){x=Pop2(&s);p=x.ptr;Visit(p->data);}if(!StackEmpty2(s)){s.a[s.top].tag=R;p=s.a[s.top].ptr->rchild;}}while(!StackEmpty2(s));}main(){BiTreeT=null;printf("\nCreateaBinaryTreeinPreOrder\n");CreateBiTree(&T);printf("ThePreOrderoftheBinaryTreeis:");PreOrderBiTree(T);printf("\n");printf("\nTheInOrderoftheBinaryTreeis:");InOrderBiTree(T);printf("\n");printf("\nThePostOrdeoftheBinaryTreeis:");PostOrderBiTree(T);}七、测试数据建立如右图所示的二叉树，以字符串的形式“根左子树右子树”先序定义一棵二叉树。输入数据次序为：ABD#H##E##C#FG###(#号代表空格）八、测试情况输出结果：题目二一、问题描述对任意给定的树（顶点数自定）建立它的二叉链表存储结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现树的先根，后根两种遍历，输出两种遍历的结果。二、基本要求1将给定的树转换成二叉树。2对给定节点，建立二叉链表存储结构；3利用栈的上述五种基本运算实现先根、后根两种遍历。4输出两种遍历结果。三、算法思想以字符串的形式“根子树”将一棵树创建为一棵二叉树。利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现树的先根、后根两种遍历，输出两种遍历结果（树的先根、后根遍历分别于其所建立的二叉树的先序、中序遍历结果一致）。四、数据结构（1）树要创建的二叉树定义如下：typedefstructtnode{chardata;structtnode*lchild,*rbrother;//左孩子、右兄弟}tnode,*Tree;（2）栈定义如下：typedefstruct{Tree*top;Tree*base;intStackSize;}Stack;//定义栈五、模块划分voidInitStack(Stack*S)初始化栈。intStackEmpty(StackS)判断栈空，若栈空返回1否则返回0。voidPush(Stack*S,Treep)压栈，将p压入栈顶。voidPop(Stack*S,Tree*p)出栈，将栈顶元素出栈并付给p。intCreateTree(Tree&T)创建二叉树T。voidPreOrderTraverse(TreeT)先序遍历二叉树并输出到屏幕。voidInOrderTraverse(TreeT)中序遍历二叉树并输出到屏幕。voidmain()主函数，调用其他函数。六、源程序#include<stdio.h>#include<stdlib.h>#defineOVERFLOW-2#defineINITSTACKSIZE100typedefstructCSNode{//树的二叉链表存储类型定义intdata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;typedefstruct{//栈的顺序存储表示CSTree*top;CSTree*base;intStackSize;}Stack;voidInitStack(Stack*S){(*S).base=(CSTree*)malloc(sizeof(CSNode));if(!(*S).base)exit(OVERFLOW); (*S).top=(*S).base;(*S).StackSize=INITSTACKSIZE;}//构造一个空栈intStackEmpty(StackS){if(S.top==S.base)return1;return0;}//判空栈voidPush(Stack*S,CSTreep){if((*S).top-(*S).base==(*S).StackSize)exit(OVERFLOW);*(*S).top++=p;}//进栈voidPop(Stack*S,CSTree*p){if((*S).top==(*S).base)exit(OVERFLOW);*p=*--(*S).top;}//出栈CSTreeCreateCSTree(){charch;CSTreeT;scanf("%c",&ch);if(ch=='')T=NULL;else{if(!(T=(CSTree)malloc(sizeof(CSNode))))exit(OVERFLOW);T->data=ch;T->firstchild=CreateCSTree();T->nextsibling=CreateCSTree();}returnT;}//建树voidPreorder(CSTreeT){//先序遍历之非递归算法CSTreep;StackS;InitStack(&S);p=T;while(p||!StackEmpty(S)){ if(p){ printf("%c",p->data);//访问结点 Push(&S,p); p=p->firstchild; } else{ Pop(&S,&p); p=p->nextsibling; }}}//实现先根遍历voidPostTorder(CSTreeT){CSTreep;StackS;InitStack(&S);p=T;while(p||!StackEmpty(S)){if(p){Push(&S,p);p=p->firstchild;}else{Pop(&S,&p);printf("%c",p->data);p=p->nextsibling; }}}//实现树的后根遍历voidmain(){CSTreeT;printf("构造一棵树\n");T=CreateCSTree();printf("\n树的先根遍历为\n");Preorder(T);printf("\n树的后根遍历为\n");PostTorder(T);printf("\n");}七、测试数据树转的二叉树建立如上图所示的树，以字符串的形式“根子树”将一棵树先序创建为一棵二叉树。输入数据次序为：ABE##CF##DG#H####(#为空格)。八、测试情况输出结果：重言式的判别一.需求分析

1.逻辑表达式从终端输入，长度不超过一行，逻辑运算符包括"|","&"和"~",分别表示或，与和非，运算符的优先程度递增，但可有括号改变，即括号内的运算优先。逻辑变元为大写字母。表达式中的任何地方都可以含有多个空格符。2.若是重言式或矛盾式，可以只显示"Trueforever"或"Falseforever",否则显示"Satisfactible"以及变量名序列，与用户交互。若用户对表达式中变元取定一组值，程序就求出表达式的值。3.程序要求必须输入语法正确的表达式，程序没有语法检查功能。4.本程序在vs2008下编译通过。二.概要设计

1.设定栈的抽象数据类型定义：ADTStack{数据对象：D={ai|ai∈IntSet，i=1，2，……，n，n≥0}数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2，……，n}基本操作：InitStack(&S)操作结果：构造一个空栈S。Push(&S,e);初始条件：栈S已存在。操作结果：在栈S的栈顶插入新的栈顶元素e。Pop(&S);初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并以e返回其值。DestroyStack(&s)初始条件：栈S已存在。操作结果：释放栈S占有的内存空间，将栈销毁。}ADTStack本程序允许表达式中有空格，在利用算符优先法建立二叉树的存储结构之前应将表达式中的空格删除，利用递归算法借助二叉树求出表达式的值，程序中设立软计数器，产生变量的值的组合。详细设计1.栈类型typedefstruct{ BiTree*base; BiTree*top; intstacksize;}Stack;/*栈的实现*/intInitStack(Stack&s){ s.base=(BiTree*)malloc(STACKINITSIZE*sizeof(BiTree)); if(!s.base) { exit(-2); } s.top=s.base; s.stacksize=STACKINITSIZE; return1;}BiTreeGetTop(Stacks){ if(s.top==s.base) { returnNULL; } return*(s.top-1);}intPush(Stack&s,BiTreee){ if(s.top-s.base>=s.stacksize) { s.base=(BiTree*)realloc(s.base, (s.stacksize+STACKINCREMENT)*sizeof(BiTree)); if(!s.base) { exit(-2); } s.top=s.base+s.stacksize; s.stacksize+=STACKINCREMENT; } *(s.top)=e; s.top++; return1;}BiTreePop(Stack&s){ if(s.top==s.base) { returnNULL; } return*(--s.top);}voidDestroyStack(Stack&s){ free(s.base);}/*栈的实现结束*/二叉树的结点类型定义typedefstructBiTNode{ chardata;structBiTNode*lchild; structBiTNode*rchild;}BiTNode,*BiTree;/*利用栈建立二叉树的存储结构*/voidCreatBiTree(){ BiTreetemp,a,b; char*p=str; temp=(BiTree)malloc(sizeof(BiTNode)); temp->data='#'; Push(optrstack,temp);/*虚拟栈底压栈*/ while((*p!='#')||(GetTop(optrstack)->data!='#')) { if((*p>=65)&&(*p<=90))/*当前是操作数*/ { temp=(BiTree)malloc(sizeof(BiTNode)); temp->data=*p; temp->lchild=NULL; temp->rchild=NULL; Push(opndstack,temp); p++; } else {/*当前是运算符*/ switch(cmp(GetTop(optrstack)->data,*p)) { case'<':/*栈顶的运算符的优先级小，当前运算符压栈*/ temp=(BiTree)malloc(sizeof(BiTNode)); temp->data=*p; temp->lchild=NULL; temp->rchild=NULL; Push(optrstack,temp); p++; break; case'=':/*运算符的优先级相等，脱括号*/ temp=Pop(optrstack); free(temp);/*释放括号结点的空间*/ p++; break; case'>':/*栈顶的运算符的优先级高，出栈建立子二叉树，压入操作数栈*/ temp=Pop(optrstack); b=Pop(opndstack); temp->rchild=b; if(temp->data!='~')/*出栈的运算符有两个操作数*/ { a=Pop(opndstack); temp->lchild=a; } Push(opndstack,temp); break; }/*switch*/ }/*else*/ }/*while*/ root=Pop(opndstack);/*若为空表达式,则返回NULL*/ temp=Pop(optrstack);/*去除运算符栈的伪栈底，并将其所占内存单元释放*/free(temp);}/*利用二叉树的存储结构求表达式值的递归算法*/intGetValue(BiTree&tree){ if(!tree) { return0; } elseif((tree->data>=65)&&(tree->data<=90)) { returnvaritab[tree->data-64]; } else { switch(tree->data) { case'|': return(GetValue(tree->lchild)||GetValue(tree->rchild)); case'&': return(GetValue(tree->lchild)&&GetValue(tree->rchild)); case'~': return(!GetValue(tree->rchild)); } }}/*二叉树的销毁算法*/voidDestroyBiTree(BiTree&tree){ if(!tree) { return; } elseif((tree->lchild==NULL)&&(tree->rchild==NULL)) { free(tree); return; } else { DestroyBiTree(tree->lchild);DestroyBiTree(tree->rchild); free(tree); }}软计数器的定义intvaritab[VARIMAXNUM+1];/*varitab[0]存放变量的个数*//*求变量的组合值的算法*/voidCreatVaritab(unsignedn){ inti; for(i=0;i<*varitab;i++) { varitab[*varitab-i]=(n>>i)%2; }}运算符的优先级表charoptrtable[6][7]={'','|','&','~','(',')','#','|','>','<','<','<','>','>','&','>','>','<','<','>','>','~','>','>','>','<','>','>','(','<','<','<','<','=','','#','<','<','<','<','','='};/*此优先级表没有')'对应的行，因为没有必要，')'永远不会入栈*//*两个运算符的优先级的比较算法*/charcmp(chara,charb){ inti,j; for(i=1;i<6;i++) { if(optrtable[i][0]==a) break; } for(j=1;j<7;j++) { if(optrtable[0][j]==b) break; } returnoptrtable[i][j];}函数的调用关系反映了程序的层次结构:mainmainPushPopGetTopCreatVaritabGetValueDestroyBiTreeDestroyStackInputCreatBiTreeOExpValTabUsrMutualInitStackInitInterpretDestroyReadCommandPushPopGetTopCreatVaritabGetValueDestroyBiTreeDestroyStackInputCreatBiTreeOExpValTabUsrMutualInitStackInitInterpretDestroyReadCommand 调试分析开始由于失误，将运算符的优先级表弄错，导致程序运行错误。伪栈底开始由于失误，虽然出栈，但忘记释放所占内存空间。用户手册本程序的可执行文件为main.exe进入程序后，即显示文本方式的用户界面:输入1命令，用户可以输入要计算的表达式，在表达式的任何地方允许出现任意多个空格，如果程序开始不输入表达式，直接输入2或3命令，则默认为空表达式。输入2命令，程序可以与用户交互，如果是永真式，则程序显示永真式，如果是矛盾式，则程序显示矛盾式，否则用户可以输入变量的一组值，程序可以输出对应的表达式的值。输入3命令，程序可以输出表达式的真值表。测试结果*************1.输入表达式2.与用户交互3.输出真值表4.退出本程序*************请输入命令:1输入变量个数:2输入表达式:(A|~A)&(B|~B)*************1.输入表达式2.与用户交互3.输出真值表4.退出本程序*************请输入命令:2永真式!*************1.输入表达式2.与用户交互3.输出真值表4.退出本程序*************请输入命令:3真值表是:AB00真01真10真11真*************1.输入表达式2.与用户交互3.输出真值表4.退出本程序*************请输入命令:1输入变量个数:2输入表达式:(A&~A)&B*************1.输入表达式2.与用户交互3.输出真值表4.退出本程序*************请输入命令:2矛盾式!*************1.输入表达式2.与用户交互3.输出真值表4.退出本程序*************请输入命令:3真值表是:AB00假01假10假11假*************1.输入表达式2.与用户交互3.输出真值表4.退出本程序*************请输入命令:1输入变量个数:2输入表达式:(A|B)&(A|~B)*************1.输入表达式2.与用户交互3.输出真值表4.退出本程序*************请输入命令:2输入变量值:A=1B=1表达式值为真!1.继续交互2.退出交互输入命令:1输入变量值:A=1B=0表达式值为真!1.继续交互2.退出交互输入命令:1输入变量值:A=0B=0表达式值为假!1.继续交互2.退出交互输入命令:2*************1.输入表达式2.与用户交互3.输出真值表4.退出本程序*************请输入命令:3真值表是:AB00假01假10真11真*************1.输入表达式2.与用户交互3.输出真值表4.退出本程序*************请输入命令:4谢谢使用!请按任意键继续...附录本程序为单文