【PTA数据结构 | C语言版】一元多项式的乘法运算

本专栏持续输出数据结构题目集，欢迎订阅。

题目

请设计实现两个链式存储的一元多项式乘法运算的算法，并分析该算法的时间复杂度。

输入格式：
输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过 1000 的整数）。数字间以空格分隔。

输出格式：
在一行中以指数递降方式输出乘积多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出 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

代码

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

typedef struct PolyNode *Polynomial;
struct PolyNode {
    int coef;
    int exp;
    Polynomial link;
};

// 创建新节点
Polynomial createNode(int coef, int exp) {
    Polynomial p = (Polynomial)malloc(sizeof(struct PolyNode));
    p->coef = coef;
    p->exp = exp;
    p->link = NULL;
    return p;
}

// 读取多项式
Polynomial readPoly() {
    int n, coef, exp;
    scanf("%d", &n);
    Polynomial head = NULL, rear = NULL;
    
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &coef, &exp);
        if (coef == 0) continue;  // 跳过系数为0的项
        
        Polynomial p = createNode(coef, exp);
        if (!head) head = rear = p;
        else {
            rear->link = p;
            rear = p;
        }
    }
    return head;
}

// 插入乘积项到结果多项式（按指数降序）
void insert(Polynomial *head, int coef, int exp) {
    if (coef == 0) return;  // 系数为0不插入
    
    Polynomial p = createNode(coef, exp);
    if (!(*head) || exp > (*head)->exp) {
        p->link = *head;
        *head = p;
    } else {
        Polynomial prev = *head;
        Polynomial curr = prev->link;
        
        while (curr && exp < curr->exp) {
            prev = curr;
            curr = curr->link;
        }
        
        if (curr && exp == curr->exp) {
            curr->coef += coef;
            if (curr->coef == 0) {
                prev->link = curr->link;
                free(curr);
            }
            free(p);
        } else {
            p->link = curr;
            prev->link = p;
        }
    }
}

// 多项式乘法
Polynomial multiply(Polynomial poly1, Polynomial poly2) {
    if (!poly1 || !poly2) return NULL;
    
    Polynomial result = NULL;
    Polynomial p1 = poly1;
    
    while (p1) {
        Polynomial p2 = poly2;
        while (p2) {
            int coef = p1->coef * p2->coef;
            int exp = p1->exp + p2->exp;
            insert(&result, coef, exp);
            p2 = p2->link;
        }
        p1 = p1->link;
    }
    return result;
}

// 打印多项式
void printPoly(Polynomial poly) {
    if (!poly) {
        printf("0 0\n");
        return;
    }
    
    int first = 1;
    while (poly) {
        if (!first) printf(" ");
        printf("%d %d", poly->coef, poly->exp);
        first = 0;
        poly = poly->link;
    }
    printf("\n");
}

int main() {
    Polynomial poly1 = readPoly();
    Polynomial poly2 = readPoly();
    Polynomial product = multiply(poly1, poly2);
    printPoly(product);
    
    return 0;
}