《(完整word版)樹和二叉樹——數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《(完整word版)樹和二叉樹——數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告.doc（22頁珍藏版）》請?jiān)趨R文網(wǎng)上搜索。

1、實(shí)習(xí)報(bào)告題目：編寫一個(gè)實(shí)現(xiàn)基于二叉樹表示的算術(shù)表達(dá)式Expression操作程序班級(jí)： 姓名： 學(xué)號(hào)： 完成日期/一、 需求分析算術(shù)表達(dá)式Expression內(nèi)可以含有變量（az）、常量（09）和二元算術(shù)符（+,-,*,/,（乘冪）。實(shí)現(xiàn)以下操作： （1）ReadExpr(E)以字符序列的形式輸入語法正確的前綴表達(dá)式并構(gòu)造表達(dá)式E。 （2）WriteExpr(E)用帶括號(hào)的中綴表達(dá)式輸出表達(dá)式E。 （3）Assign(V，c)實(shí)現(xiàn)對變量V的賦值（V=c），變量的初值為0。 （4）Value(E)對算術(shù)表達(dá)式E求值。 （5）CompoundExpr(p,E1,E2)構(gòu)造一個(gè)新的復(fù)合表達(dá)式（E1）

2、p（E2）。二、 概要設(shè)計(jì)1、數(shù)據(jù)類型的聲明：在這個(gè)課程設(shè)計(jì)中，采用了鏈表二叉樹的存儲(chǔ)結(jié)構(gòu)，以及兩個(gè)順序棧的輔助存儲(chǔ)結(jié)構(gòu)/*頭文件以及存儲(chǔ)結(jié)構(gòu)*/#include#include#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW 0typedef int Status;2、表達(dá)式的抽象數(shù)據(jù)類型定義ADT Expression數(shù)據(jù)對象D：D是具有數(shù)值的常量C和沒有數(shù)值的變量V；數(shù)據(jù)關(guān)系：R=|V,CD, 表示由運(yùn)算符P結(jié)合起來的表達(dá)式E基本操作：Status Input_

3、Expr(&string,flag)操作結(jié)果：以字符序列的形式輸入語法正確的前綴表達(dá)式，保存到字符串string； 參數(shù)flag表示輸出的提示信息是什么，輸入成功返回OK，否則，返回ERROR。void judge_value(&E,&string,i)初始條件：樹E存在，表達(dá)式的前綴字符串string存在；操作結(jié)果：判斷字符stringi，如果是0-9常量之間，二叉樹結(jié)點(diǎn)E存為整型；否則，存為字符型。Status ReadExpr(&E,&exprstring)初始條件：表達(dá)式的前綴形式字符串exprstring存在；操作結(jié)果：以正確的前綴表示式exprstring并構(gòu)造表達(dá)式E，構(gòu)造成功，

4、返回OK，否則返回ERROR。Status Pri_Compare(c1,c2)初始條件：c1和c2是字符；操作結(jié)果：如果兩個(gè)字符是運(yùn)算符，比較兩個(gè)運(yùn)算符的優(yōu)先級(jí)，c1比c2優(yōu)先，返回OK，否則返回ERROR。void WriteExpr(&E)初始條件：表達(dá)式E存在；操作條件：用帶括弧的中綴表達(dá)式輸入表達(dá)式E。void Assign(&E,V,c,&flag)初始條件：表達(dá)式E存在，flag為標(biāo)志是否有賦值過；操作結(jié)果：實(shí)現(xiàn)對表達(dá)式E中的所有變量V的賦值(V=c)。long Operate(opr1,opr,opr2)初始條件：操作數(shù)opr1和操作數(shù)opr2以及操作運(yùn)算符opr;操作結(jié)果：運(yùn)

5、算符運(yùn)算求值，參數(shù)opr1,opr2為常量，opr為運(yùn)算符，根據(jù)不同的運(yùn)算符，實(shí)現(xiàn)不同的運(yùn)算，返回運(yùn)算結(jié)果。Status Check(E)初始條件：表達(dá)式E存在；操作結(jié)果：檢查表達(dá)式E是否還存在沒有賦值的變量，以便求算數(shù)表達(dá)式E的值。long Value(E)初始條件：表達(dá)式E存在；操作結(jié)果：對算術(shù)表達(dá)式求值，返回求到的結(jié)果。void CompoundExpr(P,&E1,E2)初始條件：表達(dá)式E1和E2存在；操作條件：構(gòu)造一個(gè)新的復(fù)合表達(dá)式(E1)P(E2)。Status Read_Inorder_Expr(&string,&pre_expr)操作結(jié)果：以表達(dá)式的原書寫形式輸入，表達(dá)式的原書

6、寫形式字符串string變?yōu)樽址畃re_expr，后調(diào)用reversal_string()函數(shù)反轉(zhuǎn)得到前綴表達(dá)式pre_expr。得到正確的前綴表達(dá)式返回OK，否則，返回ERROR。void MergeConst(&E)操作結(jié)果：常數(shù)合并操作，合并表達(dá)式E中所有常數(shù)運(yùn)算。ADT Expression3、整體設(shè)計(jì)1、順序棧的基本操作：對于棧SqStack:Status InitStack(SqStack *S)/* 構(gòu)造一個(gè)空棧S */Status StackEmpty(SqStack S)/* 若棧S為空棧，則返回TRUE，否則返回FALSE */Status Push(SqStack *S

7、,SElemType e)/* 插入元素e為新的棧頂元素 */Status Pop(SqStack *S,SElemType *e) /* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */Status GetTop(SqStack S,SElemType *e) /* 若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR */對于棧SqStack1:Status InitStack1(SqStack1 *S)/* 構(gòu)造一個(gè)空棧S */Status StackEmpty1(SqStack1 S)/* 若棧S為空棧，則返回TRUE，否則返回FALSE *

8、/Status Push1(SqStack1 *S,SElemType1 e)/* 插入元素e為新的棧頂元素 */Status Pop1(SqStack1 *S,SElemType1 *e)/* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */Status GetTop1(SqStack1 S,SElemType1 *e) /* 若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR */2、主程序模塊的整體流程在主函數(shù)中，采用多分支程序設(shè)計(jì)語句switch()使程序產(chǎn)生不同的流向，從而達(dá)到實(shí)現(xiàn)課程設(shè)計(jì)的各個(gè)要求。void main() printf(

9、n 1 輸入正確的前綴表達(dá)式);printf(n 2 帶括弧的中綴表示式輸出);printf(n 3 對變量進(jìn)行賦值);printf(n 4 對算數(shù)表達(dá)式求值);printf(n 5 構(gòu)造一個(gè)新的復(fù)合表達(dá)式);printf(n 0 退出);while(1)switch( )根據(jù)不同的選擇，調(diào)用不同的操作函數(shù)，完成各個(gè)操作；2、本程序有四個(gè)模塊，主程序模塊，二叉樹模塊，兩個(gè)順序棧模塊。四者的調(diào)用關(guān)系如下：主程序模塊中的對于表達(dá)式的存儲(chǔ)結(jié)構(gòu)調(diào)用了二叉樹模塊，而在構(gòu)造表達(dá)式的二叉樹模塊中又調(diào)用了順序棧SqStack模塊，主程序中在將原表達(dá)式形式輸入表達(dá)式轉(zhuǎn)換為前綴表達(dá)式操作中調(diào)用了順序棧SqStac

10、k1模塊。主程序模塊二叉樹模塊順序棧SqStack模塊順序棧SqStack1模塊三、 詳細(xì)設(shè)計(jì)1、二叉樹的存儲(chǔ)類型/*二叉樹結(jié)點(diǎn)類型*/typedef enumINT,CHARElemTag;/*INT為整型數(shù)據(jù)num，CHAR為字符型數(shù)據(jù)c*/typedef struct TElemTypeElemTag tag;/*INT,CHAR指示是整型還是字符型*/unionint num;/*tag=INT時(shí)，為整型*/char c;/*tag=CHAR時(shí)，為字符型*/; TElemType;/*二叉樹的二叉鏈表存儲(chǔ)表示 */typedef struct BiTNode TElemType dat

11、a; struct BiTNode *lchild,*rchild; /* 左右孩子指針 */ BiTNode,*BiTree;二叉樹的基本操作已經(jīng)在構(gòu)造表達(dá)式和表達(dá)式中的基本操作中根據(jù)不同的功能和實(shí)際情況修改了，詳細(xì)見各個(gè)函數(shù)操作的算法設(shè)計(jì)。2、順序棧的存儲(chǔ)類型/*棧的順序存儲(chǔ)表示 */#define STACK_INIT_SIZE 10 /* 存儲(chǔ)空間初始分配量 */#define STACKINCREMENT 2 /* 存儲(chǔ)空間分配增量 */*兩個(gè)順序棧*/typedef struct SqStack SElemType *base; /* 在棧構(gòu)造之前和銷毀之后，base的值為NULL

12、 */ SElemType *top; /* 棧頂指針 */ int stacksize; /* 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位 */ SqStack; /* 順序棧SqStack */typedef struct SqStack1 SElemType1 *base; /* 在棧構(gòu)造之前和銷毀之后，base的值為NULL */ SElemType1 *top; /* 棧頂指針 */ int stacksize; /* 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位 */ SqStack1; /* 順序棧SqStack1 */相關(guān)的基本操作見上面的“expression.h文件的整體結(jié)構(gòu)”的說明，詳細(xì)的

13、算法設(shè)計(jì)見附錄的程序清單。3、表達(dá)式的基本操作Status Input_Expr(char *string,int flag);/*以字符序列的形式輸入語法正確的前綴表達(dá)式，保存到字符串string*/*參數(shù)flag=0表示輸出的提示信息是請輸入正確的前綴表示式：*/*flag=1表示輸出的提示信息為請以表達(dá)式的原書寫形式輸入正確表示式：*/void judge_value(BiTree *E,char *string,int i);/*判斷字符stringi，如果是0-9常量之間，二叉樹結(jié)點(diǎn)存為整型；否則，存為字符型*/Status ReadExpr(BiTree *E,char *expr

14、string);/*以正確的前綴表示式并構(gòu)造表達(dá)式E*/Status Pri_Compare(char c1,char c2);/*如果兩個(gè)字符是運(yùn)算符，比較兩個(gè)運(yùn)算符的優(yōu)先級(jí)，c1比c2優(yōu)先，返回OK，否則返回ERROR*/void WriteExpr(BiTree E);/*用帶括弧的中綴表達(dá)式輸入表達(dá)式*/void Assign(BiTree *E,char V,int c,int *flag);/*實(shí)現(xiàn)對表達(dá)式中的所有變量V的賦值(V=c)，參數(shù)flag為表示是否賦值過的標(biāo)志*/long Operate(int opr1,char opr,int opr2);/*運(yùn)算符運(yùn)算求值，參數(shù)opr1,opr2為常量，opr為運(yùn)算符，根據(jù)不同的運(yùn)算符，實(shí)現(xiàn)不同的運(yùn)算，返回運(yùn)算結(jié)果*/Status Check(BiTree E);/*檢查表達(dá)式是否還存在沒有賦值的變量，以便求算數(shù)表達(dá)式的值*/long Value(BiTree E);/*對算術(shù)表達(dá)式求值*/void CompoundExpr(char P,BiTree *E1,BiTree E2