數據結構實驗報告 圖

問題描述：;四則運算表達式求值，將四則運算表達式用中綴表達式;一、需求分析：;1、本程序是利用二叉樹后序遍歷來實現表達式的轉換;2、輸入輸出格式：;輸入格式：在字符界面上輸入一個中綴表達式，回車表;請輸入表達式：;輸入一個中綴表達式;輸出格式：如果該中綴表達式正確，那么在字符界面上;式，其中后綴表達式中兩相鄰操作數之間利用空格隔開;果不正確，在字符界面上輸出

問題描述：

四則運算表達式求值，將四則運算表達式用中綴表達式，然后轉換為后綴表達式，并計算結果。

一、 需求分析：

1、本程序是利用二叉樹后序遍歷來實現表達式的轉換，同時可以使用實驗三的結果來求解后綴表達式的值。

2、輸入輸出格式：

輸入格式：在字符界面上輸入一個中綴表達式，回車表示結束。

請輸入表達式：

輸入一個中綴表達式

輸出格式：如果該中綴表達式正確，那么在字符界面上輸出其后綴表達

式，其中后綴表達式中兩相鄰操作數之間利用空格隔開;如

果不正確，在字符界面上輸出表達式錯誤提示。

逆波蘭表達式為：

3、測試用例

輸入：21+23*(12-6)

輸出：21 23 12 6 -*+ 輸出逆波蘭表達式 運算結果為：輸出運算后的結果

二、概要設計 ：

抽象數據類型

二叉樹類BiTree

算法的基本思想

根據題目要求，利用棧計算，和二叉樹存儲，來計算表達式

該算法的基本思想是：

先利用棧進行計算，然后用二叉樹進行存儲，和實驗三算法一樣來計算逆波蘭表達式的值

程序的流程

程序由三個模塊組成：

(1) 輸入模塊：輸入一個運算式

(2) 計算模塊：利用棧進行表達式的計算，二叉樹來存儲。 (3 ) 輸出模塊：屏幕上顯示出后綴表達式和運算結果。

三、詳細設計

物理數據類型

程序含有兩個類，其中棧不再贅述，另一個類為二叉樹class BiTree包含私有成員struct BiTreeNode，根節(jié)點BiTreeNode *T;索引index; int number_of_point 優(yōu)先級比較函數 compare(char a,char b);生成樹的函數void InorderCreate(BiTreeNode *&T,char str[30][10],int start,int end);判斷數字函數bool IsNumber(char a);求值函數double Operate(BiTreeNode *T);還有顯示后綴表達式的函數void display(BiTreeNode *T) ;而公有成員函數則是對私有函數的重載，為方便使用，因為函數中普遍使用了遞歸的算法。

算法的時空分析

此算法利用棧和二叉樹來實現，故次算法的的時間復雜度為(N)。

輸入和輸出的格式

輸入格式：請輸入表達式：

輸入一個中綴表達式 //回車

輸出格式：逆波蘭表達式為：

輸出逆波蘭表達式

運算結果為：輸出運算后的結果

四、調試分析

略。

五、測試結果

本實驗的測試結果截圖如下：

六、用戶使用說明(可選)

1、本程序的運行環(huán)境為windows 操作系統(tǒng)，執(zhí)行文件為 biaodashi.exe 2 、運行程序時

提示輸入表達式

本程序可以將中綴表達式轉換為后綴表達式后在計算出運算式的結果。 提示：請輸入表達式：

輸出

提示：逆波蘭表達式為：

運算結果：

七、實驗心得(可選)

本次實驗過程比較復雜，由于書上的知識掌握的還不是很牢靠，所以現在實驗做起來有點兒吃力。本實驗主要是通過與同學的討論和課后查閱資料來完成的，雖然有些地方還不是很懂，但基本上能完成此次實驗的內容。而且通過本次實驗，加深了對二叉樹算法的了解。

附錄(實驗代碼)：

#include

#include

#include

#include

#include

#include

#define STACK_INIT_SIZE 100

#define DATA_SIZE 10

#define STACKINCREMENT 10

#define OK 1

#define TRUE 1

#define FALSE 0

#define ERROR 0

#define OVERFLOW -2

using namespace std;

typedef float SElemtype;

typedef int Status;

typedef char * TElemType;

typedef struct BiTNode {

TElemType data;

int len; //data字符串中字符的個數

struct BiTNode * lchild, * rchild;

}BiTNode, *BiTree;

typedef struct

{

SElemtype *base;

SElemtype *top;

int stacksize;

} SqStack;

Status IsDigital(char ch)

{ if(ch>='0'&&ch<='9')

{return 1; //是數字字母

}

return 0; //不是數字字母

}

int CrtNode(stack &PTR, char *c)

{

BiTNode * T;

int i=0;

T = (BiTNode *)malloc(sizeof(BiTNode));

T->data = (char *)malloc(DATA_SIZE*sizeof(char));

while(IsDigital(c[i]))

{T->data [i] = c[i];

i++; }

T->len = i;

T->lchild = T->rchild = NULL;

PTR.push (T);

return i;

}

void CrtSubTree(stack &PTR, char c)

{BiTNode * T;

T = (BiTNode *)malloc(sizeof(BiTNode));

T->data = (char *)malloc(DATA_SIZE*sizeof(char));

T->data [0] = c;

T->len = 1;

T->rchild = PTR.top(); //先右子樹，否則運算次序反了

PTR.pop ();

T->lchild = PTR.top();

PTR.pop ();

PTR.push (T);

}

char symbol[5][5]={{'>', '>', '<', '<', '>'}, //符號優(yōu)先級

{'>', '>', '<', '<', '>'},

{'>', '>', '>', '>', '>'},

{'>', '>', '>', '>', '>'},

{'<', '<', '<', '<', '='}};

int sym2num(char s) //返回符號對應優(yōu)先級矩陣位置 { switch(s)

{

case '+': return 0; break;

case '-': return 1; break;

case '*': return 2; break;

case '/': return 3; break;

case '#': return 4; break;

}

}

char Precede(char a, char b) //返回符號優(yōu)先級

{return(symbol[sym2num(a)][sym2num(b)]);}

void CrtExptree(BiTree &T, char exp[])

{ //根據字符串exp的內容構建表達式樹T

stack PTR;//存放表達式樹中的節(jié)點指針

stack OPTR;//存放操作符

char op;

int i=0;

OPTR.push ('#');

op = OPTR.top();

while( !((exp[i]=='#') && (OPTR.top()=='#')) ) //與

{

if (IsDigital(exp[i]))

{//建立葉子節(jié)點并入棧 PTR

i+=CrtNode(PTR, &exp[i]);

}

else if (exp[i] == ' ')

i++;

else{

switch (exp[i])

{

case '(': {

OPTR.push (exp[i]);

i++;

break;}

case ')': {

op = OPTR.top (); OPTR.pop ();

while(op!='('){

CrtSubTree(PTR, op);

op = OPTR.top (); OPTR.pop ();

}//end while

【數據結構實驗報告 圖】相關文章：

科技實驗報告05-26

化學實驗報告07-03

實驗報告總結02-14

生物實驗報告08-13

關于實驗報告01-27

化學實驗報告01-28

電路實驗報告11-09

實驗報告范文09-05

【熱門】實驗報告格式07-02

實驗報告的書寫格式04-01