一元稀疏多项式的运算.docx

一元稀疏多项式的运算.docx

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

一元稀疏多项式的运算

《高级语言程序设计》

课程设计报告

题目：

一元稀疏多项式的运算

专业：

班级：

姓名：

指导教师：

成绩：

计算机与信息工程系

2014年6月20日

目录

1设计内容与要求1

1.1设计内容1

1.2主要功能与要求1

2概要设计1

2.1设计思路1

2.2设计思路分析1

2.3主要模块和流程2

3设计过程4

3.1代码分析及确定4

3.2关键代码解释8

4设计结果与分析11

4.1设计结果11

4.2分析12

5参考文献13

附录：

源代码14

1设计内容与要求

1.1设计内容

设计一个一元稀疏多项式简单计算器

1.2主要功能与要求

1输入并建立多项式

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

n，c1,e1,c2,e2,………cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；

3求多项式a、b的导函数

4计算多项式在x处的值

5多项式a和b相加，建立多项式a+b

6多项式a和b相减，建立多项式a-b

2概要设计

2.1设计思路

1定义线性表的动态分配顺序存储结构；

2建立多项式存储结构，定义指针*next

3利用链表实现队列的构造。

每次输入一项的系数和指数，可以输出构造的一元多项式

4演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；最后根据相应的输入数据（滤去输入中的非法字符）建立的多项式以及多项式相加的运行结果在屏幕上显示。

多项式显示的格式为：

c1x^e1+c2x^e2+…+cnx^en

2.2设计思路分析

要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为

序数coef

指数expn

指针域next

运用尾插法建立两条单链表，以单链表polynp和polynh分别表示两个一元多项式a和b，a+b的求和运算等同于单链表的插入问题（将单链表polynp中的结点插入到单链表polynh中），因此“和多项式”中的结点无须另生成。

为了实现处理，设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项，由此得到下列运算规则：

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

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

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

2.3主要模块和流程

15

26

37

48

9

3设计过程

3.1代码分析及确定

1）元素类型、结点类型和指针类型：

typedefstructPolynomial{

floatcoef;//系数

intexpn;//指数

structPolynomial*next;

}*Polyn,Polynomial;

2）建立一个头指针为head、项数为m的一元多项式,建立新结点以接收数据,调用Insert函数插入结点:

PolynCreatePolyn（Polynhead,intm）{

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）;

}

returnhead;

}

3）主函数和其他函数：

voidmain（）

{

intm,n,a,x;

charflag;

Polynpa=0,pb=0,pc;

}

floatValuePolyn（Polynhead,intx）//输入x值，计算并返回多项式的值

4）界面代码：

printf（"--------------------------------------------------\n"）;

printf（"|数字媒体技术13级

（2）班于富洋|\n"）;

printf（"--------------------------------------------------\n"）;

printf（"欢迎使用一元稀疏多项式操作程序\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:

输出多项式aB:

输出多项式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"）;

5）在主函数中调用子函数代码：

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=%.3f\n",x,ValuePolyn（pa,x））;

break;

}

case'F':

case'f':

{

printf（"输入x的值：

x="）;

scanf（"%d",&x）;

printf（"\nx=%d时，b=%.3f\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"）;

}

}

}

3.2关键代码解释

1）这段代码主要求a-b，利用指针返回，首先将将pb的系数取反进行判断，然后恢复pb的系数输入x值，计算并返回多项式的值

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;

}

floatValuePolyn（Polynhead,intx）{//输入x值，计算并返回多项式的值

Polynp;

inti,t;

floatsum=0;

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;

}

2）求解并建立导函数多项式，并返回其头指针，然后判断是不是常数项，再进行数据处理。

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;

}

3）求解并建立多项式a*b，返回其头指针，调用Insert函数以合并指数相同的项

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;

}

4设计结果与分析

4.1设计结果

代码正确,可以正常运行。

实例：

对x+2x2+3x5与2x2+2x2+2x2进行运算

4.2分析

程序的运行环境是VC6.0，所以可以对代码进行较好的编写与处理，比如说可以对代码进行复制、删除、粘贴等操作（这些都优于TC）。

当把代码进行调试时，遇到了很多预想不到的麻烦。

1）定义函数类型时，没有较好的选择适当的类型，进而导致结果错误。

所以以后要注意：

前后定义变量要统一。

2）如果要调用添加函数，修改函数，修改函数，查找函数，统计函数等要在主函数前面进行申明。

否则会显示警告。

3）在运行的过程中，对于一个循环语句，遇到了返回的值始终是真，程序进如死循环，这是编写代码粗心造成的，以后必须警示。

4）因为此程序是简单的一元稀疏多项式的运算，所以精确度不是要求过高，但还是得对精确度进行明确，否则结果会出现错误。

在编写程序过程中明白了很多重要的步骤以及注意事项

1编写代码前要对要求进行明确。

2作出流程图。

3对各部分进行模块化，然后编写代码。

4用最规范的、最清晰的、最容易理解的方式写程序。

5在编程中，应仔细研究编译程序给出的错误信息和警告信息，弄清楚每条信息的确切根源并予以解决。

6对关键语句进行注释。

5参考文献

[1]谭浩强著.C程序设计（第二版）.北京：

清华大学出版社，1999

[2]谭浩强编著.QBASIC语言教程.北京：

电子工业出版社，1997

[3]谭浩强.C程序设计[M].3版.北京：

清华大学出版社，2005

[4]HerbertSchildt著.戴健鹏译.C语言大全（第二版）.北京：

电子工业出版社，1994

附录：

源代码

#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;

}

floatValuePolyn（Polynhead,intx）{//输入x值，计算并返回多项式的值

Polynp;

inti,t;

floatsum=0;

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）