Cấu trúc dữ liệu mẫu với C++
Lời cảm ơn
Trớc tiên, tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo h-
ớng dẫn TS Đoàn Văn Ban, phòng CSDL&LT Viện Công Nghệ
Thông Tin thuộc trung tâm Khoa Học Tự Nhiên và Công Nghệ
Quốc Gia đã tận tình giúp đỡ tôi hoàn thành bài luận văn này.
Tôi xin chân thành cảm ơn các thầy, cô giáo khoa Công Nghệ
Thông Tin trờng ĐHDL Đông Đô đã giảng dạy và giúp đỡ em
trong quá trình học tập ở trờng.
Cuối cùng, xin chân thành cảm ơn những ngời thân trong gia
đình và bạn bè đã giúp đỡ, động viên trong quá trình học tập.
Hà nội tháng 6 năm 2000
Mục lục
Lời cảm ơn
Phần A
Chơng I. Ngôn ngữ C++ và lập trình hớng đối tợng
I.1. Lập trình hớng đối tợng là gì? 4
I.2. Các u điểm của lập trình hớng đối tợng 5
I.3. Đối tợng 6
Cấu trúc dữ liệu mẫu với C++
I.4. Các lớp đối tợng 7
I.5. Trừu tợng hoá dữ liệu và bao gói thông tin 8
I.6. Thừa kế 8
I.7. Tơng ứng bội 9
I.8. Truyền thông báo 10
I.9. Những ứng dụng của lập trình hớng đối tợng 11
Chơng II. Thiết kế và cài đặt các lớp đối tợng
II.1. Định nghĩa lớp 13
II.1.1. Khai báo lớp tên đối tợng 13
II.1.2. Tạo lập các lớp đối tợng 14
II.1.3. Các thành phần dữ liệu 15

IV.3.2. Xây dựng lớp hàm đợi mẫu 45
IV.4. Hàng quay tròn 47
IV.5. Danh sách liên kết 48
IV.6 Danh sách liên kết đơn 48
IV.7 Danh sách liên kết đôi 56
IV.8. Cây nhị phân 64
IV.9. Nhận xét 74
Phần B
I. Chơng trình quản lý sinh viên 76
II. Chơng trình thống kê từ tiếng Việt 85
Kết luận 92
Tài liệu tham khảo 93
Cấu trúc dữ liệu mẫu với C++
Chơng I
Ngôn ngữ C
++
và lập trình hớng đối tợng
I.1. Lập trình hớng đối tợng là gì?
Lập trình hớng đối tợng dựa trên nền tảng là các đối tợng. Đối tợng
đợc xây dựng trên cơ sở gắn cấu trúc dữ liệu với các phép toán sẽ thể đợc
đúng cách mà chúng ta suy nghĩ, bao quát về thế giới thực. [3]
Lập trình hớng đối tợng cho phép chúng ta kết hợp những tri thức
bao quát về các quá trình với những khái niệm trừu tợng đợc sử dụng trong
máy tính .
Lập trình hớng đối tợng là phơng pháp lập trình lấy đối tợng làm nền
tảng để xây dựng thuật giải, xây dựng chơng trình, là cách tiếp cận để phân
chia chơng trình thành các đơn thể (modul) bằng cách tạo ra các vùng bộ
nhớ cho cả dữ liệu lẫn hàm và chúng sẽ đợc sử dụng nh các mẫu để tạo ra
bản sao từng đơn thể khi cần thiết. Đối tợng ở đây đợc xem nh là vùng phân
chia chia bộ nhớ trong máy tính để lu trữ dữ liệu và tập các hàm tác động

Thông qua nguyên lý thừa kế, chúng ta có thể loại bỏ đợc những
đoạn chơng trình lặp lại, d thừa trong quá trình mô tả các lớp và khả
năng sử dụng các lớp đã đợc xây dựng.
Chơng trình đợc xây dựng từ các đơn thể (module) trao đổi với nhau
nên việc thiết kế và lập trình sẽ đợc thực hiện theo quy trình nhất
định chứ không phải dựa vào kinh nghiệm và kỹ thuật nh trớc. Điều
này đảm bảo rút ngắn đợc thời gian xây dựng hệ thống và tăng năng
xuất lao động.
Nguyên lý che dấu thông tin giúp ngời lập trình tạo ra đợc những ch-
ơng trình an toàn không bị thay đổi bởi những chơng trình khác.
Có thể xây dựng đợc các ánh xạ đối tợng của bài toán vào đối tợng
của chơng trình.
Cách tiếp cận thiết kế đặt trọng tâm vào dữ liệu giúp ta xây dựng đợc
mô hình chi tiết và gần với dạng cài đặt hơn.
Những hệ thống hớng đối tợng dễ mở rộng, nâng cấp thành những hệ
thống lớn hơn.
Kỹ thuật truyền thông báo trong việc tao trao đổi thông tin giữa các
đối tợng giúp cho việc mô tả giao diện với các hệ thống bên ngoài
đơn giản hơn.
Có thể quản lý độ phức tạp của những sản phẩm phần mềm.
I.3. Đối tợng
Đối tợng là thực thể đợc xác định trong thời hạn hệ thống hớng đối t-
ợng hoạt động. Nh vậy đối tợng là con ngời, sự vật, thiết bị, bảng dữ liệu
cần xử lý trong chơng trình. Mỗi đối tợng gồm có: tập các thuộc tính
(attribute) và tập các hàm (function) để xử lý các thuộc tính đó.[5]
Một đối tợng có thể đợc minh hoạ nh sau :
Đối T ợng
Thuộc
Tính
Hàm

Hiển thị
Hình 2. Mô tả đối t ợng hình chữ nhật.
Cấu trúc dữ liệu mẫu với C++
I.5. Trừu tợng hoá dữ liệu và bao gói thông tin
Việc đóng gói dữ liệu và các hàm vào một đơn vị cấu trúc đợc xem
nh một nguyên tắc (che dấu) thông tin, dữ đợc tổ chức sao cho thế giới bên
ngoài không truy nhập đợc vào mà chỉ cho phép các hàm trong cùng lớp
hoặc trong những lớp có quan hệ thừa với nhau đợc quền truy nhập. Chính
các hàm thành phần của lớp sẽ đóng vai trò nh là giao diện giữa dữ liệu của
đối tợng và phần còn lại của chơng trình. Nguyên tắc bao gói dữ liệu để
ngăn cấm sự truy nhập trực tiếp trong lập trình đợc gọi là che dấu thông tin.
Trừu tợng hoá là cách biểu diễn những đặc tính chính và bỏ qua
những chi tiết vụn vặt hoặc những giải thích. Để xây dựng các lớp chúng ta
phải sử dụng khái niệm trừu tợng hoá. Trong lập trình hớng đối tợng lớp đ-
ợc sử dụng nh dữ liệu trừu tợng. Ví dụ nh chúng ta có thể định nghĩa một
lớp là danh sách các thuộc tính trừu tợng nh là kích thớc, hình dáng mầu và
các hàm xác định trên các thuộc tính này để mô tả các đối tợng trong không
gian hình học.
I.6. Thừa Kế
Thừa kế là quá trình trong đó các đối tợng của lớp này đợc quyền sử
dụng một số tính chất của các đối tợng của các lớp khác.
Nguyên lý thừa kế hỗ trợ cho việc tạo ra cấu trúc phân cấp các lớp.
Nó đợc thực hiện dựa trên nguyên lý tổng quát hoá hoặc chi tiết hoá các đặc
tính của các đối tợng trong các lớp.
Trong lập trình hớng đối tợng, khái niệm thừa kế kéo theo ý tởng sử
dụng lại. Nghĩa là một lớp đã đợc xây dựng (lớp cha hay lớp cơ sở) của
chúng có thể bổ sung thêm các tính chất mới để tạo các lớp mới (lớp con
hay lớp dẫn xuất) mô tả chi tiết hơn về một nhóm đối tợng cụ thể (theo
nguyên lý chi tiết hoá) hoặc từ một nhóm lớp có số đặc tính giống nhau gộp
chung các đặc tính đó lại để tạo ra một lớp mới, đợc gọi là lớp trừu tợng

Chẳng hạn nh hàm VE() trong hình 3, theo nguyên lý kế thừa thì mọi
đối tợng đều có thể sử dụng hàm này để vẽ theo yêu cầu. Tuy nhiên, thuật
toán thực hiện hàm VE() là duy nhất đối với từng đối tợng Hình_TRòn,
Đa_Giác, Đơng_th và vì vậy hàm VE() sẽ đợc định nghĩa lại khi các
đối tợng tơng ứng đợc xác định.
Cấu trúc dữ liệu mẫu với C++
I.8. Truyền thông báo
Các đối tợng gửi và nhận thông tin với nhau giống nh con ngời trao
đổi thông tin với nhau. Chính nguyên lý trao đổi thông tin với nhau bằng
cách truyền thông báo cho phép chúng ta dễ dàng xây dựng đợc hệ thống
mô phỏng gần những hệ thống trong thế giới thực. Truyền thông báo cho
một đối tợng tức là báo cho nó phải thực hiện một việc gì đó. Cách ứng xử
cả đối tợng sẽ đợc mô tả ở trong lớp thông qua các hàm (hay còn đợc gọi là
lớp dịch vụ). Thông báo truyền đi phải chỉ ra đợc hàm cần thực hiện trong
đối tợng nhận thông báo. Hơn thế nữa thông báo truyền đi phải xác định tên
đối tợng, tên hàm và thông tin truyền đi.
Ví dụ: Lớp CONG_NHAN có thể là đối tợng cụ thể đợc xác định bởi
HO_TEN nhận đợc thông báo cần TINH_LUONG đã đợc xác định trong
lớp CONG_NHAN. Thông báo đó sẽ đợc xử lý nh sau:
Mỗi đối tợng chỉ tồn tại trong một thời gian nhất định. Đối tợng tạo
ra khi nó đợc khai báo và sẽ bị huỷ bỏ khi chơng trình ra khỏi miền xác
định của đối tợng đó. Sự trao đổi thông tin chỉ có thể thực hiện trong thời
gian đối tợng tồn tại.
đối t ợng thông báo thông tin
CONG_NHAN.TINH_LUONG(HO_TEN)
Hình Học
VE()
ĐA_GIAC
VE(ĐA_GIAC)
ĐƯƠNG_TH

phần giải quyết những vấn đề tồn tại trong công nghệ phần mềm.
C
++
là một công cụ lập trình hớng đối tợng
C
++
là công cụ lập trình hớng đối tợng. Ban đầu đợc gọi là "C with class" (C
với các lớp) sau đó C
++
đợc phát triển vào những năm đầu thập kỉ 80 ở
AT&T Bell Laboratories. Nó đợc phát triển trên nền ngôn ngữ C.
Cấu trúc dữ liệu mẫu với C++
C
++
là một tập mở rộng của C, vì thế hầu hết các tính chất của C vẫn đợc sử
dụng trong C
++
. Điều này có nghĩa là hầu nh toàn bộ các chơng trình đợc
viết bằng C thì cũng là chơng trình của C
++
. Tuy nhiên cũng có một số khác
biệt làm cho chơng trình C không thực đợc dới chơng trình C
++
.
Ba khái niệm quan trọng của C
++
đợc bổ xung vào C là: lớp, hàm tải
bội và toán tử tải bội. Những khái niệm cho phép chúng ta tạo ra những
kiểu dữ liệu trừu tợng, kế thừa nhiều tính chất của những kiểu dữ liệu đã
xây dựng và hỗ trợ cho việc sử dụng cơ chế tơng ứng bội cho C

private: // vùng riêng (mặc định)
// khai báo dữ liệu và các hàm
public:// vùng công cộng
// khai báo dữ liệu và các hàm
};
// kết thúc bằng dấu ";"
Từ khoá class định nghĩa một kiểu dữ liệu trừu tợng có tên gọi là
class_name. Trong nội dung lớp có các biến và hàm, các biến và hàm đợc tổ
chức thành hai nhóm: dùng chung (public) và sở hữu riêng (private,
protected). Những thành phần đợc khai báo private, protected chỉ đợc truy
nhập bởi các hàm thành phần của lớp, riêng đối với các hàm kiểu protected
thì cho phép các hàm thành phần trong các lớp có quan hệ kế thừa (lớp dẫn
xuất) mới đợc truy nhập. Ngợc lại các thành phần kiểu public có thể đợc
truy nhập từ bên ngoài lớp. Nguyên lí che dấu thông tin của C
++
đợc thực
hiện bằng cách sử dụng dạng khai báo private hoặc protected. Từ khoá
private là tuỳ chọn, nếu mặc định thì những thành phần không đợc khai báo
là public sẽ là private.
Cấu trúc dữ liệu mẫu với C++
Những biến đợc khai báo trong các lớp đợc gọi là dữ liệu thành phần,
còn các hàm đợc gọi là hàm thành phần. Các hàm thành phần kiểu private
chỉ có thể truy nhập đợc các dữ liệu và hàm trong vùng private, còn các
hàm thành phầm kiểu public thì truy nhập đợc tất cả các kiểu dữ liệu và các
hàm trong cùng lớp.
Trong lớp Point thì các biến đợc khai báo trong vùng private (vùng
riêng) là dữ liệu thành phần, còn các hàm trong vùng public (vùng chung) là
các thành phần. Dữ liệu thành phần của lớp không thể có kiểu của chính lớp
đó, nhng có thể là kiểu con trỏ của lớp này, ví dụ:
class A

II.1.3. Các thành phần dữ liệu
Các thành phần dữ liệu trong một lớp không thể đợc khai báo kiểu
auto, register, hay extern. Chúng có thể là các enum, nhóm bit và các kiểu
dữ liệu có sẵn hoặc của ngời sử dụng định nghĩa. Thành phần dữ liệu cũng
có thể là một đối tợng, tuy nhiên chúng chỉ có thể là những đối tợng của các
lớp đã đợc khai báo hoặc đã đợc định nghĩa trớc đó.
*Dữ liệu thành phần kiểu private
Khi các thành phần dữ liệu một lớp đợc khai báo theo kiểu private thì
chỉ có thánh phần của chính lớp đó hoặc các lớp bạn của nó mới đợc truy
nhập đến các thành phần này.
*Dữ liệu thành phần public
Nếu ta khai báo lại các thành phần dữ liệu trong lớp Point sang dạng
public, tức là: Lúc đó mội thành phần trong lớp Point đều có thể đợc truy
nhập từ thế giới bên ngoài.
*Dữ liệu thành phần protected
Để sử dụng đợc các thành phần dữ liệu của một lớp từ các lớp khác
nhng phải bảo đảm nguyên lý che dấu thông tin thì chúng ta phải khai báo
kiểu protected. Các thành phần dữ liệu trong protected chỉ cho phép các
thành phần trong cùng lớp và trong dẫn xuất truy nhập đến.
*Dữ liệu thành phần tĩnh static
Dữ liệu thành phần tĩnh là dữ liệu đợc khai báo với từ khoá static ở
đầu. Khi dữ liệu thành phần tĩnh thì tất cả các thể hiện của lớp đó đều đợc
phép dùng chung thành phần dữ liệu này. Dữ liệu theo kiểu static đợc phân
bố ở một vùng bộ nhớ cố định trong quá trình liên kết cũng giống nh các
biến đợc khai báo theo kiểu tổng thể (global).
Cấu trúc dữ liệu mẫu với C++
Biến dữ liệu tĩnh có những tính chất sau:
Khi đối tợng đầu tiên của lớp đợc tạo lập thì các biến dữ liệu tĩnh
đợc gán là 0.
Chỉ có một bản sao của biến tĩnh đợc tạo ra cho cả lớp và sẽ đợc

, việc định nghĩa này là
hoàn toàn hợp lệ, các hàm này khác nhau về số lợng hoặc kiểu của các đối
số cho hàm. Các hàm nh vậy đợc gọi là hàm tải bội (kể cả cấu từ).
II.2.2. Toán tử tải bội.
Đã nhiều lần chúng ta khẳng định rằng trong C
++
chúng ta có thể tạo
ra những kiểu dữ liệu mới có hành vi giống nh các kiểu dữ liệu cơ sở. Hơn
thế nữa chúng ta còn có thể đa thêm định nghĩa mới cho những toán tử đợc
định nghĩa trớc. Những toán tử cùng tên thức hiện đợc nhiều chức năng
khác nhau đợc gọi là toàn tử tải bội.
Quy tắc xây dựng toán tử tải bội:
1. Chỉ có thể xây dựng những toán tử đã có trong C
++
để thành toán tử
bội . Không thể tự ý tạo ra những toán tử mới .
2. Toán tử tải bội phải có ít nhất một toán hạng có kiểu là kiểu đợc
định nghĩa bởi ngời sử dụng .
3. Chúng ta không thể tự ý làm thay đổi ý nghĩa cơ bản của toán tử
đã đợc định nghĩa trớc . Ví dụ, chúng ta không thể định nghĩa lại
đợc các phép +, - đối với các kiểu cơ sở ( int, float).
4. Toán tử tải bội đợc xây dựng và sử dụng tuân theo quy tắc cú pháp
của toán tử cơ sở nh đã đợc định nghĩa trong ngôn ngữ.
Cấu trúc dữ liệu mẫu với C++
5. Một số toán tử không thể định nghĩa thành toán tử tải bội đợc
( bảng 3-1).
6. Một số toán tử không thể sử sụng với friend để thành hàm toán tử
tải bội( bảng 3-2), nhng có thể sử dụng hàm thành phần để đổi
thành hàm toán tử tải bội.
7. Hàm thành phần toán tử tải bội một ngôi không có tham biến và trả

Trong đó return-type là kiểu của kết quả thực hiện các phép toán, op
là toán tử tải bội đứng sau là từ khoá operator op đợc gọi là hàm các toán tử
với các tham biến là arg-list.
Hàm các toán tử tải bội phải là hàm thành phần (không phải là hàm
tĩnh) hoặc là hàm thân thiện (friendly). Sự khác nhau cơ bản giữa chúng là:
Hàm thành phần tải bội không có đối số cho hàm toán tử một ngôi
và một đối số cho hàm toán tử hai ngôi .
Hàm tải bội thân thiện có một đối số cho hàm toán tử một ngôi ,
hai đối số cho hàm toán tử hai ngôi .
Có sự khác nhau này bởi vì đối với hàm thành phần thì đối tợng đợc
sử dụng liên quan đến hàm thành phần đựơc tự động truyền vào tham số
cho nó còn hàm thân thiện thì không làm đợc điều đó.
Ví dụ:
class Vector
{
private:
int v[100];
Cấu trúc dữ liệu mẫu với C++
public:
openrator + (vector); // cộng vector, hàm thành phần.
openrator - (vector & a); // trừ vector, hàm thành phần.
openrator = (const vector & a); // phép gán vector, hàm thành phần.
openrator -(); // đổi dấu vector, hàm thành phần.
friend vector+(vector, vector);// cộng vector hàm thân thiện.
int oprator == (vector);// so sánh hàm thành phần.
friend int == (vector, vector);// so sánh, hàm thân thiện.
};
Trong đó các vector là lớp các đối tợng.
Quá trình xác định các hàm toán tử tải bội đợc thực hiện nh sau:
Định nghĩa lớp để xác định kiểu dữ liệu sẽ đợc xác định trong

Dạng tổng quát của toán tử quy hồi kiểu tải bội ở dạng hàm:
operator double() chuyển lớp vector sang kiểu double. Khi đó
trong chơng trình chúng ta có thể viết:
double len = double(v1); // v1 là đối tợng trong lớp vector hoặc:
double len = v1;
Hàm toán tử kiểu quy hồi phải thỏa mãn những tính chất sau:
- Nó phải là hàm thành phần của một lớp.
- Nó không chỉ định kiểu giá trị quay trở lại.
- Nó không có đối số.
Từ một lớp sang một lớp khác: việc chuyển đổi kiểu giữa những
đối tợng ở nhiều lớp khác nhau đợc thực hiện thông qua toán tử
khởi tạo đối tợng hoặc hàm đổi kiểu. Hàm đổi kiểu phải là hàm
thành phần: operator type_name0. Chuyển đối tợng trong lớp chứa
nó sang kiểu type_name. Type_name có thể là kiểu bất kỳ. Nếu
chuyển kiểu giữa các đối tợng thông qua cấu tử thì thực chất là
sao chép dữ liệu giữa các đối tợng.
Cấu trúc dữ liệu mẫu với C++
II.3. Kế thừa và sự mở rộng các lớp
Khả năng sử dụng lại là đặc tính quan trọng của lập trình hớng đối t-
ợng. Việc sử dụng lại những đơn thể chơng trình, những lớp đã đợc phát
triển tốt, đã đợc kiểm nghiệm không những tiếp kiệm đợc tiền của, thời gian
mà còn làm tăng thêm những khả năng tơng thích, độ tin cậy của hệ thống.
C
++
hỗ trợ rất mạnh cho những khái niệm về sử dụng lại. Lớp đợc
thiết kế trong C
++
luôn luôn có thể đợc sử dụng lại theo nhiều cách khác
nhau. Khi một lớp đã đợc định nghĩa, đợc kiểm nghiệm thì ngời lập trình
khác có thể sử dụng nó trong các mục đích riêng của mình. Những lớp này

đối tợng của lớp dẫn xuất có thể truy nhập đến thành phần public của, lớp
cơ sở (hình 3-3).
Trong cả hai trờng hợp, thành phần private của lớp cơ sở hoàn toàn
không đợc kế thừa. Vì thế những thành phần private của lớp cơ sở không
khi nào trở thành thành phần của lóp dẫn xuất.
II.3.1. Kế thừa đơn
Kế thừa đơn là một lớp chỉ kế thừa một lớp đã có.
Chúng ta có thể mô tả nh sau:
A
B
Lớp cơ sở
Lớp dẫn xuất
class A
Dữ liệu và hàm
public
Dữ liệu và hàm
private
Dữ liệu và hàm
protected
A
B
Lớp cơ sở
Lớp dẫn xuất
Cấu trúc dữ liệu mẫu với C++
*Lớp B kế thừa kiểu public từ lớp A:
class B: public A
{
// Dữ liệu và hàm vùng private
// Dữ liệu và hàm vùng protected
// Dữ liệu và hàm vùng public

X.show_a();
đều không thực hiện đợc, bởi vì chúng đã trở thành private của lớp B.
Hình 3-5 Bổ sung thành phần kế thừa vào vùng private.
Chúng ta thấy rằng, những thành phần khai báo ở vùng private của
lớp cơ sở không đợc kế thừa. Do vậy mà lớp kế thừa của lớp dẫn xuất không
sử dụng đợc những thành phần mà nó kế thừa. Chúng ta sẽ thực hiện nh thế
nào khi trong lớp dẫn xuất có nhu cầu kế thừa những thành phần dữ liệu
private của lớp cơ sở. Điều này có thể thực hiện đợc bằng cách chuyển dữ
kiệu thành phần đặc khai báo trong vùng private sang vùng public. Nhng
khi đó thì dữ liệu đó lại có thể truy nhập bởi tất cả những thành phần khác
trong chơng trình. Điều này phá vỡ nguyên lý che dấu thông tin mà chúng
ta cần thực hiện.
Để giải quyết vấn đề trên, C
++
đa thêm thể khai báo protected (đợc
bảo vệ) cho những thành phần của lớp cơ sở cần đợc kế thừa chỉ trong
những lớp dẫn xuất trực tiếp. Những thành phần đợc khai báo protected có
thể đợc truy nhập bởi những thành phần trong cùng lớp và trong những lớp
Vùng public
Dữ liệu và
hàm public B
Vùng private
Dữ liệu và hàm
public A
Dữ liệu và hàm
private B
class B