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

福建农林大学计算机与信息学院课程设计报告课程名称：数据结构课程设计题目：一元多项式的加法减法乘法的实现姓 名：系：软件工程系专 业：软件工程专业年 级：2014学 号：指导教师：黄思先职 称：副教授完成起止日期：2016.6.5 - 2016.7.12016年07月1日福建农林大学计算机与信息学院课程设计结果评定评价内容评价指标评分权值评定成绩业务水平有扎实的基础理论知识和课程知识；能正确设计实验方案；独立进行实验工作；能运用所学课程知识和技能去发现与解决实际问题0.2设计质量实验正确，分析处理科学；设计结果有应用价值；图纸绘制符合国家标准，质量符合要求；计算及测试结果准确；工作中有创新意识；对前人工作有改进或突破，或有独特见解； 0.4工作量、工作态度按期完成规定的任务，工作量饱满，难度较大；工作努力，遵守纪律；工作作风严谨务实0.2报告质量文字通顺，技术用语准确，符号统一，编号齐全，书写工整规范，图表完备、整洁、正确；0.2合 计1.0指导教师签字：评定日期：目录一、 问题分析和任务定义1二、 程序设计内容1三、 程序调试与测试7四、 实验心得9五、 程序编码9一、问题分析及任务定义顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。 【问题描述和基本要求】 设有一元多项式Am(x)和Bn(x). Am(x)=A0+A1x1+A2x2+A3x3+ +Amxm Bn(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()多项式输出函数void Prin_poly(PolyNode *h)多项式升序排列函数void Insortup(PolyNode *h)多项式降序排列函数void Insortdown(PolyNode *h)多项式合并函数void UnitePoly(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输出文字合并同类项排序输出多项式A创建多项式B输出文字 合并同类项排序输出多项式BadditionYa=1NYsubductiona=2NYa=3polymuti结束(2) void Insortup(PolyNode *h)开始p=hnext结束NP!=NULLYp=hnexts=hnextNs=snextsexp与snextexp互换scoef与snextcoef互换Ysnext!=NULLsexpsnextexpYN- 17 -(3)void Insortdown(PolyNode *h)开始p=hnext结束NP!=NULLYp=hnexts=hnextNs=snextsexp与snextexp互换scoef与snextcoef互换Ysnext!=NULLsexpsnextexpYN(4) PolyNode *polymuti(PolyNode *h1,PolyNode *h2)（5）void UnitePoly(PolyNode *h) (6) PolyNode *addition(PolyNode *ha, PolyNode *hb)开始 三、程序调试与测试 相加结果相减结果相乘结果四、 实验心得在本次课程设计中，我明白了理论应与实际相结合，上机练习是提高编程能力最有效的办法，这次实验提高了我编写大型程序的能力以及查阅资料并从中获得有效资料的能力。这次课程设计加深了我对数据结构的进一步理解。五、程序编码实验程序：#include#include #include typedef struct Nodeint coef;/系数int exp;/指数struct Node *next;PolyNode;PolyNode *Creatpoly()/创建多项式的单链表PolyNode *h,*p,*q;h=(PolyNode *)malloc(sizeof(PolyNode);p=h;p-next=NULL;printf(请输入多项式的系数及其指数a b，当系数输入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);void Prin_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);else if(p-expcoef,p-exp);elseprintf(+%d,p-coef);else if(p-coefnext)if(p-exp0)printf(%dx%d,p-coef,p-exp);else if(p-expcoef,p-exp);elseprintf(%d,p-coef);else if(p-exp0)printf(%dx%d,p-coef,p-exp);else if(p-expcoef,p-exp);else printf(%d,p-coef);p=p-next;void Insortup(PolyNode *h)/排序函数，使多项式中的各项按X的升幂排列PolyNode *s,*p;int t,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;void Insortdown(PolyNode *h)/排序函数，使多项式中的各项按X的降幂排列PolyNode *s,*p;int t,m;for(p=h-next;p!=NULL;p=p-next)/类似于冒泡排序for(s=h-next;s-next!=NULL;s=s-next)if(s-expnext-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;void UnitePoly(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;elsetemp=p2;q2-next=p2-next;p2=p2-next;free(temp);elseq2=p2;p2=p2-next;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; int sum; p=ha-next; q=hb-next; pre=ha; while(p!=NULL&q!=NULL) if(p-expexp) pre-next=p; pre=pre-next; p=p-next; else if(p-exp=q-exp) 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; else pre-next=q; return ha;PolyNode *subduction(PolyNode *ha, PolyNode *hb)/一元多项式相减函数，用于将两个多项式相减，然后将差多项式存放在多项式ha中，并将多项式hb删除 PolyNode *p,*q,*pre,*temp; int sum; p=ha-next; q=hb-next; pre=ha; while(p!=NULL&q!=NULL) if(p-expexp) pre-next=p; pre=pre-next; p=p-next; else if(p-exp=q-exp) 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; else pre-next=q; return ha;main() int a=-1;PolyNode *h1,*h2,*h;h1=Creatpoly();printf(该多项式为P1(x)=);UnitePoly(h1);Insortup(h1);Prin_poly(h1);printf(n);h2=Creatpoly();printf(该多项式为P2(x)=);UnitePoly(h2);Insortup(h2);Prin_poly(h2);printf(n);printf(输入1查看两多项式相加结果n输入2查看两多项式相减结果n输入3查看两多项式相乘结果n);scanf(%d,&a);if(a=1)printf(相加后的多项式n);h=addition(h1,h2);UnitePoly(h);printf(按X的升幂排列);Insortup(h);Prin_poly(h);printf(n);printf(按X的降幂排列);Insortdown(h);Prin_poly(h);printf(n);if(a=2)printf(相减后的多项式n);h=subduction(h1,h2);UnitePoly(h);printf(按X的升幂排列);Insortup