一元稀疏多项式计算器C语言课程设计.docx

一元稀疏多项式计算器C语言课程设计.docx

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

计算机学院《软件工程》课程设计报告

学号

2014-2015学年第二学期

1308210115

《软件工程》

课程设计报告

题目：

一元稀疏多项式计算器

专业：

计算机科学与技术

班级：

计算机科学与技术

（2）班

姓名：

指导教师：

成绩：

一、问题描述 3

二、需求分析 3

三、概要设计 4

四、详细设计 5

五、源代码 6

六、程序测试 18

七、使用说明 24

八、课设总结 25

一、问题描述

1.1基本要求

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

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

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

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

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

（5）计算多项式在x处的值。

（6）计算器的仿真界面。

1.2设计目的

数据结构是实践性很强的课程。

课程设计是加强学生实践能力的一个强有力手段。

课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。

严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用

二、需求分析

2.1设计开发环境：

软件方面：

系统windows7编程软件：

VC++6.0

2.2思路分析：

①一般情况下的一元n次多项式可写成pn（x）=p1xe1+p2xe2+……+pmxem

其中，p1是指数为ei的项的非零系数，且满足0≦e1

②用两个带表头结点的单链表分别存储两个多项式

③根据一元多项式相加的运算规则：

对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；

④只需要将第二个多项式的系数改为其相反数，然后根据一元多项式相加的运算规则便可以得到其相应的“差多项式”

三、概要设计菜单

加法

AddPolyn（ma,mb）

减法SubtractPolyn（ma,mb）

乘法

MultiplyPolyn（ma,mb）

求值ValuePolyn（ma,x）

输入Insert（Polynp,Polynh）

除法DevicePolyn（ma,mb）

输出desktop（）

图3-1功能模块图

为实现上述程序功能，用带表头结点的单链表存储多项式。

元素类型，节点类型，和指针类型：

typedefstructPolynomial{

intcoe;//系数

intexp;//指数

structPolynomial*next;

}*Polyn,Polynomial;

各个模块之间的调用如图3-1所示，调用insert（）函数将输入的多项式按降幂排列，通过主函数main（）中swith语句，选择用户所选择的对应的模块，然后又模块对应的功能函数对用户输入的数据进行相应的操作，最后通过desktop（）模块将最后结果输出。

四、详细设计

开始运行

多项式加法计算器

退出

求积、商

求和（差）

输入多项式

关闭运行

多项式相加求和

（差）

多项式求积、商

建立2个多项式

输出结果

输出求和（差）

结果

按任意键退出

图4-1功能实现流程图

4.1输入模块

用户可通过本模块来输入一个多项式，在每次输入一个多项式时，本模块会先判断谁否是第一次输入，如果是，创建节点，如果不是则模块会通过判断本次输入的数的指数与第一项输入的指数的大小，如果第一项的指数较大，则刚输入的这一项继续与第二项比较指数，以此类推，如果发现刚输入的这一项的指数比比较的这一项的指数要大，则插入比较项的前面。

4.2求和、差模块

用户通过本模块可以实现两个多项式的求和或差值，此模块先调用输入模块，进行对两个要运算的多项式进行初始化，并按降幂排列。

然后将两个多项式的幂进行一个对比，如果第一个数的第一项的系数大于第二个多项式的第一个项的系数，那么直接将第一项赋值于刚开始创建的链表的第一项，作为答案的最后一项，反之亦然，如果第一个数的第一项，与第二个数的第一项的系数相同，那么将两个数的系数与指数分别相加或者相减并将对应值赋值给答案相对应的项。

以此类推。

最后有输出模块输出最后答案。

4.3求积、商模块

用户可通过该模块实现两个多项式的相乘（相除），此模块先调用输入模块，进行对两个要运算的多项式的初始化，并按降幂排列。

然后将第一个数的系数、指数与第二个数的系数、指数分别相乘（相除），相加（相减），并且赋值给答案相应的系数、指数。

完成后执行第一个数的第一项与第二个数的第二项进行相应的操作…….执行完之后最后调用输出模块将结果输出到屏幕上。

4.4求值模块

用户可通过此模块实现多项式的求值，此模块调用输入模块，完成相对应的操作，然后需要用户输入此时变量的值，并且将变量的值赋值给变量，最后将答案通过输出模块输出到屏幕上。

五、源代码

[键入文字]6[键入文字]

#include

#include

#include

typedefstructPolynomial{

intcoe;//系数

intexp;//指数

structPolynomial*next;

}*Polyn,Polynomial;

Polynma,mb;

voidInsert（Polynp,Polynh）

{

if（p->coe==0）deletep;

else{

Polynq1,q2;

q1=h;q2=h->next;

while（q2&&p->expexp）

{

q1=q2;

q2=q2->next;

}

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

{

q2->coe+=p->coe;

deletep;

if（!

q2->coe）

{

q1->next=q2->next;

deleteq2;}

}

else

{

p->next=q2;

q1->next=p;

}

}

}

PolynCreatePolyn（Polynhead,intm）

{

inti;

Polynp;

p=head=newPolynomial;

head->next=NULL;

for（i=0;i

p=newPolynomial;;

cout<<"请输入第"<

";

cin>>p->coe;

cout<<"指数:

";

cin>>p->exp;

Insert（p,head）;

}

returnhead;

}

voidDestroyPolyn（Polynp）

{

Polynt;

while（p!

=NULL）

{

t=p;

p=p->next;

deletet;

}

}

voidPrintPolyn（PolynPm）

{

Polynqa=Pm->next;

intflag=1;

if（!

qa）

{

cout<<"0";

cout<

return;

}

while（qa）

{

if（qa->coe>0&&flag!

=1）cout<<"+";

if（qa->coe!

=1&&qa->coe!

=-1）

{

cout<coe;

if（qa->exp==1）cout<<"X";

elseif（qa->exp）cout<<"X^"<exp;

}

else

{

if（qa->coe==1）

{

if（!

qa->exp）cout<<"1";

elseif（qa->exp==1）cout<<"X";

elsecout<<"X^"<exp;

}

if（qa->coe==-1）

{

if（!

qa->exp）cout<<"-1";

elseif（qa->exp==1）cout<<"-X";

elsecout<<"-X^"<exp;

}

}

qa=qa->next;

flag++;

}

cout<

}

intcompare（Polyna,Polynb）

{

if（a&&b）

{

if（!

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

elseif（!

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

elsereturn0;

}

elseif（!

a&&b）return-1;

elsereturn1;

}

PolynAddPolyn（Polynpa,Polynpb）

{

Polynqa=pa->next;

Polynqb=pb->next;

Polynheadc,hc,qc;

hc=newPolynomial;

hc->next=NULL;

headc=hc;

while（qa||qb）

{

qc=newPolynomial;

switch（compare（qa,qb））

{

case1:

{

qc->coe=qa->coe;

qc->exp=qa->exp;

qa=qa->next;

break;

}

case0:

{

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

qc->exp=qa->exp;

qa=qa->next;

qb=qb->next;

break;

}

case-1:

{

qc->coe=qb->coe;

qc->exp=qb->exp;

qb=qb->next;

break;

}

}

if（qc->coe!

=0）

{

qc->next=hc->next;

hc->next=qc;

hc=qc;

}

elsedeleteqc;

}

returnheadc;

}

PolynSubtractPolyn（Polynpa,Polynpb）

{

Polynh=pb;

Polynp=pb->next;

Polynpd;

while（p）

{

p->coe*=-1;

p=p->next;

}

pd=AddPolyn（pa,h）;

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

p->coe*=-1;

returnpd;

}

PolynMultiplyPolyn（Polynpa,Polynpb）

{

Polynhf,pf;//

Polynqa=pa->next;//新建一个结点作为pa的后继结点

Polynqb=pb->next;//新建一个结点作为pb的后继结点

hf=newPolynomial;

hf->next=NULL;

while（qa）//使用while循环，使得多项式的每项得以运算

{

qb=pb->next;

while（qb）

{

pf=newPolynomial;

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

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

Insert（pf,hf）;//调用插入函数，将新的结点插入到新建链表中，并合并同类项

qb=qb->next;

}

qa=qa->next;

}

returnhf;//返回所得链表的头指针

}

voidDevicePolyn（Polynpa,Polynpb）

{

Polynquotient,remainder,temp1,temp2;

Polynqa=pa->next;

Polynqb=pb->next;

quotient=newPolynomial;//建立头结点,存储商

quotient->next=NULL;

remainder=newPolynomial;//建立头结点，存储余数

remainder->next=NULL;

temp1=newPolynomial;

temp1->next=NULL;

temp2=newPolynomial;

temp2->next=NULL;

temp1=AddPolyn（temp1,pa）;

while（qa!

=NULL&&qa->exp>=qb->exp）

{

temp2->next=newPolynomial;

temp2->next->coe=（qa->coe）/（qb->coe）;

temp2->next->exp=（qa->exp）-（qb->exp）;

Insert（temp2->next,quotient）;

pa=SubtractPolyn（pa,MultiplyPolyn（pb,temp2））;

qa=pa->next;

temp2->next=NULL;

}

remainder=SubtractPolyn（temp1,MultiplyPolyn（quotient,pb））;

pb=temp1;

cout<

"）;

PrintPolyn（quotient）;

cout<<"yushu"<

"）;

PrintPolyn（remainder）;

}

floatValuePolyn（Polynhead,floatx）

{

Polynp;

p=head->next;

floatresult=0;

while（p!

=NULL）

{

result+=（p->coe）*（float）pow（x,p->exp）;

p=p->next;

}

returnresult;

}

voiddesktop（）

{

system（"cls"）;

cout<

cout<<" **********************************************"<

cout<<" **1.输出多项式a和b**"<

cout<<" **2.建立多项式a+b**"<

cout<<" **3.建立多项式a-b**"<

cout<<" **4.建立多项式a*b**"<

cout<<" **5.建立多项式a/b**"<

cout<<" **6.计算多项式a的值**"<

cout<<" **7.退出**"<

cout<<" **********************************************"<

cout<<" 执行操作:

";

}

voidinput（）{

intm,n;

//Polynpa,pb;

cout<<"请输入多项式a的项数:

";

cin>>m;

ma=CreatePolyn（ma,m）;

cout<

cout<<"请输入多项式b的项数:

";

cin>>n;

mb=CreatePolyn（mb,n）;}

voidmain（）

{

//intm,n;

floatx,result;

charkey;

//Polynpa,pb;

cout<

"<

cout<<"系统正在初始化数据，请稍后..."<

_sleep（3*1000）;

system（"cls"）;

while（key）

{

desktop（）;

cin>>key;

switch（key）

{

case'1':

input（）;

cout<<"多项式a：

";

PrintPolyn（ma）;

cout<<"多项式b：

";

PrintPolyn（mb）;

break;

case'2':

input（）;

//pc=AddPolyn（pa,pb）;

cout<<"多项式a：

";

PrintPolyn（ma）;

cout<<"多项式b：

";

PrintPolyn（mb）;

cout<<"多项式a+b：

";

PrintPolyn（AddPolyn（ma,mb））;

//DestroyPolyn（pc）;

break;

case'3':

input（）;

//pd=SubtractPolyn（pa,pb）;

cout<<"多项式a：

";

PrintPolyn（ma）;

cout<<"多项式b：

";

PrintPolyn（mb）;

cout<<"多项式a-b：

";

PrintPolyn（SubtractPolyn（ma,mb））;

//DestroyPolyn（pd）;

break;

case'4':

input（）;

//pd=SubtractPolyn（pa,pb）;

cout<<"多项式a：

";

PrintPolyn（ma）;

cout<<"多项式b：

";

PrintPolyn（mb）;

cout<<"多项式a*b：

";

PrintPolyn（MultiplyPolyn（ma,mb））;

//DestroyPolyn（pd）;

break;

case'5':

input（）;

//pd=SubtractPolyn（pa,pb）;

cout<<"多项式a：

";

PrintPolyn（ma）;

cout<<"多项式b：

";

PrintPolyn（mb）;

cout<<"多项式a/b：

";

DevicePolyn（ma,mb）;

//DestroyPolyn（pd）;

break;

case'6':

input（）;

cout<<"多项式a：

";

PrintPolyn（ma）;

cout<<"输入x的值：

x=";

cin>>x;

result=ValuePolyn（ma,x）;

cout<<"多项式a的值:

"<

break;

case'7':

DestroyPolyn（ma）;

DestroyPolyn（mb）;

exit（0）;

break;

default:

cout<<"Error!

!

!

"<

}

cout<

system（"pause"）;

}

}

六、程序测试

6.1测试软件：

MicrosoftVisualC++6.0

6.2测试的数据：

（1）A+BA=3x14-8x8+6x2+2B=2x10+4x8+-6x2

（2）A-BA=11x14+3x10+2x8+10x6+5B=2x14+3x8+5x6+7

（3）A*BA=5x6+4x5+3x4B=6x6+5x5

（4）A=5x6+4x5+3x4X=2

（5）A/BA=2x2B=x2+1

6.3测试过程与结果：

（1）

A=3x14-8x8+6x2+2

B=2x10+4x8-6x2

A+B=3x14+2x10-4x8+2

图6-1加法测试

（2）A=11x14+3x10+2x8+10x6+5

B=2x14+3x8+5x6+7

A-B=9x14+3x10-x8+5x6-2

图6-2减法测试图

（3）

A=5x6+4x5+3x4

B=6x6+5x5

A*B=30x12+49x11+38x10+15x9