/******************************************************
多项式相乘
*******************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
//多项式中的一项的结构
typedef struct term{
double coef;
int expn;
struct term* next;
}PolyNode ,*pPolyNode;
//创建一个保存多项式的链表，返回指向头结点的指针。多项式按指数降序排列
pPolyNode CreatePoly()
{
PolyNode *p,*q,*s,*head=NULL;
double coef;
int expn;
head=(pPolyNode)malloc( sizeof(PolyNode) );
if(head==NULL)
{
printf("Allocable memory fail!\n");
return NULL;
}
head->coef =0.0;
head->expn =0;
head->next =NULL;
printf("Please input Coefficient and exponent (intput 0 0 end):\n");
//scanf("%lf%d",&coef,&expn);
printf("Please input Coefficient:");
scanf("%lf",&coef);
printf("please input exponent:");
scanf("%d",&expn);
while( (long)coef !=0 && expn !=0 )
{
s = (pPolyNode)malloc(sizeof(PolyNode));
s->coef = coef;
s->expn = expn;
q=head->next ;
p=head;
while(q && expn <q->expn )
{
p=q;
q=q->next;
}
if(q== NULL || expn > q->expn )
{
p->next =s;
s->next =q;
}
else
{
q->coef+=coef;
}
//read next number
printf("Please input Coefficient:");
scanf("%lf",&coef);
printf("please input exponent:");
scanf("%d",&expn);
}
return head;
}
//将多项式逆置,按升幂排列
pPolyNode Reverse(pPolyNode head)
{
PolyNode *p,*q,*t;
p=NULL;
q=head->next;
while( q!=NULL )
{
t=q->next;
q->next =p;
p=q;
q=t;
}
head->next =p;
return head;
}
//两个多项式相乘
pPolyNode multiply(pPolyNode A,pPolyNode B)
{
PolyNode *pa,*pb,*pc,*u,*head;
int k ,maxExp;
double coef;
//The head node of the multiply
head=(pPolyNode)malloc( sizeof (PolyNode) );
if(head==NULL)
{
printf("Allocable memory fail!\n");
return NULL;
}
head->coef=0.0;
head->expn =0;
head->next =NULL;
if(A->next !=NULL && B->next != NULL)
{
maxExp=(A->next) ->expn +(B->next )->expn ;
}
else
{
return head;
}
pc=head;
B=Reverse (B);
for(k=maxExp; k>=0; k--)
{
pa = A->next ;
while(pa != NULL && pa->expn >k)
pa=pa->next ;
pb = B->next ;
while( pb != NULL && pa != NULL && (pa->expn + pb->expn) < k )
pb=pb->next;
coef=0.0;
while(pa != NULL && pb != NULL )
{
if( (pa->expn +pb->expn )==k )
{
coef+=pa->coef * pb->coef;
pa=pa->next;
pb=pb->next;
}
else
{
if(( pa->expn + pb->expn ) > k )
{
pa=pa->next;
}
else
{
pb=pb->next;
}
}
}
if( coef != 0.0 )
{
u=(pPolyNode)malloc(sizeof(PolyNode));
u->coef =coef;
u->expn =k;
u->next =pc->next;
pc->next=u;
pc=u;
}
}
B=Reverse(B);
return head;
}
//print Poly
void Printpoly(pPolyNode head)
{
PolyNode *p=head->next;
while(p)
{
printf("%1.1f",p->coef);
if(p->expn )
printf("*x^%d",p->expn );
if(p->next && p->next->coef >0)
printf("+");
p=p->next;
}
}
int main()
{
pPolyNode A,B,C;
A=CreatePoly();
printf("A(x)=");
Printpoly (A);
printf("\n");
B=CreatePoly();
printf("B(x)=");
Printpoly (B);
printf("\n");
C=multiply(A,B);
//C=CreatePoly();
printf("C(x)=");
Printpoly (C);
printf("\n");
//getch();
return 0;
}