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 }