链表——多项式加法

# 链表——多项式加法

#include <iostream>
using namespace std;
struct PolyNode {
    int coef;
    int expon;
    struct PolyNode* link;
};
typedef struct PolyNode* Polynomial;

void Attach(int coef, int expon, Polynomial* pRear) {
    Polynomial P;
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->coef = coef; P->expon = expon; P->link = NULL;
    (*pRear)->link = P;
    *pRear = P;
}

int Compare(int expon1, int expon2) {
    if (expon1 == expon2)    return 0;
    else if (expon1 > expon2)    return 1;
    else     return -1;
}

Polynomial AddPoly(Polynomial P1, Polynomial P2) {
    Polynomial front, rear, temp;
    int sum;  //无需初始化
    rear = (Polynomial)malloc(sizeof(struct PolyNode));
    //rear->link=NULL; 需要加，因为Attach()会改变rear->link
    front = rear;
    while (P1 && P2) {
        switch (Compare(P1->expon, P2->expon)) {
        case 0:  //指数相等 
            sum = P1->coef + P2->coef;
            if (sum) {
                Attach(sum, P1->expon, &rear);
                P1 = P1->link;
                P2 = P2->link;
            }
            else {
                P1 = P1->link;
                P2 = P2->link;
            }
            break; //别忘了
        case 1:
            Attach(P1->coef, P1->expon, &rear);
            P1 = P1->link;
            break;
        case -1:
            Attach(P2->coef, P2->expon, &rear);
            P2 = P2->link;
            break;
        }
    }
    for (; P1; P1 = P1->link)    Attach(P1->coef, P1->expon, &rear);
    for (; P2; P2 = P2->link)    Attach(P2->coef, P2->expon, &rear);
    rear->link = NULL;
    //三行代码free头节点
    temp = front;
    front = front->link;
    free(temp);

    return front;    //别忘了
}

Polynomial ReadPoly() { //读入多项式
    Polynomial front, rear, temp;
    int n, coef, expon;
    rear = (Polynomial)malloc(sizeof(struct PolyNode));
    rear->link = NULL;
    front = rear;

    cin >> n;
    while (n--) {
        cin >> coef >> expon;
        Attach(coef, expon, &rear);
    }

    temp = front;
    front = front->link;
    free(temp);

    return front;
}

void PrintPoly(Polynomial P) {
    int flag = 0;  //调整输出格式
    if (!P) {
        cout << 0 << " " << 0;
        return;
    }
    while (P) {
        if (!flag)
            flag = 1;
        else
            cout << " ";
        cout << P->coef << " " << P->expon;
        P = P->link;
    }
}

int main()
{
    Polynomial P1, P2;
    P1 = ReadPoly();
    P2 = ReadPoly();
    PrintPoly(AddPoly(P1, P2));
    return 0;
}

输入样例

4 3 4 -5 2 6 1 -2 0

3 5 20 -7 4 3 1

输出样例

笔记

1.计数器：什么时候把n– P=P->link等操作写入while()? 在函数作用域内不对当前值进行操作时。

2.生成新节点,必P->Link=NULL;

3.链表插入思路：生成新节点，让rear连结新节点