【线性表】一元多项式相乘

  1 /* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */
  2 
  3 #include <stdio.h>
  4 #include <stdlib.h>
  5 
  6 typedef struct node
  7 {   int    coef, exp;           //coef：系数     exp：指数
  8     struct node  *next;         //下一项
  9 } NODE;
 10 
 11 NODE* multiplication( NODE *, NODE * , NODE * );
 12 void input( NODE * );
 13 void output( NODE * );
 14 
 15 int main()
 16 {   NODE * head1, * head2, * head3;
 17 
 18     head1 = ( NODE * ) malloc( sizeof(NODE) );
 19     input( head1 );
 20 
 21     head2 = ( NODE * ) malloc( sizeof(NODE) );
 22     input( head2 );
 23 
 24     head3 = ( NODE * ) malloc( sizeof(NODE) );
 25     head3->next = NULL;
 26     head3 = multiplication( head1, head2, head3 );
 27     output( head3 );
 28 
 29     return 0;
 30 }
 31 /* PRESET CODE END - NEVER TOUCH CODE ABOVE */
 32 void input( NODE * head )      //输入顺序：<   -   0~9   ,    >
 33 {   int flag, sign, sum, x;    //sign：系数符号     sum：项系数,指数
 34     char c;
 35 
 36     NODE * p = head;
 37 
 38     while ( (c=getchar()) !=‘\n‘ )
 39     {
 40         if ( c == ‘<‘ )
 41         {    sum = 0;
 42              sign = 1;
 43              flag = 1;
 44         }
 45         else if ( c ==‘-‘ )
 46              sign = -1;
 47         else if( c >=‘0‘&& c <=‘9‘ )
 48         {    sum = sum*10 + c - ‘0‘;
 49         }
 50         else if ( c == ‘,‘ )
 51         {    if ( flag == 1 )
 52              {    x = sign * sum;
 53                   sum = 0;
 54                   flag = 2;
 55                   sign = 1;
 56              }
 57         }
 58         else if ( c == ‘>‘ )
 59         {    p->next = ( NODE * ) malloc( sizeof(NODE) );
 60              p->next->coef = x;                            //项系数
 61              p->next->exp  = sign * sum;                //指数
 62              p = p->next;
 63              p->next = NULL;
 64              flag = 0;
 65         }
 66     }
 67 }
 68 void output( NODE * head )
 69 {
 70     while ( head->next != NULL )
 71     {   head = head->next;
 72         printf("<%d,%d>,", head->coef, head->exp );
 73     }
 74     printf("\n");
 75 }
 76 NODE* multiplication( NODE *h1, NODE *h2 , NODE *h3 )//不允许修改指针内容
 77 {
 78     NODE *head1, *head2, *head3,*head;//head临时头指针
 79     int max_exp = 0,count_exp = 0;
 80     head1 = h1;
 81     head2 = h2;
 82     head3 = h3;
 83     while(head1->next!=NULL){
 84         while(head2->next!=NULL){
 85             head3->next = (NODE *) malloc(sizeof(NODE));
 86             head3->next->coef = head1->next->coef*head2->next->coef;
 87             head3->next->exp = head1->next->exp+head2->next->exp;
 88             head2 = head2->next;
 89             head3 = head3->next;
 90             head3->next = NULL;
 91             if(head3->exp>max_exp)            //记录最大指数
 92                 max_exp = head3->exp;
 93         }
 94         head2 = h2;      //返回头指针
 95         head1 = head1->next;
 96     }
 97     //合并指数相同的多项式
 98     head = (NODE *)malloc(sizeof(NODE));
 99     head->next = (NODE*)malloc(sizeof(NODE));
100     head3 = h3;             //返回头指针
101     head1 = head;
102     for(count_exp = 0;count_exp<=max_exp;count_exp++){
103         head->next->coef = 0;
104         head->next->exp = count_exp;
105         while(head3->next!=NULL){
106             if(count_exp == head3->next->exp)
107                 head->next->coef += head3->next->coef;
108             head3 = head3->next;
109         }
110         //零多项式标志位
111         if(head->next->coef != 0){
112             head = head->next;
113             head->next = (NODE*)malloc(sizeof(NODE));
114         }
115         head3 = h3;             //返回头指针
116     }
117     head->next = NULL;
118     return head1;
119 }
120 
121 
122