单链表应用------一元多项式
【学习时间】2021/2/26
【题目名称】单链表应用------一元多项式
【问题描述】编写一个程序用单链表存储多项式,并实现两个一元多项式A与B相加的函数。A,B刚开始是升序的,A与B之和按降序排列。例如:
多项式A: 1.2X^0 2.5X^1 3.2X^3 -2.5X^5
多项式B: -1.2X^0 2.5X^1 3.2X^3 2.5X^5 5.4X^10
多项式A与B之和:5.4X^10 6.4X^3 5X^1
【输入形式】任意两个多项式A和B
【输出形式】多项式中某一项的系数与指数,系数保留一位小数。
【样例输入】
1.2 0 2.5 1 3.2 3 -2.5 5
-1.2 0 2.5 1 3.2 3 2.5 5 5.4 10
2
【样例输出】6.4 3
【样例说明】
第一个多项式的系数与指数对,以空格隔开
第二个多项式的系数与指数对,以空格隔开
输出第2项的系数与指数,系数与指数间用空格隔开,系数保留一位小数
【评分标准】必须用链表实现。
【思路分析】
###Step1.初始化
首先设置结构体Node,内含系数(coef)和指数(exp)以及结构体指针(next),采用头插法建立两个单链表A,B,目的是为下一步降序输出结果提供便利。
###Step 2. 链表相加
为了便于操作我们将结果存储到A链表中,同时为了方便后续的插入删除操作,我们对A设置pre指针指向当前节点的前驱。因此我们可以考虑以下三种情况:
(1)当A中节点的exp>B中节点的exp时,则A后移一位(包括pre)
(2)当A中节点的exp<B中节点的exp时,则B的当前节点插入到A中,位置是pre前面。
(3)当A中节点的exp=B中节点的exp时,那么进行系数相加,并把结果赋值个A中节点的coef,注意,在此处需要判断系数和是否为0,如果等于0,则需要把A中的该节点删除;无论是否等于0,B都需要后移一位。
###Step 3. 结果输出
遍历单链表的同时计数,当计数器为n时,打印该节点。
【源代码】
#include<iostream>
#include<algorithm>
#include <cstdio>
using namespace std;
struct Node
{
float coef;
int exp;
Node *next;
};
Node *Creat()//头插法
{
int coef,exp,i=0;
Node *first=new Node;
Node *last=new Node;
Node *r=NULL,*s=NULL;
Node *temp;
first->next=NULL;
char c;
do{
s=new Node;
scanf("%f%d",&s->coef,&s->exp);
if(i==0)
{
temp=s;
i=1;
}
s->next=first->next;
first->next=s;
c=getchar();//接收空格的作用
}while(c!=EOF&&c!='\n');//判断数据是否传输结束
temp->next=last;
return first;
}
Node *Add(Node *a,Node *b)
{
Node *pa=a->next;
Node *pb=b->next;
Node *pre=a;
while(pa!=NULL&&pb!=NULL)
{
if((pa->exp)>(pb->exp))//当a的指数大于b的指数 ,pa向前移动一个
{
pre=pa;
pa=pa->next;
}
else if((pa->exp)<(pb->exp))//当a的指数小于于b的指数 , 将pb插入到a中
{
Node *q=pb;
pb=pb->next;
pre->next=q;
q->next=pa;
pre=q;
}
else{//指数相同,求和计算
pa->coef+=pb->coef;
if(pa->coef==0)//系数为0,从a中删除该节点
{
pre->next=pa->next;
pa->next=NULL;
pa=pre->next;
}
pb=pb->next;//无论系数是否为零pb都需要向下一位移动
}
}
return a;
}
void show(Node *first,int num)
{
int i=1;
Node *p=first->next;
while(p!=NULL)
{
if(i==num)
printf("%.1f %d",p->coef,p->exp);
p=p->next;
i++;
}
}
int main()
{
int num;
Node *A_first=Creat();
Node *B_first=Creat();
cin>>num;
Node *C_first=Add(A_first,B_first);
show(C_first,num);
return 0;
}
【结果分析】
上面的代码存在局限性,当出现这种输入时,正确结果应该如下;
但是,程序显示结果是:
求大佬解答!!!!!