《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》表達(dá)式求值實(shí)驗(yàn)報(bào)告-1

1/1《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》表達(dá)式求值實(shí)驗(yàn)報(bào)告試驗(yàn)課程名稱

專業(yè)班級(jí)

同學(xué)姓名

學(xué)號(hào)

指導(dǎo)老師

20至20學(xué)年第學(xué)期第至周

算術(shù)表達(dá)式求值演示

一、概述

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

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

二、系統(tǒng)分析

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

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

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

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

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

本程序?yàn)榱耸褂迷敿?xì).采納菜單式的方式來完成程序的演示.幾乎不用輸入什么特別的命令.只需按提示輸入表達(dá)式即可。（要留意輸入時(shí)格式.否者可能會(huì)引起一些錯(cuò)誤）5.測(cè)試數(shù)據(jù)。

三、概要設(shè)計(jì)

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

算法設(shè)計(jì)

程序包含三個(gè)模塊

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

voidmain{

輸入表達(dá)式；

依據(jù)要求進(jìn)行轉(zhuǎn)換并求值；

輸出結(jié)果；

}

(2)表達(dá)式求值模塊——實(shí)現(xiàn)詳細(xì)求值。

(3)表達(dá)式轉(zhuǎn)換模塊——實(shí)現(xiàn)轉(zhuǎn)換。

各個(gè)函數(shù)之間的調(diào)用關(guān)系

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

主函數(shù)

表達(dá)式轉(zhuǎn)換表達(dá)式求值

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

輸出輸出

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

數(shù)據(jù)關(guān)系：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);//聲明運(yùn)算函數(shù)

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

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

}ADTSqStack

結(jié)構(gòu)分析:

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

算法的時(shí)空分析：

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

四、具體設(shè)計(jì)

源程序

#include

usingnamespacestd;

#defineSTACK_INIT_SIZE100

#defineSTACKINCREMENT10

typedefstruct//運(yùn)算符棧

{

char*base;

char*top;

intstacksize;

}SqStack1;

typedefstruct//運(yùn)算數(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);//聲明運(yùn)算函數(shù)voidDispStack1(SqStack1//從棧底到棧頂依次輸出各元素voidDispStack2(SqStack2//從棧底到棧頂依次輸出各元素

/*主函數(shù)*/

voidmain

{

SqStack1S1;//定義運(yùn)算符棧

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

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

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

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

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

evaluate(S1,S2);//調(diào)用確定如何入棧函數(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)先級(jí)高.則退棧并將運(yùn)算結(jié)果入棧

p1=Pop2(S2);

p2=Pop2(S2);

ch1=Pop1(S1);

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

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

}

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

{

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

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

}

else//輸入符號(hào)為其他

{

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

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

}

}

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

{

floattmp=0;

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

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

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

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

{

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

elsetmp=a/b;

}

returntmp;

}

五、運(yùn)行與測(cè)試

第六章總結(jié)與心得

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

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

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