3091 字

15 分钟

【数据结构】多项式功能实现

2022-10-26

2024-01-13

学习笔记/数据结构

多项式

/

数据结构

前言#

使用表的时候，我们有一个非常常见的问题——多项式ADT，即用表来解决关于一元多项式的抽象数据类型。

我们现在要使用表来对一元多次方程进行操作，例如加减法和乘法。

一元多次方程形如： $Polymial(X)= \sum A_i X^i$

接下来就是使用数组（线性表）和链表的解决。

数组实现#

我们使用数组实现的话，我们可能需要处理的是系数（coefficient）和指数（exponent），我们很容易想到的是使用二维数组来存储。但是当系数或指数比较大的时候，二维数组所占用的空间过多，所以不是一个合适的解法。

那如果使用数组的下标表示指数，然后数组存储系数的话，或许是个可行的方法。并且时间复杂度也随之下降。

为了表示系数和指数的关联，我们使用结构体来定义这个数组和记录它的最高次幂。

1
#define MaxDegree 100
2
//MaxDegree记录允许的最大幂
3
typedef struct poly_array
4
{
5
    int CoeffArray[MaxDegree+1];    //store the coefficients
6
    int HighPower;    //表示当前方程的最高次幂，小于等于MaxDegree
7
}*poly;

接下来就是对这个数组进行一些初始化了，如全部初始化为0先：

1
void zeropoly(poly p)
2
{
3
    p->HighPower=0;    //当前没有东西，最高次为0
4
    for(int i=0;i<=MaxDegree;i++)
5
        p->CoeffArray[i]=0;
6
}

加法#

接下来的内容是实现多项式加法，这个比较简单。根据我们数学知识，多项式加法，同次幂的系数相加，若没有同次幂的情况，则保留即可。

因为我们是以最大次项作为循环的标志来操作数组的，所以需要考虑一个特殊情况：如果最高次项相加为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; 此时我们的这一项不应该是最高次项。

所以我们就有这样的函数：

1
poly poly_addition(const poly p1, const poly p2)
2
{
3
    poly sum=(poly)malloc(sizeof(struct poly_array));
4
    zeropoly(sum);
5
    int power=max(p1->HighPower,p2->HighPower);
6
    for(int i=power;i>=0;i--)
7
        if(p1->CoeffArray[i] || p2->CoeffArray[i])    //if terms need to add
8
            sum->CoeffArray[i]=p1->CoeffArray[i]+p2->CoeffArray[i];
9
    for(int i=power;i>=0;i--)    //refind the highest power of sum
10
        if(sum->CoeffArray[i])
11
            sum->HighPower=i,break;    //the first none-zero if the highest power.
12
    return sum;
13
}

代码中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; 此时我们的这一项不应该是最高次项。

故代码为：

1
poly poly_subtraction(const poly p1, const poly p2)
2
{
3
    poly sum=(poly)malloc(sizeof(struct poly_array));
4
    zeropoly(sum);
5
    int power=max(p1->HighPower,p2->HighPower);
6
    for(int i=power;i>=0;i--)
7
        if(p1->CoeffArray[i] || p2->CoeffArray[i])    //if terms need to subtract
8
            sum->CoeffArray[i]=p1->CoeffArray[i]-p2->CoeffArray[i];
9
    for(int i=power;i>=0;i--)
10
        if(sum->CoeffArray[i])
11
            sum->HighPower=i,break;    //the first none-zero if the highest power.
12
    return sum;
13
}

和之前加法的代码基本相同，这里就不再解释。

乘法#

多项式的乘法满足逐项相乘后相加的特点——逐项相乘并相加，相乘时系数相乘，指数相加，例如：

根据乘法法则，对于 $7x^2$ 这一项，它与第二个多项式逐项相乘并相加： $7 \cdot 8x^4 + 7 \cdot 6x^3 + 7 \cdot 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的情况，但是因为乘法法则，指数相加了，所以还需要我们重新找一次最高指数。

故代码为：

1
poly poly_mutiplication(const poly p1, const poly p2)
2
{
3
    poly product=(poly)malloc(sizeof(struct poly_array));
4
    zeropoly(product);
5
    for(int i=0;i<=p1->HighPower;i++)
6
    {
7
        for(int j=0;j<=p2->HighPower;j++)
8
        {
9
            if(!(i + j > MaxDegree))    //Determine whether the size is exceeded
10
            {
11
                product->CoeffArray[i+j] += p1->CoeffArray[i]*p2->CoeffArray[j];
12
            }
13
            else
14
            {
15
                printf("Out of size!\n");
16
                return NULL;
17
            }
18
        }
19
    }
20
    for(int i=p1->HighPower + p2->HighPower;i>0;i--)    //find the highest power of product
21
        if(product->CoeffArray[i]!=0)
22
            product->HighPower=i,break;    //first none-zero coeffcient power is the highest.
23
}

代码中循环我们先判断当前生成的指数i+j会不会超过限制，超过限制了就不能相乘了。注意相乘时，我们应该是product->coeffarray**+=**…因为可能相乘会出现同样指数的项，我们需要把它们合并相加，不能直接覆盖了，所以必须是+=。

最后重新查找时，我们假设从最大可能位置开始找，找到第一个系数不为0的即最大指数。

但是我们试想一下，如果最高指数与后面的指数相差很多，例如 $5x^{1000}+2x$ 这种，我们就需要生成一个1000+1个位的数组，其中只用到了很少的空间，造成了空间浪费。

因为数组是连续的，如果换成不连续的链表就可以节省很多空间。

链表实现#

和数组一样的，我们也需要存储系数和指数，我们使用单向链表还需要一个指向下一项的指针。故定义：

1
typedef struct poly_linked
2
{
3
    int coefficient;
4
    int exponent;
5
    struct poly_linked *next;
6
}*poly,Node;

接下来也是对链表的初始化和其他函数，默认传进来的数组是已经递减排序的：

1
poly createpoly(int *arr, int n)    //arr must exponentially decreasing!
2
{
3
    poly p=(poly)malloc(sizeof(Node));    //p为哑节点，p->next的为head
4
    poly t=p;
5
    for(int i=n;i>0;i--)
6
    {
7
        if(arr[i] != 0)    //如果存在项
8
        {
9
            t=insert(t,arr[i],i);    //把当前插入，并且将其设为前节点
10
        }
11
    }
12
    return p;
13
}
14

15
poly insert(poly t,int c,int e)    //t是前节点，因为需要单向链表连接
16
{
17
    poly node=(poly)malloc(sizeof(Node));
18
    if(node == NULL) {printf("No Space!\n");return NULL;}
19
    node->coefficient=c;
20
    node->exponent=e;
21
    node->next=NULL;
22
    if(t!=NULL) t->next=node;    //连接
23
    return node;    //返回新的节点
24
}
25

26
int max(int x,int y)
27
{
28
    return (x>y)?x:y;
29
}
30

31
poly find_exp(poly t, int e)    //找到指数为e的节点，并返回
32
{
33
    while(t)
34
    {
35
        if(t->exponent == e)
36
            return t;
37
        t=t->next;
38
    }
39
    return NULL;
40
}

加法#

使用链表时，两个多项式不一定是项相对的。我们在链表加法中，应该是如图所示的做法：

即找到相同指数，并且系数相加；没找到则保留。因为我们是从大到小创造链表了，所以在两个位置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加入。

故此时我们的代码就分三种情况即可：

1
poly poly_addition(poly p1, poly p2)
2
{
3
    poly t1=p1,t2=p2;
4
    poly sum=(poly)malloc(sizeof(Node));    //sum has dumb node.
5
    sum->next=NULL;
6
    poly t3=sum;    //record preview node of sum
7
    while(t1 && t2)
8
    {
9
        if(t1->exponent == t2->exponent)    //Counterpoint
10
        {
11
            int count=t1->coefficient + t2->coefficient;
12
            if(count != 0)    //avoid count==0 => no need to store
13
            {
14
                t3=insert(t3,count,t1->exponent);
15
            }
16
            t1=t1->next;t2=t2->next;
17
            continue;
18
        }
19
        if(t1->exponent > t2->exponent)    //Dislocation 1: t1 have and t2 haven't
20
        {
21
            t3=insert(t3,t1->coefficient,t1->exponent);    //must exist
22
            t1=t1->next;    //移动t1
23
            continue;
24
        }
25
        if(t1->exponent < t2->exponent)    //Dislocation 2: t2 have and t1 haven't
26
        {
27
            t3=insert(t3,t2->coefficient,t2->exponent);    //must exist
28
            t2=t2->next;    //移动t2
29
            continue;
30
        }
31
    }
32
    return sum->next;
33
}

这里当它们对位相加的时候，要注意可能出现相加为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的情况：

1
poly poly_subtraction(poly p1, poly p2)
2
{
3
    poly t1=p1,t2=p2;
4
    poly sum=(poly)malloc(sizeof(Node));    //sum has dumb node.
5
    sum->next=NULL;
6
    poly t3=sum;    //record preview node of sum
7
    while(t1 && t2)
8
    {
9
        if(t1->exponent == t2->exponent)    //Counterpoint
10
        {
11
            int sub=t1->coefficient - t2->coefficient;
12
            if(sub != 0)    //avoid sub==0 => no need to store
13
            {
14
                t3=insert(t3,sub,t1->exponent);
15
            }
16
            t1=t1->next;t2=t2->next;
17
            continue;
18
        }
19
        if(t1->exponent > t2->exponent)    //Dislocation 1: t1 have and t2 haven't
20
        {
21
            t3=insert(t3,t1->coefficient,t1->exponent);    //must exist
22
            t1=t1->next;
23
            continue;
24
        }
25
        if(t1->exponent < t2->exponent)    //Dislocation 2: t2 have and t1 haven't
26
        {
27
            t3=insert(t3,0-t2->coefficient,t2->exponent);    //must exist
28
            t2=t2->next;
29
            continue;
30
        }
31
    }
32
    return sum->next;
33
}

乘法#

乘法根据乘法律，我们也是逐项相乘，然后化简。于是当我们相乘的时候，要讨论两种情况：

结果中已经存在当前相乘得到的指数，此时我们把它们相加；
结果中不存在当前得到的指数，我们新创建node。

故此时代码：

1
poly poly_multiplication(poly p1, poly p2)
2
{
3
    poly p=p1,q=p2;
4
    poly product=(poly)malloc(sizeof(Node));    //product has dumb node.
5
    product->next=NULL;
6
    poly pre=product;    //record preview node of product
7
    while(p)
8
    {
9
        while(q)
10
        {
11
            //Find if a result with the same exponent already exists before
12
            poly found=find_exp(product->next,p->exponent+q->exponent);
13
            if(!found)    //No find, create
14
            {
15
                pre=insert(pre,p->coefficient*q->coefficient,p->exponent+q->exponent);
16
            }
17
            else    //Merge the results of the same exponent
18
            {
19
                found->coefficient+=p->coefficient*q->coefficient;
20
            }
21
            q=q->next;
22
        }
23
        p=p->next;
24
        q=p2;
25
    }
26
    return product->next;
27
}

但是此时可能会出现乱序的问题，因为我们不能保证新相乘得到的指数一定是递减的，故可能需要给这个新的多项式进行排序。例如： $(3x^3+x)(x+x^2)$ ，其中第一项指数为4，第二项指数为5，此时4<5，已经乱序了。

对于重新排序多项式，我们只需要使用类似冒泡排序之类的就可以解决了。

1
poly poly_sorting(poly p)
2
{
3
    poly t1=p;
4
    poly t2=p->next;
5
    while(t1)    //类似冒泡排序
6
    {
7
        while(t2)
8
        {
9
            if(t1->exponent < t2->exponent)
10
            {
11
                poly t=find_pre(p,t1->exponent);    //preview node of t1
12
                t->next=t2;
13
                t1->next=t2->next;
14
                t2->next=t1;
15
            }
16
            t2=t2->next;
17
        }
18
        t1=t1->next;
19
    }
20
    return p;
21
}
22

23
poly find_pre(poly p, int e)    //找到前节点
24
{
25
    poly t=p;
26
    while(t)
27
    {
28
        if(t->next->exponent == e)
29
            return t;
30
        else t=t->next;
31
    }
32
    return NULL;
33
}