一元稀疏多项式计算器实验.docx

一元稀疏多项式计算器实验.docx

《一元稀疏多项式计算器实验.docx》由会员分享，可在线阅读，更多相关《一元稀疏多项式计算器实验.docx（15页珍藏版）》请在冰点文库上搜索。

一元稀疏多项式计算器实验

一元稀疏多项式计数器预习报告

姓名：

刘茂学号2220

一、实验要求

（1）输入并建立多项式；

（2）输出多项式，输出形式为整数序列：

n，c1，e1，c2，e2……cn，en，其中n是多项式的项数，ci，ei分别为第i项的系数和指数。

序列按指数降序排列；

（3）多项式a和b相加，建立多项式a+b；

（4）多项式a和b相减，建立多项式a-b。

（5）多项式求值；

（6）多项式求导；

（7）求多项式的乘积。

二、测试数据：

1、（2x+5x^^11）+（7-5x^8+11x^9）=^11+11x^9+2x+7）;

2、（6x^-3-x+^^9+^9）-（-6x^-3+^2-x^2+^15

）=^^9+12x^-3-x）;

3、（1+x+x^2+x^3+x^4+x^5）+（-x^3-x^4）=（1+x+x^2+x^5）;

4、（x+x^3）+（-x-x^3）=0;

5、（x+x^100）+（x^100+x^200）=（x+2x^100+x^200）;

6、（x+x^2+x^3）+0=x+x^2+x^3.

7、互换上述测试数据中的前后两个多项式。

三、思路分析

用带表头结点的单链表存储多项式。

本程序要求输入并建立多项式，能够降幂显示出多项式，实现多项式相加相减的计算问题，输出结果。

采用链表的方式存储链表，定义结点结构体。

运用尾差法建立两条单链表，以单链表polynp和polynh分别表示两个一元多项式a和b。

为实现处理，设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项。

①若p->expnexpn，则结点p所指的结点应是“和多项式”中的一项，令指针p后移。

②若p->expn=q->expn，则将两个结点中的系数相加，当和不为0时修改结点p的系数。

③若p->expn>q->expn，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移。

四、实验程序

//头文件

#include<>

#include<>

#include<>

//定义多项式的项

typedefstructPolynomial{

floatcoef;

intexpn;

structPolynomial*next;

}*Polyn,Polynomial;

voidInsert（Polynp,Polynh）{

if（p->coef==0）free（p）;//系数为0的话释放结点

else

{

Polynq1,q2;

q1=h;

q2=h->next;

while（q2&&p->expnexpn）

{//查找插入位置

q1=q2;

q2=q2->next;

}

if（q2&&p->expn==q2->expn）

{//将指数相同相合并

q2->coef+=p->coef;

free（p）;

if（!

q2->coef）

{//系数为0的话释放结点

q1->next=q2->next;

free（q2）;

}

}

else

{//指数为新时将结点插入

p->next=q2;

q1->next=p;

}

}

}

PolynCreatePolyn（Polynhead,intm）{

//建立一个头指针为head、项数为m的一元多项式

inti;

Polynp;

p=head=（Polyn）malloc（sizeof（structPolynomial））;

head->next=NULL;

for（i=0;i

{

p=（Polyn）malloc（sizeof（structPolynomial））;//建立新结点以接收数据

printf（"请输入第%d项的系数与指数:

",i+1）;

scanf（"%f%d",&p->coef,&p->expn）;

Insert（p,head）;//调用Insert函数插入结点

}

returnhead;

}

voidDestroyPolyn（Polynp）{

//销毁多项式p

Polynq1,q2;

q1=p->next;

q2=q1->next;

while（q1->next）

{

free（q1）;

q1=q2;

q2=q2->next;

}

}

voidPrintPolyn（PolynP）{

Polynq=P->next;

intflag=1;//项数计数器

if（!

q）

{//若多项式为空，输出0

putchar（'0'）;

printf（"\n"）;

return;

}

while（q）

{

if（q->coef>0&&flag!

=1）putchar（'+'）;//系数大于0且不是第一项

if（q->coef!

=1&&q->coef!

=-1）

{//系数非1或-1的普通情况

printf（"%g",q->coef）;

if（q->expn==1）putchar（'X'）;

elseif（q->expn）printf（"X^%d",q->expn）;

}

else

{

if（q->coef==1）

{

if（!

q->expn）putchar（'1'）;

elseif（q->expn==1）putchar（'X'）;

elseprintf（"X^%d",q->expn）;

}

if（q->coef==-1）

{

if（!

q->expn）printf（"-1"）;

elseif（q->expn==1）printf（"-X"）;

elseprintf（"-X^%d",q->expn）;

}

}

q=q->next;

flag++;

}

printf（"\n"）;

}

intcompare（Polyna,Polynb）{

if（a&&b）

{

if（!

b||a->expn>b->expn）return1;

elseif（!

a||a->expnexpn）return-1;

elsereturn0;

}

elseif（!

a&&b）return-1;//a多项式已空，但b多项式非空

elsereturn1;//b多项式已空，但a多项式非空

}

PolynAddPolyn（Polynpa,Polynpb）{//求解并建立多项式a+b，返回其头指针

Polynqa=pa->next;

Polynqb=pb->next;

Polynheadc,hc,qc;

hc=（Polyn）malloc（sizeof（structPolynomial））;//建立头结点

hc->next=NULL;

headc=hc;

while（qa||qb）

{

qc=（Polyn）malloc（sizeof（structPolynomial））;

switch（compare（qa,qb））{

case1:

{

qc->coef=qa->coef;

qc->expn=qa->expn;

qa=qa->next;

break;

}

case0:

{

qc->coef=qa->coef+qb->coef;

qc->expn=qa->expn;

qa=qa->next;

qb=qb->next;

break;

}

case-1:

{

qc->coef=qb->coef;

qc->expn=qb->expn;

qb=qb->next;

break;

}

}

if（qc->coef!

=0）

{

qc->next=hc->next;

hc->next=qc;

hc=qc;

}

elsefree（qc）;//当相加系数为0时，释放该结点

}

returnheadc;

}

PolynSubtractPolyn（Polynpa,Polynpb）{//求解并建立多项式a-b，返回其头指针

Polynh=pb;

Polynp=pb->next;

Polynpd;

while（p）

{//将pb的系数取反

p->coef*=-1;

p=p->next;

}

pd=AddPolyn（pa,h）;

for（p=h->next;p;p=p->next）//恢复pb的系数

p->coef*=-1;

returnpd;

}

intValuePolyn（Polynhead,intx）{

//输入x值，计算并返回多项式的值

Polynp;

inti;

intsum=0,t;

for（p=head->next;p;p=p->next）

{

t=1;

for（i=p->expn;i!

=0;）

{

if（i<0）{t/=x;i++;}//指数小于0，进行除法

else{t*=x;i--;}//指数大于0，进行乘法

}

sum+=p->coef*t;

}

returnsum;

}

PolynDerivative（Polynhead）{

//求解并建立导函数多项式，并返回其头指针

Polynq=head->next,p1,p2,hd;

hd=p1=（Polyn）malloc（sizeof（structPolynomial））;//建立头结点

hd->next=NULL;

while（q）

{

if（q->expn!

=0）

{//该项不是常数项时

p2=（Polyn）malloc（sizeof（structPolynomial））;

p2->coef=q->coef*q->expn;

p2->expn=q->expn-1;

p2->next=p1->next;//连接结点

p1->next=p2;

p1=p2;

}

q=q->next;

}

returnhd;

}

PolynMultiplyPolyn（Polynpa,Polynpb）{

//求解并建立多项式a*b，返回其头指针

Polynhf,pf;

Polynqa=pa->next;

Polynqb=pb->next;

hf=（Polyn）malloc（sizeof（structPolynomial））;//建立头结点

hf->next=NULL;

for（;qa;qa=qa->next）

{

for（qb=pb->next;qb;qb=qb->next）

{

pf=（Polyn）malloc（sizeof（structPolynomial））;

pf->coef=qa->coef*qb->coef;

pf->expn=qa->expn+qb->expn;

Insert（pf,hf）;//调用Insert函数以合并指数相同的项

}

}

returnhf;

}

voidmain（）

{

intm,n,a,x;

charflag;

Polynpa=0,pb=0,pc;

printf（"欢迎使用多项式操作程序\n\n"）;

printf（"请输入a的项数:

"）;

scanf（"%d",&m）;

pa=CreatePolyn（pa,m）;//建立多项式a

printf（"请输入b的项数:

"）;

scanf（"%d",&n）;

pb=CreatePolyn（pb,n）;//建立多项式b

//输出菜单

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

printf（"*多项式操作程序*\n"）;

printf（"**\n"）;

printf（"*A:

输出多项式B:

输出多项式b*\n"）;

printf（"**\n"）;

printf（"*C:

输出a的导数D:

输出b的导数*\n"）;

printf（"**\n"）;

printf（"*E:

代入x的值计算aF:

代入x的值计算b*\n"）;

printf（"**\n"）;

printf（"*G:

输出a+bH:

输出a-b*\n"）;

printf（"**\n"）;

printf（"*I:

输出a*bJ:

退出程序*\n"）;

printf（"**\n"）;

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

while（a）

{

printf（"\n请选择操作：

"）;

scanf（"%c",&flag）;//空格符号一定要注意

switch（flag）

{

case'A':

case'a':

{

printf（"\n多项式a="）;

PrintPolyn（pa）;

break;

}

case'B':

case'b':

{

printf（"\n多项式b="）;

PrintPolyn（pb）;

break;

}

case'C':

case'c':

{

pc=Derivative（pa）;

printf（"\n多项式a的导函数为：

a'="）;

PrintPolyn（pc）;

break;

}

case'D':

case'd':

{

pc=Derivative（pb）;

printf（"\n多项式b的导函数为：

b'="）;

PrintPolyn（pc）;

break;

}

case'E':

case'e':

{

printf（"输入x的值：

x="）;

scanf（"%d",&x）;

printf（"\nx=%d时，a=%d\n",x,ValuePolyn（pa,x））;

break;

}

case'F':

case'f':

{

printf（"输入x的值：

x="）;

scanf（"%d",&x）;

printf（"\nx=%d时，b=%d\n",x,ValuePolyn（pb,x））;

break;

}

case'G':

case'g':

{

pc=AddPolyn（pa,pb）;

printf（"\na+b="）;

PrintPolyn（pc）;

break;

}

case'H':

case'h':

{

pc=SubtractPolyn（pa,pb）;

printf（"\na-b="）;

PrintPolyn（pc）;

break;

}

case'I':

case'i':

{

pc=MultiplyPolyn（pa,pb）;

printf（"\na*b="）;

PrintPolyn（pc）;

break;

}

case'J':

case'j':

{

printf（"\n感谢使用此程序！

\n"）;

DestroyPolyn（pa）;

DestroyPolyn（pb）;

a=0;

break;

}

default:

printf（"\n您的选择错误，请重新选择!

\n"）;

}

}

}