资源描述:
《数据结构上机实习报告.doc》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、数据结构上机实习报告实验题目:一元多项式班级:193121姓名:邹冠宏学号:20121002758指导老师:郭艳完成日期:2013/9/30一问题分析1.问题描述设计一个n元多项式程序,并完成多项式的加法,乘法运算。从实际的角度出发,这里设计的程序是基于一元n次多项式的数学模型。2、功能需求1)构造一个空的多项式。2)多项式插入新的一项。3)计算多项式的值。4)打印多项式。5)多项式合并同类项。6)多项式加法。7)多项式乘法。8)多项式减法二、概要设计1问题分析在数学上,一个一元多项式Pn(x)可按升幂写成:Pn(
2、x)=a0+a1x+a2x^2+…+anx^n-1.它由n+1个系数惟一确定,因此,在计算机里,它可用一个线性表P来表示:Pn=(a0,a1,a2,…,an)每一项的指数i隐含在其系数ai的序号里。2数据模型设计一个单链表模型,动态分配空间,刻意随时插入新的一项多项式加法规则:两个具有相同指数的项合并,系数为0时把这一项省去,也就是删除了这一节点。多项式的乘法规则:多次运用单项式与多项式相乘的法则得到的.计算时(a+b)(c+d),把(c+d)看成一个单项式,(a+b)是一个多项式,运用单项式与多项式相乘的法则,得
3、到(a+b)(c+d)=a(c+d)+b(c+d),然后再次运用单项式与多项式相乘的法则。3构造数据结构通过分析多项式的特征,不难看出多项式是由单项式构成的,而每个单项式都具有系数和指数,当系数为0时,该项就失去了意义,在计算机内要表示一个多项式,至少以下数据信息:系数信息、指数信息和指向下一个单项式的指针。通过指针,我们就可以把多个单项式连接起来,形式一个多项式,基于以上的分析,我们定义多项式的数据结构为如下结构体形式:typedefstructPolynomial{floatcoef;//系数intexpn;/
4、/指数structPolynomial*next;//指向下一个结点}*Polyn,Polynomial;//Polyn为结点指针类型三、详细设计1一元多项式运算程序具有以下基本功能:1).界面输出,提示如何输入数据。要求先输入多项式的项数。2).创建多项式。接收输入的数据,并保存到链表中。3).显示程序的功能表,允许使用者选择运算类型。4).打印多项式。5).实现加法运算。7).实现乘法运算。6).清除内存内容,销毁创建的链表,退出程序。2功能算法描述与数据结构说明该多项式程序除了main()函数外,主要有以下函
5、数:PolynCreatePolyn(Polynhead,intm)voidInsert(Polynp,Polynh)voidPrintPolyn(PolynP)intcompare(Polyna,Polynb)PolynAddPolyn(Polynpa,Polynpb)PolynMultiplyPolyn(Polynpa,Polynpb)voidDestroyPolyn(Polynp)voidCountPolyn(PolynP,intk)3.主要功能函数的详细设计1). main()函数main函数是用来实现提示
6、使用者输入、显示功能列表、调用其他运算函数实现运算功能。在main()函数中,定义m、n用来保存两个多项式的项数,pa、pb、pc、pd、pf定义程序所需链表的头指针。在程序开始要求输入两个多项式的项数,随后根据项数创建两个链表以保存多项式,再显示出功能列表后通过输入数字来选择来实现功能的选择,从而达到对整个程序流程进行控制。2).PolynCreatePolyn(Polynhead,intm)该函数功能是创建新的多项式链表。intm保存的多项式的项数,使用for语句,控制输入多项式的每一项。若创建的链表长度为m时
7、,将不再提示用户继续输入多项式的系数和指数。因为是从0项开始计算的。在该函数中要用到分配空间的函数malloc()为新建链表分配空间。而空间的长度要用sizeof()。3).voidInsert(Polynp,Polynh)该函数功能:将新的节点p插入到现有链表的后面,并确保多项式的指数exp是升序。将s节点插入到head所指向的链表。在该函数的操作中,要注意指针是如何移动的。对插入的位置要分情况讨论。在头,中,尾三处的插入。4).intcompare(Polyna,Polynb)该函数功能:判断两个多项式在同一指
8、数下是否有其中一个为系数为0。根据不同情况来讨论多项式的指数,用来辅助加法和乘法运算。5).PolynAddPolyn(Polynpa,Polynpb)该函数功能:实现两个多项式pa、pb相加,并将计算结果存储于新建立的pc中,它的原理是将指数相同的单项式相加,系数相加后为0,则pa、pb的指针都后移。在加法计算中要求pa,与pb的幂次序都是升序,否则可能得