“?本文主要討論線性表在多項式計算中的應用，討論內容涉及到一元n次多項式在計算機中的表示，及多項式相加運算。”

01

在數學上，一個一元n次多項式可以按照升冪寫成

Pn(x)= p0 + p1x + p2x2 + …… + pnxn

它由n+1個系數唯一確定。因此，一個一元n次多項式可以用一個線性表P來表示：

P = (p0，p1，p2，……，pn)

多項式每一項的指數隱含在線性表的序號里。假設Q是另外一個一元m次多項式，同樣也可以用線性表Q來表示

Q = (q0，q1，q2，q2，……，qm)

如果m

因此，多項式P和Q相加的結果可以用線性表R表示

R =(p0+ q0，p1+ q1，p2+ q2，……，pm+ qm，pm+1，……，pn)

由此可以看出，一元n次多項式在計算機中可以用線性表來表示，其加法運算也可以在線性表的基礎上進行。但在實際應用中，多項式的次數可能很高并且變化很大時，使得線性表最大長度很難確定，特別是在處理類似如下多項式時

T(x)= 12x2 + 2x12000+3x30000

雖然多項式只有3項非零元素，但仍然需要一個長度為30000的線性表來表示，造成對內存空間的浪費。在程序設計中，這種浪費是應當避免的。可以考慮用線性表存儲多項式每項系數的同時，也存儲相應的指數，這樣就可以不用存儲多項式的非零項了。

一般情況下，一元n次多項式也可以寫成

Pn(x)= p1xe1+ p2xe2 + …… + pmxem

其中，pi是指數為ei項的非零系數，并且滿足

0<=e1< e2

因此，若用一個長度為m，且每個元素有兩個數據項(系數項和指數項)的線性表，便可唯一確定多項式P(x)

P = ((p1，e1)，(p1，e2)，……，(pm，em))

上面的式子在每項都不為零的情況下，僅只比存儲每項系數的方案多存儲一倍的數據。但是對于T(x)類的多項式，這種表示將極大節省存儲空間。

用線性表存儲多項式可以采用兩種存儲結構，一種是順序存儲結構，一種是鏈式存儲結構。在實際應用中，具體采用什么存儲結構，則要視作什么運算而定。一般來說如果僅是求多項式值的運算，宜采用順序存儲結構，當需要修改多項式的系數和值時宜采用鏈式存儲結構。

例如??多項式

P(x)= 12 + 2x3+8x5+11x6

線性表的表示為

P = ((12，0)，(2，3)，(8，5)，(11，6))

一元多項式相加的運算規則非常簡單，兩個多項式中指數相同的項對應系數相加，若相加的和不為零，則構成相加結果多項式中的一項，所有指數不相同的項均復制到相加結果多項式中。

02

下面用Java語言給出一元多項式表示及加法運算案例。前面討論過，用線性表存儲多項式時，宜采用系數項和指數項同時存儲的結構。因此在案例中定義了PolyData類，用于存儲多項式的項數據。

package com.milihua.algorithm.lineartable;public class PolyData { /** * 多項式系數項 */ public int coef; /** * 多項式指數項 */ public int expn; /** * 多項式項構造函數 */ PolyData(int coef,int expn){ this.coef = coef; this.expn = expn; } public int getCoef() { return coef; } public void setCoef(int coef) { this.coef = coef; } public int getExpn() { return expn; } public void setExpn(int expn) { this.expn = expn; }}

多項式存儲采用LinkedList類，LinkedList是一個雙向鏈表，當數據量很大或者操作很頻繁的情況下，添加和刪除元素時具有比ArrayList更好的性能。

package com.milihua.algorithm.lineartable;import java.util.Iterator;import java.util.LinkedList;import java.util.Scanner;public class Polynomial { /** * 存儲第一個多項式的鏈表 */ LinkedList polyListOne = new LinkedList(); /** * 存儲第二個多項式的鏈表 */ LinkedList polyListTwo = new LinkedList(); /** * 存儲運算結果的多項式鏈表 */ LinkedList polyListResult = new LinkedList(); /** * 添加數據到鏈表尾部 * * @param inPolyData * @return */ public void addLastPol(LinkedList list, PolyData inPolyData) { list.addLast(inPolyData); } /** * 添加數據到鏈表 * * @param inPolyData * @return */ public void addPol(LinkedList list, PolyData inPolyData) { list.add(inPolyData); } /** * 比較每項的指數大小 * * @param aExpen * @param bExpn * @return 0兩個指數相等，1第一個鏈表的指數大，-1第二個鏈表的指數大 */ public int compExpn(int aExpen, int bExpn) { if (aExpen == bExpn) { return 0; } else if (aExpen > bExpn) { return 1; } else { return -1; } } /** * 兩個多項式鏈表相加 * * @return */ public void addPol() { for (Iterator iter = polyListOne.iterator(); iter.hasNext();) { PolyData poly = iter.next(); for (Iterator iterTwo = polyListTwo.iterator(); iterTwo.hasNext();) { PolyData polyTwo = iterTwo.next(); switch (compExpn(poly.expn, polyTwo.expn)) { case 0: PolyData newPolyData = new PolyData(poly.coef + polyTwo.coef, poly.expn); polyListResult.add(newPolyData); polyListTwo.remove(polyTwo); break; case 1: polyListResult.add(polyTwo); polyListResult.add(poly); polyListTwo.remove(polyTwo); break; case -1: polyListResult.add(poly); polyListResult.add(polyTwo); polyListTwo.remove(polyTwo); break; } break; } } } /** * 遍歷鏈表并顯示出來 * * @param list */ public void display(LinkedList list) { for (Iterator iter = list.iterator(); iter.hasNext();) { PolyData poly = iter.next(); System.out.print(poly.getCoef() + "x^" + poly.getExpn() + "+"); } System.out.println(); } public LinkedList getPolyListOne() { return polyListOne; } public void setPolyListOne(LinkedList polyListOne) { this.polyListOne = polyListOne; } public LinkedList getPolyListTwo() { return polyListTwo; } public void setPolyListTwo(LinkedList polyListTwo) { this.polyListTwo = polyListTwo; } public LinkedList getPolyListResult() { return polyListResult; } public void setPolyListResult(LinkedList polyListResult) { this.polyListResult = polyListResult; }}

Polynomial類是案例文件的主要處理類，在類中聲明了三個LinkedList類，分別存儲第一個多項式、第二個多項式以及兩個多項式相加運算的結果。

Polynomial類的addPol()方法用于執行兩個多項式的相加運算，具體算法過程是：

(1)遍歷第一個多項式；

(2)在遍歷過程中，處理每一個單項；

• 遍歷第二個多項式；

• 比較兩個單項式的指數；

• 若指數相同，則兩個單項式的系數相加，并形成新的單項式添加到運算結果列表中；若指數不相同，則兩個單項式都添加到運算結果列表中。

addPol算法的執行頻率為n*m，n為第一個多項式的單項式個數，m為第二個多項式的單項式個數，其算法復雜度為O(n^2)。

PolynomialTest類為測試類，代碼如下：package unittest;import java.util.Scanner;import com.milihua.algorithm.lineartable.PolyData;import com.milihua.algorithm.lineartable.Polynomial;public class PolynomialTest { public static void main(String[] args) { Polynomial poly = new Polynomial(); //聲明Scanner變量，并用new運算符實例化Scanner Scanner sc = new Scanner(System.in); System.out.println("----請輸入第一個多項式\r\n輸入方式為“系數，" + "指數”\r\n結束請輸入0----"); while(true) { String str = sc.next(); if( str.equals("0") ) { System.out.println("----第一個多項式輸入結束----"); break; } String[] strArray = str.split(","); if( strArray.length < 2 ) { System.out.println("----輸入的數據格式錯誤----"); break; } int coef = Integer.parseInt(strArray[0]); int expn = Integer.parseInt(strArray[1]); PolyData polyData = new PolyData(coef,expn); poly.addPol(poly.getPolyListOne(),polyData); } poly.display(poly.getPolyListOne()); System.out.println("----請輸入第二個多項式\r\n輸入方式為“系數，" + "指數”\r\n結束請輸入0----"); while(true) { String str = sc.next(); if( str.equals("0") ) { System.out.println("----第二個多項式輸入結束----"); break; } String[] strArray = str.split(","); if( strArray.length < 2 ) { System.out.println("----輸入的數據格式錯誤----"); break; } int coef = Integer.parseInt(strArray[0]); int expn = Integer.parseInt(strArray[1]); PolyData polyData = new PolyData(coef,expn); poly.addPol(poly.getPolyListTwo(),polyData); } poly.display(poly.getPolyListTwo()); poly.addPol(); poly.display(poly.getPolyListResult()); }}

用線性表存儲一元多項式時，線性表的元素由兩部分組成，一部分用于存儲多項式的系數項，一部分用于存儲多項式的指數項。這種存儲結構對指數項很高且變化很大的多項式特別有用。在存儲多項式時，線性表的存儲結構可以采用順序存儲結構，也可以采用鏈式存儲結構，推薦使用鏈式存儲結構，存儲空間靈活其運算方便。

一元多項式相加的運算規則非常簡單，兩個多項式中指數相同的項對應系數相加，若相加的和不為零，則構成相加結果多項式中的一項，所有指數不相同的項均復制到相加結果多項式中。多項式加法運算的時間復雜度為O(n)或O(n^2),算法不同，其時間復雜度也不同。本文給出的案例時間復雜度為O(n^2)，時間復雜度為O(n)的算法，請自行給出。

—END—編程訓練營APP創新在線學習模式，學習編程不再半途而廢安卓手機應用商店搜索編程訓練營下載

總結

以上是生活随笔為你收集整理的c++用模板实现稀疏多项式_用线性表实现一元多项式及相加运算的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。