数据基础教程21_第1页
数据基础教程21_第2页
数据基础教程21_第3页
数据基础教程21_第4页
数据基础教程21_第5页
已阅读5页,还剩27页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

2.5线性表的应用2.5.1求解两个多项式相加问题描述多项式求两个多项式相加的程序例如,p(x)=2x3+3.2x5-6x+10,q(x)=6x+1.8x5-2x3+x2-2.5x4-5r(x)=5x5-2.5x4+x2+5r(x)=p(x)+q(x)1/32(c1,e1)(c2,e2)…(cm,em)多项式项多项式线性表2/32ADTPolyClass{

//多项式抽象数据类型

数据对象: PolyElem={(ci,ei)|1≤i≤n,ci∈double,ei∈int};

数据关系:

r={<xi,yi>|xi,yi∈PolyElem,i=1,…,n-1}

基本运算: voidAdd(PolyElemp):将多项式项p添加到末尾。 voidCreatePoly(double[]a,int[]b,intn):

由数组a和b创建多项式顺序表。 voidSort():对多项式顺序表按指数递减排序。 voidDispPoly():输出多项式顺序表。}在PolyClass的基础上实现以下求两个多项式L1和L2相加的运算算法:PolyClassAdd(PolyClassL1,PolyClassL2);3/322.5.2采用顺序存储结构求解1.设计顺序存储结构多项式项类型PolyElemclassPolyElem { //多项式顺序表元素类型doublecoef; //系数intexp; //指数PolyElem(doublec,inte){ //构造方法coef=c;exp=e;}publicintgetexp(){ //返回expreturnexp;}}4/32多项式顺序表PolyClass类classPolyClass{

//多项式顺序表类ArrayList<PolyElem>poly; //存放多项式顺序表publicPolyClass(){ //构造方法poly=newArrayList<PolyElem>(); //分配顺序表的data空间}

//包含Add、CreatePoly、Sort和DispPoly方法}5/322.0coef33.25-6.0110.00…………exppolyp(x)=2x3+3.2x5-6x+106/322.设计PolyClass的基本运算算法(1)在顺序表末尾添加元素Add(p)publicvoidAdd(PolyElemp){//末尾添加一个多项式项poly.add(p);}7/32(2)创建多项式顺序表CreatePoly(a,b,n)publicvoidCreatePoly(double[]a,int[]b,intn){

//建立多项式顺序表for(inti=0;i<n;i++)poly.add(newPolyElem(a[i],b[i]));}8/32(3)按exp成员递减排序Sort()publicvoidSort(){ //对多项式顺序表按exp成员递减排序poly.sort(Cparing(PolyElem::getexp).reversed());}9/32(4)输出多项式顺序表DispPoly()publicvoidDispPoly(){ //输出多项式顺序表booleanfirst=true; //first为true表示是第一项inti=0;while(i<poly.size()){PolyElemp=(PolyElem)poly.get(i);if(first)first=false;elseif(p.coef>0)System.out.print("+");if(p.exp==0) //指数为0时不输出'x'System.out.print(p.coef);elseif(p.exp==1) //指数为1时不输出指数System.out.print(p.coef+"x");elseSystem.out.print(p.coef+"x^"+p.exp);i++;}System.out.println();}10/323.设计主要运算算法两个多项式相加运算两个按指数递减排序的多项式顺序表相加的结果多项式顺序表二路归并+整体创建顺序表11/32publicstaticPolyClassAdd(PolyClassL1,PolyClassL2){inti=0,j=0; doublec;PolyClassL3=newPolyClass();while(i<L1.poly.size()&&j<L2.poly.size()){if(L1.poly.get(i).exp>L2.poly.get(j).exp){ //L1元素指数较大L3.Add(newPolyElem(L1.poly.get(i).coef,L1.poly.get(i).exp));i++;}elseif(L1.poly.get(i).exp<L2.poly.get(j).exp){//L2的指数较大L3.Add(newPolyElem(L2.poly.get(j).coef,L2.poly.get(j).exp));j++;}else{ //两元素的指数相等c=L1.poly.get(i).coef+L2.poly.get(j).coef;//求系数和cif(c!=0) //系数和c≠0时复制L3.Add(newPolyElem(c,L1.poly.get(i).exp));i++;j++;}}12/32while(i<L1.poly.size()){ //复制L1余下的元素L3.Add(newPolyElem(L1.poly.get(i).coef,L1.poly.get(i).exp));i++;}while(j<L2.poly.size()){ //复制L2余下的元素L3.Add(newPolyElem(L2.poly.get(j).coef,L2.poly.get(j).exp)); j++;}returnL3;}13/324.设计主函数abc.in文件abc.out文件14/32publicstaticvoidmain(String[]args)throwsFileNotFoundException{System.setIn(newFileInputStream("abc.in"));

//将标准输入流重定向至abc.inScannerfin=newScanner(System.in);System.setOut(newPrintStream("abc.out"));

//将标准输出流重定向至abc.outPolyClassL1=newPolyClass(); //多项式顺序表对象L1和L2PolyClassL2=newPolyClass();PolyClassL3;double[]a=newdouble[100];int[]b=newint[100];intn;n=fin.nextInt(); //输入nfor(inti=0;i<n;i++) //输入aa[i]=fin.nextDouble();for(inti=0;i<n;i++) //输入bb[i]=fin.nextInt();15/32L1.CreatePoly(a,b,n); //创建第1个多项式顺序表L1System.out.print("第1个多项式:");L1.DispPoly();L1.Sort(); //排序System.out.print("排序后结果:");L1.DispPoly();n=fin.nextInt(); //输入nfor(inti=0;i<n;i++) //输入aa[i]=fin.nextDouble();for(inti=0;i<n;i++) //输入bb[i]=fin.nextInt();L2.CreatePoly(a,b,n); //创建第2个多项式顺序表L2System.out.print("第2个多项式:");L2.DispPoly();L2.Sort(); //排序System.out.print("排序后结果:");L2.DispPoly();L3=Add(L1,L2); //两多项式相加System.out.print("相加后多项式:");L3.DispPoly();}16/325.程序执行结果abc.in文件abc.out文件423.2-6103510661.8-21-2.5-5153240第1个多项式:2.0x^3+3.2x^5-6.0x+10.0排序后结果:3.2x^5+2.0x^3-6.0x+10.0第2个多项式:6.0x+1.8x^5-2.0x^3+1.0x^2-2.5x^4-5.0排序后结果:1.8x^5-2.5x^4-2.0x^3+1.0x^2+6.0x-5.0相加后多项式:5.0x^5-2.5x^4+1.0x^2+5.017/322.5.3采用链式存储结构求解1.设计链式存储结构多项式单链表结点类classPolyNode { //单链表结点类型publicdoublecoef; //系数publicintexp; //指数publicPolyNodenext; //指针成员PolyNode(){ //构造方法next=null;}PolyNode(doublec,inte){ //重载构造方法coef=c;exp=e;next=null;}}18/32多项式单链表PolyClass类classPolyClass{

//多项式单链表类PolyNodehead; //存放多项式单链表头结点publicPolyClass() { //构造方法head=newPolyNode(); //建立头结点head}//包含CreatePoly、Sort和DispPoly方法}19/32p(x)=2x3+3.2x5-6x+10head2.033.25-6.0110.00∧coefexp20/322.设计PolyClass的基本运算算法(1)创建多项式单链表CreatePoly(a,b,n)publicvoidCreatePoly(double[]a,int[]b,intn){//采用尾插法建立多项式单链表PolyNodes,t;t=head; //t始终指向尾结点,开始时指向头结点for(inti=0;i<n;i++){s=newPolyNode(a[i],b[i]); t.next=s; //在t结点之后插入s结点t=s;}t.next=null; //尾结点next成员置为null}21/32(2)按exp成员递减排序Sort()head3.25∧2.03-6.0110.00∧phead3.252.03-6.0110.00∧有序插入22/32publicvoidSort(){ //对多项式单链表按exp成员递减排序PolyNodep,pre,q;q=head.next; //q指向开始结点if(q==null)return; //原单链表空返回p=head.next.next; //p指向q结点的后继结点if(p==null)return; //原单链表只有一个数据结点返回q.next=null; //构造只含一个数据结点的有序单链表while(p!=null){q=p.next; //q用于临时保存p结点后继结点pre=head; //pre从头结点开头while(pre.next!=null&&pre.next.exp>p.exp)pre=pre.next; //在有序表中找插入结点p的前驱结点prep.next=pre.next; //将pre结点之后插入p结点pre.next=p;p=q; //扫描原单链表余下的结点}}23/32(3)输出多项式单链表DispPoly()publicvoidDispPoly(){ //输出多项式单链表booleanfirst=true; //first为true表示是第一项PolyNodep=head.next;while(p!=null){if(first)first=false;elseif(p.coef>0)System.out.print("+");if(p.exp==0) //指数为0时不输出'x'System.out.print(p.coef);elseif(p.exp==1) //指数为1时不输出指数System.out.print(p.coef+"x");elseSystem.out.print(p.coef+"x^"+p.exp);p=p.next;}System.out.println();}24/323.设计主要运算算法两个多项式相加运算两个按指数递减排序的多项式单链表相加的结果多项式单链表二路归并+尾插法创建结果单链表25/32publicstaticPolyClassAdd(PolyClassL1,PolyClassL2){//两个多项式相加运算PolyNodep,q,s,t; //t始终指向L3的尾结点doublec;PolyClassL3=newPolyClass(); //创建空多项式单链表L3t=L3.head; //t为L3的尾结点p=L1.head.next;q=L2.head.next;while(p!=null&&q!=null) { //p、q均没有遍历完if(p.exp>q.exp){ //L1的结点的指数较大t.next=s;t=s; //将p结点插入到L3的末尾p=p.next; //后移p结点}elseif(p.exp<q.exp){ //L2的结点的指数较大t.next=s;t=s; //将q结点插入到L3的末尾q=q.next; //后移q结点}26/32else{ //两结点的指数相等c=p.coef+q.coef; //求两指数相等结点的系数和cif(c!=0){ //系数和c不为0时s=newPolyNode(c,p.exp);t.next=s;t=s; //将s结点插入到L3的末尾}p=p.next;q=q.next; //后移p结点和q结点} } if(q!=null)p=q; while(p!=null){ //将余下的结点复制到L3中 s=newPolyNode(p.coef,p.exp); t.next=s;t=s; } t.next=null; //尾结点next置为null returnL3;}27/324.设计主函数abc.in文件abc.out文件28/32publicstaticvoidmain(String[]args)throwsFileNotFoundException{

System.setIn(newFileInputStream("abc.in"));

//将标准输入流重定向至abc.inScannerfin=newScanner(System.in);

System.setOut(newPrintStream("abc.out"));

//将标准输出流重定向至abc.outPolyClassL1=newPolyClass(); //多项式顺序表对象L1和L2PolyClassL2=newPolyClass();PolyClassL3;double[]a=newdouble[100];int[]b=newint[100];intn;n=fin.nextInt(); //输入nfor(inti=0;i<n;i++) //输入aa[i]=fin.nextDoub

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论