两一元高次多项式的乘法.doc

Xx学院 《数据结构与算法》课程设计 报 告 书  课程设计题目 实现任意两个一元高次多项式的乘法运算 院系名称计算机科学与技术系 专 业 （班 级） 姓 名 （学 号） 指 导 教 师 完 成 时 间 【课题】设计程序以实现任意两个高次多项式的乘法运算。 【要求】〈1〉所设计的数据结构应尽可能节省空间。〈2〉程序的运行时间尽可能少 一、问题分析和任务定义： 1.问题描述： 根据对本次设计课题的理解：实现是任意两个高次多项式相乘，可以是一元也可以是多元，在本次设计中针对的是对两个一元高次多项式的相乘。首先高次多项式可以出现两次到多次及两项到多项的多种不同情况；其次存储空间和程序运行时间是矛盾的，必须从中找到最合理的算法使得程序存储空间及运行时间都相对较少。 2.输入、输出的形式. 输入多项式时应注意该元之前的数字为系数，其后数字为指数，本程序按提示采用的人机对话的形式输入每一项的系数（实数型）和指数（整型） 输出时是以数学表达式的形式输出，如输出相乘后的结（4.3*X^5）+(-13*X^-3) 3.算法（程序）所能达到的功能 ①多项式的建立 ②多项式的相乘 ③合并同类项 ④ 对合并后的多项式按降幂排序 ⑤输出最终多项式表达 ⑥释放内存 4.测试用的数据（注：以下enter代表回车换行） 输入两个多项式并相乘：(x+2.5x2+3x3)*(-4x4+5x5) 输出相乘后的结果：12.5X7-5X6-4X5+15X2-12X1 在程序中的输入： 2 enter 1 enter 1 enter 2.5 enter 2 enter 3 enter -3 enter -4 enter 4 enter 5 enter 5 enter 1 enter 1 enter 1.6 enter -5 enter 86 enter 3 enter 在程序中的输出： (12.5*x^7)+(-5*x^6)+(-4*x^5)+(15*x^2) +(-12*x^1) 二、概要设计和数据结构的选择 根据对本课题的理解，线性表是一个很好的选择。而线性表有两种可选的存储表示方式，顺序表和链表。考虑到课题要求：所设计的数据结构应尽可能节省空间。若采用顺序存储，需事先分配足够的空间，造成内存空间的浪费；而用链接存储，动态创建新结点以存储多项式的项，就简单的多。所以本设计采用的数据结构是链表。 算法（程序）中用到的所有各种数据类型的定义 本程序设计用到一中结构体和若干中变量的定义如下： 1.1 用单链表存储多项式的结点： struct List { float data; //系数 int index; //指数 struct List *next; };//多项式项的数据类型定义 1.2 其它主要变量的定义： int testNum; //测试数据的组数 int LA_Num,LB_Num; //多项式A，B中的项数 struct List *la,*lb; //定义两个链表，分别表示要相加的两个多项式中的项 struct List *pa,*pb=NULL;//pa指向存放相乘后的结果 ，pb为空指针指向合并同类项后的结果 struct List *result; //指向合并同类项后按降幂排序后的结果 2.程序流程图 流程图说明： 先定义变量并初始相关变量 输入测试数据的组数 分配两多项式的存储空间 调用inputData()建立多项式 A不为空时执行相乘 如果A、B只有一项无须合并直接跳到⑧ 否则要进行合并同类项，排序合并后的结果 输出排序后的结果(释放内存(如果循环次数不大于测试数据组数，跳到④进行下一组测试数据 图1.流程图 3．程序主要（调用）关系： 图2.函数调用图 各函数的功能如下： inputData() 功能： 完成多项式建立，如输入系数，指数的输入都在此函数中完成。 LaAndLb() 功能： 完成la中的某项分别与lb中的每一项相乘。 PaAndPb() 功能： 完成把相乘后的结果进行合并同类项。 Order() 功能： 完成最终合并后的结果按