題目詳情：

設(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í)課本上講過了，就是分別遍歷L1和L2，

（1）兩者如果指數(shù)不等則將指數(shù)大的節(jié)點(diǎn)加入新鏈表，同時(shí)移動(dòng)新鏈表與加入節(jié)點(diǎn)的指針;

（2）兩者如果指數(shù)相等則系數(shù)相加，同時(shí)要判斷兩者是否為0，不為0時(shí)再把合并后接入新鏈表

（3）如果最后L1或L2有多余直接一次性接入

本題難點(diǎn)在于乘法

我的思路是利用之前實(shí)現(xiàn)的多項(xiàng)式加法函數(shù)，將多項(xiàng)式乘法轉(zhuǎn)化為多項(xiàng)式加法

（1）用L1的每一項(xiàng)乘整個(gè)L2，得到一個(gè)多項(xiàng)式

（2）將新得到的多項(xiàng)式與L1前一項(xiàng)與整個(gè)L2相乘結(jié)果相加

如此便可以得到最終乘法結(jié)果

第一次寫錯(cuò)誤：

（1）每次遍歷鏈表時(shí)都會(huì)忘記移動(dòng)指針

（2）題目要求0多項(xiàng)式輸出0 0 ，所以首先系數(shù)如果是0就不要加入鏈表，最后如果鏈表為空打印鏈表時(shí)打印 0 0文章來源地址http://www.zghlxwxcb.cn/news/detail-536317.html

代碼實(shí)現(xiàn)：

#include <stdio.h>
#include <stdlib.h>
/*鏈表表示多項(xiàng)式的數(shù)據(jù)結(jié)構(gòu)*/
typedef struct ListNode ListNode;
typedef ListNode* List;
struct ListNode {
    int Coefficient, Exponent;
    List Next;
};
/*實(shí)現(xiàn)尾插法的函數(shù)*/
void Attach(int coef, int expo, List* rear) {   //傳rear地址的原因是因?yàn)橐诤瘮?shù)里修改main函數(shù)必須通過地址進(jìn)行
    List newNode = (List)malloc(sizeof(ListNode));
    newNode->Coefficient = coef;
    newNode->Exponent = expo;
    (*rear)->Next = newNode;
    (*rear) = (*rear)->Next;
    (*rear)->Next = NULL;
}
/*用到尾插法構(gòu)造鏈表的函數(shù)*/
List CreateList(int degree) {
    List dummyHead = (List)malloc(sizeof(ListNode)); //多項(xiàng)式虛擬頭結(jié)點(diǎn)
    List rear = dummyHead;
    rear->Next = NULL;
    for(int i = 0; i < degree; i++) {  //創(chuàng)建多項(xiàng)式鏈表
        int coef, expo;
        scanf("%d %d", &coef, &expo);
        if(coef == 0) continue;
        Attach(coef, expo, &rear);
    }
    return dummyHead;
}


/*打印鏈表*/
void PrintList(List L) {
    List ptr = L->Next;
    if(ptr == NULL) printf("0 0");
    while(ptr) {
        printf("%d %d", ptr->Coefficient, ptr->Exponent);
        if(ptr->Next) printf(" ");
        ptr = ptr->Next;
    }
    return;
}
/*刪除鏈表*/
void DeleteList(List L) {
    List ptr = L->Next;
    while(ptr) {
        List tmp = ptr;
        ptr = ptr->Next;
        free(tmp);
    }
    free(L);
    return;
}
/*多項(xiàng)式加法,參數(shù)是兩個(gè)鏈表頭指針，不能操作傳進(jìn)來的鏈表*/
List AddPolynomial(List L1, List L2) {
    List dummyHead = (List)malloc(sizeof(ListNode));
    dummyHead->Next = NULL;
    List rear = dummyHead, ptr1 = L1->Next, ptr2 = L2->Next;
    while(ptr1 && ptr2) {
        int expo1 = ptr1->Exponent, expo2 = ptr2->Exponent;
        int coef1 = ptr1->Coefficient, coef2 = ptr2->Coefficient;
        if(expo1 > expo2) {
            Attach(coef1, expo1, &rear);
            ptr1 = ptr1->Next;
        }
        else if(expo1 < expo2) {
            Attach(coef2, expo2, &rear);
            ptr2 = ptr2->Next;
        }
        else {
            if((coef1 + coef2)) {
                Attach(coef1 + coef2, expo1, &rear);
            }
            ptr1 = ptr1->Next;
            ptr2 = ptr2->Next;
        }
    }
    
    if(ptr1) {
        while(ptr1) {
            Attach(ptr1->Coefficient, ptr1->Exponent, &rear);
            ptr1 = ptr1->Next;
        }
    }
    if(ptr2) {
        while(ptr2) {
            Attach(ptr2->Coefficient, ptr2->Exponent, &rear);
            ptr2 = ptr2->Next;
        }
    }
    return dummyHead;
}
/*多項(xiàng)式乘法，參數(shù)是兩個(gè)鏈表頭指針，不能操作傳進(jìn)來的鏈表*/
List ProductPolynomial(List L1, List L2) {
    List dummyHead = (List)malloc(sizeof(ListNode));
    List ptr0 = dummyHead, ptr1 = L1->Next, ptr2 = L2->Next;
    ptr0->Next = NULL;
    while(ptr2) {  
        int polyCoef2 = ptr2->Coefficient, polyExpo2 = ptr2->Exponent;
        List dummyHeadTmp = (List)malloc(sizeof(ListNode));
        List ptrTmp = dummyHeadTmp;
        ptrTmp->Next = NULL;
        while(ptr1) {   //將L2的每一項(xiàng)取出來，與L1相乘，得到一條tmp多項(xiàng)式鏈表
            int polyCoef1 = ptr1->Coefficient, polyExpo1 = ptr1->Exponent;
            int polyCoefTmp = polyCoef1 * polyCoef2;
            int polyExpoTmp = polyExpo1 + polyExpo2;
            if(polyCoefTmp == 0) continue;
            Attach(polyCoefTmp, polyExpoTmp, &ptrTmp);
            ptr1 = ptr1->Next;
        }
        dummyHead = AddPolynomial(dummyHead, dummyHeadTmp); //將這條tmp鏈表累加到結(jié)果鏈表上即可得到多項(xiàng)式乘法結(jié)果
        DeleteList(dummyHeadTmp);   //釋放tmp鏈表
        ptr1 = L1->Next;            //將ptr1重新指向L1
        ptr2 = ptr2->Next;          //ptr2指向L2的下一項(xiàng)
    }
    return dummyHead;
}
int main() {
    int degree1;
    scanf("%d", &degree1);
    List polynomial1 = CreateList(degree1);
    int degree2;
    scanf("%d", &degree2);
    List polynomial2 =  CreateList(degree2);
    List polynomialAdd = AddPolynomial(polynomial1, polynomial2);
    List polynomialPtrduct = ProductPolynomial(polynomial1, polynomial2);
    PrintList(polynomialPtrduct);
    printf("\n");
    PrintList(polynomialAdd);
    DeleteList(polynomial1);
    DeleteList(polynomial2);
    DeleteList(polynomialAdd);
    return 0;
}

到了這里，關(guān)于浙大數(shù)據(jù)結(jié)構(gòu)第二周02-線性結(jié)構(gòu)2 一元多項(xiàng)式的乘法與加法運(yùn)算的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！