一元多项式的加法减法乘法的实现

福建农林大学计算机与信息学院课程设计报告课程名称：数据结构课程设计题目：一元多项式的加法减法乘法的实现姓名：系：软件工程系专业：软件工程专业年级：2014学号：指导教师：黄思先职称：副教授完成起止日期：2016.6.5-2016.7.12016年07月1日福建农林大学计算机与信息学院课程设计结果评定评价内容评价指标评分权值评定成绩业务水平有扎实的基础理论知识和课程知识；能正确设计实验方案；独立进行实验工作；能运用所学课程知识和技能去发现与解决实际问题0.2设计质量实验正确，分析处理科学；设计结果有应用价值；图纸绘制符合国家标准，质量符合要求；计算及测试结果准确；工作中有创新意识；对前人工作有改进或突破，或有独特见解；0.4工作量、工作态度按期完成规定的任务，工作量饱满，难度较大；工作努力，遵守纪律；工作作风严谨务实0.2报告质量文字通顺，技术用语准确，符号统一，编号齐全，书写工整规范，图表完备、整洁、正确；0.2合计1.0指导教师签字：评定日期：目录一、问题分析和任务定义……………………………………………1二、程序设计内容……………………………………………………1三、程序调试与测试…………………………………………………7四、实验心得…………………………………………………………9五、程序编码…………………………………………………………9-1-一、问题分析及任务定义顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。【问题描述和基本要求】设有一元多项式Am(x)和Bn(x).Am(x)=A0+A1x1+A2x2+A3x3+…+AmxmBn(x)=B0+B1x1+B2x2+B3x3+…+Bnxn请实现求M(x)=Am(x)+Bn(x)、M(x)=Am(x)-Bn(x)和M(x)=Am(x)×Bn(x)。要求：1)首先判定多项式是否稀疏2)分别采用顺序和动态存储结构实现；3)结果M(x)中无重复阶项和无零系数项；4)要求输出结果的升幂和降幂两种排列情况二、课程设计的内容2.1函数多项式创建函数PolyNode*Creatpoly()多项式输出函数voidPrin_poly(PolyNode*h)多项式升序排列函数voidInsortup(PolyNode*h)多项式降序排列函数voidInsortdown(PolyNode*h)多项式合并函数voidUnitePoly(PolyNode*h)多项式相乘函数PolyNode*polymuti(PolyNode*h1,PolyNode*h2)多项式相加函数PolyNode*addition(PolyNode*ha,PolyNode*hb)多项式相减函数PolyNode*subduction(PolyNode*ha,PolyNode*hb)2.2设计各个模块的流程图（1）main()开始定义*h1,*h2，*h输出文字创建多项式A-2-开始Np=h—nexts=h—next(2)voidInsortup(PolyNode*h)YYYNN合并同类项a=1a=2a=3additionsubduction排序输出多项式A创建多项式B输出文字合并同类项排序输出多项式Bpolymuti结束YP!=NULLNs—next!=NULL结束Yp=h—next-3-开始Np=h—nexts=s—nexts=h—nextY(3)voidInsortdown(PolyNode*h)(4)PolyNode*polymuti(PolyNode*h1,PolyNode*h2)YP!=NULLNNs—exps—next—exp—s—next!=NULLs—exp与s—next—exp互换s—coef与s—next—coef互换结束Yp=h—next-4-（5）voidUnitePoly(PolyNode*h)-5--6-开始(6)PolyNode*addition(PolyNode*ha,PolyNode*hb)三、程序调试与测试相加结果-7-相减结果-8-相乘结果-9-四、实验心得在本次课程设计中，我明白了理论应与实际相结合，上机练习是提高编程能力最有效的办法，这次实验提高了我编写大型程序的能力以及查阅资料并从中获得有效资料的能力。这次课程设计加深了我对数据结构的进一步理解。五、程序编码实验程序：#includestdio.h#includestdlib.h#includeconio.htypedefstructNode{intcoef;//系数intexp;//指数structNode*next;}PolyNode;PolyNode*Creatpoly()//创建多项式的单链表{PolyNode*h,*p,*q;h=(PolyNode*)malloc(sizeof(PolyNode));-10-p=h;p-next=NULL;printf(请输入多项式的系数及其指数ab，当系数输入0时停止输入\n);q=(PolyNode*)malloc(sizeof(PolyNode));scanf(%d%d,&q-coef,&q-exp);while(q-coef!=0){p-next=q;p=q;q=(PolyNode*)malloc(sizeof(PolyNode));scanf(%d%d,&q-coef,&q-exp);}p-next=NULL;return(h);}voidPrin_poly(PolyNode*h)//将多项式输出函数{PolyNode*p;p=h-next;while(p!=NULL){if(p-coef0&&p!=h-next){if(p-exp0)printf(+%dx^%d,p-coef,p-exp);elseif(p-exp0)printf(+%dx^(%d),p-coef,p-exp);elseprintf(+%d,p-coef);}elseif(p-coef0&&p!=h-next){if(p-exp0)printf(%dx^%d,p-coef,p-exp);elseif(p-exp0)printf(%dx^(%d),p-coef,p-exp);elseprintf(%d,p-coef);}else{if(p-exp0)-11-printf(%dx^%d,p-coef,p-exp);elseif(p-exp0)printf(%dx^(%d),p-coef,p-exp);elseprintf(%d,p-coef);}p=p-next;}}voidInsortup(PolyNode*h)//排序函数，使多项式中的各项按X的升幂排列{PolyNode*s,*p;intt,m;for(p=h-next;p!=NULL;p=p-next)//类似于冒泡排序{for(s=h-next;s-next!=NULL;s=s-next){if(s-exps-next-exp){t=s-exp;m=s-coef;s-coef=s-next-coef;s-exp=s-next-exp;s-next-coef=m;s-next-exp=t;}}}}voidInsortdown(PolyNode*h)//排序函数，使多项式中的各项按X的降幂排列{PolyNode*s,*p;intt,m;for(p=h-next;p!=NULL;p=p-next)//类似于冒泡排序{for(s=h-next;s-next!=NULL;s=s-next){if(s-exps-next-exp){t=s-exp;m=s-coef;s-coef=s-next-coef;s-exp=s-next-exp;-12-s-next-coef=m;s-next-exp=t;}}}}voidUnitePoly(PolyNode*h)//合并同类项{PolyNode*p1,*p2,*q1,*q2,*temp;q1=h;p1=q1-next;while(p1!=NULL){p2=p1-next;q2=p1;while(p2!=NULL){if(p1-exp==p2-exp){p1-coef=p1-coef+p2-coef;if(p1-coef==0){temp=p2;q2-next=p2-next;free(temp);temp=p1;q1-next=p1-next;p1=q1;free(temp);break;}else{temp=p2;q2-next=p2-next;p2=p2-next;free(temp);}}else{q2=p2;p2=p2-next;}-13-}q1=p1;p1=p1-next;}}PolyNode*polymuti(PolyNode*h1,PolyNode*h2)//多项式相乘{PolyNode*h,*p,*p1,*p2,*q;p1=h1-next;h=p=(PolyNode*)malloc(sizeof(PolyNode));p-next=NULL;while(p1){p2=h2-next;while(p2){q=(PolyNode*)malloc(sizeof(PolyNode));q-coef=p1-coef*p2-coef;q-exp=p1-exp+p2-exp;p-next=q;p=q;p2=p2-next;}p1=p1-next;}p-next=NULL;return(h);}PolyNode*addition(PolyNode*ha,PolyNode*hb)//一元多项式相加函数，用于将两个多项式相加，然后将和多项式存放在多项式ha中，并将多项式hb删除{PolyNode*p,*q,*pre,*temp;intsum;p=ha-next;q=hb-next;pre=ha;while(p!=NULL&&q!=NULL){if(p-expq-exp){pre-next=p;pre=pre-next;p=p-next;}elseif(p-exp==q-exp){-14-sum=p-coef+q-coef;if(sum!=0){p-coef=sum;pre-next=p;pre=pre-next;p=p-next;temp=q;q=q-next;free(temp);}else//如果系数和为零，则删除结点p与q，并将指针指向下一个结点{temp=p-next;free(p);p=temp;temp=q-next;free(q);q=temp;}}else{pre-next=q;pre=pre-next;q=q-next;}}if(p!=NULL)//将多项式A中剩余的结点加入到和多项式中pre-next=p;elsepre-next=q;returnha;}PolyNode*subduction(PolyNode*ha,PolyNode*hb)//一元多项式相减函数，用于将两个多项式相减，然后将差多项式存放在多项式ha中，并将多项式hb删除{PolyNode*p,*q,*pre,*temp;intsum;p=ha-next;q=hb-next;pre=ha;while(p!=NULL&&q!=NULL){if(p-expq-exp){pre-next=p;pre=pre-next;p=p-next;}elseif(p-exp==q-exp){-15-sum=p-coef-q-coef;if(sum!=0){p-coef=sum;pre-next=p;pre=pre-next;p=p-next;temp=q;q=q-next;free(temp);}else//如果系数和为零，则删除结点p与q，并将指针指向下一个结点{temp=p-next;