一元多项式用链表表示，只用表示非零项。每个非零项都包含指数和系数两部份，这样可以用链表结构来表示。
结构定义如下：
|
1 2 3 4 5 6 |
typedef struct PolyNode* Polynomial; struct PolyNode{ int coef; //系数 int expon; //指数 Polynomial plink; //下一项 } |
写一段运用链表结构表示一元多项式，相加运算：
两个一元多项式：
f1(x) = 8x13+10X9+4x2
f2(x) = 8x18-2X9+4x+4
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
// 梁笔记 // https://zouzhongliang.com #include <iostream> #include <ctime> using namespace std; typedef struct PolyNode* Polynomial; struct PolyNode{ int coef; //系数 int expon; //指数 Polynomial plink; //下一项 PolyNode(){ coef = 0; expon = 0; plink = NULL; } PolyNode(int coef_,int expon_,Polynomial pLink_){ coef = coef_; expon = expon_; plink = pLink_; } PolyNode(int coef_,int expon_){ coef = coef_; expon = expon_; plink = NULL; } }; void PolynomialAdd(PolyNode* f, PolyNode* f1, PolyNode* f2) { while(f1 || f2 ){ if (f1 && f2){ if (f1->expon == f2->expon){ if (f1->coef + f2->coef == 0){ }else{ f->plink = new PolyNode( f1->coef + f2->coef, f1->expon); f = f->plink; } f1 = f1->plink; f2 = f2->plink; }else if (f1->expon > f2->expon){ f->plink = new PolyNode( f1->coef, f1->expon); f1 = f1->plink; f = f->plink; }else{ f->plink = new PolyNode( f2->coef, f2->expon); f2 = f2->plink; f = f->plink; } }else{ if (f1){ f->plink = new PolyNode( f1->coef, f1->expon); f1 = f1->plink; f = f->plink; }else{ f->plink = new PolyNode( f2->coef, f2->expon); f2 = f2->plink; f = f->plink; } } } } //f1(x) = 8x13+10X9+4x2 //f2(x) = 8x18-2X9+4x+4 int main() { PolyNode* f1; PolyNode* f2; PolyNode* f = new PolyNode(0,0,NULL);; f1 = new PolyNode(8,13, new PolyNode(10,9, new PolyNode(4,2,NULL))); f2 = new PolyNode(8,18, new PolyNode(-2,9, new PolyNode(4,1, new PolyNode(4,0,NULL)))); PolynomialAdd( f, f1, f2); while(f){ if (f->expon !=0 || f->coef !=0) cout<<"指数："<<f->expon<<" "<<"系数："<<f->coef<<endl; f = f->plink; } return 0; } |
链表结构表示一元多项式非零项，相加结果：
|
1 2 3 4 5 6 |
指数：18 系数：8 指数：13 系数：8 指数：9 系数：8 指数：2 系数：4 指数：1 系数：4 指数：0 系数：4 |
注：存一元多项式非零项时，要按指数大小有序存储，为了方便相加计算。