#include#include #define LEN sizeof(PolyNode)typedef struct node{ //声明多项式节点的结构体表示 float coef; //系数 int exp; //指数 struct node* next;}PolyNode; //多项式节点typedef PolyNode* Polynomial; Polynomial create(){ //输入并创建链表的函数 Polynomial p,q,head=(Polynomial)malloc(LEN); float coef; int exp; head->next=NULL; printf("Please enter the coef and exp,ending with '0 0':"); while(scanf("%f %d",&coef,&exp)&&coef){ if(head->next){ p=head; while(p->next&&exp next->exp) //找到要插入的位置，插在p节点的后面 p=p->next; if(p->next){ if(p->next->exp==exp){ //有相同指数时直接加到原来的节点上 p->next->coef+=coef; if(p->next->coef>-0.000001&&p->next->coef<0.000001){ //若系数之和为零，则舍去该点,浮点运算存在误差 q=p->next; p->next=q->next; free(q); } } else{ q=(Polynomial)malloc(LEN); q->coef=coef; q->exp=exp; q->next=p->next; p->next=q; } } else{ //若要插入的系数最小，插在最末 p->next=(Polynomial)malloc(LEN); p->next->coef=coef; p->next->exp=exp; p->next->next=NULL; } } else{ //插入第一个节点时 head->next=(Polynomial)malloc(LEN); head->next->coef=coef; head->next->exp=exp; head->next->next=NULL; } } return head;}Polynomial add(Polynomial poly1,Polynomial poly2){ //将poly1,poly2相加得到一个新多项式链表poly3 Polynomial p,q,r,poly=(Polynomial)malloc(LEN); //poly为和多项式链表的头节点 poly->next=NULL; r=poly; //r指向poly的最后一个节点 p=poly1->next; q=poly2->next; while(p&&q){ if(p->exp>q->exp){ r->next=(Polynomial)malloc(LEN); r=r->next; r->coef=p->coef; r->exp=p->exp; p=p->next; } else if(p->exp exp){ r->next=(Polynomial)malloc(LEN); r=r->next; r->coef=q->coef; r->exp=q->exp; q=q->next; } else{ float m=p->coef+q->coef; if(!(m>-0.000001&&m<0.000001)){ r->next=(Polynomial)malloc(LEN); r=r->next; r->coef=m; r->exp=p->exp; } p=p->next; q=q->next; } } while(p){ //若p中有剩余 r->next=(Polynomial)malloc(LEN); r=r->next; r->coef=p->coef; r->exp=p->exp; p=p->next; } while(q){ //若q中有剩余 r->next=(Polynomial)malloc(LEN); r=r->next; r->coef=q->coef; r->exp=q->exp; q=q->next; } r->next=NULL; return poly;}void polyAdd(Polynomial poly1,Polynomial poly2){ //把poly2加到poly1上，加完之后poly1为和多项式，poly2将被释放 Polynomial p,q,t; q=poly2->next; while(q){ p=poly1; while(p->next&&q->exp next->exp) //找到要插入poly1的位置，插在p与p->next之间 p=p->next; if(p->next){ //插在poly1中间 if(q->exp==p->next->exp){ //若要插入节点的系数等于p->next的系数 float m=q->coef+p->next->coef; if(m>-0.000001&&m<0.000001){ Polynomial tmp1=p->next; p->next=tmp1->next; free(tmp1); } else{ p->next->coef=m; } } else{ Polynomial tmp2=(Polynomial)malloc(LEN); tmp2->coef=q->coef; tmp2->exp=q->exp; tmp2->next=p->next; p->next=tmp2; } } else{ //插在poly1末端 p->next=(Polynomial)malloc(LEN); p->next->coef=q->coef; p->next->exp=q->exp; p->next->next=NULL; } t=q; q=q->next; free(t); } free(poly2); //释放poly2的头节点}Polynomial multiply(Polynomial poly,float coef,int exp){ //多项式poly与单项coef^exp相乘，返回乘法之后的多项式链表 Polynomial p,r,head=(Polynomial)malloc(LEN); head->next=NULL; r=head; p=poly->next; while(p){ r->next=(Polynomial)malloc(LEN); r=r->next; r->coef=p->coef*coef; r->exp=p->exp+exp; p=p->next; } return head;}Polynomial polyMultiply(Polynomial poly1,Polynomial poly2){ //返回poly1*poly2的多项式链表 Polynomial p,poly=(Polynomial)malloc(LEN); //乘积多项式的头指针 poly->next=NULL; p=poly2->next; while(p){ polyAdd(poly,multiply(poly1,p->coef,p->exp)); //把poly1和poly2中的每一项相乘后求和 p=p->next; } return poly;}void print(Polynomial poly){ //输出链表的函数 if(poly&&poly->next){ Polynomial p=poly->next; while(p){ if(p->next==NULL){ //当p为最后一个节点时 if(p->exp!=0) printf("%fx^%d",p->coef,p->exp); else printf("%f",p->coef); } else{ printf("%fx^%d",p->coef,p->exp); if(p->next->coef>0) printf("+"); } p=p->next; } printf("\n"); } else printf("0.000000\n");}void clear(Polynomial poly){ //释放内存 if(poly&&poly->next){ Polynomial p,q; p=poly; while(p){ q=p->next; free(p); p=q; } } poly=NULL;}int main(){ Polynomial p1,p2,p3,p4; printf("Please input p1:\n"); p1=create(); printf("Please input p2:\n"); p2=create(); printf("p1="); print(p1); printf("p2="); print(p2); p3=add(p1,p2); //p3=p1+p2 printf("p3=p1+p2="); print(p3); p4=polyMultiply(p1,p2); //p4=p1*p2 printf("p4=p1*p2="); print(p4); clear(p1); //释放内存 clear(p2); clear(p3); clear(p4); return 0;}