一元多项式的表示及相加一元多项式抽象数据类型的动态链式表示操作举例：构造多项式

一元多项式的表示及相加

符号多项式的表示及其操作是线性表处理的典型用例。 一个一元多项式 Pn(x) 可以表示为 ： P_n(x)=p₀+p₁x+p₂x²+…+p_nxⁿ (最多有 n+1 项)它由 n+1 个系数唯一确定。

因此可用一个线性表 P 来表示：P = ( p₀, p₁, p₂, …, p_n ) 每一项的指数 i 隐含在其系数 pi 的序号里。

假设 Qm(x) 是一元 m 次多项式，同样可用线性表 Q 表示： Q = (q₀, q₁, q₂, …, q_m）

若 m < n，则两个多项式相加的结果 R_n(x)= P_n(x)+ Q_m(x) 可用线性表 R 来表示： R = (p₀+ q₀, p₁+ q₁, p₂+q₂, …, p_m+ q_m, p_m+1, …, p_n）

但是只存储系数的方案对存在大量零系数的多项式并不适用。

例如： S(x) = 1 + 3x¹⁰⁰⁰⁰ + 2x²⁰⁰⁰⁰

要用一个长度为 20001 的线性表来表示，表中仅有 3 个非零系数，会浪费大量存储空间。

若只存储非零系数项，则必须同时存储相应的指数。

一般一元 n 次多项式 (只表示非零系数项) 可写成：

其中 p_i≠0 (i =1, 2, …, m)，n = e_m > e_m-1 > … > e₁ >= 0

用一个长度为 m 且每个数据元素有两个数据项（系数项和指数项）的线性表 (( p₁, e₁), ( p₂, e₂), …, ( p_m, e_m)) 便可唯一确定多项式 P_n(x)。 对于 S(x) 类的多项式将大大节省空间。

所以这里我们选择链式存储结构。

例：假设多项式 A₁₇(x)=7+3x+9x⁸+5x¹⁷ 与 B₈(x)=8x+22x⁷-9x⁸ 已经用单链表表示，其头指针分别为 A 与 B， 如下图所示。

将两个多项式相加为 C₁₇(x)=7+11x+22x⁷+5x¹⁷

一元多项式抽象数据类型的动态链式表示

typedef struct{ float coef; //系数 int exp; //指数 }term, ElemType; typedef LinkList Polynomal; Polynomal pl;

操作举例：构造多项式

void CreatePolyn(Polynomal &p,int m) { //构建一个有序链表p，其中元素为结构体，有m个元素 InitList(p); h=p; e.coef=0.0; e.expn=-1; SetCurElem(h,e);//设置头节点的数据元素 for(i=1;i<m+1;i++) { //向结构体变量e中输入系数和指数 if(!LocateElem(p,e,q,(*cmp)())) { if(MakeNode(s,e)) //生成节点s;s是指针变量 InsFirst(q,s); //将s节点插在q节点之前 } } }