作者：解学武

问题说明

求两个一元多项式 A(x) = a₀ + a₁x + a₂x² + … + a_nxⁿ 和 B(x) = b₀ + b₁x + b₂x² + … + b_mx^m 的和。
要求：分别输入两个多项式的各个系数和指数。要求程序输出多项式的和。

实现思路

求此问题，用单链表实现更加简单直观。其链表中的每个结点表示多项式中的每一项。

多项式每一项都是由：数据域（包含系数和指数）和指针域构成。所以在定义表示结点的结构体时，可如下所示进行定义：

typedef struct PLnode{
    //数据域，coef 表示系数，expn 表示指数
    float coef;
    int expn;
    //指针域
    struct PLnode *next;
}PLnode,*PLinkList;

如下图所示，为一元多项式 A(x)=7+3x+9x⁸+5x¹⁷ 和 B(x)=8x+22x⁷-9x⁸ 的链表表示图：
当两个一元多项式相加时，需遵循如下的运算规则。假设指针 qa 和qb 分别指向多项式 A 和多项式 B 中当前进行比较的某个结点，则比较两个结点的指数项，有以下 3 种情况：

• 指针 qa 所指结点的指数值小于指针 qb 所指结点的指数值，则应摘除 qa 所指结点插入到“和多项式”链表中去；
• 指针 qa 所指结点的指数值大于指针 qb 所指结点的指数值，则应摘除 qb 所指结点插入到“和多项式”链表中去；
• 指针 qa 所指结点的指数值等于指针 qb 所指结点的指数值，则将两个结点的系数相加：若和不为 0 ，则修改 qa 所指结点的系数值，同时释放qb所指结点；若和为 0，则应从多项式 A 的链表中删除相应结点，并释放指针 qa 和 qb 所指结点。

代码实现

#include <stdio.h>
#include <stdlib.h>
typedef struct PLnode{
    //数据域，coef 表示系数，expn 表示指数
    float coef;
    int expn;
    //指针域
    struct PLnode *next;
}PLnode,*PLinkList;

//一元多项式的链表表示创建函数，输入 m 项的系数和指数，建立表示一元多项式的有序链表L
void creatpolyn(PLinkList L, int m){
    int i;
    float coef;
    int expn;
    PLinkList tail,new;
    //初始化头结点L，其中系数域记录 链表的长度
    L->coef = m;
    L->expn = -1;
    //另 tail 作为遍历链表的指针
    tail = L;
    //创建 m 个新结点并对其初始化，而后链接到 L 上
    for(i=1 ; i<=m ; i++){
         new = (PLinkList)malloc(sizeof(PLnode));
         printf("intput coef & expn:");
         scanf("%f",&coef);
         scanf("%d",&expn);
         new->coef = coef;
         new->expn = expn;
         new->next = NULL;
         //将新结点链接到 L 上
         tail->next = new;
         tail = new;
    }
}
//完成多项式相加运算，即 Lc = La + Lb，并销毁一元多项式 Lb
PLinkList addpolyn(PLinkList La , PLinkList Lb){
    int x,len;
    float y;
    PLinkList Lc,pa,pb,pc,u;
    Lc = La;
    len = 0;
    pc = Lc;
    //另pa，pb 指向La 、Lb 的首元结点
    pa = La->next;
    pb = Lb->next;
    //通过 pa，pb 遍历链表 La、Lb，只有两指针同时存在时，才需要讨论
    while(pa && pb){
        x = pa->expn-pb->expn;
        //判断pa 所指结点的指数与pb 所指结点指数的大小关系
        if(x<0){
            //如果小，则找去 qa 结点到Lc 上
            pc = pa;
            len++;
            pa = pa->next;
        }
        //如果相等，则判断两结点的系数和是否为0
        else if(x == 0){
            y = pa->coef + pb->coef;
            if(y!=0.0){
                //如果不为 0，修改 pa 结点的系数值，同时链接到 LC 上
                pa->coef = y;
                pc = pa;
                len++;
            }
            //如果 y 值为0，则从 pc 的链表中摘除该结点，并释放该结点
            else{
                pc->next=pa->next;
                free(pa);
            }
            //无论是否相等，都执行下列操作
            pa = pc->next;
            u = pb;
            pb = pb ->next;
            free(u);
        }
        //如果pb 所指结点指数值小，则摘取pb所指结点到 LC链表上
        else{
            u = pb->next;
            pb->next= pa;
            pc->next=pb;
            pc = pb;
            len++;
            pb = u;
        }
    }
    //由于是在 La 上进行一元多项式的加和，所以如果运行过程 pa 不再有结点，而pb 上有，则需要将pb剩余结点链接到 Lc 上
    if(pb){
        pc->next = pb;
    }
    //计算 Lc 的长度
    while(pc){
        pc = pc->next;
        if(pc){
            len++;
        }
    }
    //Lc 的头结点中记录Lc 链表的长度
    Lc->coef = len;
    //加和完成的同时，释放Lb 结点
    free(Lb);
    return Lc;
}
//根据链表存储信息。输出结点 q
void printpoly(PLinkList q){
    if(q->expn == 0){
        printf("%.0f",q->coef);
    }
    else if(q->expn == 1){
        if(q->coef == 1){
            printf("x");
        }
        else if (q->coef == -1){
            printf("-x");
        }
        else{
            printf("%.0f",q->coef);
            printf("x");
        }
    }
    else if (q->coef == 1){
        printf("x^%d",q->expn);
    }
    else if(q->coef == -1){
        printf("-x^%d",q->expn);
    }
    else{
        printf("%.0fx^%d",q->coef,q->expn);
    }
}
//输出一元多项式L
void printpolyn(PLinkList L){
    int n;
    PLinkList p;
    p = L->next;
    n = 0;
    while(p){
        n++;
        if(n == 1){
            printpoly(p);
        }else if(p->coef>0){
            printf("+");
            printpoly(p);
        }else{
            printpoly(p);
        }
        p = p->next;
    }
}
int main(){
    PLinkList La,Lb,Lc;
    int m,n;
    //根据 n 的值，创建链表La
    printf("input n of La:");
    scanf("%d",&n);
    La = (PLinkList)malloc(sizeof(PLnode));
    creatpolyn(La,n);
    //根据 m 的值，创建 Lb
    printf("input m of Lb:");
    scanf("%d",&m);
    Lb = (PLinkList)malloc(sizeof(PLnode));
    creatpolyn(Lb,m);
    //输出La和Lb
    printf("\nLa=");
    printpolyn(La);
    printf("\nLb=");
    printpolyn(Lb);
    //计算La+Lb，结果保存在 Lc中
    Lc = addpolyn(La,Lb);
    printf("\nLc=");
    printpolyn(Lc);
    return 0;
}

运行结果：
声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。