数据结构 稀疏多项式:各项的最高次幂相差很大,很稀疏的意思。
struct PolyTerm{ int coef; int exp; }; struct SqPoly{ PolyTerm *data; int last; }; float GetValue_SqPoly(SqPoly P,int x0)//求升幂顺序存储的稀疏多项式的值 { float exx=1.0,sum=0; int ex=0; PolyTerm *p=P.data; while(p->coef) { while(ex<p->exp) { exx*=x0; ++ex; } sum+=p->coef*exx; ++p; } return sum; }//时间复杂度O(m*e(m)) void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly &P3)//求稀疏多项式 P1 减 P2 的差式 P3 { PolyTerm *p,*q,*r; p=P1.data;q=P2.data;r=P3.data; while(p->coef&&q->coef) { if(p->exp<q->exp) { r->coef=p->coef; r->exp=p->exp; p++;r++; } else if(p->exp<q->exp) { r->coef=-q->coef; r->exp=q->exp; q++;r++; } else { if((p->coef-q->coef)!=0) //只有同次项相减不为零时才需要存入 P3 中 { r->coef=p->coef-q->coef; r->exp=p->exp;r++; }//if p++;q++; }//else }//while while(p->coef) //处理 P1 或 P2 的剩余项 { r->coef=p->coef; r->exp=p->exp; p++;r++; } while(q->coef) { r->coef=-q->coef; r->exp=q->exp; q++;r++; } }//Subtract_SqPoly
typedef struct PolyNode { PolyTerm data; struct PolyNode *next; } PolyNode, *PolyLink; typedef PolyLink LinkedPoly; void QiuDao_LinkedPoly(LinkedPoly &L)//对有头结点循环链表结构存储的稀疏多项式 L 求导 { PolyNode *p=L->next; if(!p->data.exp) { L->next=p->next;p=p->next; //跳过常数项 } while(p!=L) { p->data.coef*=p->data.exp--;//对每一项求导 p=p->next; } }//QiuDao_LinkedPoly void Divide_LinkedPoly(LinkedPoly &L,LinkedPoly &A,LinkedPoly &B)//把循环链表存储的稀疏多项式 L 拆成只含奇次项的 A 和只含偶次项的 B { PolyNode *p=L->next; A=(PolyNode*)malloc(sizeof(PolyNode)); B=(PolyNode*)malloc(sizeof(PolyNode)); PolyNode *pa=A;PolyNode *pb=B; while(p!=L) { if(p->data.exp!=2*(p->data.exp/2)) { pa->next=p;pa=p; } else { pb->next=p;pb=p; } p=p->next; }//while pa->next=A;pb->next=B; }//Divide_LinkedPoly