多项式运算数据结构 实验 程序.docx

多项式运算数据结构 实验 程序.docx

《多项式运算数据结构 实验 程序.docx》由会员分享，可在线阅读，更多相关《多项式运算数据结构 实验 程序.docx（18页珍藏版）》请在冰点文库上搜索。

多项式运算数据结构实验程序

//Polynomial_list

//功能：

输入两个多项式（不要求是升幂排列，程序将自动合并同类项和排序），进行加减乘除运算

#include

#include

#include

//结点定义

typedefstructPolyNode

{

intexp;//指数

floatcoef;//系数

PolyNode*next;

}PolyNode,*PolyList;

//函数声明

PolyListCreatePolyList（）;//创建多项式链表，返回头指针

voidDisplayPolyList（PolyListPoly）;//显示多项式

voidDestroyPolyList（PolyListL）;//释放链表所用存储空间

voidMergePoly（PolyListPoly）;//将多项式和并同类项

voidSortPoly（PolyListPoly）;//将多项式按升序排列

PolyListPolyAdd（PolyListPolyA,PolyListPolyB）;//多项式相加，返回和多项式链表头指针

PolyListPolySub（PolyListpolya,PolyListpolyb）;//多项式相减，返回差多项式链表头指针

PolyListPolyMutiply（PolyListPolyA,PolyListPolyB）;//多项式相乘，结果由PolyC返回

PolyListPolyDivide（PolyListPolyA,PolyListPolyB）;//多项式相除，结果存到PolyC中，商和余数用系数为0的结点分开

//函数实现

//创建多项式链表，返回头指针

PolyListCreatePolyList（）

{

PolyNode*s,*rear,*head;

inte;//指数

floatc;//系数

intn=1;//计数器

head=（PolyNode*）malloc（sizeof（PolyNode））;

rear=head;

//输入多项式的系数和指数，若输入系数为0退出

printf（"请输入多项式的第%d项的系数和指数：

",n++）;

scanf（"%f,%d",&c,&e）;

while（fabs（c）>1e-6）

{s=（PolyNode*）malloc（sizeof（PolyNode））;

s->exp=e;

s->coef=c;

rear->next=s;

rear=s;

printf（"请输入多项式的第%d项的系数和指数：

",n++）;

scanf（"%f,%d",&c,&e）;

}

rear->next=NULL;

returnhead;

}

//计算两个多项式（可不按顺序排列），结果存到链表PolyC中，并返回

PolyListPolyAdd（PolyListPolyA,PolyListPolyB）

{

PolyListPolyC;

SortPoly（PolyA）;

SortPoly（PolyB）;

floatsum=0;//存储两项系数和

PolyNode*pa,*pb,*rear,*s;

PolyC=（PolyNode*）malloc（sizeof（PolyNode））;

pa=PolyA->next;

pb=PolyB->next;

rear=PolyC;

rear->next=NULL;

while（pa&&pb）

{

if（pa->exp==pb->exp）

{

sum=pa->coef+pb->coef;

if（fabs（sum）>1e-6）//如果两两系数不为0，则将两项和存入s中，并插入PolyC尾部

{

s=（PolyNode*）malloc（sizeof（PolyNode））;

s->coef=sum;

s->exp=pa->exp;

rear->next=s;

rear=s;

}

//pa,pb指针后移

pa=pa->next;

pb=pb->next;

}

elseif（pa->exp>pb->exp）//若pa指数大于pb指数，将pa结点副本插入到PolyC尾部

{

s=（PolyNode*）malloc（sizeof（PolyNode））;

s->coef=pa->coef;

s->exp=pa->exp;

rear->next=s;

rear=s;

pa=pa->next;

}

else//若pb指数大于pa指数，将pb结点副本插入到PolyC尾部

{

s=（PolyNode*）malloc（sizeof（PolyNode））;

s->coef=pb->coef;

s->exp=pb->exp;

rear->next=s;

pb=pb->next;

rear=s;

}

}

//插入剩余结点

while（pa）

{

s=（PolyNode*）malloc（sizeof（PolyNode））;

s->coef=pa->coef;

s->exp=pa->exp;

rear->next=s;

pa=pa->next;

rear=s;

}

while（pb）

{

s=（PolyNode*）malloc（sizeof（PolyNode））;

s->coef=pb->coef;

s->exp=pb->exp;

rear->next=s;

pb=pb->next;

rear=s;

}

rear->next=NULL;

returnPolyC;

}

//释放链表所用存储空间

voidDestroyPolyList（PolyListL）

{

PolyNode*p,*temp;

p=L;

while（p!

=NULL）

{temp=p;p=p->next;free（temp）;}

}

//将多项式和并同类项

voidMergePoly（PolyListPoly）

{

PolyNode*p,*q,*rear,*pre,*temp;

rear=Poly;

p=Poly->next;

while（rear->next!

=NULL）

{

q=p->next;

pre=p;

temp=p;

while（q）

{

if（p->exp==q->exp）//两项指数相等，合并两项，并释放结点q

{

p->coef+=q->coef;

if（fabs（p->coef）>1e-6）

{

pre->next=q->next;

temp=q;

q=temp->next;

free（temp）;

}

else//两项系数和为0，释放结点p和q

{

rear->next=p->next;

temp=p;

p=temp->next;

free（temp）;

pre->next=q->next;

temp=q;

q=temp->next;

free（temp）;

}

}

else{pre=q;q=q->next;}//指数不等，指针q后移

}

//与p指数相同的节点合并完毕，或者没有找到，p后移

rear=p;

p=rear->next;

}

rear->next=NULL;

}

//将多项式按升序排列

voidSortPoly（PolyListPoly）

{

PolyListrear,p,temp,prior;

if（!

Poly->next）return;//若多项式为空，返回

MergePoly（Poly）;

rear=Poly;

intexp;//记录当前啊搜索项中的最小指数

while（rear->next!

=NULL）

{

exp=rear->next->exp;

p=rear->next;

prior=rear;

temp=prior->next;

while（p!

=NULL）

{

if（p->exp>exp）

{

exp=p->exp;

temp=p;

p=temp->next;

}

else

{

p=p->next;

if（rear->next->next==NULL）return;//p为最后一个元素且指数最小，提前返回

}

}

while（prior->next!

=temp）prior=prior->next;

prior->next=temp->next;

temp->next=rear->next;

rear->next=temp;

rear=rear->next;

}

}

//多项式相减，返回差多项式链表头指针

PolyListPolySub（PolyListPolyA,PolyListPolyB）

{

PolyListPolyC;

SortPoly（PolyA）;

SortPoly（PolyB）;

floatsum=0;//存储两项系数差

PolyNode*pa,*pb,*rear,*s;

PolyC=（PolyNode*）malloc（sizeof（PolyNode））;

pa=PolyA->next;

pb=PolyB->next;

rear=PolyC;

rear->next=NULL;

while（pa&&pb）

{

if（pa->exp==pb->exp）

{

sum=pa->coef-pb->coef;

if（fabs（sum）>1e-6）//如果两两系数不为0，则将两项和存入s中，并插入PolyC尾部

{

s=（PolyNode*）malloc（sizeof（PolyNode））;

s->coef=sum;

s->exp=pa->exp;

rear->next=s;

rear=s;

}

//pa,pb指针后移

pa=pa->next;

pb=pb->next;

}

elseif（pa->exp>pb->exp）//若pa指数大于pb指数，将pa结点副本插入到PolyC尾部

{

s=（PolyNode*）malloc（sizeof（PolyNode））;

s->coef=pa->coef;

s->exp=pa->exp;

rear->next=s;

rear=s;

pa=pa->next;

}

else//若pb指数大于pa指数，将pb结点副本插入到PolyC尾部

{

s=（PolyNode*）malloc（sizeof（PolyNode））;

s->coef=-pb->coef;

s->exp=pb->exp;

rear->next=s;

pb=pb->next;

rear=s;

}

}

//插入剩余结点

while（pa）

{

s=（PolyNode*）malloc（sizeof（PolyNode））;

s->coef=pa->coef;

s->exp=pa->exp;

rear->next=s;

pa=pa->next;

rear=s;

}

while（pb）

{

s=（PolyNode*）malloc（sizeof（PolyNode））;

s->coef=-pb->coef;

s->exp=pb->exp;

rear->next=s;

pb=pb->next;

rear=s;

}

rear->next=NULL;

returnPolyC;

}

//输出多项式

voidDisplayPolyList（PolyListPoly）

{

if（Poly==NULL）{printf（"\n"）;return;}

PolyNode*p=Poly->next;

if（p==NULL）{printf（"0\n"）;return;}//如果链表为空提前退出

while（p->next!

=NULL）

{

if（fabs（p->coef）>1e-6）

{

if（fabs（p->next->coef）>1e-6）printf（"%f*x**%d+",p->coef,p->exp）;

elseprintf（"%f*x**%d",p->coef,p->exp）;

}

elseprintf（"......"）;//输出分割点

p=p->next;

}

if（fabs（p->coef）>1e-6）printf（"%f*x**%d",p->coef,p->exp）;

printf（"\n"）;

}

//多项式相乘，结果由PolyC返回

PolyListPolyMutiply（PolyListPolyA,PolyListPolyB）

{

PolyListPolyC;

PolyNode*pa,*pb,*pc_pre,*pc,*s;

if（PolyA==NULL||PolyB==NULL）returnNULL;//若某一个多项式为空，返回

PolyC=（PolyNode*）malloc（sizeof（PolyNode））;

pc=PolyC;

pc->next=NULL;

if（PolyA->next==NULL||PolyB->next==NULL）returnPolyC;

SortPoly（PolyA）;

SortPoly（PolyB）;

pa=PolyA->next;

pb=PolyB->next;

s=（PolyNode*）malloc（sizeof（PolyNode））;

s->coef=pa->coef*pb->coef;

s->exp=pa->exp+pb->exp;

if（pc->next==NULL）

{

pc->next=s;

pc=s;

pc->next=NULL;

}//直接插入第一个结点

while（pa）

{

pb=PolyB->next;

while（pb）

{

//两项对应相乘，结果存入到s中

pc=PolyC->next;

if（pa==PolyA->next&&pb==PolyB->next）//避免重复插入第一个结点

{

pb=pb->next;

if（pb==NULL）break;

}

s=（PolyNode*）malloc（sizeof（PolyNode））;

s->coef=pa->coef*pb->coef;

s->exp=pa->exp+pb->exp;

//查找s合适的插入位置，使得插入后PolyC仍为升序排列

while（pc&&pc->exp>s->exp）{pc_pre=pc;pc=pc_pre->next;}

if（pc==NULL）{pc_pre->next=s;s->next=NULL;pb=pb->next;}

elseif（pc->expexp）{pc_pre->next=s;s->next=pc;pb=pb->next;}

elseif（s->exp==pc->exp）

{

pc->coef+=s->coef;

free（s）;

if（fabs（pc->coef）<1e-6）{pc_pre->next=pc->next;free（pc）;}

pb=pb->next;

}

}

pa=pa->next;

}

returnPolyC;

}

//多项式相除，结果存到PolyC中，商和余数用系数为0的结点分开

PolyListPolyDivide（PolyListPolyA,PolyListPolyB）

{

if（!

PolyA||!

PolyB）returnNULL;

if（PolyB->next==NULL）{printf（"Error:

除项为空!

\n"）;returnNULL;}

PolyListPolyT1,PolyT2,pt,s,PolyC,p,s_pre;

PolyC=（PolyList）malloc（sizeof（PolyNode））;

PolyC->next=NULL;

if（PolyA->next==NULL）returnPolyC;

p=PolyA->next;

PolyT1=（PolyList）malloc（sizeof（PolyNode））;

pt=PolyT1;

s_pre=（PolyList）malloc（sizeof（PolyNode））;

while（p）//将PollyA复制到PolyT中

{

s=（PolyList）malloc（sizeof（PolyNode））;

s->coef=p->coef;

s->exp=p->exp;

pt->next=s;

pt=s;

p=p->next;

}

pt->next=NULL;

//将商存入到PolyC中

p=PolyC;

while（PolyT1->next&&PolyT1->next->exp>=PolyB->next->exp）

{

s=（PolyList）malloc（sizeof（PolyNode））;

s_pre->next=s;

s->next=NULL;

s->coef=PolyT1->next->coef/PolyB->next->coef;

s->exp=PolyT1->next->exp-PolyB->next->exp;

p->next=s;

p=s;

//PolyT2=（PolyList）malloc（sizeof（PolyNode））;

PolyT2=PolySub（PolyT1,PolyMutiply（PolyB,s_pre））;

DestroyPolyList（PolyT1）;

PolyT1=PolyT2;

}

//设置分隔结点

s=（PolyList）malloc（sizeof（PolyNode））;

s->coef=0;

s->exp=0;

p->next=s;

p=s;

p->next=PolyT1->next;//将余项PolyT复制到PolyC中

free（PolyT1）;

returnPolyC;

}

voidmain（）

{

PolyListPolyA,PolyB,PolyC;

//初始化PolyA，PolyB，以0结束

printf（"************************************************************************\n"）;

PolyA=CreatePolyList（）;

printf（"输入的PolyA:

"）;

DisplayPolyList（PolyA）;

printf（"************************************************************************\n"）;

PolyB=CreatePolyList（）;

printf（"输入的PolyB:

"）;

DisplayPolyList（PolyB）;

printf（"************************************************************************\n"）;

SortPoly（PolyA）;

printf（"合并排序后的PolyA:

"）;

DisplayPolyList（PolyA）;

SortPoly（PolyB）;

printf（"合并排序后的PolyB:

"）;

DisplayPolyList（PolyB）;

printf（"************************************************************************\n"）;

//PolyA+PolyB

PolyC=PolyAdd（PolyA,PolyB）;

printf（"PolyA+PolyB:

"）;

DisplayPolyList（PolyC）;

DestroyPolyList（PolyC）;

printf（"************************************************************************\n"）;

//PolyA-PolyB

PolyC=PolySub（PolyA,PolyB）;

printf（"PolyA-PolyB:

"）;

DisplayPolyList（PolyC）;

DestroyPolyList（PolyC）;

//PolyA*PolyB

printf（"************************************************************************\n"）;

PolyC=PolyMutiply（PolyA,PolyB）;

printf（"PolyA*PolyB:

"）;

DisplayPolyList（PolyC）;

DestroyPolyList（PolyC）;

//PolyA/PolyB

printf（"************************************************************************\n"）;

PolyC=PolyDivide（PolyA,PolyB）;

printf（"PolyA/PolyB:

"）;

DisplayPolyList（PolyC）