一元多项式相加

Bertha 。 2022-06-02 08:55 169阅读 0赞

### 题目说明： ###

编写一元多项式加法运算程序。要求用线性链表存储一元多项式（参照课本）。该程序有以下几个功能：

1. 多项式求和

输入：输入三个多项式，建立三个多项式链表Pa、Pb、Pc

（提示：调用CreatePolyn(polynomial &P,int m)。

输出：显示三个输入多项式Pa、Pb、Pc、和多项式Pa+Pb、多项式Pa+Pb+Pc

（提示：调用AddPolyn(polynomial &Pa, polynomial Pb), 调用PrintPolyn(polynomial P))。

0. 退出

### 输入： ###

根据所选功能的不同，输入格式要求如下所示（第一个数据是功能选择编号，参见测试用例）：

*  1

多项式A包含的项数，以指数递增的顺序输入多项式A各项的系数（整数）、指数（整数）

多项式B包含的项数，以指数递增的顺序输入多项式B各项的系数（整数）、指数（整数）

多项式C包含的项数，以指数递增的顺序输入多项式C各项的系数（整数）、指数（整数）

*  0 －－－操作终止，退出。

### 输出： ###

对应一组输入，输出一次操作的结果（参见测试用例）。

*  1 多项式输出格式：以指数递增的顺序输出: <系数,指数>,<系数,指数>,<系数,指数>,参见测试用例。零多项式的输出格式为<0,0>
 *  0 无输出

<table style="color:rgb(68,68,68); font-size:13px; line-height:25px; 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=64756&amp;test=82445&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)">1↵</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)">2↵</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)">1&nbsp;1&nbsp;2&nbsp;2↵</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)">2↵</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)">1&nbsp;1&nbsp;2&nbsp;2↵</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)">2↵</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)">1&nbsp;1&nbsp;2&nbsp;2↵</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=64756&amp;test=82445&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,1&gt;,&lt;2,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,1&gt;,&lt;2,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,1&gt;,&lt;2,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;2,1&gt;,&lt;4,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;3,1&gt;,&lt;6,2&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=64756&amp;test=82446&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)">1↵</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)">2↵</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)">6&nbsp;3&nbsp;8&nbsp;6↵</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)">2↵</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)">3&nbsp;4&nbsp;4&nbsp;8↵</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)">3↵</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)">1&nbsp;1&nbsp;5&nbsp;5&nbsp;9&nbsp;9↵</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=64756&amp;test=82446&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;6,3&gt;,&lt;8,6&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;3,4&gt;,&lt;4,8&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,1&gt;,&lt;5,5&gt;,&lt;9,9&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;6,3&gt;,&lt;3,4&gt;,&lt;8,6&gt;,&lt;4,8&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,1&gt;,&lt;6,3&gt;,&lt;3,4&gt;,&lt;5,5&gt;,&lt;8,6&gt;,&lt;4,8&gt;,&lt;9,9&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=64756&amp;test=82447&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)">1↵</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)">2↵</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)">1&nbsp;1&nbsp;2&nbsp;2↵</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)">2↵</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)">-1&nbsp;1&nbsp;-2&nbsp;2↵</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)">2↵</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)">1&nbsp;1&nbsp;2&nbsp;2↵</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=64756&amp;test=82447&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,1&gt;,&lt;2,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,1&gt;,&lt;-2,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,1&gt;,&lt;2,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;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,1&gt;,&lt;2,2&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>

#include<stdio.h> 
    #include<stdlib.h> 
    #define LEN sizeof(struct node) 
    typedef struct node 
    { 
     int coef; 
      int exp; 
       struct node *next; 
    }*polynomial, Polynomial; 
     
    CreatePolyn(polynomial P, int m) 
    { 
       polynomial p1=P; 
       for (int i = 0; i < m; i++) 
     { 
          polynomial pnew = (polynomial)malloc(LEN); 
         scanf("%d %d", &pnew->coef, &pnew->exp); 
         p1->next = pnew; 
            p1 = pnew; 
     } 
      p1->next = NULL; 
    } 
     
     
    PrintPolyn(polynomial P) 
    { 
     polynomial tmp = P->next; 
       if (tmp== NULL) 
        { 
          printf("<0,0>\n"); 
       } 
      else 
       { 
          while (tmp->next) 
           { 
              printf("<%d,%d>,", tmp->coef, tmp->exp); 
               tmp = tmp->next; 
            } 
          printf("<%d,%d>\n", tmp->coef, tmp->exp); 
      } 
    } 
     
    AddPolyn(polynomial Pa, polynomial Pb) 
    { 
      polynomial ha = Pa, hb = Pb, qa = ha->next, qb = hb->next; int a, b; 
     while (qa&&qb) 
     { 
          a = qa->exp, b = qb->exp; 
            if (a < b) 
          { 
              ha = qa; qa = qa->next; 
         } 
          else if (a == b) 
           { 
              int sum = qa->coef+ qb->coef; 
                if (sum != 0) 
              { 
                  qa->coef = sum; ha = qa; 
                } 
              else 
               { 
                  ha->next = qa->next; free(qa); 
               } 
              hb->next = qb->next; free(qb); qb = hb->next; qa = ha->next; 
           } 
          else if (a>b) 
           { 
              hb->next = qb->next;  
                ha->next = qb;  
             qb->next = qa;  
             qb = hb->next;  
             ha = ha->next; 
          } 
      } 
      if (qb != NULL) 
        { 
     
         while (qb != NULL) 
         { 
              polynomial pnew = (polynomial)malloc(LEN); 
             pnew->coef = qb->coef; 
               pnew->exp = qb->exp; 
             pnew->next = NULL; 
              ha->next = pnew; 
                ha = ha->next; 
              qb = qb->next; 
          } 
      } 
    } 
     
    int main() 
    { 
      //freopen("5.txt", "r", stdin); 
        int cmd; int num; 
      while (scanf("%d", &cmd) != EOF) 
       { 
          if (cmd == 0) 
              break; 
         Polynomial pa, pb, pc; 
         pa.next = NULL, pb.next = NULL, pc.next = NULL; 
            scanf("%d", &num); CreatePolyn(&pa, num); 
          scanf("%d", &num); CreatePolyn(&pb, num); 
          scanf("%d", &num); CreatePolyn(&pc, num); 
          PrintPolyn(&pa); PrintPolyn(&pb); PrintPolyn(&pc); 
         AddPolyn(&pa,&pb); 
         PrintPolyn(&pa); 
           AddPolyn(&pa, &pc); 
            PrintPolyn(&pa); 
       } 
      return 0; 
    }