多项式的每一项需要两个参数，即系数与指数。描述多项式的一种方式是用数组的下标表示项的指数，而用数组存储的元素表示相应项的系数。这样表示的多项式看起来很简单，但是在很多计算中却显得很不方便，这种不方便主要出现”在稀疏的“多项式中（比如x的10000次方加1），如果要输出多项式却要从头到尾扫描数组。另一个缺点是浪费了很多的空间，上面的例子中有效的数组元素仅仅只有两个。所以最好还是用链表表示，每个节点存储一个项的系数和指数，再加上一个指向下一节点的指针。为了以后运算方便时，在构建时就将各项按指数大小排序，如果从小到大排列，那么当输出多项式时就很不方便，并且这样与数学中多项式的写法也不一致，所以最好是从大到小的排序。
;struct PolynomialItem{float Coeff;int Power;PolynomialItem* next;};struct Polynomial{int ItemCount;PolynomialItem *FirstItem;//加入一个lastItem指针，方便函数的编写//特别是编写O(M^2N)时间复杂度的Multi算法时PolynomialItem *LastItem;};
数据结构定义好之后，再写一些基本的函数，方便后面编写多项式运算的代码：
PolynomialItem* CreatePolyItem(float Coeff,int Power){if(Coeff == 0.0f) return NULL;PolynomialItem* PolyItem = new PolynomialItem;PolyItem->Coeff = Coeff;PolyItem->Power = Power;PolyItem->next = NULL;return PolyItem;}PolynomialItem* CopyPolyItem(const PolynomialItem* Item){if(Item == NULL) return NULL;return CreatePolyItem(Item->Coeff,Item->Power);}Polynomial* CreateEmptyPolynomial(){Polynomial* Poly = new Polynomial;Poly->ItemCount = 0;Poly->FirstItem = NULL;Poly->LastItem = NULL;return Poly;}//Append表示不考虑输入Item中Power的值，直接连接到多项式的后面//不保证插入的节点处在正确的位置上void AppendPolyItem(Polynomial** Poly,PolynomialItem *Item){if((*Poly)->ItemCount == 0){(*Poly)->FirstItem = Item;(*Poly)->LastItem = Item;++(*Poly)->ItemCount;return;}Item->next = NULL;(*Poly)->LastItem->next = Item;(*Poly)->LastItem = Item;++(*Poly)->ItemCount;}void AppendPolyItem(Polynomial** Poly,float Coeff,int Power){AppendPolyItem(Poly,CreatePolyItem(Coeff,Power));}//Insert会将输入Item安插到正确的位置void InsertPolyItem(Polynomial** Poly,PolynomialItem *Item){if((*Poly)->ItemCount == 0){AppendPolyItem(Poly,Item);return;}if((*Poly)->FirstItem->Power < Item->Power){Item->next = (*Poly)->FirstItem;(*Poly)->FirstItem = Item;++(*Poly)->ItemCount;return;}PolynomialItem* p = (*Poly)->FirstItem;PolynomialItem* q;while(p){if(p->Power > Item->Power){q = p;p = p->next;}else if(p->Power == Item->Power){p->Coeff += Item->Coeff;return;}else{Item->next = q->next;q->next = Item;++(*Poly)->ItemCount;return;}}AppendPolyItem(Poly,Item);return;}void InsertPolyItem(Polynomial** Poly,float Coeff,int Power){InsertPolyItem(Poly,CreatePolyItem(Coeff,Power));}Polynomial* CreatePolynomial(float Coeffs[],int Powers[],int Count){if(Count <= 0) return NULL;Polynomial* Poly = CreateEmptyPolynomial();for (int i = 0; i < Count; ++i){InsertPolyItem(&Poly,Coeffs[i],Powers[i]);}return Poly;}
构建数据结构的函数基本编写完成，可以开始编写运算函数了：
//以下三个函数只负责项与项的运算PolynomialItem* ItemPlus(const PolynomialItem* item1,const PolynomialItem* item2){if(item1->Power != item2->Power) return NULL;float Coeff = item1->Coeff + item2->Coeff;int Power = item1->Power;return CreatePolyItem(Coeff,Power);}PolynomialItem* ItemMinus(const PolynomialItem* item1,const PolynomialItem* item2){if(item1->Power != item2->Power) return NULL;float Coeff = item1->Coeff – item2->Coeff;int Power = item1->Power;return CreatePolyItem(Coeff,Power);}PolynomialItem* ItemMulti(const PolynomialItem* item1,const PolynomialItem* item2){float Coeff = item1->Coeff * item2->Coeff;int Power = item1->Power + item2->Power;return CreatePolyItem(Coeff,Power);}//多项式运算函数开始Polynomial* Plus(const Polynomial* Poly1,const Polynomial* Poly2){Polynomial* Poly = CreateEmptyPolynomial();PolynomialItem* p = Poly1->FirstItem,*q = Poly2->FirstItem;while(p && q){PolynomialItem* newItem = NULL;if(p->Power == q->Power){newItem = ItemPlus(p,q);p = p->next;q = q->next;}else if(p->Power > q->Power){newItem = CopyPolyItem(p);p = p->next;}else{newItem = CopyPolyItem(q);q = q->next;}AppendPolyItem(&Poly,newItem);}while(p){AppendPolyItem(&Poly,CopyPolyItem(p));p = p->next;}while(q){AppendPolyItem(&Poly,CopyPolyItem(q));q = q->next;}return Poly;}Polynomial* Minus(const Polynomial* Poly1,const Polynomial* Poly2){Polynomial* Poly = CreateEmptyPolynomial();PolynomialItem* p = Poly1->FirstItem,*q = Poly2->FirstItem;while(p && q){PolynomialItem* newItem = NULL;if(p->Power == q->Power){newItem = ItemMinus(p,q);p = p->next;q = q->next;}else if(p->Power > q->Power){newItem = CopyPolyItem(p);p = p->next;}else{newItem = CopyPolyItem(q);newItemCoeff;q = q->next;}AppendPolyItem(&Poly,newItem);}while(p){AppendPolyItem(&Poly,CopyPolyItem(p));p = p->next;}while(q){PolynomialItem* newItem = CopyPolyItem(q);newItemCoeff;AppendPolyItem(&Poly,newItem);q = q->next;}return Poly;}Polynomial* Multi(const Polynomial* Poly1,const Polynomial* Poly2){Polynomial* Poly = CreateEmptyPolynomial();PolynomialItem* q = Poly2->FirstItem;PolynomialItem* p = Poly1->FirstItem;while(q){AppendPolyItem(&Poly,ItemMulti(p,q));q = q->next;}p = p->next;Polynomial* tempPoly = CreateEmptyPolynomial();while(p){q = Poly2->FirstItem;while(q){AppendPolyItem(&tempPoly,ItemMulti(p,q));q = q->next;}PolynomialItem* r = tempPoly->FirstItem;PolynomialItem* s = Poly->FirstItem,*t = NULL;while(s && s->Power >= r->Power){t = s;s = s->next;}while(r && s){tempPoly->FirstItem = r->next;if(t->Power > r->Power){r->next = t->next;t->next = r;t = r;++Poly->ItemCount;}else if(t->Power == r->Power){t->Coeff += r->Coeff;delete r;}r = tempPoly->FirstItem;–tempPoly->ItemCount;while(r && s && s->Power >= r->Power){t = s;s = s->next;}}if(r){if(r->Power == Poly->LastItem->Power){Poly->LastItem->Coeff += r->Coeff;tempPoly->FirstItem = r->next;–tempPoly->ItemCount;delete r;}Poly->LastItem->next = tempPoly->FirstItem;Poly->LastItem = tempPoly->LastItem;Poly->ItemCount += tempPoly->ItemCount;}tempPoly->FirstItem = NULL;tempPoly->LastItem = NULL;tempPoly->ItemCount = 0;p = p->next;}return Poly;}流转的时光，都成为命途中美丽的点缀，
