学步园

/*
一元多项式求乘积
*/

#include<stdio.h>
#include<time.h>
#include<stdlib.h>

void init_num(int x[],int y[])
{
 /*
 int i;
 srand( (unsigned)time( NULL ) );
 for(i=0;i<65536;i++)
 {
  srand( (unsigned)time( NULL ) );
  x[i]=rand();
  srand( (unsigned)time( NULL ) );
  y[i]=rand();
 }*/

 
}

void show(int a[],int MaxLen)
{
 int i;
 int first=0;
 for(i=0;i<=MaxLen;i++)
 {
  if(a[i]!=0)
  {
   if(i!=MaxLen)
   {
    if(first==0)
    {
     first++;
     printf("%dX(%d)",a[i],i);
    }
    else
    {
     printf(" + %dX(%d) ",a[i],i);
    }
   }

  }
 }
 printf("/n");
}

/*采用数组存储一元多项式*/
void method_one(int a[], int b[],int c[],int MaxLen_a,int MaxLen_b) //MaxLen只带
{
 int i,j;
 for(i=0;i<=MaxLen_a;i++)
 {
  for(j=0;j<=MaxLen_b;j++)
  {
   c[i+j] += a[i]*b[j];
  }
 }
}

/*第二种存储方式，采用链表*/
struct Node
{
 int x;//指示x的幂
 int coff;
 struct Node *next;
};

struct Node *Creat_Node(int x,int coff)
{
 struct Node *node=(struct Node *)malloc(sizeof(struct Node)) ;
 node->coff=coff;
 node->x=x;
 node->next=NULL;
 return node;
}
//int a[4]={1,0,3,0};
struct Node * init_a(void)
{
 struct Node *first;
 first=Creat_Node(0,1);
 first->next=Creat_Node(2,3);
 return first;
}
//int b[4]={0,3,2,1};
struct Node * init_b(void)
{
 struct Node *first;
 first=Creat_Node(1,3);
 first->next=Creat_Node(2,2);
 first->next->next=Creat_Node(3,1);
 return first;
}

void show_link(struct Node *node)
{
 int first=0;
 struct Node *p=node;
 while( p!=NULL  )
 {
  if(p->coff!=0)
  {
   if(first==0)
   {
    first=1;
    printf("%dX(%d)",p->coff,p->x);
   }
   else
   {
    printf(" + %dX(%d) ",p->coff,p->x);
   }
  }
  p=p->next;
 }
 printf("/n");
}

struct Node * mul(struct Node * a,struct Node * b)
{
 struct Node * first;
 struct Node *p1,*p2;
 
 first=Creat_Node(0,0);
 p1=a;
 while(p1!=NULL)
 {
  p2=b;
  while(p2!=NULL)
  {
   
   {
    int M=p1->x+p2->x;
    int COFF=p1->coff*p2->coff;
    struct Node *p=first;
    for(; p->next!=NULL;p=p->next)
    {
     if(p->x==M)
     {
      p->coff +=COFF;
     }
    }
    if(p->next==NULL)
    {
     if(p->x==M)
     {
      p->coff +=COFF;
     }
     else
     {
      p->next=Creat_Node(M,COFF);
     }
    }
    
   }
   p2=p2->next;
  }
  p1=p1->next;
 }
 
 return first;
}

int main()
{
 clock_t start,finish;
 double difTime;
 
 int a[4]={1,2,3,0};
 int b[4]={2,3,4,1};
 int c[7]={0};

 struct Node *a1,*a2,*a3;
 method_one(a,b,c,3,3);
 show(a,3);
 show(b,3);
 show(c,6);

 a1=init_a();
 show_link(a1);
 a2=init_b();
 show_link(a2);
 a3=mul(a1,a2);
 show_link(a3);

 start=clock();

 finish=clock();
 difTime=(double)(finish-start)/CLOCKS_PER_SEC;
 printf("use %f secons/n",difTime);

 
 return 0;
}