Bài giảng Câu trúc dữ liệu và giải thuật

1C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
1
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 
Số tín chỉ: 3
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
2
Phân bổ thời gian
 Giảng lý thuyết trên lớp: 70%
 Thực hành : 30%
 Tự học/ nghiên cứu : 200 %
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
3
Nội Dung Chƣơng Trình
 Chƣơng 1: Một số khái niệm cơ bản về cấu trúc 
dữ liệu và giải thuật 
 Chƣơng 2: Danh sách đặc (condensed list) 
 Chƣơng 3: Danh sách liên kết (linked list) 
 Chƣơng 4: Cây (tree) 
 Chƣơng 5: Bảng băm 
 Chƣơng 6: Đồ thị (Graph) 
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
4
Tài Liệu Tham Khảo
 Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật , Nxb 
Khoa học Kỹ thuật, 1995 .
 Lê Xuân Trường, Cấu trúc dữ liệu bằng ngôn ngữ 
C++, Nxb Thống kê.
 Deshpande, Kakde, C & data structures, 
Massachusetts, 2004 (pdf).
 Introduction To Algorithms 2Nd Edition. 
 Bài soạn của giảng viên.
 Các tài liệu điện tử/ website. 
2C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
5
Đánh giá học phần
 Điểm chuyên cần : 10%
 Kiểm tra/ thi giữa kỳ: 30%
 Thi cuối kỳ : 60%
 Tổng điểm: 10 điểm.
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
6
CHƢƠNG 1
MỘT SỐ KHÁI NIỆM CƠ BẢN VỀ 
CTDL VÀ GIẢI THUẬT 
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
7
Nội Dung
 1.1. Các khái niệm
 1.2. Quan hệ giữa giải thuật và cấu trúc DL
 1.3. Vị trí cấu trúc dữ liệu trong một áp dụng tin 
học
 1.4. Tìm hiểu tổ chức một số CTDL cơ bản 
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
8
1.1. Các khái niệm
 Môn học giới thiệu
Các cấu trúc dữ liệu cơ bản
Các giải thuật điển hình trên các cấu 
trúc dữ liệu đó
 Cấu trúc dữ liệu là một kết hợp nhiều 
thành phần dữ liệu khác nhau thành một 
thực thể thống nhất để thể hiện một kiểu dữ 
liệu
3C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
9
Cấu Trúc Dữ Liệu
 Cách tổ chức lưu trữ dữ liệu.
 Các tiêu chuẩn của CTDL:
 Phải biểu diễn đầy đủ thông tin.
 Phải phù hợp với các thao tác trên đó.
 Phù hợp với điều kiện cho phép của NNLT.
 Tiết kiệm tài nguyên hệ thống.
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
10
Vai Trò Của Cấu Trúc Dữ Liệu
 Cấu trúc dữ liệu đóng vai trò quan trọng trong 
việc kết hợp và đưa ra cách giải quyết bài toán.
 CTDL hỗ trợ cho các thuật toán thao tác trên đối 
tượng được hiệu quả hơn
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
11
Các kiểu cấu trúc dữ liệu cơ bản
 Bản ghi (struct)
 Danh sách (array)
 Danh sách liên kết (list)
 Cây (tree)
 Bảng băm (hash table)
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
12
Thuật toán
 Thuật toán: Một dãy hữu hạn các chỉ thị có thể thi 
hành để đạt mục tiêu đề ra nào đó.
 Ví dụ: Thuật toán tính tổng tất cả các số nguyên 
dương nhỏ hơn n gồm các bước sau:
Bước 1: S=0, i=1; 
Bước 2: nếu i<n thì s=s+i;
Ngược lại: qua bước 4;
Bước 3: 
i=i+1;
Quay lại bước 2;
Bước 4: Tổng cần tìm là S.
4C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
13
Các Tiêu Chuẩn Của Thuật Toán
 Xác định rõ dữ liệu đầu vào 
 Xác định rõ kết quả đầu ra 
 Tính xác định: cùng một dữ liệu đầu vào thì cùng 
đưa đến một kết quả đầu ra 
 Tính khả thi: đơn giản, làm được, thời gian hữu 
hạn
 Tính dừng: sau một số bước hữu hạn thực hiện 
sẽ phải kết thúc
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
14
Sự Cần Thiết Của Thuật Toán
 Tại sao sử dụng máy tính để xử lý dữ liệu?
 Nhanh hơn.
 Nhiều hơn.
 Giải quyết những bài toán mà con người 
không thể hoàn thành được.
 Làm sao đạt được những mục tiêu đó?
 Nhờ vào sự tiến bộ của kỹ thuật: tăng cấu 
hình máy  chi phí cao 
 Nhờ vào các thuật toán hiệu quả: thông minh 
và chi phí thấp 
“Một máy tính siêu hạng vẫn không thể cứu vãn một 
thuật toán tồi!”
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
15
Biễu Diễn Thuật Toán
 Dạng ngôn ngữ tự nhiên
 Dạng lưu đồ (sơ đồ khối)
 Dạng mã giả
 Ngôn ngữ lập trình
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
16
Biểu Diễn Bằng Ngôn Ngữ Tự Nhiên
 NN tự nhiên thông qua các bước được tuần tự 
liệt kê để biễu diễn thuật toán.
 Ưu điểm:
 Đơn giản, không cần kiến thức về về cách 
biểu diễn (mã giả, lưu đồ,...)
 Nhược điểm:
 Dài dòng, không cấu trúc.
 Đôi lúc khó hiểu, không diễn đạt được thuật 
toán.
5C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
17
Lƣu Đồ 
 Là hệ thống các nút, cung hình dạng khác nhau 
thể hiện các chức năng khác nhau.
A
B
A
Begin
End
Thực hiện A Gọi hàm A Vào / Ra dữ liệu
Điều kiện rẻ nhánh B
Đúng
Sai
Nút giới hạn bắt đầu / 
kết thúc chƣơng trình
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
18
Biểu Diễn Bằng Lƣu Đồ
Bắt đầu amax = a0
i<n
i = 1
amax là lớn nhất Kết thúc
amax < ai
i = i+1
amax =ai
S
S
Đ
Đ
Tìm phần tử mang 
giá trị lớn nhất 
trong mảng
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
19
Biểu Diễn Bằng Mã Giả
 Ngôn ngữ tựa ngôn ngữ lập trình:
 Dùng cấu trúc chuẩn hóa, chẳng hạn tựa 
Pascal, C.
 Dùng các ký hiệu toán học, biến, hàm.
 Ưu điểm:
 Đỡ cồng kềnh hơn lưu đồ khối.
 Nhược điểm:
 Không trực quan bằng lưu đồ khối.
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
20
Biểu Diễn Bằng Mã Giả
 Một số quy ƣớc
1. Các biểu thức toán học
2. Lệnh gán: “=” (AB)
3. So sánh: “==”, “!=”
4. Khai báo hàm (thuật toán)
Thuật toán ()
Input: 
Output: 
End
6C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
21
Biểu Diễn Bằng Mã Giả
5. Các cấu trúc:
Cấu trúc chọn:
if  then  [else ] 
Vòng lặp:
while  do
do  while ()
for  do  
6. Một số câu lệnh khác:
Trả giá trị về: return [giá trị]
Lời gọi hàm: (tham số)
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
22
Biểu Diễn Bằng Mã Giả
 Ví dụ: Tìm phần tử lớn nhất trong mảng một 
chiều.
amax=a0;
i=1;
while (i<n)
if (amax<ai) amax = ai;
i++;
end while;
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
23
Biểu Diễn Bằng Ngôn Ngữ Lập Trình
 Dùng ngôn ngữ máy tính (C, Pascal,...) để diễn tả 
thuật toán, CTDL thành câu lệnh.
 Kỹ năng lập trình đòi hỏi cần học tập và thực 
hành (nhiều).
 Dùng phương pháp tinh chế từng bước để 
chuyển hoá bài toán sang mã chương trình cụ 
thể.
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
24
 Học:
 Nhớ giải thuật (mã giả)
 Dùng NNLT cụ thể để minh chứng
7C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
25
Độ Phức Tạp Của Thuật Toán
 Một thuật toán hiệu quả: 
 Chi phí cần sử dụng tài nguyên thấp: Bộ nhớ, 
thời gian sử dụng CPU, 
 Phân tích độ phức tạp thuật toán:
 N là khối lượng dữ liệu cần xử lý.
 Mô tả độ phức tạp thuật toán qua một hàm 
f(N).
 Hai phương pháp đánh giá độ phức tạp của 
thuật toán:
 Phương pháp thực nghiệm.
 Phương pháp xấp xỉ toán học.
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
26
Phƣơng Pháp Thực Nghiệm
 Cài thuật toán rồi chọn các bộ dữ liệu thử nghiệm. 
 Thống kê các thông số nhận được khi chạy các 
bộ dữ liệu đó.
 Ưu điểm: Dễ thực hiện.
 Nhược điểm: 
 Chịu sự hạn chế của ngôn ngữ lập trình.
 Ảnh hưởng bởi trình độ của người lập trình.
 Chọn được các bộ dữ liệu thử đặc trưng cho 
tất cả tập các dữ liệu vào của thuật toán: khó 
khăn và tốn nhiều chi phí. 
 Phụ thuộc vào phần cứng.
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
27
Phƣơng Pháp Xấp Xỉ
 Đánh giá giá thuật toán theo hướng tiệm xấp xỉ 
tiệm cận qua các khái niệm O().
 Ưu điểm: Ít phụ thuộc môi trường cũng như phần 
cứng hơn.
 Nhược điểm: Phức tạp.
 Các trường hợp độ phức tạp quan tâm:
 Trường hợp tốt nhất (phân tích chính xác)
 Trường hợp xấu nhất (phân tích chính xác)
 Trường hợp trung bình (mang tích dự đoán)
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
28
Phƣơng Pháp Xấp Xỉ
Ký pháp
Giả sử T(n) là thời gian thực hiện TT và f(n), g(n), 
h(n) là các hàm xác định dương. 
 Hàm Theta lớn:
T(n) là hàm Theta lớn của g(n): T(n) =Θ(g(n))
nếu  các hằng số dương c1 ,c2 ,n0 sao cho với mọi
n>= n0 :
c1 g(n) <= T(n) <= c2 g(n)
8C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
29
Phƣơng Pháp Xấp Xỉ
 Hàm Omega lớn:
T(n) hàm Omega lớn của g(n):
T(n)=Ω(g(n)) nếu  c và n0 sao cho với
mọi n>= n0
T(n) >= c.g(n)
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
30
Phƣơng Pháp Xấp Xỉ
 Hàm O lớn: 
 T(n) hàm Omega lớn của g(n), T(n) =O (g(n))
nếu  c và n0 sao cho với mọi n>= n0 :
T(n) <=c g(n)
 g(n) giới hạn trên của T(n).
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
31
Ví dụ, nếu T(n) = n2 + 1 thì T(n) = O(n2).
Chọn c=2 và n0 =1, khi đó với mọi n>=1, ta
có T(n)= n2+1 <= 2n2 =2g(n).
Phƣơng Pháp Xấp Xỉ
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
32
Các tính chất
(i) Tính bắc cầu: nếu f(n)= O(g(n)) và g(n)=
O(h(n)) thì f(n)= O(h(n))
(ii) Tính phản xạ: f(n)=O(f(n))
9C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
33
Xác định độ phức tạp
Quy tắc hằng số
Nếu P có T(n)= O(c1f(n)) P có độ 
phức tạp O(f(n)).
CM: T(n)= O(c1f(n)) nên tồn tại c0>0 và n0 >0 
để T(n) = n0.
Đặt c=c0.c1 ta có điều cần CM
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
34
Xác định độ phức tạp
 Quy tắc lấy Max
Nếu P có T(n)= O( f(n)+g(n)) thì P có độ 
phức tạp là O( max ( f(n), g(n))).
CM: T(n) = O( f(n)+g(n)) nên tồn tại n0>0 và c>0 để 
T(n) = n0
vậy T(n) <= cf(n) +cg(n) <= 2c max (f(n),g(n)) với 
mọi n>=n0.
Từ đó suy điều cần CM.
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
35
Xác định độ phức tạp
 Quy tắc cộng
Nếu P1 có T1 (n) = O( f(n) và P2 có T2(n)= 
O(g(n)), khi đó: T1(n) +T2(n) = O(f(n) +g(n)).
CM: Vì T1(n)= O(f(n)) nên  các hàng số c1 và n1 sao 
cho T(n) = n1.
Vì T2(n) =O(g(n)) nên  các hàng số c2 và n2 sao 
cho T(n) = n2
Chọn c= max (c1,c2) và n0 = max(n1,n2) ta có n: 
n>= n0:
T(n) = T1(n) + T2(n) <= c1f(n) + c2g(n) 
<= cf(n) +cg(n) = c(f(n)+g(n)).
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
36
Xác định độ phức tạp
 Quy tắc nhân
Nếu P có T(n)= O(f(n)). Khi đó nếu thực hiện 
k(n) lần P với k(n)=O(g(n)) thì độ phức tạp là 
O(f(n) g(n)).
CM: Thời gian thực hiện k(n) lần đoạn chương trình P sẽ là 
k(n) T(n), theo định nghĩa:
 ck>=0 và nk >0 để k(n) = nk
 cT>=0 và nT >0 để T(n) = nT
Vậy với mọi n >= max(nT,nk) ta có k(n)T(n) <= 
ckcT(f(n)g(n)).
10
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
37
4. Bài toán và thuật toán
e) Áp dụng đánh giá chương trình
 Câu lệnh đơn thực hiện một thao tác
QT hằng số
 Câu lệnh hợp thành là dãy các câu lệnh
QT tổng
 Câu lệnh rẽ nhánh dạng If ..then..else. 
QT Max
 Các câu lệnh lặp QT Nhân
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
38
Ví dụ 1
Analysing an Algorithm
• Simple statement sequence
 s1; s2; . ; sk
• O(1) as long as k is constant
• Simple loops
 for(i=0;i<n;i++) { s; }
 where s is O(1)
• Time complexity is n O(1) or O(n)
• Nested loops
 for(i=0;i<n;i++)
for(j=0;j<n;j++) { s; }
• Complexity is n O(n) or O(n2)
This part is
O(n)
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
39
Analysing an Algorithm
• Loop index doesn’t vary linearly
 h = 1;
while ( h <= n ) {
s;
h = 2 * h;
 }
• h takes values 1, 2, 4,  until it exceeds n
• There are 1 + log2n iterations
• Complexity O(log n)
Ví dụ 2
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
40
Ví dụ 3
Analysing an Algorithm
• Loop index depends on outer loop index
 for(j=0;j<n;j++)
 for(k=0;k<j;k++){
s;
}
• Inner loop executed
• 1, 2, 3, ., n times
 Complexity O(n2)
n
 i =
i=1
n(n+1)
2
Distinguish this case -
where the iteration count 
increases (decreases) by a 
constant  O(nk)
from the previous one -
where it changes by a factor 
 O(log n) 
11
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
41
Một số dạng hàm
 Đa thức bậc k: P(n), O (nk).
 logaf(n), O(log f(n)). 
 Hằng số, O(1)
 Hàm mũ O(2n.)
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
42
4. Bài toán và thuật toán
Lgn n nlgn n2 n3 2n
0 1 0 1 1 2
1 2 2 4 8 4
2 4 8 16 64 16
3 8 24 64 512 256
4 16 64 256 4096 65536
5 32 160 1024 32768 214748364
8
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
43
Sự Phân Lớp Theo Độ Phức Tạp Của Thuật Toán
 Sử dụng ký hiệu BigO 
 Hằng số : O(c)
 logN : O(logN)
 N : O(N)
 NlogN : O(NlogN)
 N2 : O(N2)
 N3 : O(N3)
 2N : O(2N)
 N! :O(N!)
Độ phức tạp tăng dần
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
44
12
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
45
1.2. Quan hệ giữa giải thuật và cấu trúc DL
 Niklaus Wirth:
CTDL + Thuật toán = Chương trình
Data structures + Algorithms =Program 
 Cần nghiên cứu về thuật toán và CTDL!
 Cấu trúc dữ liệu cụ thể: chọn giải thuật
 Giải thuật cụ thể: chọn cấu trúc dữ liệu
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
46
1.3. Vị trí CTDL trong tin học
 Thiết kế chương trình
 Đặc tả vấn đề
 Thiết kế cấu trúc dữ liệu và giải thuật
 Cài đặt (C++, Java)
 Thử nghiệm và sửa lỗi
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
47
1.4. Tìm hiểu tổ chức một số CTDL cơ bản
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
48