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

1、学号13082101152014-2015学年 第二学期软件工程课程设计报告一兀稀疏多项式计算器计算机科学与技术计算机科学与技术（2 ）班指导教师：成绩 ：一、问题描述 4二、需求分析 4三、概要设计5四、详细设计7五、源代码10六、 程序测试 32七、使用说明 4.1八、课设总结 4.3一、问题描述1.1 基本要求(1) 输入并建立多项式；(2) 输出多项式，输出形式为整数序列： n,c1,e1, c2,e2, ,en, 其中n是多项式的项数，ci,ei,分别是第i项的系数和指数，序列按指数降序排序；(3) 多项式a和b相加，建立多项式a+b ;( 4)多项式 a 和 b 相减，建立多项式

2、a-b ；(5) 计算多项式在 x 处的值。(6) 计算器的仿真界面。1.2 设计目的数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个 强有力手段。课程设计要求学生在完成程序设计的同时能够写出比较规的 设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培 养和软件工作者工作作风的训练，将起到显著的促进作用二、需求分析2.1 设计开发环境 ：软件方面：系统 windows 7 编程软件： VC+ 6.02.2 思路分析 ： 一般情况下的一元n次多项式可写成pn(x)=p1xe1+p2xe2+pmxem其中，pl是指数为ei的项的非零系数，且满足0至1<e2<

3、<em=n , 若用一个长度为 m 且每个元素有两个数据项(系数项和指数项)的线性表(p1,e1 ) ,(p2,e2), ；(pm,em)便可惟一确定多项式 pn(x)。 用两个带表头结点的单链表分别存储两个多项式 根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零， 则构成“和多项式” 中的一项； 只需要将第二个多项式的系数改为其相反数，然后根据一元多项式 相加的运算规则便可以得到其相应的“差多项式”三、概要设计f祟单_,J1r求值加法减法乘法除法SubtracDeviceValuePIn sert( Poly n p,PolyAddPoly

4、n(ma,mb)tPoly n(ma,mbJMultipl yPolyn (ma,m -lbPol yn(ma,mboly n(ma,x)输出输入desktoP()图3-1功能模块图为实现上述程序功能，用带表头结点的单链表存储多项式。元素类型，节点类型，和指针类型：typedef struct Pol yno mialint coe; / 系数int exp;/ 指数struct Poly no mial *n ext;*Poly n,Poly no mial;各个模块之间的调用如图3-1所示，调用insert ()函数将输入的多项式 按降幕排列，通过主函数 ma in ()中swith语句，

5、选择用户所选择的对应 的模块，然后又模块对应的功能函数对用户输入的数据进行相应的操作， 最后通过desktop ()模块将最后结果输出。四、详细设计q开始运行多项式加法计算器退出输入多项式求和(差)求积、商多项式相加求和关闭运行建立2个多项式多项式求积、商（差）输出求和（差） 结果输出结果按任意键退出图4-1功能实现流程图4.1输入模块用户可通过本模块来输入一个多项式，在每次输入一个多项式时，本 模块会先判断谁否是第一次输入，如果是，创建节点，如果不是则模块会 通过判断本次输入的数的指数与第一项输入的指数的大小，如果第一项的 指数较大，则刚输入的这一项继续与第二项比较指数，以此类推，如果发 现

6、刚输入的这一项的指数比比较的这一项的指数要大，则插入比较项的前 面。4.2 求和、差模块用户通过本模块可以实现两个多项式的求和或差值，此模块先调用输 入模块，进行对两个要运算的多项式进行初始化，并按降幂排列。然后将 两个多项式的幂进行一个对比，如果第一个数的第一项的系数大于第二个 多项式的第一个项的系数，那么直接将第一项赋值于刚开始创建的链表的 第一项，作为答案的最后一项，反之亦然，如果第一个数的第一项，与第 二个数的第一项的系数相同，那么将两个数的系数与指数分别相加或者相 减并将对应值赋值给答案相对应的项。以此类推。最后有输出模块输出最 后答案。4.3 求积、商模块用户可通过该模块实现两个多

7、项式的相乘（相除），此模块先调用输 入模块，进行对两个要运算的多项式的初始化，并按降幂排列。然后将第 一个数的系数、指数与第二个数的系数、指数分别相乘（相除），相加（相 减），并且赋值给答案相应的系数、指数。完成后执行第一个数的第一项 与第二个数的第二项进行相应的操作执行完之后最后调用输出模块将 结果输出到屏幕上。4.4 求值模块用户可通过此模块实现多项式的求值，此模块调用输入模块，完成相 对应的操作，然后需要用户输入此时变量的值，并且将变量的值赋值给变 量，最后将答案通过输出模块输出到屏幕上。五、源代码#include<iostream.h>#include <stdlib

8、.h>#include <math.h>typedef struct Polynomialint coe; / 系数int exp;/ 指数struct Polynomial *next;*Polyn,Polynomial;Polyn ma,mb;void Insert(Polyn p,Polyn h)if(p->coe=0) delete p;elsePolyn q1,q2;q1=h;q2=h->next;while(q2&&p->exp<q2->exp) q1=q2;q2=q2->next; if(q2&&

9、;p->exp=q2->exp)q2->coe+=p->coe;delete p;if(!q2->coe)q1->next=q2->next;delete q2;elsep->next=q2;q1->next=p;Polyn CreatePolyn(Polyn head,int m) int i;Polyn p;p=head=new Polynomial;head->next=NULL;for(i=0;i<m;i+)p=new Polynomial;项的系数 :"cout<<" 请输入第 &quo

10、t;<<i+1<<" cin>>p->coe;cout<<"指数 :cin>>p->exp;Insert(p,head);return head;void DestroyPolyn(Polyn p)Polyn t;while(p!=NULL)t=p;p=p->next;delete t;void PrintPolyn(Polyn Pm)Polyn qa=Pm->next;int flag=1;if(!qa)cout<<"0"cout<<endl;r

11、eturn;while (qa)if(qa->coe>0&&flag!=1) cout<<"+"if(qa->coe!=1&&qa->coe!=-1)cout<<qa->coe;if(qa->exp=1) cout<<"X"else if(qa->exp) cout<<"XA"<<qa->exp;elseif(qa->coe=1)if(!qa->exp) cout<<&qu

12、ot;1"else if(qa->exp=1) cout<<"X" else cout<<"XA"<<qa->exp;if(qa->coe=-1)if(!qa->exp) cout<<"-1"else if(qa->exp=1) cout<<"-X"else cout<v"-XA"vvqa->exp;qa=qa->next;flag+;cout<<endl;int c

13、ompare(Polyn a,Polyn b)if(a&&b)if(!b|a->exp>b->exp) return 1;else if(!a|a->exp<b->exp) return -1;else return 0;else if(!a&&b) return -1;else return 1;Polyn AddPolyn(Polyn pa,Polyn pb)Polyn qa=pa->next;Polyn qb=pb->next;Polyn headc,hc,qc;hc=new Polynomial;hc-&g

14、t;next=NULL;headc=hc;while(qa|qb)qc=new Polynomial;switch(compare(qa,qb)case 1:qc->coe=qa->coe; qc->exp=qa->exp; qa=qa->next; break;case 0: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;q

15、b=qb->next; break;if(qc->coe!=0)qc->next=hc->next; hc->next=qc;hc=qc;else delete qc;return headc;Polyn SubtractPolyn(Polyn pa,Polyn pb) Polyn h=pb;Polyn p=pb->next;Polyn pd;while(p)p->coe*=-1;p=p->next;pd=AddPolyn(pa,h);for(p=h->next;p;p=p->next)p->coe*=-1;return pd;

16、Polyn MultiplyPolyn(Polyn pa,Polyn pb)Polyn hf,pf;/Polyn qa=pa->next; / 新建一个结点作为 pa 的后继结点Polyn qb=pb->next; / 新建一个结点作为 pb 的后继结点hf=new Polynomial;hf->next=NULL;while(qa)/ 使用 while 循环，使得多项式的每项得以运算qb=pb->next;while(qb)pf=new Polynomial;pf->coe=qa->coe*qb->coe;pf->exp=qa->exp+

17、qb->exp;Insert(pf,hf);/ 调用插入函数， 将新的结点插入到新建链表 中，并合并同类项qb=qb->next;qa=qa->next;return hf;/ 返回所得链表的头指针void DevicePolyn(Polyn pa,Polyn pb)Polyn quotient,remainder,temp1,temp2;Polyn qa=pa->next;Polyn qb=pb->next;quotient=new Polynomial; / 建立头结 点,存储商quotient->next=NULL;/ 建立头结remainder=ne

18、w Polynomial;点，存储余数remainder->next=NULL;temp1=new Polynomial;temp1->next=NULL;temp2=new Polynomial;temp2->next=NULL;temp1=AddPolyn(temp1,pa);while(qa!=NULL&&qa->exp>=qb->exp)temp2->next=new Polynomial;temp2->next->coe=(qa->coe)/(qb->coe);temp2->next->ex

19、p=(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<<endl<<"shang"<<endl;/printf("t商： ");PrintPolyn(qu

20、otient);cout<<"yushu"<<endl;/printf("t余数： ");PrintPolyn(remainder);float ValuePolyn(Polyn head,float x)Polyn p;p=head->next;float result=0;while(p!=NULL)result+=(p->coe)*(float)pow(x,p->exp);p=p->next;return result;void desktop()system("cls");元多项

21、式的计cout<<endl<<endl<<endl<<"算"<<e ndl;cout<<"<<endl;*、'cout<<" *1.输出多项式 a 和 b*"<<endl;cout<<"*2. 建立多项式 a+b*"<<endl;cout<<"*3. 建立多项式 a-b*"<<endl;文案*"<<endl;cout<

22、;<"*"<<endl;cout<<"*"<<endl;cout<<"*"<<endl;cout<<"5. 建立多项式 a/b6.计算多项式 a 的值7.退出<<endl<<endl;*、'cout<<" 执行操作 :"void input()int m,n;/Polyn pa,pb;cout<<" 请输入多项式 a 的项数 :"cin>>m

23、;ma=CreatePolyn(ma,m);cout<<" 请输入多项式 b 的项数 :"cin>>n;mb=CreatePolyn(mb,n);void main()/int m,n;float x,result;char key;/Polyn pa,pb;cout<<endl<<endl<<endl<<endl<<"欢迎您的使用！ "<<endl;cout<<"系统正在初始化数据，请稍后."<<endl;_sle

24、ep(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);cou

25、t<<" 多项式 b ："PrintPolyn(mb);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

26、,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,

27、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;resu

28、lt=ValuePolyn(ma,x);cout<<" 多项式 a 的值 :"<<result<<endl; break;case'7':DestroyPolyn(ma);DestroyPolyn(mb);exit(0);break;default:cout<<"Error!"<<endl;cout<<endl<<endl;system("pause");六、程序测试6.1测试软件：Microsoft Visual C+ 6.06.2测

29、试的数据：B=2x10+4x8+-6x2(1) A+BA= 3x14-8x8+6x2+2(2) A-BA=11x14+3x10+2x8+10x6+5B=2x14+3x8+5x6+7B= 6x6+5x5X=2B=x2+1(3) A*BA= 5x6+4x5+3x4A= 5x6+4x5+3x4(5) A/BA=2x26.3测试过程与结果：(1)A= 3x14-8x8+6x2+2B=2x10+4x8-6x2A+B=3x14+2x10-4x8+2d|x一元多顼式的计算A14-8XA8+&XA2*23 X 14+2 X 0-4X "8 *22枠：+ba b a 舉巩式式 行项项项和*b-

30、b的誥 a A a a a 3 式式式式式多 多多多多多建 岀±-±-4王薪出 建；重退 12 3 4 5 6 7E : '一元宰攻式的计DebugBain* exe*图 6-1 加法测试(2) A=11x14+3x10+2x8+10x6+5B=2x14+3x8+5x6+7A-B=9x14+3x10-x8+5x6-2" 帀 "h 值0 "和*b-bKI诙瞅 耗 a a a a a 5 E式式式式多 项项项项项亞 多多多多多建 -出立立算立新出 -输建建计逹重退7234 567行项项项311XA14*3XA10*21C"8*10

31、X2XA14+3XA8+5XA&+7=9XA14+3XA10-X"8+5XA请按任意犍继续图 6-2 减法测试图(3)A= 5x6+4x5+3x4B= 6x6+5x5A*B =30x12+49x11+38x10+15x9fe : i * 行项顶项 执多多多A6+5X"51 多项式艮和b2 -建立多项式录#b3.建立参项SGa-b 驭甘塞暑项式a的值5 建立务项式严b6 -SW&3L多项式戏和b 沢退出元冬项式KJitXDebugXaain.«zc|!W ME JI M! If 耳 . I请按任意犍继续k T丄1/图6-3乘法测试A= 5x6+4x5

32、+3x4X=2A=496c"E八一元爭顶式fiThffDebugB3in- ese-g|x11E" EiHHEEjnEHE m ne jh " e <h r e mI <JTI 输出多项式和h 器建李多项式kh3 建辽备项式a-h 4.W多顼式a的值9 建立多项式衣山&重新建立多项式厲和bI：賢N图 6-4 求值测试图(5) A=2x2B=x2+1A/B=2余数是-2 ;2立务坝瓦Kb3 建立多贡式皿4-建辛多顶式"h5 建立多项式*b6-W多项式“的值 退出d的亲数是:*»M-M-M-M-的/h12 10项数数数数 tb的

33、的 勢项11AlAIJA" 嶽输输 主尸主冃 主异 :/h是 VUV荷 项项项2 2I1A1A 主冃主戶 5 作操i前项数数的e.图 6-5 除法测试图七、使用说明程序开始运行后，出现如图界面：撕T帜Tih 值 -囿序功站旳科A 庐4祖卢 13项顶J501HT卫壬立卫菖77 轲込址建遂1T貝 *! 12 3 4-567叩 rC-DgcuMCTits wd S*ttinf?t&dBinirtr»torkM j j(Debijgb j jg «e*图7-1界面初始图1、如果要进行加法运算，请输入 2,出现请输入a的项数：请输入第一项的系数：就是输入第一个多项式的每一项的系数和指数注意：输入是随便输入的。如第一个多项式为5xA