描述：
对于两个一元多项式，如果需要对他们进行多项式相加操作，常见的两种思路如下：(1)对于一个多项式，保存其最高项次数HighPowder，以及一个该多项式对应次数分别为0-HighPowder的各项的系数的数组()。(2)多项式中系数不为零的每一项，保存其系数与该项的次数。下面分别用这两种思路实现一元多项式加法操作。
思路一（数组实现）：
数据结构定义：
1 typedef struct Poly
2 {
3 int CoeffArray[11];
4 int HighPower;
5 } *Polynomial;
实现：
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 typedef struct Poly
5 {
6 int CoeffArray[11];
7 int HighPower;
8 } *Polynomial;
9
10 void ZeroPolynomial(Polynomial Poly)
11 {
12 int i;
13 for(i = 0; i < 11; i++)
14 {
15 Poly->CoeffArray[i] = 0;
16 }
17 Poly->HighPower = 0;
18 }
19
20 void AddPolynomial(Polynomial Poly1,Polynomial Poly2, Polynomial PolySum)
21 {
22 int i;
23 ZeroPolynomial(PolySum);
24 PolySum->HighPower = Poly1->HighPower > Poly2->HighPower?
25 Poly1->HighPower:Poly2->HighPower;
26 for(i = PolySum->HighPower; i >= 0 ; i--)
27 {
28 PolySum->CoeffArray[i] = Poly1->CoeffArray[i] + Poly2->CoeffArray[i];
29 }
30 }
31
32 int main(void)
33 {
34 int i,j,k;
35 Polynomial P1,P2,Sum;
36 P1 = malloc(sizeof(struct Poly));
37 P2 = malloc(sizeof(struct Poly));
38 Sum = malloc(sizeof(struct Poly));
39 //初始化
40 ZeroPolynomial(P1);
41 ZeroPolynomial(P2);
42 P1->HighPower = 10;
43 for(i = 10; i >= 0; i--)
44 {
45 P1->CoeffArray[i] = i;
46 }
47
48 P2->HighPower = 8;
49 for(j = 8; j >=0; j--)
50 {
51 P2->CoeffArray[j] = j;
52 }
53 P2->CoeffArray[8] = 8;
54 AddPolynomial(P1,P2,Sum);
55
56 printf("The high power of the Polynomial is %d
",Sum->HighPower);
57 for(k = 0; k <= 10; k++)
58 {
59 printf("The Coeff of power %d is %d
",k,Sum->CoeffArray[k]);
60 }
61
62 return 0;
63 }
它适合大部分项都有的稠密多项式。
思路二（单链表实现）：
数据结构定义：
1 typedef struct PolyNode *PtrToNode;
2
3 //定义链表节点，也就是多项式中的某一项；
4 typedef struct PolyNode
5 {
6 int Coeff;
7 int Exponent;
8 PtrToNode Next;
9 } PolyNode;
实现：
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 typedef struct PolyNode *PtrToNode;
5
6 //定义链表节点，也就是多项式中的某一项；
7 typedef struct PolyNode
8 {
9 int Coeff;
10 int Exponent;
11 PtrToNode Next;
12 } PolyNode;
13
14
15 typedef PtrToNode Polynomial;
16
17 /************************************************************
18 *多项式相加的函数:
19 *P、Q为存储两个多项式各项的单链表(含头结点)
20 *Sum为多项式相加结果存放的单链表
21 *
22 ************************************************************/
23 void AddPolynomial(Polynomial P,Polynomial Q,Polynomial Sum)
24 {
25 Polynomial PIndex,QIndex,SumIndex;
26 PIndex = P->Next;
27 QIndex = Q->Next;
28 SumIndex = Sum;
29 while(!(PIndex == NULL && QIndex == NULL))
30 {
31 if(PIndex==NULL)
32 {
33 SumIndex->Next = QIndex;
34 QIndex = QIndex->Next;
35 SumIndex = SumIndex->Next;
36 }
37 else if(QIndex == NULL)
38 {
39 SumIndex->Next = PIndex;
40 PIndex = PIndex->Next;
41 SumIndex = SumIndex->Next;
42 }
43 else
44 {
45 if(PIndex->Exponent > QIndex->Exponent)
46 {
47 SumIndex->Next = PIndex;
48 PIndex = PIndex->Next;
49 SumIndex = SumIndex->Next;
50 //continue在判断下面if条件时会有异常，类似Java
51 //的空引用异常
52 continue;
53 }
54 if(PIndex->Exponent == QIndex->Exponent)
55 {
56 Polynomial PP = malloc(sizeof(struct PolyNode));
57 PP->Exponent = PIndex->Exponent;
58 PP->Coeff = PIndex->Coeff + QIndex->Coeff;
59 SumIndex->Next = PP;
60 PIndex = PIndex->Next;
61 QIndex = QIndex->Next;
62 SumIndex = SumIndex->Next;
63 continue;
64 }
65 if(PIndex->Exponent < QIndex->Exponent)
66 {
67 SumIndex->Next = QIndex;
68 QIndex = QIndex->Next;
69 SumIndex = SumIndex->Next;
70 continue;
71 }
72 }
73 }
74 SumIndex->Next = NULL;
75 }
76
77 /************************************************************
78 *遍历单链表(含头结点)函数:
79 *P：待遍历的链表
80 *************************************************************/
81 void TraversePolynomial(Polynomial P)
82 {
83 Polynomial Tmp = P->Next;
84 while(Tmp != NULL)
85 {
86 printf("Coeff is %d and Exponent is %d
",Tmp->Coeff,Tmp->Exponent);
87 Tmp = Tmp->Next;
88 }
89 }
90
91
92
93 int main(void)
94 {
95 Polynomial Poly1,Poly2,Poly3,Poly11,Poly22;
96 int i,j;
97 Poly1 = malloc(sizeof(struct PolyNode));
98 Poly2 = malloc(sizeof(struct PolyNode));
99 Poly3 = malloc(sizeof(struct PolyNode));
100 Poly11 = Poly1;
101 Poly22 = Poly2;
102
103 //创建两个链表时，需要保证是按照指数递减的方式构造的
104 for(i = 5;i >= 1;i--)
105 {
106 Polynomial Tmp = malloc(sizeof(struct PolyNode));
107 Tmp->Coeff = i;
108 Tmp->Exponent = i;
109 Poly11->Next = Tmp;
110 Poly11 = Poly11->Next;
111 }
112 Poly11->Next = NULL;
113 for(j = 11;j >= 3;j--)
114 {
115 Polynomial Tmp = malloc(sizeof(struct PolyNode));
116 Tmp->Coeff = j;
117 Tmp->Exponent = j;
118 Poly22->Next = Tmp;
119 Poly22 = Poly22->Next;
120 }
121 Poly22->Next = NULL;
122 TraversePolynomial(Poly1);
123 printf("*****************************************
");
124 TraversePolynomial(Poly2);
125 AddPolynomial(Poly1,Poly2,Poly3);
126 printf("*****************************************
");
127 TraversePolynomial(Poly3);
128 return 0;
129 }