设为首页收藏本站

开启辅助访问切换到窄版

第一问答网»论坛 › 中问网 › 问答 › 用链表实现多项式加减法的时候，加法或者减法单独可以实 ...

用链表实现多项式加减法的时候，加法或者减法单独可以实现，但是合在一起却总是减法出错

11 |

2 | 2021-1-27 05:30:26 | 显示全部楼层 |阅读模式

问题描述
给定两个多项式，求解其和与差。多项式的项数为M，而最高幂次为N。（1#include
#include
typedefstructNode{
intxishu;//多项式系数
intzhishu;//多项式指数
Node*next;
}node,*LinkedList;
voidshow(LinkedListl)//打印链表的函数
{
while(l)
{
printf("%d%d",l->xishu,l->zhishu);
l=l->next;
}
}
intmain()
{
LinkedListl1,l2,l3,l4,head1,head2,head3,head4;//l1,l2用于接受输入的链表，l3储存加法结果，l4储存减法结果
l1=head1=(LinkedList)malloc(sizeof(node));
l2=head2=(LinkedList)malloc(sizeof(node));
l3=head3=(LinkedList)malloc(sizeof(node));
l4=head4=(LinkedList)malloc(sizeof(node));
LinkedListtemp=(LinkedList)malloc(sizeof(node));
printf("分配空间完成");
intM,cntplus,cntminus;//cntplus统计加法结果的项数
cntplus=cntminus=0;
scanf("%d",&M);
for(inti=1;inext=(LinkedList)malloc(sizeof(node));
l1=l1->next;
scanf("%d",&l1->xishu);
}//两个两个读取，第一个读给系数，第二个读给指数
else
{
scanf("%d",&l1->zhishu);
}
}
l1->next=NULL;
scanf("%d",&M);
for(inti=1;inext=(LinkedList)malloc(sizeof(node));
l2=l2->next;
scanf("%d",&l2->xishu);
}
else
{
scanf("%d",&l2->zhishu);
}
}
l2->next=NULL;
l1=head1->next;l2=head2->next;
while(l1&&l2)//做加法
{
if(l1->zhishu>l2->zhishu)
{
l3->next=l1;//如果l1的指数大于l2的，那么把l1加入到结果链表l3中去，同时l1指针向后拨一个
l3=l3->next;
l1=l1->next;
}
elseif(l1->zhishuzhishu)//如果l1的指数小于l2,那么把l2加入到l3，同时l2指针向后拨一个
{
l3->next=l2;
l3=l3->next;
l2=l2->next;
}
elseif(l1->zhishu==l2->zhishu)//指数相等，可以合并
{
if(l1->xishu+l2->xishu==0)//如果合并项系数为0，那么不需要添加到l3，继续向后
{
l1=l1->next;
l2=l2->next;
//cntplus--;
}
else//合并项系数不为零，创建节点temp，为temp赋值，将temp插入到l3中去，继续向后
{
temp->xishu=l1->xishu+l2->xishu;
temp->zhishu=l1->zhishu;
l3->next=temp;
l3=l3->next;
//free(temp);
l1=l1->next;
l2=l2->next;
}
}
}
if(l1)//从while循环中跳出来后，可能有一个链表还没有遍历完，又因为多项式是降序排列的，则只需要把那个链表剩下的部分添加到链表l3中去即可
{
while(l1)
{
l3->next=l1;
l3=l3->next;
l1=l1->next;
}
}
elseif(l2)
{
while(l2)
{
l3->next=l2;
l3=l3->next;
l2=l2->next;
}
}
l3->next=NULL;
l3=head3->next;
while(l3)//把项数算出来
{
cntplus++;
l3=l3->next;
}
printf("%d",cntplus);
l3=head3->next;
show(l3);

//下面和上述操作原理一样，做减法
l1=head1->next;
l2=head2->next;
while(l1&&l2)//减法
{
if(l1->zhishu>l2->zhishu)
{
l4->next=l1;//如果l1的指数大于l2的，那么把l1加入到结果链表l4中去
l4=l4->next;
l1=l1->next;
}
elseif(l1->zhishuzhishu)
{
l4->next=l2;
l4=l4->next;
l4->xishu=-l2->xishu;//和加法有点不同的是，如果是把l2直接插入l4，那么需要添加负号
l2=l2->next;
}
elseif(l1->zhishu==l2->zhishu)
{
if(l1->xishu-l2->xishu==0)
{
l1=l1->next;
l2=l2->next;
}
else
{
//LinkedListtemp=(LinkedList)malloc(sizeof(node));
temp->xishu=l1->xishu-l2->xishu;
temp->zhishu=l1->zhishu;
l4->next=temp;
l4=l4->next;
//free(temp);
l1=l1->next;
l2=l2->next;
}
}
}
if(l1)
{
while(l1)
{
l4->next=l1;
l4=l4->next;
l1=l1->next;
}
}
elseif(l2)
{
while(l2)
{
l4->next=l2;
l4=l4->next;
l4->xishu=-l4->xishu;//同样的，把l2加入到l3需要添加负号
l2=l2->next;
}
}

l4->next=NULL;
l4=head4->next;
while(l4)
{
cntminus++;
l4=l4->next;
}
l4=head4->next;
printf("\n%d",cntminus);
show(l4);
free(l4);
return0;
}
分 -->

回复

使用道具举报

千问 | 2021-1-27 05:30:26 | 显示全部楼层

仅供参考：//链表实现一元多项式的加法减法乘法
#include
#include
typedefstructnode{
floatcoef;//系数
intexpn;//指数
structnode*next;
}
PolyNode;//多项式节点polynomialnode
typedefPolyNode*Polynomial;
PolynomialcreatePolynomial(){//创建多项式
PolyNode*p,*q,*head=(PolyNode*)malloc(sizeof(PolyNode));//头节点
head->next=NULL;
floatcoef;
intexpn;
printf("输入该多项式每一项的系数和指数，每项一行，输入00结束！\n");
while(scanf("%f%d",&coef,&expn)&&coef){//默认，按指数递减排列
if(head->next){
p=head;
while(p->next&&expnnext->expn)
p=p->next;
if(p->next){
if(expn==p->next->expn){//有相同指数的直接把系数加到原多项式
p->next->coef+=coef;
if(p->next->coef>-0.000001&&p->next->coefnext;
p->next=q->next;
free(q);
}
}else{
q=(PolyNode*)malloc(sizeof(PolyNode));
q->coef=coef;
q->expn=expn;
q->next=p->next;
p->next=q;
}
}else{
p->next=(PolyNode*)malloc(sizeof(PolyNode));
p=p->next;
p->coef=coef;
p->expn=expn;
p->next=NULL;
}
}else{
head->next=(PolyNode*)malloc(sizeof(PolyNode));
head->next->coef=coef;
head->next->expn=expn;
head->next->next=NULL;
}
}
returnhead;
}
Polynomialmultiply(Polynomialpoly,floatcoef,intexpn){//多项式与指定单项式相乘，该单项式为coefx^expn
PolyNode*p,*q,*Poly=(PolyNode*)malloc(sizeof(PolyNode));
p=Poly;
q=poly->next;
while(q){
p->next=(PolyNode*)malloc(sizeof(PolyNode));
p=p->next;
p->coef=(q->coef*coef);
p->expn=(q->expn+expn);
q=q->next;
}
p->next=NULL;
returnPoly;
}
voidadd(Polynomialpoly1,Polynomialpoly2){//把poly2加到poly1上
PolyNode*p,*q,*r;
r=poly1;
p=poly1->next;//指向第一个节点
q=poly2->next;
poly2->next=NULL;
while(p&&q){
if(p->expn>q->expn){
r->next=p;
p=p->next;
r=r->next;
}elseif(p->expnexpn){
r->next=q;
q=q->next;
r=r->next;
}else{
PolyNode*t;
p->coef+=q->coef;
if(!(p->coef>-0.000001&&p->coefnext=p;
r=r->next;
p=p->next;
}else{
t=p;
p=p->next;
free(t);
}
t=q;
q=q->next;
free(t);
}
}
if(p)
r->next=p;
if(q)
r->next=q;
}
PolynomialpolySubtract(Polynomialpoly1,Polynomialpoly2){//多项式减法poly1-poly2形成一个新的多项式
//把poly2的系数取相反数，形成一个新的多项式
Polynomialpoly=(PolyNode*)malloc(sizeof(PolyNode));//构造头节点
PolyNode*p,*q;
p=poly;
q=poly2->next;
while(q){
p->next=(PolyNode*)malloc(sizeof(PolyNode));
p=p->next;
p->coef=-(q->coef);//系数取反
p->expn=q->expn;
q=q->next;
}
p->next=NULL;
add(poly,poly1);//利用加法
returnpoly;
}
PolynomialpolyAdd(Polynomialpoly1,Polynomialpoly2){//多项式相加poly1+poly2形成一个新的多项式
Polynomialpoly=(PolyNode*)malloc(sizeof(PolyNode));//和多项式的头节点
poly->next=NULL;
PolyNode*p,*q,*r;
r=poly;
p=poly1->next;
q=poly2->next;
while(p&&q){
if(p->expn>q->expn){
r->next=(PolyNode*)malloc(sizeof(PolyNode));
r=r->next;
r->coef=p->coef;
r->expn=p->expn;
p=p->next;
}elseif(p->expnexpn){
r->next=(PolyNode*)malloc(sizeof(PolyNode));
r=r->next;
r->coef=q->coef;
r->expn=q->expn;
q=q->next;
}else{
floatm=p->coef+q->coef;
if(!(m>-0.000001&&mnext=(PolyNode*)malloc(sizeof(PolyNode));
r=r->next;
r->coef=m;
r->expn=p->expn;
}
q=q->next;
p=p->next;
}
}
while(p){
r->next=(PolyNode*)malloc(sizeof(PolyNode));
r=r->next;
r->coef=p->coef;
r->expn=p->expn;
p=p->next;
}
while(q){
r->next=(PolyNode*)malloc(sizeof(PolyNode));
r=r->next;
r->coef=q->coef;
r->expn=q->expn;
q=q->next;
}
r->next=NULL;
returnpoly;
}
PolynomialpolyMultiply(Polynomialpoly1,Polynomialpoly2){//多项式相乘
Polynomialpoly=(PolyNode*)malloc(sizeof(PolyNode));//创建多项式和的头节点
poly->next=NULL;
PolyNode*p;
p=poly2->next;
while(p){
add(poly,multiply(poly1,p->coef,p->expn));
p=p->next;
}
returnpoly;
}
voidprintPoly(Polynomialpoly){//打印多项式
if(poly&&poly->next){
PolyNode*p=poly->next;//p指向第一个节点
while(p->next){
printf("%gx^%d",p->coef,p->expn);
p=p->next;
if(p&&(p->coef>0))
printf("+");
}
if(p->expn==0)
printf("%g",p->coef);//打印常数项
else
printf("%gx^%d",p->coef,p->expn);
printf("\n");
}
}
voidfreePoly(Polynomialpoly){//释放内存
if(poly&&poly->next){
PolyNode*p,*q;
p=poly;
while(p){
q=p->next;
free(p);
p=q;
}
}
poly=NULL;
}
intmain(){
printf("用链表实现多项式的加减法\n");
Polynomialpoly1,poly2,poly3;
printf("创建多项式一\n");
poly1=createPolynomial();
printf("多项式一：\n");
printPoly(poly1);
printf("创建多项式二\n");
poly2=createPolynomial();
printf("多项式二：\n");
printPoly(poly2);
printf("两多项式相加，和为：\n");
poly3=polyAdd(poly1,poly2);
printPoly(poly3);
freePoly(poly3);
printf("两个多项式相乘，积为：\n");
poly3=polyMultiply(poly1,poly2);
printPoly(poly3);
freePoly(poly3);
printf("两多项式相减，差为：\n");
poly3=polySubtract(poly1,poly2);
printPoly(poly3);
freePoly(poly1);
freePoly(poly2);
freePoly(poly3);
system("pause");
return0;
}

回复

使用道具举报

千问 | 2021-1-27 05:30:26 | 显示全部楼层

建议楼主把功能从main函数里独立出去，比如加法，减法，合并分别做独立的函数。楼主这样写在main函数里，会导致代码的可读性大大降低。
先调整一下代码吧，这样也便于查找问题～
#include
#include
#include
typedefintelem_type;
typedefstructpoly_key{
elem_typeratio;
elem_typepower;
}poly_obj,*poly_handle;
typedefstructpoly_node{
poly_objpoly;
structpoly_node*next;
}polynomial_obj,*polynomial_handle;
typedefint(*pfunc)(poly_obj,poly_obj);

staticpolynomial_handlecreate_node(void)
{
polynomial_handlepnew;
pnew=(polynomial_handle)malloc(sizeof(polynomial_obj));
if(!pnew){
fprintf(stderr,"mallocerror!\n");
returnNULL;
}
pnew->poly.ratio=0;
pnew->poly.power=0;
pnew->next=NULL;
returnpnew;
}
/*Createapolynomial*/
voidcreate_polynomial_link(polynomial_handle*phead)
{
polynomial_handlep,q;
while(1){
p=create_node();
printf("Pleaseinputtwonumbers(ratioandpower):");
scanf("%d%d",&p->poly.ratio,&p->poly.power);
if(p->poly.ratio==0)/*ifratioisequalzero,thenbreakfromwhile.*/
break;
if(!(*phead)){
*phead=p;
q=*phead;
continue;
}
q->next=p;
q=p;
}
free(p);
}

voidshow_polynomial_link(polynomial_handlephead)
{
polynomial_handlepcur;
pcur=phead;
while(pcur){
printf("%dx^%d",pcur->poly.ratio,pcur->poly.power);
pcur=pcur->next;
}
putchar(10);
}
intget_length_polynomial(polynomial_handlephead)
{
intcnt=0;
polynomial_handlepcur=phead;
while(pcur){
cnt++;
pcur=pcur->next;
}
returncnt;
}
/*flag:0:comparebyratio,1:comparebypower*/
staticintcheck_cond(polynomial_handlepnode,intval,intflag)
{
assert(pnode);
if(flag)
return(pnode->poly.power==val);
else
return(pnode->poly.ratio==val);
}

voiddelete_polynomail(polynomial_handle*phead,intval,intflag)
{
polynomial_handlepcur,prev;
pcur=prev=*phead;
while(pcur){
if(check_cond(pcur,val,flag)){
if(pcur==*phead){
*phead=(*phead)->next;
free(pcur);
pcur=*phead;
continue;
}
prev->next=pcur->next;
free(pcur);
pcur=prev->next;
}else{
prev=pcur;
pcur=pcur->next;
}
}
}
staticintcompare_as_ratio(poly_obja,poly_objb)
{
return(a.ratio-b.ratio);
}
staticintcompare_as_power(poly_obja,poly_objb)
{
return(a.power-b.power);
}
voidbubble_asc_sort(polynomial_handlephead,pfunccmp)
{
polynomial_handlep,q;
poly_objtmp;
for(p=phead;p;p=p->next)
for(q=phead;q->next;q=q->next)
if(cmp(q->poly,q->next->poly)>0){
tmp=q->poly;
q->poly=q->next->poly;
q->next->poly=tmp;
}
}
/*insertnodebeforephead*/
voidinsert_polynomail_node(polynomial_handle*phead,poly_objparam)
{
polynomial_handlepnew;
pnew=create_node();
pnew->poly=param;
pnew->next=*phead;
*phead=pnew;
}
voiddestroy_polynomail_link(polynomial_handlephead)
{
polynomial_handlepcur,prev;
pcur=phead;
while(pcur){
prev=pcur->next;
free(pcur);
pcur=prev;
}
}
intmain(void)
{
intlen,flag,val;
polynomial_handlephead=NULL;
poly_objpoly;
create_polynomial_link(&phead);
show_polynomial_link(phead);
printf("Addoneterm(ratio,power):");
scanf("%d%d",&poly.ratio,&poly.power);
insert_polynomail_node(&phead,poly);
printf("Afterinsert:\n");
show_polynomial_link(phead);
len=get_length_polynomial(phead);
printf("Thetermofpolynomialis%d\n",len);

bubble_asc_sort(phead,compare_as_ratio);
printf("Aftersortasratio:\n");
show_polynomial_link(phead);
bubble_asc_sort(phead,compare_as_power);
printf("Aftersortaspower:\n");
show_polynomial_link(phead);
printf("Delterms,delratioorpower(0,1):");
scanf("%d",&flag);
printf("Pleaseinputanumber:");
scanf("%d",&val);
delete_polynomail(&phead,val,flag);
printf("Afterdelete:\n");
show_polynomial_link(phead);
destroy_polynomail_link(phead);
return0;
}

个人写的多项式，供参考～

回复

使用道具举报

返回列表发新帖

主题	0 回帖	4882万积分

Rank: 8 Rank: 8

积分: 48824836

回复楼主返回列表

问答

热门排行