多项式加减法课件.ppt

单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,*,单击此处编辑母版标题样式,,实验目的,,编写程序，实现多项式的加法和减法运算,,数据结构及算法,,队列表示：相应多项式加法算法（减法类似）,,链表表示：相应多项式加法算法（减法类似）,,具体实现时需要注意的问题,,输入,,输出,,空间分配和释放（,new,和,delete,）,,,多项式的表示1：队列,,用一个队列表示一个多项式,,队列中的每个成员是多项式的一项,,struct Node,,{,,float coef;//,系数,,,int exp;//,指数,,};,,约定：队列从头到尾，按照多项式指数增加（或减少）排列,多项式,用队列表示的上述多项式,队列头,,多项式的表示1：队列,,-3 8,2 3,-5 5,6 0,3 8,6 0,2 3,-5 5,多项式,1,多项式,2,结果多项式,,多项式的表示1：队列,,算法实现,,可以使用第一个实验中自己实现的队列类,,可以使用,STL,中的队列,,具体用法可以参看,msdn,,多项式的表示2：链表,,用一个链表表示一个多项式,,链表中的每个结点是多项式的一项,,struct Node,,{,,float coef;//,系数,,,int exp;//,指数,,,Node *next;,,};,,6 0,-5 5,3 8,多项式,链表表示,,多项式的表示2：链表,,方式一：基于某个链表,6 0,-5 5,3 8 ^,2 3,3 5,-3 8 ^,6 0,2 3,-2 5 ^,链表,1,表示多项式,1,链表,2,表示多项式,2,链表,1,表示结果多项式,链表,2,为空,结果多项式为,在链表,1,的基础上对其进行结点的插入和删除，得到结果多项式。

即将链表,2,中的结点插入到链表,1,中适当的地方，或者若与链表,1,中结点指数相等则运算后删除该节点,,多项式的表示2：链表,,方式二：利用原结点空间，结果用一个新链表存放,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,的尾部,,多项式的表示2：链表,,方式三：新开辟结点空间，结果用一个新链表存放,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,中,,具体实现：多项式输入,,按多项式一项一项输入，比如提示输入多项式中某一项的系数，输入多项式某一项的指数,,项数预先定好,,约定某特殊符号作为输入结束符,,直接将整个多项式一次输入,,,6-5x^5+3x^8,,不用输入，直接程序内赋值，构造多项式,,编写程序测试的时候使用，用于测试多项式算法是否成功,,表示为,,具体实现：多项式结果输出,,将多项式一项项输出,,比如，输出多项式中第,n,项的指数，系数,,多项式整体输出,,6-5x^5+3x^8,,考虑每一项的符号问题,,加号还是减号？通过判断系数与,0,的大小，决定是否要加上“,+”,,第一项是否有符号（加号可以省略，减号不可以省略）,,考虑指数为,0,的情况,,x,0,不用输出（,x^0,）,,,,,具体实现,,主要目的是实现多项式的加法和减法，那么可以先把目光集中在具体的算法上，而输入输出可以简化先，等把多项式的加法减法实现，再进一步完善输入输出,,省略输入：直接在程序内部赋值,,省略输出：直接用单步调试的方式，观察,,具体实现方法一：用STL中的队列,,#ifndef POLYNOMIAL_H_,,#define POLYNOMIAL_H_,,,#include ,,#include ,,using namespace std;,,,struct Node,,{,,float coef;//,系数,,,int exp;//,指数,,};,,,,//class Polynomial-------------------------------------,,//,,class Polynomial:private queue,,{,,public:,,void read();,,void print()const;,,//,多项式,p+q,,void equals_sum(Polynomial p,Polynomial q);,,//,多项式,p-q,,void equals_difference(Polynomial p,Polynomial q);,,};,,#endif,Polynomial.h,,具体实现方法二：用自己实现的队列类,#ifndef POLYNOMIAL_H_,,#define POLYNOMIAL_H_,,,#include ,,using namespace std;,,#include "Extended_queue.h",,,//class Polynomial-------------------------------------,,//,,,class Polynomial:private Extended_queue,,{,,public:,,void read();,,void print()const;,,void equals_sum(Polynomial p,Polynomial q);,,void equals_difference(Polynomial p,Polynomial q);,,};,,,#endif,Polynomial.h,,具体实现方法三：直接用链表,,#ifndef POLY_H,,#define POLY_H,,,#include ,,#include "LinkedList.h",,,using namespace std;,,,class Poly,,{,,public:,,LinkedList *polynomial;,,,//,构造函数,,,Poly(),,{,,polynomial=new LinkedList;,,},,//,读入多项式,,,LinkedList* createPoly();,,,//,多项式的加法,,,Poly* operator+(const Poly *p);,,//,多项式的减法,,,Poly* operator-(const Poly *p);,,};,,#endif,Poly.h,,。