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

学号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 相减，建立多项式 a-b ；(5) 计算多项式在 x 处的值。(6) 计算器的仿真界面。1.2 设计目的数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个 强有力手段。课程设计要求学生在完成程序设计的同时能够写出比较规的 设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培 养和软件工作者工作作风的训练，将起到显著的促进作用二、需求分析2.1 设计开发环境 ：软件方面：系统 windows 7 编程软件： VC+ 6.02.2 思路分析 ： 一般情况下的一元n次多项式可写成pn(x)=p1xe1+p2xe2+pmxem其中，pl是指数为ei的项的非零系数，且满足0至1e2 em=n , 若用一个长度为 m 且每个元素有两个数据项(系数项和指数项)的线性表(p1,e1 ) ,(p2,e2), ；(pm,em)便可惟一确定多项式 pn(x)。 用两个带表头结点的单链表分别存储两个多项式 根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零， 则构成“和多项式” 中的一项； 只需要将第二个多项式的系数改为其相反数，然后根据一元多项式 相加的运算规则便可以得到其相应的“差多项式”三、概要设计f祟单_,J1r求值加法减法乘法除法SubtracDeviceValuePIn sert( Poly n p,PolyAddPolyn(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语句，选择用户所选择的对应 的模块，然后又模块对应的功能函数对用户输入的数据进行相应的操作， 最后通过desktop ()模块将最后结果输出。四、详细设计q开始运行多项式加法计算器退出输入多项式求和(差)求积、商多项式相加求和关闭运行建立2个多项式多项式求积、商（差）输出求和（差） 结果输出结果按任意键退出图4-1功能实现流程图4.1输入模块用户可通过本模块来输入一个多项式，在每次输入一个多项式时，本 模块会先判断谁否是第一次输入，如果是，创建节点，如果不是则模块会 通过判断本次输入的数的指数与第一项输入的指数的大小，如果第一项的 指数较大，则刚输入的这一项继续与第二项比较指数，以此类推，如果发 现刚输入的这一项的指数比比较的这一项的指数要大，则插入比较项的前 面。4.2 求和、差模块用户通过本模块可以实现两个多项式的求和或差值，此模块先调用输 入模块，进行对两个要运算的多项式进行初始化，并按降幂排列。然后将 两个多项式的幂进行一个对比，如果第一个数的第一项的系数大于第二个 多项式的第一个项的系数，那么直接将第一项赋值于刚开始创建的链表的 第一项，作为答案的最后一项，反之亦然，如果第一个数的第一项，与第 二个数的第一项的系数相同，那么将两个数的系数与指数分别相加或者相 减并将对应值赋值给答案相对应的项。以此类推。最后有输出模块输出最 后答案。4.3 求积、商模块用户可通过该模块实现两个多项式的相乘（相除），此模块先调用输 入模块，进行对两个要运算的多项式的初始化，并按降幂排列。然后将第 一个数的系数、指数与第二个数的系数、指数分别相乘（相除），相加（相 减），并且赋值给答案相应的系数、指数。完成后执行第一个数的第一项 与第二个数的第二项进行相应的操作执行完之后最后调用输出模块将 结果输出到屏幕上。4.4 求值模块用户可通过此模块实现多项式的求值，此模块调用输入模块，完成相 对应的操作，然后需要用户输入此时变量的值，并且将变量的值赋值给变 量，最后将答案通过输出模块输出到屏幕上。五、源代码#include#include #include 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-expexp) q1=q2;q2=q2-next; if(q2&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;im;i+)p=new Polynomial;项的系数 :;cout 请输入第 i+1p-coe;coutp-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)cout0;coutcoe0&flag!=1) coutcoe!=1&qa-coe!=-1)coutcoe;if(qa-exp=1) coutexp) coutXAexp;elseif(qa-coe=1)if(!qa-exp) coutexp=1) coutX; else coutXAexp;if(qa-coe=-1)if(!qa-exp) coutexp=1) cout-X;else coutexp;qa=qa-next;flag+;coutexpb-exp) return 1;else if(!a|a-expexp) 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-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;qb=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;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+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=new 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-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; coutendlshangendl;/printf(t商： );PrintPolyn(quotient);coutyushunext;float result=0;while(p!=NULL)result+=(p-coe)*(float)pow(x,p-exp);p=p-next;return result;void desktop()system(cls);元多项式的计coutendlendlendl算e ndl;coutendl;*、cout *1.输出多项式 a 和 b*endl;cout*2. 建立多项式 a+b*endl;cout*3. 建立多项式 a-b*endl;文案*endl;cout*endl;cout*endl;cout*endl;cout5. 建立多项式 a/b6.计算多项式 a 的值7.退出endlendl;*、cout 执行操作 :;void input()int m,n;/Polyn pa,pb;coutm;ma=CreatePolyn(ma,m);coutn;mb=CreatePolyn(mb,n);void main()/int m,n;float x,result;char key;/Polyn pa,pb;coutendlendlendlendl欢迎您的使用！ endl;cout系统正在初始化数据，请稍后.key;switch (key)case1:input();cout 多项式 a： ;PrintPolyn(ma);cout 多项式 b ：PrintPolyn(mb);break;case2:input();/pc=AddPolyn(pa,pb);cout 多项式 a： ;PrintPolyn(ma);cout 多项式 b ：PrintPolyn(mb);PrintPolyn(AddPolyn(ma,mb);/DestroyPolyn(pc);break;case3:input();/pd=SubtractPolyn(pa,pb);cout 多项式 a： ;PrintPolyn(ma);cout 多项式 b ：;PrintPolyn(mb);cout 多项式 a-b ： ;PrintPolyn(SubtractPolyn(ma,mb);/DestroyPolyn(pd);break;case4:input();/pd=SubtractPolyn(pa,pb);cout 多项式 a：PrintPolyn(ma);cout 多项式 b ：;PrintPolyn(mb);cout 多项式 a*b ：;PrintPolyn(MultiplyPolyn(ma,mb);/DestroyPolyn(pd);break;case5:input();/pd=SubtractPolyn(pa,pb);cout 多项式 a： ;PrintPolyn(ma);cout 多项式 b ：;PrintPolyn(mb);cout 多项式 a/b ： ;DevicePolyn(ma,mb);/DestroyPolyn(pd);break;case6:input();cout 多项式 a： ;PrintPolyn(ma);coutx;result=ValuePolyn(ma,x);cout 多项式 a 的值 :resultendl; break;case7:DestroyPolyn(ma);DestroyPolyn(mb);exit(0);break;default:coutError!endl;coutendlendl;system(pause);六、程序测试6.1测试软件：Microsoft Visual C+ 6.06.2测试的数据：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-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*21C8*10X2XA14+3XA8+5XA&+7=9XA14+3XA10-X8+5XA请按任意犍继续图 6-2 减法测试图(3)A= 5x6+4x5+3x4B= 6x6+5x5A*B =30x12+49x11+38x10+15x9fe : i * 行项顶项 执多多多A6+5X51 多项式艮和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+3x4X=2A=496cE八一元爭顶式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的的 勢项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&dBinirtrtorkM j j(Debijgb j jg e*图7-1界面初始图1、如果要进行加法运算，请输入 2,出现请输入a的项数：请输入第一项的系数：就是输入第一个多项式的每一项的系数和指数注意：输入是随便输入的。如第一个多项式为5xA5;过程如下：请输入a的项数：1请输入 a 的系数： 5请输入a的指数：5接着输入第 2 个多项式的每一项的系数和指数。 输入完以后就直接显示结果了：2、如果要进行减法运算，请输入 3 ，过程和输入加法一样，输入个多 项式即可。3、如果要退出的话，请输入 7 即可结束程序的运行。八、课设总结学完数据结构线性表一章后做此题，自觉就想到用带头结点的单链表 来存储多项式，只需用结点记录多项式的系数和指数，此数据结构即节省 空间又好进行操作，且进行运算的主要设计思路也易想到，大体设计结构 在较短时间能够完成。但当设计到具体细节代码时遇到了不少困难，主要 困难是进行结点操作时，对指针考虑得不够细致，调试时常出现指针指错 的情况，没有认真理清条件层次。完成此程序后，受益匪浅，它巩固了线 性表一章学到的知识，而且重温了函数传参等重点知识。尽管对程序进行 大量的调试分析修改，可还有些代码写得十分啰嗦，程序也不够健壮，对 多项式的操作只限于 2 个多项式，还有在界面设计上没花太大心思，界面 不美观。这些问题在日后还需进行改善。 本次课程设计采用 C+ 语言实现 . 这次设计基本上能实现指导书上的要求。我们可以通过这个程序实现计算 器的一些基本功能 ,实现相关操作。通过本次课程设计 ,让我进一步了解了 c+ 的一些知识 ,C+ 的字符串处理功能完全依靠字符串数组来实现，很多 在其他高级语言中实现的字符串比较等操作，在这里完全依靠函数来实现， 因此调试中字符串处理函数的调试很多本次课程设计培养了我们对这些实 际问题的分析能力以及解决一些实际问题的能力。通过编程，巩固了我们 对编程思想和写程序的能力。课程设计是对我们的学习很有利的一个环节。 在这个阶段，我们学会把理论与实际的结合、懂得人与人沟通的重要性， 明白合作的可贵。当然，在编写的过程中也出现了很多问题，但通过调试 和看书解决了，大大的提高了我自学的能力，学会了遇到问题，如何利用 资源去解决问题也明白了要完成一项设计，首先要有扎实的基础知识，这 就要求我们在平时的学习中要不断提高自己。其次，要充分利用身边的各 种资源，图书馆有很多相关的书，网上也有不少的知识解答，要好好的利 用。第三，要多向身边的同学多请教，在交流中提高自己的实力。理论联系实践，在实践中提高。通过这次课程设计中，我加深了对课本知识的理 解。九、产考文献1 王挺，周会平，贾丽丽，许锡山 C+程序设计M.:清华大学，20052 严蔚敏，吴伟民.数据结构（C语言版）M.:清华大学，20053 根强 . 数据结构（ C+ 版）习题解答及实训指导 M. :中国水利水电， 2009