《（可编）两一元高次多项式的乘法》由会员分享，可在线阅读，更多相关《（可编）两一元高次多项式的乘法（14页珍藏版）》请在金锄头文库上搜索。
1、文档从网络中收集.己重新整理排版.word版本可编辑.欢迎下我支持.数据结构与算法课程设计报告书课程设计题目 实现任意两个一元高次多项式的乘法运算院 系名称 计算机科学与技术系专业（班级） 姓名（学号） 指导教师 完成时间 【课题】设计程序以实现任意两个髙次多项式的乘法运算。【要求】1所设计的数据结构应尽可能日省空间o （2程序的运行时间尽可能少一、问题分析和任务定义：1. 问题描述：根据对本次设计课题的理解：实现是任意两个髙次多项式相乘，可以是一元也可以是多 元.在本次设计中针对的是对两个一元高次多项式的相乘。首先髙次多项式可以出现两次到 务次及两项到多项的多种不同情况：其次存储空间和程序运
2、行时间是矛盾的.必须从中找到 最合理的算法使得程序存储空间及运行时间都相对较少。2. 输入、输出的形式.输入多项式时应注意该元之前的数字为系数.其后数字为指数，本程序按提示采用的人 机对话的形式输入每一项的系数（实数型）和指数（整型） 输出时是以数学表达式的形式输出，如输出相乘后的结（4.3*XT） +（-!3*XM）3. 算法（程序）所能达到的功能 多项式的建立 多项式的相乘合并同类项对合并后的多项式按降繇排序输出最终多项式表达释放内存4. 测试用的数据（注：以下enter代表回车换行）输入两个多项式并相乘:（x+2.5x2+3x3）*（-4x4+5x5）12.5X7-5XMX5+15X%
3、12X12 enter输出相乘后的结果：1enter1enter2.5enter2enter3 enter3enter-4enter4enter5enter5enter1enter1enter1.6enter-5enter86 enter3enter(12.5*xA7)+(-5*xA6)+(-4*xA5)+( 15*xA2) +(- 12*xAl)在程序中的输入：在程序中的输出：二、概要设计和数据结构的选择根据对本课题的理解，线性表是一个很好的选择。而线性表有两种口 J选的存储表示方式, 顺序表和链表。考虑到课题要求：所设计的数据结构应尽可能廿省空间.若采用顺序存储. 需事先分配足够的空间，造
4、成内存空间的浪费：而用链接存储动态创建新结点以存储多项 式的项，就简单的多。所以本设计采用的数据结构是链表。1. 算法（程序）中用到的所有各种数据类型的定义本程序设计用到一中结构体和若干中变量的定义如下：1.1用单链表存储多项式的结点：struct List（ float data: / 系数int index:/指数struct List *nexl:少多项式项的数据类型定义1.2其它主要变量的定义：int testNum;/测试数据的组数int LVNum. LB.Num;多项式A, B中的项数struct List/定义两个链表，分别表示要相加的两个多项式中的项struct List *
5、pa, *pb=NULL;/pa指向存放相乘后的结果.pb为空指针指向合并 同类项后的结果Iword版本口J编辑.欢迎卜载支持.文档从网络中收集.己重新整理排版.word版本可编辑.欢迎下我支持.struct List *result; 指向合并同类项后按降昇排序后的结果2. 程序流程图流程图说明： 先定义变量并初始相关变量 输入测试数据的组数 分配两多项式的存储空间 调用inputData()建立多项式 A不为空时执行相乗 如果A、B只有一项无须合并直接跳到 否则要进行合并同类项，排序合并后的结果 输出排序后的结果今释放内存今如果循环次数不大于测试数据组数,跳到进行卜一组 测试数据开始初始化
6、相关变18输入测试La.lb分配内存调用inpuiDmm理立多 项式A. BA乡项艾的B多項式的URMSfll二A不为空2word版本可编辑.欢迎卜裁支持.A左项式指针后移降*排序多頂式腐岀多项式作放内存图1.流程图图2.函数调用图文档从网络中收集.己重新整理排版.word版本可编辑.欢迎下我支持.各函数的功能如下：inputData()功能：完成多项式建立，如输入系数，指数的输入都在此函数中完成。LaAndLb()功能：完成la中的某项分别与lb中的每一项相乗。PaAndPbO功能：完成把相乘后的结果进行合并同类项。OrderO功能：完成最终合并后的结果按降皋排序。Print。功能：完成把最
7、终排序后的结果以数学表达式的形式输出.freeM ()功能：完成中间变量所占存储空间的释放。Introduce。功能：输岀登陆界面的信息提示。三、详细设计和编码变虽说明：data-多项式系数index 一多项式指数testNum-测试数据的组数laA多项式lbB多项式LA_NumA多项式的项数LB.Num-B多项式的项数pb用来存放新多项式相加后的结果paA中某项与B中每项相乘后得到的新的多项式 result指向结果的头指针。LaLb临时存放相乘结果在此次设计中用到三个主要函数具体算法描述如下： LaAndLbO：算法描述：先将A多项式分解，函数LaAndLbO,此函数中冇四个参数，分别为A中
8、某项系 数：data; A中某项指数：index;B多项式：lb和B名项式的项数：ListB.Num; 通过for循环控制使每次传来A的某项与B中的所有项相乘，形成一个新的多 项式存放临时指针变量LaLb中。返回主函数。(2) PaAndPbO：算法描述：将中产生新的多项式用pa表示，定义一个空链表pb。利用函数PaAndPbO 将多项式pa与pb进行相加。第一次循环是将pa复制到pb中，此后，pa中项 与pb中的某项的指数相同，则将两系数相加，如果pb中没有与pa相等的项, 则将pa插到pb的末端。 Order。：算法描述:经过ListA.Num次循环，pb中存放的是没冇排序的结果。函数or
9、der 0的功能就 是用来给结果排序。本函数是通过定义几个中间结构体指针变量,每次使pb中的 进行冒泡排序，实现将排好序的链表的头指针城给result.四、上机调试下面为调程序遇到的问题和最后实验成功的心得体会：1. 程序调试遇到的问题：在程序调试中遇到六种问题如下1.1由于输出i吾句printf()在输出提示语时由于在书写时粗心导致下图3错误： ilu?uieiit5 di)(l SelliiiMJXujei X-bjkcsj.cpp(110) ; error C2018;_uiiknuwii chardcLer Cxc7 :Docunent5 and Settinqsusers jXkcs
10、j .cpp(11 0) : error C2918: unknown character * 6xeL :Docunent5 and Settingsuser面、sj、kc5j.cpp(110) : error C2018: unknown character 6xca 图33word版本口J编辑.欢迎卜裁支持.文档从网络中收集.己重新整理排版.word版本可编辑.欢迎下我支持.1.2由于在所有的scanf(H%f&p-data;ift句少&而导致出现卜图4情况: C:Docments and SettingsuserMsjDebus唉聽学组岑坦教摇一一奇数项为系数;偈数顼为指数。应用程序辱
11、误2d。心如製爻扌鈴引冃的hqJHOOV内净 该为有不能力，丫代0.图41.3当输入的测试数据组数超岀1时，运行时只能完成第一组测试数据，不能进入下一组測 试数据的输入主要是在main。函数中对测试数据的组数任for循环没控制好所致。1.4开始输入的多项式要按降品输入才能得岀正确结果，否则运算结果岀错，加了一个sinicl List *order(struct List*&pb)解决 了 此问题图51.6任输入地一个多项式的项数为1时岀现下面图6的问题:1.5由于要求界而更美观，现想要求在输出时：整数就输整数.小数输小数。出现以下问题, 当在一行输入时，系数和指数之间用空格分隔而出现指数没被接
12、受结果出错如下图5示。 加逗号输入解决了，八，and Sztin.，0604081昇兰金糸篦乌(丄。8。七C+* Debug Library?rDelag Aszsvtion Failed!、其血W?J&YCG4C81C33-沔干高汽多項？;旳乘法ap. cLtW 当 o /、 初八不 I歹2/3 4,1弟2 1、多项瓦t inExFtion on how yew ftcq5 cz. 4use q sserti 二 xil/ar乌 see the Visual CH dccui ex.iaii oxi 及 sser13.第2个多项亢匚正咚I重试成I SBSfD(?r&S3 fittrj* tn
13、 debu ite ejfli843lWU2现想把上图的输出中整数后的0去掉岀现下面的问题把 printf(H(%f*xA%d)+,q-data,q-indcx);改为 coiil”(”dataFAindex”)”+”九3忍是”、多项式的项数沱 入莓2多项式的顼敖泛年1个多顼式为系裁,指数以空裕分隅每一项:2 !*荤2个多项式的系规 悟数成空梧分同每一项”4.5,4節个多项式中共有2项.分别是:*第2个多项式中共有2 项,分别是: .腐测试的笫1沮数据的洁果为：*图7把上面的输出语句改为 coutvv”(”vvq-datavv”*xQvvq.indcxvv”)”； if(n!=0)(cout”+;n-;其中n为定义一个全局变量控制n的初值为两个多项式的项数 的乘积，每合并一次n-.由于加号总比多项式的项数少一，所以最后把n-1传给printO 通过语句if(n!=0)comvv”+”:n-.;控制“十”的输出。最终实现了正确的输出2. 心得体会1.1算法的时空分析：(1) 、算法的时间夏杂度
