线性表的应用算法:构造两个按指数递增的有序链表，实现两个元多项式相加

题目描述

线性表的应用算法::构造两个按指数递增的有序链表，实现两个元多项式相加

编写思路

我们首先定义一个多项式项的结构体PolyNode，其中包含系数coef和指数expon两个成员变量，以及一个指向下一项的指针next。然后，我们定义了一些函数来操作这些多项式项。

在NewNode()函数中，我们创建一个新节点，并将系数和指数设置为给定的值。

在InsertNode()函数中，我们将一个新节点插入到有序链表中。具体来说，我们首先遍历链表，找到第一个指数小于等于给定指数的节点。如果找到了一个指数与给定指数相等的节点，则将它的系数加上给定系数；否则，我们创建一个新节点，并将它插入到链表中。

在BuildPoly()函数中，我们构造一个多项式链表。具体来说，我们首先读取一个整数n，表示多项式的项数。然后，我们使用InsertNode()函数逐个插入每个项。

在PrintPoly()函数中，我们打印一个多项式。具体来说，我们遍历链表，跳过头结点，并打印每个项的系数和指数。如果多项式的所有项系数都为0，则我们打印”0 0″表示多项式为0。

在AddPoly()函数中，我们实现了两个多项式相加。具体来说，我们使用两个指针p1和p2分别指向两个多项式的头结点，然后逐个比较它们的每个项。如果p1的指数大于p2的指数，则将p1的项插入结果链表中；如果p1的指数小于p2的指数，则将p2的项插入结果链表中；如果p1和p2的指数相等，则将它们的系数相加，并插入结果链表中。最后，我们将剩余的项插入到结果链表中。

在main()函数中，我们首先使用BuildPoly()函数构造两个多项式。然后，我们使用AddPoly()函数计算它们的和，并使用PrintPoly()函数打印结果。

源代码

以下是一个C语言实现，可以构造两个按指数递增的有序链表，并实现两个多项式相加：

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

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

// 创建新节点
PtrToPolyNode NewNode(int coef, int expon)
{
    PtrToPolyNode p = (PtrToPolyNode)malloc(sizeof(struct PolyNode));
    p->coef = coef;
    p->expon = expon;
    p->next = NULL;
    return p;
}

// 插入新节点
void InsertNode(PtrToPolyNode p, int coef, int expon)
{
    PtrToPolyNode q = NewNode(coef, expon);
    while (p->next != NULL && p->next->expon > expon) {
        p = p->next;
    }
    if (p->next != NULL && p->next->expon == expon) {
        p->next->coef += coef;
        free(q);
    } else {
        q->next = p->next;
        p->next = q;
    }
}

// 构造多项式链表
PtrToPolyNode BuildPoly()
{
    PtrToPolyNode head = NewNode(0, -1);
    int n, coef, expon;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &coef, &expon);
        InsertNode(head, coef, expon);
    }
    return head;
}

// 打印多项式
void PrintPoly(PtrToPolyNode p)
{
    int flag = 0;
    while (p->next != NULL) {
        p = p->next;
        if (p->coef != 0) {
            if (flag == 0) {
                printf("%d %d", p->coef, p->expon);
                flag = 1;
            } else {
                printf(" %d %d", p->coef, p->expon);
            }
        }
    }
    if (flag == 0) {
        printf("0 0");
    }
    printf("\n");
}

// 多项式相加
PtrToPolyNode AddPoly(PtrToPolyNode p1, PtrToPolyNode p2)
{
    PtrToPolyNode head = NewNode(0, -1);
    PtrToPolyNode p = head;
    while (p1->next != NULL && p2->next != NULL) {
        if (p1->next->expon > p2->next->expon) {
            p->next = NewNode(p1->next->coef, p1->next->expon);
            p1 = p1->next;
        } else if (p1->next->expon < p2->next->expon) {
            p->next = NewNode(p2->next->coef, p2->next->expon);
            p2 = p2->next;
        } else {
            int coef = p1->next->coef + p2->next->coef;
            if (coef != 0) {
                p->next = NewNode(coef, p1->next->expon);
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        p = p->next;
    }
    while (p1->next != NULL) {
        p->next = NewNode(p1->next->coef, p1->next->expon);
        p1 = p1->next;
        p = p->next;
    }
    while (p2->next != NULL) {
        p->next = NewNode(p2->next->coef, p2->next->expon);
        p2 = p2->next;
        p = p->next;
    }
    return head;
}

int main()
{
    // 构造两个多项式
    PtrToPolyNode p1 = BuildPoly();
    PtrToPolyNode p2 = BuildPoly();

    // 计算相加结果
    PtrToPolyNode p3 = AddPoly(p1, p2);

    // 打印结果
    PrintPoly(p3);

    return 0;
}