2.一元多项式相乘

蔚落 2022-04-06 04:56 245阅读 0赞

## 2.一元多项式相乘 ##

### 题目说明： ###

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

### 输入： ###

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

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

### 输出： ###

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

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

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

### 预设代码 ###

前置代码

[view plain][][print][view plain][?][view plain]

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;
8.  struct node \*next;
9.  \} NODE;
10. 
11. void multiplication( NODE \*, NODE \* , NODE \* );
12. void input( NODE \* );
13. void output( NODE \* );
14. 
15. void input( NODE \* head )
16. \{ int flag, sign, sum, x;
17. char c;
18. 
19. NODE \* p = head;
20. 
21. while ( (c=getchar()) !='\\n' )
22. \{
23. if ( c == '<' )
24. \{ sum = 0;
25. sign = 1;
26. flag = 1;
27. \}
28. else if ( c =='-' )
29. sign = -1;
30. else if( c >='0'&& c <='9' )
31. \{ sum = sum\*10 + c - '0';
32. \}
33. else if ( c == ',' )
34. \{ if ( flag == 1 )
35. \{ x = sign \* sum;
36. sum = 0;
37. flag = 2;
38. sign = 1;
39. \}
40. \}
41. else if ( c == '>' )
42. \{ p->next = ( NODE \* ) malloc( sizeof(NODE) );
43. p->next->coef = x;
44. p->next->exp = sign \* sum;
45. p = p->next;
46. p->next = NULL;
47. flag = 0;
48. \}
49. \}
50. \}
51. 
52. void output( NODE \* head )
53. \{
54. while ( head->next != NULL )
55. \{ head = head->next;
56. printf("<%d,%d>,", head->coef, head->exp );
57. \}
58. printf("\\n");
59. \}
60. 
61. int main()
62. \{ NODE \* head1, \* head2, \* head3;
63. 
64. head1 = ( NODE \* ) malloc( sizeof(NODE) );
65. input( head1 );
66. 
67. head2 = ( NODE \* ) malloc( sizeof(NODE) );
68. input( head2 );
69. 
70. head3 = ( NODE \* ) malloc( sizeof(NODE) );
71. head3->next = NULL;
72. multiplication( head1, head2, head3 );
73. 
74. output( head3 );
75. return 0;
76. \}
77. 
78. /\* PRESET CODE END - NEVER TOUCH CODE ABOVE \*/

#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");  
    }  
      
    void multiplication(NODE *head1, NODE *head2, NODE *head3){
        NODE *p1, *p2, *p3,*p3_pre, *pnew, *start;
        int flag = 0;//x为系数 y为指数
        p1 = head1->next;
        while(p1 != NULL){
            p2 = head2->next;
            start = head3;
            while(p2 != NULL){
                pnew = (NODE *)malloc(sizeof(NODE));
                pnew->coef = p2->coef * p1->coef;
                pnew->exp = p2->exp + p1->exp;
                if(pnew->coef == 0){
                    p2 = p2->next;
                    continue;
                }
                flag = 0;
                p3 = start->next;
                p3_pre = start;
                while(p3 != NULL){
                    if(p3->exp < pnew->exp){
                        p3 = p3->next;
                        p3_pre = p3_pre->next;
                        continue;
                    }
                    else if(p3->exp == pnew->exp){
                        p3->coef += pnew->coef;
                        if(p3->coef == 0){
                            p3_pre->next = p3->next;
                        }
                        start = p3_pre;
                        flag = 1;
                        break;
                    }
                    else{
                        p3_pre->next = pnew;
                        pnew->next = p3;
                        flag = 1;
                        start = p3_pre;
                        break;
                    }
                }
                if(flag == 0){
                    p3_pre->next = pnew;
                    pnew->next = NULL;
                    start = p3_pre;
                }
                p2 = p2->next;
            }
            p1 = p1->next;
        }
        if(head3->next == NULL){
            pnew = (NODE *)malloc(sizeof(NODE));
            pnew->coef = 0;
            pnew->exp = 0;
            head3->next = pnew;
            pnew->next = NULL;
        }
    }
    
    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;  
    }

[view plain]: http://online.bit.edu.cn/moodle/mod/programming/view.php?id=77899#