多项式加法.doc

班级：信息1301 姓名： 胡苗苗 = 实习报告一 “PolyAdd”演示程序 =（一）、程序的功能和特点功能：将两个多项式相加，利用单链表存储多项式，并实现多项式的加法。特点：利用单链表进行多项式相加时，不生成新的结点，直接在原来的结点上运算。（二）、程序中的算法设计1.【逻辑结构与存储结构设计】逻辑结构：存储多项式的的单链表是线性结构。存储（物理）结构：存储多项式的的单链表是链式存储结构。例如：头指针Null数据域 指针域2.【基本操作设计】public boolean insertBack(double c,int e)给存储多项式的单链表的尾部插入一个结点头指针NullNull给存储多项式的单链表中插入一个结点新结点Null头指针新结点3.【算法设计】流程图：输入链表s1输入链表s2S1与S2的结点阶数比较大小s1指数小于s2s1指数等于s2s1指数大于s2s1自身结点不变，指针后移，继续与s2当前结点比较阶数让指向s1当前结点的指针指向s2当前结点，然后让s2当前结点指针指向s1系数相加，阶数不变，指针同时后移判断s1或s2指针是否到末尾 s2指针指向末尾s1指到末尾将s1的末尾指针指向s2的剩余部分输出s1算法描述：构造两个链表类s1，s2，头指针分别为ah，bh，从第一个结点开始比较：（1）如果两个结点的多项式阶数相等，那么把两个系数相加，指数不变赋给s1的第一个结点，指针后移；（2）如果s1的结点阶数小于s2的结点阶数，s1的指针ah后移，判断下一个结点阶数与s2当前阶数大小；（3）如果s1的结点阶数大于s2，那么将s2的当前结点插入s1当前结点的前面。直到s1或s2的指针指向空。判断s1或者s2指针是否指到末尾：若s2指针指空，那么结束程序。若s1指针指空，则把s1的末尾指针指向s2剩余的部分。4.【高级语言代码】 多项式加法:自身多项式和ob相加，和为自身public void addPoly(linkList ob) link ah=first; /自身的第一个结点link bh=ob.first; /ob的第一个结点link p,q; /辅助的指针，指向某个结点/指针ah和bh都没有移到结束处while(ah!=null&bh!=null) if(ah.exp=bh.exp) /阶数相同ah.coef+=bh.coef; /改变自身结点系数ah=ah.next; /自身单链表的当前指针后移bh=bh.next;/多项式ob的当前指针后移else if(ah.expbh.exp)ah=ah.next; /自身结点不变，指针后移else p=bh; /让p指向ob的当前结点bh=bh.next; /多项式ob的当前指针后移q=first; /把q指针移到ah的前驱结点while(q.next!=ah) q=q.next; q.next=p; /把p结点插在了ah的位置p.next=ah; /把ah接到了p结点后 /循环while结束if(bh!=null) /如果多项式ob