数据结构用c语言实现多项式相加求值

为了实现多项式相加求值，我们可以使用链表来表示多项式。链表的每个节点表示多项式的一项，包含系数和指数两个成员变量。

具体实现步骤如下：

1. 定义链表节点结构体

typedef struct PolyNode {
    int coef;  // 系数
    int expn;  // 指数
    struct PolyNode *next;
} PolyNode, *Polynomial;

2. 定义多项式相加函数

Polynomial AddPolynomial(Polynomial p1, Polynomial p2) {
    Polynomial result = (Polynomial)malloc(sizeof(PolyNode));
    Polynomial p = result;
    while (p1 && p2) {
        if (p1->expn > p2->expn) {
            p->next = p1;
            p1 = p1->next;
        } else if (p1->expn < p2->expn) {
            p->next = p2;
            p2 = p2->next;
        } else {
            int coef = p1->coef + p2->coef;
            if (coef != 0) {
                p->next = (Polynomial)malloc(sizeof(PolyNode));
                p->next->coef = coef;
                p->next->expn = p1->expn;
                p = p->next;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
    }
    p->next = p1 ? p1 : p2;
    return result->next;
}

3. 定义多项式求值函数

int EvaluatePolynomial(Polynomial p, int x) {
    int result = 0;
    while (p) {
        int term = p->coef;
        for (int i = 0; i < p->expn; i++) {
            term *= x;
        }
        result += term;
        p = p->next;
    }
    return result;
}

4. 定义测试函数

void TestPolynomial() {
    // 多项式 P1(x) = 2x^3 + 3x^2 + 4x + 5
    Polynomial p1 = (Polynomial)malloc(sizeof(PolyNode));
    p1->coef = 2;
    p1->expn = 3;
    p1->next = (Polynomial)malloc(sizeof(PolyNode));
    p1->next->coef = 3;
    p1->next->expn = 2;
    p1->next->next = (Polynomial)malloc(sizeof(PolyNode));
    p1->next->next->coef = 4;
    p1->next->next->expn = 1;
    p1->next->next->next = (Polynomial)malloc(sizeof(PolyNode));
    p1->next->next->next->coef = 5;
    p1->next->next->next->expn = 0;
    p1->next->next->next->next = NULL;

    // 多项式 P2(x) = 3x^4 + 2x^2 + 1
    Polynomial p2 = (Polynomial)malloc(sizeof(PolyNode));
    p2->coef = 3;
    p2->expn = 4;
    p2->next = (Polynomial)malloc(sizeof(PolyNode));
    p2->next->coef = 2;
    p2->next->expn = 2;
    p2->next->next = (Polynomial)malloc(sizeof(PolyNode));
    p2->next->next->coef = 1;
    p2->next->next->expn = 0;
    p2->next->next->next = NULL;

    // 多项式相加 P3(x) = P1(x) + P2(x) = 3x^4 + 2x^3 + 5x^2 + 4x + 6
    Polynomial p3 = AddPolynomial(p1, p2);
    printf("P3(x) = ");
    while (p3) {
        printf("%dx^%d", p3->coef, p3->expn);
        p3 = p3->next;
        if (p3) {
            printf(" + ");
        }
    }
    printf("\n");

    // 多项式求值 P3(2) = 3 * 2^4 + 2 * 2^3 + 5 * 2^2 + 4 * 2 + 6 = 62
    int result = EvaluatePolynomial(p3, 2);
    printf("P3(2) = %d\n", result);
}

5. 调用测试函数

int main() {
    TestPolynomial();
    return 0;
}