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謝謝使用!請按任意鍵繼續...附錄本程序為單文