数组实现
介绍
数组实现较为简单直接。数组下标代表的多项式的次方数,例如定义一个数组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