數(shù)據(jù)結(jié)構(gòu)算術(shù)表達(dá)式求值實驗報告.doc

北京理工大學(xué)珠海學(xué)院北京理工大學(xué)珠海學(xué)院 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計報告課程設(shè)計報告 題目 題目 算術(shù)表達(dá)式求值算術(shù)表達(dá)式求值 所在學(xué)院 所在學(xué)院 專業(yè)班級 專業(yè)班級 學(xué)生姓名 學(xué)生姓名 指導(dǎo)教師 指導(dǎo)教師 2010 年年 05 月月 26 日日 目錄目錄 1 前 前 言言 1 2 概要設(shè)計 概要設(shè)計 1 2 1 數(shù)據(jù)結(jié)構(gòu)設(shè)計數(shù)據(jù)結(jié)構(gòu)設(shè)計 1 2 2 算法設(shè)計算法設(shè)計 1 2 3 ADT 描述描述 2 2 4 功能模塊分析功能模塊分析 2 3 詳細(xì)設(shè)計 詳細(xì)設(shè)計 3 3 1 數(shù)據(jù)存儲結(jié)構(gòu)設(shè)計數(shù)據(jù)存儲結(jié)構(gòu)設(shè)計 3 3 2 主要算法流程圖 或算法偽代碼 主要算法流程圖 或算法偽代碼 3 4 軟件測 軟件測試試 6 5 心得體會 心得體會 8 參考文獻(xiàn)參考文獻(xiàn) 8 附附 錄錄 8 北京理工大學(xué)珠海學(xué)院計算機(jī)科學(xué)技術(shù)學(xué)院 第 1 頁 1 前 前 言言 在計算機(jī)中 算術(shù)表達(dá)式由常量 變量 運算符和括號組成 由于不同的運算符具有不同的優(yōu)先級 又要考慮括號 因此 算術(shù)表達(dá)式的求值不可能嚴(yán)格地從左到右進(jìn)行 因而在程序設(shè)計時 借助棧實現(xiàn) 算法輸入 一個算術(shù)表達(dá)式 由常量 變量 運算符和括號組成 以字符串形式輸入 為簡化 規(guī) 定操作數(shù)只能為正整數(shù) 操作符為 用 表示結(jié)束 算法輸出 表達(dá)式運算結(jié)果 算法要點 設(shè)置運算符棧和運算數(shù)棧輔助分析算符優(yōu)先關(guān)系 在讀入表達(dá)式的字符序列的同時 完 成運算符和運算數(shù)的識別處理 以及相應(yīng)運算 2 概要設(shè)計 概要設(shè)計 2 1 數(shù)據(jù)結(jié)構(gòu)設(shè)計 任何一個表達(dá)式都是由操作符 運算符和界限符組成的 我們分別用順序棧來寄存表達(dá)式的操作 數(shù)和運算符 棧是限定于緊僅在表尾進(jìn)行插入或刪除操作的線性表 順序棧的存儲結(jié)構(gòu)是利用一組連 續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素 同時附設(shè)指針 top 指示棧頂元素在順序棧中的位置 base 為棧底指針 在順序棧中 它始終指向棧底 即 top base 可作為?？盏臉?biāo)記 每當(dāng)插入新的 棧頂元素時 指針 top 增 1 刪除棧頂元素時 指針 top 減 1 2 2 算法設(shè)計 為了實現(xiàn)算符優(yōu)先算法 可以使用兩個工作棧 一個稱為 OPTR 用以寄存運算符 另一個稱做 OPND 用以寄存操作數(shù)或運算結(jié)果 1 首先置操作數(shù)棧為空棧 表達(dá)式起始符 為運算符棧的棧底元素 2 依次讀入表達(dá)式 若是操作符即進(jìn) OPND 棧 若是運算符則和 OPTR 棧的棧頂運算符比較優(yōu) 先權(quán)后作相應(yīng)的操作 直至整個表達(dá)式求值完畢 即 OPTR 棧的棧頂元素和當(dāng)前讀入的字符均為 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 第 2 頁 2 3 ADT 描述 ADT Stack 數(shù)據(jù)對象 D ElemSet i 1 2 n n 0 i a i a 數(shù)據(jù)對象 R1 i 2 n 1 ii aa 1 i aDai 約定端為棧頂 端為棧底 n a i a 基本操作 InitStack char base char top Stack 定義整型棧 typedef struct int stacksize int base int top Stack2 3 2 主要算法流程圖 或算法偽代碼 1 Precede char c1 char c2 判斷運算符優(yōu)先權(quán) 返回優(yōu)先權(quán)高的 算符間的優(yōu)先關(guān)系如下 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 第 4 頁 用一維數(shù)組存儲 49 種情況 switch c1 i 為下面 array 的橫標(biāo) case i 0 break case i 1 break case i 2 break case i 3 break case i 4 break case i 5 break case i 6 break switch c2 j 為下面 array 的縱標(biāo) case j 0 break case j 1 break case j 2 break case j 3 break case j 4 break case j 5 break case j 6 break return array 7 i j 返回運算符 array 7 i j 為對應(yīng)的 c1 c2 優(yōu)先關(guān)系 北京理工大學(xué)珠海學(xué)院計算機(jī)科學(xué)技術(shù)學(xué)院 第 5 頁 2 int EvalExpr 主要操作函數(shù) 算法概要流程圖 利用該算法對算術(shù)表達(dá)式 3 7 2 求值操作過程如下 步驟OPTR 棧OPND 棧輸入字符主要操作 1 3 7 2 Push OPND 3 2 3 7 2 Push OPTR 3 3 7 2 Push OPNR 4 37 2 Push OPND 7 5 3 7 2 Push OPNR 6 3 72 Push OPND 2 7 3 7 2 Operate 7 2 8 3 5 Pop OPTR 9 3 5 Operate 3 5 10 15 Return GetTop2 OPND 表 2 算法偽代碼如下 int EvalExpr 主要操作函數(shù) c ptr while c GetTop OPTR if In c 不是運算符即進(jìn)棧 if In ptr 1 ptr ptr 1 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 第 6 頁 m atoi ptr 取字符串前面的數(shù)字段 n num m Push2 ptr ptr n c ptr else switch Precede GetTop OPTR c case 退棧并將運算結(jié)果入棧 theta Pop b Pop2 a Pop2 Push2 break 4 軟件測試 軟件測試 1 運行成功后界面 北京理工大學(xué)珠海學(xué)院計算機(jī)科學(xué)技術(shù)學(xué)院 第 7 頁 2 輸入正確的表達(dá)式后 3 更改表達(dá)式 輸入有 2 位數(shù)的整數(shù)調(diào)試 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 第 8 頁 5 心得體會 心得體會 這次課程設(shè)計讓我更加了解大一學(xué)到的 C 和這個學(xué)期學(xué)到的數(shù)據(jù)結(jié)構(gòu) 課設(shè)題目要 求不僅要求對課本知識有較深刻的了解 同時要求程序設(shè)計者有較強(qiáng)的思維和動手能力 和更加了解編程思想和編程技巧 這次課程設(shè)計讓我有一個深刻的體會 那就是細(xì)節(jié)決定成敗 編程最需要的是嚴(yán)謹(jǐn) 如何的嚴(yán)謹(jǐn)都不過分 往往檢查了半天發(fā)現(xiàn)錯誤發(fā)生在某個括號 分號 引號 或者數(shù) 據(jù)類型上 就像我在寫 EvalExpr 函數(shù)時 忘了指針的地址符值不用加 號 這一點小小 的錯誤也耽誤了我?guī)资昼?所以說細(xì)節(jié)很重要 程序設(shè)計時 也不要怕遇到錯誤 在實際操作過程中犯的一些錯誤還會有意外的收 獲 感覺課程設(shè)計很有意思 在具體操作中這學(xué)期所學(xué)的數(shù)據(jù)結(jié)構(gòu)的理論知識得到鞏固 達(dá)到課程設(shè)計的基本目的 也發(fā)現(xiàn)自己的不足之出 在以后的上機(jī)中應(yīng)更加注意 同時 體會到 C 語言具有的語句簡潔 使用靈活 執(zhí)行效率高等特點 發(fā)現(xiàn)上機(jī)的重要作用 特別算術(shù)表達(dá)式有了深刻的理解 這個程序是我們 3 個人完成的 同時我認(rèn)為我們的工作是一個團(tuán)隊的工作 團(tuán)隊需 要個人 個人也離不開團(tuán)隊 必須發(fā)揚團(tuán)結(jié)協(xié)作的精神 某個人的離群都可能導(dǎo)致導(dǎo)致 整項工作的失敗 實習(xí)中只有一個人知道原理是遠(yuǎn)遠(yuǎn)不夠的 必須讓每個人都知道 否 則一個人的錯誤 就有可能導(dǎo)致整個工作失敗 團(tuán)結(jié)協(xié)作是我們成功的一項非常重要的 保證 而這次課程設(shè)計也正好鍛煉我們這一點 這也是非常寶貴的 最后 感謝老師在這次課程設(shè)計的悉心指導(dǎo) 祝老師身體健康 工作順利 最后 感謝老師在這次課程設(shè)計的悉心指導(dǎo) 祝老師身體健康 工作順利 參考文獻(xiàn)參考文獻(xiàn) 1 數(shù)據(jù)結(jié)構(gòu) C 語言版 嚴(yán)蔚敏 清華大學(xué)出版社 2 C 語言程序設(shè)計 丁峻嶺 中國鐵道出版社 3 C 程序設(shè)計 譚浩強(qiáng) 清華大學(xué)出版社 附附 錄錄 程序源代碼 北京理工大學(xué)珠海學(xué)院計算機(jī)科學(xué)技術(shù)學(xué)院 第 9 頁 include include include define NULL 0 define OK 1 define ERROR 1 define STACK INIT SIZE 100 define STACKINCREMENT 20 定義字符類型棧 typedef struct int stacksize char base char top Stack 定義整型棧 typedef struct int stacksize int base int top Stack2 全局變量 Stack OPTR 定義運算符棧 Stack2 OPND 定義操作數(shù)棧 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 第 10 頁 char expr 255 存放表達(dá)式串 char ptr expr int InitStack Stack s 構(gòu)造運算符棧 s base char malloc STACK INIT SIZE sizeof char if s base return ERROR s top s base s stacksize STACK INIT SIZE return OK int InitStack2 Stack2 s 構(gòu)造操作數(shù)棧 s base int malloc STACK INIT SIZE sizeof int if s base return ERROR s stacksize STACK INIT SIZE s top s base return OK int In char ch 判斷字符是否是運算符 運算符即返回 1 return ch ch ch ch ch ch ch 北京理工大學(xué)珠海學(xué)院計算機(jī)科學(xué)技術(shù)學(xué)院 第 11 頁 int Push Stack s char ch 運算符棧插入 ch 為新的棧頂元素 s top ch s top return 0 int Push2 Stack2 s int ch 操作數(shù)棧插入 ch 為新的棧頂元素 s top ch s top return 0 char Pop Stack s 刪除運算符棧 s 的棧頂元素 用 p 返回其值 char p s top p s top return p int Pop2 Stack2 s 刪除操作數(shù)棧 s 的棧頂元素 用 p 返回其值 int p 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 第 12 頁 s top p s top return p char GetTop Stack s 用 p 返回運算符棧 s 的棧頂元素 char p s top 1 return p int GetTop2 Stack2 s 用 p 返回操作數(shù)棧 s 的棧頂元素 int p s top 1 return p 判斷運算符優(yōu)先權(quán) 返回優(yōu)先權(quán)高的 char Precede char c1 char c2 int i 0 j 0 static char array 49 北京理工大學(xué)珠海學(xué)院計算機(jī)科學(xué)技術(shù)學(xué)院 第 13 頁 switch c1 i 為下面 array 的橫標(biāo) case i 0 break case i 1 break case i 2 break case i 3 break case i 4 break case i 5 break case i 6 break switch c2 j 為下面 array 的縱標(biāo) case j 0 break case j 1 break case j 2 break case j 3 break 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 第 14 頁 case j 4 break case j 5 break case j 6 break return array 7 i j 返回運算符 操作函數(shù) int Operate int a char op int b switch op case return a b case return a b case return a b case return a b return 0 int num int n 返回操作數(shù)的長度 char p 10 itoa n p 10 把整型轉(zhuǎn)換成字符串型 n strlen p 北京理工大學(xué)珠海學(xué)院計算機(jī)科學(xué)技術(shù)學(xué)院 第 15 頁 return n int EvalExpr 主要操作函數(shù) char c theta x int n m int a b c ptr while c GetTop OPTR if In c if In ptr 1 ptr ptr 1 m atoi ptr 取字符串前面的數(shù)字段 n num m Push2 ptr ptr n c ptr else switch Precede GetTop OPTR c case theta Pop b Pop2 a Pop2 Push2 break return GetTop2 OPND int main printf 請輸入正確的表達(dá)式以 結(jié)尾 do gets expr while expr InitStack 初始化運