題目簡(jiǎn)述

設(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

基本思路

以數(shù)組結(jié)構(gòu)的方式構(gòu)造多項(xiàng)式，并設(shè)計(jì)以下函數(shù)：

• 兩個(gè)多項(xiàng)式相加：逐項(xiàng)比對(duì)，指數(shù)較大者放置項(xiàng)；指數(shù)相等時(shí)系數(shù)相加；一個(gè)多項(xiàng)式所有項(xiàng)放置完后直接放置另一個(gè)多項(xiàng)式的剩余項(xiàng)；
• 多項(xiàng)式乘單項(xiàng)式：每一項(xiàng)指數(shù)相加，系數(shù)相乘即可；
• 多項(xiàng)式乘多項(xiàng)式：逐項(xiàng)進(jìn)行多項(xiàng)式乘單項(xiàng)式；
• 特殊情形：存在零多項(xiàng)式時(shí)，乘積結(jié)果為0；

代碼

#include <iostream>
using namespace std;

/**
 多項(xiàng)式每一項(xiàng)的數(shù)據(jù)結(jié)構(gòu)
 */
typedef struct{
    int coef;
    int expo;
} poly;

/**
讀取多項(xiàng)式

 @param length 多項(xiàng)式長(zhǎng)度
 @param p 多項(xiàng)式數(shù)組地址
 @return 多項(xiàng)式數(shù)組地址
 */
poly* ScanfPoly(int length,poly *p){
    for (int i=0; i<length; i++) {
        cin>>p[i].coef>>p[i].expo;
    }
    return p;
}

/**
 輸出多項(xiàng)式

 @param length 要輸出的多項(xiàng)式長(zhǎng)度
 @param p 要輸出的多項(xiàng)式數(shù)組地址
 */
void PrintPoly(int length,poly *p){
    bool flag=false;
    /*輸出第一項(xiàng)*/
    if(p->coef!=0){//只輸出非零項(xiàng)
        printf("%d %d",p->coef,p->expo);
        flag=true;
    }
    /*依次輸出后面的每一項(xiàng)*/
    poly *pol=p+1;
    while (pol<(p+length)) {
        if(pol->coef!=0) {
            printf(" %d %d",pol->coef,pol->expo);
            flag=true;
        }
        pol++;
    }
    /*如果沒輸出過任何項(xiàng)，輸出0 0*/
    if(flag==false)printf("0 0");
}

/**
 多項(xiàng)式的加法運(yùn)算

 @param p1 多項(xiàng)式1
 @param l1 多項(xiàng)式1的項(xiàng)數(shù)
 @param p2 多項(xiàng)式2
 @param l2 多項(xiàng)式2的項(xiàng)數(shù)
 @param is 接收和多項(xiàng)式項(xiàng)數(shù)的值
 @return 和多項(xiàng)式的地址
 */
poly* PlusPoly(poly *p1,int l1,poly *p2,int l2,int &is){
    poly *sum=(poly*)malloc((l1+l2)*sizeof(poly));

    int i1,i2;
    for (i1=0,i2=0,is=0; i1<l1 || i2<l2; is++) {
        if(i2>=l2 || p1[i1].expo>p2[i2].expo){
            sum[is]=p1[i1];
            i1++;
        }
        else if(i1>=l1 || p1[i1].expo<p2[i2].expo){
            sum[is]=p2[i2];
            i2++;
        }
        else if(p1[i1].expo==p2[i2].expo){
            sum[is].expo=p1[i1].expo;
            sum[is].coef=p1[i1].coef+p2[i2].coef;
            i1++;
            i2++;
        }
    }
    return sum;
}

bool polyComplare(poly p1,poly p2){
    return (p1.expo>p2.expo);
}

/**
 單項(xiàng)式乘多項(xiàng)式

 @param p1 單項(xiàng)式
 @param p2 多項(xiàng)式
 @param l2 多項(xiàng)式的項(xiàng)數(shù)
 @return 多項(xiàng)式的地址
 */
poly* multiOnePoly(poly p1,poly *p2,int l2){
    poly *proPoly=(poly*)malloc(l2*sizeof(poly));
    for (int i=0; i<l2; i++) {
        proPoly[i].coef = p2[i].coef*p1.coef;
        proPoly[i].expo = p2[i].expo+p1.expo;
    }
    return proPoly;
}

/**
 多項(xiàng)式乘多項(xiàng)式（??！不能有零多項(xiàng)式）

 @param p1 多項(xiàng)式1
 @param l1 多項(xiàng)式1的長(zhǎng)度
 @param p2 多項(xiàng)式2
 @param l2 多項(xiàng)式2的長(zhǎng)度
 @param lpro 要接收的積多項(xiàng)式的長(zhǎng)度
 @return 積多項(xiàng)式
 */
poly* MultiplyPoly(poly *p1,int l1,poly *p2,int l2,int &lpro){
    poly *AllProductPoly;
    lpro=0;
    int lengthPro=0;
    for (int i=0; i<l1; i++) {
        poly* SingleProductPoly;
        SingleProductPoly=multiOnePoly(p1[i], p2, l2);//求出p2與p1的每一項(xiàng)相乘的積多項(xiàng)式
        
        /*總積多項(xiàng)式必須放后面*/
        AllProductPoly=PlusPoly(SingleProductPoly, l2, AllProductPoly, lpro, lengthPro);
        free(SingleProductPoly);//手動(dòng)釋放內(nèi)存空間，后同
        
        lpro=lengthPro;
    }
    return AllProductPoly;
}

int main(int argc, const char * argv[]) {
    /*讀取多項(xiàng)式1和多項(xiàng)式2*/
    int K1,K2;
    cin>>K1;
    poly *p1=(poly*)malloc(K1*sizeof(poly));
    ScanfPoly(K1,p1);

    cin>>K2;
    poly *p2=(poly*)malloc(K2*sizeof(poly));
    ScanfPoly(K2,p2);
    
    
    /*求積*/
    if(K1!=0 && K2!=0){
        poly *productPoly;
        int lpro=0;
        productPoly=MultiplyPoly(p1, K1, p2, K2, lpro);
        PrintPoly(lpro, productPoly);
        free(productPoly);
        cout<<'\n';
    }else printf("0 0\n");
    
    /*求和*/
    poly *sumPoly;
    int lsum;
    sumPoly=PlusPoly(p1, K1, p2, K2, lsum);
    PrintPoly(lsum, sumPoly);
    free(sumPoly);
}