用C语言描述单链表表示一元多项式相减

假设有两个一元多项式A(x)和B(x)，它们分别由单链表La和Lb表示。现在要求计算它们的差C(x)=A(x)-B(x)，并用单链表Lc表示。

单链表的结构体定义如下：

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

其中，coef表示系数，expn表示指数，next表示指向下一个节点的指针。

单链表的初始化函数如下：

List InitList() {
    List L = (List) malloc(sizeof(Node));
    L->next = NULL;
    return L;
}

单链表的插入函数如下：

void Insert(List L, int coef, int expn) {
    Node *p = L, *q;
    while (p->next && p->next->expn > expn) {
        p = p->next;
    }
    if (p->next && p->next->expn == expn) {
        p->next->coef += coef;
    } else {
        q = (Node *) malloc(sizeof(Node));
        q->coef = coef;
        q->expn = expn;
        q->next = p->next;
        p->next = q;
    }
}

单链表的遍历函数如下：

void Traverse(List L) {
    Node *p = L->next;
    while (p) {
        printf("%dx^%d ", p->coef, p->expn);
        p = p->next;
        if (p) {
            printf("+ ");
        }
    }
    printf("\n");
}

现在，我们可以用这些函数来实现一元多项式相减的操作。具体步骤如下：

1. 创建一个新的单链表Lc，表示A(x)-B(x)的结果。

2. 遍历La和Lb，将它们的每一项都插入到Lc中。

3. 如果La和Lb的当前指数相同，则将它们的系数相减，并插入到Lc中。

4. 遍历完La和Lb后，Lc中就存储了A(x)-B(x)的结果。

代码实现如下：

List Subtract(List La, List Lb) {
    List Lc = InitList();
    Node *pa = La->next, *pb = Lb->next;
    while (pa && pb) {
        if (pa->expn > pb->expn) {
            Insert(Lc, pa->coef, pa->expn);
            pa = pa->next;
        } else if (pa->expn < pb->expn) {
            Insert(Lc, -pb->coef, pb->expn);
            pb = pb->next;
        } else {
            int coef = pa->coef - pb->coef;
            if (coef != 0) {
                Insert(Lc, coef, pa->expn);
            }
            pa = pa->next;
            pb = pb->next;
        }
    }
    while (pa) {
        Insert(Lc, pa->coef, pa->expn);
        pa = pa->next;
    }
    while (pb) {
        Insert(Lc, -pb->coef, pb->expn);
        pb = pb->next;
    }
    return Lc;
}

其中，Insert函数用来插入每一项，-pb->coef表示将B(x)的系数取负数。最后，返回Lc即可。