PTA 7-2 一元多项式的乘法与加法运算

设计函数分别求两个一元多项式的乘积与和。

输入格式:

输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:

输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例:

4 3 4 -5 2  6 1  -2 0
3 5 20  -7 4  3 1

输出样例:

15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0

C语言实现代码

/*
    先给出项数,随后以指数递降的方式给出系数和指数
    一共两行,
    输出两个多项式的和与乘积
    由于给出了项数,可以使用动态数组来存储
*/

#include <stdio.h>
#include <stdlib.h>

// 定义部分
typedef struct _poly* pNode;

struct _poly {
    int coef;
    int expo;   
    pNode next; 
};

typedef pNode Poly;

Poly readPoly();
void attach(int c, int e, Poly *pRear);
int printPoly(Poly p);
void destroyPoly(Poly p);
Poly addPoly(Poly p1, Poly p2);
Poly MuttPoly(Poly p1, Poly p2);
// 实现部分
/*
打印每项系数和指数
返回值是成功打印的项数
若其为0,则为空表达式
*/
int printPoly(Poly p) {
    int cnt = 0;
    while(p) {
        printf("%d %d", p->coef, p->expo);
        cnt++;
        if(p->next != NULL) {
            printf(" ");
        } else {
            printf("\n");
        }
        p = p->next;
    }
    return cnt;
}
/*
        将项连接到链表末尾的函数
    指向pRear的指针1             pRear         last node
    [&(pRear)]      ->      [&(last node)]  ->  []
    
    指向pRear的指针2             ^
    [&(pRear)]       ------------|
    通过pRear来改变last node  
    通过指向pRear的指针来改变pRear 
    传递pRear的地址来实现
*/

void attach(int c, int e, Poly *pRear) {
    if( c == 0) //若系数为0,不添加
        return;
    Poly p = (Poly)malloc(sizeof(struct _poly));
    p->coef = c;
    p->expo = e;
    p->next = NULL;
    (*pRear)->next = p;
    *pRear = p;
}

Poly readPoly() {                                                                           
    // 表头使用一个临时的空节点
    Poly p1 = (Poly)malloc(sizeof(struct _poly));
    p1->coef = 0;
    p1->expo = 0;
    p1->next = NULL;
    // a pointer to Currnet node
    Poly pRear = p1;

    int n = 0;
    scanf("%d", &n);
    while(n--) {
        // 读入节点
        int c = 0, e = 0;
        scanf("%d %d", &c, &e);
        // 要想改变pRear值,则传入pRear的地址
        attach(c, e, &pRear);
    }
    // 删除头节点
    Poly t = p1;
    p1 = p1->next;
    free(t);
    t = NULL;
    return p1;
}

void destroyPoly(Poly p) {
    Poly tmp;
    while(p) {
        tmp = p->next;
        free(p);
        p = tmp;
    }
}

Poly addPoly(Poly p1, Poly p2) {
    // 一个临时空节点
    Poly sumPoly = (Poly)malloc(sizeof(struct _poly));
    sumPoly->coef = 0;
    sumPoly->expo = 0;
    sumPoly->next = NULL;
    Poly pt1 = p1, pt2 = p2, pts = sumPoly; //指向当前节点的指针
    while(pt1 && pt2) {
        if(pt1->expo > pt2->expo) {
            attach(pt1->coef, pt1->expo, &pts);
            pt1 = pt1->next;
        } else if(pt2->expo > pt1->expo) {
            attach(pt2->coef, pt2->expo, &pts);
            pt2 = pt2->next;
        } else {
            // 两项的指数相同,将系数相加
            int sumCoef = pt1->coef + pt2->coef;
            // 不为0,则加入节点链表
            if(sumCoef) {
                attach(sumCoef, pt1->expo, &pts);
            }
            // pt1, pt2前进
            pt1 = pt1->next;
            pt2 = pt2->next;
        }
    }
    // 将较长的一个多项式追加到末尾
    while(pt1) {
        attach(pt1->coef, pt1->expo, &pts);
        pt1 = pt1->next;
    }

    while(pt2) {
        attach(pt2->coef, pt2->expo, &pts);
        pt2 = pt2->next;
    }

    // 删除头部的空节点
    Poly t = sumPoly;
    sumPoly = sumPoly->next;
    free(t);
    t = NULL;
    return sumPoly;
}


Poly MuttPoly(Poly p1, Poly p2) {
    if(!p1 || !p2)
        return NULL;
    Poly prdPoly = (Poly)malloc(sizeof(struct _poly));
    prdPoly->coef = 0;
    prdPoly->expo = 0;
    prdPoly->next = NULL;
    Poly pt1 = p1, pt2 = p2, ptp = prdPoly;
    // 先用pt1的第一项乘pt2的所有项        
    while(pt2) {
        attach(pt1->coef * pt2->coef, pt1->expo + pt2->expo, &ptp);
        pt2 = pt2->next;
    }
    // 将随后的项目插入到得到的多项式中
    pt1 = pt1->next;
    while(pt1) {
        pt2 = p2; ptp = prdPoly;
        while(pt2) {
            int e = pt1->expo + pt2->expo;
            int c = pt1->coef * pt2->coef;
            // 查找插入的位置
            while(ptp->next && ptp->next->expo > e) {
                ptp = ptp->next;
            }
            if( ptp->next && ptp->next->expo == e) {
                // 直接加上c
                ptp->next->coef += c;
                if(!ptp->next->coef) {
                    // =0 删除该节点
                    Poly tmp = ptp->next;
                    ptp->next = tmp->next;
                    free(tmp);
                    tmp = NULL;
                }
            } else {
                // ptp->next < e 插入一个新节点
                Poly tmp = (Poly)malloc(sizeof(struct _poly));
                tmp->coef = c;
                tmp->expo = e;
                tmp->next = ptp->next;
                ptp->next = tmp;
                // 由于按照指数递减,pt1乘以下一项的指数比当前结果小,故
                // ptp指向该项,下次从这里开始搜索
                ptp = tmp;  // or ptp = ptp->next;
            }
            pt2 = pt2->next;
        }
        pt1 = pt1->next;
    }
    // 删除头部的空节点
    Poly t = prdPoly;
    prdPoly = prdPoly->next;
    free(t);
    t = NULL;
    return prdPoly;
}

int main(void) {
    Poly p1 = readPoly();
    Poly p2 = readPoly();
    Poly pSum = addPoly(p1, p2);
    Poly pPrd = MuttPoly(p1, p2);
    int c1 = printPoly(pPrd);
    if(!c1) {
        printf("0 0");
    }
    int c2 = printPoly(pSum);
    if(!c2) {
        printf("0 0");
    }
    destroyPoly(p1);
    destroyPoly(p2);
    destroyPoly(pSum);
    return 0;
}

C++实现代码

使用stl中的forward_list,没有按照格式输出,将系数和指数声明为私有成员带来了麻烦,实际上声明为私有更加
简单.

#include <forward_list>
#include <iostream>
#include <algorithm>

using namespace std;

class polyNode
{
    //声明友元
    friend polyNode* polyAdd(const polyNode*, const polyNode*);
    friend polyNode* polyMutt(const polyNode*, const polyNode*);
    friend bool operator<(const polyNode&, const polyNode&);
    friend bool operator>(const polyNode&, const polyNode&);
    friend bool operator==(const polyNode&, const polyNode&);
public:
    polyNode() : coef(0), expo(0) {}
    polyNode(int a, int b) : coef(a), expo(b) {}
    // 常量成员函数,常量对象也可以使用
    // const polyNode* const this;
    void polyPrint() const{
        cout << coef << "{X^" << expo << "} ";
    }

private:
    int coef;
    int expo;
};

polyNode* polyAdd(const polyNode* p1, const polyNode* p2) {
    if(!p1 || !p2)
        return NULL;
    if(p1->expo != p2->expo)
        return NULL;
    if(p1->coef+p2->coef) {
        // new polyNode(),对于定义了默认构造函数的类,默认初始化和值初始化相同,都调用默认构造函数
        polyNode* pSum = new polyNode;
        pSum->coef = p1->coef + p2->coef;
        pSum->expo = p1->expo;
        return pSum;
    } else {
        return NULL;
    }
}

polyNode* polyMutt(const polyNode* p1, const polyNode* p2) {
    if(!p1 || !p2)
        return NULL;
    //不会出现系数为0的情况,因为p1,p2的系数都不为0
    if(!p1->coef || !p2->coef)  return NULL;
    polyNode* pPrd = new polyNode;
    pPrd->coef = p1->coef * p2->coef;
    pPrd->expo = p1->expo + p2->expo;
    return pPrd;
}
// 在使用之前要判断p1,p2有意义
bool operator<(const polyNode& p1, const polyNode& p2) {
    return (p1.expo < p2.expo) ? true : false;
}

bool operator>(const polyNode& p1, const polyNode& p2) {
    return (p1.expo > p2.expo) ? true : false;
}
bool operator==(const polyNode& p1, const polyNode& p2) {
    return (p1.expo == p2.expo) ? true : false;
}

int main(void) {
    forward_list<polyNode*> lp1, lp2, lpSum, lpPrd;
    int n1 = 0, n2 = 0;
    int c = 0, e = 0;
    cin >> n1;
    auto prev1 = lp1.before_begin();
    while(n1--) {
        cin >> c >> e;
        polyNode* tmp = new polyNode(c, e);
        lp1.insert_after(prev1, tmp);
    }
    for_each(lp1.begin(), lp1.end(), [](const polyNode* pn){pn->polyPrint();});
    cout << endl;
    cin >> n2;
    auto prev2 = lp2.before_begin();
    while(n2--) {
        cin >> c >> e;
        polyNode* tmp = new polyNode(c, e);
        // 头插法,每次都在首前之后插入
        lp2.insert_after(prev2, tmp);
    }
    for_each(lp2.begin(), lp2.end(), [](const polyNode* pn){pn->polyPrint();});
    cout << endl;
    cout << "the sum is:" << endl;
    auto lst1 = lp1.begin();
    auto lst2 = lp2.begin();
    while(lst1 != lp1.end() && lst2 != lp2.end()) {
        if(*(*lst1) < *(*lst2)) {
            lpSum.insert_after(lpSum.before_begin(), *lst1);
            lst1++;
        } else if(*(*lst1) == *(*lst2)) {
            polyNode* tsum = polyAdd(*lst1, *lst2);
            if(tsum) {
                lpSum.insert_after(lpSum.before_begin(), tsum);
            }
            lst1++;
            lst2++;
        } else {
            lpSum.insert_after(lpSum.before_begin(), *lst2);
            lst2++;
        }
    }
    while(lst1 != lp1.end()) {
        lpSum.insert_after(lpSum.before_begin(), *lst1);
        lst1++;
    }
    while(lst2 != lp1.end()) {
        lpSum.insert_after(lpSum.before_begin(), *lst2);
        lst2++;
    }
    for_each(lpSum.begin(), lpSum.end(), [](const polyNode* pn){pn->polyPrint();});
    cout << endl;
    // 求两个多项式的积
    cout << "the product is" << endl;
    lst1 = lp1.begin();
    lst2 = lp2.begin();
    while(lst2 != lp2.end()) {
        polyNode *tprd = polyMutt(*lst1, *lst2);
        lpPrd.insert_after(lpPrd.before_begin(), tprd);
        lst2++;
    }
    lst1++;
    while(lst1 != lp1.end()) {
        lst2 = lp2.begin();
        while(lst2 != lp2.end()) {
            auto lstprev = lpPrd.before_begin();
            auto lstprd = lpPrd.begin();
            polyNode *tprd = polyMutt(*lst1, *lst2);
            while(lstprd != lpPrd.end() && *(*lstprd) > *tprd) {
                lstprd++;
                lstprev++;
            }
            if(lstprd != lpPrd.end() && *(*lstprd) == *tprd) {
                polyNode *tsum2 = polyAdd(tprd, *lstprd);
                // 释放当前项
                polyNode* tmpDel = *lstprd;
                // 后erase当前项,因为迭代器失效,
                // 返回一个被删除元素之后的迭代器
                lstprd = lpPrd.erase_after(lstprev);
                delete tmpDel;
                if(tsum2) {
                    //加和结果非0
                    // 返回一个指向最后一个插入元素的迭代器
                    lstprd = lpPrd.insert_after(lstprev, tsum2);
                }
            } else {
                //插入一个新节点
                // 1)比所有的都大,2)比所有的都小3)找到了插入了的位置
                lpPrd.insert_after(lstprev, tprd);
            }
            lst2++;
        }
        lst1++;
    }
    for_each(lpPrd.begin(), lpPrd.end(), [](const polyNode* pn){pn->polyPrint();});
    cout << endl;
    // release resource
    // 可以销毁一个const 动态对象
    for_each(lp1.begin(), lp1.end(), [](polyNode* pn){delete pn; pn = NULL;});
    for_each(lp2.begin(), lp2.end(), [](polyNode* pn){delete pn; pn = NULL;});
    for_each(lpSum.begin(), lpSum.end(), [](polyNode *pn){delete pn; pn = NULL;});
    for_each(lpPrd.begin(), lpPrd.end(), [](polyNode *pn){delete pn; pn = NULL;});
    return 0;
}