一元稀疏多项式加法运算实验报告

稀疏多项式加法运算实验报告 本实验报告主要介绍了一元稀疏多项式加法运算的实验实现，包括需求分析、输入输出、测试数据、概要设计、详细设计等方面的内容。 一、需求分析 1.1 程序的主要功能： * 输入两个稀疏的一元 n 次多项式 * 计算两个多项式的和 * 输出和多项式 多项式相加的运算规则为： * 对于两个一元多项式中指数相同的子项，对应的系数相加，若和非零，将其构成和多项式中的一项 * 对于两个一元多项式中指数不同的子项，则分别复制到和多项式中 1.2 输入输出： * 输入要求：按照指数递增的顺序和指定的输入格式输入各个系数不为 0 的子项：“系数、指数对”，直至遇到输入结束标志（“系数、指数对”为“0、0”）的时候停止 * 输出多项式：输出形式为整数序列：n，c1,e1,c2,e2,………cn,en，其中 n 是多项式的项数，ci 和 ei 分别是第 i 项的系数和指数，序列按指数降序排列 二、概要设计 1. 建立一个头指针为 head、项数为 m 的一元多项式，建立新结点以接收数据，调用 Insert 函数插入结点 2. 本程序包括以下 4 个模板： * 主程序模块：main() * 建立链表：Polyn CreatePolyn(Polyn head,int m) * 多项式相加：Polyn AddPolyn(Polyn pa,Polyn pb) * 输出多项式：void PrintPolyn(Polyn P) 三、详细设计 1. 多项式的数据类型定义： typedef struct Polynomial{ float coef; //系数 int expn; //指数 struct Polynomial *next; }*Polyn,Polynomial; 2. 详细设计思路： 要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为序数 coef 指数 expn 指针域 next 运用尾插法建立两条单链表，以单链表 polyn p 和 polyn h 分别表示两个一元多项式 a 和 b，a+b 的求和运算等同于单链表的插入问题（将单链表 polyn p 中的结点插入到单链表 polyn h 中），因此“和多项式”中的结点无须另生成。 为了实现处理，设 p、q 分别指向单链表 polya 和 polyb 的当前项，比较 p、q 结点的指数项，由此得到下列运算规则： ① 若 p->expn<q->expn，则结点 p 所指的结点应是“和多项式”中的一项，令指针 p 指向下一结点 ② 若 p->expn==q->expn，则结点 p 和结点 q 的系数相加，若和非零，将其构成和多项式中的一项 ③ 若 p->expn>q->expn，则结点 q 所指的结点应是“和多项式”中的一项，令指针 q 指向下一结点 通过以上设计，我们可以实现一元稀疏多项式加法运算的实验报告。