PAT 解题报告 (数据结构学习与实验指导) 3-04. 一元多项式的乘法与加法运算

题目描述:

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

算法分析:

数据结构选择链表吧, 然后模拟多项式的乘法和加法就可以了. 容易出错的地方应该是:在乘法的时候(其实也是退化成做加法), 有可能这次乘法得到的某一项和之前的部分乘法的和里面的某一项正好抵消, 那么要注意在结果中删除这个系数是0的项. 比如(x^2 +1 ) *(x^2-1) 就是先得到了x^4 – x^2 然后再加上x^2 – 1于是x^2项就被抵消了. 这一点要特别注意.

实现加法的代码可以参考(乘法类似, 也是退化到做加法而已):

// result = l1 + l2
void add_list(list<ListNode> &l1, list<ListNode> &l2, list<ListNode> &result) {
    itr1 = l1.begin();
    itr2 = l2.begin();

    while(itr1 != l1.end() && itr2 != l2.end()) {
        if(itr1->exponent < itr2->exponent)
            result.push_back(*(itr2++));
        else if(itr1->exponent == itr2->exponent) {
            ListNode node(itr1->coefficient + itr2->coefficient, itr1->exponent);
            if(node.coefficient) result.push_back(node);
            ++itr1;
            ++itr2;
        }
        else
            result.push_back(*(itr1++));
    }
    while(itr1 != l1.end()) result.push_back(*(itr1++));
    while(itr2 != l2.end()) result.push_back(*(itr2++));
}

注意点:

注意算法分析里面提到的做乘法的时候注意两项相消的问题就可以了.

Written on August 3, 2013