用单链表解决一元N次多项式相加C语言

在C语言中，我们可以使用单链表来表示一元N次多项式的系数及其对应的指数。每个节点可以包含两个部分：一个整数存储系数，另一个整数存储指数。当我们需要对两个多项式进行相加时，可以创建一个新的链表，遍历原有的两个链表，并将对应项的系数累加，同时取指数较大的值作为新的节点的指数。

以下是大致步骤：

1. 定义一个结构体`Term`，包含系数`coeff`和指数`exp`。

typedef struct {
    int coeff;
    int exp;
} Term;

2. 创建一个`Node`结构体，用于存放一个多项式的部分。

typedef struct Node {
    Term term;
    struct Node* next;
} Node;

3. 初始化链表头指针。

Node* head = NULL;

4. 遍历第一个多项式，将每项添加到链表中。

void addTerm(Node** head, int coeff, int exp) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->term.coeff = coeff;
    newNode->term.exp = exp;
    newNode->next = *head;
    *head = newNode;
}

5. 对第二个多项式同样处理，然后合并两个链表。这里需要注意如果两个节点有相同的指数，则将它们的系数相加。

void mergePolynomials(Node** head1, Node** head2) {
    while (*head1 && *head2) {
        if ((*head1)->term.exp > (*head2)->term.exp) {
            Node* temp = *head1;
            *head1 = *head1->next;
            free(temp);
            addTerm(head2, (*head1)->term.coeff + (*head2)->term.coeff, (*head1)->term.exp);
        } else if ((*head1)->term.exp < (*head2)->term.exp) {
            Node* temp = *head2;
            *head2 = *head2->next;
            free(temp);
            addTerm(head1, (*head1)->term.coeff + (*head2)->term.coeff, (*head2)->term.exp);
        } else {
            (*head1)->term.coeff += (*head2)->term.coeff;
            Node* temp = *head2;
            *head2 = *head2->next;
            free(temp);
        }
    }

    // 如果还有剩余节点未处理，将其中一个链表连接到另一个链表的末尾
    while (*head1) {
        addTerm(head2, (*head1)->term.coeff, (*head1)->term.exp);
        Node* temp = *head1;
        *head1 = *head1->next;
        free(temp);
    }

    while (*head2) {
        addTerm(head1, (*head2)->term.coeff, (*head2)->term.exp);
        Node* temp = *head2;
        *head2 = *head2->next;
        free(temp);
    }
}

6. 最后返回合并后的链表的头部指针。