单链表的运用——多项式及其运算

我不是女神ヾ 2022-06-07 02:29 168阅读 0赞

**包括：多项式的class定义+多项式加法+多项式乘法**  
黄金周即将过去，好多任务都没有完成，还好提前意识到，最近两天只好奋笔疾书了！  
本篇依旧是数据结构的内容，但是是单链表的一个应用实例，还是比较实用的，相信透彻理解这个多项式的应用，对数据结构单链表这一块会更好的把握。废话不多说，下面给出完整代码：  
多项式class定义：

#include <iostream>
    #include <cmath>
    using namespace std;
    
    struct Term {
        float coef;
        int exp;
        Term * link;
        //多项式节点的定义
        Term(float c, int e, Term * next = NULL) {      //构造函数
            coef = c;                                   //系数
            exp = e;                                    //指数
            link = next;                                //指向下一个节点的指针
        }
        Term * InsertAfter(float c, int e);
        friend ostream & operator << (ostream&, const Term&);
    };
    
    class Polynomal {
    public:
        Polynomal(){ first = new Term(0, -1); }                         //构造函数
        Polynomal(Polynomal &R);                                        //复制构造函数
        int maxOrder();                                                 //计算最大阶数
        Term * getHead() const { return first; }                        //取得多项式单链表的表头指针
    private:
        Term *first;
        friend ostream & operator << (ostream &, const Polynomal &);
        friend istream & operator >> (istream &, Polynomal &);
        friend Polynomal operator + (Polynomal &, Polynomal &);
        friend Polynomal operator * (Polynomal &, Polynomal &);
    };
    
    //函数定义
    Term * Term::InsertAfter(float c, int e) {
        //在当前由this指针指示的项（即调用此函数的对象）后面插入一个新项
        link = new Term(c, e, link);                                    //创建一个新节点，自动连接
        return link;                                                    //返回新节点，以便下一次追加使用
    }
    
    ostream & operator << (ostream & out, Term & x) {
        //Term的友元函数，输出一个项x的内容到输出流out中
        if (0 == x.coef) {                                              //如果这一项的系数为0，则不输出
            return out;
        }
        out << x.coef;
        switch (x.exp) {                                                //不同指数的格式控制
        case 0: break;
        case 1: out << "X"; break;
        default: out << "X^" << x.exp; break;
        }
    
        return out;
    }
    
    Polynomal::Polynomal(Polynomal & R) {
        //复制构造函数 ： 用已有的多项式对象R初始化当前多项式对象
        first = new Term(0, -1);
        Term *destptr = first, *srcptr = R.getHead()->link;
        while (NULL != srcptr) {
            destptr->InsertAfter(srcptr->coef, srcptr->exp);            //在destptr所指节点后插入新节点
            srcptr = srcptr->link;
            destptr = destptr->link;
        }
    }
    
    int Polynomal::maxOrder() {
        //计算最大阶数，当多项式按照升序排序时，最后一项的指数最大
        Term *current = first;
        while (NULL != current->link) {
            current = current->link;                                    //表为NULL的时候，current停留在first，否则指向尾节点
        }
    
        return current->exp;
    }
    
    istream & operator >> (istream & in, Polynomal & x) {
        //Polynomal class 的友元函数，从输入流in输入各项，用顺序法建立一个多项式
        Term *rear = x.getHead();
        int c, e;
        while (true) {
            cout << "Input a term(coef, exp) : " << endl;
            in >> c >> e;
            if (e < 0) {
                break;                                                  //指数是负数作为结束的标志
            }
            rear = rear->InsertAfter(c, e);                             //链接到rear所指节点后
        }
        return in;
    }
    
    ostream & operator << (ostream & out, Polynomal & x) {
        //Polynomal class 的友元函数 : 输出带附加头节点的多项式链表x
        Term *current = x.getHead()->link;                              //先令current指向当前多项式的开始节点
        cout << "这个多项式是 ： " << endl;
        bool h = true;
        while (NULL != current) {
            if (current->coef > 0 && h == false) {
                cout << "+";
            }
            h = false;
            out << *current;
            current = current->link;
        }
        cout << endl;
        return out;
    }
    
    Polynomal operator + (Polynomal & A, Polynomal & B) {
        //友元函数：两个带附加头节点的按升幂排序的多项式链表的头指针分别是A.first and B.first
        //返回的结果是两个多项式的和链表
        Term *pa, *pb, *pc, *p;
        float temp;
        Polynomal C;
        pc = C.first;                                                   //pc是结果多项式C在创建过程中的尾指针
        pa = A.getHead()->link;
        pb = B.getHead()->link;                                         //pa,pb定位在A，B两个多项式的相应节点
        while (pa != NULL && pb != NULL) {                              //对两个子多项式的节点指数逐一比较
            if (pa->exp == pb->exp) {                                   //相等的情况
                temp = pa->coef + pb->coef;                             //系数相加
                if (fabs(temp) > 0.001) {                               //相加后系数不等于0
                    pc = pc->InsertAfter(temp, pa->exp);                //提取指数与系数追加在和多项式之后
                }
                pa = pa->link;
                pb = pb->link;                                          //检测指针向后一个节点移动
            }
            else if (pa->exp < pb->exp) {                               //指数不想等的两种大小关系
                pc = pc->InsertAfter(pa->coef, pa->exp);
                pa = pa->link;                                          //仅pa检测指针向后一个节点移动
            }
            else {
                pc = pc->InsertAfter(pb->coef, pb->exp);
                pb = pb->link;
            }
        }
        //检查是否有剩余链表，若有直接链接到和链表C后
        if (pa != NULL) {                                               //借助p指针标记剩余链表，待之后做链接
            p = pa;
        }
        else {
            p = pb;
        }
        while (p != NULL) {
            pc = pc->InsertAfter(p->coef, p->exp);
            p = p->link;
        }
    
        return C;
    }
    
    Polynomal operator * (Polynomal & A, Polynomal & B) {
        //将一元多项式A 和 B相乘，乘积用带附加头节点的单链表存储
        //返回值为指向存储乘积多项式的单链表
        Term *pa, *pb, *pc;
        int AL, BL, i, k, maxExp;
        Polynomal C;
        pc = C.getHead();
        AL = A.maxOrder();                                              //首先计算乘积后的最大指数
        BL = B.maxOrder();
        if (AL != -1 || BL != -1) {
            maxExp = AL + BL;
            float *result = new float[maxExp + 1];                      //开辟辅助数组用来存储相关指数项的系数
            for (i = 0; i <= maxExp; i ++) {
                result[i] = 0;                                          //初始化辅助数组
            }
            pa = A.getHead()->link;
            while (pa != NULL) {                                        //双重循环实现两个多项式相乘
                pb = B.getHead()->link;
                while (pb != NULL) {
                    k = pa->exp + pb->exp;                              //乘积的指数
                    //注意此处是累加
                    result[k] = result[k] + pa->coef * pb->coef;        //计算乘积后的系数并存储在相应指数序号的数组中
                    pb = pb->link;                                      //向后一个节点移动
                }
                pa = pa->link;                                          //向后一个节点移动
            }
            //将指数——系数数组中的数据存储到新的单链表中，组成乘积多项式
            for (i = 0; i <= maxExp; i ++) {
                if (fabs(result[i]) > 0.001) {
                    pc = pc->InsertAfter(result[i], i);
                }
            }
            delete[] result;                                            //释放资源数组
        }
        pc->link = NULL;
        return C;
    }

主函数测试代码：

int main()
    {
        ////多项式输入与输出的简单测试
        //Polynomal poly1;
        //cin >> poly1;                         //通过输入重载运算符对多项式输入
        //cout << poly1;                        //通过输出重载运算符对多项式输出
    
        ////多项式求和运算简单测试
        //Polynomal poly2, poly3, polySum;
        //cin >> poly2 >> poly3;
        //polySum = poly2 + poly3;
        //cout << polySum << endl;
    
        //多项式相乘测试
        Polynomal poly4, poly5, polyMul;
        cin >> poly4 >> poly5;
        polyMul = poly4 * poly5;
        cout << polyMul << endl;
    
        system("pause");
        return 0;
    }

部分运行结果：  
![运行结果][SouthEast]  
问题：  
在整理及录入这部分代码的时候，并没有做非法数据的测试及预防，这使得程序的健壮性需要提高；另一个问题是份文件写入的时候出现大量函数重定义的错误，这个问题还没有解决，但是已经找到比较详细的资料，希望遇到相同问题的小伙伴可以一块讨论，我也会在理解后，写篇相应的文章。

[SouthEast]: /images/20220607/2d20e056386b4d71ad124f618988dc2e.png