《數(shù)據(jù)結構課程設計》表達式求值實驗報告-1

1/1《數(shù)據(jù)結構課程設計》表達式求值實驗報告試驗課程名稱

專業(yè)班級

同學姓名

學號

指導老師

20至20學年第學期第至周

算術表達式求值演示

一、概述

數(shù)據(jù)結構課程設計.要求同學在數(shù)據(jù)結構的規(guī)律特性和物理表示、數(shù)據(jù)結構的選擇和應用、算法的設計及其實現(xiàn)等方面.加深對課程基本內容的理解。同時.在程序設計方法以及上機操作等基本技能和科學作風方面受到比較系統(tǒng)和嚴格的訓練。

在這次的課程設計中我選擇的題目是算術表達式求值演示。表達式計算是實現(xiàn)程序設計語言的基本問題之一.也是棧的應用的一個典型例子。設計一個程序.演示用算符優(yōu)先法對算術表達式求值的過程。深化了解棧和隊列的特性.以便在解決實際問題中敏捷運用它們.同時加深對這種結構的理解和熟悉。

二、系統(tǒng)分析

1．以字符列的形式從終端輸入語法正確的、不含變量的整數(shù)表達式。利用已知的算符優(yōu)先關系.實現(xiàn)對算術四則混合運算表達式的求值.并仿照教科書的例子在求值中運算符棧、運算數(shù)棧、輸入字符和主要操作的變化過程。

2．一般來說.計算機解決一個詳細問題時.需要經(jīng)過幾個步驟：首先要從詳細問題抽象出一個適當?shù)臄?shù)學模型.然后設計一個解決此數(shù)學模型的算法.最終編出程序.進行測試.

調試直至得到想要的答案。對于算術表達式這個程序.主要利用棧.把運算的先后步驟進行分析并實現(xiàn)簡潔的運算！為實現(xiàn)算符優(yōu)先算法.可以使用兩個棧.一個用以寄存運算符.另一個用以寄存操作數(shù)和運算結果。

3．演示程序是以用戶于計算機的對話方式執(zhí)行.這需要一個模塊來完成使用者與計算機語言的轉化。

4．程序執(zhí)行時的命令：

本程序為了使用詳細.采納菜單式的方式來完成程序的演示.幾乎不用輸入什么特別的命令.只需按提示輸入表達式即可。（要留意輸入時格式.否者可能會引起一些錯誤）5.測試數(shù)據(jù)。

三、概要設計

一個算術表達式中除了括號、界限符外.還包括運算數(shù)據(jù)和運算符。由于運算符有優(yōu)先級別之差.所以一個表達式的運算不行能總是從左至右的循序執(zhí)行。每次操作的數(shù)據(jù)或運算符都是最近輸入的.這與棧的特性相吻合.故本課程設計借助棧來實現(xiàn)按運算符的優(yōu)先級完成表達式的求值計算。

算法設計

程序包含三個模塊

(1)主程序模塊.其中主函數(shù)為

voidmain{

輸入表達式；

依據(jù)要求進行轉換并求值；

輸出結果；

}

(2)表達式求值模塊——實現(xiàn)詳細求值。

(3)表達式轉換模塊——實現(xiàn)轉換。

各個函數(shù)之間的調用關系

棧的抽象數(shù)據(jù)類型定義ADTSqStack{

主函數(shù)

表達式轉換表達式求值

數(shù)據(jù)輸入

輸出輸出

數(shù)據(jù)對象：D={ai|ai∈ElemSet,i=1,2,3…….n,n≥0}

數(shù)據(jù)關系：R1={|ai-1,ai∈D,i=1,2,3,…….n}

商定其中ai端為棧底.an端為棧頂。

操作集合：

(1)voidInitStack1(SqStack1//聲明棧建立函數(shù)

(2)voidInitStack2(SqStack2//聲明棧建立函數(shù)

(3)voidevaluate(SqStack1//確定如何入棧函數(shù)

(4)voidPush1(SqStack1//聲明入棧函數(shù)

(5)voidPush2(SqStack2//聲明入壓棧函數(shù)

(6)charGetTop1(SqStack1//聲明取棧頂元素函數(shù)

(7)floatGetTop2(SqStack2//聲明取棧頂元素函數(shù)

(8)charPop1(SqStack1//聲明出棧函數(shù)

(9)floatPop2(SqStack2//聲明出棧函數(shù)

(10)charCompare(charm,charn);//聲明比較函數(shù)

(11)floatOperate(floata,charrheta,floatb);//聲明運算函數(shù)

(12)voidDispStack1(SqStack1//從棧底到棧頂依次輸出各元素

(13)voidDispStack2(SqStack2//從棧底到棧頂依次輸出各元素

}ADTSqStack

結構分析:

棧中的數(shù)據(jù)節(jié)點是通過數(shù)組來存儲的。由于在C語言中數(shù)組是用下標從零開頭的.因此我們在調用他們的數(shù)據(jù)是要特殊留意。指針變量的值要么為空(NULL).不指向任何結點；要么其值為非空.即它的值是一個結點的存儲地址。留意.當P為空值時.則它不指向任何結點.此時不能通過P來訪問結點.否則會引起程序錯誤。假如輸入的數(shù)字不符合題目要求.則會產(chǎn)生錯誤結果。

算法的時空分析：

時間和空間性能分析：時間上.對于含n個字符的表達式.無論是對其進行合法性檢測還是對其進行入棧出棧操作n次.因此其時間簡單度為O(n)?？臻g上.由于是用數(shù)組來存儲輸入的表達式.用棧來存儲運算中的數(shù)據(jù)和運算符.而棧的本質也用到的數(shù)組.數(shù)組在定義時必需確定其大小。在不知表達式長度的狀況下確定數(shù)組的長度確非易事.此時極易造成空間的鋪張.因此空間性能不是很好。

四、具體設計

源程序

#include

usingnamespacestd;

#defineSTACK_INIT_SIZE100

#defineSTACKINCREMENT10

typedefstruct//運算符棧

{

char*base;

char*top;

intstacksize;

}SqStack1;

typedefstruct//運算數(shù)棧

{

float*base;

float*top;

intstacksize;

}SqStack2;

voidInitStack1(SqStack1//聲明棧建立函數(shù)

voidInitStack2(SqStack2//聲明棧建立函數(shù)

voidevaluate(SqStack1//確定如何入棧函數(shù)voidPush1(SqStack1//聲明入棧函數(shù)

voidPush2(SqStack2//聲明入壓棧函數(shù)

charGetTop1(SqStack1//聲明取棧頂元素函數(shù)

floatGetTop2(SqStack2//聲明取棧頂元素函數(shù)

charPop1(SqStack1//聲明出棧函數(shù)

floatPop2(SqStack2//聲明出棧函數(shù)

charCompare(charm,charn);//聲明比較函數(shù)

floatOperate(floata,charrheta,floatb);//聲明運算函數(shù)voidDispStack1(SqStack1//從棧底到棧頂依次輸出各元素voidDispStack2(SqStack2//從棧底到棧頂依次輸出各元素

/*主函數(shù)*/

voidmain

{

SqStack1S1;//定義運算符棧

SqStack2S2;//定義運算數(shù)棧

//freopen("data1.in","r",stdin);

//freopen("data1.out","w",stdout);

InitStack1(S1);//調用棧建立函數(shù)

InitStack2(S2);//調用棧建立函數(shù)

evaluate(S1,S2);//調用確定如何入棧函數(shù)

cout>ch;

c=ch[0];

cout1)t=t*10+e;

c=ch[s++];

}

if(n==-1)

{

e=float(c-48);

t=t+e/10;

c=ch[s++];

}

if(c=='.')

{

n=-1;

c=ch[s++];

}

if((c>='0'

gotoas;

}

if(c'9')

{

Push2(S2,t);

}

cout'://棧頂元素優(yōu)先級高.則退棧并將運算結果入棧

p1=Pop2(S2);

p2=Pop2(S2);

ch1=Pop1(S1);

Push2(S2,Operate(p2,ch1,p1));

cout';//否則.棧頂符號優(yōu)先級高,返回">"

}

elseif(n=='*'||n=='/')//輸入的符號為"*"、"/"

{

if(m==')'||m=='*'||m=='/')return'>';//棧頂元素為")"、"*"、"/",此時棧頂符號優(yōu)先級高.返回">"

elsereturn'';//否則.棧頂符號優(yōu)先級高,返回">"

}

else//輸入符號為其他

{

if(m=='#')return'=';//棧頂元素為"#",此時優(yōu)先級同.返回"="

elsereturn'>';//否則.棧頂符號優(yōu)先級高,返回">"

}

}

floatOperate(floata,chartheta,floatb)//運算函數(shù)

{

floattmp=0;

if(theta=='+')tmp=a+b;//從運算符棧取出的符號為"+".則運算數(shù)棧的兩元素相加.并返回

elseif(theta=='-')tmp=a-b;//從運算符棧取出的符號為"-".則運算數(shù)棧的兩元素相減.并返回

elseif(theta=='*')tmp=a*b;//從運算符棧取出的符號為"*".則運算數(shù)棧的兩元素相乘.并返回

elseif(theta=='/')//從運算符棧取出的符號為"/".則運算數(shù)棧的兩元素相除.并返回

{

if(b==0)cout<<"\n表達式出錯!除數(shù)不能為0!\n";

elsetmp=a/b;

}

returntmp;

}

五、運行與測試

第六章總結與心得

數(shù)據(jù)結構的討論不僅涉及到計算機硬件的討論.而且和計算機軟件的討論有著更親密的關系.無論是編譯程序還是操作系統(tǒng).都涉及到數(shù)據(jù)元素在存儲器中的安排問題。在討論信息檢索時也必需考慮如何組織數(shù)據(jù).以便使查找和存取數(shù)據(jù)元素更為便利。

在課程設計中.應當力求算法簡明易懂.而易于轉換為上機程序；假如程序反復多次使用.則應當盡可能選用快速的算法；假如待解決的問題數(shù)據(jù)量極大.機器的存儲空間較小.則在編寫算法時應當考慮如何節(jié)約空間。以后在編寫程序時就應當留意到所編寫程序的時間簡單度.以及是否運用了良好的算法.而不能只是像以前編寫程序時單純使用C語言的學問.要充分考慮程序的性能.爭取編寫出更優(yōu)良的程序來。

讓我對數(shù)據(jù)結構有了更進一步的熟悉和了解.也讓我知道.要想學好它要重在實踐.理論與實際應用相結合.提高了自己組織數(shù)據(jù)及編寫大型程序的力