#include <iostream.h> #include <stdio.h> #include <stdlib.h> #include <malloc.h> typedef int datatype;
typedef struct node { float coef; /*多项式系数*/ int expn; /*多项式指数*/ struct node *next; }listnode;
typedef listnode *linklist;
/*---------创建带头结点的多项式链表--------*/ linklist creat() { linklist head,s,p,pre,r; float coef; int expn; head=(linklist)malloc(sizeof(listnode)); /*表头结点*/ head->next=NULL; cout<<"输入系数："; cin>>coef; cout<<endl<<"输入指数："; cin>>expn; while (coef!=0) { cout<<"用系数0作为结束标记!"<<endl; s=(linklist)malloc(sizeof(listnode)); /*生成新结点*/ s->coef=coef; s->expn=expn; s->next=NULL; pre=head; /*插入到有序的多项式链表中去*/ p=head->next; while (p && p->expn <expn) { pre=p; p=p->next; } s->next=p; pre->next=s; cout<<"'读下一项"; cout<<endl<<"输入系数："; cin>>coef; cout<<endl<<"输入指数:"; cin>>expn; } return head; } /*-----------输出多项式链表-------------*/ void print(linklist head) { linklist p; p=head->next; while (p) { cout<<p->coef<<"x^"<<p->expn<<"+"; p=p->next; } cout<<endl; }
/*-------------多项式相加----------------*/ linklist add(linklist pa,linklist pb) { linklist p,q,pre,r,head; float x; p=head=pa->next; //p,q 指向头接点的下一个接点，即多项式的第一个接点 q=pb->next; pre=pa; //pre指向p的前驱
while((p!=NULL)&&(q!=NULL)) //处理多项式的相加的问题 if(p->expn<q->expn) { pre=p; p=p->next; } else if (p->expn==q->expn) { x=p->coef+q->coef; if(x!=0) //系数相加不为0的情况 { p->coef=x; pre=p; p=p->next; } else //系数相加为0的情况 { pre->next=p->next; free(p); p=pre->next; } r=q; q=q->next; free(r); } else { r=q->next; q->next=p; pre->next=q; pre=q; q=r; } if(q!=NULL) pre->next=q; return head; free(pb); }
/*----主程序------*/ void main() { linklist a,b,c; cout<<"请输入第一个多项式："<<endl; a=creat(); /*创建多项式链表a*/ cout<<endl; cout<<"请输入第二个多项式："<<endl; b=creat(); /*创建多项式链表b*/ cout<<endl; cout<<"您输入的第一个多项式为："<<endl; print(a); cout<<"您输入的第二个多项式为："<<endl; print(b); cout<<endl; cout<<"两多项式相加后为："<<endl; c=add(a,b); /* 计算多项式a+b */ print(c); }
