无头节点链表实现 | 一元多项式加法、乘法

今天保研上机考快乐爆零😊。出题大佬可能误解了老年人的水平吧。
然后意识到，PAT真的太新手友好了，我应该珍惜。虽然emmmm大学科班好多年了，但是真的毫无专业能力。

一元多项式加法、乘法题目链接

• 多项式加法乘法用数组写起来非常愉快，🤔️考虑到应该练习一下链表的操作，又怕自己参考着参考着开始照抄，写了一个无头节点链表的版本。就很容易出现段错误，或者申请了没有free掉的情况（尤其操作头部、有零多项式的时候）。
  

  真的是以时间换空间啊（特喵的写了好久，老是有诡异的段错误）

• 链表含头节点的版本见浙大ds MOOC

• 下面的实现基本练习到了增（⚠️头）、删(⚠️头)、改、线性查找。

#include <cstdio>
#include <cstdlib>

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

/* 对m次项
 *  若有次数相同项，系数相加
 *      为0，则删除该项
 *      不为0，则修改value
 *  若没有，在最后一个次数大于m的项后插入
 */
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;
        }
    }
    // 当前项次数比目前表达式结果中项的次数都要低，在末尾插入 (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) {
    // 注意：零多项式、常数多项式！！！
    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);// 坑点：需要把curr的上一个节点的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所有项相乘，形成一个多项式，
 * 以此多项式为基础做插入操作(伴随着对次数的查找，同次的系数相加)
 * 相加后结果为0的话，删除节点（练习删除= =，或者可以保留，在打印结果时跳过系数为0的项）
 * */
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;
}