现在的位置: 首页 > 综合 > 正文

数据结构题集(严蔚敏)2.39 稀疏多项式

2019年02月07日 ⁄ 综合 ⁄ 共 1484字 ⁄ 字号 评论关闭

数据结构  稀疏多项式:各项的最高次幂相差很大,很稀疏的意思。

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 





【上篇】
【下篇】

抱歉!评论已关闭.