一元多项式相乘

r囧r小猫 2022-06-02 08:56 220阅读 0赞

### 题目说明： ###

要求采用链表形式，求两个一元多项式的乘积：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. 
76. **return** 0; 
77. \} 
78. 
79. /\* PRESET CODE END - NEVER TOUCH CODE ABOVE \*/

<table style="width:1615px; margin-bottom:20px; background-color:transparent"> 
 <thead> 
  <tr> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> &nbsp;</th> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 测试输入<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=input&amp;lang=zh_cn" title="关于“测试输入”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“测试输入”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></span></th> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 期待的输出<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=expectedoutput&amp;lang=zh_cn" title="关于“期待的输出”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“期待的输出”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></span></th> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 时间限制<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=timelimit&amp;lang=zh_cn" title="关于“时间限制”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“时间限制”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></span></th> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 内存限制<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=memlimit&amp;lang=zh_cn" title="关于“内存限制”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“内存限制”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></span></th> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 额外进程<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=nproc&amp;lang=zh_cn" title="关于“{$a} 个额外进程”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“{$a} 个额外进程”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></span></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 测试用例 1</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64753&amp;test=82419&amp;type=in&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
     <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">&lt;1,0&gt;,&lt;2,1&gt;,&lt;1,2&gt;,↵</span></li> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">&lt;1,0&gt;,&lt;1,1&gt;,↵</span></li> 
     </ol> 
    </div> </td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64753&amp;test=82419&amp;type=out&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
     <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">&lt;1,0&gt;,&lt;3,1&gt;,&lt;3,2&gt;,&lt;1,3&gt;,↵</span></li> 
     </ol> 
    </div> </td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 1秒</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 1024KB</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 0</td> 
  </tr> 
  <tr> 
   <td style="padding:4px; line-height:20px; vertical-align:middle"> 测试用例 2</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64753&amp;test=82420&amp;type=in&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
     <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">&lt;0,0&gt;,↵</span></li> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">&lt;1,20&gt;,&lt;-8,40&gt;,↵</span></li> 
     </ol> 
    </div> </td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64753&amp;test=82420&amp;type=out&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
     <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">&lt;0,0&gt;,↵</span></li> 
     </ol> 
    </div> </td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle"> 1秒</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle"> 1024KB</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle"> 0</td> 
  </tr> 
  <tr> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 测试用例 3</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64753&amp;test=82421&amp;type=in&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
     <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">&lt;1,20&gt;,&lt;-8,40&gt;,↵</span></li> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">&lt;0,0&gt;,↵</span></li> 
     </ol> 
    </div> </td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64753&amp;test=82421&amp;type=out&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
     <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">&lt;0,0&gt;,↵</span></li> 
     </ol> 
    </div> </td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 1秒</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 1024KB</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 0</td> 
  </tr> 
  <tr> 
   <td style="padding:4px; line-height:20px; vertical-align:middle"> 测试用例 4</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64753&amp;test=82422&amp;type=in&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
     <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">&lt;-1,0&gt;,&lt;1,1&gt;,↵</span></li> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">&lt;1,0&gt;,&lt;1,1&gt;,↵</span></li> 
     </ol> 
    </div> </td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64753&amp;test=82422&amp;type=out&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
     <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">&lt;-1,0&gt;,&lt;1,2&gt;,↵</span></li> 
     </ol> 
    </div> </td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle"> 1秒</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle"> 1024KB</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle"> 0</td> 
  </tr> 
  <tr> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 测试用例 5</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64753&amp;test=82423&amp;type=in&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
     <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">&lt;5,0&gt;,&lt;10,1&gt;,↵</span></li> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">&lt;2,0&gt;,&lt;3,1&gt;,&lt;4,2&gt;,&lt;5,3&gt;,↵</span></li> 
     </ol> 
    </div> </td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64753&amp;test=82423&amp;type=out&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
     <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">&lt;10,0&gt;,&lt;35,1&gt;,&lt;50,2&gt;,&lt;65,3&gt;,&lt;50,4&gt;,↵</span></li> 
     </ol> 
    </div> </td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 1秒</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 1024KB</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 0</td> 
  </tr> 
 </tbody> 
</table>

void multiplication(NODE *head1, NODE *head2, NODE *head3) 
    { 
       NODE*p1 = head3; NODE*p2 = head3; 
      NODE*h1 = head1->next; NODE*h2 = head2->next; 
         
       while (h1) 
     { 
          while (h2) 
         { 
              int coef = h1->coef*h2->coef; 
                if (coef == 0) 
             { 
                  h2 = h2->next; 
                  continue; 
              } 
              int exp = h1->exp+h2->exp; 
               if (p1->next == NULL) 
               { 
                  NODE*tmp = (NODE*)malloc(sizeof(struct node)); 
                 tmp->coef = coef; tmp->exp = exp; 
                    p1->next = tmp; 
                 tmp->next = NULL; 
               } 
              else 
               { 
                  while (p2->next&&exp>p2->next->exp) 
                    { 
                      p2 = p2->next; 
                  } 
                  NODE*tmp = p2->next; 
                    if (p2->next == NULL) 
                   { 
                      NODE*pnew = (NODE*)malloc(sizeof (struct node)); 
                       pnew->coef = coef; 
                      pnew->exp = exp; 
                        p2->next = pnew; 
                        pnew->next = NULL; 
                  } 
                  else if (tmp->exp == exp) 
                   { 
                      tmp->coef += coef; 
                      if (tmp->coef == 0) 
                     { 
                          NODE*mark = tmp->next; 
                          p2->next = mark; 
                            free(tmp); 
                     } 
                  } 
                  else if (tmp->exp > exp) 
                 { 
                      NODE*pnew = (NODE*)malloc(sizeof (struct node)); 
                       pnew->coef = coef; 
                      pnew->exp = exp; 
                        p2->next = pnew; 
                        pnew->next = tmp; 
                   } 
     
             } 
              h2 = h2->next; 
              p2 = head3; 
            } 
          h2 = head2->next; 
           h1 = h1->next; 
      } 
      if (head3->next==NULL) 
      { 
          NODE*end = (NODE*)malloc(sizeof(struct node)); 
         end->coef = 0; 
          end->exp = 0; 
           end->next = head3->next; 
         head3->next = end; 
      } 
    }

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