第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

利用棧求表達(dá)式的值

2013級(jí)計(jì)算機(jī)科學(xué)與技術(shù)系

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

目 錄

目 錄..................................................................................................................................2 摘要......................................................................................................................................3 1 引言..................................................................................................................................4 1.1問題的提出.............................................................................................................4 1.2 任務(wù)與分析............................................................................................................4 2 程序的主要功能................................................................................................................5 2.1 程序功能設(shè)計(jì).........................................................................................................5 2.2 附加功能................................................................................................................5 2.3功能函數(shù).................................................................................................................5 3 程序運(yùn)行平臺(tái)....................................................................................................................6 4總體設(shè)計(jì)............................................................................................................................6 4.1 方案總體設(shè)計(jì).........................................................................................................6 4.2程序流程圖.............................................................................................................7 5程序類的說明....................................................................................................................8 5.1主要函數(shù).................................................................................................................8 5.2 函數(shù)間的調(diào)用關(guān)系..................................................................................................9 5.2.1函數(shù)調(diào)用流程................................................................................................9 5.2.2函數(shù)調(diào)用說明................................................................................................9 6系統(tǒng)測(cè)試分析..................................................................................................................10 7程序源代碼......................................................................................................................13 8心得體會(huì)..........................................................................................................................25 9參考文獻(xiàn)..........................................................................................................................25

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

摘要

隨著計(jì)算機(jī)科學(xué)與技術(shù)的迅猛發(fā)展，計(jì)算機(jī)應(yīng)用層面的不斷普及，利用計(jì)算機(jī)及相關(guān)的計(jì)算機(jī)編程技術(shù)實(shí)現(xiàn)對(duì)現(xiàn)實(shí)生活中一些問題的處理，可以簡(jiǎn)化生活中的某些問題，給人民生活帶來方便。數(shù)據(jù)結(jié)構(gòu)是一門基于數(shù)據(jù)類型處理的學(xué)科，利用數(shù)據(jù)結(jié)構(gòu)相關(guān)知識(shí)處理表達(dá)式的合法性及表達(dá)式的處理結(jié)果可以簡(jiǎn)化計(jì)算、判斷表達(dá)式。

此軟件可以實(shí)現(xiàn)判斷表達(dá)式的合法性，如果表達(dá)式合法則進(jìn)行計(jì)算，如果不合法則提醒用戶表達(dá)式錯(cuò)誤，請(qǐng)用戶重新輸入。在合法的基礎(chǔ)上會(huì)對(duì)表達(dá)式進(jìn)行計(jì)算，在計(jì)算完成的同時(shí)會(huì)提醒用戶是否繼續(xù)進(jìn)行計(jì)算，不進(jìn)行計(jì)算則進(jìn)入是否保存界面。用戶可以保存多次記錄，并可以隨時(shí)查看，也可以清楚全部記錄，根據(jù)用戶需求而定。

關(guān)鍵詞：表達(dá)式的值，數(shù)據(jù)結(jié)構(gòu),棧；

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 引言

1.1問題的提出

數(shù)據(jù)結(jié)構(gòu)是一門理論性很強(qiáng)的學(xué)科、思維抽象、難度較大的課程，是專業(yè)課和基礎(chǔ)課之間的橋梁。該課程的先行課是計(jì)算機(jī)基礎(chǔ)，c語言程序設(shè)計(jì)，離散數(shù)學(xué)等，后續(xù)課程有操作系統(tǒng)，數(shù)據(jù)庫(kù)原理，軟件工程等。通過本門課程的學(xué)習(xí)，我們應(yīng)該能夠透徹的理解各種數(shù)據(jù)對(duì)象的特點(diǎn)，學(xué)會(huì)數(shù)據(jù)的組織方法和實(shí)現(xiàn)方法，并進(jìn)一步培養(yǎng)良好的程序設(shè)計(jì)能力，而且該課程的研究方法對(duì)我們學(xué)生在校及工作學(xué)習(xí)都是很有幫助，意義重大。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)的一門專門的核心專業(yè)基礎(chǔ)課，在該專業(yè)起著承上啟下的作用，學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)于提高理論認(rèn)知水平和實(shí)踐能力都有著極為重要的作用。學(xué)好數(shù)據(jù)結(jié)構(gòu)的最終目的是為了獲得新的解決問題的辦法。對(duì)于現(xiàn)實(shí)世界的問題，應(yīng)該能抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，該數(shù)學(xué)模型在計(jì)算機(jī)內(nèi)部的數(shù)據(jù)結(jié)構(gòu)表示，然后設(shè)計(jì)一個(gè)解決此數(shù)學(xué)模型的算法，在進(jìn)行程序編寫調(diào)試，最后得到問題的解答。

1.2 任務(wù)與分析

基于上述數(shù)據(jù)結(jié)構(gòu)的分析，我們開設(shè)了數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)這門課。針對(duì)這門課程的特點(diǎn)，著重培養(yǎng)我們的動(dòng)手實(shí)踐能力，我們的任務(wù)是基于visual c++ 6.0運(yùn)行平臺(tái)設(shè)計(jì)出一套完整的c語言算法，解決表達(dá)是求值問題。表達(dá)式的求值分為幾個(gè)階段：首先判斷表達(dá)式是否正確，針對(duì)出現(xiàn)的符號(hào)是否是合法字符以及是否是字符重復(fù)出現(xiàn)進(jìn)行判斷，此過程運(yùn)用數(shù)據(jù)結(jié)構(gòu)中棧的基本原理。然后對(duì)于檢查過的表達(dá)式進(jìn)行計(jì)算，運(yùn)用數(shù)學(xué)中的先乘后除再加減，有括號(hào)先計(jì)算括號(hào)的運(yùn)算規(guī)則進(jìn)行四則運(yùn)算。最后，在計(jì)算完整的基礎(chǔ)上詢問是否保存本次運(yùn)行記錄，根據(jù)相應(yīng)提示即可進(jìn)行操作。利用棧求表達(dá)式的值，雖然是很簡(jiǎn)單的程序算法，但是在編寫過程中可能也會(huì)遇到很多問題，我們組的成員也會(huì)通過各種途徑進(jìn)行排難，達(dá)到成功運(yùn)行并解決問題的辦法。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 程序的主要功能

2.1 程序功能設(shè)計(jì)

編寫程序?qū)崿F(xiàn)表達(dá)式求值，即驗(yàn)證某算術(shù)表達(dá)式的正確性，若正確，則計(jì)算該算術(shù)表達(dá)式的值。主要功能描述如下：

1、從鍵盤上輸入表達(dá)式，以“=” 號(hào)結(jié)束表達(dá)式。

2、分析該表達(dá)式是否合法：

（1）是數(shù)字，則判斷該數(shù)字的合法性。若合法，則壓入數(shù)據(jù)到堆棧中。（2）是規(guī)定的運(yùn)算符，則根據(jù)規(guī)則進(jìn)行處理。在處理過程中，將計(jì)算該表達(dá)式的值。

（3）若是其它字符，則返回錯(cuò)誤信息。

3、若上述處理過程中沒有發(fā)現(xiàn)錯(cuò)誤，則認(rèn)為該表達(dá)式合法，并打印處理結(jié)果。

2.2 附加功能

1、規(guī)定表達(dá)式的合法性

2、小數(shù)計(jì)算

3、計(jì)算記錄的保存與查看

4、其他

（1）規(guī)定表達(dá)式的合法性，括號(hào)配對(duì)，不能出現(xiàn)“6++3”、“6+－3”等符號(hào)重疊的情況。

（2）表達(dá)式開頭只能是數(shù)字或“（”，表達(dá)式中只能有一個(gè)“=”。

2.3功能函數(shù)

程序中主要包含下面幾個(gè)功能函數(shù)： void initstack()：初始化堆棧 int make_str()：語法檢查并計(jì)算

int push_num(double num)：將操作數(shù)壓入堆棧 char procede(char top,char code)：處理操作碼

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

int change_opnd(int operate)：將字符型操作碼轉(zhuǎn)換成優(yōu)先級(jí) int change_opnd(char code)：將操作碼壓入堆棧 char pop_opnd(opnd *op)：將操作碼彈出堆棧 int caculate(int cur_opnd)：簡(jiǎn)單計(jì)算+，-，*，/ double pop_num(num *nu)：彈出操作數(shù) 程序運(yùn)行平臺(tái)

硬件系統(tǒng)：Intel（R）Core(TM)i3-3240 CPU @ 3.40GHz 3.39GHz, 4GB內(nèi)存，500GB硬盤。

軟件系統(tǒng)：windows xp操作系統(tǒng)，visual c++ 6.0 編譯軟件。

4總體設(shè)計(jì)

4.1 方案總體設(shè)計(jì)

（1）定義一個(gè)expression全局表達(dá)式結(jié)構(gòu)體expr[1000]存放計(jì)算過的表達(dá)式(expstr[MAXSIZE])和計(jì)算結(jié)果(result)、一個(gè)計(jì)量器(i)、一個(gè)表達(dá)式字符串、一個(gè)操作碼棧和一個(gè)操作數(shù)棧；

（2）把表達(dá)式字符串從頭到尾逐一掃描，將輸入的表達(dá)式進(jìn)行語法檢查；（3）第一個(gè)字符只能是數(shù)字或“（”，最重一個(gè)字符只能是“=”；（4）表達(dá)式括號(hào)必須配對(duì)，中間不能出現(xiàn)“=”；

（5）在“（”前面只能是“+、－、*、/、(”，在“+、－、*、/、=、)”前面只能是數(shù)字或“）”；

（6）把表達(dá)式字符串從頭到尾逐一掃描，直到表達(dá)式掃描完畢，操作碼棧為空；

（7）把字符根據(jù)運(yùn)算優(yōu)先級(jí)別選擇操作；

（8）把表達(dá)式中的數(shù)值部分字符串轉(zhuǎn)成數(shù)值壓入操作數(shù)棧；

（9）是“(”直接壓入到操作碼棧，級(jí)別比操作碼棧頂元素高的，把運(yùn)算符壓入操作碼棧；

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

（10）級(jí)別比操作碼棧低的，彈出操作碼棧的棧頂元素和操作數(shù)棧的兩個(gè)棧頂元素，進(jìn)行運(yùn)算后再壓入操作數(shù)棧；

（11）是“)”，若操作碼棧頂是“(”，把彈出操作碼棧頂元素，否則“)”視為級(jí)別最低的元素，重復(fù)7；

（12）最后計(jì)算出結(jié)果并將其存放在expr[i]，計(jì)量器加1；（13）重復(fù)計(jì)算后，將結(jié)果保存在文件里，并統(tǒng)計(jì)計(jì)算次數(shù)；（14）查看多次計(jì)算結(jié)果，以表形式輸出；（15）查看本次計(jì)算記錄，以表形式輸出；（16）清除計(jì)算記錄，重新計(jì)算。

4.2程序流程圖

main Exit()start()load()ClearFile result()check()

Start2()save()7

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

5程序類的說明

5.1主要函數(shù)

void start(opnd *op,num *nu)//程序主菜單

void start2(opnd *op,num *nu)//第二層計(jì)算選擇，子菜單 void load()//顯示所有計(jì)算記錄 void save()//保存計(jì)算結(jié)果 void check()//顯示本次計(jì)算結(jié)果 void result(opnd *op,num *nu)//計(jì)算結(jié)果

double caculate(opnd *op,num *nu)//簡(jiǎn)單計(jì)算+，-，*，/ 表達(dá)式處理函數(shù)： int make_str()//語法檢查

double change_num(char str[])//數(shù)字字符串轉(zhuǎn)成double型數(shù)字 char procede(char top,char code)//處理操作碼，判斷棧的操作 int change_opnd(char code)//字符型操作碼轉(zhuǎn)換優(yōu)先級(jí)，非表達(dá)式字符返回-2 棧操作函數(shù)：

double get_num(num *nu)//查看操作數(shù)棧棧頂 double pop_num(num *nu)//操作數(shù)棧出棧

int push_num(num *nu,double da)//壓入操作數(shù)棧 int empty_num(num *nu)//判空 void initstack(num *nu)char get_opnd(opnd *op)//查看棧頂 char pop_opnd(opnd *op)//出棧 int push_opnd(opnd *op,char co)//壓棧 int empty_opnd(opnd *op)//判空 void initstack(opnd *op)//初始化棧

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

5.2 函數(shù)間的調(diào)用關(guān)系 5.2.1函數(shù)調(diào)用流程

main()：主函數(shù) → start();↗load()→start();start()程序模式函數(shù)→清空文件→exit();↘make_str()→result(op,nu)→start2()→start();↗ load → start();start2()子菜單 → save()→ start2();↘ check()→ start2();result(op,nu)計(jì)算結(jié)果→initstack(op)→initstack(nu)→push_opnd(op,'=')→

↗push_num(nu,change_num(str2));→change_opnd(*ps)↗push_opnd(op,*ps)； ↘procede(get_opnd(op),*ps)→pop_opnd(op);↘push_num(nu,caculate(op,nu))caculate(op,nu)→b=pop_num(nu)→a=pop_num(nu)→pop_opnd(op)

5.2.2函數(shù)調(diào)用說明

main()函數(shù)：調(diào)用了一個(gè)函數(shù)start()，start()判斷執(zhí)行查看所有計(jì)算記錄函數(shù)load()，或是清空以往的所有計(jì)算記錄，或是退出程序，或是檢查輸入表達(dá)式語法make_str()并計(jì)算表達(dá)式result(op,nu)的操作。

result(op,nu)函數(shù)：是計(jì)算表達(dá)式，調(diào)用了初始化棧函數(shù)和字符級(jí)別判斷change_opnd(*ps)，若是數(shù)字，則調(diào)用轉(zhuǎn)化數(shù)字change_num(str2)然后壓入操作數(shù)棧，若是運(yùn)算符，剛調(diào)用判斷操作procede(get_opnd(op),*ps)，若是“<”,則壓入操作碼棧push_opnd(op,*ps)，若是“=”，則彈出操作碼棧頂pop_opnd(op)，若是“>”，則彈出操作碼棧的棧頂元素和操作數(shù)棧的兩個(gè)棧頂元素，進(jìn)行運(yùn)算caculate(op,nu)后再壓入操作數(shù)棧，計(jì)算完畢后按start()順序

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

運(yùn)行。

start2()函數(shù)：在計(jì)算結(jié)果后調(diào)用跟隨的選擇菜單，進(jìn)行查看結(jié)果check()、保存結(jié)果save()、查看計(jì)算記錄load()、回到主菜單的操作。

6系統(tǒng)測(cè)試分析

(1)程序主界面，根據(jù)提示選擇相應(yīng)的輸入字母選擇相應(yīng)菜單。在系統(tǒng)第一次運(yùn)行的時(shí)候，查看記錄是不會(huì)有結(jié)果的，應(yīng)當(dāng)首先進(jìn)行計(jì)算式子，然后進(jìn)行保存過，才會(huì)有結(jié)果。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

（2）計(jì)算式子，根據(jù)需要輸入了以上三個(gè)式子，計(jì)算結(jié)果都正確無誤。計(jì)算完畢，輸入e結(jié)束計(jì)算，程序進(jìn)入子菜單。

（3）在計(jì)算完式子以后進(jìn)入子菜單選擇界面，我們對(duì)式子進(jìn)行保存處理。進(jìn)入（4）。

（4）對(duì)剛剛輸入計(jì)算的式子進(jìn)行保存，選擇s，提示式子已經(jīng)被保存下來了。接下來我們回到主界面，查看記錄。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

（5）我們輸入了l，程序返回我們剛剛保存的計(jì)算記錄，并且進(jìn)行個(gè)數(shù)統(tǒng)計(jì)。

（6）我們對(duì)剛才的保存的記錄進(jìn)行清空處理，按c，確定后，返回結(jié)果為所有記錄為空，我們也可以對(duì)此事的系統(tǒng)進(jìn)行再次查詢處理，結(jié)果也會(huì)發(fā)現(xiàn)是沒有記錄的。最后我們按e，則整個(gè)系統(tǒng)退出。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

7程序源代碼

#include #include #include #include //宏定義

#define MAXSIZE 100 #define N 1000 int i=0;

//表達(dá)式數(shù)

typedef struct expression//表達(dá)式結(jié)構(gòu)

{ long double result;

char expstr[MAXSIZE];}expression;expression expr[N];//表達(dá)式的一個(gè)整體容器s

typedef struct//操作碼棧定義

{ char code[MAXSIZE];int top;}opnd;

typedef struct//操作數(shù)棧定義

{ double date[MAXSIZE];int top;}num;//《——opnd棧操作——》：

void initstack(opnd *op)//初始化棧

{ op->top=-1;} int empty_opnd(opnd *op)//判斷是否為空棧

{ if(op->top==-1)

return 0;else return 1;}

int push_opnd(opnd *op,char co)//入棧

{

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

if(op->top==MAXSIZE-1)

{

printf(“The ”opnd“ stack is full.”);

return 0;

} op->top++;op->code[op->top]=co;return 1;} char pop_opnd(opnd *op)//出棧

{ char a='