[PAT] 一元多项式的乘法与加法运算 C语言实现

[PAT] 02-线性结构1 一元多项式的乘法与加法运算
设计函数分别求两个一元多项式的乘积与和。

输入格式:

输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:

输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例:
4 3 4 -5 2  6 1  -2 0
3 5 20  -7 4  3 1
输出样例:
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0
时间限制：200ms
内存限制：64MB
代码长度限制：16kB
判题程序：系统默认
作者：DS课程组
单位：浙江大学

　　原题点击此处

　　好的,宝宝又来写东西啦~这次的题目是一道多项式计算题:输入两个多项式,输出他们的乘积与和,格式大概是这样:

　　[15 24] [-25 22] [30 21] [-10 20]...

　　每个中括号前面的是系数,后面的是指数,排序是指数从高到低.

　　这题难度本身不大,做出来很容易.但是要追求速度和更少内存消耗的话还是需要考虑用什么方式去储存和处理这些数据,下面给出我个人的一个方法:求乘积用双向链表,求和用动态数组.另外,我的代码比较长,因为我采用的是"空间换时间"的总体方向,所以消耗较多储存空间,好处是不用递归函数,那个是计算机最不擅长的事情.

#include <stdio.h>
#include <stdlib.h>typedef struct 
{int cofe;int expo;
} NODE;typedef struct _List
{int cofe;int expo;  struct _List * _next;struct _List * _back;        
} List;

　　构造一个NODE型的struct.存放原始每一项的系数(cofe)和指数(expo),再构造一个List型的struct,这是一个可以增长的链表,在原始数据里面不断抽取数据按指数大小进行比较排序,若指数比当前指的小就向后(左)移动一位,比当前大就向后(右)移动一位如果已经指到头则新建一个节点再写入,这其中的判断逻辑还包括系数相乘后写入系数区,排序结束后的双向链表就可以直接输出了.

 1 int main(void) //全局初始化,包括建立各种变量以及读入原始数据
 2 {
 3     int PolyOneCount,PolyTwoCount,i,k,cofe_temp,expo_temp,flag=1,Once=1,NotZeroCount=0;
 4     NODE* PolyOne=NULL;
 5     NODE* PolyTwo=NULL;
 6     List* PL=NULL;
 7     NODE* PolySum=NULL;
 8     List* PTemp;
 9     NODE* P1=NULL;
10     NODE* P2=NULL;
11     scanf("%d",&PolyOneCount);
12     P1=PolyOne=(NODE*)malloc(PolyOneCount*sizeof(NODE));
13     for ( i=0; i<PolyOneCount; i++ ) 
14     {
15         scanf("%d",&((PolyOne+i)->cofe));
16         scanf("%d",&((PolyOne+i)->expo));
17     }
18     scanf("%d",&PolyTwoCount);
19     P2=PolyTwo=(NODE*)malloc(PolyTwoCount*sizeof(NODE));
20     for ( i=0; i<PolyTwoCount; i++ )
21     {
22         scanf("%d",&((PolyTwo+i)->cofe));
23         scanf("%d",&((PolyTwo+i)->expo));
24     }
25     List* PC=(List*)calloc(1,sizeof(List)); //PC是游走的指针,相当于一个爪子,把元素送到它需要去的地方

　　全局初始化,包括建立各种变量以及读入原始数据.　　

  1 for (i=0; i<PolyOneCount; i++) 
  2     for (k=0; k<PolyTwoCount; k++)
  3         {
  4         cofe_temp=((PolyOne+i)->cofe)*((PolyTwo+k)->cofe);
  5         expo_temp=((PolyOne+i)->expo)+((PolyTwo+k)->expo);
  6             while (1)
  7             {
  8                 if (Once)
  9                 {
 10                     PC->cofe = cofe_temp;
 11                     PC->expo = expo_temp;
 12                     PL=PC;
 13                     Once=0;
 14                     break;
 15                 } 
 16                      
 17                  
 18                 if (expo_temp > PC->expo) //元素需要后移 
 19                 {
 20                     if (PC->_next) //链表存在下一节点 
 21                     {
 22                         flag=1;
 23                         if (expo_temp > (PC->_next)->expo) //尚未到位 
 24                             PC=PC->_next;
 25                         else if (expo_temp < (PC->_next)->expo) //已到位 
 26                         {
 27                             PTemp = (List*)calloc(1,sizeof(List));
 28                             PTemp->_next = (PC->_next); 
 29                             (PC->_next)->_back = PTemp;
 30                             PC->_next = PTemp;
 31                             PTemp->_back = PC;
 32                             PC=PC->_next;
 33                             PC->cofe = cofe_temp;
 34                             PC->expo = expo_temp;
 35                             break;
 36                         }
 37                         else if (expo_temp == (PC->_next)->expo) //元素与下一个相等 
 38                         {
 39                             PC=PC->_next;
 40                             (PC->cofe)+=cofe_temp;
 41                             flag=0;
 42                             break;
 43                         }
 44                     }
 45                      
 46                     else //双向链表无下一节点. 
 47                     {
 48                         PTemp = (List*)calloc(1,sizeof(List));
 49                         PTemp->_back = PC;
 50                         PL=PTemp;
 51                         PC->_next = PTemp;
 52                         PC=PC->_next;
 53                         PC->cofe = cofe_temp;
 54                         PC->expo = expo_temp;
 55                          
 56                         break;
 57                     }                           
 58                 }
 59                  
 60                 else if (expo_temp < PC->expo) //元素需要前移 
 61                 {
 62                     if (PC->_back) //存在前驱节点 
 63                     {
 64                         flag=1;
 65                         if (expo_temp < (PC->_back)->expo) //未到位 
 66                             PC=PC->_back;
 67                         else if (expo_temp > (PC->_back)->expo) //已到位 
 68                         {
 69                             PTemp = (List*)calloc(1,sizeof(List));
 70                             PTemp->_back = (PC->_back); 
 71                             (PC->_back)->_next = PTemp;
 72                             PC->_back = PTemp;
 73                             PTemp->_next = PC;
 74                             PC=PC->_back;
 75                             PC->cofe = cofe_temp;
 76                             PC->expo = expo_temp;
 77                             break;
 78                         }
 79                         else if (expo_temp == (PC->_back)->expo)
 80                         {
 81                             PC=PC->_back;
 82                             (PC->cofe)+=cofe_temp;
 83                             flag=0;
 84                         }
 85                     } 
 86                     else //不存在前驱节点 
 87                     {
 88                         PTemp = (List*)calloc(1,sizeof(List));
 89                         PTemp->_next = PC;
 90                     //  PH=PTemp;
 91                         PC->_back = PTemp;
 92                         PC=PC->_back;
 93                         PC->cofe = cofe_temp;
 94                         PC->expo = expo_temp;
 95                         break;
 96                          
 97                     }
 98                 }       
 99              
100                 else 
101                 {
102                     if (flag) (PC->cofe)+=cofe_temp;
103                     break;
104                 }
105             }
106         }
107　　PC=PL;

　　以上是乘积计算代码,Once是一个标志,用来创建第一个节点.两个for循环用来遍历所有的乘积组合,当然也是这个程序中时间复杂度最高的一段代码,达到了O(N²).

 1    for (;PC;PC=PC->_back)  
 2     {
 3         if (PC->_back != NULL) 
 4         {
 5             if (PC->cofe) 
 6             {
 7                 printf("%d %d ",PC->cofe,PC->expo);
 8                 NotZeroCount++;
 9             } 
10             else continue;
11         }
12         else 
13         {
14             printf("%d %d\n",PC->cofe,PC->expo);
15             NotZeroCount++;
16         }
17     }
18     if (!NotZeroCount) printf("0 0\n");
19     NotZeroCount=0;

　　输出语句,中间有个if是因为题目要求最后一个不带空格;最后一个判断是看看是否是零多项式,如果是就输出"0 0"(题目要求)

 1 int max = 0,Lowest = 0;
 2     if ( PolyOne->expo >= PolyTwo->expo ) max = PolyOne->expo;
 3     else max = PolyTwo->expo;
 4     PolySum=(NODE*)calloc(max+1,sizeof(NODE));
 5     i=k=0;
 6     for (i=0;i<PolyOneCount;i++) 
 7     {
 8         (PolySum+((PolyOne+i)->expo))->cofe += (PolyOne+i)->cofe;
 9         (PolySum+((PolyOne+i)->expo))->expo = (PolyOne+i)->expo;
10     }
11     for (i=0;i<PolyTwoCount;i++) 
12     {
13         (PolySum+((PolyTwo+i)->expo))->cofe += (PolyTwo+i)->cofe;
14         (PolySum+((PolyTwo+i)->expo))->expo = (PolyTwo+i)->expo;
15          
16     }
17        NotZeroCount=0;
18     for (i=0;i<=max;i++)
19     {
20         if( (PolySum+i)->cofe ) 
21         {
22             NotZeroCount=1;
23             Lowest=i;
24             break;
25         }
26     }
27     if (!NotZeroCount) printf("0 0");
28     else
29     for (k=max;k>=0;k--)  
30     if ((PolySum+k)->cofe != 0) 
31     {
32         
33         if (k==Lowest) printf("%d %d",(PolySum+k)->cofe,(PolySum+k)->expo);    
34         else  printf("%d %d ",(PolySum+k)->cofe,(PolySum+k)->expo);
35    
36     }
37     return 0;
38 }//这里没有写free,因为做题时追求速度就省略了这一步,但是大家应当养成"一个malloc一个free"的好习惯

　　这里是加法的处理,直接给一个NODE型数组,其大小取两个多项式中最大指数加一为数组大小.毕竟相加的指数最大值不超过单个指数的最大值,于是数组的下标就是对应指数的存放地址啦.这里不需要考虑太多,直接连续把两个多项式加到新建的数组上,加完以后用一个for检查系数是不是全是0,如果不是,再用一个for从高指数往低指数输出所有系数非0的一组数据,就此完成~