《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告-多項(xiàng)式計(jì)算

1、<p>　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告</p><p>　姓名學(xué)號(hào)2009 級(jí)7組實(shí)驗(yàn)室：</p><p>　提交日期成績(jī)指導(dǎo)教師</p><p>　實(shí)驗(yàn)題目： 多項(xiàng)式計(jì)算器</p><p>　問題解析（對(duì)問題的分析、理解和解題方法）：我們先對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行了分析，對(duì)其運(yùn)算進(jìn)行了詳細(xì)的分解。我們把整個(gè)程序

2、我們分為6個(gè)部分加減法，乘法，除法，排序整理，多項(xiàng)式解析，輸入輸出的格式及用戶界面。一·1. 多元多項(xiàng)式加法：直接加，進(jìn)行排序整理。2. 多元多項(xiàng)式減法即加法的取反運(yùn)算。3. 如何進(jìn)行解析是一個(gè)難點(diǎn)，我們中序表達(dá)式轉(zhuǎn)后序表達(dá)式的方法進(jìn)行解析。二·多元多項(xiàng)式乘法是前一個(gè)多項(xiàng)式的每一項(xiàng)與后一項(xiàng)的每一項(xiàng)相乘相加，然后排序整理。5. 由于上述分析中提到對(duì)多項(xiàng)式進(jìn)行排序整理，則我們就要先寫一個(gè)sort()的函數(shù)，對(duì)多項(xiàng)式進(jìn)行排

3、序整理。其原理是按照其中一個(gè)字母的次數(shù)的降次排序，使用的是冒泡算法。三·6. 一元多項(xiàng)式除法即比較前一項(xiàng)與后一項(xiàng)的最高次數(shù),若被除數(shù)的最高次數(shù)大于等于除數(shù)的最高次數(shù),則被除數(shù)的用最高次項(xiàng)除以除數(shù)的最高次項(xiàng),得到一個(gè)臨時(shí)的商.再用被除數(shù)減去這個(gè)商乘以除數(shù)的積作為新的被除數(shù)。如此循環(huán)，就可以得到商。7. 一元多項(xiàng)式的模，模就是除法中最后的被除數(shù)。8. 對(duì)整個(gè)多項(xiàng)式進(jìn)行輸入輸出的界面比較容易設(shè)計(jì)，但是對(duì)多項(xiàng)式的輸出格式很難調(diào)試，有很

4、多情況（去符號(hào)，去0，指數(shù)是0的情況等等</p><p>　數(shù)據(jù)結(jié)構(gòu)選擇、算法設(shè)計(jì)：我們用java語言編輯程序，應(yīng)為它里面含有很多可以直接引用的的方法。多項(xiàng)式用List（線性表）存儲(chǔ)，其中每一個(gè)節(jié)點(diǎn)為一個(gè)單項(xiàng)式，單項(xiàng)式內(nèi)部有系數(shù)和指數(shù)，系數(shù)為一個(gè)double型數(shù)字，指數(shù)用一個(gè)TreeMap<String,Integer>（可排序映射表）表示，字符串存單項(xiàng)式的字母,對(duì)應(yīng)的值為該字母的指數(shù).多項(xiàng)式內(nèi)部封裝

5、了加減乘除模運(yùn)算和轉(zhuǎn)換為字符串，作為支持，又封裝了 getMaxExp（取最高次數(shù)），sort（排序整理，去0項(xiàng)），negate（取反）.這些計(jì)算需要用到單項(xiàng)式的計(jì)算，所以也對(duì)單項(xiàng)式封裝了多種方法。單項(xiàng)式封裝了add（加），multiple（乘）divide（除），compareTo（比較），remove0（去除指數(shù)為0的項(xiàng)），isNegative（判斷是否為負(fù)數(shù)項(xiàng)），轉(zhuǎn)換為字符串。另外還有解析運(yùn)算類，用于把字符串解析成多項(xiàng)式和運(yùn)算符，

6、然后通過多項(xiàng)式類進(jìn)行運(yùn)算，這樣的好處就是程序入口簡(jiǎn)單，降低耦合性，便于代碼復(fù)用.用戶界面單獨(dú)編寫，并通過解析運(yùn)算類進(jìn)行多項(xiàng)式處理，返回結(jié)果。用戶界面只有輸入框,輸出框和一個(gè)按鈕，用法簡(jiǎn)單，報(bào)錯(cuò)功能完善。中綴表達(dá)式轉(zhuǎn)后</p><p>　任務(wù)分工及進(jìn)度計(jì)劃：任務(wù)分工： 我的任務(wù)是解析字符串,按順序轉(zhuǎn)換成后綴表達(dá)式,并調(diào)用多項(xiàng)式的計(jì)算.以及編輯多項(xiàng)式的加法和減法運(yùn)算。進(jìn)度：我們?cè)?.24下午進(jìn)行分組，大家討論整個(gè)程序

7、的大體構(gòu)架，并且進(jìn)行任務(wù)的劃分。8.25白天在各自的程序完成后，進(jìn)行合并以及大量的調(diào)試，晚上把輸入輸出界面編輯出來了，并開始寫了各自的實(shí)驗(yàn)報(bào)告。8.26早上交付程序并提交實(shí)驗(yàn)報(bào)告。</p><p>　用戶手冊(cè)：1. 在用戶界面的第一行輸入你想要計(jì)算的多項(xiàng)式。2. 用戶要記住多元多項(xiàng)式只能計(jì)算加，減，乘法而不能進(jìn)行除法和模運(yùn)算；一元多項(xiàng)式可以進(jìn)行加，減，乘，除，模運(yùn)算。3. 輸入完畢后，請(qǐng)檢查多項(xiàng)式是否輸入錯(cuò)誤。4

8、. 檢查完畢后，請(qǐng)按“計(jì)算”按鈕，你會(huì)在下一行得出你想要運(yùn)算的多項(xiàng)式的結(jié)果。</p><p>　測(cè)試結(jié)果：一元多項(xiàng)式加法：一元多項(xiàng)式減法：一元多項(xiàng)式乘法：一元多項(xiàng)式除法：一元多項(xiàng)式模運(yùn)算：多元多項(xiàng)式加法：多元多項(xiàng)式減法：多元多項(xiàng)式乘法：</p><p>　程序清單：解析并計(jì)算:package polynomial;import java.util.ArrayList;import java

9、.util.HashSet;import java.util.List;import java.util.Set;import java.util.Stack;public class Eval{public Poly eval(String exp){List<Object> list = infixExpToPostExp(exp);// 轉(zhuǎn)化成后綴表達(dá)式return doEval(list);// 真正求值}// 查找

10、字母?jìng)€(gè)數(shù)（元數(shù)）public int countEle(String exp){Set<Character> ele = new HashSet<Character>();for (int i = 0; i < exp.length(); i++){if (Character.isLetter(exp.charAt(i)))ele.add(exp.charAt(i));}return ele.size();

11、}// 遇到操作符壓棧，遇</p><p>　總結(jié)（對(duì)所作程序進(jìn)行分析、評(píng)價(jià)運(yùn)行效果，總結(jié)遇到的問題和解決辦法）這次的收獲很大，明白了老師讓我們做這個(gè)程序的目的，合作，分工。在這次程序調(diào)試中,我們學(xué)會(huì)了很多調(diào)試技巧,提高了調(diào)試的效率,也加快了進(jìn)度.另外我們明白了一個(gè)好的代碼結(jié)構(gòu)體系能夠加快編寫速度以及調(diào)試速度,進(jìn)一步理解了重構(gòu)以及面向?qū)ο笏枷氲膬?yōu)點(diǎn)和技巧.首先在我們?cè)谧龀绦蛑?，?jīng)過商討，我們確定了整個(gè)程序的框架

12、，理清了步驟。我們使用了模塊化設(shè)計(jì)，對(duì)程序進(jìn)行了封裝，確定了幾個(gè)可以實(shí)現(xiàn)程序的類，用類之間的合理的調(diào)用實(shí)現(xiàn)了整個(gè)的算法。用封裝成類的方法，也提高了程序的復(fù)用性。在寫程序的過程中也遇到了很多的問題在編寫的時(shí)候很多變量寫錯(cuò),產(chǎn)生異常,死循環(huán),經(jīng)過不斷的調(diào)試才更改好.我們組里也有過爭(zhēng)論，為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)產(chǎn)生了爭(zhēng)議，但是通過討論，最終確定了一個(gè)合理的方案。對(duì)于多項(xiàng)式的加，減，乘，除取整，除取模運(yùn)算，其實(shí)有很多情況，實(shí)現(xiàn)起來有很大難度，比如，系數(shù)