题目说明：

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

输入：

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

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

输出：

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

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

说明：本题目有预设代码，只要提交你编写的函数即可。

预设代码

前置代码

/* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */  #include <stdio.h>  
#include <stdlib.h>  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,0>,<3,1>,<3,2>,<1,3>,↵	1秒	1024KB	0
测试用例 2	以文本方式显示 <0,0>,↵ <1,20>,<-8,40>,↵	以文本方式显示 <0,0>,↵	1秒	1024KB	0
测试用例 3	以文本方式显示 <1,20>,<-8,40>,↵ <0,0>,↵	以文本方式显示 <0,0>,↵	1秒	1024KB	0
测试用例 4	以文本方式显示 <-1,0>,<1,1>,↵ <1,0>,<1,1>,↵	以文本方式显示 <-1,0>,<1,2>,↵	1秒	1024KB	0
测试用例 5	以文本方式显示 <5,0>,<10,1>,↵ <2,0>,<3,1>,<4,2>,<5,3>,↵	以文本方式显示 <10,0>,<35,1>,<50,2>,<65,3>,<50,4>,↵	1秒	1024KB	0

 

void multiplication(NODE * h1, NODE * h2, NODE * h3)  
{  int coefp,expp;  NODE *p1 = h1, *p2 = h2, *p3 = h3;  int exist0=0;  while (p1->next != NULL)   {  start: if(p1->next==NULL) break;  p1 = p1->next;  if (p1->coef == 0 && exist0)continue;  //已出现零项   p2 = h2;  p3 = h3;   //回到起点   while (p2->next != NULL) //与h2链逐项相乘  {  p2 = p2->next;  coefp = p1->coef * p2->coef;  expp = p1->exp + p2->exp;        //计算乘积的系数和指数   if (coefp == 0 && exist0)continue;  //已出现零项   NODE *per;  while (p3 != NULL)   {  per = p3;  p3 = p3->next;  if (p3 == NULL|| expp< p3->exp)    {  NODE *insert = (NODE*)malloc(sizeof(NODE));  if (coefp == 0 && !exist0) //零项   {  insert->exp = 0;  exist0=1;  insert->coef = coefp;  insert->next = p3; //插到前面   per->next = insert;  p3 = per;  goto start;  // 跳过   }  else insert->exp = expp;  insert->coef = coefp;  insert->next = p3; //插到前面   per->next = insert;  p3 = per;  break;  }  if (expp > p3->exp)continue;  if (p3->exp == expp) {  p3->coef += coefp;  if (p3->coef == 0 && expp != 0)//系数等于0则删除（不删<0,0>）   {  per->next = p3->next;  free(p3);  }  p3 = per;  break;  }  }  }  }  
}