數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--《十進(jìn)制表達(dá)式四則運(yùn)算》

1、<p><b>　　目 錄</b></p><p><b>　　前言1</b></p><p><b>　　正文1</b></p><p>　　2.1 課程設(shè)計(jì)的教學(xué)目的和任務(wù)1</p><p>　　2.2課程設(shè)計(jì)的主要內(nèi)容2</p><p

2、>　　2.3課程設(shè)計(jì)報(bào)告的要求2</p><p>　　2.4算法設(shè)計(jì)基本要求2</p><p>　　2.4.1算法設(shè)計(jì)主要內(nèi)容3</p><p>　　2.4.2算法設(shè)計(jì)的思想3</p><p>　　2.5 算法描述3</p><p>　　2.6 設(shè)計(jì)方案3</p><p>

3、　　2.7 設(shè)計(jì)內(nèi)容4</p><p>　　2.7.1需求分析4</p><p>　　2.7.2概要設(shè)計(jì)4</p><p>　　2.7.3 詳細(xì)設(shè)計(jì)5</p><p>　　2.7.4 調(diào)試分析與結(jié)果8</p><p>　　2.7.5 算法分析10</p><p><b>

4、　　課程總結(jié)11</b></p><p><b>　　參考文獻(xiàn)12</b></p><p><b>　　附錄13</b></p><p><b>　　前 言</b></p><p>　　簡(jiǎn)單的四則運(yùn)算對(duì)我們來(lái)說(shuō)很簡(jiǎn)單，但是當(dāng)你一直都在重復(fù)這個(gè)簡(jiǎn)單的腦力操作時(shí)，

5、也許你會(huì)疏忽，會(huì)不小心搞錯(cuò)，從而影響工作，比如說(shuō)會(huì)計(jì)等職業(yè)，所以我們就在考慮，當(dāng)今社會(huì)是信息時(shí)代，能否用計(jì)算機(jī)代替人類做這份工作呢？在數(shù)據(jù)結(jié)構(gòu)中，則能用棧實(shí)現(xiàn)簡(jiǎn)單四則運(yùn)算，為我們進(jìn)行計(jì)算，避免不必要的錯(cuò)誤。</p><p>　　棧（stack，又稱為堆棧）是一種特殊的線性表。棧（stack）是限定僅在表尾進(jìn)行插入或刪除操作的線性表，允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底

6、固定，而棧頂浮動(dòng)；棧中元素個(gè)數(shù)為零時(shí)稱為空棧。棧中的元素的進(jìn)出是按照“后進(jìn)先出”的原則進(jìn)行，根據(jù)棧的這種特征，因此棧又稱為后進(jìn)先出表（LIFO表—Last In First Out）。</p><p>　　由于棧的結(jié)構(gòu)具有后進(jìn)先出的固有特性，致使棧成為程序設(shè)計(jì)中的有用工具。運(yùn)用棧來(lái)實(shí)現(xiàn)表達(dá)式求值問(wèn)題也是程序設(shè)計(jì)語(yǔ)言編譯中的一個(gè)最基本的問(wèn)題。</p><p><b>　　正 文&l

7、t;/b></p><p>　　2.1 課程設(shè)計(jì)的教學(xué)目的和任務(wù)</p><p>　　本學(xué)期我們對(duì)《數(shù)據(jù)結(jié)構(gòu)》這門(mén)課程進(jìn)行了學(xué)習(xí)。這門(mén)課程是一門(mén)實(shí)踐性非常強(qiáng)的課程，為了讓大家更好地理解與運(yùn)用所學(xué)知識(shí)，提高動(dòng)手能力，我們進(jìn)行了此次課程設(shè)計(jì)實(shí)習(xí)。《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》是計(jì)算機(jī)專業(yè)集中實(shí)踐性環(huán)節(jié)之一，是學(xué)習(xí)完《數(shù)據(jù)結(jié)構(gòu)》課程后進(jìn)行的一次全面的綜合練習(xí)。這次課程設(shè)計(jì)不但要求學(xué)生掌握《數(shù)據(jù)結(jié)構(gòu)》

8、中的各方面知識(shí)，還要求學(xué)生具備一定的C語(yǔ)言基礎(chǔ)和編程能力。</p><p><b>　　其目的是：</b></p><p>　　(1) 使學(xué)生進(jìn)一步理解和掌握所學(xué)的各種數(shù)據(jù)類型的結(jié)構(gòu)和操作實(shí)現(xiàn)算法，以及它們?cè)诔绦蛑械氖褂梅椒ā?lt;/p><p>　　(2) 使學(xué)生初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、設(shè)計(jì)、編碼、測(cè)試等基本方法和基本技能。</p&

9、gt;<p>　　(3) 使學(xué)生掌握使用各種計(jì)算機(jī)資料和有關(guān)參考資料，提高學(xué)生進(jìn)行程序設(shè)計(jì)的基本能力。</p><p>　　(4) 使學(xué)生能用系統(tǒng)的觀點(diǎn)和軟件開(kāi)發(fā)一般規(guī)范進(jìn)行軟件開(kāi)發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。</p><p>　?。?）要達(dá)到理論與實(shí)際應(yīng)用相結(jié)合，使學(xué)生能夠根據(jù)數(shù)據(jù)對(duì)象的特性，學(xué)會(huì)數(shù)據(jù)組織的方法，能把現(xiàn)實(shí)世界中的實(shí)際問(wèn)題在計(jì)算機(jī)內(nèi)部表示出

10、來(lái)，并培養(yǎng)良好的程序設(shè)計(jì)技能。 </p><p>　?。?）在實(shí)踐中認(rèn)識(shí)為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，掌握數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)語(yǔ)言、程序設(shè)計(jì)技術(shù)之間的關(guān)系，是前面所學(xué)知識(shí)的綜合和回顧。</p><p>　　2.2課程設(shè)計(jì)的主要內(nèi)容</p><p>　　(1) 問(wèn)題分析和任務(wù)定義。</p><p>　　根據(jù)題目的要求，充分地分析問(wèn)題，明確要求。</

11、p><p>　　(2)在這個(gè)過(guò)程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡(jiǎn)單和易于調(diào)試，基本操作的規(guī)格說(shuō)明盡可能明確具體。</p><p><b>　　(3)程序編碼。</b></p><p>　　把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語(yǔ)言程序。同時(shí)加入一些注解和斷言，使程序中邏輯概念清楚。</p><p>　　(4)

12、 程序調(diào)試與測(cè)試。</p><p>　　能夠熟練掌握調(diào)試工具的各種功能，設(shè)計(jì)測(cè)試數(shù)據(jù)確定疑點(diǎn)，通過(guò)修改程序來(lái)證實(shí)它或繞過(guò)它。調(diào)試正確后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果。</p><p><b>　　(5) 結(jié)果分析。</b></p><p>　　程序運(yùn)行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。&

13、lt;/p><p><b>　　撰寫(xiě)課程設(shè)計(jì)報(bào)告。</b></p><p>　　2.3課程設(shè)計(jì)報(bào)告的要求</p><p>　　課程設(shè)計(jì)報(bào)告要求規(guī)范書(shū)寫(xiě)。應(yīng)當(dāng)包括如下內(nèi)容：</p><p>　?。?）問(wèn)題描述：描述要求編程解決的問(wèn)題。</p><p>　　（2）基本要求：給出程序要達(dá)到的具體的要求。&l

14、t;/p><p>　?。?） 算法思想：描述解決相應(yīng)問(wèn)題算法的設(shè)計(jì)思想。</p><p>　　（4）源程序：給出所有源程序清單，要求程序有充分的注釋語(yǔ)句，至少要注釋每個(gè)函數(shù)參數(shù)的含義和函數(shù)返回值的含義。</p><p>　?。?）測(cè)試情況：給出程序的測(cè)試情況，并分析運(yùn)行結(jié)果。</p><p>　?。?）參考文獻(xiàn)：列出參考的相關(guān)資料和書(shū)籍。<

15、/p><p>　　本課程設(shè)計(jì)以字符序列的形式從鍵盤(pán)輸入語(yǔ)法正確的、不含變量的整數(shù)（或?qū)崝?shù)）表達(dá)式，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值。當(dāng)用戶輸入一個(gè)合法的算術(shù)表達(dá)式后，能夠返回正確的結(jié)果。能夠計(jì)算的運(yùn)算符包括：加、減、乘、除、括號(hào)，對(duì)于異常表達(dá)式能給出錯(cuò)誤提示。</p><p>　　2.4算法設(shè)計(jì)基本要求</p><p>　　掌握棧和隊(duì)列的定義、特性；</p>

16、;<p>　　熟練掌握棧的順序表示、鏈表表示以及相應(yīng)操作的實(shí)現(xiàn)；</p><p>　　（3） 掌握棧的基本運(yùn)算，并能正確應(yīng)用它們解決實(shí)際問(wèn)題；</p><p>　　2.4.1算法設(shè)計(jì)主要內(nèi)容</p><p>　　算術(shù)表達(dá)式由操作數(shù)、運(yùn)算符和界限符組成。操作數(shù)是正整數(shù)，運(yùn)算符為加減乘除，界限符有左右括號(hào)和表達(dá)式起始。</p><p&

17、gt;　　2.4.2算法設(shè)計(jì)的思想</p><p>　　已知輸入一個(gè)中綴表達(dá)式，利用棧（這里用棧的順序存儲(chǔ)結(jié)構(gòu)）的后進(jìn)先出性，將一個(gè)中綴表達(dá)式轉(zhuǎn)換成一個(gè)后綴表達(dá)式，然后同樣利用棧的后進(jìn)先出性，由后綴表達(dá)式求出這個(gè)表達(dá)式的值，并輸出。</p><p><b>　　2.5 算法描述</b></p><p>　　main ( ) （主函數(shù)）<

18、/p><p>　　在主函數(shù)中建兩個(gè)工作棧。一個(gè)稱為OPTR，用以寄存運(yùn)算符；另一個(gè)稱作OPND，用以寄存操作數(shù)或運(yùn)算結(jié)果。</p><p>　　首先置操作數(shù)棧為空棧，表達(dá)式起始符“#”為運(yùn)算符棧的棧底元素；</p><p>　　一次讀入表達(dá)式中的每一個(gè)字符，若是操作數(shù)則進(jìn)OPND棧，若是運(yùn)算符則和OPRT棧的棧頂運(yùn)算符比較優(yōu)先權(quán)后作相應(yīng)的操作，直至整個(gè)表達(dá)式求值完畢（即

19、OPRT棧的棧頂元素和當(dāng)前輸入的字符均為“#”）。</p><p><b>　　2.6設(shè)計(jì)方案</b></p><p>　　任何一個(gè)表達(dá)式都是由操作符，運(yùn)算符組成的。我們分別用順序棧來(lái)寄存表達(dá)式的操作數(shù)和運(yùn)算符。棧是限定于緊僅在表尾進(jìn)行插入或刪除操作的線性表。順序棧的存儲(chǔ)結(jié)構(gòu)是利用一組連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。</p><p&g

20、t;　　為了實(shí)現(xiàn)算符優(yōu)先算法?？梢允褂脙蓚€(gè)棧。一個(gè)稱為OPF，用以寄存運(yùn)算符，另一個(gè)稱做OPS，用以寄存操作數(shù)或運(yùn)算結(jié)果。</p><p>　　1.首先置操作數(shù)棧為空棧，表達(dá)式起始符”#”為運(yùn)算符棧的棧底元素；</p><p>　　2.依次讀入表達(dá)式，若是操作符即進(jìn)OPS棧，若是運(yùn)算符則和OPF棧的棧頂運(yùn)算符比較優(yōu)先權(quán)后作相應(yīng)的操作，直至整個(gè)表達(dá)式求值完畢（即OPF棧的棧頂元素和當(dāng)前讀入的

21、字符均為”#”）。</p><p><b>　　2.7設(shè)計(jì)內(nèi)容</b></p><p>　　2.7.1．需求分析</p><p>　　本程序所做的工作為：能直接求出四則表達(dá)式的值，并輸出；本程序可用于小學(xué)教師對(duì)學(xué)生作業(yè)的快速批改以及對(duì)數(shù)值位數(shù)要求較大的科學(xué)運(yùn)算。</p><p>　　2.7.2．概要設(shè)計(jì)</p>

22、;<p>　　a.//用于存儲(chǔ)操作數(shù)和運(yùn)算結(jié)果（OPS）:</p><p>　　ADT LinkStack{</p><p>　　數(shù)據(jù)元素：此鏈棧中的所有元素類型為字符型的數(shù)字字符</p><p>　　數(shù)據(jù)關(guān)系：棧中數(shù)據(jù)元素之間是線性關(guān)系。</p><p><b>　　基本操作:</b></p>

23、<p>　?。?）InitStack(LinkStack &head)</p><p>　　操作結(jié)果：構(gòu)造一個(gè)空棧head</p><p>　?。?）IsEmpty(LinkStack head)</p><p>　　初始條件：棧head已存在</p><p>　　操作結(jié)果：若棧為空棧，則返回TRUE,否則FALSE&l

24、t;/p><p>　　（3）Push(LinkStack &head,ElementType element)</p><p>　　初始條件：棧head已存在</p><p>　　操作結(jié)果：插入元素element為新的棧頂元素</p><p>　?。?）Pop(LinkStack &head,ElementType &el

25、ement)</p><p>　　初始條件：棧head已存在且非空</p><p>　　操作結(jié)果：刪除head的棧頂元素，并用e返回其值</p><p>　?。?）GetTop(LinkStack head, ElementType &element)</p><p>　　初始條件：棧head已存在并且非空</p>&l

26、t;p>　　操作結(jié)果：用e返回head的棧頂元素</p><p>　?。?）DestroyStack(LinkStack &head)</p><p>　　初始條件：棧head已存在</p><p>　　操作結(jié)果：棧head 被銷毀</p><p>　　}ADT LinkStack</p><p>　　b

27、．//用于存儲(chǔ)運(yùn)算符(OPF)：</p><p>　　ADT LinkCharStack{</p><p>　　數(shù)據(jù)對(duì)象D：元素類型為字符型的符號(hào)字符</p><p><b>　　數(shù)據(jù)關(guān)系R：</b></p><p>　　基本操作：棧中數(shù)據(jù)元素之間是線性關(guān)系。</p><p>　?。?）CInit

28、Stack(LinkCharStack &head) </p><p>　　操作結(jié)果：構(gòu)造一個(gè)空棧head</p><p>　　（2）CIsEmpty(LinkCharStack head)</p><p>　　初始條件：棧head已存在</p><p>　　操作結(jié)果：若棧為空棧，則返回TRUE,否則FALSE</p>

29、<p>　?。?）CPush(LinkCharStack &head,ElementType element)</p><p>　　初始條件：棧head已存在</p><p>　　操作結(jié)果：插入元素element為新的棧頂元素</p><p>　　（4）CPop(LinkCharStack &head,ElementType &el

30、ement)</p><p>　　初始條件：棧head已存在且非空</p><p>　　操作結(jié)果：刪除head的棧頂元素，并用e返回其值</p><p>　?。?）CGetTop(LinkCharStack head, ElementType &element)</p><p>　　初始條件：棧head已存在并且非空</p>

31、;<p>　　操作結(jié)果：用e返回head的棧頂元素</p><p>　　（6）CDestroyStack(LinkCharStack &head)</p><p>　　初始條件：棧head已存在</p><p>　　操作結(jié)果：棧head 被銷毀</p><p>　　}ADT LinkCharStack</p>

32、<p>　　c.系統(tǒng)中子程序及功能要求：</p><p>　　if(!In(c[i]))：判斷讀入的字符不是運(yùn)算符 是則進(jìn)棧；</p><p>　　char Proceed(char op,char c)： op為棧頂元素，c為當(dāng)前讀入的運(yùn)算符,比較二者的優(yōu)先級(jí)；</p><p>　　int EvalExpres(void)：表達(dá)式求解函數(shù)</

33、p><p>　　ElementType EvaluateExpression(char *exp)：這是此程序的核心函數(shù)，可以綜合其它子函數(shù)，實(shí)現(xiàn)最終的表達(dá)式求解。</p><p>　　各程序模塊之間的調(diào)用關(guān)系（子程序編號(hào)見(jiàn)上）：</p><p>　　主函數(shù)可調(diào)用子程序5，6，7。</p><p>　　子程序7可調(diào)用子程序1，2，3，4。 <

34、;/p><p>　　2.7.3 詳細(xì)設(shè)計(jì)</p><p><b>　　此算法的基本思想：</b></p><p>　　首先置操作數(shù)棧OPS為空棧，表達(dá)式起始符“#”為運(yùn)算符的棧底元素；依次讀入表達(dá)式中每個(gè)字符，若是操作數(shù)則進(jìn)棧，若是運(yùn)算符則和OPF棧的棧頂運(yùn)算符比較優(yōu)先權(quán)作相應(yīng)操作，直至整個(gè)表達(dá)式求值完畢（即OPF棧的棧頂元素和當(dāng)前讀入的字符均為“

35、#”）</p><p><b>　　此算法的偽代碼：</b></p><p>　　ElementType EvaluateExpression(char *exp)</p><p>　　{ 定義兩個(gè)字符變量c和ch,c代表輸入表達(dá)式中的字符，ch代表?xiàng)ｍ斶\(yùn)算符;</p><p>　　定義字符指針 *p,*q,*temp

36、;temp指向運(yùn)算符后面的一個(gè)字符</p><p>　　double i=0,a=0,b=0;</p><p>　　將傳入的實(shí)參賦給p,q;</p><p>　　定義一個(gè)運(yùn)算符棧 OPF;</p><p>　　定義一個(gè)操作數(shù)棧 OPS;</p><p>　　調(diào)用函數(shù)InitStack()初始化棧OPS; </p&

37、gt;<p>　　調(diào)用函數(shù)CInitCharStack()初始化棧OPF;</p><p>　　調(diào)用函數(shù)CPush(OPF,'#')將#壓入運(yùn)算符棧;</p><p>　　c=*p;temp=p;p++;</p><p>　　if(第一個(gè)字符就為‘-’)</p><p><b>　　{</b>

38、;</p><p>　　c=*p;temp=p;p++;</p><p><b>　　}</b></p><p>　　while(棧不為空或表達(dá)式?jīng)]有結(jié)束)</p><p>　　{//進(jìn)入最外層循環(huán)</p><p>　　if(不是運(yùn)算符)//則解析數(shù)字字符串然后進(jìn)操作數(shù)棧</p>&

39、lt;p><b>　　{</b></p><p><b>　　整數(shù)部分m=0;</b></p><p><b>　　小數(shù)部分n=0;</b></p><p>　　while(沒(méi)有遇到小數(shù)點(diǎn)并且為數(shù)字字符)</p><p>　　{ 解析整數(shù)部分m }</p>

40、<p><b>　　if(遇到小數(shù)點(diǎn))</b></p><p><b>　　{ 解析小數(shù)部分</b></p><p><b>　　c=*p;</b></p><p>　　將p指針移到第一個(gè)出現(xiàn)的字符;</p><p>　　將q指針指向小數(shù)的最后一位;</p

41、><p>　　while(p指針不指向’.’)</p><p><b>　　{</b></p><p>　　將p指向的字符轉(zhuǎn)為小數(shù)n</p><p><b>　　p--;</b></p><p><b>　　}</b></p><p>

42、;<b>　　p=q;</b></p><p><b>　　p++;</b></p><p><b>　　}</b></p><p>　　if(運(yùn)算符為‘-’并且運(yùn)算符前一個(gè)為‘（’或者為表達(dá)式的開(kāi)始)</p><p>　　調(diào)用Push(OPS,-(m+n))將m+n的相反

43、數(shù)入棧;</p><p><b>　　else </b></p><p>　　調(diào)用Push(OPS,m+n)將m+n入棧;</p><p><b>　　}數(shù)字進(jìn)棧結(jié)束</b></p><p>　　else//是運(yùn)算符時(shí)則進(jìn)棧OPF</p><p>　　{ if(運(yùn)算符為‘-’

44、&&運(yùn)算符前一個(gè)為‘（’)</p><p><b>　　{ c=*p;</b></p><p><b>　　temp=p;</b></p><p><b>　　p++;</b></p><p><b>　　}</b></p>

45、<p><b>　　else</b></p><p>　　{ 調(diào)用函數(shù)CGetTop(OP,ch)得到OPF的棧頂元素;</p><p>　　switch(調(diào)用函數(shù)Precede(ch,c)判斷棧頂元素與接收的字符的優(yōu)生級(jí)別)</p><p><b>　　{</b></p><p>　　

46、case 棧頂運(yùn)算符優(yōu)先權(quán)低:</p><p>　　調(diào)用函數(shù)CPush(OPF,c)將c入運(yùn)算符棧;</p><p><b>　　接收下一個(gè)字符;</b></p><p>　　case 棧頂運(yùn)算符優(yōu)先權(quán)高：</p><p>　　運(yùn)算符出棧得到ch;</p><p>　　數(shù)字棧連續(xù)出棧兩次得到a,b

47、 ;</p><p>　　調(diào)用Operate(a,ch,b)并將結(jié)果入棧到數(shù)字棧;break;</p><p>　　case 優(yōu)生權(quán)相等：脫括號(hào)并接收下一個(gè)字符;</p><p>　　調(diào)用CPop(OPF,ch)脫括號(hào);接收下一個(gè)字符;</p><p>　　default:接收下一個(gè)字符;</p><p>　　}退出s

48、witch循環(huán)</p><p><b>　　}//else1</b></p><p><b>　　}//else2</b></p><p>　　}//退出最外層while循環(huán)</p><p>　　調(diào)用函數(shù)GetTop(OPS,i)得到棧頂元素i;</p><p><b&

49、gt;　　將兩個(gè)棧消毀;</b></p><p>　　}EvaluateExpression函數(shù)結(jié)束</p><p>　　利用該算法對(duì)算術(shù)表達(dá)式3*(7-2)求值操作過(guò)程如下：</p><p><b>　　表一</b></p><p>　　2.7.4 調(diào)試分析與結(jié)果</p><p>

50、<b>　　測(cè)試數(shù)據(jù)</b></p><p>　　第一組表達(dá)式測(cè)試結(jié)果：</p><p>　　圖1 12+（9-8）*7-（6*5）表達(dá)式運(yùn)算結(jié)果</p><p>　　上示結(jié)果說(shuō)明該程序能計(jì)算個(gè)位數(shù)組成的表達(dá)式。</p><p>　　第二組表達(dá)式的測(cè)試結(jié)果：</p><p>　　圖2 表達(dá)式3*

51、（67-65）+3表達(dá)式的運(yùn)行結(jié)果</p><p>　　上示結(jié)果說(shuō)明該程序能正常運(yùn)行計(jì)算兩位數(shù)組成的表達(dá)式。</p><p>　　第三組表達(dá)式的測(cè)試結(jié)果：</p><p>　　圖3 表達(dá)式4-{2*[10/(2+3)]}的運(yùn)行結(jié)果</p><p>　　上示結(jié)果說(shuō)明本程序?qū)τ卸鄬?duì)括號(hào)的表達(dá)式仍能正常運(yùn)行。</p><p&g

52、t;　　第四組表達(dá)式的測(cè)試結(jié)果：</p><p>　　圖4 錯(cuò)誤表達(dá)式12-（（（3-6*7）+8）-4的測(cè)試結(jié)果</p><p>　　上示結(jié)果表明當(dāng)我們輸入第五組錯(cuò)誤的表達(dá)式時(shí)，程序能做出正確判斷，提醒用戶輸入的表達(dá)式錯(cuò)誤。</p><p>　　2.7.5 算法分析</p><p>　　該算法的時(shí)間復(fù)雜度為O（n）</p>

53、<p>　　本算法有運(yùn)行效率高優(yōu)點(diǎn)，缺點(diǎn)就是需要建兩個(gè)棧，所需空間較大。</p><p><b>　　課程總結(jié)</b></p><p>　　轉(zhuǎn)眼，為期兩周的《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)實(shí)習(xí)即將結(jié)束了。在這次實(shí)習(xí)中，自己的C語(yǔ)言知識(shí)和數(shù)據(jù)結(jié)構(gòu)知識(shí)得到了鞏固，編程能力也有了一定的提高。同時(shí)也學(xué)會(huì)了解決問(wèn)題的方法?？偨Y(jié)起來(lái)，自己主要有以下幾點(diǎn)體會(huì)：</p>

54、<p>　　1.必須牢固掌握基礎(chǔ)知識(shí)。由于C語(yǔ)言是大一所學(xué)知識(shí)，有所遺忘，且未掌握好這學(xué)期所學(xué)的《數(shù)據(jù)結(jié)構(gòu)》這門(mén)課，所以在實(shí)習(xí)之初感到棘手。不知如何下手，但在后來(lái)的實(shí)習(xí)過(guò)程中自己通過(guò)看書(shū)和課外資料，并請(qǐng)教其他同學(xué)，慢慢地對(duì)C語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)知識(shí)有所熟悉。這時(shí)才逐漸有了思路。所以，這次實(shí)習(xí)之后，我告誡自己：今后一定要牢固掌握好專業(yè)基礎(chǔ)知識(shí)。</p><p>　　2.必須培養(yǎng)嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度。自己在編程時(shí)經(jīng)常因

55、為一些類似于“少了分號(hào)”的小錯(cuò)誤而導(dǎo)致錯(cuò)誤，不夠認(rèn)真細(xì)致，這給自己帶來(lái)了許多麻煩。編程是一件十分嚴(yán)謹(jǐn)?shù)氖虑?，容不得馬虎。所以在今后自己一定要培養(yǎng)嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度。我想這不僅是對(duì)于程序設(shè)計(jì)，做任何事都應(yīng)如此。</p><p>　　3.這次課程設(shè)計(jì)也讓我充分認(rèn)識(shí)到《數(shù)據(jù)結(jié)構(gòu)》這門(mén)課的重要性。它給我們一個(gè)思想和大綱，讓我們?cè)诰幊虝r(shí)容易找到思路，不至于無(wú)章可循。同時(shí)它也有廣泛的實(shí)際應(yīng)用。</p><p&

56、gt;　　總之，在這次實(shí)習(xí)中，自己的C語(yǔ)言以及數(shù)據(jù)結(jié)構(gòu)知識(shí)得到提高，編程能力也得到了提高。</p><p><b>　　參考文獻(xiàn)：</b></p><p>　　[1]譚浩強(qiáng)編著.C++課程設(shè)計(jì).北京：清華大學(xué)社，2004</p><p>　　[2]S.B.Lippman，J.Lajoie著.潘愛(ài)民譯.C++Primer（3rd Edition）

57、中文版.北京：中國(guó)電力出版社，2002</p><p>　　[3]H.M.Deitel，Paul James Deitel著.薛萬(wàn)鵬譯.C++程序設(shè)計(jì)教程.北京：機(jī)械工業(yè)出版社，2000</p><p>　　[4]Stephen R.Savis著.C++ For Dummies 4th edition，IDG Books Worldwide，Inc.，2002</p><

58、;p>　　[5]Harvey M.Deitel .Jack W.Davidson著.邱仲潘譯.C++大學(xué)教程（第二版）.北京：電子工業(yè)出版社，2002</p><p>　　[6]James P.Cohoon.Jack W.Davidson著.劉瑞挺等譯.C++程序設(shè)計(jì)（第三版）.北京：電子工業(yè)出版社</p><p>　　[7]Decoder編著.C/C++程序設(shè)計(jì).北京：中國(guó)鐵道出版

59、社，2002</p><p>　　[8]Brian Overland著.董梁等譯.C++語(yǔ)言命令譯解（第二版）.北京：機(jī)械工業(yè)出版社，2002</p><p>　　[9] H.M.Deitel，Paul James Deitel著.薛萬(wàn)鵬譯.C/C++程序設(shè)計(jì)大全.北京：機(jī)械工業(yè)出版社.1997</p><p>　　[10]Al Strevens,Clayton W

60、alnum著.林麗閩等譯.標(biāo)準(zhǔn)C++寶典.北京：電子工業(yè)出版社.2001</p><p>　　[11]Michael J.Young著.Mastering Visual C++6.0 Sybex Inc.1999</p><p>　　[12]Leen Ammeraal著.劉瑞挺等譯.C++程序設(shè)計(jì)教程（第三版）.北京：zhongguo 鐵道出版社，2003</p><p

61、>　　[13] 呂鳳翥著. C++語(yǔ)言程序設(shè)計(jì).北方交通大學(xué)出版社，2003</p><p>　　[14] 袁啟昌著.C++語(yǔ)言程序設(shè)計(jì).清華大學(xué)出版社，2004</p><p>　　[15] 劉振安，劉燕君，孫忱C++語(yǔ)言課程設(shè)計(jì).機(jī)械工業(yè)出版社，2007</p><p>　　[16] 楊進(jìn)才，沈顯君，劉蓉編.C++語(yǔ)言程序設(shè)計(jì)教程.清華大學(xué)出版社，2006

62、</p><p>　　[17] 宋振會(huì)著. C++語(yǔ)言編程基礎(chǔ)教程.清華大學(xué)出版社，2005</p><p><b>　　附錄：</b></p><p><b>　　源代碼：</b></p><p>　　#include <stdio.h></p><p>　　#

63、define MAXSIZE 16</p><p>　　typedef struct{</p><p>　　int data[MAXSIZE];</p><p><b>　　int top;</b></p><p><b>　　int base;</b></p><p&g

64、t;　　}seqstack; /* 順序棧的定義*/</p><p>　　/*以下為函數(shù)聲明*/</p><p>　　void InitStack(seqstack *); </p><p>　　int Empty(seqstack *);</p><p>　　void Push(seqstack *, int );&

65、lt;/p><p>　　int Pop(seqstack *);</p><p>　　int GetTop(seqstack *);</p><p>　　int Operate(int ,char ,int );</p><p>　　char Proceed(char ,char );</p><p>　　int

66、 In(char );</p><p>　　int EvalExpres(void);</p><p>　　/* 定義兩個(gè)棧分別存放運(yùn)算符和操作數(shù)*/</p><p>　　seqstack StackR,StackD; </p><p><b>　　/*主函數(shù)*/</b></p><p>　　i

67、nt main()</p><p><b>　　{</b></p><p><b>　　int v;</b></p><p><b>　　char ch;</b></p><p><b>　　while(1)</b></p><p>

68、;<b>　　{</b></p><p>　　printf("\t本程序的功能為：用順序棧實(shí)現(xiàn)整型算術(shù)表達(dá)式的求值\n");</p><p>　　v = EvalExpres(); </p><p>　　printf("The result is:%d",v);</p><

69、;p>　　/*以下為程序控制*/ </p><p>　　printf("\nInput 'q' to quit and ENTER run again:"); </p><p><b>　　do{ </b></p><p>　　scanf("%c",&ch);

70、 </p><p>　　if(ch == 'q' || ch == 'Q')</p><p><b>　　exit(0);</b></p><p>　　}while(ch!='\n');</p><p>　　system("cls"); <

71、/p><p><b>　　}</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　void InitStack(seqstack *s)</p><p>　　{ s->t

72、op = 0;</p><p>　　s->base = 0;</p><p>　　} /* 初始化棧*/</p><p>　　int Empty(seqstack *s)</p><p>　　{ if(s->top == s->base)</p><p><b>　　return

73、 1;</b></p><p><b>　　else</b></p><p><b>　　return 0;</b></p><p>　　} /* 判斷棧是否為空*/</p><p>　　void Push(seqstack *s, int x)</p><p&

74、gt;<b>　　{ </b></p><p>　　if(s->top == MAXSIZE)</p><p>　　{ printf("OVER FLOW!\n");</p><p><b>　　exit(0);</b></p><p><b>　　}&

75、lt;/b></p><p><b>　　else</b></p><p>　　{ s->data[s->top] = x;</p><p><b>　　s->top++;</b></p><p><b>　　} </b></p>

76、<p>　　} /* 進(jìn)棧 */</p><p>　　int Pop(seqstack *s)</p><p>　　{ int e;</p><p>　　if(Empty(s))</p><p>　　{ printf("Under flow!\n");</p><p&g

77、t;<b>　　return 0;</b></p><p>　　} /* 下溢*/</p><p><b>　　else </b></p><p>　　{ s->top--;</p><p>　　e = s->data[s->top];</p><p&

78、gt;<b>　　return e;</b></p><p><b>　　}</b></p><p>　　} /* 出棧*/</p><p>　　int GetTop(seqstack *s) /*取棧頂元素*/</p><p><b>　　{ </b></p

79、><p>　　if(Empty(s))</p><p>　　{ printf("Under flow!\n");</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　else

80、</b></p><p>　　return s->data[s->top-1]; </p><p><b>　　}</b></p><p>　　int EvalExpres(void) /* 表達(dá)式求解函數(shù)*/</p><p><b>　　{</b></

81、p><p>　　int a,b,i=0,s=0;</p><p>　　char c[80],r;</p><p>　　InitStack(&StackR);</p><p>　　Push(&StackR,'#');</p><p>　　InitStack(&StackD);</

82、p><p>　　printf(" 請(qǐng)輸入表達(dá)式并以‘#’結(jié)束：");</p><p><b>　　gets(c);</b></p><p>　　while(c[i]!='#' || GetTop(&StackR)!='#')</p><p><b>　　{

83、 </b></p><p>　　if(!In(c[i])) /* 判斷讀入的字符不是運(yùn)算符 是則進(jìn)棧*/</p><p>　　{ if(c[i] >= '0' && c[i] <= '9')</p><p><b>　　{</b></p><

84、;p>　　s += c[i]-'0'; </p><p>　　while(!In(c[++i])) /*此處實(shí)現(xiàn)的功能為當(dāng)輸入的數(shù)字為多位數(shù)時(shí)*/</p><p><b>　　{ s*=10;</b></p><p>　　s += c[i]-'0';</p><p>

85、<b>　　}</b></p><p>　　Push(&StackD,s+'0'); </p><p><b>　　s = 0;</b></p><p><b>　　}</b></p><p><b>　　else </b><

86、/p><p><b>　　{</b></p><p>　　printf("你輸入的表達(dá)式有誤!\n");</p><p>　　return 0; </p><p>　　} </p><p><b>　　} </b></p>&

87、lt;p>　　else </p><p>　　switch(Proceed(GetTop(&StackR),c[i])) /* 此函數(shù)用來(lái)比較讀取的運(yùn)算符和棧頂運(yùn)算符的優(yōu)先級(jí)*/</p><p><b>　　{</b></p><p>　　case '<': /* 棧頂?shù)脑貎?yōu)先級(jí)高*/&

88、lt;/p><p>　　Push(&StackR,c[i]);</p><p><b>　　i++;</b></p><p><b>　　break;</b></p><p>　　case '=': /* 遇到匹配的小括號(hào)時(shí)則去掉他*/</p><p>

89、;　　Pop(&StackR);</p><p><b>　　i++;</b></p><p><b>　　break;</b></p><p>　　case '>': /* 棧頂?shù)膬?yōu)先級(jí)低則出棧并將結(jié)果寫(xiě)入棧內(nèi)*/</p><p>　　r = Pop(&St

90、ackR);</p><p>　　a = Pop(&StackD)-'0';</p><p>　　b = Pop(&StackD)-'0';</p><p>　　Push(&StackD,Operate(a,r,b)) ;</p><p>　　break; &

91、lt;/p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　return (GetTop(&StackD)-'0'); /* 返回運(yùn)算結(jié)果*/</p><p><b>　　}</b></p>&

92、lt;p>　　int In(char c) /*問(wèn)題2：解決In函數(shù)問(wèn)題:判斷C是否為運(yùn)算符是返回1否則返回0*/</p><p><b>　　{</b></p><p>　　char ch[7]={'+','-','*','/','#','(',&

93、#39;)'};</p><p><b>　　int i;</b></p><p>　　for(i = 0; i < 7; i++)</p><p>　　if(c == ch[i])</p><p><b>　　return 1;</b></p><p>　　r

94、eturn 0; </p><p><b>　　}</b></p><p>　　char Proceed(char op,char c) /*op為棧頂元素，c為當(dāng)前讀入的運(yùn)算符,比較二者的優(yōu)先級(jí)*/</p><p>　　{

95、 /*問(wèn)題1：解決Proceed函數(shù)*/</p><p>　　char ch; </p><p>　　if(op=='(' && c==')' || op=='#' && c=='#' )</p><p><b>　　ch = '

96、;=';</b></p><p><b>　　else</b></p><p>　　if(op=='+' || op=='-') /*棧頂元素為‘+’或‘-’的時(shí)候*/</p><p><b>　　switch(c)</b></p><p>

97、;<b>　　{</b></p><p><b>　　case '+':</b></p><p><b>　　case '-':</b></p><p><b>　　case ')':</b></p><p>

98、;　　case '#': ch = '>'; break;</p><p><b>　　case '*':</b></p><p><b>　　case '/':</b></p><p>　　case '(': ch = '&

99、lt;';</p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　if(op=='*' || op=='/') /*棧頂元素為‘*’或‘/’的時(shí)候*/</p><p><b>　　switch

100、(c)</b></p><p><b>　　{</b></p><p><b>　　case '+':</b></p><p><b>　　case '-':</b></p><p><b>　　case '*

101、9;:</b></p><p>　　case '/': </p><p><b>　　case ')':</b></p><p>　　case '#': ch = '>'; break;</p><p>　　case '

102、(': ch = '<'; </p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　if(op=='(') /*棧頂元素為‘(’的時(shí)候*/</p><p><b>

103、;　　switch(c)</b></p><p><b>　　{</b></p><p><b>　　case '+':</b></p><p><b>　　case '-':</b></p><p><b>　　case

104、'*':</b></p><p><b>　　case '/':</b></p><p>　　case '(': ch = '<'; break; </p><p>　　case '#': printf("Error!\n"

105、;); exit(0);</p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　if(op==')') /*棧頂元素為‘)’的時(shí)候*/</p><p><b>　　switch(c)</b></

106、p><p><b>　　{</b></p><p><b>　　case '+':</b></p><p><b>　　case '-':</b></p><p><b>　　case '*':</b></

107、p><p><b>　　case '/':</b></p><p>　　case '#': ch = '>'; break; </p><p>　　case '(': printf("Error!\n"); exit(0);</p><

108、;p><b>　　}</b></p><p><b>　　else</b></p><p>　　if(op=='#') /*棧頂元素為‘#’的時(shí)候*/</p><p><b>　　switch(c)</b></p><p><

109、;b>　　{</b></p><p><b>　　case '+':</b></p><p><b>　　case '-':</b></p><p><b>　　case '*':</b></p><p><

110、;b>　　case '/':</b></p><p>　　case '(': ch = '<'; break; </p><p>　　case ')': printf("Error!\n"); exit(0);</p><p><b>　　}

111、</b></p><p>　　return ch; </p><p>　　} </p><p>　　/* 問(wèn)題3：解決Operate函數(shù)*/</p><p>　　int Operate(int a,char r,int b) /*返回由aRb的值

112、 */</p><p><b>　　{ </b></p><p><b>　　int s;</b></p><p>　　int d1 = a;</p><p>　　int d2 = b; /*把字符ab變?yōu)閷?duì)應(yīng)數(shù)字*/</p><p><b>　　switch(r

113、)</b></p><p><b>　　{</b></p><p>　　case '+': s = d1+d2; break;</p><p>　　case '-': s = d2-d1; break;</p><p>　　case '*': s = d1