02-線性結構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           

例子輸入與輸出：

序号	輸入	輸出
1	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
2	2 1 2 1 0 2 1 2 -1 0	1 4 -1 0 2 2
3	2 -1000 1000 1000 0 2 1000 1000 -1000 0	-1000000 2000 2000000 1000 -1000000 0 0 0
4	1 999 1000	999 1000

/*!
 * \file 02-線性結構2 一進制多項式的乘法與加法運算.cpp
 *
 * \author ranjiewen
 * \date 2017/03/19 16:11
 *
 * 
 */
   

//動态數組實作較好

//用連結清單設計

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

typedef struct PolyNode* Polynomial;

struct PolyNode{
    int coef;
    int expon;
    Polynomial next;
};

Polynomial ReadPoly();
Polynomial Mult(Polynomial P1,Polynomial P2);
void PrintPoly(Polynomial PP);
Polynomial Add(Polynomial P1,Polynomial P2);

int main() //程式架構搭建
{
    Polynomial P1, P2, PP, PS;
    P1 = ReadPoly();
    P2 = ReadPoly();

    PP = Mult(P1, P2);
    PrintPoly(PP);

    PS = Add(P1, P2);
    PrintPoly(PS);

    return 0;
}

//對Rear指針的處理：1.初值為NULL,根據是否為空做不同處理；2.指向一個空節點
//*pRear目前結果表達式尾項指針的指針
//函數實作在pRear後面插入節點
void Attach(int c, int e, Polynomial *pRear)  
{
    Polynomial P;
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->coef = c;
    P->expon = e;
    P->next = NULL;
    (*pRear)->next = P;
    *pRear = P;
}

Polynomial ReadPoly()
{
    Polynomial P, Rear, t;
    int c, e, N;
    scanf("%d", &N);
    P = (Polynomial)malloc(sizeof(struct PolyNode)); //連結清單頭空節點
    P->next = NULL;
    Rear = P; 
    while (N--)
    {
        scanf("%d %d", &c, &e);
        if (c != 0)  
           Attach(c, e, &Rear); //将目前項插入多項式尾部
    }
    t = P;
    P = P->next;
    free(t); //删除臨時生成的頭結點
    return P;
}

Polynomial Add(Polynomial P1, Polynomial P2)
{
    Polynomial t1, t2;
    t1 = P1;
    t2 = P2;
    //生成新的頭結點
    Polynomial P,t;
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->next = NULL;
    Polynomial Rear;
    Rear = P;
    while (t1&&t2)
    {
        if (t1->expon==t2->expon)
        {
            if (t1->coef+t2->coef)  //系數和為0時不添加到尾節點上  /*考慮周全*/
            {
                Attach(t1->coef + t2->coef, t1->expon, &Rear);
            }
            t1 = t1->next;
            t2 = t2->next;
        }
        else if (t1->expon>t2->expon)
        {
            Attach(t1->coef, t1->expon, &Rear);
            t1=t1->next;
        }else 
        {
            Attach(t2->coef, t2->expon, &Rear);
            t2 = t2->next;
        }
    }
    while (t1)
    {
        Attach(t1->coef, t1->expon, &Rear);
        t1 = t1->next;
    }
    while (t2)
    {
        Attach(t2->coef, t2->expon, &Rear);
        t2 = t2->next;
    }
    t = P;
    P = P->next;
    free(t);
    return P;
}

//多項式乘法方法：
//1. 将乘法運算轉換為加法運算，讓P1的每一項和P2相乘，在加到結果多項式中
//2. 逐項插入，将P1目前項乘P2目前項，在插入到結果表達式中，關鍵是要找到插入的位置

Polynomial Mult(Polynomial P1, Polynomial P2)
{
    Polynomial P, Rear;
    Polynomial t1, t2, t;
    if (!P1||!P2)
    {
        return NULL;
    }
    t1 = P1;
    t2 = P2;
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    Rear = P;
    while (t2)
    {
        //先用P1的第一項乘以P2,得到初始結果多項式
        Attach(t1->coef*t2->coef, t1->expon + t2->expon, &Rear);
        t2 = t2->next;
    }
    t1 = t1->next;
    while (t1)
    {
        t2 = P2;
        Rear = P; //将尾節點置到頭結點來
        while (t2)
        {
            int e = t1->expon + t2->expon;
            int c = t1->coef * t2->coef;   //以後的每一項相乘的結果
            while (Rear->next&&Rear->next->expon>e) //找插入位置
            {
                Rear = Rear->next;
            }
            if (Rear->next&&Rear->next->expon==e)
            {
                if (Rear->next->coef+c) //判系數是否為0
                {
                    Rear->next->coef += c;
                }
                else  //為0删除節點
                {
                    t = Rear->next;
                    Rear->next = t->next;
                    free(t);
                }
            }
            else  //插入位置
            {
                t = (Polynomial)malloc(sizeof(struct PolyNode));
                t->coef = c;
                t->expon = e;
                t->next = Rear->next;
                Rear->next = t;

                Rear = Rear->next;
            }
            t2 = t2->next;
        }
        t1 = t1->next;
    }
    t2 = P;
    P = P->next;
    free(t2);

    return P;
}

void PrintPoly(Polynomial P)
{
    int flag = 0;//輔助調整輸出格式
    if (!P)
    {
        printf("0 0\n"); /*格式*/
        return;
    }
    while (P)
    {
        if (!flag) //第一次
        {
            flag = 1;
        }
        else
        {
            printf(" ");
        }
        printf("%d %d", P->coef, P->expon);
        P = P->next;
    }
    printf("\n");
}      

reference：[PAT] 02-線性結構2 一進制多項式的乘法與加法運算

C/C++基本文法學習

STL

C++ primer