設(shè)計(jì)函數(shù)分別求兩個(gè)一元多項(xiàng)式的乘積與和媒熊。

輸入格式:

輸入分2行谋作，每行分別先給出多項(xiàng)式非零項(xiàng)的個(gè)數(shù)州疾，再以指數(shù)遞降方式輸入一個(gè)多項(xiàng)式非零項(xiàng)系數(shù)和指數(shù)（絕對(duì)值均為不超過1000的整數(shù)）裳食。數(shù)字間以空格分隔。

輸出格式:

輸出分2行焦影，分別以指數(shù)遞降方式輸出乘積多項(xiàng)式以及和多項(xiàng)式非零項(xiàng)的系數(shù)和指數(shù)。數(shù)字間以空格分隔封断，但結(jié)尾不能有多余空格斯辰。零多項(xiàng)式應(yīng)輸出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語言實(shí)現(xiàn)代碼

/*
    先給出項(xiàng)數(shù),隨后以指數(shù)遞降的方式給出系數(shù)和指數(shù)
    一共兩行,
    輸出兩個(gè)多項(xiàng)式的和與乘積
    由于給出了項(xiàng)數(shù),可以使用動(dòng)態(tài)數(shù)組來存儲(chǔ)
*/

#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);
// 實(shí)現(xiàn)部分
/*
打印每項(xiàng)系數(shù)和指數(shù)
返回值是成功打印的項(xiàng)數(shù)
若其為0,則為空表達(dá)式
*/
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;
}
/*
        將項(xiàng)連接到鏈表末尾的函數(shù)
    指向pRear的指針1             pRear         last node
    [&(pRear)]      ->      [&(last node)]  ->  []
    
    指向pRear的指針2             ^
    [&(pRear)]       ------------|
    通過pRear來改變last node  
    通過指向pRear的指針來改變pRear 
    傳遞pRear的地址來實(shí)現(xiàn)
*/

void attach(int c, int e, Poly *pRear) {
    if( c == 0) //若系數(shù)為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() {                                                                           
    // 表頭使用一個(gè)臨時(shí)的空節(jié)點(diǎn)
    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--) {
        // 讀入節(jié)點(diǎn)
        int c = 0, e = 0;
        scanf("%d %d", &c, &e);
        // 要想改變pRear值,則傳入pRear的地址
        attach(c, e, &pRear);
    }
    // 刪除頭節(jié)點(diǎn)
    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) {
    // 一個(gè)臨時(shí)空節(jié)點(diǎn)
    Poly sumPoly = (Poly)malloc(sizeof(struct _poly));
    sumPoly->coef = 0;
    sumPoly->expo = 0;
    sumPoly->next = NULL;
    Poly pt1 = p1, pt2 = p2, pts = sumPoly; //指向當(dāng)前節(jié)點(diǎn)的指針
    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 {
            // 兩項(xiàng)的指數(shù)相同,將系數(shù)相加
            int sumCoef = pt1->coef + pt2->coef;
            // 不為0,則加入節(jié)點(diǎn)鏈表
            if(sumCoef) {
                attach(sumCoef, pt1->expo, &pts);
            }
            // pt1, pt2前進(jìn)
            pt1 = pt1->next;
            pt2 = pt2->next;
        }
    }
    // 將較長的一個(gè)多項(xiàng)式追加到末尾
    while(pt1) {
        attach(pt1->coef, pt1->expo, &pts);
        pt1 = pt1->next;
    }

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

    // 刪除頭部的空節(jié)點(diǎn)
    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的第一項(xiàng)乘pt2的所有項(xiàng)        
    while(pt2) {
        attach(pt1->coef * pt2->coef, pt1->expo + pt2->expo, &ptp);
        pt2 = pt2->next;
    }
    // 將隨后的項(xiàng)目插入到得到的多項(xiàng)式中
    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 刪除該節(jié)點(diǎn)
                    Poly tmp = ptp->next;
                    ptp->next = tmp->next;
                    free(tmp);
                    tmp = NULL;
                }
            } else {
                // ptp->next < e 插入一個(gè)新節(jié)點(diǎn)
                Poly tmp = (Poly)malloc(sizeof(struct _poly));
                tmp->coef = c;
                tmp->expo = e;
                tmp->next = ptp->next;
                ptp->next = tmp;
                // 由于按照指數(shù)遞減,pt1乘以下一項(xiàng)的指數(shù)比當(dāng)前結(jié)果小,故
                // ptp指向該項(xiàng),下次從這里開始搜索
                ptp = tmp;  // or ptp = ptp->next;
            }
            pt2 = pt2->next;
        }
        pt1 = pt1->next;
    }
    // 刪除頭部的空節(jié)點(diǎn)
    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++實(shí)現(xiàn)代碼

使用stl中的forward_list,沒有按照格式輸出,將系數(shù)和指數(shù)聲明為私有成員帶來了麻煩,實(shí)際上聲明為私有更加
簡單.

#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) {}
    // 常量成員函數(shù),常量對(duì)象也可以使用
    // 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(),對(duì)于定義了默認(rèn)構(gòu)造函數(shù)的類,默認(rèn)初始化和值初始化相同,都調(diào)用默認(rèn)構(gòu)造函數(shù)
        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;
    //不會(huì)出現(xiàn)系數(shù)為0的情況,因?yàn)閜1,p2的系數(shù)都不為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;
    // 求兩個(gè)多項(xiàng)式的積
    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);
                // 釋放當(dāng)前項(xiàng)
                polyNode* tmpDel = *lstprd;
                // 后erase當(dāng)前項(xiàng),因?yàn)榈魇?
                // 返回一個(gè)被刪除元素之后的迭代器
                lstprd = lpPrd.erase_after(lstprev);
                delete tmpDel;
                if(tsum2) {
                    //加和結(jié)果非0
                    // 返回一個(gè)指向最后一個(gè)插入元素的迭代器
                    lstprd = lpPrd.insert_after(lstprev, tsum2);
                }
            } else {
                //插入一個(gè)新節(jié)點(diǎn)
                // 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
    // 可以銷毀一個(gè)const 動(dòng)態(tài)對(duì)象
    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;
}