今天保研上機(jī)考快樂爆零??袱箱。出題大佬可能誤解了老年人的水平吧。
然后意識(shí)到义矛，PAT真的太新手友好了，我應(yīng)該珍惜盟萨。雖然emmmm大學(xué)科班好多年了凉翻，但是真的毫無專業(yè)能力。

一元多項(xiàng)式加法捻激、乘法題目鏈接

• 多項(xiàng)式加法乘法用數(shù)組寫起來非常愉快制轰，???考慮到應(yīng)該練習(xí)一下鏈表的操作，又怕自己參考著參考著開始照抄胞谭，寫了一個(gè)無頭節(jié)點(diǎn)鏈表的版本垃杖。就很容易出現(xiàn)段錯(cuò)誤，或者申請(qǐng)了沒有free掉的情況（尤其操作頭部丈屹、有零多項(xiàng)式的時(shí)候）调俘。
  

  真的是以時(shí)間換空間啊（特喵的寫了好久旺垒，老是有詭異的段錯(cuò)誤）

• 鏈表含頭節(jié)點(diǎn)的版本見浙大ds MOOC

• 下面的實(shí)現(xiàn)基本練習(xí)到了增（??頭）彩库、刪(??頭)、改先蒋、線性查找骇钦。

#include <cstdio>
#include <cstdlib>

struct PNode {
    int value, exp;
    PNode *next;
};
typedef PNode *Ptr2Node;
typedef Ptr2Node Expression;

/* 對(duì)m次項(xiàng)
 *  若有次數(shù)相同項(xiàng)，系數(shù)相加
 *      為0竞漾，則刪除該項(xiàng)
 *      不為0眯搭，則修改value
 *  若沒有，在最后一個(gè)次數(shù)大于m的項(xiàng)后插入
 */
void locate_and_insert(Expression &e, int exp, int val) {
    Ptr2Node p_res = e, pre = nullptr;
    while (p_res) {
        if (p_res->exp == exp) {
            //此處可以判0刪除
            p_res->value += val;
            return;
        }
        if (p_res->exp > exp) {
            pre = p_res;
            p_res = p_res->next;
        } else {
            //在pre和p_res之間插入
            Ptr2Node new_node = (Ptr2Node) malloc(sizeof(struct PNode));
            new_node->exp = exp, new_node->value = val;
            new_node->next = p_res;
            if (pre)
                pre->next = new_node;
            else e = new_node;
            return;
        }
    }
    // 當(dāng)前項(xiàng)次數(shù)比目前表達(dá)式結(jié)果中項(xiàng)的次數(shù)都要低业岁，在末尾插入 (pre不可能為空)
    Ptr2Node new_node = (Ptr2Node) malloc(sizeof(struct PNode));
    new_node->exp = exp, new_node->value = val;
    if (pre) pre->next = new_node;
    else e = new_node;
}

void delete_0_term(Expression &e) {
    // 注意：零多項(xiàng)式鳞仙、常數(shù)多項(xiàng)式！＿督蟆繁扎！
    Ptr2Node curr = e, pre = nullptr;
    while (curr != nullptr) {
        if (curr->value == 0) {
            if (pre) {
                pre->next = curr->next;
                free(curr);
            } else e = e->next;
        }
        pre = curr;
        curr = curr->next;
    }
}

// with no head_node
Expression read_poly() {
    Expression e = (Expression) malloc(sizeof(struct PNode));
    e->next = nullptr;
    Ptr2Node curr = e, rear = nullptr;
    int tn, val, power;
    scanf("%d", &tn);
    for (int i = 0; i < tn; ++i) {
        scanf("%d%d", &val, &power);
        curr->value = val, curr->exp = power;
        rear = curr;
        curr->next = (Ptr2Node) malloc(sizeof(PNode));
        curr = curr->next;
    }
    free(curr);// 坑點(diǎn)：需要把curr的上一個(gè)節(jié)點(diǎn)的next置為null（rear的作用）
    if (rear) rear->next = nullptr;
    else e = nullptr;
    return e;
}

Expression add(Expression e1, Expression e2) {
    Expression res = (Expression) malloc(sizeof(struct PNode));
    Ptr2Node p1 = e1, p2 = e2, p_res = res, rear = nullptr;
    while (p1 && p2) {
        if (p1->exp == p2->exp) {
            if (p1->value + p2->value != 0) {
                p_res->value = p1->value + p2->value;
                p_res->exp = p1->exp;
                rear = p_res;
                p_res->next = (Ptr2Node) malloc(sizeof(struct PNode));
                p_res = p_res->next;
            }
            p1 = p1->next;
            p2 = p2->next;
        } else if (p1->exp > p2->exp) {
            p_res->value = p1->value;
            p_res->exp = p1->exp;
            rear = p_res;
            p1 = p1->next;
            p_res->next = (Ptr2Node) malloc(sizeof(struct PNode));
            p_res = p_res->next;
        } else {
            p_res->value = p2->value;
            p_res->exp = p2->exp;
            rear = p_res;
            p2 = p2->next;
            p_res->next = (Ptr2Node) malloc(sizeof(struct PNode));
            p_res = p_res->next;
        }
    }
    free(p_res);
    if (rear) rear->next = nullptr;
    else res->next = nullptr;
    if (p1) {
        if (rear) rear->next = p1;
        else res = p1;
    } else if (p2) {
        if (rear) rear->next = p2;
        else res = p2;
    }
    return res;
}

void print_expression(Expression e) {
    Ptr2Node curr = e;
    if (curr == nullptr) {
        puts("0 0");
        return;
    }
    // with no head_node
    while (curr != nullptr) {
        printf("%d %d", curr->value, curr->exp);
        curr = curr->next;
        printf(curr != nullptr ? " " : "\n");
    }
}

/* 好xx麻煩
 * 先用e1的term1和e2所有項(xiàng)相乘，形成一個(gè)多項(xiàng)式，
 * 以此多項(xiàng)式為基礎(chǔ)做插入操作(伴隨著對(duì)次數(shù)的查找梳玫，同次的系數(shù)相加)
 * 相加后結(jié)果為0的話爹梁，刪除節(jié)點(diǎn)（練習(xí)刪除= =，或者可以保留提澎，在打印結(jié)果時(shí)跳過系數(shù)為0的項(xiàng)）
 * */
Expression multiply(Expression e1, Expression e2) {
    Expression res = (Expression) malloc(sizeof(struct PNode));
    Ptr2Node p1 = e1, p2 = e2, p_res = res, rear = nullptr;
    if (p1) {
        while (p2) {
            p_res->exp = p1->exp + p2->exp;
            p_res->value = p1->value * p2->value;
            p2 = p2->next;
            p_res->next = (Ptr2Node) malloc(sizeof(struct PNode));
            rear = p_res;
            p_res = p_res->next;
        }
    }
    free(p_res);
    if (rear) rear->next = nullptr;
    if (p1) p1 = p1->next;
    while (p1) {
        p2 = e2;
        while (p2) {
            int t_val = p1->value * p2->value, t_exp = p1->exp + p2->exp;
            locate_and_insert(res, t_exp, t_val);
            p2 = p2->next;
        }
        p1 = p1->next;
    }
    delete_0_term(res);
    return res;
}

int main() {
    Expression e1, e2, add_e, mult_e;
    e1 = read_poly();
    e2 = read_poly();
    mult_e = multiply(e1, e2);
    print_expression(mult_e);
    add_e = add(e1, e2);
    print_expression(add_e);
    return 0;
}

測試點(diǎn)情況23333