C语言一元多项式的创建、输出、撤销以及两个一元多项式的相加和相乘

在C语言中，我们可以设计一个简单的数据结构来表示一元多项式，包括一个节点结构用于存储系数和指数，以及链表来存储各个项。以下是如何实现这些功能的基本步骤：

1. **创建一元多项式**:
- 使用`struct`定义`Term`作为项，包含`coef`(系数)和`exp`(指数)。
- 定义`Polynomial`结构体，包含一个指向`Term`首节点的指针。
- 实现`CreatePolynomial`函数，让用户依次输入系数和指数，将每个项添加到链表中。

struct Term {
    int coef;
    int exp;
};

typedef struct Polynomial {
    struct Term* head;
} Polynomial;

void CreatePolynomial(Polynomial* poly) {
    Term* term = malloc(sizeof(Term));
    term->coef = 1; // 初始化为常数项，如果没有输入则默认是1
    term->exp = 0;
    poly->head = term;

    while (true) {
        printf("请输入系数（若为0则结束输入）：");
        scanf("%d", &term->coef);

        if (term->coef == 0)
            break;

        printf("请输入指数：");
        scanf("%d", &term->exp);

        // 同样确保添加新节点至链表尾部
        Term* prev = poly->head;
        while (prev->next && prev->next->exp > term->exp) {
            prev = prev->next;
        }
        term->next = prev->next;
        prev->next = term;
    }
}

2. **输出一元多项式**:
- 定义`PrintPolynomial`函数遍历链表，输出各项的系数和指数。

void PrintPolynomial(Polynomial poly) {
    if (poly.head == NULL)
        return;

    Term* current = poly.head;
    while (current != NULL) {
        printf("(%dx^%d) + ", current->coef, current->exp);
        current = current->next;
    }
    printf("0)\n");
}

3. **撤销操作**:
- 这里不直接支持撤销，因为一元多项式的结构一旦创建就不能改变。但可以通过重新调用`CreatePolynomial`函数创建新的多项式。

4. **多项式相加**:
- 通过比较两个多项式的头结点，将系数相加并将指数较小的那个作为结果的指数。
- 遍历链表，直到其中一个项的系数变为0。

Polynomial AddPolynomials(Polynomial poly1, Polynomial poly2) {
    Polynomial result;
    result.head = NULL;

    Term* term1 = poly1.head;
    Term* term2 = poly2.head;

    while (term1 && term2) {
        int coefSum = term1->coef + term2->coef;
        if (coefSum > 0) {
            Term* newTerm = malloc(sizeof(Term));
            newTerm->coef = coefSum;
            newTerm->exp = term1->exp < term2->exp ? term1->exp : term2->exp;
            newTerm->next = result.head;
            result.head = newTerm;
        }

        term1 = term1->next;
        term2 = term2->next;
    }

    if (term1)
        result.head = term1;
    else if (term2)
        result.head = term2;

    return result;
}

5. **多项式相乘**:
- 可以使用Karatsuba算法或者朴素方法，这里展示朴素方法。遍历第一个多项式的项，对每一个项与第二个多项式的所有项相乘，然后累加结果。

Polynomial MultiplyPolynomials(Polynomial poly1, Polynomial poly2) {
    Polynomial result;
    result.head = NULL;

    Term* term1 = poly1.head;
    while (term1 != NULL) {
        Polynomial tempPoly;
        tempPoly.head = NULL;
        Term* tempTerm = malloc(sizeof(Term));

        // 对于当前的term1，计算其与poly2的所有项的积
        for (Term* term2 = poly2.head; term2 != NULL; term2 = term2->next) {
            int prodCoef = term1->coef * term2->coef;
            Term* newTerm = malloc(sizeof(Term));
            newTerm->coef = prodCoef;
            newTerm->exp = term1->exp + term2->exp;
            if (tempPoly.head == NULL)
                tempPoly.head = newTerm;
            else
                tempTerm->next = tempPoly.head;
            tempPoly.head = tempTerm;
        }

        // 将tempPoly的结果添加到result中
        MergePolynomial(&result, &tempPoly);

        term1 = term1->next;
    }

    return result;
}

void MergePolynomial(Polynomial* target, Polynomial* source) {
    if (*target.head == NULL)
        *target = *source;
    else {
        Term* tail = *target->head;
        while (tail->next != NULL)
            tail = tail->next;

        tail->next = source->head;
        if (source->head != NULL)
            source->head->prev = tail;
    }
}