线性表的应用2.5求解两个多项式相加问题描述2.5.1多项式p()=cx1+C,x2+..+cmxm求两个多项式相加的程序例如，p(x)=2x3+3.2x5-6x+10,q(×)=6x+1.8x5-2x3+x2-2.5x4-5r(x)=p(x)+q(x)r(x)=5x5-2.5x4+x2+51/38
多项式 求两个多项式相加的程序 例如，p(x)=2x 3+3.2x 5-6x+10，q(x)=6x+1.8x 5-2x 3+x 2-2.5x 4-5 r(x)=5x 5-2.5x 4+x 2+5 r(x)=p(x)+q(x) 1/38
p(x) = Cixe1+c,xe2 +...+cmxem拉(c2,e2) ..(C1,e1)(cm,em)多项式线性表多项式项2/38
(c1,e1) (c2,e2) . (cm,em) 多项式项 多项式线性表 2/38
ADT PolyClass//多项式抽象数据类型【 数据对象：PolyElem={(ci,ei) 1≤i≤n,c,Edouble,e,Eint);数据关系：r={I Xi, yiEPolyElem,i=1,., n-1]基本运算：voidAdd(PolyElemp)：将多项式项p添加到末尾。void CreatePoly(double[] a,int [] b,int n):由数组a和b创建多项式顺序表。void Sort()：对多项式顺序表按指数递减排序。voidDispPoly()：输出多项式顺序表。//ADT PolyClass在PolyClaSs的基础上实现以下求两个多项式L1和L2相加的运算算法：PolyClass Add(PolyClass L1,PolyclassL2);3/38
ADT PolyClass //多项式抽象数据类型 { 数据对象： PolyElem={(ci，ei) | 1≤i≤n，ci∈double，ei∈int}; 数据关系： r={ | xi，yi∈PolyElem，i=1，.，n-1} 基本运算： void Add(PolyElem p)：将多项式项p添加到末尾。 void CreatePoly(double [] a，int [] b,int n)： 由数组a和b创建多项式顺序表。 void Sort()：对多项式顺序表按指数递减排序。 void DispPoly()：输出多项式顺序表。 } //ADT PolyClass 在PolyClass的基础上实现以下求两个多项式L1和L2相加的运算算法： PolyClass Add(PolyClass L1，PolyClass L2); 3/38
采用顺序存储结构求解2.5.21.设计顺序存储结构多项式项类型PolyElem//多项式顺序表元素类型class PolyElem//系数double coef;1 /指数int exp;1/构造方法PolyElem(double c,int e) coef=c;exp=e;11 /返回exppublic int getexp()return exp;}4/38
1. 设计顺序存储结构 多项式项类型PolyElem class PolyElem //多项式顺序表元素类型 { double coef; //系数 int exp; //指数 PolyElem(double c,int e) //构造方法 { coef=c; exp=e; } public int getexp() //返回exp { return exp; } } 4/38
多项式顺序表Polyclass类//多项式顺序表类class Polyclass//存放多项式顺序表ArrayListpoly//构造方法public Polyclass(){//分配顺序表的data空间poly=new ArrayList();7//包含Add、CreatePoly、Sort和DispPoly方法75/38
多项式顺序表PolyClass类 class PolyClass //多项式顺序表类 { ArrayList poly; //存放多项式顺序表 public PolyClass() //构造方法 { poly=new ArrayList(); //分配顺序表的data空间 } //包含Add、CreatePoly、Sort和DispPoly方法 } 5/38
p(x)=2x3+3.2x5-6x+10polycoef3.2-6.02.010.0...3510exp...6/38
coef 2.0 3 3.2 5 -6.0 1 10.0 0 . . . exp . poly p(x)=2x 3+3.2x 5-6x+10 6/38
2．设计Polyclass的基本运算算法(1)在顺序表末尾添加元素Add（p）/末尾添加一个多项式项public void Add(PolyElemp)Tpoly.add(p);7/38
2. 设计PolyClass的基本运算算法 public void Add(PolyElem p) //末尾添加一个多项式项 { poly.add(p); } 7/38
(2）创建多项式顺序表CreatePoly（a，b，n）public voidCreatePoly(double[] a,int[] b,int n)1/建立多项式顺序表for （(int i=o;i<n;i++)poly.add(new PolyElem(a[i],b[i]));8/38
public void CreatePoly(double[] a,int[] b,int n) //建立多项式顺序表 { for (int i=0;i<n;i++) poly.add(new PolyElem(a[i],b[i])); } 8/38
（3）按exp成员递减排序Sort（）public void Sort()//对多项式顺序表按exp成员递减排序poly.sort(Comparator.comparing(PolyElem::getexp).reversed());9/38
public void Sort() //对多项式顺序表按exp成员递减排序 { poly.sort(Comparator.comparing(PolyElem::getexp).reversed()); } 9/38
（4）输出多项式顺序表DispPoly(）//输出多项式顺序表public void DispPoly()//first为true表示是第一项boolean first=true;一int i=o;while (io) System.out.print("+");//指数为0时不输出xif (p.exp==0)System.out.print(p.coef);//指数为1时不输出指数else if (p.exp==1)System.out.print(p.coef+"x");elseSystem.out.print(p.coef+"x^"+p.exp);i++;System.out.println();10/38
public void DispPoly() //输出多项式顺序表 { boolean first=true; //first为true表示是第一项 int i=0; while (i0) System.out.print("+"); if (p.exp==0) //指数为0时不输出'x' System.out.print(p.coef); else if (p.exp==1) //指数为1时不输出指数 System.out.print(p.coef+"x"); else System.out.print(p.coef+"x^"+p.exp); i++; } System.out.println(); } 10/38