1. 实现两个一元多项式的加法运算。 要求： （1）设计函数 createPoly( )，建立一个以单链表形式表示的一元多项式，输 入次序不限，但要求单链表中元素按指数递增次序排列（不能排序算法）。 （2）设计函数 addPoly( )，实现任意两个多项 A 和 B 加法运算，相加结果 在多项式 A 中。要求结果链表仍使用原来两个链表的存储空间，不另外占用其 它的存储空间。 （3）设计函数 output( )，输出多项式。

题目翻译：

1. 实现两个一元多项式的加法运算。 要求：

* 设计函数 createPoly( )，建立一个以单链表形式表示的一元多项式，输 入次序不限，但要求单链表中元素按指数递增次序排列（不能排序算法）。

* 设计函数 addPoly( )，实现任意两个多项 A 和 B 加法运算，相加结果 在多项式 A 中。要求结果链表仍使用原来两个链表的存储空间，不另外占用其 它的存储空间。

* 设计函数 output( )，输出多项式。

解题思路：

这道题目是多项式加法，比较常见。链表不需要排序算法来排序，只需要在插入时按照指数递增的顺序插入即可。

假设现在有两个多项式：

$$
A(x) = a_0 + a_1 x + a_2x^2 + ... + a_nx^n
$$

$$
B(x) = b_0 + b_1 x + b_2x^2 + ... + b_mx^m
$$

这里实现的 addPoly 函数将两个多项式相加，结果存储在 A 中。具体的实现方式是遍历链表 A 和 B，按照指数的大小进行合并，如果指数相同则将系数相加，如果 A 中的节点指数小于 B 中的，则将 A 中的节点插入到 B 中对应节点之前。

完整代码如下：

相关问题

设计一个算法，以实现一元稀疏多项式的加法运算。

可以使用哈希表来存储多项式中的每一项，其中哈希表的键为指数，值为系数。首先将两个多项式中的所有项存储到哈希表中，然后遍历其中一个多项式的哈希表，将另一个多项式中对应指数的项与其相加，最后将结果存储到一个新的哈希表中。最后遍历新的哈希表，将每一项输出即可。

以下是伪代码：

function add_sparse_polynomial(polynomial1, polynomial2):
result = {}
for term in polynomial1:
result[term.exponent] = term.coefficient
for term in polynomial2:
if term.exponent in result:
result[term.exponent] += term.coefficient
else:
result[term.exponent] = term.coefficient
return result

其中，term.exponent 表示项的指数，term.coefficient 表示项的系数。

编写一个c语言程序用单链表储存一元多项式，并实现两个多项式相加的运算

好的，以下是一个基于单链表储存一元多项式的C语言程序，并实现了两个多项式相加的运算：

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

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

// 创建一个空的多项式
Polynomial CreatePoly() {
    Polynomial P = (Polynomial)malloc(sizeof(PolyNode));
    if (!P) {
        printf("内存分配失败！\n");
        exit(1);
    }
    P->next = NULL;
    return P;
}

// 释放多项式所占用的内存
void DestroyPoly(Polynomial P) {
    Polynomial temp;
    while (P) {
        temp = P;
        P = P->next;
        free(temp);
    }
}

// 将项插入多项式
void InsertItem(Polynomial P, int coef, int expon) {
    Polynomial temp, pre, newnode;
    pre = P;
    temp = pre->next;
    while (temp && temp->expon > expon) {
        pre = temp;
        temp = pre->next;
    }
    if (temp && temp->expon == expon) {
        temp->coef += coef;
        if (temp->coef == 0) {
            pre->next = temp->next;
            free(temp);
        }
    } else {
        newnode = (Polynomial)malloc(sizeof(PolyNode));
        if (!newnode) {
            printf("内存分配失败！\n");
            exit(1);
        }
        newnode->coef = coef;
        newnode->expon = expon;
        newnode->next = temp;
        pre->next = newnode;
    }
}

// 读入多项式
Polynomial ReadPoly() {
    Polynomial P = CreatePoly();
    int n, coef, expon;
    scanf("%d", &n);
    while (n--) {
        scanf("%d %d", &coef, &expon);
        InsertItem(P, coef, expon);
    }
    return P;
}

// 求两个多项式的和
Polynomial AddPoly(Polynomial P1, Polynomial P2) {
    Polynomial P = CreatePoly();
    Polynomial temp1 = P1->next, temp2 = P2->next;
    while (temp1 && temp2) {
        if (temp1->expon > temp2->expon) {
            InsertItem(P, temp1->coef, temp1->expon);
            temp1 = temp1->next;
        } else if (temp1->expon < temp2->expon) {
            InsertItem(P, temp2->coef, temp2->expon);
            temp2 = temp2->next;
        } else {
            InsertItem(P, temp1->coef + temp2->coef, temp1->expon);
            temp1 = temp1->next;
            temp2 = temp2->next;
        }
    }
    while (temp1) {
        InsertItem(P, temp1->coef, temp1->expon);
        temp1 = temp1->next;
    }
    while (temp2) {
        InsertItem(P, temp2->coef, temp2->expon);
        temp2 = temp2->next;
    }
    return P;
}

// 输出多项式
void PrintPoly(Polynomial P) {
    Polynomial temp = P->next;
    int flag = 0;  // 标记是否为第一项
    if (!temp) {
        printf("0 0\n");
        return;
    }
    while (temp) {
        if (!flag) {
            flag = 1;
        } else {
            printf(" ");
        }
        printf("%d %d", temp->coef, temp->expon);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    Polynomial P1, P2, P;
    P1 = ReadPoly();
    P2 = ReadPoly();
    P = AddPoly(P1, P2);
    PrintPoly(P);
    DestroyPoly(P1);
    DestroyPoly(P2);
    DestroyPoly(P);
    return 0;
}

上述程序中，我们定义了一个多项式结构体，并实现了创建一个空的多项式、将项插入多项式、读入多项式、释放多项式、求两个多项式的和、输出多项式等基本操作。在主函数中，我们读入两个多项式，并通过AddPoly函数求它们的和，最后输出结果并释放内存。