测试一 一元稀疏多项式的计算测试一 一元稀疏多项式的计算.pdfVIP

2 实验一 一元稀疏多项式的计算 一、实验目的 通过一元稀疏多项式的表示和计算，帮助学生熟练掌握线性表的基本操作，以及用线性 链表表示线性表的存储结构和操作的实现。 二、实验内容 实现一元稀疏多项式的如下运算： (1)两个一元稀疏多项式相加运算 (2)两个一元稀疏多项式相减运算 (3)两个一元稀疏多项式相乘运算 三、实验原理 1、一元多项式的逻辑表示 一元多项式 p (x)可表示成: n 2 n p (x)=p +p x+p x + …+p x n 0 1 2 n n+1 个系数可用线性表来表示： p ，p ，p ，…，p ） 0 1 2 n 其中每一项的指数 i 隐含在其系数pi 的序号中。 一个一元多项式，如果其系数不为 0 的项相对于其多项式的次数（最大指数）而言要少 得多，则称该一元多项式为一元稀疏多项式。 对一元稀疏多项式，若采用顺序存储结构，需 n+1 个元素单元存放系数。当 n 很大且为 零的系数较多时，既浪费存储空间，又浪费运算时间。如： 10000 20000 s(x)=1+3x +2x 采用顺序存储分配需 20001 个元素空间，但只有 3 个元素有意义。若参与同数量级的加 法运算，要运行 2000 次以上。因此，对一元多项式采用链式存储结构是必然的选择。上例的 链表表示形式如图 1-1 所示。 p 1 0 3 1000 2 2000 ٨ 图 1-1：一元稀疏多项式的链表表示示意图 2、一元稀疏多项式的链式存储表示 结点结构定义如下： typedef struct Item{ double coef; 3 int expn; struct Item *next; }Item,*Polyn; 3、一元稀疏多项式运算原理 设有两个稀疏多项式 A 和 B ，其运算原理如下： （1）两个多项式相加(C=A＋B) 的运算原则： 指数相同，系数相加，若不为 0，则在结果多项式中构成一新项。 指数不同，则两项分别抄入结果多项式中。 （2 ）两个多项式相减(C=A －B) 的运算原则： 指数相同，系数相减，若不为 0，则构成一新项。 指数不同，对 A 多项式的项，直接抄入结果多项式中。 对 B 多项式的项，系数符号变换后，再将放入结果多项式中 （3 ）两个多项式相乘(C=A ×B) 的运算原则 用 B 多项式的每一项分别去乘 A 多项式的每一项，并将乘得得结果放入结果 多项式中。 若结果多项式中有指数相同的项，则应把它们合并为一项。 四、实现 1、约定使用带头结点的链表表示一元稀疏多项式。 （2 ） 用线性链表表示的一元稀疏多项式中，各结点按指数的升序排列。 （3 ） 每个多项式都独立存在，即参与运算的两个多项式的数据不能因运算而受到破坏， 加、减、乘运算的结果应相互不受影响。因此，对于每种情况都必须单独建立一个链表进行 表示。 （4 ） 每一种重复性的操作都要进行确认，以免破坏原有操作的结果。如需要输入 A 多 项式，而 A 多项式已经存在，这时通过“确认”后再确定是否真正需要