文章导读
【本文主要讨论线性表在多项式计算中的应用，讨论内容涉及到一元n次多项式在计算机中的表示及多项式相加运算】
在数学上，一个一元n次多项式可以按照升幂写成
它由n+1个系数唯一确定。因此，一个一元n次多项式可以用一个线性表P来表示：
多项式每一项的指数隐含在线性表的序号里。假设Q是另外一个一元m次多项式，同样也可以用线性表Q来表示
如果m<n，则
因此，多项式P和Q相加的结果可以用线性表R表示
由此可以看出，一元n次多项式在计算机中可以用线性表来表示，其加法运算也可以在线性表的基础上进行。但在实际应用中，多项式的次数可能很高并且变化很大时，使得线性表最大长度很难确定，特别是在处理类似如下多项式时
虽然多项式只有3项非零元素，但仍然需要一个长度为30000的线性表来表示，造成对内存空间的浪费。在程序设计中，这种浪费是应当避免的。可以考虑用线性表存储多项式每项系数的同时，也存储相应的指数，这样就可以不用存储多项式的非零项了。
一般情况下，一元n次多项式也可以写成
其中，pi是指数为ei项的非零系数，并且满足
因此，若用一个长度为m，且每个元素有两个数据项（系数项和指数项）的线性表，便可唯一确定多项式P（x）
上面的式子在每项都不为零的情况下，仅只比存储每项系数的方案多存储一倍的数据。但是对于T（x）类的多项式，这种表示将极大节省存储空间。
用线性表存储多项式可以采用两种存储结构，一种是顺序存储结构，一种是链式存储结构。在实际应用中，具体采用什么存储结构，则要视作什么运算而定。一般来说如果仅是求多项式值的运算，宜采用顺序存储结构，当需要修改多项式的系数和值时宜采用链式存储结构。
例如，多项式
线性表的表示为
图 3 多项式表的顺序存储结构
图 4 多项式表的链式存储结构
一元多项式相加的运算规则非常简单，两个多项式中指数相同的项对应系数相加，若相加的和不为零，则构成相加结果多项式中的一项，所有指数不相同的项均复制到相加结果多项式中。
下面用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<PolyData> polyListOne = new LinkedList<PolyData>();
/**
* 存储第二个多项式的链表
*/
LinkedList<PolyData> polyListTwo = new LinkedList<PolyData>();
/**
* 存储运算结果的多项式链表
*/
LinkedList<PolyData> polyListResult = new LinkedList<PolyData>();
/**
* 添加数据到链表尾部
*
* @param inPolyData
* @return
*/
public void addLastPol(LinkedList<PolyData> list, PolyData inPolyData) {
list.addLast(inPolyData);
}
/**
* 添加数据到链表
*
* @param inPolyData
* @return
*/
public void addPol(LinkedList<PolyData> 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<PolyData> iter = polyListOne.iterator(); iter.hasNext();) {
PolyData poly = iter.next();
for (Iterator<PolyData> 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<PolyData> list) {
for (Iterator<PolyData> iter = list.iterator(); iter.hasNext();) {
PolyData poly = iter.next();
System.out.print(poly.getCoef() + "x^" + poly.getExpn() + "+");
}
System.out.println();
}
public LinkedList<PolyData> getPolyListOne() {
return polyListOne;
}
public void setPolyListOne(LinkedList<PolyData> polyListOne) {
this.polyListOne = polyListOne;
}
public LinkedList<PolyData> getPolyListTwo() {
return polyListTwo;
}
public void setPolyListTwo(LinkedList<PolyData> polyListTwo) {
this.polyListTwo = polyListTwo;
}
public LinkedList<PolyData> getPolyListResult() {
return polyListResult;
}
public void setPolyListResult(LinkedList<PolyData> 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）的算法，请自行给出。