这是一个C语言实现多项式除法的代码实例，多项式除法和多项式加减乘不同,比较难以实现,所以一直是各个教材和老师避讳的,故小可今天现丑将其算法和代码贴出,算法和效率上我也不甚满意,虽不免遗笑于方家,但本着学习进步的原则,希望能得到诸君点拨。
大概描述:用被除数的最大项除以除数最大项,然后用这个商遍乘除数,其间要申请式子的拷贝,然后被除数再减遍乘过后的那个积,差又是下一轮的被除数,如此直到最后被除数幂小于除数,可能说的不很清楚,全部代码如下(通过turboc调试成功):
#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
typedef struct LinkList{
float coef;
int expn;
struct LinkList* next;
}LinkList,*PLink;
void AddPolyn(PLink *p1,PLink p2);
void SubPolyn(PLink *p1,PLink p2);
void MulPolyn(PLink *p1,PLink p2);
int cmp(int,int);
void Del(PLink*,PLink);
void Ins(PLink*,PLink);
void Append(PLink*,PLink);
void DevPolyn(PLink*,PLink*);
void Destroy(PLink*);
PLink GetMax(PLink);
void CreatePolyn(PLink *p)
{
int m;
float b;
PLink s;
printf("\nHow many polynomial:");
scanf("%d",&m);
printf("Enter the expn from large to small:");
for(m;m>0;m--)
{
s=(PLink)malloc(sizeof(LinkList));
printf("\nEnter the coef:");
scanf("%f",&b);
s->coef=b;
printf("\nEnter the expn:");
scanf("%d",&(s->expn));
s->next=(*p)->next;
(*p)->next=s;
}
}
void PrintPolyn(PLink p)
{
PLink q=p->next;
while(q!=0)
{
printf("%3.1fx^%d+",q->coef,q->expn);
q=q->next;
}
if(q==p->next)
printf("0");
}
main()
{
PLink p1=(PLink)malloc(sizeof*p1);
PLink p2=(PLink)malloc(sizeof*p2);
p1->next=p2->next=0;
p1->coef=p1->expn=p2->coef=p2->expn=0;
printf("\nBuild the p1\n");
CreatePolyn(&p1);
PrintPolyn(p1);
printf("\nBuild the p2\n");
CreatePolyn(&p2);
PrintPolyn(p2);
DevPolyn(&p1,&p2);printf("\n");
PrintPolyn(p1);
printf("\nthe surplus is:\n");
PrintPolyn(p2);
Destroy(&p1);
Destroy(&p2);
getch();
}
void AddPolyn(PLink *p1,PLink p2)//加法
{
PLink qa=(*p1)->next,ha=*p1;
PLink qb=p2->next,hb;
int a,b;
while(qa&&qb)
{
a=qa->expn;
b=qb->expn;
switch(cmp(a,b))
{
case -1:
ha=qa;qa=qa->next;break;
case 0:
qa->coef+=qb->coef;
if(qa->coef!=0)ha=qa;
else Del(&ha,qa);
qa=ha->next;
qb=qb->next;break;
case 1:
hb=(PLink)malloc(sizeof*hb);//注意:这里是加入一个拷贝,而不是改变一个链接
hb->coef=qb->coef;
hb->expn=qb->expn;
Ins(&ha,hb);
qb=qb->next;
ha=ha->next;
break;
}
}
if(qb!=0)Append(&ha,qb);
}
void SubPolyn(PLink *p1,PLink p2)
{
PLink qa=(*p1)->next,ha=*p1;
PLink qb=p2->next,hb;
int a,b;
while(qa&&qb)
{
a=qa->expn;
b=qb->expn;
switch(cmp(a,b))
{
case -1:
ha=qa;qa=qa->next;break;
case 0:
qa->coef-=qb->coef;
if(qa->coef!=0)ha=qa;
else Del(&ha,qa);
qa=ha->next;
qb=qb->next;break;
case 1:
hb=(PLink)malloc(sizeof*hb);
hb->coef=-1*qb->coef;
hb->expn=qb->expn;
Ins(&ha,hb);
qb=qb->next;
ha=ha->next;
break;
}
}
if(qb!=0)Append(&ha,qb);
ha=ha->next;
while(ha!=0)
{
ha->coef*=-1;
ha=ha->next;
}
}
void MulPolyn(PLink *p1,PLink p2)
{
PLink temp,res,qa,qb=p2->next;
res=(PLink)malloc(sizeof*res);
res->coef=res->expn=0;
res->next=0;
while(qb!=0)
{
temp=(PLink)malloc(sizeof*temp);
temp->coef=temp->expn=0;
temp->next=0;
AddPolyn(&temp,*p1);
qa=temp->next;
while(qa!=0)
{
qa->coef*=qb->coef;
qa->expn+=qb->expn;
qa=qa->next;
}
AddPolyn(&res,temp);
Destroy(&temp);
qb=qb->next;
}
temp=*p1;
*p1=res;
Destroy(&temp);
}
void DevPolyn(PLink *p1,PLink *p2)
{
PLink res2,temp1,temp2,q;
res2=(PLink)malloc(sizeof(*res2));//res2用来暂存商
res2->coef=res2->expn=0;res2->next=0;
while(GetMax(*p1)!=0&&GetMax(*p1)->expn>=GetMax(*p2)->expn)
{
temp2=(PLink)malloc(sizeof*temp2);
temp1=(PLink)malloc(sizeof(LinkList));
temp1->coef=temp1->expn=0;
temp1->next=0;
temp2->coef=(GetMax(*p1)->coef)/(GetMax(*p2)->coef);
temp2->expn=(GetMax(*p1)->expn)-(GetMax(*p2)->expn);
AddPolyn(&temp1,*p2);//temp1是p2的一个拷贝,p2在此期间一直不变
q=temp1->next;
Ins(&res2,temp2);
while(q!=0)//除数的遍乘
{
q->coef*=temp2->coef;
q->expn+=temp2->expn;
q=q->next;
}
SubPolyn(p1,temp1);//被除数减去遍乘后的积
Destroy(&temp1);
}
temp1=*p1;
temp2=*p2;
*p1=res2;*p2=temp1;
Destroy(&temp2);
}
int cmp(int a,int b)
{
if(a>b)return 1;
if(a<b)return -1;
return 0;
}
void Del(PLink *p,PLink pa)
{
(*p)->next=pa->next;
free(pa);
}
void Ins(PLink *p,PLink pa)
{
pa->next=(*p)->next;
(*p)->next=pa;
}
void Append(PLink *p,PLink pa)
{
PLink temp,end=*p;
while(pa!=0)
{
temp=(PLink)malloc(sizeof(LinkList));
temp->coef=pa->coef;
temp->expn=pa->expn;
temp->next=0;
end->next=temp;
end=temp;
pa=pa->next;
}
}
void Destroy(PLink *p)//注意,这里destroy将free掉头结点
{
while((*p)->next!=0)
Del(p,(*p)->next);
free(*p);
}
PLink GetMax(PLink p)
{
PLink q=p->next;
if(q!=0)
while(q->next!=0)
q=q->next;
else
return 0;
return q;
}
