前言
使用表的时候，我们有一个非常常见的问题——多项式ADT，即用表来解决关于一元多项式的抽象数据类型。
我们现在要使用表来对一元多次方程进行操作，例如加减法和乘法。
一元多次方程形如：Polymial(X)=∑AiX^i
接下来就是使用数组（线性表）和链表的解决。
数组实现
我们使用数组实现的话，我们可能需要处理的是系数（coefficient）和指数（exponent），我们很容易想到的是使用二维数组来存储。但是当系数或指数比较大的时候，二维数组所占用的空间过多，所以不是一个合适的解法。
那如果使用数组的下标表示指数，然后数组存储系数的话，或许是个可行的方法。并且时间复杂度也随之下降。
为了表示系数和指数的关联，我们使用结构体来定义这个数组和记录它的最高次幂。
#define MaxDegree 100
//MaxDegree记录允许的最大幂
typedef struct poly_array
{
int CoeffArray[MaxDegree+1]; //store the coefficients
int HighPower; //表示当前方程的最高次幂，小于等于MaxDegree
}*poly;接下来就是对这个数组进行一些初始化了，如全部初始化为0先：
void zeropoly(poly p)
{
p->HighPower=0; //当前没有东西，最高次为0
for(int i=0;i<=MaxDegree;i++)
p->CoeffArray[i]=0;
}加法
接下来的内容是实现多项式加法，这个比较简单。根据我们数学知识，多项式加法，同次幂的系数相加，若没有同次幂的情况，则保留即可。
因为我们是以最大次项作为循环的标志来操作数组的，所以需要考虑一个特殊情况：如果最高次项相加为0——这种情况下该项就不存在了，最高次项就应该发生转移。解决这个问题需要我们在循环中时刻警惕更新最大次幂的值。
故总的来说，加法需要考虑如下情况，我们设两个多项式分别为p1,p2，在指数为i时：
- p1->coeffarray[i] ≠ 0 , p2->coeffarray[i] == 0，此时p1存在项，p2不存在，我们得到的sum->coeffarray[i] = p1->coeffarray[i];
- p1->coeffarray[i] == 0 , p2->coeffarray[i] ≠ 0，此时p2存在项，p1不存在，我们得到的sum->coeffarray[i] = p2->coeffarray[i];
- p1->coeffarray[i] ≠ 0 , p2->coeffarray[i] ≠ 0，此时p1，p2均存在项，我们得到的sum->coeffarray[i] = p1->coeffarray[i] + p2->coeffarray[i];
- p1->coeffarray[i] == 0 , p2->coeffarray[i] == 0，此时p1，p2均不存在项，我们得到的sum->coeffarray[i] = 0;
- p1->coeffarray[i] ≠ 0 , p2->coeffarray[i] ≠ 0, p1->coeffarray[i] + p2->coeffarray[i] ==0，此时p1，p2均存在项但和为0，我们得到的sum->coeffarray[i] = 0; 此时我们的这一项不应该是最高次项。
所以我们就有这样的函数：
poly poly_addition(const poly p1, const poly p2)
{
poly sum=(poly)malloc(sizeof(struct poly_array));
zeropoly(sum);
int power=max(p1->HighPower,p2->HighPower);
for(int i=power;i>=0;i--)
if(p1->CoeffArray[i] || p2->CoeffArray[i]) //if terms need to add
sum->CoeffArray[i]=p1->CoeffArray[i]+p2->CoeffArray[i];
for(int i=power;i>=0;i--) //refind the highest power of sum
if(sum->CoeffArray[i])
sum->HighPower=i,break; //the first none-zero if the highest power.
return sum;
}代码中power取到了两个多项式的最高项，可以确定我们相加的范围；综合前面的情况，如果不是均为0的情况，我们直接将当前次数的两多项式系数相加即可。（当然均为0也可以相加，但是会多执行很多次操作。）
最后一个循环是在找新生成的多项式中的最高指数，因为存在之前第五种可能的情况，此时不一定是我们之前找到的power，它的最高指数一定是<=power的，故我们重新开始找，找到第一个不是0的指数就是我们要找的最高指数了。
减法
减法和加法一样，或者说减法就是加法的一种情况，所以情况和代码也基本相同。
减法需要考虑如下情况，我们设两个多项式分别为p1,p2，减法为p1-p2，在指数为i时：
- p1->coeffarray[i] ≠ 0 , p2->coeffarray[i] == 0，此时p1存在项，p2不存在，我们得到的sum->coeffarray[i] = p1->coeffarray[i];
- p1->coeffarray[i] == 0 , p2->coeffarray[i] ≠ 0，此时p2存在项，p1不存在，我们得到的sum->coeffarray[i] = -p2->coeffarray[i];
- p1->coeffarray[i] ≠ 0 , p2->coeffarray[i] ≠ 0，此时p1，p2均存在项，我们得到的sum->coeffarray[i] = p1->coeffarray[i] - p2->coeffarray[i];
- p1->coeffarray[i] == 0 , p2->coeffarray[i] == 0，此时p1，p2均不存在项，我们得到的sum->coeffarray[i] = 0;
- p1->coeffarray[i] ≠ 0 , p2->coeffarray[i] ≠ 0, p1->coeffarray[i] - p2->coeffarray[i] ==0，此时p1，p2均存在项但和为0，我们得到的sum->coeffarray[i] = 0; 此时我们的这一项不应该是最高次项。
故代码为：
poly poly_subtraction(const poly p1, const poly p2)
{
poly sum=(poly)malloc(sizeof(struct poly_array));
zeropoly(sum);
int power=max(p1->HighPower,p2->HighPower);
for(int i=power;i>=0;i--)
if(p1->CoeffArray[i] || p2->CoeffArray[i]) //if terms need to subtract
sum->CoeffArray[i]=p1->CoeffArray[i]-p2->CoeffArray[i];
for(int i=power;i>=0;i--)
if(sum->CoeffArray[i])
sum->HighPower=i,break; //the first none-zero if the highest power.
return sum;
}和之前加法的代码基本相同，这里就不再解释。
乘法
多项式的乘法满足逐项相乘后相加的特点——逐项相乘并相加，相乘时系数相乘，指数相加，例如：
根据乘法法则，对于7x^2这一项，它与第二个多项式逐项相乘并相加：7*8x^4 + 7*6x^3 + 7*5x^2，然后再对8x这一项逐项相乘并相加，再到2这一项。
所以很容易看出来，我们通过计算机处理它应该使用两重循环，第一层循环处理第一个多项式的第i项，第二层循环处理第二个多项式的第j项。然后逐项相乘并相加即可。
相乘时，我们生成的系数应该存在product->coffarray[i+j]处，因为系数相乘，指数相加。
同样的，它同样也会出现一些情况，我们设两个多项式为p1,p2，在i,j下：
- p1->coeffarray[i] ≠ 0 , p2->coffearray[j] == 0，此时p1存在项，p2不存在，我们得到的product->coeffarray[i+j] = 0;
- p1->coeffarray[i] == 0 , p2->coeffarray[j] ≠ 0，此时p2存在项，p1不存在，我们得到的product->coffarray[i+j] = 0;
- p1->coeffarray[i] ≠ 0 , p2->coeffarray[j] ≠ 0，此时p1，p2均存在项，我们得到的product->coeffarray[i+j] = p1->coeffarray[i] - p2->coeffarray[i];
- p1->coeffarray[i] == 0 , p2->coeffarray[j] == 0，此时p1，p2均不存在项，我们得到的product->coeffarray[i+j] = 0.
此时不存在两项非0相乘为0的情况，但是因为乘法法则，指数相加了，所以还需要我们重新找一次最高指数。
故代码为：
poly poly_mutiplication(const poly p1, const poly p2)
{
poly product=(poly)malloc(sizeof(struct poly_array));
zeropoly(product);
for(int i=0;i<=p1->HighPower;i++)
{
for(int j=0;j<=p2->HighPower;j++)
{
if(!(i + j > MaxDegree)) //Determine whether the size is exceeded
{
product->CoeffArray[i+j] += p1->CoeffArray[i]*p2->CoeffArray[j];
}
else
{
printf("Out of size!\n");
return NULL;
}
}
}
for(int i=p1->HighPower + p2->HighPower;i>0;i--) //find the highest power of product
if(product->CoeffArray[i]!=0)
product->HighPower=i,break; //first none-zero coeffcient power is the highest.
}代码中循环我们先判断当前生成的指数i+j会不会超过限制，超过限制了就不能相乘了。注意相乘时，我们应该是product->coeffarray+=...因为可能相乘会出现同样指数的项，我们需要把它们合并相加，不能直接覆盖了，所以必须是+=。
最后重新查找时，我们假设从最大可能位置开始找，找到第一个系数不为0的即最大指数。
但是我们试想一下，如果最高指数与后面的指数相差很多，例如5x^1000+2x这种，我们就需要生成一个1000+1个位的数组，其中只用到了很少的空间，造成了空间浪费。
因为数组是连续的，如果换成不连续的链表就可以节省很多空间。
链表实现
和数组一样的，我们也需要存储系数和指数，我们使用单向链表还需要一个指向下一项的指针。故定义：
typedef struct poly_linked
{
int coefficient;
int exponent;
struct poly_linked *next;
}*poly,Node;接下来也是对链表的初始化和其他函数，默认传进来的数组是已经递减排序的：
poly createpoly(int *arr, int n) //arr must exponentially decreasing!
{
poly p=(poly)malloc(sizeof(Node)); //p为哑节点，p->next的为head
poly t=p;
for(int i=n;i>0;i--)
{
if(arr[i] != 0) //如果存在项
{
t=insert(t,arr[i],i); //把当前插入，并且将其设为前节点
}
}
return p;
}
poly insert(poly t,int c,int e) //t是前节点，因为需要单向链表连接
{
poly node=(poly)malloc(sizeof(Node));
if(node == NULL) {printf("No Space!\n");return NULL;}
node->coefficient=c;
node->exponent=e;
node->next=NULL;
if(t!=NULL) t->next=node; //连接
return node; //返回新的节点
}
int max(int x,int y)
{
return (x>y)?x:y;
}
poly find_exp(poly t, int e) //找到指数为e的节点，并返回
{
while(t)
{
if(t->exponent == e)
return t;
t=t->next;
}
return NULL;
}
加法
使用链表时，两个多项式不一定是项相对的。我们在链表加法中，应该是如图所示的做法：
即找到相同指数，并且系数相加；没找到则保留。因为我们是从大到小创造链表了，所以在两个位置t1,t2上（多项式p1,p2）的时候，存在下面的情况：
- 如果t1->exponent == t2->exponent时，说明这两个位置上的指数相同，我们把它们相加。
- 如果t1->exponent > t2->exponent时，说明当前位置下，t1的指数比t2的指数大，因为是递减的，说明p2中不存在与t1这样大的指数了，故此时我们把t1加入。
- 如果t1->exponent < t2->exponent时，说明当前情况下t1的指数比t2小，在之后p1中也不会存在大于等于t2的情况，故此时把t2加入。
故此时我们的代码就分三种情况即可：
poly poly_addition(poly p1, poly p2)
{
poly t1=p1,t2=p2;
poly sum=(poly)malloc(sizeof(Node)); //sum has dumb node.
sum->next=NULL;
poly t3=sum; //record preview node of sum
while(t1 && t2)
{
if(t1->exponent == t2->exponent) //Counterpoint
{
int count=t1->coefficient + t2->coefficient;
if(count != 0) //avoid count==0 => no need to store
{
t3=insert(t3,count,t1->exponent);
}
t1=t1->next;t2=t2->next;
continue;
}
if(t1->exponent > t2->exponent) //Dislocation 1: t1 have and t2 haven't
{
t3=insert(t3,t1->coefficient,t1->exponent); //must exist
t1=t1->next; //移动t1
continue;
}
if(t1->exponent < t2->exponent) //Dislocation 2: t2 have and t1 haven't
{
t3=insert(t3,t2->coefficient,t2->exponent); //must exist
t2=t2->next; //移动t2
continue;
}
}
return sum->next;
}这里当它们对位相加的时候，要注意可能出现相加为0的情况，这个时候就不需要存储了。
我这里返回sum->next，是因为sum为哑节点，前面调用都是从它的下一位，即head开始的，故这里返回head。当然你也可以自己改。
减法
和加法一样的，同样是三种情况：
在两个位置t1,t2上（多项式p1,p2）的时候，存在下面的情况：
- 如果t1->exponent == t2->exponent时，说明这两个位置上的指数相同，我们把它们相减。
- 如果t1->exponent > t2->exponent时，说明当前位置下，t1的指数比t2的指数大，因为是递减的，说明p2中不存在与t1这样大的指数了，故此时结果为t1。
- 如果t1->exponent < t2->exponent时，说明当前情况下t1的指数比t2小，在之后p1中也不会存在大于等于t2的情况，故此时结果为0-t2。
和加法一样，我们也要主要相减等于0的情况：
poly poly_subtraction(poly p1, poly p2)
{
poly t1=p1,t2=p2;
poly sum=(poly)malloc(sizeof(Node)); //sum has dumb node.
sum->next=NULL;
poly t3=sum; //record preview node of sum
while(t1 && t2)
{
if(t1->exponent == t2->exponent) //Counterpoint
{
int sub=t1->coefficient - t2->coefficient;
if(sub != 0) //avoid sub==0 => no need to store
{
t3=insert(t3,sub,t1->exponent);
}
t1=t1->next;t2=t2->next;
continue;
}
if(t1->exponent > t2->exponent) //Dislocation 1: t1 have and t2 haven't
{
t3=insert(t3,t1->coefficient,t1->exponent); //must exist
t1=t1->next;
continue;
}
if(t1->exponent < t2->exponent) //Dislocation 2: t2 have and t1 haven't
{
t3=insert(t3,0-t2->coefficient,t2->exponent); //must exist
t2=t2->next;
continue;
}
}
return sum->next;
}乘法
乘法根据乘法律，我们也是逐项相乘，然后化简。于是当我们相乘的时候，要讨论两种情况：
- 结果中已经存在当前相乘得到的指数，此时我们把它们相加；
- 结果中不存在当前得到的指数，我们新创建node。
故此时代码：
poly poly_multiplication(poly p1, poly p2)
{
poly p=p1,q=p2;
poly product=(poly)malloc(sizeof(Node)); //product has dumb node.
product->next=NULL;
poly pre=product; //record preview node of product
while(p)
{
while(q)
{
//Find if a result with the same exponent already exists before
poly found=find_exp(product->next,p->exponent+q->exponent);
if(!found) //No find, create
{
pre=insert(pre,p->coefficient*q->coefficient,p->exponent+q->exponent);
}
else //Merge the results of the same exponent
{
found->coefficient+=p->coefficient*q->coefficient;
}
q=q->next;
}
p=p->next;
q=p2;
}
return product->next;
}
但是此时可能会出现乱序的问题，因为我们不能保证新相乘得到的指数一定是递减的，故可能需要给这个新的多项式进行排序。例如：(3x^3+x)(x+x^2)，其中第一项指数为4，第二项指数为5，此时4<5，已经乱序了。
对于重新排序多项式，我们只需要使用类似冒泡排序之类的就可以解决了。
poly poly_sorting(poly p)
{
poly t1=p;
poly t2=p->next;
while(t1) //类似冒泡排序
{
while(t2)
{
if(t1->exponent < t2->exponent)
{
poly t=find_pre(p,t1->exponent); //preview node of t1
t->next=t2;
t1->next=t2->next;
t2->next=t1;
}
t2=t2->next;
}
t1=t1->next;
}
return p;
}
poly find_pre(poly p, int e) //找到前节点
{
poly t=p;
while(t)
{
if(t->next->exponent == e)
return t;
else t=t->next;
}
return NULL;
}后记
多项式算法就到这里结束了，仅为个人代码，如有出错请告知！
Comments NOTHING