AI 助理
备案控制台
开发者社区 人工智能 文章 正文

一元多项式相加问题（两种方法）

2023-02-01 337
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 一元多项式的相加问题，主要运用了线性结构的合并，在合并线性结构的基础上，增加判断，所以我们可以将这个问题理解为一个复杂的线性表合并问题

问题描述

【问题描述】
用线性表存放一元多项式，实现两个一元多项式相加，输出结果多项式。
【输入形式】
分两行依次输入两个一元多项式，按指数由低到高依次输入表达式各项的系数和指数，输入字符结束，如果输入的某项系数为0，则不建立该项。
【输出形式】
按指数由低到高依次输出结果表达式各项的系数和指数，如果结果表达式为空则不输出。
【样例输入1】
7 0 3 1 9 8 5 17 10 21 a
8 1 22 2 -9 8 a
【样例输出1】
7.000000 0 11.000000 1 22.000000 2 5.000000 17 10.000000 21
【样例输入2】
22.2 1 a
-22.2 1 b
【样例输出2】

一、顺序表法

利用顺序表实现一元多项式的相加时，我们需要一个存放系数项的数组和一个存放指数项的数组，在执行合并的过程中对指数项进行判断，最后将系数等于零的项删除即可

1.1 初始化并创建顺序表

初始化和创建过程可以参考顺序表的创建，唯一不同的是这里是两个数组而已

typedef struct List{
    double *base1;   //系数，double型变量   （理解为数组）
    int *base2;      //指数，int型变量      （数组）
    int len;
    int size;
}List,*PList;
int Init_List(PList L){
    L->base1=(double*)malloc(sizeof(double)*SIZE);  //初始化
    L->base2=(int*)malloc(sizeof(int)*SIZE);
    L->len=0;
    L->size=SIZE;
    return 1;
}
int Creat_List(PList L){   //创建的时候注意要给系数指数都赋值，其他就是创建顺序表的方法
    double a;
    int b;
    int i=0;
    while(scanf("%lf %d",&a,&b)==2){ 
        if(a==0) continue;         //系数为零时不建立这个项，直接下一次循环 
        if(L->len>=L->size){
            L->base1=(double*)realloc(L->base1,sizeof(double)*(L->size+INCREAM));
            L->base2=(int*)realloc(L->base2,sizeof(int)*(L->size+INCREAM));
            L->size+=INCREAM;
        }
        L->base1[i]=a;
        L->base2[i++]=b;
        L->len++;
    }
    return 1;
}

1.2 一元多项式相加算法

这个算法中一定要注意，当把所有元素都判断完并放入L3中后，一定要小心L3的长度不能忘

int Connect_List(PList L1,PList L2,PList L3){
    int i=0,j=0,k=0;    //分别为L1,L2,L3的下标（L1,L2,L3是数组）
    if(L1->len+L2->len>L3->len){    //判断L3空间是否足够，不够时要重新开辟空间
        L3->base1=(double *)realloc(L3->base1,(L3->size+INCREAM)*sizeof(double));
        L3->base2=(int *)realloc(L3->base2,(L3->size+INCREAM)*sizeof(int));
        L3->size+=INCREAM;
    }
    while(i<L1->len&&j<L2->len){  //循环执行判断，直到一方元素循环完退出循环
        if(L1->base2[i]==L2->base2[j]){ //当L1,L2的指数项相等时，L3的系数项等于两者系数相加
            L3->base1[k]=L1->base1[i]+L2->base1[j++]; 
            L3->base2[k++]=L1->base2[i++];
        }else if(L1->base2[i]<L2->base2[j]){  //当L1指数项较小时，L3的系数就是L1
            L3->base1[k]=L1->base1[i];
            L3->base2[k++]=L1->base2[i++];
        }else{                                //当L2指数项较小时，L3的系数就是L2
            L3->base1[k]=L2->base1[j];
            L3->base2[k++]=L2->base2[j++];
        }
    }
    while(i<L1->len){           //另一个循序表里剩余的元素都放入L3
        L3->base1[k]=L1->base1[i];
        L3->base2[k++]=L1->base2[i++];
    }
    while(j<L2->len){          
        L3->base1[k]=L2->base1[j];
        L3->base2[k++]=L2->base2[j++];
    }
    L3->len=k;                //千万不能忘掉L3的长度！！
    for(i=0;i<L3->len;i++){    //最后将L3中系数等于0的项删除
        if(L3->base1[i]==0){
            for(j=i;j<L3->len-1;j++){
                L3->base1[j]=L3->base1[j+1];
                L3->base2[j]=L3->base2[j+1];
            }
            L3->len--;
        }
    }
    return 1;
}

1.3 完整代码

#include<stdio.h>
#include<malloc.h>
#define SIZE 10
#define INCREAM 10
typedef struct List{
    double *base1;
    int *base2;
    int len;
    int size;
}List,*PList;
int Init_List(PList L){
    L->base1=(double*)malloc(sizeof(double)*SIZE);
    L->base2=(int*)malloc(sizeof(int)*SIZE);
    L->len=0;
    L->size=SIZE;
    return 1;
}
int Creat_List(PList L){
    double a;
    int b;
    int i=0;
    while(scanf("%lf %d",&a,&b)==2){
        if(a==0) continue;
        if(L->len>=L->size){
            L->base1=(double*)realloc(L->base1,sizeof(double)*(L->size+INCREAM));
            L->base2=(int*)realloc(L->base2,sizeof(int)*(L->size+INCREAM));
            L->size+=INCREAM;
        }
        L->base1[i]=a;
        L->base2[i++]=b;
        L->len++;
    }
    return 1;
}
int Print_List(PList L){
    int i;
    for(i=0;i<L->len;i++){
        printf("%lf %d ",L->base1[i],L->base2[i]);
    }
    printf("\n");
    return 1;
}
int Connect_List(PList L1,PList L2,PList L3){
    int i=0,j=0,k=0;
    if(L1->len+L2->len>L3->len){
        L3->base1=(double *)realloc(L3->base1,(L3->size+INCREAM)*sizeof(double));
        L3->base2=(int *)realloc(L3->base2,(L3->size+INCREAM)*sizeof(int));
        L3->size+=INCREAM;
    }
    while(i<L1->len&&j<L2->len){
        if(L1->base2[i]==L2->base2[j]){
            L3->base1[k]=L1->base1[i]+L2->base1[j++];
            L3->base2[k++]=L1->base2[i++];
        }else if(L1->base2[i]<L2->base2[j]){
            L3->base1[k]=L1->base1[i];
            L3->base2[k++]=L1->base2[i++];
        }else{
            L3->base1[k]=L2->base1[j];
            L3->base2[k++]=L2->base2[j++];
        }
    }
    while(i<L1->len){
        L3->base1[k]=L1->base1[i];
        L3->base2[k++]=L1->base2[i++];
    }
    while(j<L2->len){
        L3->base1[k]=L2->base1[j];
        L3->base2[k++]=L2->base2[j++];
    }
    L3->len=k;
    for(i=0;i<L3->len;i++){
        if(L3->base1[i]==0){
            for(j=i;j<L3->len-1;j++){
                L3->base1[j]=L3->base1[j+1];
                L3->base2[j]=L3->base2[j+1];
            }
            L3->len--;
        }
    }
    return 1;
}
int main(){
    List L1,L2,L3;
    Init_List(&L1);
    Init_List(&L2);
    Init_List(&L3);
    Creat_List(&L1);
    getchar();
    Creat_List(&L2);
    Connect_List(&L1,&L2,&L3);
    Print_List(&L3);
    return 0;
}

二、单链表法

运用单链表实现一元多项式相加的过程和顺序表类似，核心算法思想就是循环判断，将指数较小的项放入第三个表，当指数项相等时系数相加放入第三个表

2.1 初始化并创建链表

初始化和创建过程就是创建单链表的过程，唯一不同的也是我们有两个数据域

typedef struct Node{
    double data1;    //系数
    int data2;           //指数
    struct Node * next;
}Node,*PNode;
PNode Init_Node(){           //初始化和创建发放就是链表的创建方法
    PNode head=(PNode)malloc(sizeof(Node));
    head->next=NULL;
    return head;
}
int Creat_Node(PNode head){
    double a;
    int b;
    PNode p=head;
    while(scanf("%lf %d",&a,&b)==2){
        if(a==0) continue;        //系数为0，不建立该项
        PNode q=(PNode)malloc(sizeof(Node));
        q->data1=a;
        q->data2=b;
        p->next=q;
        p=q;
    }
    p->next=NULL;
    return 1;
}

2.2 一元多项式相加算法

算法思想与顺序表相同，循环判断，但是在单链表中，当我们遇到系数相加为零时可以直接释放，不连接到第三个单链表的后面，这正是单链表实现这个问题的一大亮点

PNode Connect_Node(PNode head1,PNode head2,PNode head3){
    PNode p,q,r;
    r=head3;     //第三个单恋表
    p=head1->next;
    q=head2->next;
    while(p&&q){
        if(p->data2<q->data2){    //判断将指数较小的项连接到r后面
            PNode s=(PNode)malloc(sizeof(Node));  //我们需要一个新的临时单链表
            s->data1=p->data1;
            s->data2=p->data2;
            r->next=s;
            r=s;
            p=p->next;
        }else if(p->data2==q->data2){   //当指数项相等时
            PNode s=(PNode)malloc(sizeof(Node));
            s->data1=p->data1+q->data1;   
            s->data2=p->data2;
            if(s->data1==0){  //判断两表系数相加是否为零
                free(s);     //为零时释放s
            }else{
                r->next=s;    //不为零时连接到r后面
                r=s;
            }
            p=p->next;
            q=q->next;
        }else{             //q的指数项较小，连接到r后面
            PNode s=(PNode)malloc(sizeof(Node));
            s->data1=q->data1;
            s->data2=q->data2;
            r->next=s;
            r=s;
            q=q->next;
        }        
    }
    if(p){       //最后还是要判断一下哪个表还有剩余元素，放入r后面
        r->next=p;
    }else if(q){
        r->next=q;
    }else{
        r->next=NULL;
    }
    return r;
}

2.3 完整代码

#include<stdio.h>
#include<malloc.h>
typedef struct Node{
    double data1;
    int data2;
    struct Node * next;
}Node,*PNode;
PNode Init_Node(){
    PNode head=(PNode)malloc(sizeof(Node));
    head->next=NULL;
    return head;
}
int Creat_Node(PNode head){
    double a;
    int b;
    PNode p=head;
    while(scanf("%lf %d",&a,&b)==2){
        if(a==0) continue;
        PNode q=(PNode)malloc(sizeof(Node));
        q->data1=a;
        q->data2=b;
        p->next=q;
        p=q;
    }
    p->next=NULL;
    return 1;
}
PNode Connect_Node(PNode head1,PNode head2,PNode head3){
    PNode p,q,r;
    r=head3;
    p=head1->next;
    q=head2->next;
    while(p&&q){
        if(p->data2<q->data2){
            PNode s=(PNode)malloc(sizeof(Node));
            s->data1=p->data1;
            s->data2=p->data2;
            r->next=s;
            r=s;
            p=p->next;
        }else if(p->data2==q->data2){
            PNode s=(PNode)malloc(sizeof(Node));
            s->data1=p->data1+q->data1;
            s->data2=p->data2;
            if(s->data1==0){
                free(s);
            }else{
                r->next=s;
                r=s;
            }
            p=p->next;
            q=q->next;
        }else{
            PNode s=(PNode)malloc(sizeof(Node));
            s->data1=q->data1;
            s->data2=q->data2;
            r->next=s;
            r=s;
            q=q->next;
        }        
    }
    if(p){
        r->next=p;
    }else if(q){
        r->next=q;
    }else{
        r->next=NULL;
    }
    return r;
}
int Print_Node(PNode head){
    PNode p=head->next;
    while(p){
        printf("%lf %d ",p->data1,p->data2);
        p=p->next;
    }
    printf("\n");
    return 1;
}
int main(){
    PNode p,q,r;
    p=Init_Node();
    q=Init_Node();
    r=Init_Node();
    Creat_Node(p);
    getchar();
    Creat_Node(q);
    Connect_Node(p,q,r);
    Print_Node(r);
    return 1;
}

三、运行结果

1.png

文章标签：
算法
Want595
目录
相关文章
CTO技术共享
Github修改仓库的基本信息
我们通常在刚开始了解学习使用github时，一般都是测试的使用，有时我们向里面添加了一些代买，如果想要修改信息并且是删除仓库重新创建提交，可以采用下面方法修改仓库信息，名称、描述等。
CTO技术共享
501 1
Github修改仓库的基本信息
东风微鸣技术博客
|
负载均衡 关系型数据库 应用服务中间件
高可用系列文章之二 - 传统分层架构技术方案
高可用系列文章之二 - 传统分层架构技术方案
东风微鸣技术博客
224 0
可为编程
|
Linux
linux mv移动文件命令详解与替换强制覆盖多个文件
命令语 法 mv [-bfiuv][–help][–version][-S &lt;附加字尾&gt;][-V &lt;方法&gt;][源文件或目录][目标文件或目录]
可为编程
3763 0
肥猪肥猪-17824
|
Web App开发 JavaScript 前端开发
构建高效后端服务：Node.js与Express框架的实战指南
【9月更文挑战第6天】在数字化时代的潮流中，后端开发作为支撑现代Web和移动应用的核心，其重要性不言而喻。本文将深入浅出地介绍如何使用Node.js及其流行的框架Express来搭建一个高效、可扩展的后端服务。通过具体的代码示例和实践技巧，我们将探索如何利用这两个强大的工具提升开发效率和应用性能。无论你是后端开发的新手还是希望提高现有项目质量的老手，这篇文章都将为你提供有价值的见解和指导。
肥猪肥猪-17824
241 5
阿里云开发者
|
5月前
|
缓存 PyTorch 算法框架/工具
AI Infra之模型显存管理分析
本文围绕某线上客户部署DeepSeek-R1满血版模型时进行多次压测后，发现显存占用一直上升，从未下降的现象，记录了排查过程。
阿里云开发者
470 41
AI Infra之模型显存管理分析
热爱技术的小郑
|
存储 SQL Java
Java 系类之 Java StringBuffer类详解
这篇文章详细介绍了Java中的StringBuffer类的使用，包括其构造方法、追加字符串、替换字符、反转字符串和删除字符串的方法，并提供了相应的示例代码。
热爱技术的小郑
265 1
土木林森
|
消息中间件 Java Kafka
如何在Kafka分布式环境中保证消息的顺序消费？深入剖析Kafka机制，带你一探究竟！
【8月更文挑战第24天】Apache Kafka是一款专为实时数据管道和流处理设计的分布式平台，以其高效的消息发布与订阅功能著称。在分布式环境中确保消息按序消费颇具挑战。本文首先介绍了Kafka通过Topic分区实现消息排序的基本机制，随后详细阐述了几种保证消息顺序性的策略，包括使用单分区Topic、消费者组搭配单分区消费、幂等性生产者以及事务支持等技术手段。最后，通过一个Java示例演示了如何利用Kafka消费者确保消息按序消费的具体实现过程。
土木林森
510 3
郑小健
|
分布式计算 并行计算 大数据
NumPy 并行计算与分布式部署
【8月更文第30天】随着数据量的不断增长，传统的单机计算模型已经难以满足对大规模数据集处理的需求。并行和分布式计算成为了处理这些大数据集的关键技术。虽然 NumPy 本身并不直接支持并行计算，但可以通过结合其他库如 Numba 和 Dask 来实现高效的并行和分布式计算。
郑小健
153 1
Ant.Dream
|
API Android开发 Kotlin
Android实战经验分享之如何获取状态栏和导航栏的高度
在Android开发中，掌握状态栏和导航栏的高度对于优化UI布局至关重要。本文介绍两种主要方法：一是通过资源名称获取，简单且兼容性好；二是利用WindowInsets，适用于新版Android，准确性高。文中提供了Kotlin代码示例，并对比了两者的优缺点及适用场景。
Ant.Dream
1037 1
小Lee
|
Linux iOS开发 MacOS
激活Python虚拟环境
激活Python虚拟环境
小Lee
1370 2