一道 google曾出过的笔试题：编程实现对数学一元多项式的相加和相乘操作

转自：http://www.cnblogs.com/kubixuesheng/p/4084095.html

数学中一元n次多项式可表示成如下的形式：

Pn(x)=p0+p1x+p2x^2+…+pnx^n (最多有 n+1 项，n +1 个系数唯一确定她)

　　(1)请设计一套接口用以表示和操作一元多项式

　　(2)根据上述设计实现一元n次多项式的加法运算

　　(3)根据上述设计实现一元n次多项式的乘法运算

分析：

题目大概意思：

数学里常见的一元 n 次表达式，设计出加减乘除的函数（方法），同时提供对外接口，把内部实现封装起来，而 n 的大小没有指定。

问题的本质：

就是一系列的单个未知数 x，指数和系数数字p（i）,0 =< i <= n组成的长串的表达式，然后把长长的表达式进行数学运算，假发和乘法，那么立马想到，这里需要线性表这个数据结构，符号多项式的表示和操作是线性表处理的典型用例。且有变量 N，那么自然会联系到范围问题。

解决思路：

对问题进行进一步分解，常用的线性表，无非就是链表和顺序表，又分静态和动态内存分配的。数学的一元多项式，用一个线性表 P 来表示：P = ( p0, p1, p2, …, pn )

每一项，x的指数隐含在其系数 p（i）的下标i里。这样的话，只是存储系数就 ok了，未知数 x 的指数让系数下标标识。比较简单是用数组（静态顺序表存储），那么问题来了……

存储空间不够了怎么办?

显然，可以使用动态线性表，这样，伸缩自如！再也不担心不够存储了！继续分析，这样解决了空间大小的问题（有限范围内的内存），剩下的就是设计计算的算法，联想中学时代的算数，多项式并不是每一个项都必须写出来的，那么问题来了……

如果 p 里含有大量的0怎么办？

显然这样的存储结构也不太好，会大量浪费内存。比如 p=1 + 7x^12000，要用一个长度为 12001 的线性表来表示，表中仅有两个非零系数，会浪费大量存储空间。不划算。需要改变策略，首先一个原则就是：系数=0不存储！那么自然是只存储非0系数，而指数就必须同时也要存储！否则无法标识指数。其实，日常生活里，也是这样的，一个数学或者物理化学的公式，表达式，系数为0的项，没人会把它写出来吧？！而且这样的多项式数序上叫稀疏多项式。

最终，确定使用链表来存储，因为，系数为0的项，经过计算，可能变为非0，相反非0的项经过计算，也可能变味0，必然要用到删除和插入算法，那么显然链表还是最佳的表示方法，效率比较高，不用大量移动元素，且可以动态增长。节省存储空间。

定义 ADT三要素：数据对象，数据关系，数据操作

PS:其实还是面向对象表达 ADT 比较好，当然 c 也完全 ok，个人 c++不是很融汇贯通，高级的语法和特性不敢乱用，免得班门弄斧，贻笑大方……不使用高级特性和复杂语法的话，cpp就索然无味，索性一直用纯真的 c 来练习一些东西，因为这样更好的把重点放到算法和工程问题本身，而不是复杂庞大的 c++语言的枝端末节上，c++还是比 c 多了很多复杂繁琐的东西（这里又想到了一道奇葩的问题——如何用 c 实现面向对象？）

google 的这个问题充分暴露了本人c++功底不过关， c++求解实现的过程因为使用的是类模版，函数模版，继承，和输入输出等的运算符重载，导致程序代码较多，且出现了很多错误，考虑编码练习和算法设计，重点学习的是思想和方法，还是用c写，c++的巩固和加强完全可以放到其他闲散时间完成.

这个题的难点其实是最后一问！

因为既然是google的题，肯丢最后要考虑时间复杂度和优化问题。只有结果肯丢过不了关，这里先提供一个最直接的思路。也是比较费时间的。o（n*m）

//直接思考，多项式相乘，每一项一一顺次（考虑两个嵌套循环）的去做乘法，指数相加，系数相乘，保存到临时变量，又考虑到有多项，自然是数组保存了……

//这是正常的很直观的思路，可以依靠数组的下标去映射指数，把系数存到对应指数（下标）处，这里是累加的和。

然后再依靠一个循环，顺次去判断数组的内容，取出想要的系数和对应下标（就是指数），组成一个新项，那就ok了。
//最后的阶数必然是两式子最高阶之和，自然这个数组的长度=这个和+1

  1 /************************************************************************/
  2 // 头文件Polynomial.h
  3 // 定义链表结构
  4 /************************************************************************/
  5 #ifndef POLYNOMIAL_H
  6 #define POLYNOMIAL_H
  7 #include <stdlib.h>
  8 #include <stdio.h>
  9 #include <float.h>
 10 
 11 //链表结构
 12 typedef struct Node{
 13     struct Node *next;
 14     double coefficient;
 15     int exponent;
 16 } Node, *Polynomial;
 17 
 18 //链表初始化
 19 void initList(Polynomial *L)
 20 {
 21     //头结点
 22     if (NULL == *L)
 23     {
 24         *L = (Polynomial)malloc(sizeof(Node));
 25         (*L)->coefficient = 0.0;
 26         (*L)->exponent = -1;
 27         (*L)->next = NULL;
 28     }
 29     else
 30     {
 31         puts("表已经存在！");
 32     }
 33 }
 34 
 35 //判断指数同否
 36 int compareExponent(Polynomial nodeA, Polynomial nodeB)
 37 {
 38     int a = nodeA->exponent;
 39     int b = nodeB->exponent;
 40 
 41     if (a == b)
 42     {
 43         return 0;
 44     }
 45     else
 46     {
 47         return a > b ? 1 : -1;
 48     }
 49 }
 50 
 51 //系数判断
 52 bool isZeroByCoefficient(Polynomial node)
 53 {
 54     if (node->coefficient >= -LDBL_EPSILON && node->coefficient <= LDBL_EPSILON)
 55     {
 56         return true;
 57     } 
 58     else
 59     {
 60         return false;
 61     }
 62 }
 63 
 64 //判断2
 65 //系数判断
 66 bool isZeroByDouble(double a)
 67 {
 68     if (a >= -LDBL_EPSILON && a <= LDBL_EPSILON)
 69     {
 70         return true;
 71     } 
 72     else
 73     {
 74         return false;
 75     }
 76 }
 77 
 78 //尾插法建表
 79 void creatListByTail(Polynomial *L, int n)
 80 {
 81     //头结点
 82     if (NULL == *L)
 83     {
 84         *L = (Polynomial)malloc(sizeof(Node));
 85         (*L)->coefficient = 0.0;
 86         (*L)->exponent = -1;
 87         (*L)->next = NULL;
 88         Polynomial tail = NULL;
 89         Polynomial ptr = *L;
 90         //初始化？
 91         if (NULL == (*L)->next)
 92         {
 93             puts("请按照指数升幂，连续的输入项的系数（double）和指数（int）：（中间空格隔开）");
 94             //循环建表
 95             for (int i = 0; i < n; i++)
 96             {
 97                 tail = (Polynomial)malloc(sizeof(Node));
 98                 tail->next = NULL;
 99                 scanf("%lf %d", &tail->coefficient, &tail->exponent);
100 
101                 while (getchar() != '\n')
102                 {
103                     continue;
104                 }
105                 //链接
106                 ptr->next = tail;
107                 //移动指针
108                 ptr = ptr->next;
109                 //尾结点
110             }
111         }
112         else
113         {
114             puts("表已经建立！");
115         }
116     }
117     else
118     {
119         puts("表头已经存在！");
120     }
121 }
122 
123 //遍历
124 void traverseList(Polynomial L)
125 {
126     Polynomial ptr = L->next;
127     int i = 1;
128 
129     while (ptr != NULL)
130     {
131 
132         printf("一元多项式的第%d项：%g X ^ %d\n", i, ptr->coefficient, ptr->exponent);
133         i++;
134         ptr = ptr->next;
135     }
136 }
137 
138 //求最高阶数
139 int getMaxExp(Polynomial L)
140 {
141     Polynomial ptr = L;
142 
143     while (ptr->next != NULL)
144     {
145         ptr = ptr->next;
146     }
147 
148     return ptr->exponent;
149 }
150 
151 //删除结点,删除L中ptr指向的结点
152 void deleteNode(Polynomial L, Polynomial ptr)
153 {
154     Polynomial p = L;
155 
156     while (p->next != ptr)
157     {
158         p = p->next;
159     }
160 
161     ptr = p->next;
162     p->next->next = ptr->next;
163     free(ptr);
164     ptr = NULL;
165 }
166 
167 //多项式相加，本质是链表的归并算法
168 //可以另外开辟空间，也可以使用已存在的空间存储，这里使用后者的算法
169 void addPolynomial(Polynomial LA, Polynomial LB)
170 {
171     //不再开辟内存
172     Polynomial a = LA->next;
173     Polynomial b = LB->next;
174     Polynomial LC = LB;
175     Polynomial tail = LC;
176 
177     while (a != NULL && b != NULL)
178     {
179         //判断指数的关系 a > b ? 1 : -1  else 0
180         switch (compareExponent(a, b))
181         {
182         case 1:
183             tail->next = b;
184             tail = tail->next;
185             b = b->next;
186             break;
187 
188         case -1:
189             tail->next = a;
190             tail = tail->next;
191             a = a->next;
192             break;
193 
194         default:
195             double temp = a->coefficient + b->coefficient;
196             // 0？
197             if (isZeroByDouble(temp))
198             {
199                 a = a->next;
200                 b = b->next;
201                 //删除
202                 deleteNode(LC, tail->next);
203             }
204             else
205             {
206                 tail->next = b;
207                 tail = tail->next;
208                 b->coefficient = temp;
209                 a = a->next;
210                 b = b->next;
211             }// end of if
212         }// end of switch
213     }//end of while
214     //一表比完
215     if (NULL == a)
216     {
217         tail->next = b;
218     }
219     else
220     {
221         tail->next = a;
222     }// end of if
223 
224     free(LA);
225     LA = NULL;
226 }
227 
228 //多项式相乘
229 void mulPolynomial(Polynomial LA, Polynomial LB, Polynomial LC)
230 {
231     Polynomial a = LA->next;
232     Polynomial b = LB->next;
233     Polynomial c = LC;
234     Polynomial ptr = NULL;
235     //两多项式的阶数
236     int numA = getMaxExp(LA);
237     int numB = getMaxExp(LB);
238     //结果多项式的阶数
239     int maxNum = numA + numB;
240      //动态开辟数组空间
241      double *receive = (double *)malloc((maxNum + 1) * sizeof(double));
242      //为数组赋值
243      for (int i = 0; i < maxNum + 1; i++)
244      {
245          //i相当于指数，数组值就是相应指数的系数
246          receive[i] = 0.0;
247      }
248     //指数及数组下标
249     int expByIndex = 0;
250     //顺次扫描A
251     while (a != NULL)
252     {
253         //A不空，顺次扫描B
254         while (b != NULL)
255         {
256             //两项做乘法之后的指数和
257             expByIndex = a->exponent + b->exponent;
258             //系数之间做乘，结果保存到对应的指数下（下标），
259             receive[expByIndex] += (a->coefficient) * (b->coefficient);
260             b = b->next;
261         }
262 
263         b = LB->next;
264         a = a->next;
265     }// end of while
266     //数组保存的是全部项，两两分别乘法之后的结果，保存在对应的下标（数组位置）
267     for (int i = 0; i < maxNum + 1; i++)
268     {
269         // 0？
270         if (isZeroByDouble(receive[i]))
271         {
272             //not do sth
273         }
274         else
275         {
276             //生成结点
277             ptr = (Polynomial)malloc(sizeof(Node));
278             //接到 LC 表
279             c->next = ptr;
280             c = c->next;
281             //赋值
282             c->coefficient =receive[i];
283             c->exponent = i;
284         }// end of if
285     }// end of for
286 
287     c->next = NULL;
288 }
289 
290 //链表销毁
291 void destroyList(Polynomial *L)
292 {
293     Polynomial ptr = NULL;
294 
295     while (*L != NULL)
296     {
297         ptr = (*L)->next;
298         free(*L);
299         *L = ptr;
300     }
301     //
302     *L = NULL;
303     puts("销毁完毕");
304 }
305 #endif

注意：

1、

//数组维数在c99之前必须是常量，c99之后可以是变长数组，但是很多编译器还不支持。

//double receive[maxNum + 1] = {0};目前来说error!

2、

最后销毁的时候销毁B就行了，因为把A插到B，B就是C，C就是B，A只剩下头结点，在相加函数里，早已经被删除！如果还销毁B，铁定报错！重复析构。

3、

多项式相乘（其实就是两个链表的合并问题），这里有两个方法比较常见:

最简单也是最费时间（时间复杂度 o（n*m）最高的实现方法）的直接相乘法:

其实很简单，把表 A 的每一项系数分别和表 B 的每一项系数做乘法，同时，把他们的指数相加，存储到临时数组里，这样得到 N（A）x N（B）个新的项，按照指数相同的，把他们的系数相加组合为一新的项，附带这个指数，输出，得结果。

比较经典的是分治法。

 1 #include "Polynomial.h"
 2 
 3 int main(void)
 4 {
 5     puts("第一波计算加法：初始化表A,B");
 6     Polynomial LA = NULL;
 7     Polynomial LB = NULL;
 8 
 9     puts("建表A");
10     creatListByTail(&LA, 4);
11     puts("打印A");
12     traverseList(LA);
13     puts("建立表B");
14     creatListByTail(&LB, 3);
15     puts("打印表B");
16     traverseList(LB);
17     //相加
18     puts("表A,B相加");
19     addPolynomial(LA, LB);
20     puts("打印和");
21     traverseList(LB);
22     //销毁B即可
23     puts("销毁表A,B");
24     destroyList(&LB);

 1 puts("第二波计算乘法：初始化表A，B，C");
 2     Polynomial LAX = NULL;
 3     Polynomial LBX = NULL;
 4     Polynomial LCX = NULL;
 5     initList(&LCX);
 6 
 7     puts("建表A,B");
 8     creatListByTail(&LAX, 4);
 9     puts("打印表A");
10     traverseList(LAX);
11     puts("建立表B");
12     creatListByTail(&LBX, 3);
13     puts("打印表B");
14     traverseList(LBX);
15     //相乘
16     puts("表A,B做乘法");
17     mulPolynomial(LAX, LBX, LCX);
18     puts("打印结果");
19     traverseList(LCX);
20     //销毁
21     puts("销毁表ABC");
22     destroyList(&LAX);
23     destroyList(&LBX);
24     destroyList(&LCX);
25 
26     system("pause");
27     return 0;
28 }