按照升幂排列的一元多项式P n ​ (x)=p 1 ​ x+p 2 ​ x 2 +⋯+p n ​ x n 可以用线性表来表示P=(p 1 ​ ,p 2 ​ ,…,p n ​ )，对于一元多项式各种操作，实际上可以利用线性表来处理。若多项式的非零项指数很高并且非零项很少称之为稀疏多项式，此时使用链式存储结构较为方便。设计一个程序，实现一元稀疏多项式简单计算器。

下面是一元稀疏多项式简单计算器的程序实现，包括链式存储结构的定义和相关操作函数的实现：

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

typedef struct PolyNode {
    int coef; // 系数
    int expn; // 指数
    struct PolyNode *next; // 指向下一个节点的指针
} PolyNode, *Polylist;

// 初始化链表
void InitPolylist(Polylist *L) {
    (*L) = (Polylist)malloc(sizeof(PolyNode));
    (*L)->next = NULL;
}

// 插入节点
void InsertPolylist(Polylist L, int coef, int expn) {
    Polylist p, q;
    q = L;
    p = L->next;
    while (p != NULL && p->expn < expn) {
        q = p;
        p = p->next;
    }
    if (p != NULL && p->expn == expn) {
        p->coef += coef;
        if (p->coef == 0) {
            q->next = p->next;
            free(p);
        }
    } else {
        Polylist s = (Polylist)malloc(sizeof(PolyNode));
        s->coef = coef;
        s->expn = expn;
        s->next = p;
        q->next = s;
    }
}

// 输出链表
void OutputPolylist(Polylist L) {
    Polylist p = L->next;
    while (p != NULL) {
        printf("%dx^%d", p->coef, p->expn);
        if (p->next != NULL) {
            printf(" + ");
        }
        p = p->next;
    }
    printf("\n");
}

// 多项式加法
Polylist AddPolylist(Polylist A, Polylist B) {
    Polylist C;
    InitPolylist(&C);
    Polylist p = A->next, q = B->next;
    while (p != NULL && q != NULL) {
        if (p->expn < q->expn) {
            InsertPolylist(C, q->coef, q->expn);
            q = q->next;
        } else if (p->expn > q->expn) {
            InsertPolylist(C, p->coef, p->expn);
            p = p->next;
        } else {
            if (p->coef + q->coef != 0) {
                InsertPolylist(C, p->coef + q->coef, p->expn);
            }
            p = p->next;
            q = q->next;
        }
    }
    while (p != NULL) {
        InsertPolylist(C, p->coef, p->expn);
        p = p->next;
    }
    while (q != NULL) {
        InsertPolylist(C, q->coef, q->expn);
        q = q->next;
    }
    return C;
}

// 多项式乘法
Polylist MultiplyPolylist(Polylist A, Polylist B) {
    Polylist C;
    InitPolylist(&C);
    Polylist p = A->next, q;
    while (p != NULL) {
        q = B->next;
        while (q != NULL) {
            InsertPolylist(C, p->coef * q->coef, p->expn + q->expn);
            q = q->next;
        }
        p = p->next;
    }
    return C;
}

// 计算多项式在x = n处的值
int ComputePolylist(Polylist L, int n) {
    int sum = 0;
    Polylist p = L->next;
    while (p != NULL) {
        sum += p->coef * pow(n, p->expn);
        p = p->next;
    }
    return sum;
}

int main() {
    Polylist A, B, C;
    InitPolylist(&A);
    InitPolylist(&B);
    InsertPolylist(A, 1, 2);
    InsertPolylist(A, 2, 3);
    InsertPolylist(A, 3, 4);
    InsertPolylist(B, 3, 1);
    InsertPolylist(B, -2, 3);
    InsertPolylist(B, 1, 4);
    printf("A(x) = ");
    OutputPolylist(A);
    printf("B(x) = ");
    OutputPolylist(B);
    C = AddPolylist(A, B);
    printf("A(x) + B(x) = ");
    OutputPolylist(C);
    C = MultiplyPolylist(A, B);
    printf("A(x) * B(x) = ");
    OutputPolylist(C);
    printf("A(2) = %d\n", ComputePolylist(A, 2));
    printf("B(3) = %d\n", ComputePolylist(B, 3));
    return 0;
}

以上程序实现了一元稀疏多项式简单计算器的功能，包括链式存储结构的定义和相关操作函数的实现，以及多项式加法、乘法和在指定点处求值的实现。