一元多项式相加 数据结构c语言版

以下是一元多项式相加的C语言代码：

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

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;
}

// 添加节点到多项式中
Node *addNode(Node *head, int coefficient, int exponent) {
    // 如果链表为空，创建一个新的节点作为头节点
    if (head == NULL) {
        return createNode(coefficient, exponent);
    }

    // 遍历链表找到插入位置
    Node *curr = head;
    while (curr->next != NULL && curr->next->exponent > exponent) {
        curr = curr->next;
    }

    // 如果指数相同，将系数相加
    if (curr->exponent == exponent) {
        curr->coefficient += coefficient;
    } else {
        // 创建一个新节点并插入到链表中
        Node *newNode = createNode(coefficient, exponent);
        newNode->next = curr->next;
        curr->next = newNode;
    }

    return head;
}

// 打印多项式
void printPolynomial(Node *head) {
    Node *curr = head;
    while (curr != NULL) {
        printf("%dx^%d", curr->coefficient, curr->exponent);
        if (curr->next != NULL) {
            printf(" + ");
        }
        curr = curr->next;
    }
    printf("\n");
}

// 多项式相加
Node *addPolynomial(Node *poly1, Node *poly2) {
    // 创建一个新的链表头节点
    Node *result = NULL;

    // 遍历两个多项式
    Node *p1 = poly1, *p2 = poly2;
    while (p1 != NULL && p2 != NULL) {
        if (p1->exponent > p2->exponent) {
            result = addNode(result, p1->coefficient, p1->exponent);
            p1 = p1->next;
        } else if (p1->exponent < p2->exponent) {
            result = addNode(result, p2->coefficient, p2->exponent);
            p2 = p2->next;
        } else {
            result = addNode(result, p1->coefficient + p2->coefficient, p1->exponent);
            p1 = p1->next;
            p2 = p2->next;
        }
    }

    // 处理剩余部分
    while (p1 != NULL) {
        result = addNode(result, p1->coefficient, p1->exponent);
        p1 = p1->next;
    }
    while (p2 != NULL) {
        result = addNode(result, p2->coefficient, p2->exponent);
        p2 = p2->next;
    }

    return result;
}

int main() {
    // 创建第一个多项式
    Node *poly1 = NULL;
    poly1 = addNode(poly1, 3, 5);
    poly1 = addNode(poly1, 2, 3);
    poly1 = addNode(poly1, 5, 1);
    printf("第一个多项式：");
    printPolynomial(poly1);

    // 创建第二个多项式
    Node *poly2 = NULL;
    poly2 = addNode(poly2, 4, 4);
    poly2 = addNode(poly2, 1, 3);
    poly2 = addNode(poly2, 3, 2);
    poly2 = addNode(poly2, 4, 1);
    printf("第二个多项式：");
    printPolynomial(poly2);

    // 计算两个多项式之和
    Node *result = addPolynomial(poly1, poly2);
    printf("相加结果：");
    printPolynomial(result);

    return 0;
}

运行结果如下：

第一个多项式：3x^5 + 2x^3 + 5x^1
第二个多项式：4x^4 + 1x^3 + 3x^2 + 4x^1
相加结果：3x^5 + 4x^4 + 3x^3 + 3x^2 + 9x^1