多项式加减法讲稿.ppt

《多项式加减法讲稿.ppt》由会员分享，可在线阅读，更多相关《多项式加减法讲稿.ppt（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、多项式加减法第一页，讲稿共十五页哦实验目的l编写程序，实现多项式的加法和减法运算 数据结构及算法l队列表示：相应多项式加法算法（减法类似）l链表表示：相应多项式加法算法（减法类似）具体实现时需要注意的问题l输入l输出l空间分配和释放（new 和delete）第二页，讲稿共十五页哦多项式的表示1：队列l用一个队列表示一个多项式队列中的每个成员是多项式的一项struct Nodefloat coef;/系数系数int exp;/指数指数;约定：队列从头到尾，按照多项式指数增加（或减少）排列多项式用队列表示的上述多项式队列头第三页，讲稿共十五页哦多项式的表示1：队列-3 82 3-5 56 03 8

2、6 02 3-5 5多项式1多项式2结果多项式第四页，讲稿共十五页哦多项式的表示1：队列l算法实现可以使用第一个实验中自己实现的队列类可以使用STL中的队列l具体用法可以参看msdn第五页，讲稿共十五页哦多项式的表示2：链表l用一个链表表示一个多项式链表中的每个结点是多项式的一项struct Nodefloat coef;/系数int exp;/指数 Node*next;6 0 -5 5 3 8 多项式链表表示第六页，讲稿共十五页哦多项式的表示2：链表l方式一：基于某个链表6 0 -5 5 3 8 2 3 3 5 -3 8 6 0 2 3 -2 5 链表1表示多项式1链表2表示多项式2链表链表

3、1表示结果多项式表示结果多项式链表链表2为空为空结果多项式为在链表1的基础上对其进行结点的插入和删除，得到结果多项式。即将链表2中的结点插入到链表1中适当的地方，或者若与链表1中结点指数相等则运算后删除该节点第七页，讲稿共十五页哦多项式的表示2：链表l方式二：利用原结点空间，结果用一个新链表存放6 0 -5 5 3 8 2 3 3 5 -3 8 6 0 2 3 -2 5 链表1表示多项式1链表2表示多项式2链表链表3表示结果多项式表示结果多项式链表链表1为空，链表为空，链表2为空为空结果多项式为从链表1和链表2的头部开始进行指数比较。指数相等则系数相加，把结果结点链接到链表3的尾部，删除多余结

4、点；该结点指数唯一，则直接将该节点链接到链表3的尾部第八页，讲稿共十五页哦多项式的表示2：链表l方式三：新开辟结点空间，结果用一个新链表存放6 0 -5 5 3 8 2 3 3 5 -3 8 6 0 2 3 -2 5 链表1表示多项式1链表2表示多项式2链表链表3表示结果多项式表示结果多项式链表链表1不变，链表不变，链表2不变不变结果多项式为从链表1和链表2的头部开始进行指数比较。指数相等则系数相加，新开辟空间存放该项结果，把新生成的结果结点链接到链表3的尾部；若结点指数唯一，也新开辟空间存放该结点的值，并将此结点链接到链表3中第九页，讲稿共十五页哦具体实现：多项式输入l按多项式一项一项输入，

5、比如提示输入多项式中某一项的系数，输入多项式某一项的指数项数预先定好约定某特殊符号作为输入结束符l直接将整个多项式一次输入 6-5x5+3x8l不用输入，直接程序内赋值，构造多项式编写程序测试的时候使用，用于测试多项式算法是否成功表示为第十页，讲稿共十五页哦具体实现：多项式结果输出l将多项式一项项输出比如，输出多项式中第n项的指数，系数l多项式整体输出6-5x5+3x8考虑每一项的符号问题l加号还是减号？通过判断系数与0的大小，决定是否要加上“+”l第一项是否有符号（加号可以省略，减号不可以省略）考虑指数为0的情况lx0不用输出（x0）第十一页，讲稿共十五页哦具体实现l主要目的是实现多项式的加

6、法和减法，那么可以先把目光集中在具体的算法上，而输入输出可以简化先，等把多项式的加法减法实现，再进一步完善输入输出省略输入：直接在程序内部赋值省略输出：直接用单步调试的方式，观察第十二页，讲稿共十五页哦具体实现方法一：用STL中的队列#ifndef POLYNOMIAL_H_#define POLYNOMIAL_H_#include#include using namespace std;struct Nodefloat coef;/系数int exp;/指数;/class Polynomial-/class Polynomial:private queuepublic:void read()

7、;void print()const;/多项式p+qvoid equals_sum(Polynomial p,Polynomial q);/多项式p-qvoid equals_difference(Polynomial p,Polynomial q);#endifPolynomial.h第十三页，讲稿共十五页哦具体实现方法二：用自己实现的队列类#ifndef POLYNOMIAL_H_#define POLYNOMIAL_H_#include using namespace std;#include Extended_queue.h/class Polynomial-/class Polyno

8、mial:private Extended_queuepublic:void read();void print()const;void equals_sum(Polynomial p,Polynomial q);void equals_difference(Polynomial p,Polynomial q);#endifPolynomial.h第十四页，讲稿共十五页哦具体实现方法三：直接用链表#ifndef POLY_H#define POLY_H#include#include LinkedList.husing namespace std;class Poly public:LinkedList*polynomial;/构造函数Poly()polynomial=new LinkedList;/读入多项式LinkedList*createPoly();/多项式的加法Poly*operator+(const Poly*p);/多项式的减法Poly*operator-(const Poly*p);#endifPoly.h第十五页，讲稿共十五页哦