poly.cpp

我们计算机科学学院教授上数据结构的课件

#include <iostream.h>
#include <stdlib.h>

typedef struct node
{
  float coef;
  int expn;
  struct node *next;
}PolyNode;

void InitList(PolyNode *&sq)
{
   sq=(PolyNode *)malloc(sizeof(PolyNode));
   sq->next=NULL;
}

int GetLength(PolyNode *sq)
{
  int i=0;
  PolyNode *p=sq->next;
  while(p!=NULL)
  {
    i++;
    p=p->next;
  }
  return i;
}

PolyNode *GetElem(PolyNode *sq,int i)
{
  int j=1;
  PolyNode *p=sq->next;
  if (i<1 || i>GetLength(sq))
    return NULL;
  while(j<i)
  {
    p=p->next;
    j++;
  }
  return p;
}

PolyNode *Locate(PolyNode *sq,float c,int e)
{
   PolyNode *p=sq->next;
   while (p!=NULL && (p->coef!=c || p->expn!=e))
     p=p->next;
   return p;
}

int InsElem(PolyNode *sq,float c,int e,int i)
{
  int j=1;
  PolyNode *p=sq,*s;
  s=(PolyNode *)malloc(sizeof(PolyNode));
  s->coef=c;
  s->expn=e;
  s->next=NULL;
  if (i<1 || i>GetLength(sq)+1)
    return 0;
  while(j<i)
  {
    p=p->next;
    j++;
  }
  s->next=p->next;
  p->next=s;
  return 1;
}

int DelElem(PolyNode *sq,int i)
{
  int j=1;
  PolyNode *p=sq,*q;
  if(i<1 || i>GetLength(sq))
    return 0;
  while(j<i)
  {
    p=p->next;
    j++;
  }
  q=p->next;
  p->next=q->next;
  free(q);
  return 1;
}

void DispList(PolyNode *sq)
{
  PolyNode *p=sq->next;
  while(p!=NULL)
  {
    cout<<"("<<p->coef<<","<<p->expn<<") "<<endl;
    p=p->next;
  }
  cout<<endl;
}

//若多项式 系数和指数 分别放在数组 C[]和E[]中，创建多项式单链表算法
void CreatePoly(PolyNode *&sq,float c[],int e[],int n)
{
  int i;
  InitList(sq);
  for(i=0;i<n;i++)
    InsElem(sq,c[i],e[i],i+1);
}

// 多项式单链表 排序 （插入排序）
void SortPoly(PolyNode *&sq)
{
  PolyNode *p=sq->next,*q,*pre;
  sq->next=NULL;
  while (p!=NULL)
  {
    if(sq->next==NULL)   //处理第一个结点
    {
      sq->next=p;p=p->next;
      sq->next->next=NULL;
    }
    else
    {
      pre=sq;q=pre->next;
      while(q!=NULL && p->expn>q->expn)
      {
        pre=q; q=q->next;
      }
      q=p->next;
      p->next=pre->next;
      pre->next=p;
      p=q;
    }
  }
}

//多项式  加
PolyNode *AddPoly(PolyNode *pa,PolyNode *pb)
{
  PolyNode *pc,*p1=pa->next,*p2=pb->next,*p,*tc,*s;
  pc=(PolyNode *)malloc(sizeof(PolyNode));
  pc->next=NULL;
  tc=pc;
  while(p1!=NULL && p2!=NULL)
  {
    if(p1->expn<p2->expn)
    {
      s=(PolyNode *)malloc(sizeof(PolyNode));
      s->coef=p1->coef;
      s->expn=p1->expn;
      s->next=NULL;
      tc->next=s;
      tc=s;
      p1=p1->next;
    }
    else if(p1->expn>p2->expn)
         {
            s=(PolyNode *)malloc(sizeof(PolyNode));
            s->coef=p2->coef;
            s->expn=p2->expn;
            s->next=NULL;
            tc->next=s;
            tc=s;
            p2=p2->next;
          }
          else
          {
            if (p1->coef+p2->coef!=0)
            {
              s=(PolyNode *)malloc(sizeof(PolyNode));
              s->coef=p1->coef+p2->coef;
              s->expn=p1->expn;
              s->next=NULL;
              tc->next=s;
              tc=s;
             }
             p1=p1->next;
             p2=p2->next;
          }
  }
  if (p1!=NULL)
    p=p1;
  else
    p=p2;
  while(p!=NULL)
  {
    s=(PolyNode *)malloc(sizeof(PolyNode));
    s->coef=p->coef;
    s->expn=p->expn;
    s->next=NULL;
    tc->next=s;
    tc=s;
    p=p->next;
  }
  tc->next=NULL;
  return pc;
}


int main()
{
   PolyNode *sq1,*sq2,*sq3;
   float c1[]={3,7,5,9},c2[]={-9,8,22};
   int e1[]={1,0,17,8},e2[]={8,1,7};
   CreatePoly(sq1,c1,e1,4);
   CreatePoly(sq2,c2,e2,3);

   cout<<"A:  ";
   DispList(sq1);

   cout<<"B:  ";
   DispList(sq2);

   SortPoly(sq1);
   SortPoly(sq2);

   sq3=AddPoly(sq1,sq2);
   cout<<"Result:  ";
   DispList(sq3);
      system("PAUSE");
      return 0;
}