数据结构一元多项式的运算.doc

目 录一、问题分析11、问题描述11、2 问题得数学模型1、 构造数据结构1二、系统分析22、1可行性研究22、2 系统结构与主要功能模块三、系统设计43、1系统设计目得与要求3、系统设计内容43、功能算法描述与数据结构说明4四、系统实现7五、调试及运行结果11六、收获与体会12附录1 问题分析1、1 问题描述设计一个元多项式程序，并完成多项式得乘法运算。从实际得角度出发,这里设计得程序就是基于一元n次多项式得数学模型。、2问题得数学模型在数学上,一个一元多项式Pn(x）可按升幂写成:P（）= 0+a x+2 +an x1 、它由n+1个系数惟一确定，因此,在计算机里，它可用一个线性表P来表示:Pn(a0,a1，a2，,an)每一项得指数i隐含在其系数ai得序号里。多项式得乘法规则：多次运用单项式与多项式相乘得法则得到得.计算时()(m+n),先把（m+n)瞧成一个单项式，（ab）就是一个多项式,运用单项式与多项式相乘得法则，得到（a)(m+)(m+n）b（mn）,然后再次运用单项式与多项式相乘得法则。1、3 构造数据结构通过分析多项式得特征，不难瞧出多项式就是由单项式构成得,而每个单项式都具有系数与指数,当系数为0时，该项就失去了意义，在计算机内要表示一个多项式,至少以下数据信息：系数信息、指数信息与指向下一个单项式得指针。通过指针,我们就可以把多个单项式连接起来,形式一个多项式，需要说明得就是从广义得角度讲，单项式也就是一个多项式。基于以上得分析,我们定义多项式得数据结构为如下结构体形式：typede struct Poynm float of;/系数 iexp;/指数 strct Polynoml net；/指向下一个结点Plyn,Poynomil; /Plyn为结点指针类型2 系统分析、1 可行性研究该程序主要从技术得角度来分析可行性.技术上得可行性研究主要分析技术条件能否顺利完成开发工作,硬、软件能否满足开发者得需要等。该系统采用了Wow X操作系统结合VisalC+ 、0，TC 、0等软件开发平台已成熟可行。硬件方面，科技飞速发展得今天，硬件更新得速度越来越快,容量越来越大，可靠性越来越高，其硬件平台也比较能满足此系统得需要。此外,还有经济可行性，用户使用可行性,法律可行性等可行性研究，这里从简省去。2、2 系统结构与主要功能模块从实现多项式式运算过程得角度来分析，至少需要这样一些子功能模块。如:、多项式创建功能;2、 多项式运算功能;3、操作界面显示功能；4、 销毁多项式得功能;5、 多项式复制功能等。系统得整体流程与主要功能模块如图2-所示开始输入选择显示加法显示功能表输入pa系数、指数退出输入pb系数、指数减法乘法i=mi=mimint=UL;fo（i=0；m;+） (olyn）mlc（zo（srt Polyomial)）；/建立新结点以接收数据 prinf(请输入第%d项得系数与指数：,i+)； sanf(”%f d”，po,xpn)； Inert（p,ea）； /调用Inser函数插入结点 retrhead;/reatPoln2、 void Inser（Poyp,Plyn) 该函数具有两个参数,用来实现链表得顺序排列与合并相同得项。以下就是实现插入得关键代码:void Insert（Plyn p，Poy h) f(pcef=0) fre（); /系数为0得话释放结点 l/如果系数不为0 Plyq1，2；q1=;q2=hnex； while(&pexpnexn） /将指数相同相合并 -c+=p-cef; fre(p）； i（！qcoe） /系数为得话释放结点 1nxq2next;fre(2）； ese /指数为新时将结点插入-nxt=2; q1next=p； /ert、 Poln AddPolyn(Polyn p,Polynpb）该函数有两个参数,其类型均为poly,分别表示要相加得两个不同得多项式.其计算得结果存放在新建得c所指向得链表中。函数中调用了itpe(Pla,Polb）得结果.下面就是实现加法得关键代码:olyn ddPlyn（Polyn a，Polyn p)/求解并建立多项式a+b，返回其头指针 Plyn a=anext； Plynq=pb-next; lyn hed，hc,qc;hc(Pyn)malc（sieo（sruct Plnomal）;/建立头结点 cne=NULL；headc=hc; whil(qa|b) qc=(ly)lloc（iof(strut olynomial）)； swch（pre（qa，qb) case1： qccoe=qaef； qcexn=aex； qa=qnext； beak； ca 0： qccof=a-cof+qbef； c-ex=qexpn; a=anet； q=q-ext; brak； cse 1： cof=b-coef； qcexpn=qe; qb=bext； rk; /swith (coe!=0) qcnextcne; hcnextqc； hc=qc; elsefre（qc）；/当相加系数为0时,释放该结点 /whle return adc；/AdPol nt pare(olyn a,Poln b） if（b） i(！b|apn） rtu 1； eseif（！a|axnxt； oyn qbpbne；f=（olyn）llc(sizf（suct Polnomil)；/建立头结点 hf-next=NU； r(；a;qaqa-net） fr（bpbext;qb=qb-t) pf=（Po）malloc（szef(stct olnomial)； pcoef=qacofqb-cef; pex=qaexpn+bepn； Isert(pf，)；/调用Inser函数以合并指数相同得项 retrh;/MultiplyPoly5、其它函数得介绍请参见附录中详细代码、5 调试及运行结果该程序在C6、0中调试通过,没有错误与警告,运行结果经过检验为正确.以下图1即为该程序运行结果效果图。图中采用得就是计算多项式x+22+x与x0+72得加减乘三种运算进行演示：输入两个多项式得每一项值提示功能选择进行三则运算得结果图516 收获与体会通过这次课程设计练习,使我更深刻地理解了C语言得精髓-指针得使用.完成整个程序设计有，对指针掌握得更加熟练.同时通过直接对链表得操作，加深了对数据结构得理解与认识。并在完成课程设计得过程作主动查阅了相关资料，学到了不少课本上没有得技术知识。经过这次课程设计,我深刻认识到算法在程序设计中得重要性,一个完整得程序总就是由若干个函数构成得，这些相应得函数体现了算法得基本思想.编程就是一件枯燥乏味工作,但就是只要认真专研，我们会从中学到很多在课本上学不到或者无法在课堂上掌握得知识,同时也能从中感受到编程得乐趣.兴趣就是可以培养得,只要坚持下去，面对困难我们总能够找到解决问题得方法。计算多项式得加、减、乘法运算-该程序虽然不就是很大，这次还就是由几位同学合作才完成这一任务.在这个小组中我就是组长,通过分工与合作,使我充分认识到在项目团队开发过程中合作得重要性,也更加理解了沟通协作能力在软件开发行业中得重要性。另外也需要提出得就是在这次程序设计得过程中,非常感谢老师对我们得耐心指导。老师在教学过程中表现出来得对学术专研一丝不苟得精神让我非常有收获。同样也就是老师得严格要求才使得小组成员能够顺利得完成任务。附录icluesdio、#ncludemallc、/*/typedef trt Poynmilfloat coef；/系数 it exn；/指数 stuct Polynoianet；/指向下一个结点Ply,Polynomia; /Polyn为结点指针类型*voidner（ol ，Poln h） if（p-coe=) fe（p); 系数为0得话释放结点else/如果系数不为0 Polyn q1,q2； q1=h;q2=hnxt； whle（q2&p-xpnn) /查找插入位置 q12; q2=ext; f(q&exp=qexpn） /将指数相同相合并 qof+=pcof； free()； if(！q2co） /系数为得话释放结点 1nex=q2ne; fre(2）； lse 指数为新时将结点插入 pxt=q2; q1next=p; Insert/*以下函数实现建立一个多项式*/Polyn CretePoly(Pln ed，intm）/建立一个头指针为head、项数为m得一元多项式/在主程序初始时，先输入得多项式中得项数、n 在这里为。主程序中得pa、pb在此为head int i；用来计数 Poyn p；/定义一个p链表 p=had=(Polyn）malloc（izef(truct Plynomial）; head-nx=NL； for(=;m;i+) p（Polyn)maloc（sieof(suctPolomia)）;/建立新结点以接收数据 prit（请输入第%d项得系数与指数：”,）; anf(%fd”,oef,&pexpn）; nsert（p，had)； /调用nsert函数插入结点 ret ead；/CreatPoyn*以下函数实现多项式得销毁*id DestoPolyn（Poln p）/销毁多项式p Pon 1，2; q1pnxt; q2=q1e； hile(net) free(1); =q;/指针后移 2=q2next； /*以下函数实现显示输出多项式* */vod Prnoln(Poln ） Pl =-nex; nt fa=1；/项数计数器 if（！q） /若多项式为空，输出 ptha（0）; t（”n）; etun； w (） if（qe0&flag!1) putchar(）;/系数大于0且不就是第一项 i（-coe!1&-coef!)/系数非1或1得普通情况 prntf(”%g”，qoef)； if（q-expn） utcha（X)； ese if（q-ex)printf（d,qxn）; lei（-cef=） if（！q-expn）putcar(1）; se f(qexn=1)putcha（X）； ese printf（X%d”，-expn）; if(cof=1） i（！qepn） prt(”1)； else i（qexpn=1） rintf(”X）; els prntf（-Xd”，qexn)； q=q-next; fla+； /whle prit(n”)；/PitPolyn/*在下面得辅助乘法与加法运算*/intp（Pna，Poln b） if（a&b) i(！b|aexpnbexp） retun 1； eseif(!a|aexpnbexp）retur -； els retn0； else if（！a&b) retun1;/多项式已空,但多项式非空 lse urn1;/多项式已空,但多项式非空/pare/*以下函数实现加法*/PolddPolyn（Polyn pa,Ply pb)/求解并建立多项式a+，返回其头指针 oyn =panext; olnq=pb-next； Polyn headc,hc,q；hc=（olyn）mallc(sizeof(uPolynol）；/建立头结点 h-nex=ULL； eadchc; wil(b) q（y）maloc（szeof(structPolynoml）； swc(pa(a，） s 1： qc-co=qacoef; qcexpn=qexp; q=nex; beak; ae 0: qccoeqaoe+qcoef; q-epn=qaepn; q=qanext； q=qbnext; brak； ase 1: qcoef=qbcoef； qcepn=qbexpn； qb=qbnxt; reak； /witch if(qc-oe！=0） qxt=net; hnext=q; hcqc； ele ee(qc）；/当相加系数为0时，释放该结点 /whieretrn headc；AddPon*以下函数实现减法*olyn btractPoyn(Polyn pa,Polyn pb)/求解并建立多项式+b，返回其头指针 Polynh=pb;Pyn pbnex; olynd; hi（p） /将pb得系数取反 poef1； =p-nt; pd=Adoyn（pa,h）;fo(p=hnext;p;p=p-et) /恢复pb得系数 p-coef*1； retu pd；/SubtractPlyn/*以下函数实现乘法*/Poly utiplyPol（ln pa，olyn pb)/求解并建立多项式*b，返回其头指针(该函数实现乘法) Polynf,pf；Poyn qa=pane; olnqb=pnext； h（Poly)alloc（sizeof(strut lynoi);/建立头结点hfnex=NU； fr（;qa；qaqaext） or（qb=bnet；q；bqbnet) p=(Polyn)mllc（zeof（struct Polynomial)； pc=qcof*qb-coef； pf-pn=q-xp+qpn； Inser（p，hf）;调用srt函数以合并指数相同得项 retur f;/ltiplyPoyn/*主函数实现显示与功能选择*/int mai（）intm,，flag=0;/m、n为分别为、b两个多项式得项数Pln a0,b=0，pc，pd，pf；/定义各式得头指针,pa与b在使用前付初值NLL /p头指针所在得多项式用在加法中作为结果,pd用在加法中,pf乘法中 ntf（”*欢迎使用一元多项式运算程序*n)； prin(请输入第一个多项式得项数:）；sca（d,);p=Creat（p,）；/建立第一个多项式a printf（请输入第二个多项式b得项数：）；scaf(%d,n）； b=CreatePyn（pb,n）；/建立第二个多项式 /输出菜单 pritf(”*n); rnt（”情选择您要进行得操作：nt1、输出多项式与nt2、建立多项式a+bnt、建立多项式abn)；ptf（t4、计算多项式*b得值nt、退出n); for（;；fg=0) prnf（”n”）; scn（”d，lg）； if(lag=1） pintf（多项式a：）;Pinolyn(pa); itf（”多项式b:)；PritPlyn(b)；conine； f（fl=) pc=ddPoly(p，b）； printf(多项式a+:）；PrntPly(pc）; DtoyPoln(pc);continue; i(a=3) pdbtrclyn(pa，pb)； prif(”多项式-b：”）；Prily（p）； estroyPolyn(pd);coninue; if（fa=4） pf=MltiplyPoln（a，pb); prnf（”多项式ab：”)；PrnPoly(pf）； Destroyon（)；continue； if（fla=5) break; f（lag|fla5) prit（Error！!”);ontinue; /fo Destroln（）； Desroyoly（pb）；eun0;