數(shù)據(jù)結(jié)構(gòu)-實驗7-標識符樹與表達式求值

1、精選優(yōu)質(zhì)文檔-傾情為你奉上1、 實驗目的（1）掌握二叉樹的數(shù)組存儲方法。（2）掌握二叉樹的非線性特點、遞歸特點和動態(tài)特性。（3）復習二叉樹遍歷算法和標識符樹的概念。（4）利用標識符樹的后序計算表達式的值（運算只涉及+、-、*、/）。2、 實驗內(nèi)容（1）定義二叉樹的結(jié)構(gòu)如下：struct tree / 定義結(jié)構(gòu)體 int data; / 定義一個整型數(shù)據(jù)域 struct tree *left; / 定義左子樹指針 struct tree *right; / 定義右子樹指針;typedef struct tree btnode; / 樹的結(jié)構(gòu)類型+*/2363 標識符樹typedef btnode

2、 *bt; / 定義樹結(jié)點的指針類型（2）把算術(shù)表達式2*3+6/3的標識符樹（見圖7-35）存入一維數(shù)組。（3）求標識符樹的前序遍歷、中序遍歷和后序遍歷的序列。（4）以后序計算標識符樹的值。3、 實驗要求（1) 用C（C+）語言完成算法設計和程序設計。（2) 上機調(diào)試通過實驗程序。（3) 輸入數(shù)據(jù)，檢驗程序運行結(jié)果。（4) 給出具體的算法分析，包括時間復雜度和空間復雜度等。（5) 撰寫實驗報告（把輸入實驗數(shù)據(jù)及運行結(jié)果用抓圖的形式粘貼到實驗報告上）。4、 實驗步驟與源程序 實驗步驟先從具體的問題中抽象出適當?shù)臄?shù)學模型，然后設計出相應的算法，其中，需要設計一個主函數(shù)來實現(xiàn)菜單的輸出，設計另外五

3、個函數(shù)來求分別實現(xiàn)新建，先序遍歷輸出，中序遍歷輸出，后序遍歷輸出，表達式求值，最后，串接函數(shù)，并調(diào)試程序，多次調(diào)試后，發(fā)現(xiàn)沒有問題，得出實驗結(jié)果，并截圖。 源代碼#include<stdlib.h>#include<stdio.h>struct tree / 樹的結(jié)構(gòu)聲明char data; / 結(jié)點數(shù)據(jù) struct tree *left; / 指向左子樹的指針 struct tree *right; / 指向右子樹的指針;typedef struct tree treenode; / 樹的結(jié)構(gòu)新類型typedef treenode *btree; / 聲明樹結(jié)點指針

4、類型int n; / n計算字符串長度btree createbtree(int *data,int pos) / 創(chuàng)建表達式二叉樹 btree newnode; / 新結(jié)點指針 if (datapos=0|pos>n) / 終止條件 return NULL; else newnode=new treenode; / 創(chuàng)建新結(jié)點內(nèi)存 newnode->data=datapos; / 創(chuàng)建結(jié)點內(nèi)容 newnode->left=createbtree(data,2*pos); / 創(chuàng)建左子樹遞歸調(diào)用 newnode->right=createbtree(data,2*pos

5、+1); / 創(chuàng)建右子樹遞歸調(diào)用return newnode;void preorder(btree ptr) / 表達式二叉樹前序輸出 if(ptr!=NULL) / 終止條件 printf(" %c",ptr->data); / 輸出結(jié)點內(nèi)容 preorder(ptr->left); / 左子樹 preorder(ptr->right); / 右子樹 void inorder(btree ptr) / 表達式二叉樹中序輸出 if (ptr!=NULL) / 終止條件 inorder(ptr->left); / 左子樹 printf("

6、%c",ptr->data); / 輸出結(jié)點內(nèi)容 inorder(ptr->right); / 右子樹 void postorder(btree ptr) / 表達式二叉樹后序輸出 if(ptr!=NULL) / 右子樹 postorder(ptr->left); / 左子樹 postorder(ptr->right); / 右子樹 printf(" %c",ptr->data); / 輸出結(jié)點內(nèi)容 int cal(btree ptr) / 表達式二叉樹后序計值 int operand1=0; / 定義操作數(shù)變量1 int opera

7、nd2=0; / 定義操作數(shù)變量2 int getvalue(int op,int operand1,int operand2); / 對getvalue函數(shù)作聲明 if (ptr->left=NULL && ptr->right=NULL) / 終止條件 return ptr->data-48; operand1=cal(ptr->left); / 左子樹 operand2=cal(ptr->right); / 右子樹 return getvalue(ptr->data,operand1,operand2); int getvalue(in

8、t op,int operand1,int operand2) / 計算二叉樹表達式值 switch(char)op) case'*':return(operand1*operand2); case'/':return(operand1/operand2); case'+':return(operand1+operand2); case'-':return(operand1-operand2); void main() / 主程序 btree root=NULL; / 表達式二叉樹指針 int result,k=1; / 定義輸出

9、結(jié)果變量 int data100=' ' char ch; printf("按層次輸入標識符樹的結(jié)點數(shù)據(jù)，以回車鍵表示結(jié)束n"); while(ch=getchar()!='n') datak+=ch; datak='0' n=k-1; root=createbtree(data,1); / 創(chuàng)建表達式二叉樹 printf("tn 前序表達式："); preorder(root); / 前序輸出二叉樹 printf("tnn 中序表達式："); inorder(root); / 中序輸出二叉樹 printf("tnn 后序表達式："); postorder(root); / 后序輸出二叉樹 result=cal(root); / 計算 printf("tnn 表達式結(jié)果是：%dnn",result); / 輸出計算結(jié)果5、 測試數(shù)據(jù)與實驗結(jié)果（可以抓圖粘貼）6、 結(jié)果分析與實驗體