BÀI TỰ CHỮA PHẦN BINARY TREE.doc
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (77.05 KB, 3 trang )
BÀI TỰ CHỮA PHẦN BINARY TREE
I. Phong cách lập trình: Phần làm có nhiều điểm sửa những cái nho nhỏ. Mong cô đọc
hết. Tuy chỉ nhỏ thôi nhưng em thấy cũng quan trọng.
1. Kỹ thuật làm việc với biến.
• Đặt tên cho biến: Tự xác định cho mình một phong cách đặt tên cho biến.:
Nếu là hằng thì luôn viết hoa
Từ thứ nhất của biến không viết hoa. Các từ còn lại viết hoa và viết liền với
nhau. Ví dụ: typeNode hoặc valueNode
Dùng danh từ hoặc cụm danh từ đặt tên cho biến.
Tên biến có tính gợi nhớ cao: Ví dụ: Trước đây để đặt tên cho một biến thể
hiện biến đó là giá trị của Node: thì đặt luôn là Node trong khi đó loại giá trị
của node lại đặt là type. Sau đó đặt lại là valueNode và typeNode
• Khởi tạo biến.
Luôn tránh việc dùng biến global một cách tối đa có thể
Hầu hết các biến được khởi tạo ngay sau khi khai báo so với việc trước đây
thường khá ít làm. Ví dụ: BinaryTree::node *root = NULL
2. Kỹ thuật viết mã chương trình hiệu quả.
• Version 1 viết liền một mạch không có cách dòng giữa các phần chính. Như khai
báo biến. Phần viết hàm. Hàm main … Giữa các hàm cũng không có dấu cách
để phân biệt.
Version 2 có khoảng cách giữa các phần rõ ràng. Những phần chung xếp lại
cạnh nhau như các contructor, setter,…Giữa các chức năng cụ thể có để lại
những khoảng phân biện
Ví dụ ____________________InitBinaryTree_____________
//tất cả các hàm về khởi tạo cây ở đây
_____________________DuyetTruoc________________
Hàm duyệt trước để ở đây ….
• Đối với khoảng cách giữa các từ:
Ví dụ: version 1
node *SearchNode(node *root,char *type,ValueNode *valueNode);
node *SearchNode(node *root, char *type, ValueNode *valueNode);
Có khoảng cách giữa các từ sau dấu , hoặc dấu ;
Hoặc là khi có logic && version 2 đã chữa lại thành && có dấu cách giữa 2 &&
để dễ sửa hoặc dễ nhận ra sai các dấu ) hoặc ( mỗi khi có lỗi.
Hình thành thói quen viết: ví dụ: a=a+b; viết thành a = a + b; có dấu cách để dễ
nhìn.
Version 2: Luôn để dấu () khi có phép logic đôi khi cũng hơi máy móc.
• Viết các biểu thức và phép toán theo đúng ý nghĩa:
Version 1 viết: if(!root){..}
->if(root != NULL)
II. Hàm , Chương trình con
1. Vấn đề rút gọn thành 1 hàm: version 1 có khá nhiều đoạn trùng mà hoàn toàn có thể tạo
thành 1 hàm riêng biệt để có thể sử dụng
switch(*typeNode){
case 'i':
cin>>(valueNode->dataInt);
break;
case 'o':
cin>>(valueNode->op);
break;
default:
break;
}
Đoạn này được sử dụng lại 3 lần trong hàm Input. Và 1 lần trong hàm
InitBinaryTree khi khỏi tạo root. ( lúc đầu) -> đổi thành 1 hàm
InputValueNode
void BinaryTree::InputValueNode(char *typeNode, BinaryTree::ValueNode
*valueNode){
switch(*typeNode){
case 'i':
cin>>(valueNode->dataInt);
break;
case 'o':
cin>>(valueNode->op);
break;
default:
break;
}
}
Khi đó chỉ gọi hàm và truyền tham số.
2. Một hàm chỉ làm một nhiệm vụ: Version 2 phân chia thành nhiều hàm hơn. Mỗi hàm chỉ
thực hiện 1 nhiệm vụ. Ví dụ hàm nhập Input chỉ thực hiện việc nhâp sau đó có hàm test
để kiểm tra giá trị nhập. Không cho hàm vừa kiểm tra vừa nhập. Vấn đề này là một vấn
đề rất hay đã giúp em rất nhiều để chương trình đơn giản, dễ sửa và sử dụng lại được
các hàm đó.
3. Version 1 khi viết các hàm ko có một lời giải thích. Chỉ viết hàm và nói qua về mục đích
làm gì. Không nói rõ dl đầu vào. Và đầu ra cụ thể làm gì. Khi viết như thế đã rất nhiều
lần viết hàm xong rồi lại cho thêm một nhiệm vụ khác vào hàm đó, rồi lại thêm. Cuối
cùng nhiệm vụ của hàm lại bị đẩy sang một hướng khác. Cho nên khi viết hàm thì sẽ
nêu rõ mục đích của hàm đó. Đầu ra và đầu vào tương ứng với thực hiện một nhiệm vụ
cụ thể.
4. Version 2 viết theo kiểu top down, modun hóa dần. Phân chia các hàm cụ thể không bị
trùng code như version 1. Không viết tự phát ( chỉ để suy nghĩ trong đầu) rồi viết như
version 1.
III. Những điểm cải tiến so với version 1
1. Sử dụng c++:
Chương trình version 1 sử dụng c để viết. Các dữ liệu của node khai báo bằng
struct. Version 2 viết bằng c++ khai báo lớp BinaryTree. Các thuộc tính của node
đều ở trong lớp.
2. Vấn đề thuộc tính.
Version 1 khai báo node chỉ có giá trị kiểu số nguyên không có kiểu char để thể hiện
node cũng có thể là toán tử.( Không đúng với yêu cầu của đề bài.
Version 2 viết lại các thuộc tính là kiểu hợp union có thể chứa cả 2 kiểu int là
toán hạng và char là toán tử
union {
int dataInt;
char op;
}Node;
3. Vấn đề đệ quy
Trong version 1 dùng thuật toán khử đệ quy đối với tất cả các chức năng là duyệt
trước, sau , giữa và cả kiểm tra xem đó có phải là cây biểu thức không. Thuật toán
khá lằng nhằng và tương đối là khó hiểu. Nếu người khác test thì tương đối là khó
để phát hiện ra lỗi và sửa. Nhưng nó lại nhanh nếu làm nhiều node so với kiểu đệ
quy.
Khai báo thêm một struct stack để khử đệ quy.
Version 2 sử dụng đệ quy nên không có stack. Rất dễ hiểu. Rất dễ để test lỗi.
Ví dụ: Hàm duyệt trước:
void BinaryTree::DuyetTruoc(BinaryTree::node *root){
if(root!=NULL){
displayNode(root);
DuyetTruoc(root->leftPointer);
DuyetTruoc(root->rightPointer);
}
}//_end_DuyetTruoc.
4. Thuật toán khởi tạo cây:
Version 1 sử dụng cho người dùng nhập vào một giá trị n. Và chương trình sẽ tự
khởi tạo một cây có n nút. Và cây đó là cây nhị phân đầy đủ. Khi đó phải sử dụng
thêm một queue để thực hiện thuật toán này.
Version 2 dùng thuật toán cho phép người dùng nhập vào từng node một. Như
thế sẽ đúng ý của người dùng hơn. Nhưng không có đồ họa người dùng phải tự
vẽ cây ra giấy để biết cây như nào để có thể nhập tiếp theo( Do visual c++
khônng có đồ họa của c++ ).
