单链表实现一元多项式加法与乘法

程序运行结果

实现原理

多项式加法：

（1）如果cpa的指数<cpb的指数，则将cpa所指向的插入和多项式链中，向后移动指针；

（2）如果cpa的指数>cpb的指数，则将cpb所指向的插入和多项式链中，向后移动指针；

（3）如果cpa的指数=cpb的指数，则若cpa的指数+cpb的指数=0，则删除相应结点，向后移动指针，并释放内存空间；

（4）否则cpa的指数+cpb的指数!=0，则修改同指数项的系数值，向后移动指针；

（5）如果pa链表非空，则链接pa剩余结点；

（6）如果pb链表非空，则链接pb剩余结点。

多项式乘法：

（1）多项式乘法可以看成单项式和多项式相乘，再作加法；

（2）可以利用循环，将被乘多项式与乘多项式每一项依次相乘；

（3）循环中每一次应累加部分积；

（4）循环结束时多项式相乘完成。

程序实现

1. 创建多项式，m为多项式的项数，当m为0时，函数只初始化头结点

void CreatePolyn(polynomial **p, int m){
    int i, data;
    int flag;
    polynomial *cp, *temp;
    (*p) = (polynomial *)malloc(sizeof(polynomial));
    (*p)->coef = 0.0;
    (*p)->expn = -1;
    (*p)->next = NULL;
    for(i = 1; i <= m; ++i){
        cp = *p;
        flag = 0; // 标志多项式中是否已经存在相同指数的多项式
        temp = (polynomial *)malloc(sizeof(polynomial));
        // 接收所输入的多项式的各项，默认各项指数互异 
        scanf("%f %d", &(temp->coef), &(temp->expn));
        while(cp->next && temp->expn > cp->next->expn){
            cp = cp->next;
        }
        if(cp->next && temp->expn == cp->next->expn){
            continue;// 如果已经存在相同指数的多项式，忽略该项
        }
        temp->next = cp->next;
        cp->next = temp;
    }
}

1. 打印多项式，考虑多种特殊项的格式，均以最简形式打印

void PrintPolyn(polynomial *p){
    polynomial *temp = p->next;
    while(temp){
        if(temp->coef == 1 && temp->expn == 0) // 1x^0 = 1 
            printf("1");
        else if(temp->coef == 1 && temp->expn == 1) // 1x^1 = x 
            printf("x", temp->coef);
        else{
            if(temp->expn == 0) // nx^0 = n 
                printf("%.0f", temp->coef);
            else if(temp->expn == 1) // nx^1 = nx
                printf("%.0fx", temp->coef);
            else{
                if(temp->coef == 1){
                    if(temp->expn < 0) // 1x^(-m) = x^(-m)
                        printf("x^(%d)", temp->expn);
                    else // 1x^m = x^m
                        printf("x^%d", temp->expn);
                }
                else{ // nx^(-m) = nx^(-m)
                    if(temp->expn < 0)
                        printf("%.0fx^(%d)", temp->coef, temp->expn);
                    else // nx^m = nx^m
                        printf("%.0fx^%d", temp->coef, temp->expn);
                }    
            }
        }
        temp = temp->next;
        if(temp) 
            printf(" + "); 
    }
}

1. 将pb中的多项式复制到pa中

void CopyPolyn(polynomial **pa, polynomial *pb){
    CreatePolyn(pa, 0);
    polynomial *temp, *cpa;
    cpa = *pa;
    pb = pb->next; // 移动指针指向第一个节点
    while(pb){
        temp = (polynomial *)malloc(sizeof(polynomial));
        temp->coef = pb->coef;
        temp->expn = pb->expn;
        temp->next = NULL;
        cpa->next = temp;
        cpa = temp;
        pb = pb->next;
    }
}

1. 多项式加法，结果保存在pa中

void AddPolyn(polynomial **pa, polynomial **pb){
    polynomial *cpa, *cpb, *temp, *ccpa, *p = (*pa);
    cpa = (*pa)->next;
    cpb = (*pb)->next;
    while(cpa && cpb){
        if(cpa->expn < cpb->expn){ // cpa的指数<cpb的指数，则将cpa所指向的插入和多项式链中，向后移动指针
            p->next = cpa;
            p = cpa;
            cpa = cpa->next;
        } else if(cpa->expn > cpb->expn) { // cpa的指数>cpb的指数，则将cpb所指向的插入和多项式链中，向后移动指针
            p->next = cpb;
            p = cpb;
            cpb = cpb->next;
        } else { // cpa的指数=cpb的指数
            if(cpa->coef + cpb->coef == 0){ // cpa的指数+cpb的指数=0，则删除相应结点，向后移动指针，并释放内存空间
                temp = *pa;
                while(temp->next != cpa)
                    temp = temp->next;
                temp->next = cpa->next;
                ccpa = cpa;
                cpa = cpa->next;
                cpb = cpb->next;
                free(ccpa);
            } else { // cpa的指数+cpb的指数!=0，则修改同指数项的系数值，向后移动指针 
                cpa->coef += cpb->coef;
                p->next = cpa;
                p = cpa;
                cpa = cpa->next;
                cpb = cpb->next;
            }
        }
    }
    if(cpa)
        p->next = cpa; // pa链表非空，链接pa剩余结点 
    else
        p->next = cpb; // pb链表非空，链接pb剩余结点
    free(*pb);
}

1. pa为多项式，pb为单项式，依次与pa中的每一项相乘，将结果保存到pa中

void MultiplyOperate(polynomial *pa, polynomial *pb){
    pa = pa->next;
    while(pa){
        pa->coef *= pb->coef;
        pa->expn += pb->expn;
        pa = pa->next;
    }
}

1. 多项式乘法，结果保存在pa中

void MultiplyPolyn(polynomial **pa, polynomial **pb){
    polynomial *cpa, *ccpa, *res;
    cpa = *pa; // 保存着原pa的内容
    CreatePolyn(pa, 0); // 从新初始化pa为头结点
    (*pb) = (*pb)->next; // 依次从pb中提取单项式 
    while(*pb){
        CopyPolyn(&ccpa, cpa);
        MultiplyOperate(ccpa, *pb); // 将所提取的单项式，依次与pa中的每一项相乘
        AddPolyn(pa, &ccpa); // 将部分积累加 
        (*pb) = (*pb)->next; // 提取下一个单项式 
    }
}

1. 主函数

#include <stdio.h>
#include <stdlib.h>
/* 单链表实现多项式相加和相乘 */ 
typedef struct polynomial{
    float coef; // 项的系数 
    int expn; // 项的指数 
    struct polynomial *next;
}polynomial;
int main(){
    polynomial *pa, *pb, *cpa, *cpb;
    int ma, mb;
    printf("请输入多项式A的项数：");
    scanf("%d", &ma);
    printf("请输入多项式A的各项系数和指数：");
    CreatePolyn(&pa, ma);
    CopyPolyn(&cpa, pa);
    printf("A = ");
    PrintPolyn(pa);
    printf("\n请输入多项式B的项数：");
    scanf("%d", &mb);
    printf("请输入多项式B的各项系数和指数：");
    CreatePolyn(&pb, mb);
    CopyPolyn(&cpb, pb);
    printf("B = ");
    PrintPolyn(pb);
    AddPolyn(&cpa, &cpb);
    MultiplyPolyn(&pa, &pb);
    printf("\n\nA + B = ");
    PrintPolyn(cpa);
    printf("\nA * B = ");
    PrintPolyn(pa);
    return 0;
}