如何利用单链表建立多项式

利用单链表构建多项式可以将每个节点关联到一个系数和指数，从而表示一个多项式的各个项。这里是一个简化的步骤：

1. **节点设计**：
设计一个链表节点，包含两个成员变量：
- `coeff` (系数)：存储数值部分。
- `exp` (指数)：存储指数部分，通常用于表示x的幂。

2. **链表结构**：
创建一个空的链表头节点，用于连接所有项。

3. **添加项**：
对于多项式的每一项（如a_n * x^n），创建一个新的节点，设置其`coeff`为n的系数，`exp`为n。然后，将这个新节点插入到链表中，位置取决于它的指数（通常按降序排列，高次项在前）。

4. **访问多项式**：
当需要计算某个特定值时，遍历链表，累加每个节点乘以x的相应次方。对于`coeff * x^exp`，如果`exp`大于当前值的指数，则不需要计算，因为更前面的项已经包含了更大的幂。

5. **操作**：
可以对链表进行加法、减法和乘法运算，通过节点之间的合并、替换以及创建新的节点来完成。

6. **示例**：
比如，一个三次多项式（2x^2 + 3x + 1）可以表示为这样的链表：

   3 -> 2 -> x -> 1

其中，最右边的1对应常数项，x指x的一次方，`2 -> x`表示二次项2x。

相关问题

利用所学的数据结构的基本知识，设计一个一元稀疏多项式简单计算器。 输入：输入并建立多项式； 输出：输出多项式，输出形式为整数序列要求：1）多项式相加/相减；2）计算多项式在x处的值；可以用带表头结点的单链表存储多项式，多项式的项数存放在头结点中。用C语言数据结构

下面是一个基于带头结点的单链表实现的一元稀疏多项式简单计算器的代码：

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

// 定义多项式项的结构体
typedef struct PolyNode {
    int coef;  // 系数
    int expon; // 指数
    struct PolyNode *next; // 指向下一项的指针
} PolyNode, *Polynomial;

// 创建一个空的多项式（只有头结点）
Polynomial createPoly() {
    Polynomial poly = (Polynomial) malloc(sizeof(PolyNode));
    poly->next = NULL;
    return poly;
}

// 从标准输入读入多项式
Polynomial readPoly() {
    Polynomial poly = createPoly();
    int n; // 项数
    scanf("%d", &n);
    while (n--) {
        int coef, expon;
        scanf("%d%d", &coef, &expon);
        if (coef != 0) { // 忽略系数为0的项
            Polynomial p = (Polynomial) malloc(sizeof(PolyNode));
            p->coef = coef;
            p->expon = expon;
            p->next = NULL;
            // 将新项插入到多项式中
            Polynomial q = poly;
            while (q->next && q->next->expon > expon) {
                q = q->next;
            }
            if (q->next && q->next->expon == expon) { // 合并同类项
                q->next->coef += coef;
                if (q->next->coef == 0) { // 合并后系数为0，删除该项
                    Polynomial t = q->next;
                    q->next = t->next;
                    free(t);
                }
            } else { // 插入新项
                p->next = q->next;
                q->next = p;
            }
        }
    }
    return poly;
}

// 将多项式输出到标准输出
void printPoly(Polynomial poly) {
    if (!poly->next) {
        printf("0\n");
    } else {
        printf("%d ", count(poly)); // 输出项数
        Polynomial p = poly->next;
        while (p) {
            printf("%d %d ", p->coef, p->expon);
            p = p->next;
        }
        printf("\n");
    }
}

// 返回多项式的项数
int count(Polynomial poly) {
    int count = 0;
    Polynomial p = poly->next;
    while (p) {
        count++;
        p = p->next;
    }
    return count;
}

// 多项式相加
Polynomial addPoly(Polynomial poly1, Polynomial poly2) {
    Polynomial poly = createPoly();
    Polynomial p = poly1->next, q = poly2->next;
    while (p && q) {
        if (p->expon > q->expon) {
            Polynomial t = (Polynomial) malloc(sizeof(PolyNode));
            *t = *p;
            t->next = NULL;
            p = p->next;
            insertPoly(poly, t);
        } else if (p->expon < q->expon) {
            Polynomial t = (Polynomial) malloc(sizeof(PolyNode));
            *t = *q;
            t->next = NULL;
            q = q->next;
            insertPoly(poly, t);
        } else {
            Polynomial t = (Polynomial) malloc(sizeof(PolyNode));
            t->coef = p->coef + q->coef;
            t->expon = p->expon;
            t->next = NULL;
            p = p->next;
            q = q->next;
            if (t->coef != 0) {
                insertPoly(poly, t);
            } else {
                free(t);
            }
        }
    }
    while (p) {
        Polynomial t = (Polynomial) malloc(sizeof(PolyNode));
        *t = *p;
        t->next = NULL;
        p = p->next;
        insertPoly(poly, t);
    }
    while (q) {
        Polynomial t = (Polynomial) malloc(sizeof(PolyNode));
        *t = *q;
        t->next = NULL;
        q = q->next;
        insertPoly(poly, t);
    }
    return poly;
}

// 在多项式中插入一个项，按指数降序排列
void insertPoly(Polynomial poly, Polynomial node) {
    Polynomial p = poly;
    while (p->next && p->next->expon > node->expon) {
        p = p->next;
    }
    if (p->next && p->next->expon == node->expon) { // 合并同类项
        p->next->coef += node->coef;
        if (p->next->coef == 0) { // 合并后系数为0，删除该项
            Polynomial t = p->next;
            p->next = t->next;
            free(t);
        } else {
            free(node);
        }
    } else {
        node->next = p->next;
        p->next = node;
    }
}

// 多项式相减
Polynomial subPoly(Polynomial poly1, Polynomial poly2) {
    Polynomial poly = createPoly();
    Polynomial p = poly1->next, q = poly2->next;
    while (p && q) {
        if (p->expon > q->expon) {
            Polynomial t = (Polynomial) malloc(sizeof(PolyNode));
            *t = *p;
            t->next = NULL;
            p = p->next;
            insertPoly(poly, t);
        } else if (p->expon < q->expon) {
            Polynomial t = (Polynomial) malloc(sizeof(PolyNode));
            *t = *q;
            t->coef = -t->coef;
            t->next = NULL;
            q = q->next;
            insertPoly(poly, t);
        } else {
            Polynomial t = (Polynomial) malloc(sizeof(PolyNode));
            t->coef = p->coef - q->coef;
            t->expon = p->expon;
            t->next = NULL;
            p = p->next;
            q = q->next;
            if (t->coef != 0) {
                insertPoly(poly, t);
            } else {
                free(t);
            }
        }
    }
    while (p) {
        Polynomial t = (Polynomial) malloc(sizeof(PolyNode));
        *t = *p;
        t->next = NULL;
        p = p->next;
        insertPoly(poly, t);
    }
    while (q) {
        Polynomial t = (Polynomial) malloc(sizeof(PolyNode));
        *t = *q;
        t->coef = -t->coef;
        t->next = NULL;
        q = q->next;
        insertPoly(poly, t);
    }
    return poly;
}

// 计算多项式在x处的值
int calcPoly(Polynomial poly, int x) {
    int sum = 0;
    Polynomial p = poly->next;
    while (p) {
        sum += p->coef * pow(x, p->expon);
        p = p->next;
    }
    return sum;
}

int main() {
    // 读入第一个多项式
    Polynomial poly1 = readPoly();
    // 读入第二个多项式
    Polynomial poly2 = readPoly();

    // 输出第一个多项式
    printf("Poly1: ");
    printPoly(poly1);
    // 输出第二个多项式
    printf("Poly2: ");
    printPoly(poly2);

    // 计算第一个多项式在x=2处的值
    int x = 2;
    int result = calcPoly(poly1, x);
    printf("Poly1(%d) = %d\n", x, result);

    // 计算第二个多项式在x=3处的值
    x = 3;
    result = calcPoly(poly2, x);
    printf("Poly2(%d) = %d\n", x, result);

    // 计算两个多项式相加的结果
    Polynomial sum = addPoly(poly1, poly2);
    printf("Poly1 + Poly2: ");
    printPoly(sum);

    // 计算两个多项式相减的结果
    Polynomial diff = subPoly(poly1, poly2);
    printf("Poly1 - Poly2: ");
    printPoly(diff);

    return 0;
}

这个计算器支持读入两个多项式，计算多项式在某个点的值，以及将两个多项式相加和相减。其中，多项式以带头结点的单链表形式存储，每个节点表示一个项，包含系数和指数两个成员变量。

用c语言建立单链表来表示多项式，并进行二个多项式的相乘并输出结果

在C语言中，我们可以使用结构体（struct）来表示多项式，每个节点包含一个系数（coefficient）和一个指向下一个节点的指针（next）。下面是一个简单的示例，展示如何创建单链表表示多项式，以及两个多项式相乘的基本步骤：

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

// 定义多项式节点结构体
typedef struct {
    int coefficient; // 系数
    struct PolynomialNode *next; // 指向下一个节点的指针
} PolynomialNode;

// 创建一个新的多项式节点
PolynomialNode* createTerm(int coefficient) {
    PolynomialNode* newNode = (PolynomialNode*)malloc(sizeof(PolynomialNode));
    newNode->coefficient = coefficient;
    newNode->next = NULL;
    return newNode;
}

// 插入节点到链表
void insertTerm(PolynomialNode** head, int coefficient) {
    PolynomialNode* newTerm = createTerm(coefficient);
    if (*head == NULL) {
        *head = newTerm;
    } else {
        PolynomialNode* current = *head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newTerm;
    }
}

// 打印链表表示的多项式
void printPolynomial(PolynomialNode* head) {
    PolynomialNode* temp = head;
    printf("(");
    while (temp != NULL) {
        printf("%d", temp->coefficient);
        if (temp->next != NULL) {
            printf(" + ");
        }
        temp = temp->next;
    }
    printf(")");
}

// 相乘的主函数
void multiplyPolynomials(PolynomialNode** p1, PolynomialNode** p2, PolynomialNode** result) {
    PolynomialNode* current1 = *p1;
    PolynomialNode* current2 = *p2;
    PolynomialNode* dummy = createTerm(0); // 初始化一个哑节点，用于合并结果
    PolynomialNode* temp = dummy;

    while (current1 != NULL || current2 != NULL) {
        if (current1 != NULL) {
            PolynomialNode* term1 = createTerm(current1->coefficient * current2->coefficient);
            term1->next = temp->next;
            temp->next = term1;
            current1 = current1->next;
        }

        if (current2 != NULL) {
            current2 = current2->next;
        }

        if (current1 == NULL && current2 == NULL) {
            *result = dummy->next;
            break;
        }
        
        if (current2 != NULL) {
            current1 = current1 ? current1 : dummy;
        }
    }
}

int main() {
    PolynomialNode* p1_head = NULL, *p2_head = NULL, *result_head = NULL;

    // 示例：输入两个多项式
    insertTerm(&p1_head, 2); insertTerm(&p1_head, -1); insertTerm(&p1_head, 3); // (2 - 1 + 3)
    insertTerm(&p2_head, 4); insertTerm(&p2_head, 5);                // (4 + 5)

    multiplyPolynomials(&p1_head, &p2_head, &result_head);

    // 输出结果
    printPolynomial(result_head);

    return 0;
}

在这个例子中，我们首先创建了两个多项式`p1`和`p2`的链表表示，然后通过`multiplyPolynomials`函数计算它们的乘积，并将结果存储在一个新的链表`result`中。最后，`printPolynomial`函数用于打印出结果多项式。