使用STL裡标準list以及iterator實作多項式加法

利用C++标準模闆庫LIST實作多項式加法，可參考課本（P526-533）。求以下兩個多項式的和：

F(x)=8x7+7x4+3x2+5 G(x)=9x6+2x5+5x4+2

編譯環境

在 Visual Studio 2019 平台下開發。

硬體環境：

作業系統：Windows10

處理器：Inter® Core™ i5-8300H CPU @ 2.30GHZ 2.30 GHZ

安裝記憶體(RAM)：8GB

系統類型：64 位作業系統，基于 x64 的處理器

設計思路

使用STL裡的list以及iterator實作。

先将兩個多項式以幂次升序排序，友善後續比較。

這裡使用标準list的sort函數，并自定義排序方式函數。

struct cmp {                                       //自定義多項式的存儲方式
	bool operator()(const datas& t1, const datas& t2) {
		return t1.expo < t2.expo;                  //将多項式按幂次進行升序存儲
	}
};
           

再使用下列語句即可完成多項式按幂次的升序排序。

a2的定義如下：

因為兩多項式首節點的幂次一樣，系數相加且不為0，将其加入和連結清單中，然後兩個疊代器都移動一位，進行下一輪次的判斷。

這輪比較中，iter1指向節點的幂次為2，小于iter2指向節點的幂次，是以将iter1指向的節點添加進和連結清單中。iter1移動一位。

這輪比較中，兩疊代器指向節點的幂次相同，将系數相加，且系數和不為0，将新的系數（即系數和）和原幂次作為新節點添加進和連結清單中。

後續操作同理。

最後一次的添加時，iter2指向g（x）連結清單的尾節點的下一位，隻需将f（x）的剩下節點一次添加進和連結清單中即可。

直到iter1移動到f（x）連結清單尾節點的下一位，跳出循環。至此多項式連結清單的相加結束。

代碼實作

話不多說，直接上代碼。

#include<iostream>
#include<list>
using namespace std;
class datas {
public:
	int coef;
	int expo;
	datas(int a,int y):coef(a),expo(y){}           //定義list的元素類型
};
struct cmp {                                       //自定義多項式的存儲方式
	bool operator()(const datas& t1, const datas& t2) {
		return t1.expo < t2.expo;                  //将多項式按幂次進行升序存儲
	}
};
list<datas>operator+(list<datas>& a1, list<datas>& a2) {
	list<datas> sumlist;                           //儲存多項式和得list
	list<datas>::iterator
		iter1 = a1.begin(),                        //定義兩個iterator分别指向兩多項式得首節點
		iter2 = a2.begin();
	while (iter1 !=a1.end()|| iter2!=a2.end()) {   //當兩個iter都周遊完各自list後循環結束
		if (iter1 == a1.end()||(iter2!=a2.end())&&iter1->expo>iter2->expo) {
			//當連結清單a1複制完或目前a1節點的幂大于目前a2節點的幂時，複制第二個多項式
			datas s(iter2->coef, iter2->expo);            
			sumlist.push_back(s);
			iter2++;                               //a2疊代器向後移動一位，指向a2下一個節點
		}
		else if (iter2 == a2.end() || (iter1!=a1.end())&&iter2->expo > iter1->expo) {
			//當連結清單a2複制完或目前a2節點的幂大于目前a1節點的幂時，複制第二個多項式
			datas s(iter1->coef, iter1->expo);             
			sumlist.push_back(s);
			iter1++;						       //a1疊代器向後移動一位，指向a1下一個節點
		}
		else {                                     //兩個節點同幂
			int sum = iter1->coef + iter2->coef; 
			if (sum != 0) {                        //若兩個節點系數和不為0，将其添加進和list
				datas s(sum, iter1->expo);
				sumlist.push_back(s);
			}
			iter1++;
			iter2++;                               //兩疊代器都指向下一個節點
		}
	}
	return sumlist;                                //傳回多項式之和
}
void priint(list<datas>& a){                       //将連結清單元素輸出形如"ax^b+cx^d"的多項式
	list<datas>::iterator i;
	for (i = a.begin(); i != a.end(); ++i) {
		if (i == a.begin()) {
			if (i->expo == 0)
				cout << i->coef;
			else cout << i->coef << "x^" << i->expo;
		}
		else
			cout << "+" << i->coef << "x^" << i->expo;
	}
	cout << endl;
}
int main() {
	list<datas> a1;
	datas s1(8, 7);
	datas s2(7, 4);
	datas s3(3, 2);
	datas s4(5, 0);
	a1.push_back(s1);
	a1.push_back(s2);
	a1.push_back(s3);
	a1.push_back(s4);
	list<datas> a2;
	datas ss1(9, 6);
	datas ss2(2, 5);
	datas ss3(5, 4);
	datas ss4(2, 0);
	a2.push_back(ss1);
	a2.push_back(ss2);
	a2.push_back(ss3);
	a2.push_back(ss4);
	a1.sort(cmp());
	a2.sort(cmp());                                 //将多項式以幂次升序儲存
	cout << "f(x)=";
	priint(a1);
	cout << "g(x)=";
	priint(a2);
	cout << "f(x)+g(x)=";
	list<datas>a3 = a1 + a2;
	priint(a3);
}
           

運作結果

總結

第一次寫部落格肯定有許多不足之處，我會慢慢改進。

寫部落格也是為了記錄學習過程中發現的有意義的題目和問題，以便日後複習。