Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 1: Giới thiệu

ất, 
4. Các khai báo bên trong một lớp CTDL. 
Lớp CTDL cung cấp các thao tác dữ liệu thông qua các phương thức được 
khai báo là public. 
Tất cả những thuộc tính và các hàm còn lại luôn được khai báo private 
hoặc protected. 
Các thuộc tính của một lớp CTDL có thể được phân làm hai loại: 
• Thuộc tính bắt buộc phải có để lưu dữ liệu. 
Chương 1: Giới thiệu 
Giáo trình Cấu trúc dữ liệu và Giải thuật 12/16 
• Thuộc tính mà đối tượng cần có để tự quản lý, trong số này có thuộc tính 
được bổ sung chỉ để đẩy nhanh tốc độ của các thao tác dữ liệu. 
Các hàm được che dấu bên trong lớp được gọi là các hàm phụ trợ (auxilary 
function), chúng chỉ được sử dụng bởi chính các phương thức của lớp CTDL 
đó mà thôi. 
Việc mở rộng thêm các tác vụ cho một lớp có sẵn có thể theo một trong 
hai cách: 
• Bổ sung thêm phương thức mới. 
• Xây dựng lớp thừa kế. 
5. Một số hướng dẫn cần thiết trong việc thử nghiệm chương trình. 
9 Bộ chương trình thử (driver): Đây là đoạn chương trình thường được viết 
trong hàm main và chứa một thực đơn (menu) cho phép thử mọi phương 
thức của lớp CTDL đang được xây dựng. 
Chúng ta sẽ viết, thử nghiệm, và hoàn chỉnh nhiều lớp CTDL khác nhau. 
Do đó ngay từ đầu chúng ta nên xây dựng một driver sao cho tổng quát, khi 
cần thử với một CTDL nào đó chỉ cần chỉnh sửa lại đôi chút mà thôi. 
Trong driver chúng ta nên chuẩn hóa việc đọc ghi tập tin, xử lý các thao 
tác đọc từ bàn phím và xuất ra màn hình. Phần còn lại là một menu cho 
phép người sử dụng chạy chương trình chọn các chức năng như tạo đối 
tượng CTDL mới, gọi các thao tác thêm, xóa, tìm kiếm, truy xuất, trên 
CTDL đó. 
9 Các mẩu tạm (stub): đây là một mẹo nhỏ nhưng rất hữu ích. Để dịch và 
chạy thử một vài phần nhỏ đã viết, những phần chưa viết của chương trình 
sẽ được tạo như những mẩu nhỏ và chỉ cần hợp cú pháp (Xem ứng dụng 
tính toán các đa thức trong chương 15). 
Ví dụ: Trong đoạn chương trình nào đó chúng ta đang muốn chạy thử mà 
có sử dụng lớp A, hàm B,, chúng ta sẽ tạm khai báo các stub: 
class A 
{ 
}; // Một lớp chưa có thuộc tính vì chúng ta chưa quyết định nên chọn 
kiểu thuộc tính như thế nào. 
void B() 
{ 
} // Một hàm với thân hàm còn rỗng mà chúng ta hẹn sẽ viết sau. 
Nếu một hàm đã có định nghĩa thì chỉ cần trả về sao cho hợp lệ: 
Chương 1: Giới thiệu 
Giáo trình Cấu trúc dữ liệu và Giải thuật 13/16 
int C() 
{ 
 return 1; 
} // chỉ cần cẩn thận trong trường hợp nếu như giá trị trả về lại được 
dùng trong một biểu thức luận lý để xét điều kiện lặp vòng thì có 
khả năng vòng lặp không được thực hiện hoặc lặp vô tận. 
9 Cách thức theo dõi một chương trình đang chạy hoặc nhu cầu khảo sát cách 
làm việc của một trình biên dịch nào đó: 
Ví dụ gợi ý: 
void D() 
{ 
 count << “\n Hàm D đang được gọi \n”; 
} 
Trong C++ các hàm constructor và destructor được trình biên dịch gọi khi 
một đối tượng vừa được tạo ra hoặc sắp bị hủy. Vậy nếu có thắc mắc về thứ 
tự gọi các hàm này của một lớp thừa kế từ lớp khác, chúng ta có thể dùng 
cách tương tự để viết trong constructor và destructor của từng lớp cha, con. 
Nếu chúng ta có thắc mắc về cách ứng xử của trình biên dịch khi gọi các 
hàm này hay các hàm được định nghĩa đè (overloaded, overwriten) trong 
trường hợp các lớp thừa kế lẫn nhau, hoặc một số trường hợp khác nào đó, 
thì đây là cách hay nhất để chúng ta tự kiểm nghiệm lấy. 
Phần lớn các giải thuật được nghiên cứu trước hết chỉ dựa trên ý tưởng 
(biểu diễn bằng ngôn ngữ giả và độc lập với mọi ngôn ngữ lập trình). Tuy 
nhiên khi hiện thực chúng ta thường gặp vướng mắc ở chỗ mỗi ngôn ngữ 
lập trình có một số đặc điểm khác nhau, và ngay cả khi dùng chung một 
ngôn ngữ, các trình biên dịch khác nhau (khác hãng sản xuất hay khác 
phiên bản) đôi khi cũng ứng xử khác nhau. Điều đó gây rất nhiều khó khăn 
và lãng phí thời gian của nhiều sinh viên. 
Chỉ cần lấy một ví dụ đơn giản, đó là việc đọc ghi file, việc thường xuyên 
phải cần đến khi muốn thử nghiệm một giải thuật nào đó. Các vòng lặp 
thường nhầm lẫn ở điều kiện kết thúc file trong ngôn ngữ C++, mà điều 
này hoàn toàn phụ thuộc vào việc xử lý con trỏ file của trình biên dịch. 
Ngay một phần mềm như Visual C++ hiện tại cũng chứa cùng lúc trong thư 
viện không biết bao nhiêu lớp phục vụ cho việc khai báo và đọc ghi file. 
Chúng ta chỉ có thể sử dụng một trong các thư viện đó một cách chính xác 
sau khi đã tìm hiểu thật kỹ! Một ví dụ khác cũng hay gây những lỗi mất 
rất nhiều thời gian, đó là việc so sánh các trị: NULL, ‘0’, ‘\0’, 0,  mà nếu 
không khảo sát kỹ chúng ta sẽ bị trả giá bởi sự chủ quan cho rằng mình đã 
hiểu đúng quy ước của trình biên dịch. 
Chương 1: Giới thiệu 
Giáo trình Cấu trúc dữ liệu và Giải thuật 14/16 
Việc tìm đọc tài liệu kèm theo trình biên dịch là một việc làm cần thiết, nó 
cho chúng ta sự hiểu biết đầy đủ và chính xác. Nhưng để rút ngắn thời gian 
thì gợi ý trên đây cũng là một lời khuyên quý báu. Không gì nhanh và 
chính xác bằng cách tìm câu trả lời trong thử nghiệm. Việc sửa đổi chương 
trình như thế nào để có được các stub thỏa những nhu cầu cần thử nghiệm 
là tùy thuộc vào sự tích cực, say mê và sáng tạo của sinh viên. 
9 Gỡ rối chương trình (debug) 
Đây là khả năng theo vết chương trình ở những đoạn mà người lập trình 
còn nghi ngờ có lỗi. Bất cứ người lập trình nào cũng có lúc cần phải chạy 
debug. Vì vậy tốt hơn hết là ngay từ đầu sinh viên nên tìm hiểu kỹ các khả 
năng của công cụ debug của trình biên dịch mà mình sử dụng (cho phép 
theo dõi trị các biến, lịch sử các lần gọi hàm,). 
Một gợi ý trong phần này là sinh viên cần biết cách cô lập từng phần của 
chương trình đã viết bằng cách dùng ký hiệu dành cho phần chú thích 
(comment) để khóa bớt những phần chưa đến lượt kiểm tra. Hoặc khi lỗi do 
trình biên dịch báo có vẻ mơ hồ, thì cách cô lập bằng cách giới hạn dần 
đoạn chương trình đang dịch thử sẽ giúp chúng ta sớm xác định được phạm 
vi có lỗi. Cũng có thể làm ngược lại, chỉ dịch thử và chỉnh sửa từng đoạn 
chương trình nhỏ, cho đến khi hết lỗi mới nới dần phạm vi chương trình để 
dịch tiếp. 
1.6. Giới thiệu về ngôn ngữ giả: 
Phần lớn chương trình được trình bày trong giáo trình này đều sử dụng ngôn 
ngữ C++, sau khi ý tưởng về giải thuật đã được giải thích cặn kẽ. Phần còn lại có 
một số giải thuật được trình bày bằng ngôn ngữ giả. 
Ngôn ngữ giả, hay còn gọi là mã giả (pseudocode), là một cách biểu diễn độc 
lập với mọi ngôn ngữ lập trình, nó không ràng buộc sinh viên vào những cú pháp 
nghiêm ngặt cũng như cách gọi sao cho chính xác các từ khóa, các hàm có trong 
thư viện một trình biên dịch nào đó. Nhờ đó sinh viên có thể tập trung vào ý 
tưởng lớn của giải thuật. 
Các quy định về mã giả được sử dụng trong giáo trình này: 
¾ Biểu diễn sự tuần tự của các lệnh chương trình: các lệnh được thực thi tuần tự 
lệnh này sang lệnh khác sẽ có cùng khoảng cách canh lề như nhau và được 
đánh số thứ tự tăng dần, luôn bắt đầu từ 1. 
Chương 1: Giới thiệu 
Giáo trình Cấu trúc dữ liệu và Giải thuật 15/16 
¾ Cấu trúc khối lồng nhau: một khối nằm trong một khối khác sẽ có khoảng 
cách canh lề lớn hơn. 
Trong giáo trình này, chỉ những phần được trình bày bằng mã giả mới có số 
thứ tự ở đầu mỗi dòng lệnh. 
Ví dụ: 
 1. 
 1. 
 2. 
 1. // Đây là dòng lệnh có số thứ tự là 1.2.1 
 2. 
 3. 
 2. 
 1. 
 3. 
 1. 
 2. 
¾ Sự rẽ nhánh: chúng ta sử dụng các từ khóa: 
• if 
endif 
• if 
else 
 endif 
• case 
case1:  
case2:  
case3:  
else:  
 endcase 
¾ Sự lặp vòng: 
• loop 
endloop // lặp trong khi biểu thức luận lý còn đúng. 
• repeat 
until // lặp cho đến khi biểu thức luận lý 
đúng. 
Chương 1: Giới thiệu 
Giáo trình Cấu trúc dữ liệu và Giải thuật 16/16 
¾ Khai báo hàm: 
 tên hàm (danh sách thông số) 
trong đó danh sách thông số: val/ ref tên thông số, val/ ref 
 tên thông số, 
val: dành cho tham trị; ref: dành cho tham biến. 
¾ Khai báo cấu trúc, lớp: 
 struct tên kiểu dữ liệu cấu trúc 
 end struct 
 class tên kiểu dữ liệu cấu trúc 
 end class 
¾ Khai báo phương thức của lớp: 
 tên lớp::tên hàm (danh sách thông số); 
¾ Khai báo biến: 
 tên biến 
Một chút lưu ý về cách trình bày trong giáo trình: 
Do các đoạn chương trình sử dụng font chữ Courier New, nên các tên biến, 
tên lớp, tên đối tượng, tên các hàm khi được nhắc đến cũng dùng font chữ này. 
Các từ tiếng Anh khác được in nghiêng. Đặc biệt những phần có liên quan chặt 
chẽ đến những đặc thù của ngôn ngữ lập trình C++ thường dùng kích cỡ chữ nhỏ 
hơn, để phân biệt với những phần quan trọng khác khi nói về ý tưởng và giải 
thuật, và đó mới là mục đích chính của môn học này. 
Có một số từ hay đoạn được in đậm hay gạch dưới nhằm giúp sinh viên đọc dễ 
dàng hơn.