Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 15: Ứng dụng của hàng đợi

 sách các cặp gồm hệ số và số mũ. Chúng ta dùng struct để 
khai báo số hạng 
Chương 15 – Ứng dụng của hàng đợi 
Giáo trình Cấu trúc dữ liệu và Giải thuật 382
struct Term { 
 int degree; 
 double coefficient; 
 Term (int exponent = 0, double scalar = 0); 
}; 
Term::Term(int exponent, double scalar) 
/* 
post: Term được khởi tạo bởi hệ số và số mũ nhận được, nếu không có thông số truyền vào thì 
hai số này được gán mặc định là 0. 
*/ 
{ 
 degree = exponent; 
 coefficient = scalar; 
} 
Chúng ta chưa lưu tâm về thứ tự của các số hạng trong đa thức, tuy nhiên nếu 
cho phép các số hạng có một thứ tự tùy ý thì chúng ta sẽ gặp khó khăn trong việc 
nhận ra các đa thức bằng nhau cũng như trong việc tính toán trên các đa thức. 
Chúng ta chọn phương án buộc các số hạng trong một đa thức phải có thứ tự giảm 
dần theo số mũ, đồng thời cũng không cho phép hai số hạng có cùng số mũ hoặc 
số hạng có hệ số bằng không. Với sự ràng buộc này, khi thực hiện một phép tính 
số học nào đó trên hai đa thức, chúng ta thường lần lượt xử lý cho từng cặp số 
hạng của hai đa thức từ trái sang phải. Các số hạng của đa thức kết quả cũng 
được ghi vào đa thức theo thứ tự này. Một đa thức được biểu diễn bằng một danh 
sách các Term. Như vậy, các phép tính số học có thể xem đa thức như là một 
Queue, hay chính xác hơn, như là Extended_queue, vì chúng ta thường xuyên 
cần đến các phương thức clear và serve_and_retrieve. 
Chúng ta thử hỏi nên dùng hàng liên tục hay hàng liên kết. Nếu biết trước bậc 
của đa thức và các đa thức ít có hệ số bằng không thì chúng ta nên dùng hàng 
liên tục. Ngược lại, nếu không biết trước bậc, hoặc đa thức có rất ít hệ số khác 
không thì hàng liên kết thích hợp hơn. Hình 15.1 minh họa đa thức hiện thực 
bằng hàng liên kết. 
Mỗi phần tử trong hàng chứa một số hạng của đa thức và chỉ có những số hạng có 
hệ số khác không mới được lưu vào hàng. Đa thức bằng 0 biểu diễn bởi hàng rỗng. 
Với cấu trúc dữ liệu được chọn cho đa thức như trên chúng ta xây dựng lớp 
Polynomial là lớp dẫn xuất từ lớp Extended_Queue, chúng ta chỉ việc bổ sung 
các phương thức riêng của đa thức. 
Để hiện thực cụ thể cho lớp dẫn xuất Polynomial, chúng ta cần đặt câu hỏi: 
một đa thức có hẳn là một Extended_Queue hay không? 
Chương 15 – Ứng dụng của hàng đợi 
Giáo trình Cấu trúc dữ liệu và Giải thuật 383
Một Extended_Queue cung cấp các phương thức như serve chẳng hạn, 
phương thức này không nhất thiết và cũng không nên là phương thức của 
Polynomial. Sẽ là một điều không hay khi chúng ta cho phép người sử dụng gọi 
phương thức serve để loại đi một phần tử của Polynomial. Đa thức nên là một 
đối tượng đóng kín. Vì vậy một Polynomial không hẳn là một Extended_Queue. 
Mặc dù rất có lợi khi sử dụng lại các thuộc tính và các phương thức từ 
Extended_Queue cho Polynomial, nhưng chúng ta không thể sử dụng phép thừa 
kế đơn giản, vì quan hệ của hai lớp này không phải là quan hệ “is-a”. 
Quan hệ “is-a” là dạng thừa kế public trong C++. Nếu khai báo thừa kế public thì người sử 
dụng có thể xem một đa thức cũng là một hàng đợi. C++ cung cấp một dạng thừa kế thứ hai, gọi là 
thừa kế riêng (private inheritance), đây chính là điều chúng ta mong muốn. Sự thừa kế riêng cho 
phép lớp dẫn xuất được hiện thực bằng cách sử dụng lại lớp cơ sở, nhưng người sử dụng không gọi 
được các phương thức của lớp cơ sở thông qua đối tượng của lớp dẫn xuất. Quan hệ này còn được 
gọi là quan hệ “is implemented of”. Chúng ta sẽ định nghĩa lớp Polynomial thừa kế riêng từ lớp 
Extended_Queue: các thuộc tính và các phương thức của Extended_Queue có thể được sử dụng 
trong hiện thực của lớp Polynomial, nhưng chúng không được nhìn thấy bởi người sử dụng. 
class Polynomial: private Extended_queue { // Thừa kế riêng. 
public: 
 void read(); 
 void print() const; 
 void equals_sum(Polynomial p, Polynomial q); 
 void equals_difference(Polynomial p, Polynomial q); 
 void equals_product(Polynomial p, Polynomial q); 
 Error_code equals_quotient(Polynomial p, Polynomial q); 
 int degree() const; 
private: 
 void mult_term(Polynomial p, Term t); 
}; 
Hình 15.1- Biểu diễn đa thức bởi một hàng liên kết các số hạng 
Chương 15 – Ứng dụng của hàng đợi 
Giáo trình Cấu trúc dữ liệu và Giải thuật 384
Định nghĩa trên bổ sung thêm các phương thức như degree trả về bậc của đa 
thức và mult_term để nhân một đa thức với một term. 
15.5.4. Đọc và ghi các đa thức 
Việc in đa thức đơn giản chỉ là duyệt qua các phần tử của hàng và in dữ liệu 
trong mỗi phần tử. Phương thức dưới đây in đa thức với một số xử lý cho các 
trường hợp đặc biệt như loại bỏ dấu + (nếu có) ở đầu đa thức, không in hệ số hoặc 
số mũ nếu bằng 1 và không in x0. 
void Polynomial::print() const 
/* 
post: Đa thức được in ra cout. 
*/ 
{ 
 Node *print_node = front; 
 bool first_term = true; 
 while (print_node != NULL) { 
 Term &print_term = print_node->entry; 
 if (first_term) { // Không in dấu ‘+’ đầu đa thức. 
 first_term = false; 
 if (print_term.coefficient < 0) cout << "- "; 
 } 
 else if (print_term.coefficient < 0) cout << " - "; 
 else cout << " + "; 
 double r = (print_term.coefficient >= 0) 
 ? print_term.coefficient : -(print_term.coefficient); 
 if (r != 1) cout << r; 
 if (print_term.degree > 1) cout << " X^" << print_term.degree; 
 if (print_term.degree == 1) cout << " X"; 
 if (r == 1 && print_term.degree == 0) cout << " 1"; 
 print_node = print_node->next; 
 } 
 if (first_term) 
 cout << "0"; // Print 0 for an empty Polynomial. 
 cout << endl; 
} 
Phương thức đọc đa thức thực hiện việc kiểm tra để các số hạng nhập vào thỏa 
điều kiện số mũ giảm dần và một số ràng buộc trong việc biểu diễn đa thức như 
đã nêu trên. Việc nhập kết thúc khi hệ số và số mũ đều nhận trị 0. 
void Polynomial::read() 
/* 
post: Đa thức được đọc từ cin. 
*/ 
{ 
 clear(); 
 double coefficient; 
 int last_exponent, exponent; 
 bool first_term = true; 
Chương 15 – Ứng dụng của hàng đợi 
Giáo trình Cấu trúc dữ liệu và Giải thuật 385
 cout << "Enter the coefficients and exponents for the polynomial, " 
 << "one pair per line. Exponents must be in descending order." 
<< endl 
 << "Enter a coefficient of 0 or an exponent of 0 to terminate." << 
endl; 
 do { 
 cout << "coefficient? " << flush; 
 cin >> coefficient; 
 if (coefficient != 0.0) { 
 cout << "exponent? " << flush; 
 cin >> exponent; 
 if ((!first_term && exponent >= last_exponent) || exponent < 0) { 
 exponent = 0; 
 cout << "Bad exponent: Polynomial terminates without its last 
term." 
 << endl; 
 } 
 else { 
 Term new_term(exponent, coefficient); 
 append(new_term); 
 first_term = false; 
 } 
 last_exponent = exponent; 
 } 
 } while (coefficient != 0.0 && exponent != 0); 
} 
15.5.5. Phép cộng đa thức 
Phần này chúng ta chỉ hiện thực phép cộng đa thức, các phép tính khác xem 
như bài tập. 
Do các số hạng trong cả hai đa thức có số mũ giảm dần nên phép cộng rất đơn 
giản. Chúng ta chỉ cần duyệt qua một lần và đồng thời đối với cả hai đa thức. Nếu 
gặp hai số hạng của hai đa thức có số mũ bằng nhau, chúng ta cộng hai hệ số và 
kết quả đưa vào đa thức tổng, ngược lại, số hạng của đa thức nào có số mũ cao 
hơn được đưa vào tổng, phép duyệt chỉ dịch chuyển tới một bước trên đa thức này. 
Chúng ta chỉ phải lưu ý đến trường hợp tổng hai hệ số của hai số hạng bằng 0 thì 
sẽ không có phần tử mới được đưa vào đa thức tổng. Ngoài ra, vì phương thức này 
sẽ phá hủy các đa thức toán hạng được đưa vào nên chúng được gởi bằng tham trị. 
void Polynomial::equals_sum(Polynomial p, Polynomial q) 
/* 
post: Đối tượng đa thức sẽ có trị bằng tổng hai đa thức nhận vào từ thông số. 
*/ 
{ 
 clear(); 
 while (!p.empty() || !q.empty()) { 
 Term p_term, q_term; 
 if (p.degree() > q.degree()) { 
 p.serve_and_retrieve(p_term); 
 append(p_term); 
 } 
Chương 15 – Ứng dụng của hàng đợi 
Giáo trình Cấu trúc dữ liệu và Giải thuật 386
 else if (q.degree() > p.degree()) { 
 q.serve_and_retrieve(q_term); 
 append(q_term); 
 } 
 else { 
 p.serve_and_retrieve(p_term); 
 q.serve_and_retrieve(q_term); 
 if (p_term.coefficient + q_term.coefficient != 0) { 
 Term answer_term(p_term.degree, 
 p_term.coefficient + q_term.coefficient); 
 append(answer_term); 
 } 
 } 
 } 
} 
Phương thức trên bắt đầu bằng việc dọn dẹp mọi số hạng trong đa thức sẽ 
chứa kết quả của phép cộng. Phương thức degree được gọi để trả về bậc của đa 
thức, nếu đa thức rỗng, degree sẽ trả về -1. 
15.5.6. Hoàn tất chương trình 
15.5.6.1. Các phương thức còn thiếu 
Phép trừ hai đa thức hoàn toàn tương tự phép cộng. Đối với phép nhân, trước 
hết chúng ta phải viết hàm nhân một đa thức với một số hạng, sau đó kết hợp với 
phương thức cộng hai đa thức để hoàn tất phép nhân. Phép chia đa thức phức tạp 
hơn rất nhiều, phép chia đa thức cho một kết quả là đa thức thương và một là đa 
thức số dư.