1、 题目题目: :一元多项式的一元多项式的 计算计算 班级班级 _软件软件 11021102_ 姓名姓名 _ _ 学号学号 _ _ 一元多项式的加减一元多项式的加减 一一实验课题：运用数据结构的知识编写一实验课题：运用数据结构的知识编写一 个程序， 要求此程序能够进行个程序， 要求此程序能够进行 2 2 个一元多项个一元多项 式的加减，并将答案输出在屏幕上式的加减，并将答案输出在屏幕上。 二二. .问题分析：一元多项式可以看做是问题分析：一元多项式可以看做是 n n 个个 元素的相加， 而这元素的相加， 而这 n n 个元素的唯一差别就在个元素的唯一差别就在 于系数和指数，运用数据结构的知识可以
2、通于系数和指数，运用数据结构的知识可以通 过将过将2 2个一元多项式的系数和指数分别存储个一元多项式的系数和指数分别存储 在在 2 2 个线性表中， 然后个线性表中， 然后通过线性表的检索比通过线性表的检索比 较指数，若指数相同就将系数相加，将结果较指数，若指数相同就将系数相加，将结果 存储在另一个线性表中。存储在另一个线性表中。 三三 . . 程 序 运 行 环 境 ：程 序 运 行 环 境 ： Microsoft Visual Microsoft Visual StudioStudio 四：概要设计四：概要设计 存储结构：存储结构： 一元多项式的表示在计算机内可以用链表来表示， 为了节省存
3、储空间， 只存储多项式中系数非零的项。 链表中的每一个结点存放多项式的一个系数非零 项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的 指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行 分析，实现一元多项式的相加、相减操作。 1 单连表的抽象数据类型定义： ADT List 数据对象：D=ai|aiElemSet,i=1,2,n,n0 数据关系： R1=| ai-1, aiD,i=2,n 基本操作： InitList（L） /操作结果：构造一个空的线性表 CreatPolyn( void InitList(LinkList LNode *L1,*L2;
4、 Polyn(L1,L2); 2.1 加，减操作模块实现加减操作 各模块之间的调用关系如下： 主程序模块 加法操作模块 减法操作模块 基本算法：基本算法： 1、输入输出 （1）功能：将要进行运算的多项式输入输出。 （2）数据流入：要输入的多项式的系数与指数。 （3）数据流出：合并同类项后的多项式。 （4）程序流程图：多项式输入流程图如图 1 所示。 （5）测试要点：输入的多项式是否正确，若输入错误则重新输入 用户菜单 多项式链表 各函数 退出 指针数组 主函数 开始 申请结点空间 输入多项式的项数 输入多项式各项的系数 x, 指数 y 输出已输入的多项式 合并同类项 结束 否 是 是否输入正确
5、 图表 1 2、多项式的加法 （1）功能：将两多项式相加。 （2）数据流入：输入函数。 （3）数据流出：多项式相加后的结果。 （4）程序流程图：多项式的加法流程图如图 2 所示。 （5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运 算。 图表 2 开始 定义存储结果的空链 r r 是 否 输出存储多项式的和的链 r 结束 是 否 同指数项系数相加后存入 r 直接把 p 中 各项存入 r 直接把 q 中 各项存入 r 存储多项式2的空 链 Q 是否为空 存储多项式 1 的空 链 P 是否为空 合并同类项 3、多项式的减法 （1）功能：将两多项式相减。 （2）数据流入：调用输入函数
6、。 （3）数据流出：多项式相减后的结果。 （4）程序流程图：多项式的减法流程图如图 3 所示。 （5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运 算。 开始 定义存储结果的空链 r r 是 否 输出存储多项式的和的链 r 结束 是 否 同指数项系数相加后存入 r 把 p 中各项系数 改变符号后存入 直接把 q 中 各项存入 r 存储多项式2的空 链 Q 是否为空 存储多项式 1 的空 链 P 是否为空 合并同类项 图表 3 五. 调试分析 采用单连表形式按照指数降序排列建立并输出多项式；在相加，相减的过 程 中如果指数相同就执行系数相加，相减，否则就把大的项直接写入。完成两 个多 项式的相加、相减;将从新得到的单连表结果输出；该算法的时间复杂度为 两个 多项式的项式之和 六：调试结果六：调试结果 1. 测试的数据及结果 相乘： 相加： 相减：
