資料結構課程設計
設計說明書
數學與電腦科學學院
2023年 9月 7日
資料結構課程設計評閱書
注：指導教師成績60%，答辯成績40%，總成績合成後按五級制記入
課程設計任務書
2011—2012學年第2學期
專業學號姓名
課程設計名稱資料結構課程設計
設計題目表示式求值演算法的實現
完成期限：自 2012 年 8 月 28 日至 2012 年 9 月 7 日共 2 周
棧的儲存和相關運算是資料結構中陣列部分的重點知識和技能。表示式求值演算法可借助棧來完成，它的儲存可以使用順序結構也可以使用鏈式結構，這要根據具體的應用來決定。本課程設計按以下的要求運用c/ c++結構體、指標、資料結構等基知識程式設計實現。
任務要求：1）闡述設計思想,畫出流程圖;2）任意輸入乙個表示式（算術、邏輯、關係表示式）；3）建立棧；4）借助棧的相關運算完成表示式求值過程;5）將表示式及其運算結果按照其數學形式列印輸出; 6）說明測試方法,寫出完整的執行結果,較好的介面設計；7）按照格式要求完成課程設計說明書。
設計要求:
1）問題分析和任務定義：根據設計題目的要求，充分地分析和理解問題，明確問題要求做什麼？（而不是怎麼做？）限制條件是什麼？確定問題的輸入資料集合。
2）邏輯設計：對問題描述中涉及的操作物件定義相應的資料型別，並按照以資料結構為中心的原則劃分模組，定義主程式模組和各抽象資料型別。邏輯設計的結果應寫出每個抽象資料型別的定義（包括資料結構的描述和每個基本操作的功能說明），各個主要模組的演算法，並畫出模組之間的呼叫關係圖；
3）詳細設計：定義相應的儲存結構並寫出各函式的偽碼演算法。在這個過程中，要綜合考慮系統功能，使得系統結構清晰、合理、簡單和易於除錯，抽象資料型別的實現盡可能做到資料封裝，基本操作的規格說明盡可能明確具體。
詳細設計的結果是對資料結構和基本操作做出進一步的求精，寫出資料儲存結構的型別定義，寫出函式形式的演算法框架；
4）程式編碼：把詳細設計的結果進一步求精為程式語言程式。同時加入一些註解和斷言，使程式中邏輯概念清楚；
5）程式除錯與測試：能夠熟練掌握除錯工具的各種功能，設計測試資料確保程式正確。除錯正確後，認真整理源程式及其注釋，形成格式和風格良好的源程式清單和結果；
6）結果分析：程式執行結果包括正確的輸入及其輸出結果和含有錯誤的輸入及其輸出結果。演算法的時間、空間複雜性分析；
7）編寫課程設計報告；
指導教師（簽字教研室主任（簽字
批准日期： 年月日
摘要 本次課程設計利用visual c++6.0程式設計軟體，運用c語言、指標、結構體、資料結構中棧的相關知識編寫了表示式求值演算法的程式。為了實現算符優先演算法使用兩個工作棧，乙個稱為optr，用以寄存運算子；另乙個稱做opnd，用以寄存運算元或運算結果。
依次讀入表示式，若是操作符即進opnd棧，若是運算子則和optr棧的棧頂運算子比較優先權後作相應的操作，直至整個表示式求值完畢，最終實現了任意表示式求值的簡單運算。
關鍵詞 ：指標;結構體;棧 目錄
1課題描述 1
2 設計要求 2
2.1設計具體要求 2
2.2總體規劃 2
3邏輯設計與分析 3
3.1舉例分析 3
3.2演算法核心 3
4 演算法流程圖 4
4.1 主演算法流程圖 4
4.2主要演算法流程** 5
5詳細設計 6
5.1順序棧的建立 6
5.2函式及對應程式 7
6程式測試 10
6.1合法資料輸入 10
6.2非法資料輸入 11
總結 12
查考文獻 13
隨著現代科學技術的迅猛發展，計算機技術已經滲透到各個領域，成為各行業必不可少的工具.借助現從識經濟時代的特點，對國民經濟建設提出了「用資訊化帶動工業化」的指導思想。對常用演算法的實現與比較操作校管而言，全面開發和應用計算機作業系統就是近期不能迴避的問題。
由於計算機技術的發展，許多複雜的數值問題才得以解決。乙個數學問題，乃至乙個數值計算公式，如何在計算機上實現，而在計算機處理計算的過程中又會產生哪些新問題，這是在實際應用演算法操作中經常會遇到的課題。
在計算機中，算術表示式由常量、變數、運算子和括號組成。由於不同的運算子具有不同的優先順序，又要考慮括號，因此，算術表示式的求值不可能嚴格地從左到右進行。因而在程式設計時，借助棧實現。
演算法輸入：乙個算術表示式，由常量、變數、運算子和括號組成（以字串形式輸入）。為簡化，規定運算元只能為正整數，操作符為+、-*、/，用#表示結束。
演算法輸出：表示式運算結果。演算法要點：
設定運算子棧和運算數棧輔助分析算符優先關係。在讀入表示式的字串行的同時，完成運算子和運算數的識別處理，以及相應運算。
開發工具： visual c++
運用c/c++、指標、結構體、資料結構中棧的相關知識編寫任意表示式求值演算法的實現。
主函式只要是表示式的輸入再通過呼叫evaluateexpression()函式進行運算數、運算子等相關處理，最後輸出結果。如圖2.1
圖2.1總體規劃圖
如下表3.1是對3*(7-2)的求值分析步驟。特別說明當在計算除法運算時如果分母為』0』,則出現錯誤提示。
表3.1 例子分析
為了實現算符優先演算法。可以使用兩個工作棧。乙個稱為optr，用以寄存運算子，另乙個稱做opnd，用以寄存運算元或運算結果。
（1） 首先置運算元棧為空棧，表示式起始符」#」為運算子棧的棧底元素；
（2） 依次讀入表示式，若是操作符即進opnd棧，若是運算子則和optr棧的棧頂運算子比較優先權後作相應的操作，直至整個表示式求值完畢（即optr棧的棧頂元素和當前讀入的字元均為」#」）。
如下圖4.1給出了主要演算法控制流程圖：
圖4.1主演算法流程圖
算術表示式求值的算符優先演算法。
設optr和opnd分別為運算子棧和運算數棧，opset為運算子集合。
sqstack optr; // 運算子棧，字元元素
sqstack opnd; // 運算數棧，實數元素
char tempdata[20];
float data,a,b;
char theta,c,x,dr[2];
initstack,char> (optr);
push (optr, '#');
initstack ,float>(opnd);
strcpy(tempdata,"\0");//將tempdata置為空
c=getchar();
while (cgettop,char>(optr)!= '#')
{if (!in(c, opset))
{dr[0]=c;
dr[1]='\0';//存放單個數
strcat(tempdata,dr);//將單個數連到tempdata中，形成字串
c=getchar();
if(in(c,opset))//如果遇到運算子，則將字串tempdata轉換成實數，入棧，
並重新置空
{data=(float)atof(tempdata);
實驗四算術表示式求值
源 include include include define plus 0 define minus 1 define power 2 define divide 3 define leftp 4 define righp 5 define startend 6 define digit 7 d...
表示式求值
課程設計報告 課程名稱資料結構 課題名稱表示式求值 專業電腦科學與技術 班級0901 學號 200903010102 姓名覃宇星 指導教師李珍輝鄧作傑郭芳 2011年7月7日 湖南工程學院 課程設計任務書 課程名稱 c語言程式設計 課題表示式求值 專業班級計算機0901 學生姓名 學號指導老師周鐵山...
資料結構算術表示式求值實驗報告
目錄1 前言 1 2 概要設計 1 2.1 資料結構設計 1 2.2 演算法設計 1 2.3 adt描述 2 2.4 功能模組分析 2 3 詳細設計 3 3.1 資料儲存結構設計 3 3.2主要演算法流程圖 或演算法偽 3 4 軟體測試 6 5 心得體會 8 參考文獻 8 附錄 8 在計算機中，算術...