NBP部落格-分享是為了成長

028.多項式相加。如輸入 3X^3+2X^2+X+1 與 2X^3+5, 則輸出 5X^3+2X^2+X+6
用Link List的方式完成，所以很多血都吐再處理處理Link List.....
如果有後進願意提供STL版本也歡迎

#include <iostream>

using namespace std;

struct poly{
   int constant;
   int exp;
   poly* next;
};

typedef poly* poly_ptr;

poly_ptr PlusElement(poly_ptr,poly_ptr);
void AddElement(poly_ptr,int,int);
void PrintElement(poly_ptr);
void FreeElement(poly_ptr);

int main(void)
{
/*假設輸入已經排序過
   condition 1: 3X^3+2X^2+X+1
   condition 2: 2X^3+5
   Result : 5X^3+2X^2+X+6
*/

poly_ptr condition1 = new poly;
poly_ptr condition2 = new poly;
// condition 1: 3X^3+2X^2+X+1
condition1->next = NULL;
AddElement(condition1,3,3);
AddElement(condition1,2,2);
AddElement(condition1,1,1);
AddElement(condition1,1,0);
// condition 2: 2X^3+5
condition2->next = NULL;
AddElement(condition2,2,3);
AddElement(condition2,5,0);
//Print Poly
PrintElement(condition1);
cout << endl;
PrintElement(condition2);
cout << endl;
//Plus poly
poly_ptr condition3;
condition3 = PlusElement(condition1,condition2);
PrintElement(condition3);
//Free Poly
FreeElement(condition1);
FreeElement(condition2);
FreeElement(condition3);
cin.get();
return 0;
}

poly_ptr PlusElement(poly_ptr source1,poly_ptr source2)
{
   poly_ptr result = new poly;
   poly_ptr tmp1 = source1->next;
   poly_ptr tmp2 = source2->next;
   while(tmp1)
   {
       while(tmp2)
       {
         //比較是否有相同的指數出現在source2
         if(tmp1->exp == tmp2->exp) // condition1 & condition2同時有的項次
         {
            AddElement(result,tmp1->constant+tmp2->constant,tmp1->exp);
            tmp2 = tmp2->next;
            break;
         }else
         if(tmp2->exp > tmp1->exp) //conditon1 沒有的項次
         {
            AddElement(result,tmp2->constant,tmp2->exp);
            tmp2 = tmp2->next;
         }else
         if(tmp2->exp < tmp1->exp)//condition2沒有的項次
         {
            AddElement(result,tmp1->constant,tmp1->exp);
            break;
         }
       }
       tmp1 = tmp1->next;
   }
   return result;
}

// 新增多項式的每一個項次....沒有自動作排序
void AddElement(poly_ptr source,int constant,int exp)
{
   poly_ptr tmp = new poly;
   while(source->next)
   {
       source = source->next;
   }
   tmp->constant = constant;
   tmp->exp      = exp;
   tmp->next     = NULL;
   source->next = tmp;
}

//列印多項式
void PrintElement(poly_ptr source)
{
  poly_ptr tmp = source->next;
  while(tmp)
  {
     if(tmp->exp == 0){
              cout << " "<< tmp->constant;
     }
     else  
     if(tmp->exp == 1){
           cout << " " << tmp->constant << "X";
     }
     else{
           cout << " " << tmp->constant << "X^" << tmp->exp;
     }
     
     tmp = tmp->next;
  }
}

//歸還記憶體
void FreeElement(poly_ptr source)
{
  poly_ptr tmp;
  while(source)
  {
     tmp = source;
     source = source->next;
     delete tmp;
  }
}

在此感謝當年在數位高手(NBP)分享的朋友，本人將資料彙整於此並盡量將當初發表者名稱註記。