T i li u tham kh o à ệ ả
môn h c c u trúc dọ ấ ữ
li uệ

- 1 -
LỜI NÓI ĐẦU
Giáo trình này được viết cho sinh viên các trường Cao đẳng Đại học
Để học tốt giáo trình này sinh viên cần có kiến thức về tin học cơ sở và đã biết một ngôn
ngữ lập trình bậc cao như Pascal, Delphi, C hay C
++
...
Giáo trình được viết nhằm những mục tiêu sau đây:
• Giới thiệu cho học sinh về khái niệm về kiểu dữ liệu trừu tượng.
• Cung cấp cho học sinh kiến thức cơ bản về những kiểu dữ liệu trừu tượng, cấu
trúc dữ liệu thông dụng, nâng cao và những thao tác trên các cấu trúc đó.
• Cung cấp một số thuật toán cơ bản và rèn luyện một số kĩ năng phân tích thuật
toán cho học sinh.
• Rèn luyện cho học sinh cách áp dụng các cấu trúc dữ liệu đã học và tư duy thuật
toán để có thể thiết kế và cài đặt một số chương trình bằng một ngôn ngữ bậc
cao.
Để có thể học tốt các chương sau, sinh viên cần đọc kĩ chương 1 và chương 2. Chương
1 giới thiệu những khái niệm cơ bản về thuật giải. Chương 2 giới thiệu những khái
niệm cơ bản về kiểu dữ liệu trừu tượng. Đây là khái niệm mới đối với học sinh. Một
kiểu dữ liệu trừu tượng là một tập hợp các đối tượng và được xác định hoàn toàn bởi
các phép toán có thể biểu diễn trên các đối tượng đó. Người sử dụng được phép tìm
hiểu các đối tượng và thực hiện các thao tác trên các đối tượng của kiểu dữ liệu thông
qua các phép toán đó mà không cần quan tâm đến việc đối tượng được cài như thế nào
trong ngôn ngữ lập trình. Chúng tôi có đưa ra một vài ví dụ đơn giản về kiểu dữ liệu
trừu tượng, cách đặc tả và xây dựng chúng để định hướng cho việc đặc tả và xây dựng
những kiểu dữ liệu trừu tượng trong những chương sau.
Trong khi trình bày mỗi kiểu dữ liệu trừu tượng ở mỗi chương sau, chúng tôi cố gắng

Cuối mỗi chương đều có hệ thống bài tập để học sinh làm và tự kiểm tra kiến thức của
mình.
Cuối cùng là phần phụ lục, trong đó chúng tôi có đưa ra một số bài tập lớn, để học sinh
áp dụng những kiến thức đã học tập giải quyết những vấn đề phức tạp hơn so với bài tập
sau mỗi chương. Với những bài tập lớn này, để nâng cao hiệu quả, yêu cầu học sinh cần
- 3 -
đặc tả rõ bài toán, phân tích và thiết kế thuật giải, sau đó cài đặt trên một ngôn ngữ cụ
thể. Tiếp theo học sinh cần phải kiểm thử phần mềm mình vừa cài đặt và có những
nhận xét về độ phức tạp của thuật toán mình thiết kế, về các hướng cần mở rộng cho các
bài tập này. Chỉ khi nào học sinh làm tốt các bài tập lớn đó mới có thể nói là họ đã
thành công trong việc học tập môn học này.
Chủ biên và hiệu đính toàn bộ nội dung bản thảo:
Chương 1: Mở đầu
chương 2: .
Chương 3: .
Chương 4,
Chương 6:
Chương 7:
Chương 8:
- 4 -
CHƯƠNG I: MỞ ĐẦU
Chương này trình bày một số khái niệm cơ bản đầu tiên về bài toán theo quan điểm Tin
học, thuật giải, cấu trúc dữ liệu, mối quan hệ giữa cấu trúc dữ liệu và thuật giải. Những
khái niệm về độ phức tạp của thuật giải và phân tích thuật giải cũng được giới thiệu
trong chương.
1.1. Khái niệm về cấu trúc dữ liệu và thuật giải
1.1.1. Khái niệm bài toán
Trong phạm vi Tin học, ta có thể quan niệm bài toán là bất cứ việc gì ta muốn máy tính
thực hiện. Như vậy những việc như viết một dòng chữ ra màn hình, giải phương trình
bậc hai, giải hệ phương trình bậc nhất hai ẩn số, quản lý các cán bộ trong một cơ quan...

Output: Các số nguyên tố p
1
,..., p
k
; các số nguyên dương α
1
,...,α
k
; sao cho
n = p
1
α
1
...p
k
α
k
;
Ví dụ 4. Bài toán kiểm tra tính nguyên tố:
Input: Số nguyên dương n;
Output: Trả lời câu hỏi n là số nguyên tố hay không?.
Ví dụ 5. Bài toán quản lý hồ sơ cán bộ:
Input: Hồ sơ gốc của các cán bộ trong cơ quan;
Output: Những biểu bảng thống kê, phân loại cán bộ, các quy trình lưu trữ, quản
lý hồ sơ cán bộ.
Ví dụ 6. Bài toán thứ 10 của Hilbert:
Input: P là đa thức (nhiều ẩn) với hệ số nguyên;
Output: Trả lời câu hỏi P có nghiệm nguyên hay không?
Qua các ví dụ trên, ta thấy các bài toán được cấu tạo bởi hai thành phần cơ bản:
- Thông tin vào (input): Cho ta biết những thông tin đã có (các giả thiết);

1.1.3. Mô tả thuật giải
Ngay từ khi học môn Tin học cơ sở học sinh đã được làm quen với khái niệm thuật giải
và được học cách mô tả hay diễn đạt những thuật giải đơn giản. Thuật giải cho những
bài toán nhỏ hay thuật giải cho những bài toán lớn khi được thiết kế ở mức thô hay được
mô tả bằng sơ đồ khối. Cách dùng sơ đồ khối để minh họa thuật giải có lợi thế là rất
trực quan, dễ hiểu. Tuy nhiên, với những bài toán lớn, phức tạp, việc dùng sơ đồ khối để
mô tả thuật giải có những hạn chế nhất định. Hạn chế này là có thể là do khuôn khổ
giấy hay màn hình ta dùng để vẽ sơ đồ hay tầm bao quát, theo dõi của mắt ta trên sơ đồ.
- 7 -
Hạn chế này cũng nảy sinh khi bài toán của ta phức tạp, có nhiều vòng lặp lồng nhau,
khi đó việc trình bày sơ đồ có rất nhiều hạn chế.
Ta cũng hay dùng phương pháp liệt kê các bước giải để mô tả thuật giải. Phương pháp
này cũng rất dễ hiểu đối với các bài toán nhỏ. Tuy nhiên, đối với các bài toán lớn, việc
liệt kê sẽ trở nên khó khăn và nếu được thì cũng gây khó khó theo dõi, nhất là đối với
vòng lặp. Hơn thế nữa việc liệt kê các bước giải ta hay phải dùng ngôn ngữ tự nhiên để
mô tả các thao tác nên việc diễn đạt nhiều khi rất khó chính xác.
Phương pháp thứ ba hay được dùng để mô tả thuật giải là dùng giả mã hay ngôn ngữ
phỏng trình. Việc dùng ngôn ngữ phỏng trình khắc phục được những nhiều nhược điểm
của hai phương pháp trên, đặc biệt đối với những bài toán lớn, phức tạp. Cũng có ý
kiến là ta nên chọn một ngôn ngữ lập trình thông dụng làm công cụ để diễn đạt thuật
giải. Tuy nhiên, ai cũng biết là thuật giải cần phải độc lập với ngôn ngữ lập trình. Khi
thuật giải được viết tốt nó có thể được cài đặt bằng bất cứ ngôn ngữ lập trình nào, tùy
theo tính thích hợp của bài toán và ý muốn của người lập trình. Hơn thế nữa, thiết kế
thuật giải là một trong những công việc quan trọng nhất của người lập trình. Nếu ta
chọn một ngôn ngữ lập trình để mô tả thuật giải thì lúc nào ta cũng phải chú ý tuân thủ
các tiểu tiết cú pháp của ngôn ngữ. Điều đó sẽ gây mất thì giờ và ảnh hưởng lớn đến sự
tập trung vào công việc chính là thiết kế và mô tả thuật giải.
Sau đây là ví dụ về mô tả thuật giải tìm ước chung lớn nhất của hai số nguyên m và n.
Cách 1: Dùng sơ đồ khối
- 8 -

trình bày mà người lập trình thường hay chọn phương pháp thích hợp nhất trong ba
phương tiện nêu trên.
- 9 -
Như vậy, việc diễn tả một thuật giải giải một bài toán nào đó có nghĩa là trình bày trình
tự các thao tác cần thực hiện. Tuy nhiên, đó chỉ là cách diễn tả thuật giải giữa người với
người.
Ngay khi thuật giải đã được diễn tả như vậy, con người có thể dùng để giải bài toán với
mỗi bộ dữ liệu vào. Tuy nhiên, theo cách diễn tả này, máy tính vẫn chưa thể thực hiện
các thao tác trong thuật giải dù các thao tác đó rất đơn giản. Thuật giải cần được diễn tả
thành một chương trình gồm những dòng lệnh. Mỗi lệnh là một việc nào đó mà ta đòi
hỏi máy tính thực hiện.
Ngôn ngữ dùng để viết chương trình được gọi là ngôn ngữ lập trình.
Phần đọc thêm
Khái niệm thuật giải trình bày ở trên đủ để ta có thể hình dung để có thể chuyển giao cho
máy tính việc giải một bài toán ta cần diễn tả cách giải như thế nào và cũng là cách nhận
biết thế nào là thuật giải đối với một bài toán nào đó.
Trong quá trình nghiên cứu cách giải bài toán theo nghĩa nêu trên,trong toán học đã diễn
ra một quá trình phát triển đầy kịch tính. Cho tới đầu thế kỷ 20, với lòng tin tiên nghiệm
vào việc mọi bài toán được phát biểu đúng đắn đều có thuật giải giải, nhiều nhà toán học
đầy tài năng và tâm huyết đã tiến công vào các bài toán đang tồn tại như những lời thách
đố trí tuệ con người.
Vấn đề then chốt nhất của lý thuyết tính toán phát sinh ở đây. Để chứng minh một bài toán
nào đó có thuật giải giải nó, ta chỉ cần đề ra một thuật giải theo quan niệm trực giác của
khái niệm này và kiểm định tính đúng đắn của nó đối với bài toán đã cho. Tuy nhiên, khi
cần chứng minh việc không có thuật giải giải một bài toán nào đó, quan niệm trực quan về
thuật giải không thể là cơ sở bảo đảm cho một chứng minh toán học chặt chẽ được. Do đó,
muốn chứng minh những điều khẳng định "không có thuật giải giải một bài toán nào dó",
ta cần có một định nghĩa toán học cho khái niệm thuật giải.
Vào khoảng những năm 1930-1936, lần lượt các nhà toán học K.Gõdel, S. Kleene,
A.Church, A.Turing đã đề ra một số định nghĩa khác nhau cho khái niệm thuật giải.

1
, Min= a
1
, i=2.
Bước 2. Nếu i<N thì thực hiện bước 3, nếu không thì kết thúc.
Bước 3
3.1. Nếu a
i
>Max thì Max= a
i
.
3.2. Nếu a
i
<Min thì Min= a
i
.
3.3. Tăng i một đơn vị và quay về bước 2.
- 11 -
Rõ ràng số thao tác cần tiến hành không quá n.
Ví dụ 3. Thuật giải để sắp xếp một dãy số cho trước thành một dãy đơn điệu không
tăng.
Ta xét bài toán sau:
Input: Số nguyên dương n và dãy n số a
1
, . . ., a
n
.
Output: Dãy số trên được sắp xếp lại thành một dãy số không tăng tức là số hạng
trước lớn hơn hay bằng số hạng sau.
Một thuật giải giải bài toán này có thể nói vắn tắt như sau: với mỗi chỉ số i, 1≤i≤n-1, xét

giải tương thích, hiệu quả là rất quan trọng. Chính vì thế cấu trúc dữ liệu và thuật giải là
hai thành tố quan trọng của chương trình máy tính và đều là những đối tượng nghiên
cứu quan trọng của khoa học máy tính. Hơn nữa, chúng có quan hệ mật thiết với nhau,
ảnh hưởng và điều phối lẫn nhau để tạo ra lời giải cho bài toán. Trong phạm vi của giáo
trình này, ta nghiên cứu những cấu trúc dữ liệu cơ bản và những thuật giải hay thao tác
thường thực hiện trên các cấu trúc dữ liệu đó.
1.2. Khái niệm về độ phức tạp của thuật giải
Mỗi thuật giải chỉ giải một bài toán nào đó nhưng có thể có nhiều thuật giải khác nhau
giải cùng một bài toán. Ví dụ, để sắp xếp một dãy số bất kỳ thành một dãy đơn điệu, có
rất nhiều thuật giải khác nhau.
Cùng một bài toán, có thể có nhiều thuật giải khác nhau. Việc lựa chọn một thuật giải
thích hợp nhất hay tốt nhất cho một bài toán luôn là mối quan tâm của người lập trình.
Vậy làm thế nào để chọn được thuật giải thích hợp nhất trong những thuật giải của một
bài toán? Nói cụ thể hơn, những tiêu chí nào là quan trọng để đánh giá một thuật giải?
Thuật giải càng trong sáng, có cấu trúc tốt thì mã hóa càng nhanh, bảo trì chương trình
càng dễ dàng và do đó giảm được giá thành của phần mềm. Tuy nhiên, có những thuật
giải rất trong sáng, dễ hiểu nhưng lại không khả thi về mặt thời gian thực hiện hay
không gian nhớ cần thiết khi thực hiện nó. Vậy làm thế nào để đánh giá được thời gian
thực hiện và không gian nhớ dành cho một thuật giải? Cách đơn giản nhất là ta cài đặt
thuật giải rồi cho máy chạy chưong trình với một tập dữ liệu vào nào đó và đo thời gian
thực hiện chương trình cũng như tính không gian nhớ cần thiết cho nó và ta có kết quả
về thời gian và không gian cần thiết cho thuật giải. Tuy nhiên, cách tính này chỉ mới áp
dụng trên một tập dữ liệu đầu vào cụ thể. Sẽ là không thích hợp nếu ta dùng kết quả này
để áp dụng chung cho các tập dữ liệu đầu vào khác. Nếu bài toán đơn giản và đầu vào
- 13 -
chỉ gồm một số ít phần tử thì ta cũng chẳng cần quan tâm nhiều đến việc lựa chọn thuật
giải làm gì. Ví dụ như bài toán sau: Ta cần chọn ra số lớn nhất trong 3 số nguyên hay
thậm chí trong vài chục số nguyên đã cho. Bạn có thể dùng bất cứ thuật giải nào bạn
nghĩ ra hay bạn thích, miễn là nó đúng, có lẽ thời gian thực hiện chúng cũng không khác
nhau bao nhiêu. Một thuật toán tìm kiếm tuần tự để tìm một số điện thoại trong một

Với mỗi bài toán, ta xét kích thước đầu vào hay gọi đơn giản là kích thước của bài toán.
Kích thước đầu vào một bài toán được đo bằng số lượng dữ liệu vào cần xử lý. Ví dụ
nếu dữ liệu vào là một dãy số có N số hạng thì kích thước bài toán dược xem bằng N,
nếu dữ liệu vào là một đồ thị có N đỉnh, kích thước bài toán bằng N, nếu dữ liệu vào là
một xâu ký tự độ dài L thì kích thước bài toán bằng L, nếu dữ liệu vào là một bảng có M
dòng và N cột thì kích thước bài toán bằng MxN. . .
Khi đó, số các thao tác cơ bản mà một thuật giải sẽ được biểu thị như một hàm f(K) của
biến số K là kích thước của bài toán. Khi đánh giá hàm f(K) người ta thường dùng ký
hiệu O hay chính xác hơn là khái niệm Ω của giải tích có nghĩa là cùng bậc. Ví dụ, giải
thuật tìm Min-Max của một dãy số trong Mục 8.1 có độ phức tạp 2N, ta nói độ phức tạp
đó cỡ Ω(N) có nghĩa là cùng bậc với N khi N tiến đến vô cùng; tương tự, giải thuật sắp
xếp dãy số có độ phức tạp cở Ω(N
2
).
Việc dùng ký hiệu Ω để thể hiện độ phức tạp của giải thuật cho ta một đánh giá tổng thể
không bị sa vào những tính toán tỉ mỉ hơn nhưng không thật cần thiết. Ví dụ, cùng là hai
phép toán cộng và nhân hai số, rõ ràng phép cộng thực hiện nhanh hơn nhiều so với
phép nhân nhưng sự khác biệt đó chỉ thể hiện bằng việc thời gian tính toán sai khác một
hằng số nhân. Do đó, nếu dùng ký hiệu Ω, ta có thể bỏ qua sự khác biệt đó.
Khi nói về độ phức tạp về thời gian, có một số bậc được sử dụng thường xuyên và
người ta đã đặt tên cho chúng. Một cách vắn tắt, nếu một thuật toán có độ phức tạp là t
- 15 -
và t < cn, với n > n
0
và c là một hằng số dương, còn n là kích cỡ đầu vào thì người ta gọi
thuật toán đó có độ phức tạp tuyến tính. Nếu t < cn
2
thì t được gọi là có độ phức tạp
bình phương. Tương tự t được gọi là có độ phức tạp lập phương, đa thức hay mũ nếu
nó có bậc lần lượt của các hàm n

trúc đệ quy.
Với cấu trúc tuần tự: Nếu ta có hai đoạn trình thực hiện tuần tự là P
1
và P
2
, độ phức tạp
của chúng lần lượt là t
1
= O(f(n)), t
2
= O(g(n)) thì độ phức tạp của cả hai đoạn P
1
và P
2

chính là O(max(f(n), g(n)).
Ví dụ: Khi ta thực hiện tuần tự hai đoạn trình P
1
và P
2
, P
1
có

độ phức tạp là O(n
2
) và P
2
có độ phức tạp là O(n
3

nếu số thao tác trong <Nhóm lệnh> là S thì số thao tác cần thực hiện tổng cộng không
lớn hơn S(b-a).
Ví dụ: trong phép nhân hai ma trận vuông A và B cấp n ta có:
Procedure Nhanmatran(A,B)
Var C;
Begin
for i ← 1 to n do
for j ← 1 to n do
Begin
- 17 -
C[i,j] ← 0
for k ← 1 to n do
C[i,j] ← C[i,j] + a[i,k] * b[k,j]
End;
Return C;
End
Ta thấy ngay là vòng lặp trong cùng (k là biến chạy) có độ phức tạp O(n), vòng lặp
trong tiếp theo (j là biến chạy) cũng có độ phức tạp O(n) và vòng lặp ngoài cùng (với i
là biến chạy) với độ phức tạp O(n). Do đó toàn bộ chương trình của ta có độ phức tạp
O(n
3
).
Đối với cấu trúc lặp loại (2) và (3), căn cứ vào điều kiện lô gic, ta có thể ước lượng
được số lần lặp tối đa do đó có thể tính được số tối đa các thao tác cần thực hiện.
Đối với các cấu trúc đệ quy, việc ước lượng số thao tác khó khăn hơn vì nói ta phải tiến
hành tính số thao tác theo một công thức truy hồi.
Sau đây ta sẽ xét một số ví dụ nữa.
Ví dụ 1. Xét bài toán
Input. Mảng một chiều A[1..N] gồm các số nguyên;
Output. Giá trị nhỏ nhất Min và giá trị lớn nhất Max của các phần tử của mảng;

cọc i sang cọc thứ ba, đó là cọc k = 6-i-j, chuyển đĩa thứ M từ cọc i sang cọc j và sau đó
chuyển M-1 đĩa từ cọc k sang cọc j. Nếu viết bằng Pascal, ta có
Procedure Hanoi(M,i,j: Byte);
Begin
If m=0 then Exit;
Hanoi(M-1,i,6-i-j);
Writeln(i,’ – ‘,j);
Hanoi(M-1,6-i-j,j);
End;
- 19 -
Nếu ký hiệu T(M) là số di chuyển cần thực hiện (xem như một thao tác cơ bản), ta có
T(M) = 2.T(M-1) - 1 (*)
Như vậy nếu xem N là kích thước của bài toán thì độ phức tạp tính toán của thuật giải
trên là T(N). Từ hệ thức (*), ta có thể suy ra T(N) = 2
N
- 1.
Hệ thức (*) là một hệ thức truy hồi.
1.3.2. Một số quan điểm phân tích thuật toán
Cách phân tích thuật toán trong mục 8.2.2 còn được gọi là phân tích theo tình huống
xấu nhất (Worst-Case Analysis). Với mỗi thuật giải đối với bài toán kích thước K, ta
luôn đánh giá số tối đa các thao tác cơ bản cần tiến hành là bao nhiêu.
Có nhiều cách khác để phân tích thuật giải như phân tích trung bình (Average Analysis),
phân tích tiệm cận (Asymptotic Analysis).
Ta sẽ giới thiệu cách phân tích trung bình. Câu chuyện bắt đầu từ việc xem xét thuật giải
đơn hình đối với bài toán Quy hoạch tuyến tính. Bài toán này có thể phát biểu trong
ngôn ngữ đại số tuyến tính như sau:
I. Ma trận A gồm M dòng, N cột; Véc tơ cột B M chiều; véc tơ dòng C N
chiều;
O. Cần tìm véc tơ cột N chiều X sao cho AX
≤

+ b
1
X + c
1
= 0 và a
2
X
2
+ b
2
X +
c
2
= 0.
Bài 6. Cho một hình chữ nhật ABCD với hai cạnh nguyên dương AB = M và BC = N.
Hình chữ nhật được chia thành các ô vuông đơn vị. Hãy tìm số ô vuông có điểm chung
với đường chéo AC.
Bài 7. Cho một hình chữ nhật ABCD với hai cạnh nguyên dương AB=M và BC= N.
Hình chữ nhật được chia thành các ô vuông đơn vị. Hãy tìm số ô vuông có điểm trong
chung với đường chéo AC.
Bài 8. Xét dãy vô hạn các chữ số A nhận được bằng cách viết liên tiếp các số nguyên
dương liên tiếp tăng dần bắt đầu từ 1, 2, 3, 4, . . . .
1234567891011121314151617181920212223.....
Cho số nguyên dương N. Hãy tìm chữ số thứ N của dãy A.
Ví dụ với N =13, chữ số thứ N của dãy trên là 1.
Bài 9. Cho số nguyên dương N. Lập dãy B các chữ số nhận được bằng cách viết các số
nguyên dương liên tiếp tăng dần bắt đầu từ 1, 2, 3, 4, . . . cho tới N. Hãy tìm chữ số thứ
N tính từ chữ số cuối cùng của dãy B.
Bài 10. Xét tập A các số nguyên dương được xác định như sau:
1. 1∈A.

Bài 16. Cho hình chữ nhật ABCD và hai điểm khác nhau M, N trên mặt phẳng toạ độ.
Biết toạ độ của A, B, C, D, M, N. Hãy cho biết khả năng nào trong ba khả năng sau xảy
ra:
1. Đoạn MN nằm trong (có thể có điểm trên biên) hình chữ nhật ABCD.
2. Đoạn MN nằm ngoài hình chữ nhật ABCD.
3. Đoạn MN có điểm nằm ngoài hình chữ nhật ABCD và có điểm nằm trong hình chữ
nhật ABCD.
Bài 17. Trên mặt phẳng toạ độ cho đa giác P
1
. . .P
N
. Đa giác được gọi là tự cắt nếu có
hai cạnh P
I
P
I+1
và P
J
P
J+1
với I<J-1 (quy ước đỉnh P
N+1
là đỉnh P
1
) có điểm chung. Đa giác
được gọi là lồi nếu với bất kỳ cạnh nào của đa giác, toàn bộ đa giác nằm về một phía
của đường thẳng đi qua cạnh đó. Biết toạ độ các đỉnh của đa giác. Hãy cho biết đa giác
có tự cắt không? Nếu đa giác không tự cắt, hãy cho biết đa giác có lồi không?. Nếu đa
giác không lồi, hãy chọn một số ít nhất các đỉnh sao cho mọi đỉnh P
1

trong chương trình chính, có thể xem nó như một thao tác mặc dù trong thực tế nó có
thể được cài đặt bằng một dãy gồm rất nhiều thao tác. Chẳng hạn, dùng cơ chế thủ tục
và hàm trong ngôn ngữ Pascal, học sinh đã được học cách xây dựng những đơn vị
chương trình và đưa nó vào thư viện để sử dụng. Ví dụ, ta có chương trình con sắp xếp
nhanh Quicksort như sau:
Procedure Quicksort (A,n), sắp sếp một mảng A gồm n số thực theo chiều tăng dần. Ta
có thể cài đặt và đưa nó vào thư viện và sau đó nó được xem như là một bộ phận của
ngôn ngữ. Ở giai đoạn thiết kế thuật toán, ta chỉ quan tâm đến việc mà thủ tục sẽ thực
- 24 -
hiện mà không cần quan tâm nó thực hiện việc đó như thế nào. Chẳng hạn, nếu ta viết
đoạn chương trình sau đây
For i:=1 to 300 do
Read (DiemThi[i]);
Quicksort (DiemThi, 300);
Người đọc sẽ thấy hoàn toàn dễ hiểu cho dù họ chưa cần biết chi tiết bên trong thủ tục
Quicksort, tức là chưa cần biết nó sắp xếp các phần tử của mảng như thế nào. Việc giấu
được những chi tiết cài đặt bên trong chương trình con làm cho cơ chế sử dụng chương
trình con trở thành một trong những phần quan trọng nhất của bất kì một ngôn ngữ lập
trình bậc cao nào. Cách trừu tượng hoá ta vừa nêu chính là trừu tượng hoá thao tác.
Chọn những thao tác thích hợp thực hiện trên các cấu trúc dữ liệu hợp lý là một công
việc hết sức quan trọng của lập trình. Cũng như việc cần thiết phải trừu tượng hoá thao
tác, bây giờ ta mở rộng ý tưởng trừu tượng hoá cho cấu trúc dữ liệu. Chúng ta sẽ xây
dựng khái niệm kiểu dữ liệu trừu tượng. Để giải thích khái niệm này, trước hết ta xét
sơ đồ sau về các mức cấu trúc dữ liệu:
Mức C.
Mức B.
- 25 -
Kiểu dữ liệu được xây dựng bởi người lập
trình đề giải những bài toán nào đó.
Kiểu dữ liệu được cung cấp bởi các ngôn