一元多项式的相加问题，主要运用了线性结构的合并，在合并线性结构的基础上，增加判断，所以我们可以将这个问题理解为一个复杂的线性表合并问题
目录
问题描述
一、顺序表法
1.1 初始化并创建顺序表
1.2 一元多项式相加算法
1.3 完整代码
二、单链表法
1.1 初始化并创建链表
1.2 一元多项式相加算法
1.3 完整代码
三、运行结果
附：系列文章
问题描述
【问题描述】
用线性表存放一元多项式，实现两个一元多项式相加，输出结果多项式。
【输入形式】分两行依次输入两个一元多项式，按指数由低到高依次输入表达式各项的系数和指数，输入字符结束，如果输入的某项系数为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;
}二、单链表法
运用单链表实现一元多项式相加的过程和顺序表类似，核心算法思想就是循环判断，将指数较小的项放入第三个表，当指数项相等时系数相加放入第三个表
1.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;
}1.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;
}1.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;
}三、运行结果
文章来源：https://www.toymoban.com/news/detail-737655.html
文章来源地址https://www.toymoban.com/news/detail-737655.html
附：系列文章
| 序号 | 文章目录 | 直达链接 |
| 1 | 顺序表的十个基本操作（全） | https://want595.blog.csdn.net/article/details/127139051 |
| 2 | 单链表的十三个基本操作（全） | https://want595.blog.csdn.net/article/details/127139598 |
| 3 | 四种创建单链表的方法 | https://want595.blog.csdn.net/article/details/127017405 |
| 4 | 删除重复元素（顺序表、单链表） | https://want595.blog.csdn.net/article/details/127023468 |
| 5 | 两个有序表的合并（三种方法） | https://want595.blog.csdn.net/article/details/127104602 |
| 6 | 一元多项式相加问题（两种方法） | https://want595.blog.csdn.net/article/details/127131351 |
| 7 | 约瑟夫环问题（三种方法） | https://want595.blog.csdn.net/article/details/127019472 |
| 8 | 顺序栈与链栈 | https://want595.blog.csdn.net/article/details/127035609 |
| 9 | 顺序循环队列与链队列 | https://want595.blog.csdn.net/article/details/127040115 |
| 10 | 后缀表达式的转换（栈的运用） | https://want595.blog.csdn.net/article/details/127088466 |
| 11 | 简单表达式的计算（两种方法） | https://want595.blog.csdn.net/article/details/127121720 |
| 12 | next数组（详细求法） | https://want595.blog.csdn.net/article/details/127217629 |
| 13 | BF算法（具体应用） | https://want595.blog.csdn.net/article/details/127138894 |
| 14 | 串的模式匹配相关问题（BF算法、KMP算法） | https://want595.blog.csdn.net/article/details/127182721 |
| 15 | 二叉树的遍历（七种方法） | https://want595.blog.csdn.net/article/details/127472445 |
到了这里，关于一元多项式相加问题（两种方法）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
