實驗要求： 1.設計帶表頭的結點的單鏈表表示多項式類。 2.在該類上增加成員函數void PolyMul(Polynominal &r)，并重載*運算符。 3.實現菜單驅動的main函數，測試多項式的各個運算：輸入多項式，顯示多項式，以及多項式加法和乘法運算。 4.采用帶表頭的非循環鏈表存儲多項式。 大致結構以及加法的運算書上的代碼已經給出。乘法運算：將乘數多項式的每一項與被乘數多項式的所有項分別相乘(系數相乘，指數 相加)，得到中間多項式。調用PolyAdd函數將這些中間多項式依次加到結果多項式中。 實現代碼： ~~~ #include "iostream" #include "cstdio" #include "cstring" #include "algorithm" using namespace std; class Term { public: Term(int c, int e); Term(int c, int e, Term *nxt); Term* InsertAfter(int c, int e); // 在this指針指示的結點后插入新節點 private: int coef, exp; // coef * x^exp Term* link; friend ostream & operator << (ostream &, const Term &); friend class Polynominal; /* data */ }; Term::Term(int c, int e) : coef(c), exp(e) { link = 0; } Term::Term(int c, int e, Term *nxt) : coef(c), exp(e) { link = nxt; } Term *Term::InsertAfter(int c, int e) // 為新項申請結點的存儲單元，并用Term函數將c, e, this -> link 的值填入新節點的相應域 { link = new Term(c, e, link); return link; } ostream & operator << (ostream& out, const Term& val) { if(val.coef == 0) return out; if(val.coef != 1) out << val.coef; switch(val.exp) { case 0: break; case 1: out << "x"; break; default: out << "x^" << val.exp; break; } return out; } class Polynominal { public: Polynominal(); ~Polynominal(); void AddTerms(istream& in); void Output(ostream& out) const; void PolyAdd(Polynominal& r); void PolyMul(Polynominal& r); private: Term* theList; friend ostream & operator << (ostream &, const Polynominal &); friend istream & operator >> (istream &, Polynominal &); friend Polynominal & operator + (Polynominal &, Polynominal &); friend Polynominal & operator * (Polynominal &, Polynominal &); /* data */ }; Polynominal::Polynominal() { theList = new Term(0, -1); // 表頭結點 theList -> link = NULL; // 尾結點為空 } Polynominal::~Polynominal() { Term *p = theList -> link; while(p != NULL) { theList -> link = p -> link; delete p; p = theList -> link; } delete theList; } void Polynominal::AddTerms(istream& in) // 按降冪輸入各項，構造單循環鏈表 { Term* q = theList; int c, e; while(true) { cout << "Input a term(coef, exp):" << endl << endl; cin >> c >> e; q = q -> InsertAfter(c, e); // 將c，e插入表尾結點q之后 if(e < 0) break; // 當輸入指數小于0時，構造結束 } } void Polynominal::Output(ostream& out) const { int first = 1; Term *p = theList -> link; for( ; p != NULL && p -> exp >= 0; p = p -> link) { if(!first && (p -> coef > 0)) out << "+"; // 在非第一項的正系數前輸出+號 first = 0; out << *p; // 調用Term類上重載的"<<"操作 } cout << endl; } void Polynominal::PolyAdd(Polynominal& r) { Term *q, *q1 = theList, *p; // q1指向表頭結點 p = r.theList -> link; // p指向第一個要處理的結點 q = q1 -> link; // q1是q的前驅，p和q就指向兩個當前進行比較的項 while(p != NULL && p -> exp >= 0) { // 對r的單鏈表遍歷，直到全部結點都處理完 while(p -> exp < q -> exp) { // 跳過q -> exp大的項 q1 = q; q = q -> link; } if(p -> exp == q -> exp) { // 指數相等時，系數相加 q -> coef = q -> coef + p -> coef; if(q -> coef == 0) { // 若相加后系數為0，則刪除q q1 -> link = q -> link; delete (q); q = q1 -> link; // 重置q指針 } else { // 若相加后系數不為0，則移動q1和q q1 = q; q = q -> link; } } else q1 = q1 -> InsertAfter(p -> coef, p -> exp); // 若p -> exp > q -> exp則以p的系數和指數生成新結點，插入q1后 p = p -> link; } } void Polynominal::PolyMul(Polynominal& r) { Polynominal result; // 存儲結果 Term *n = result.theList; // n指向result的頭結點 n = n -> InsertAfter(0, 0); // 將0, 0插入result的頭結點之后 Term *p = r.theList -> link; // p指向第一個要處理的結點 while(p -> exp >= 0) { // 對r的單鏈表遍歷，直到全部結點都處理完 Polynominal tmp; // tmp存儲當前結果 Term *m = tmp.theList; // m指向tmp頭結點 Term *q = theList -> link; // q指向表頭結點的后繼結點 while(q -> exp >= 0) { // 遍歷當前單鏈表 m = m -> InsertAfter((p -> coef) * (q -> coef), (p -> exp) + (q -> exp)); // 生成新結點插入m后 q = q -> link; } result.PolyAdd(tmp); // 當前結果加到result上 p = p -> link; } Term *q = theList -> link; while(q != NULL) { // 清空原數據 theList -> link = q -> link; delete q; q = theList -> link; } q = theList; q = q -> InsertAfter(0, 0); PolyAdd(result); // result加到當前對象上 } ostream & operator << (ostream &out, Polynominal &x) { x.Output(out); return out; } istream & operator >> (istream &in, Polynominal &x) { x.AddTerms(in); return in; } Polynominal & operator + (Polynominal &a, Polynominal &b) { a.PolyAdd(b); return a; } Polynominal & operator * (Polynominal &a, Polynominal &b) { a.PolyMul(b); return a; } int main(int argc, char const *argv[]) { cout << "***********" << endl; cout << " 按1進行多項式加法" << endl; cout << " 按2進行多項式乘法" << endl; cout << " 按0退出程序" << endl; cout << "***********" << endl; int num; while(cin >> num && num) { cout << "請輸入多項式p：" << endl; Polynominal p, q; cin >> p; cout << p << endl; cout << "請輸入多項式q：" << endl; cin >> q; cout << q << endl; if(num == 1) { Polynominal ans = p + q; cout << "p + q = " << ans << endl; } else { Polynominal ans = p * q; cout << "p * q = " << ans << endl; } cout << "***********" << endl; cout << " 按1進行多項式加法" << endl; cout << " 按2進行多項式乘法" << endl; cout << " 按0退出程序" << endl; cout << "***********" << endl << endl; } cout << endl << "感謝檢查" << endl; return 0; } ~~~