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

-.z..--可修编-**2014-2015学年2014-2015学年第二学期"软件工程"课程设计报告题目：一元稀疏多项式计算器专业：计算机科学与技术班级：计算机科学与技术〔2〕班：指导教师：成绩：一、问题描述3二、需求分析3三、概要设计3四、详细设计3五、源代码3六、程序测试3七、使用说明3八、课设总结3一、问题描述1.1根本要求〔1〕输入并建立多项式；〔2〕输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,,,,,,,,en,其中n是多项式的项数，ci,ei,分别是第i项的系数和指数，序列按指数降序排序；〔3〕多项式a和b相加，建立多项式a+b；〔4〕多项式a和b相减，建立多项式a-b；〔5〕计算多项式在*处的值。〔6〕计算器的仿真界面。1.2设计目的数据构造是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。课程设计要求学生在完成程序设计的同时能够写出比拟规的设计报告。严格实施课程设计这一环节，对于学生根本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用二、需求分析2.1设计开发环境：软件方面：系统windows7编程软件：VC++6.02.2思路分析：①一般情况下的一元n次多项式可写成pn(*)=p1*e1+p2*e2+……+pm*em

其中，p1是指数为ei的项的非零系数，且满足0≦e1<e2<……<em=n,假设用一个长度为m且每个元素有两个数据项〔系数项和指数项〕的线性表〔〔p1,e1〕,(p2,e2),……,(pm,em)〕便可惟一确定多项式pn(*)。②用两个带表头结点的单链表分别存储两个多项式③根据一元多项式相加的运算规则：对于两个一元多项式中所有指数一样的项，对应系数相加，假设其和不为零，则构成“和多项式〞中的一项；④只需要将第二个多项式的系数改为其相反数，然后根据一元多项式相加的运算规则便可以得到其相应的“差多项式〞三、概要设计菜单菜单加法AddPolyn(ma,mb)减法SubtractPolyn(ma,mb)乘法MultiplyPolyn(ma,mb)求值ValuePolyn(ma,*)输入Insert(Polynp,Polynh)除法DevicePolyn(ma,mb)输出desktop()图3-1功能模块图为实现上述程序功能，用带表头结点的单链表存储多项式。元素类型，节点类型，和指针类型：typedefstructPolynomial{intcoe;//系数inte*p;//指数structPolynomial*ne*t;}*Polyn,Polynomial;各个模块之间的调用如图3-1所示，调用insert〔〕函数将输入的多项式按降幂排列，通过主函数main〔〕中swith语句，选择用户所选择的对应的模块，然后又模块对应的功能函数对用户输入的数据进展相应的操作，最后通过desktop〔〕模块将最后结果输出。四、详细设计开场运行开场运行多项式加法计算器多项式加法计算器退出退出求积、商求和求积、商求和〔差〕输入多项式关闭运行多项式相加求和〔差〕多项式求关闭运行多项式相加求和〔差〕多项式求积、商建立2个多项式输出结果输出求和〔差〕输出结果输出求和〔差〕结果按任意键退出图4-1功能实现流程图4.1输入模块用户可通过本模块来输入一个多项式，在每次输入一个多项式时，本模块会先判断谁否是第一次输入，如果是，创立节点，如果不是则模块会通过判断本次输入的数的指数与第一项输入的指数的大小，如果第一项的指数较大，则刚输入的这一项继续与第二项比拟指数，以此类推，如果发现刚输入的这一项的指数比比拟的这一项的指数要大，则插入比拟项的前面。4.2求和、差模块用户通过本模块可以实现两个多项式的求和或差值，此模块先调用输入模块，进展对两个要运算的多项式进展初始化，并按降幂排列。然后将两个多项式的幂进展一个比照，如果第一个数的第一项的系数大于第二个多项式的第一个项的系数，则直接将第一项赋值于刚开场创立的链表的第一项，作为答案的最后一项，反之亦然，如果第一个数的第一项，与第二个数的第一项的系数一样，则将两个数的系数与指数分别相加或者相减并将对应值赋值给答案相对应的项。以此类推。最后有输出模块输出最后答案。4.3求积、商模块用户可通过该模块实现两个多项式的相乘〔相除〕，此模块先调用输入模块，进展对两个要运算的多项式的初始化，并按降幂排列。然后将第一个数的系数、指数与第二个数的系数、指数分别相乘〔相除〕，相加〔相减〕，并且赋值给答案相应的系数、指数。完成后执行第一个数的第一项与第二个数的第二项进展相应的操作…….执行完之后最后调用输出模块将结果输出到屏幕上。4.4求值模块用户可通过此模块实现多项式的求值，此模块调用输入模块，完成相对应的操作，然后需要用户输入此时变量的值，并且将变量的值赋值给变量，最后将答案通过输出模块输出到屏幕上。五、源代码-.z..--可修编-*include<iostream.h>*include<stdlib.h>*include<math.h>typedefstructPolynomial{ intcoe;//系数 inte*p;//指数 structPolynomial*ne*t;}*Polyn,Polynomial;Polynma,mb;voidInsert(Polynp,Polynh){ if(p->coe==0)deletep; else{ Polynq1,q2; q1=h;q2=h->ne*t; while(q2&&p->e*p<q2->e*p) { q1=q2; q2=q2->ne*t; } if(q2&&p->e*p==q2->e*p) { q2->coe+=p->coe; deletep; if(!q2->coe) { q1->ne*t=q2->ne*t; deleteq2;} } else { p->ne*t=q2; q1->ne*t=p; } }}PolynCreatePolyn(Polynhead,intm){ inti; Polynp; p=head=newPolynomial; head->ne*t=NULL; for(i=0;i<m;i++){ p=newPolynomial;; cout<<"请输入第"<<i+1<<"项的系数:"; cin>>p->coe; cout<<"指数:"; cin>>p->e*p; Insert(p,head); } returnhead;}voidDestroyPolyn(Polynp){ Polynt; while(p!=NULL) { t=p; p=p->ne*t; deletet; }}voidPrintPolyn(PolynPm){ Polynqa=Pm->ne*t; intflag=1; if(!qa) { cout<<"0"; cout<<endl; return; } while(qa) {if(qa->coe>0&&flag!=1)cout<<"+"; if(qa->coe!=1&&qa->coe!=-1) { cout<<qa->coe; if(qa->e*p==1)cout<<"*"; elseif(qa->e*p)cout<<"*^"<<qa->e*p; } else { if(qa->coe==1) { if(!qa->e*p)cout<<"1"; elseif(qa->e*p==1)cout<<"*"; elsecout<<"*^"<<qa->e*p; } if(qa->coe==-1) { if(!qa->e*p)cout<<"-1"; elseif(qa->e*p==1)cout<<"-*"; elsecout<<"-*^"<<qa->e*p; } } qa=qa->ne*t; flag++; } cout<<endl;}intpare(Polyna,Polynb){ if(a&&b) { if(!b||a->e*p>b->e*p)return1; elseif(!a||a->e*p<b->e*p)return-1; elsereturn0; } elseif(!a&&b)return-1; elsereturn1;}PolynAddPolyn(Polynpa,Polynpb){ Polynqa=pa->ne*t; Polynqb=pb->ne*t; Polynheadc,hc,qc; hc=newPolynomial; hc->ne*t=NULL; headc=hc; while(qa||qb) { qc=newPolynomial; switch(pare(qa,qb)) { case1: { qc->coe=qa->coe; qc->e*p=qa->e*p; qa=qa->ne*t; break; } case0: { qc->coe=qa->coe+qb->coe; qc->e*p=qa->e*p; qa=qa->ne*t; qb=qb->ne*t; break; } case-1: { qc->coe=qb->coe; qc->e*p=qb->e*p; qb=qb->ne*t; break; } } if(qc->coe!=0) { qc->ne*t=hc->ne*t; hc->ne*t=qc; hc=qc; } elsedeleteqc; } returnheadc;}PolynSubtractPolyn(Polynpa,Polynpb){ Polynh=pb; Polynp=pb->ne*t; Polynpd; while(p) { p->coe*=-1; p=p->ne*t; } pd=AddPolyn(pa,h); for(p=h->ne*t;p;p=p->ne*t) p->coe*=-1; returnpd;}PolynMultiplyPolyn(Polynpa,Polynpb){ Polynhf,pf;// Polynqa=pa->ne*t;//新建一个结点作为pa的后继结点 Polynqb=pb->ne*t;//新建一个结点作为pb的后继结点 hf=newPolynomial; hf->ne*t=NULL; while(qa)//使用while循环，使得多项式的每项得以运算 { qb=pb->ne*t; while(qb) { pf=newPolynomial; pf->coe=qa->coe*qb->coe; pf->e*p=qa->e*p+qb->e*p; Insert(pf,hf);//调用插入函数，将新的结点插入到新建链表中，并合并同类项 qb=qb->ne*t; } qa=qa->ne*t; } returnhf;//返回所得链表的头指针}voidDevicePolyn(Polynpa,Polynpb){ Polynquotient,remainder,temp1,temp2; Polynqa=pa->ne*t; Polynqb=pb->ne*t; quotient=newPolynomial;//建立头结点,存储商 quotient->ne*t=NULL; remainder=newPolynomial;//建立头结点，存储余数 remainder->ne*t=NULL; temp1=newPolynomial; temp1->ne*t=NULL; temp2=newPolynomial; temp2->ne*t=NULL; temp1=AddPolyn(temp1,pa); while(qa!=NULL&&qa->e*p>=qb->e*p) { temp2->ne*t=newPolynomial; temp2->ne*t->coe=(qa->coe)/(qb->coe); temp2->ne*t->e*p=(qa->e*p)-(qb->e*p); Insert(temp2->ne*t,quotient); pa=SubtractPolyn(pa,MultiplyPolyn(pb,temp2)); qa=pa->ne*t; temp2->ne*t=NULL; } remainder=SubtractPolyn(temp1,MultiplyPolyn(quotient,pb)); pb=temp1; cout<<endl<<"shang"<<endl;//printf("\t商："); PrintPolyn(quotient); cout<<"yushu"<<endl;//printf("\t余数："); PrintPolyn(remainder);}floatValuePolyn(Polynhead,float*){ Polynp; p=head->ne*t; floatresult=0; while(p!=NULL) { result+=(p->coe)*(float)pow(*,p->e*p);p=p->ne*t; } returnresult;}voiddesktop(){ system("cls"); cout<<endl<<endl<<endl<<" 一元多项式的计算"<<endl; cout<<" **********************************************"<<endl; cout<<" **1.输出多项式a和b**"<<endl; cout<<" **2.建立多项式a+b**"<<endl; cout<<" **3.建立多项式a-b**"<<endl; cout<<" **4.建立多项式a*b**"<<endl; cout<<" **5.建立多项式a/b**"<<endl; cout<<" **6.计算多项式a的值**"<<endl; cout<<" **7.退出**"<<endl; cout<<" **********************************************"<<endl<<endl; cout<<" 执行操作:";}voidinput(){ intm,n; //Polynpa,pb; cout<<"请输入多项式a的项数:"; cin>>m; ma=CreatePolyn(ma,m); cout<<endl; cout<<"请输入多项式b的项数:"; cin>>n; mb=CreatePolyn(mb,n);}voidmain(){ //intm,n; float*,result; charkey; //Polynpa,pb; cout<<endl<<endl<<endl<<endl<<"欢送您的使用！"<<endl; cout<<"系统正在初始化数据，请稍后..."<<endl; _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<<"输入*的值：*="; cin>>*; result=ValuePolyn(ma,*); cout<<"多项式a的值:"<<result<<endl; break; case'7': DestroyPolyn(ma); DestroyPolyn(mb); e*it(0); break; default: cout<<"Error!!!"<<endl; } cout<<endl<<endl; system("pause"); }}六、程序测试6.1测试软件：MicrosoftVisualC++6.06.2测试的数据：(1)A+BA=3*14-8*8+6*2+2B=2*10+4*8+-6*2(2)A-BA=11*14+3*10+2*8+10*6+5B=2*14+3*8+5*6+7(3)A*BA=5*6+4*5+3*4B=6*6+5*5(4)A=5*6+4*5+3*4*=2(5)A/BA=2*2B=*2+16.3测试过程与结果：(1)A=3*14-8*8+6*2+2B=2*10+4*8-6*2A+B=3*14+2*10-4*8+2图6-1加法测试(2)A=11*14+3*10+2*8+10*6+5B=2*14+3*8+5*6+7A-B=9*14+3*10-*8+5*6-2图6-2减法测试图(3)A=5*6+4*5+3*4B=6*6+5*5A*B=30*12+49*11+38*10+15*9图6-3乘法测试(4)A=5*6+4*5+3*4*=2A=496图6-4求值测试图〔5〕A=2*2B=*2+1A/B=2余数是-2；图6-5除法测试图七、使用说明程序开场运行后，出现如图界面：图7-1界面初始图1、如果要进展加法运算，请输入2，出现请输入a的项数：请输入第一项的系数：就是输入第一个多项式的每一项的系数和指数。注意：输入是随便输入的。如第一个多项式为5*^5;过程如下：请输入a的项数：1请输入a的系数：5请