用链表实现稀疏多项式相加c语言

链表是一种常用的数据结构，可以用来实现稀疏多项式的相加。在C语言中，可以通过定义一个结构体来表示多项式的每一项，然后使用链表将这些项连接起来。

首先，我们可以定义一个结构体来表示多项式的每一项，包括系数和指数：

typedef struct Node {
    int coefficient;  // 系数
    int exponent;     // 指数
    struct Node* next;  // 指向下一个节点的指针
} Node;

然后，我们可以定义一个函数来创建一个新的节点：

Node* createNode(int coefficient, int exponent) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->coefficient = coefficient;
    newNode->exponent = exponent;
    newNode->next = NULL;
    return newNode;
}

接下来，我们可以定义一个函数来将节点插入到链表中的正确位置：

void insertNode(Node** head, Node* newNode) {
    if (*head == NULL || (*head)->exponent < newNode->exponent) {
        newNode->next = *head;
        *head = newNode;
    } else {
        Node* current = *head;
        while (current->next != NULL && current->next->exponent > newNode->exponent) {
            current = current->next;
        }
        newNode->next = current->next;
        current->next = newNode;
    }
}

最后，我们可以定义一个函数来实现两个多项式的相加：

Node* addPolynomials(Node* poly1, Node* poly2) {
    Node* result = NULL;
    while (poly1 != NULL && poly2 != NULL) {
        if (poly1->exponent > poly2->exponent) {
            insertNode(&result, createNode(poly1->coefficient, poly1->exponent));
            poly1 = poly1->next;
        } else if (poly1->exponent < poly2->exponent) {
            insertNode(&result, createNode(poly2->coefficient, poly2->exponent));
            poly2 = poly2->next;
        } else {
            int sum = poly1->coefficient + poly2->coefficient;
            if (sum != 0) {
                insertNode(&result, createNode(sum, poly1->exponent));
            }
            poly1 = poly1->next;
            poly2 = poly2->next;
        }
    }
    while (poly1 != NULL) {
        insertNode(&result, createNode(poly1->coefficient, poly1->exponent));
        poly1 = poly1->next;
    }
    while (poly2 != NULL) {
        insertNode(&result, createNode(poly2->coefficient, poly2->exponent));
        poly2 = poly2->next;
    }
    return result;
}

这样，我们就可以通过调用上述函数来实现稀疏多项式的相加了。