阅读:0       作者:严长生

一元多项式相加,多项式相加(带源码和解析)

问题说明

求两个一元多项式 A(x) = a0 + a1x + a2x2 + … + anxn 和 B(x) = b0 + b1x + b2x2 + … + bmxm 的和。
要求:分别输入两个多项式的各个系数和指数。要求程序输出多项式的和。

实现思路

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

多项式每一项都是由:数据域(包含系数和指数)指针域构成。所以在定义表示结点的结构体时,可如下所示进行定义:
typedef struct PLnode{
    //数据域,coef 表示系数,expn 表示指数
    float coef;
    int expn;
    //指针域
    struct PLnode *next;
}PLnode,*PLinkList;
如下图所示,为一元多项式 A(x)=7+3x+9x8+5x17 和 B(x)=8x+22x7-9x8 的链表表示图:


当两个一元多项式相加时,需遵循如下的运算规则。假设指针 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;
}
运行结果:
input n of La:4
intput coef & expn:7 0
intput coef & expn:3 1
intput coef & expn:9 8
intput coef & expn:5 17
input m of Lb:3
intput coef & expn:8 1
intput coef & expn:22 7
intput coef & expn:-9 8

La=7+3x+9x^8+5x^17
Lb=8x+22x^7-9x^8
Lc=7+11x+22x^7+5x^17