数据结构 8.一元多项式相乘

数据结构 8.一元多项式相乘

• 问题描述
• • 输入
  • 输出
  • 预设代码
• 样例
• • 输入（1）
  • 输出（1）
  • 输入（2）
  • 输出（2）
  • 输入（3）
  • 输出（3）
  • 输入（4）
  • 输出（4）
  • 输入（5）
  • 输出（5）
• 代码

问题描述

要求采用链表形式，求两个一元多项式的乘积：h3 = h1*h2。函数原型为：void multiplication( NODE * h1, NODE * h2, NODE * h3 )。

输入

输入数据为两行，分别表示两个一元多项式。每个一元多项式以指数递增的顺序输入多项式各项的系数（整数）、指数（整数）。

例如： 1 + 2 x + x 2 1+2x+x^2 1+2x+x2表示为：<1,0>,<2,1>,<1,2>,

输出

以指数递增的顺序输出乘积： <系数,指数>,<系数,指数>,<系数,指数>,

零多项式的输出格式为：<0,0>,

预设代码

/* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */  #include   
#include   typedef struct node  
{   int    coef, exp;  struct node  *next;  
} NODE;  void multiplication( NODE *, NODE * , NODE * );  
void input( NODE * );  
void output( NODE * );  void input( NODE * head )  
{   int flag, sign, sum, x;  char c;  NODE * p = head;  while ( (c=getchar()) !='\n' )  {  if ( c == '<' )  {    sum = 0;  sign = 1;  flag = 1;  }  else if ( c =='-' )  sign = -1;  else if( c >='0'&& c <='9' )  {    sum = sum*10 + c - '0';  }  else if ( c == ',' )  {    if ( flag == 1 )  {    x = sign * sum;  sum = 0;  flag = 2;  sign = 1;  }  }  else if ( c == '>' )  {    p->next = ( NODE * ) malloc( sizeof(NODE) );  p->next->coef = x;  p->next->exp  = sign * sum;  p = p->next;  p->next = NULL;  flag = 0;  }  }  
}  void output( NODE * head )  
{  while ( head->next != NULL )  {   head = head->next;  printf("<%d,%d>,", head->coef, head->exp );  }  printf("\n");  
}  int main()  
{   NODE * head1, * head2, * head3;  head1 = ( NODE * ) malloc( sizeof(NODE) );  input( head1 );  head2 = ( NODE * ) malloc( sizeof(NODE) );  input( head2 );  head3 = ( NODE * ) malloc( sizeof(NODE) );  head3->next = NULL;  multiplication( head1, head2, head3 );  output( head3 );  return 0;  
}  /* PRESET CODE END - NEVER TOUCH CODE ABOVE */

样例

输入（1）

<1,0>,<2,1>,<1,2>,
<1,0>,<1,1>,

输出（1）

<1,0>,<3,1>,<3,2>,<1,3>,

输入（2）

<0,0>,
<1,20>,<-8,40>,

输出（2）

<0,0>,

输入（3）

<1,20>,<-8,40>,
<0,0>,

输出（3）

<0,0>,

输入（4）

<-1,0>,<1,1>,
<1,0>,<1,1>,

输出（4）

<-1,0>,<1,2>,

输入（5）

<5,0>,<10,1>,
<2,0>,<3,1>,<4,2>,<5,3>,

输出（5）

<10,0>,<35,1>,<50,2>,<65,3>,<50,4>,

代码

void multiplication(NODE *head1, NODE *head2, NODE *head3)    
{    NODE *p1, *p2, *p3,*p3_pre, *pnew, *start;    int flag = 0;  p1=head1->next;    while(p1)    {    p2=head2->next;    int c1;    c1=p1->coef;    if(c1==0)    {    p1=p1->next;    continue;    }    start=head3;    while(p2)    {    flag=0;    pnew=(NODE *)malloc(sizeof(NODE));    int c,e;    c=p2->coef*p1->coef;    e=p2->exp+p1->exp;    pnew->coef=c;    pnew->exp=e;    int c2;    c2=p2->coef;    if(c2==0)    {    p2 = p2->next;    continue;    }    p3=start->next;    p3_pre=start;    while((p3)&&(p3->exp<e))    {    p3=p3->next;    p3_pre=p3_pre->next;    }    if(!p3)    {    p3_pre->next=pnew;    pnew->next=NULL;    start=p3_pre;    }    else if(p3->exp==e)    {    p3->coef=c+p3->coef;;    start=p3_pre;    }    else if(p3->exp>e)    {    p3_pre->next=pnew;    pnew->next=p3;    start=p3_pre;    }    p2=p2->next;    }    p1=p1->next;    }    if(head3->next==NULL)    {    printf("<0,0>,");    }    NODE *tmp;    p3=head3;    while(p3)     {       if(p3->coef==0&&p3->exp!=0)    {     p3=tmp;     p3->next=p3->next->next;      p3=p3->next;     }     else    {       tmp=p3;     p3=p3->next;     }     }     
}  

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！