表的应用--多项式计算

数组实现

介绍

数组实现较为简单直接。数组下标代表的多项式的次方数，例如定义一个数组Array，那么Array[0]就代表次方为 0 的项的系数，以此类推。所以我们发现，由于数组是连续的，所以对于稀疏多项式来说，它所浪费的空间较大。

定义

#include<stdio.h>
#include<stdlib.h>
#define MaxDegree 20
#define Max(a, b) ((a)>(b)? (a): (b))
typedef struct Polynomial
{
    int CoeffArray[ MaxDegree+1 ];
    // 最高次方数，主要用于循环次数的确定
        int HighPower;
} *Polynomial;

void ZeroPolynomial(Polynomial);
void addPolynomial(Polynomial, Polynomial, Polynomial);
void MultPolynomal(Polynomial, Polynomial, Polynomial);

我们定义了数组所能承担的最大次方数，那就是MaxDegree，因为还有一个次方数为 0 的项(也就是常数项)，所以我们定义的数组CoeffArray需要MaxDegree+1个空间。

函数

我们定义了三个函数，分别是ZeroPolynomial用于将多项式置零，也就是所有项的系数置零，也就是将数组中的所有元素置零。

void
ZeroPolynomial(Polynomial Poly) {
    /* 注意这里的循环次数，由于数组有MaxDegree+1个元素，
    所以这里要循环MaxDegree+1次
    */
    for(int i = 0; i<= MaxDegree; i++) {
        Poly->CoeffArray[i] = 0;
    }
    Poly->HighPower = 0;
}

addPolynomial函数将两个多项式相加。也就是合并同类项，将相同次方的项的系数相加，也就是将相同数组下标的值相加。

void
addPolynomial(Polynomial Poly1, Polynomial Poly2, Polynomial Polysum) {
    ZeroPolynomial(Polysum);
    Polysum->HighPower = Max(Poly1->HighPower, Poly2->HighPower);
    for (int i = 0; i <= Polysum->HighPower; i++)
    {
        Polysum->CoeffArray[i] = Poly1->CoeffArray[i] + Poly2->CoeffArray[i];
    }
}

MultPolynomial函数将两个多项式相乘。难点在于合并同类项。

void
MultPolynomal(Polynomial Poly1, Polynomial Poly2, Polynomial PolyPord) {
    ZeroPolynomial(PolyPord);
    PolyPord->HighPower = Poly1->HighPower + Poly2->HighPower;
    if (PolyPord->HighPower > MaxDegree) {
        fprintf(stderr, "Exceeded array size");
    }
    else {
        for (int i = 0; i <= PolyPord->HighPower; i++)
        {
            for (int j = 0; j <= PolyPord->HighPower; j++)
            {
                // 注意这里使用 +=
                PolyPord->CoeffArray[i+j] += Poly1->CoeffArray[i] * Poly2->CoeffArray[j];
            }
        }

    }
}

链表实现

介绍

相比于数组实现，链表可以很好的处理稀疏多项式的计算，因为它不必是连续的空间。但是难点在于多项式的乘法中的合并同类项。

定义

#include<stdlib.h>
#include<stdio.h>
#define Max(a, b) ((a) > (b)? (a): (b))
typedef struct Node *PtrToNode;
typedef PtrToNode Polynomial;
struct Node {
    int Coefficient;
    // 指数
    int Exponent;
    PtrToNode Next;
};
// 顺序插入，并可以合并同类项
void Insert(int, int, Polynomial);
PtrToNode Find(int, Polynomial);
void ZeroPolynomial( Polynomial);
void AddPolynomial( Polynomial, Polynomial, Polynomial);
void MultPolynomial( Polynomial, Polynomial, Polynomial);

加法实现

加法的实现较为简单。我们分别创建两个指针指向要相加的多项式的头部，即ptr1 = poly1->Next，ptr2 = poly2->Next，然后再创建一个指针指向当前ptr1和ptr2指向的项的指数(Exponent)较小的那个节点，也就是PtrToNode minptr = ptr1->Exponent < ptr2->Exponent? ptr1: ptr2;。

一遍循环之后，将minptr指向的节点插入到新的多项式polysum中。直到任意一个多项式到达结尾，则将另一个多项式剩余的项插入到polysum的结尾。

void
AddPolynomial( Polynomial poly1, Polynomial poly2, Polynomial polysum ) {
    ZeroPolynomial(polysum);
    PtrToNode ptr1 = poly1->Next;
    PtrToNode ptr2 = poly2->Next;
    PtrToNode ptrsum = polysum;
    while (ptr1 != NULL && ptr2 != NULL) {
        // 返回第一个节点指数较小的那个链表
        PtrToNode minptr = ptr1->Exponent < ptr2->Exponent? ptr1: ptr2;
        Polynomial temCell = (PtrToNode)malloc(sizeof(struct Node));
        temCell->Next = NULL;
        if (ptr1->Exponent == ptr2->Exponent) {
            temCell->Exponent = ptr1->Exponent;
            temCell->Coefficient = ptr1->Coefficient + ptr2->Coefficient;
        } else {
            temCell->Exponent = minptr->Exponent;
            temCell->Coefficient = minptr->Coefficient;
        }
        ptrsum->Next = temCell;
        ptrsum = ptrsum->Next;
        ptr1 = ptr1->Next;
        ptr2 = ptr2->Next;
    }
    if (ptr1 == NULL) {
        ptrsum->Next = ptr2;
    } else {
        ptrsum->Next = ptr1;
    }
}

乘法实现

关键在于插入函数Insert，它可以有顺序的插入，并能判断结果多项式中是否有重复的次方项，如果有，则合并他们的系数。

void
Insert(int Exponent, int Coefficient, Polynomial Poly) {


    // 升序插入，找到一个指数大于此指数的前一个节点
    PtrToNode head = Poly;
    while (head->Next != NULL && head->Next->Exponent < Exponent) {
        head = head->Next;
    }
    // 如果到达末尾，或者找到满足上面判断表达式的，则插入
    if (head->Next == NULL || head->Next->Exponent > Exponent ) {
        PtrToNode P = (PtrToNode)malloc(sizeof(struct Node));
        P->Coefficient = Coefficient;
        P->Exponent = Exponent;
        P->Next = head->Next;
        head->Next = P;
    // 如果找到一个相等次方数的项，则合并系数
    // if find the Node which have the same Exponent then plus the Coefficient of them.
    } else if (head->Next->Exponent == Exponent) {
        head->Next->Coefficient += Coefficient;
    }
}
void
MultPolynomial( Polynomial poly1, Polynomial poly2, Polynomial polyPord) {
    ZeroPolynomial(polyPord);
    PtrToNode p1 = poly1->Next;
    PtrToNode p2 = poly2->Next;
    // 本质上是两层的嵌套循环
    while (p1 != NULL) {
        while (p2 != NULL) {
            int plusExponent = p2->Exponent + p1->Exponent;
            int multCoefficient = p1->Coefficient * p2->Coefficient;
            Insert(plusExponent, multCoefficient, polyPord);
            p2 = p2->Next;
        }
        p1 = p1->Next;
        // 复位第二个多项式的指针
        p2 = poly2->Next;
    }
}

最后修改于 2021-06-10