设计程序以实现任意两个高次多项式的加法和乘法运算.doc

王帆 《用设计程序以实现任意两个高次多项式的加法和乘法运算》 第 PAGE ２页 共34页 PAGE 设计程序以实现任意两个高次多项式的加法和乘法运算 学生姓名：王帆 指导老师：张建明 摘 要 本课程设计主要解决任意两个高次多项式的乘法运算。所设计的数据结构应尽可能节省存储空间，程序的运行时间应尽可能少。从题目看出所设计的程序应能达到的功能，设计好的程序要满足以上两点。在数据输入方面可以根据一元高次多项式的特征，从左到右开始，按每一项指数、系数的顺序输入。这里要留意一个问题，因为要相乘的多项式项数是未知的，所以选择什么样的存储方式在本课程设计中尤为重要，这也是本程序好坏的一个评定。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在商业中解决实际问题。 关键词 高次多项式；加法；乘法；时间复杂度；空间复杂度 1 问题分析和任务定义 1.1 任务定义 设计程序以实现任意两个高次多项式的乘法运算。 要求： （1）所设计的数据结构应尽可能节省存储空间。（2）程序的运行时间应尽可能少。 从题目看出所设计的程序应能达到的功能，设计好的程序要满足以上两点。在数据输入方面可以根据一元高次多项式的特征，从左到右开始，按每一项指数、系数的顺序输入。这里要留意一个问题，因为要相乘的多项式项数是未知的，所以选择什么样的存储方式在 课程设计中尤为重要，这也是本程序好坏的一个评定。 设计算法（程序）测试用例： 图1-1 图1-2 图1-1 为正确的输出结果，图1-2 为错误的输出结果 1.2 要解决的问题 （1） 怎样实现两个多项式的乘法？ （2） 相乘后若有指数相同的项用什么方法合并？ （3） 使用什么数据结构来满足尽可能节省存储空间的要求？ （4） 用什么方法来输出表达式？ 2概要设计和数据结构的选择 2.1 数据结构的选择 本程序选择的数据结构是单链表，原因如下： 链表的定义： （1） 链表是有限个具有相同数据类型的数据元素的集合，D={ai/i=1,2,…，n};ai为数据元素。 （2） 数据元素之间的关系R={ai,ai+1/ai,ai+1∈D}。 （3） 数据元素ai 在存储器中占用任意的、连续或不连续的物理存储区域。 动态链表： 当需要插入数据元素时，临时动态地为其申请一个存储空间，而不是将结点放在一个定义的数组中，删除数据元素时，可以释放该数据元素所占用的空间，即可以根据表的实际需要临时动态的分配存储空间以存储表中的数据元素。 单链表是有限个具有相同数据类型的数据元素组成的链表且该链表的每一个结点只有一个指针域。带头结点的单链表是在单链表的第一个结点之前加一个同类型的结点，目的是为了使链表有一致的描述。 本程序解决的是两多项式相乘的问题，多项式的项数本身就是不确定的，而且相乘后的多项式可能含有指数相同的问题，这时就需要合并，合并后其中的一项就没有用了需要删除，不然就浪费内存空间。基于以上几点所以采用了链表。 链表具有动态生成，灵活添加或删除结点的特点，尽可能节省存储空间。 2.2 结构图 图2-1 图2-1 即为本程序的结构图 2.3 下面是针对本程序专门定义的数据结构类型 结点的数据类型如下： typedef struct Pnode{ int coef; //系数指针 int exp; //指数指针 struct Pnode*next; }polynode; 数据结构的设计思想： 链表中的每一个结点存放多项式的一个系数非0 项。它包含三个域,分别存放放该项的系数、指数以及指向下一个多项式结点的指针。 如图2-2 所示为多项式链表结点的结构。 系数 指数 指针 图2-2 例如2-3 所示，多项式的单链表表示如下 图2-3 2.4 流程图 图2-4 图2-4为主函数的流程图 图2-5 图2-5为plcreate 多项式链表生成函数的流程图 图2-6 图2-6为置空函数流程图 图2-7 图2-7为output 输出多项式函数的流程图 图2-8 图2-8 为多项式相乘函数流程图 图2-9 图2-9 为合并指数相同项函数的流程图 2.5 各程序模块之间的层次（调用）关系 在执行主函数时先调用plcreate 生成要相乘的多项式