1 一元多项式的表示
一元多项式 p(x)=p0+p1x+p2x2+ … +pnxn ，由n+1个系数唯一确定。
则在计算机中可用线性表(p0 ，p1 ，p2 ，… ，pn )表示。
既然是线性表，就可以用顺序表和链表来实现。两种不同实现方式的元素类型定义如下
1 (1)顺序存储表示的类型
2 typedef struct
3 { float coef; /*系数部分*/
4 int expn; /*指数部分*/
5 } ElemType ;
6
7
8
9 (2)链式存储表示的类型
10 typedef struct ploy
11 { float coef ; /*系数部分*/
12 int expn ; /*指数部分*/
13 struct ploy *next ;
14 } Ploy ;
2 一元多项式的相加
不失一般性，设有两个一元多项式： P(x)=p0+p1x+p2x2+ … +pnxn ，
Q(x)=q0+q1x+q2x2+ … +qmxm (m<n) R(x)=P(x)+ Q(x) R(x)
由线性表R((p0+q0) ，(p1+q1) ，(p2+q2) ， … ，(pm+qm) ， … ， pn)唯一表示。
⑴ 顺序存储表示的相加 线性表的定义
1 typedef struct
2 { ElemType a[MAX_SIZE] ;
3 int length ;
4 }Sqlist ;
用顺序表示的相加非常简单。
访问第5项可直接访问：L.a[4].coef ， L.a[4].expn (2) 链式存储表示的相加
(2) 链式存储表示的相加
当采用链式存储表示时，根据结点类型定义，
凡是系数为0的项不在链表中出现，从而可以大大减少链表的长度。
一元多项式相加的实质是：
指数不同： 是链表的合并。
指数相同： 系数相加，和为0，去掉结点，和不为0，修改结点的系数域。
算法之一： 就在原来两个多项式链表的基础上进行相加，相加后原来两个多项式链表就不在存在。
当然再要对原来两个多项式进行其它操作就不允许了。
1 算法描述
2 Ploy *add_ploy(ploy *La， ploy *Lb)
3 /* 将以La ，Lb为头指针表示的一元多项式相加 */
4 { ploy *Lc , *pc , *pa , *pb ,*ptr ; float x ;
5 Lc=pc=La ; pa=La->next ; pb=Lb->next ;
6 while (pa!=NULL&&pb!=NULL)
7 { if (pa->expn<pb->expn)
8 { pc->next=pa ; pc=pa ; pa=pa->next ; }
9 /* 将pa所指的结点合并，pa指向下一个结点 */
10 if (pa->expn>pb->expn)
11 { pc->next=pb ; pc=pb ; pb=pb->next ; }
12 /* 将pb所指的结点合并，pb指向下一个结点 */
13 else
14 { x=pa->coef+pb->coef ;
15 if (abs(x)<=1.0e-6)
16 /* 如果系数和为0，删除两个结点 */
17 { ptr=pa ; pa=pa->next ; free(ptr) ;
18 ptr=pb ; pb=pb->next ; free(ptr) ; }
19 else /* 如果系数和不为0，修改其中一个结点的系数域，删除另一个结点 */
20 { pc->next=pa ; pa->coef=x ;
21 pc=pa ; pa=pa->next ;
22 ptr=pb ; pb=pb->next ; free(pb) ;
23 }
24 }
25 } /* end of while */
26 if (pa==NULL) pc->next=pb ;
27 else pc->next=pa ;
28 return (Lc) ;
29 }
算法之二：
对两个多项式链表进行相加，生成一个新的相加后的结果多项式链表，
原来两个多项式链表依然存在，不发生任何改变，如果要再对原来两个多项式进行其它操作也不影响。
1 算法描述
2 Ploy *add_ploy(ploy *La， ploy *Lb)
3 /* 将以La ，Lb为头指针表示的一元多项式相加，生成一个新的结果多项式 */
4 { ploy *Lc , *pc , *pa , *pb , *p ; float x ;
5 Lc=pc=(ploy *)malloc(sizeof(ploy)) ;
6 pa=La->next ; pb=Lb->next ;
7 while (pa!=NULL&&pb!=NULL)
8 { if (pa->expn<pb->expn)
9 { p=(ploy *)malloc(sizeof(ploy)) ;
10 p->coef=pa->coef ; p->expn=pa->expn ;
11 p->next=NULL ;
12 /* 生成一个新的结果结点并赋值 */
13 pc->next=p ; pc=p ; pa=pa->next ;
14 }
15 /* 生成的结点插入到结果链表的最后，pa指向下一个结点 */
16 if (pa->expn>pb->expn)
17 { p=(ploy *)malloc(sizeof(ploy)) ;
18 p->coef=pb->coef ; p->expn=pb->expn ;
19 p->next=NULL ;
20 /* 生成一个新的结果结点并赋值 */
21 pc->next=p ; pc=p ; pb=pb->next ;
22 } /* 生成的结点插入到结果链表的最后，pb指向下一个结点 */
23 if (pa->expn==pb->expn)
24 { x=pa->coef+pb->coef ;
25 if (abs(x)<=1.0e-6)
26 /* 系数和为0，pa, pb分别直接后继结点 */
27 { pa=pa->next ; pb=pb->next ; }
28 else /* 若系数和不为0，生成的结点插入到结果链表的最后， pa, pb分别直接后继结点 */
29 { p=(ploy *)malloc(sizeof(ploy)) ;
30 p->coef=x ; p->expn=pb->expn ;
31 p->next=NULL ;
32 /* 生成一个新的结果结点并赋值 */
33 pc->next=p ; pc=p ;
34 pa=pa->next ; pb=pb->next ;
35 }
36 }
37 } /* end of while */
38 if (pb!=NULL)
39 while(pb!=NULL)
40 { p=(ploy *)malloc(sizeof(ploy)) ;
41 p->coef=pb->coef ; p->expn=pb->expn ;
42 p->next=NULL ;
43 /* 生成一个新的结果结点并赋值 */
44 pc->next=p ; pc=p ; pb=pb->next ;
45 }
46 if (pa!=NULL)
47 while(pa!=NULL)
48 { p=(ploy *)malloc(sizeof(ploy)) ;
49 p->coef=pb->coef ; p->expn=pa->expn ;
50 p->next=NULL ;
51 /* 生成一个新的结果结点并赋值 */
52 pc->next=p ; pc=p ; pa=pa->next ;
53 }
54 return (Lc) ;
55 }