河池学院：《数据结构》课程电子教案（PPT教学课件）第2章 线性表 2.5 线性表的应用

多项式 求两个多项式相加的程序 例如，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

(c1,e1) (c2,e2) . (cm,em) 多项式项 多项式线性表 2/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

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 //多项式顺序表类 { ArrayList poly; //存放多项式顺序表 public PolyClass() //构造方法 { poly=new ArrayList(); //分配顺序表的data空间 } //包含Add、CreatePoly、Sort和DispPoly方法 } 5/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的基本运算算法 public void Add(PolyElem p) //末尾添加一个多项式项 { poly.add(p); } 7/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

public void Sort() //对多项式顺序表按exp成员递减排序 { poly.sort(Comparator.comparing(PolyElem::getexp).reversed()); } 9/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