给定稀疏多项式P和Q，设计实现多项式求和的算法。要求：

（1）将结果放入多项式P之中，

（2）不允许使用链表，

（3）设计2种不同的算法，并分析两种算法的时间和空间复杂性。

 

方法1：

 1 #include <stdio.h>
 2 struct poly{            /*构建结构体，含有系数coeff和幂数expo*/ 
 3     int coeff;
 4     int expo;
 5 };
 6 int readPoly(struct poly p[10]);
 7 int addPoly(struct poly p1[],struct poly p2[],int t1,int t2,struct poly p3[]);
 8 void displayPoly(struct poly p3[],int t3);
 9 struct poly p1[10],p2[10],p3[20];
10 
11 int main(int argc, char *argv[])
12 {
13     int     t1,t2,t3;
14     t1 = readPoly(p1);
15         displayPoly(p1,t1);
16     t2 = readPoly(p2);
17         displayPoly(p2,t2);    
18     t3 =  addPoly(p1,p2,t1,t2,p3);
19         printf(" \n\n Resultant polynomial after addition: ");
20         displayPoly(p3,t3);
21     return 0;
22 }
23 
24 int readPoly(struct poly p[10])
25 {
26     int i=0, t;
27     printf("Please input the total number of terms in the polynomialt_%d:\n",++i);
28     scanf ("%d",&t);                    //输入多项式的项数 
29     for   (i=0; i<t; i++)
30     {
31         printf("Please input the Coefficient%d :",i+1);
32         scanf ("%d",&p[i].coeff);        //输入多项式某项的系数coeff 
33         printf("Please input the Exponent%d :",    i+1);
34         scanf ("%d",&p[i].expo);        //输入多项式某项的幂数expo 
35     }
36     return t;                            //返回该多项式的项数  = 数组长度 
37 }
38 
39 int addPoly(struct poly p1[],struct poly p2[],int t1,int t2,struct poly p3[])
40 {
41     int i=0, j=0, k=0;
42     while(i<t1 && j<t2)                    //按照幂数expo从低到高，合并两个多项式 
43     {
44         if        (p1[i].expo == p2[j].expo)
45         {
46             p3[k].expo    = p1[i].expo;
47             p3[k++].coeff = p1[i++].coeff + p2[j++].coeff;
48         }
49         else if (p1[i].expo <  p2[j].expo)
50         {
51             p3[k].coeff  = p1[i].coeff;
52             p3[k++].expo = p1[i++].expo;
53         }
54         else
55         {
56             p3[k].coeff  = p2[j].coeff;
57             p3[k++].expo = p2[j++].expo;
58             
59         }
60     }
61     while(i < t1)                      //合并剩余多项式。此时struct poly p1[]的项数更多 
62     {
63         p3[k].coeff  = p1[i].coeff;
64         p3[k++].expo = p1[i++].expo;        
65     }
66     while (j < t2)                     //合并剩余多项式。此时struct poly p2[]的项数更多 
67     {
68         p3[k].coeff  = p2[j].coeff;
69         p3[k++].expo = p2[j++].expo;
70     }
71     return k;                        //返回合并的多项式项数  = 数组长度 
72 }
73 
74 void displayPoly(struct poly p3[],int t3)         //输出多项式的表达式 
75 {
76     int k;
77     for(k=0; k<t3; k++)
78         printf("%d(x^%d)+",p3[k].coeff,p3[k].expo);
79     printf("\b \n");
80 }