下载

0下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 n元多项式的乘法

n元多项式的乘法.doc

n元多项式的乘法

有一种爱叫放肆选择
2017-09-28 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《n元多项式的乘法doc》,可适用于高等教育领域

n元多项式的乘法《数据结构》课程设计题目n元多项式的乘法学生姓名指导教师学院专业班级完成时间目录(要求自动生成)第一章课程设计目的第二章课程设计内容和要求第三章课程设计分析第四章算法描述第五章源代码第六章运行结果分析第七章结束语第八章参考文献第一章课程设计目的本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非常强的课程为了让大家更好地理解与运用所学知识提高动手能力我们进行了此次课程设计实习。这次课程设计不但要求实习者掌握《数据结构》中的各方面知识还要求实习者具备一定的C语言基础和编程能力。具体说来这次课程设计主要有两大方面目的。一是让实习者通过实习掌握《数据结构》中的知识。对于《图的存储与遍历》这一课题来说所要求掌握的数据结构知识主要有:图的邻接表存贮结构、队列的基本运算实现、邻接表的算法实现、图的广度优先搜索周游算法实现、图的深度优先搜索周游算法实现。二是通过实习巩固并提高实习者的C语言知识并初步了解VisualC的知识提高其编程能力与专业水平。第二章课程设计内容和要求课程设计内容功能:完成两个n元多项式作乘法给出明确的等式形式。分步实施:)(初步完成总体设计搭好框架确定人机对话的界面确定函数个数)(完成最低要求:建立一个文件实现两个一元二次多项式作乘法。)(进一步要求:实现三元二次多项式的乘法。该程序的运行环境为Windowsxp系统MicrosoftVisualC版本。第三章课程设计分析我们用的存储方式是单链表单链表在C语言中是一种非常常见的结构而在C中的实现却又有不同在一些地方更简单更严密。同时由于C的一些特点使它具有C语言所不具有的“安全化”所以本程序用C。有了链表特定的数据类型Mulpoly接下来就需要建立这个链表。这里我们自定义一个构造函数CreatePoly来构造链表。首先定义一个CreatePoly型的指针变量head作为头结点存储多项式的信息(项数)为head分配存储空间建立一个头结点并为其数据域赋值分配存储空间用c语言中的malloc来实现这时输入多项式的项数num把它赋值给head的coef域exp域赋值为此时再定义一个CreatePoly型的指针变量r指向head头结点。还要用类似的算法建立多项式的其它结点剩余节点的插入用一个while循环来实现while循环中的控制变量i从大于的数n开始递增直到到达num此时while循环结束。While循环的循环体由两部分组成第一部分是为指针变量s分配存储空间和为其数据域赋值分配存储空间同样用c语言中的malloc来实现第二部分是节点的指针域转换过程将r的指针域指向新生成的结点s相当于将生成结点依次用指针连接然后将最后一个结点的指针域设置为具体代码如下:MulPoly*CreatePoly(){MulPoly*head,*r,*sintm,n,num,i=head=(MulPoly*)malloc(sizeof(MulPoly))cout<<"请输入多项式的项数:"<<endlcin>>numhead>coef=numhead>exp=r=headwhile(i<=num)n不为时建立多项式链表{s=(MulPoly*)malloc(sizeof(MulPoly))cout<<"输入第"<<i<<"组系数和指数:"<<endlcin>>n>>ms>exp=ms>coef=nr>next=sr=si}r>next=return(head)}在处理多项式相乘的问题时定义一个PolyMulti函数实现需要再建立一个MulPoly型的链表存储相乘之后的链表定义结果链表的系数等于链表P的系数乘以链表P的系数:(p>coef)=(p>coef)*(p>coef)结果链表的指数等于链表P的指数乘以链表P的指数:(p>exp)=(p>exp)(p>exp)。在整理之后可能出现零结点那么就需要进行判断和删除操作同时释放零结点这些操作是通过一个while循环来完成。具体代码如下:while(p!=q){s=qq=q>next}s>next=q>nextfree(q)}还需要定义一个输出函数在主函数中调用输出两个多项式相乘后的结果。程序的最终都是由主函数来实现。在主函数中通过对一些自定义函数的调用实现具体的操作。在此主函数调用了一个构建链表的函数CreatePoly、一个删除空结点的函数Delete和输出函数Print。在主函数的开始需要定义三个MulPoly型指针变量分别用来存储调用CreatePoly函数和PolyMulti函数生成的链表和结果链表。在构建链表之前要给节点分配存储空间s=(MulPoly*)malloc(sizeof(MulPoly))这条语句便可完成此操作。此条语句运用了c语言库函数中的malloc函数这个函数的作用是在内存的动态存储区中分配一个长度为sizeof(MulPoly)的内存空间。调用构建链表函数CreatePoly后链表Pl便构建完成。接下来需要执行m=PolyMulti(p,q)语句这条语句的目的是把多项式P和P相乘的结果多项式存储在链表m当中然后执行Print(m)语句显示输出。主函数的程序框架如下:intmain(){MulPoly*p,*q,*mp=CreatePoly()q=CreatePoly()m=PolyMulti(p,q)MergeSame(m)Print(m)system("pause")}程序的调试是程序顺利完成中非常关键的一步。通过程序的调试分析可以解决程序的运行错误也可以对程序的性能进行分析。这个多项式运算问题研究的程序最重要的就是看输出的链表是否正确是否带有空结点合并是否完全。决定程序成功与否的第一步是定义的PolyMulti函数操作是否正确。如果这一步中出现错误那么接下来的操作可以说是错上加错。在调试的时候可以在程序中加入删除、释放空结点操作此操作便是由Delete函数完成的若输出的多项式没有空结点说明函数正确可以继续向下进行。接下来就是相乘后的合并同类项控制此操作的关键是一个MergeSame函数调用Delete函数是决定成功与否的关键。可以先在本上写出两个正确的简单的多项式使其具有相加后出现空结点的特点然后变换循环变量的范围当输出吻合时则说明操作正确。各个关键部分都已检查完毕剩下的就是对程序的进一步细心的完善直到满足要求。下面我们分析一下程序的性能。在主函数中首先调用的是构造单链表函数CreatePoly在这个函数中需要通过一个for循环为每个结点分配存储空间变换节点的next域时间复杂度为O(n)。接下来执行一个双重for循环在内部的for循环中是对结点的相加、相乘操作因为是按着指针的方向就可以对结点进行相加、相乘操作所以每个结点n的操作都需要m次共n个结点则需要m次操作时间n复杂度为O(n)。第四章算法(数据结构)描述一、概要设计定义单链表的抽象数据类型:ADTLinkList{数据对象:D={ai|aiElemSet,i=,,,…n>=}数据关系:R={<ai,ai>|ai,aiD}线性表的单链表基本操作LinkListInitList(void)构造一个空的线性表voidDestroyList(LinkList*L)初始条件:线性表L已存在。操作结果:销毁线性表L。LinkListMakeEmpty(LinkListL)‘初始条件:线性表L已存在。操作结果:将线性表L重置为空表。intIsEmpty(LinkListL)初始条件:线性表L已存在。操作结果:判断线性表是否为空表。intListLength(LinkListL)初始条件:线性表L已存在。操作结果:返回线性表L结点的个数。LNodeIsLast(LinkListL)初始条件:线性表L已存在。操作结果:返回线性表L的最后一个结点(尾结点)。LNodeNewLNode(ElemTypeX)构造一个数据域为X的新结点LNodeFindPrefious(ElemTypeX,LinkListL)初始条件:线性表L已存在。操作结果:在线性表L中寻找值为X的结点若找到则返回该结点的前驱否则返回。voidListDelete(LNodePre)初始条件:线性表L中结点P已找到。操作结果:删除该结点。链表的结点结构:datanext东部data域存放结点值的数据域西部北部next域存放结点的直接后继的地址(位置)的指针域(链域)第一季度第三季度此题定义系数和指数结构如下:cenoexexfpt线性表的单链表存储结构TypedefstructLnode{ElemTypedata结点的数据域StructLnode*next结点的指针域}Lnode,*LinkList基本操作InitArray(A,n,bound,,boundn)操作结果:若维数n和各维长度合法则构造相应数组A。DestroyArray(A)初始条件:数组A已经存在。操作结果:销毁数组A。Value(A,e,index,,indexn)初始条件:A是n维数组e为元素变量n个下标值。操作结果:若各下标不超界则e赋值为所指定的A的元素值并返回OK。Assign(A,e,index,,indexn)初始条件:A是n维数组e为元素变量n个下标值。操作结果:若下标不超界则将e的值赋给A中指定下标的元素。}ADTArray第五章源代码(源代码必须给注释)单链表表示#include<stdlibh>#include<stdioh>#include<ctypeh>#include<iostream>#defineusingnamespacestdtypedefstructterm{项的表示多项式的项作为LinkList的数据元素floatcoef系数intexpn指数structterm*next}termintEmpty(term*L){if(L>next!=)returnreturn}term*CreatePoly(){term*head,*r,*sintm,n,num,i=head=(term*)malloc(sizeof(term))建立一个头结点cout<<"请输入多项式的项数:"<<endlcin>>numhead>coef=numhead>expn=r=headwhile(i<=num)n不为时建立多项式链表{s=(term*)malloc(sizeof(term))建立一个新结点cout<<"输入第"<<i<<"组系数和指数:"<<endlcin>>n>>ms>expn=ms>coef=nr>next=sr=si}r>next=return(head)}term*PolyMulti(term*f,term*g){term*p,*p,*p,*r,*headhead=(term*)malloc(sizeof(term))head>coef=head>expn=r=headfor(p=f>nextp!=p=p>next){for(p=g>nextp!=p=p>next){p=(term*)malloc(sizeof(term))(p>coef)=(p>coef)*(p>coef)(p>expn)=(p>expn)(p>expn)r>next=pr=p}}r>next=returnhead}voidDelete(term*L,term*p){term*s,*qs=Lq=L>nextwhile(p!=q){s=qq=q>next}s>next=q>nextfree(q)}voidPrint(term*L){term*pcout<<"两个多项式相乘的结果为:"<<endl<<"P(x)="if(Empty(L)){for(p=L>nextp!=p=p>next)cout<<"("<<p>coef<<")"<<"x"<<"^"<<p>expn<<""cout<<"b"}elsecout<<""}voidMergeSame(term*f){term*p,*qfor(p=f>nextp!=p=p>next)for(q=p>nextq!=q=q>next){if(p>expn==q>expn){(p>coef)=(p>coef)(q>coef)Delete(f,q)}if(p>coef==){Delete(f,p)break}}}term*CreatPolyn(term*P,intm){输入m项的系数和指数建立表示一元多项式的有序链表Pif(m<=)returnterm*h=P=(term*)malloc(sizeof(term)),*qP>coef=intiprintf("依次输入d个数(前一个为系数后一个为指数)n",m*)for(i=i<=mi){依次输入m个非零项scanf("fd",P>coef,P>expn)if(P>coef)q=PP=P>next=(term*)malloc(sizeof(term))}q>next=free(P)returnh}CreatPolynterm*selsort(term*h){term*g,*p,*qif(!h)returnfloatfinti,fini=for(g=hg>nextfinig=g>next){fini=for(p=h,q=h>nextqp=p>next,q=q>next)if(p>expn<q>expn){f=p>coefi=p>expnp>coef=q>coefp>expn=q>expnq>coef=fq>expn=ifini=}}for(g=h,p=g>nextp)if(g>expn==p>expn){g>coef=p>coefg>next=p>nextq=pp=p>nextfree(q)}elseif(g>next){g=g>nextp=p>next}returnh}voidPrintfPoly(term*P){term*q=Pif(!q){putchar('')return}if(q>coef!=){printf("g",q>coef)if(q>expn==)putchar('X')elseif(q>expn)printf("X^d",q>expn)}elseif(!q>expn)putchar('')elseif(q>expn==)putchar('X')elseprintf("X^d",q>expn)q=q>nextwhile(q){if(q>coef>)putchar('')if(q>coef!=){printf("g",q>coef)if(q>expn==)putchar('X')elseif(q>expn)printf("X^d",q>expn)}elseif(!q>expn)putchar('')elseif(q>expn==)putchar('X')elseprintf("X^d",q>expn)q=q>next}}intCompare(term*a,term*b){if(a>expn<b>expn)returnif(a>expn>b>expn)returnreturn}term*APolyn(term*Pa,term*Pb){多项式加法:Pa=PaPb利用两个多项式的结点构成"和多项式"。term*h,*qa=Pa,*qb=Pb,*p,*qfloatsumh=p=(term*)malloc(sizeof(term))p>next=while(qaqb){Pa和Pb均非空switch(Compare(qa,qb)){case:多项式PA中当前结点的指数值小p>next=qbp=qbqb=qb>nextbreakcase:两者的指数值相等sum=qa>coefqb>coefif(sum!=){修改多项式PA中当前结点的系数值p>next=qaqa>coef=sump=qaqa=qa>next}else{删除多项式PA中当前结点q=qaqa=qa>nextfree(q)}q=qbqb=qb>nextfree(q)breakcase:多项式PB中当前结点的指数值小p>next=qap=qaqa=qa>nextbreak}switch}whileif(Pa)p>next=qa链接Pa中剩余结点if(Pb)p>next=qb链接Pb中剩余结点q=hh=h>nextfree(q)returnh}APolynterm*A(term*Pa,term*Pb){intnputs("输入第二个一元多项式的项数")scanf("d",n)Pb=CreatPolyn(Pb,n)Pb=selsort(Pb)PrintfPoly(Pa)if(PbPb>coef>)printf("")PrintfPoly(Pb)Pa=APolyn(Pa,Pb)printf("=")Pa=selsort(Pa)PrintfPoly(Pa)returnPa}term*BPolyn(term*Pa,term*Pb){多项式减法:Pa=PaPb利用两个多项式的结点构成"差多项式"。term*p=Pbwhile(p){p>coef*=p=p>next}returnAPolyn(Pa,Pb)}BPolynterm*B(term*Pa,term*Pb){intnputs("输入第二个一元多项式的项数")scanf("d",n)Pb=CreatPolyn(Pb,n)Pb=selsort(Pb)PrintfPoly(Pa)printf("")putchar('(')PrintfPoly(Pb)putchar(')')Pa=BPolyn(Pa,Pb)printf("=")Pa=selsort(Pa)PrintfPoly(Pa)returnPa}intmain(){term*M,*Nterm*p,*q,*mcharsinti,nf:puts("n:加n:乘n:下一步")cin>>iswitch(i){case:puts("一元多项式计算:n输入第一个一元多项式的项数")scanf("d",n)M=CreatPolyn(M,n)M=selsort(M)PrintfPoly(M)M=A(M,N)gotofcase:p=CreatePoly()q=CreatePoly()m=PolyMulti(p,q)MergeSame(m)Print(m)gotofcase:breakdefault:puts("输入有误,请重新输入!")}}*程序源代码:*数组表示#include"stdioh"#defineN宏定义为多项式的系数数组开辟空间staticintk=记录多项式的个数voidinput(floata,intna){多项式a的系数输入其中na为次数intiprintf("请输入多项式Pd(x)的各项系数数(从高次项到低次项中间缺项则为):n",k)for(i=i<=nai){输入各项系数scanf("f",ai)}while(a==){首项系数不为printf("首项系数不能为请重新输入首项系数:")scanf("f",a)}printf("Pd(x)=f*x^d",k,a,na)for(i=i<nai){打印输入的多项式if(ai!=)printf("f*x^d",ai,nai)}if(ana!=)printf("f",ana)printf("n")k自增记录下个多项式}voidmul(floata,floatb,intna,intnb){系数相乘intn,i,jfloatcN记录乘积的系数n=nanb乘积的最高系数for(i=i<=ni)乘积系数初始化为ci=for(i=i<=nai){for(j=j<=nbj)cij=ai*bj对应相同次数的系数相加}printf("乘积P(x)=f*x^d",c,n)for(i=i<ni){打印输入的多项式if(ai!=)printf("f*x^d",ci,ni)}if(an!=)printf("f",an)printf("n")}voidmain(){floatAN,BN开辟两个数组记录多项式的值intn,nprintf("请输入多项式Pd(x)的次数:",k)scanf("d",n)input(A,n)printf("请输入多项式Pd(x)的次数:",k)scanf("d",n)input(B,n)mul(A,B,n,n)}第六章运行结果分析下面我们测试P=x^x^x^P=x^x^P=P*P=(x^x^x^)*(x^x^)=x^x^x^x^x^x^测试P=*x^*x^*x^*x^P=*x^*x^*x^P=P*P=(*x^*x^*x^*x^)*(*x^*x^*x^)测试结果如图:第七章结束语转眼为期两周的《数据结构》课程设计实习即将结束了。在这次实习中自己的C语言知识和数据结构知识得到了巩固编程能力也有了一定的提高。同时也学会了解决问题的方法。总结起来自己主要有以下几点体会:必须牢固掌握基础知识。由于C语言是大一所学知识有所遗忘且未掌握好这学期所学的《数据结构》这门课所以在实习之初感到棘手。不知如何下手但在后来的实习过程中自己通过看书和课外资料并请教其他同学慢慢地对C语言和数据结构知识有所熟悉。这时才逐渐有了思路。所以这次实习之后我告诫自己:今后一定要牢固掌握好专业基础知识。必须培养严谨的科学态度。自己在编程时经常因为一些类似于“少了分号”的小错误而导致错误不够认真细致这给自己带来了许多麻烦。编程是一件十分严谨的事情容不得马虎。所以在今后自己一定要培养严谨的科学态度。我想这不仅是对于程序设计做任何事都应如此。这次课程设计也让我充分认识到《数据结构》这门课的重要性。它给我们一个思想和大纲让我们在编程时容易找到思路不至于无章可循。同时它也有广泛的实际应用。总之在这次实习中自己的C语言以及数据结构知识得到提高编程能力也得到了提高。第八章参考文献(要求不少于篇可以是论文可以是专著)(杨路明C语言程序设计教程北京邮电大学出版社(徐孝凯数据结构课程实验清华大学出版社(严蔚敏吴伟民数据结构,C语言版,清华大学出版社

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/27

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利