《數(shù)據(jù)結構》課程設計報告-多項式計算

1、<p>　《數(shù)據(jù)結構》課程設計報告</p><p>　姓名學號2009 級7組實驗室：</p><p>　提交日期成績指導教師</p><p>　實驗題目： 多項式計算器</p><p>　問題解析（對問題的分析、理解和解題方法）：我們先對數(shù)據(jù)結構進行了分析，對其運算進行了詳細的分解。我們把整個程序

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

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

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

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

6、然后通過多項式類進行運算，這樣的好處就是程序入口簡單，降低耦合性，便于代碼復用.用戶界面單獨編寫，并通過解析運算類進行多項式處理，返回結果。用戶界面只有輸入框,輸出框和一個按鈕，用法簡單，報錯功能完善。中綴表達式轉后</p><p>　任務分工及進度計劃：任務分工： 我的任務是解析字符串,按順序轉換成后綴表達式,并調用多項式的計算.以及編輯多項式的加法和減法運算。進度：我們在8.24下午進行分組，大家討論整個程序

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

8、. 檢查完畢后，請按“計算”按鈕，你會在下一行得出你想要運算的多項式的結果。</p><p>　測試結果：一元多項式加法：一元多項式減法：一元多項式乘法：一元多項式除法：一元多項式模運算：多元多項式加法：多元多項式減法：多元多項式乘法：</p><p>　程序清單：解析并計算: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);// 轉化成后綴表達式return doEval(list);// 真正求值}// 查找

10、字母個數(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>　總結（對所作程序進行分析、評價運行效果，總結遇到的問題和解決辦法）這次的收獲很大，明白了老師讓我們做這個程序的目的，合作，分工。在這次程序調試中,我們學會了很多調試技巧,提高了調試的效率,也加快了進度.另外我們明白了一個好的代碼結構體系能夠加快編寫速度以及調試速度,進一步理解了重構以及面向對象思想的優(yōu)點和技巧.首先在我們在做程序之前，經過商討，我們確定了整個程序的框架

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