Bài giảng Cơ sở dữ liệu - Cấu trúc dữ liệu - Trần Ngọc Bảo

Đại Học Sư Phạm Tp. Hồ Chí Minh
Khoa Toán – Tin Học
Ô Ố ỆN THI T T NGHI P
ấC u trúc dữ liệu
Trần Ngọc Bảo
Email: tnbao.dhsp@gmail.com
Đại Học Sư Phạm Tp. Hồ Chí Minh
Khoa Toán – Tin Học
CẤU TRÚC DỮ LIỆU
• Cấu trúc dữ liệu mảng
• Danh sách liên kết
• Cấu trúc dữ liệu cây
Đại Học Sư Phạm Tp. Hồ Chí Minh
Khoa Toán – Tin Học
CẤU TRÚC DỮ LIỆU
• Cấu trúc dữ liệu mảng
• Danh sách liên kết
• Cấu trúc dữ liệu cây
Cấu trúc mảng một chiều
• Các giải thuật tìm kiếm
H
I
Ệ
P
H
I
Ệ
P
U U
– Tìm kiếm tuần tự (Sequence Search)
– Tìm kiếm nhị phân (Binary Search)
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U
• Các giải thuật sắp xếp
– Sắp xếp đổi chỗ trực tiếp
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D
– Sắp xếp chọn trực tiếp
– Sắp xếp chèn trực tiếp
ắ
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T – S p xếp nổi bọt
– Sắp xếp nổi bọt cải tiến
Shell sort
B
À
B
À
– 
– Heap sort
– Quick sort
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (4)4
– Merge sort
Cấu trúc mảng một chiều
Yê ầ
H
I
Ệ
P
H
I
Ệ
P
U U
• u c u
–Trình bày ý tưởng giải thuật
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U
–Cho ví dụ minh họa
–Biểu diễn giải thuật
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D
• Biểu diễn giải thuật bằng mã giả
• Biểu diễn giải thuật bằng sơ đồ khối
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T
–Cài đặt bằng ngôn ngữ C/C++
Cho biết kết quả thực hiện chạy
B
À
B
À
– 
từng bước giải thuật
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (5)5
Giải thuật tìm kiếm tuần tự
Bài t á
H
I
Ệ
P
H
I
Ệ
P
U U
• o n
–Cho mảng a có n số nguyên (n ≤ 
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U
100)
–Yêu cầu: cho biết số nguyên x có 
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D
tồn tại trong mảng a không ? 
•Nếu có cho biết vị trí đầu tiên x xuất
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T
hiện trong mảng
•Ngược lại thông báo x không tồn tại 
B
À
B
À trong mảng.
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (6)6
Giải thuật tìm kiếm tuần tự
Ví d
H
I
Ệ
P
H
I
Ệ
P
U U
• ụ
– Cho mảng a có 6 phần tử (n = 6) như 
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U sau:
1 5 4 2 3 7
Yê ầ
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D – u c u:
• Tìm x = 3 ?
Tìm x 10 ?
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T • = 
– Kết quả:
• X = 3 xuất hiện ở vị trí thứ 5 trong mảng
B
À
B
À
• X = 10 không tồn tại trong mảng
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (7)7
Giải thuật tìm kiếm tuần tự
Ý tưở iải th ật
H
I
Ệ
P
H
I
Ệ
P
U U
• ng g u
– Cho mảng a có 6 phần tử (n = 6) như 
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U sau:
1 5 4 2 3 7
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T
B
À
B
À
3X = 
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (8)8
X = 3 xuất hiện ở vị trí thứ 5 trong mảng
Giải thuật tìm kiếm tuần tự
Ý tưở iải th ật
H
I
Ệ
P
H
I
Ệ
P
U U
• ng g u
– Cho mảng a có 6 phần tử (n = 6) như 
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U sau:
1 5 4 2 3 7
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T
B
À
B
À
10X = 
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (9)9
X = 10 không tồn tại trong mảng
Giải thuật tìm kiếm tuần tự
Ví dụ
H
I
Ệ
P
H
I
Ệ
P
U U
• 
– Cho mảng a có 6 phần tử (n = 6) như sau:
1 5 4 2 3 7
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U
– Yêu cầu:
• Tìm x = 3 ?
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D – Kết quả:
Lần lặp i a[i] = x ? Kết quả
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T
1 0 a[0]=1 ≠ x=3 i=i+1 =1
2 1 a[1]=5 ≠ x=3 i=i+1 =2
3 2 a[2]=4 ≠ x=3 i=i+1 =3
B
À
B
À
4 3 a[3]=2 ≠ x=3 i=i+1 =4
5 4 a[0]=3 = x=3 Kết thúc gt
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (10)
X = 3 xuất hiện ở vị trí thứ 5 trong mảng
Giải thuật tìm kiếm tuần tự
H
I
Ệ
P
H
I
Ệ
P
U U
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T
B
À
B
À
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (11)
Giải thuật tìm kiếm nhị phân
Bài t á
H
I
Ệ
P
H
I
Ệ
P
U U
• o n
–Cho mảng a có n số nguyên (n ≤ 
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U
100)
–Yêu cầu: cho biết số nguyên x có 
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D
tồn tại trong mảng a không ? 
•Nếu có cho biết vị trí đầu tiên x xuất
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T
hiện trong mảng
•Ngược lại thông báo x không tồn tại 
B
À
B
À trong mảng.
–Điều kiện:
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (12)12
Mảng a đã được sắp thứ tự tăng
Giải thuật tìm kiếm tuần tự
Ví d
H
I
Ệ
P
H
I
Ệ
P
U U
• ụ
– Cho mảng a có 6 phần tử (n = 6) như 
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U sau:
1 2 3 4 5 7
Yê ầ
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D – u c u:
• Tìm x = 3 ?
Kết ả
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T – qu :
• X = 3 xuất hiện ở vị trí thứ 5 trong mảng
B
À
B
À
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (13)13
Giải thuật tìm kiếm nhị phân
Ví dụ
H
I
Ệ
P
H
I
Ệ
P
U U
• 
– Cho mảng a có 6 phần tử (n = 6) như sau:
1 2 3 4 5 7
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U
– Yêu cầu:
• Tìm x = 4 ?
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D – Kết quả:
Lần lặp l r m=[(l+r)/2] a[m] = x ? Kết quả
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T 1 0 5 [(0+5)/2]=2 a[2]=3 < x=4 l=m+1 =3
2 3 5 [(3+5)/2]=4 a[4]=5 > x=4 r=m-1 =3
3 3 3 [(3+3)/2]=3 a[3]=4 = x=4 Kết thúc gt
B
À
B
À
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (14)
X = 4 xuất hiện ở vị trí thứ 4 trong mảng
Giải thuật tìm kiếm nhị phân
H
I
Ệ
P
H
I
Ệ
P
U U
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T
B
À
B
À
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (15)
Cấu trúc mảng một chiều
• Các giải thuật tìm kiếm
H
I
Ệ
P
H
I
Ệ
P
U U
– Tìm kiếm tuần tự (Sequence Search)
– Tìm kiếm nhị phân (Binary Search)
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U
• Các giải thuật sắp xếp
– Sắp xếp đổi chỗ trực tiếp
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D
– Sắp xếp chọn trực tiếp
– Sắp xếp chèn trực tiếp
ắ
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T – S p xếp nổi bọt
– Sắp xếp nổi bọt cải tiến
Shell sort
B
À
B
À
– 
– Heap sort
– Quick sort
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (16)16
– Merge sort
Các giải thuật sắp xếp trên mảng 1 chiều
Yê ầ
H
I
Ệ
P
H
I
Ệ
P
U U
• u c u
–Trình bày ý tưởng giải thuật
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U
–Cho ví dụ minh họa
–Biểu diễn giải thuật
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D
• Biểu diễn giải thuật bằng mã giả
• Biểu diễn giải thuật bằng sơ đồ khối
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T
–Cài đặt bằng ngôn ngữ C/C++
Cho biết kết quả thực hiện chạy
B
À
B
À
– 
từng bước giải thuật
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (17)17
Demo
Struct và sắp xếp mảng struct
• Struct
H
I
Ệ
P
H
I
Ệ
P
U U
– Cho thông tin học sinh, sinh viên,là 1 
struct có nhiều thông tin
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U
• Sắp xếp danh sách (mảng struct)
– Chọn 1 trong các giải thuật sắp xếp trên mảng
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D
1 chiều để sắp xếp các phần tử trong danh
sách theo một hoặc nhiều tiêu chí (điều kiện)
• Sắp xếp danh sách sinh viên theo họ tên
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T
• Sắp xếp danh sách sinh viên giảm dần theo điểm tốt
nghiệp
• Sắp xếp danh sách sinh viên theo họ tên, điểm thi tốt
B
À
B
À
nghiệp
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (18)
Ví dụ
Đại Học Sư Phạm Tp. Hồ Chí Minh
Khoa Toán – Tin Học
CẤU TRÚC DỮ LIỆU
• Cấu trúc dữ liệu mảng
• Danh sách liên kết
• Cấu trúc dữ liệu cây
Danh sách liên kết
• Cấu trúc tự trỏ
H
I
Ệ
P
H
I
Ệ
P
U U
– Thành phần dữ liệu: data
– Thành phần con trỏ: Next, Previous
Cá l i d h á h liê kế
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U • c oạ an s c n t
– Danh sách liên kết đơn
– Danh sách liên kết đôi
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D – Danh sách vòng
– Danh sách đa liên kết
– Stack/Queue
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T
• Các thao tác trên sách liên kết
– Thêm phần tử
Xóa phần tử
B
À
B
À
– 
– Tìm phần tử trong danh sách
– Sắp xếp các phần tử trong danh sách
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (20)
Demo
Danh sách liên kết
H
I
Ệ
P
H
I
Ệ
P
U U
Cho danh sách liên kết đơn với các
Ví dụ 1
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U
phần tử trong danh sách là số nguyên
Vẽ sơ đồ khối và cài đặt giải thuật sắp
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D
xếp các phần tử trong danh sách theo
h h đổi hỗ iế
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T p ương p áp c trực t p.
Lưu ý: định nghĩa cấu trúc danh sách
B
À
B
À liên kết đôi trước khi thực hiện cài đặt
các giải thuật
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (21)
Danh sách liên kết
H
I
Ệ
P
H
I
Ệ
P
U U Cho mảng a có n số nguyên
Ví dụ 2.1
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U
Vẽ sơ đồ khối và cài đặt giải thuật chèn
1 hầ ử à ả đã đ ắ ế hứ
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D p n t v o m ng ược s p x p t
tự tăng (kết quả mảng cũng được sắp
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T tăng).
B
À
B
À
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (22)
Danh sách liên kết
H
I
Ệ
P
H
I
Ệ
P
U U Cho danh sách liên kết đơn với các
Ví dụ 2.2
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U
phần tử trong danh sách là số nguyên
Vẽ đồ khối à ài đặ iải h ậ hè
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D sơ v c t g t u t c n
1 phần tử vào danh sách đã được sắp xếp
ế
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T thứ tự tăng (k t quả danh sách cũng được
sắp tăng).
B
À
B
À
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (23)
Danh sách liên kết
H
I
Ệ
P
H
I
Ệ
P
U U
Cho danh sách liên kết đôi với các
Ví dụ 3
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U
phần tử trong danh sách là số nguyên
Vẽ sơ đồ khối và cài đặt giải thuật sắp
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D
xếp các phần tử trong danh sách theo
h h h iế
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T p ương p áp c èn trực t p.
Lưu ý: định nghĩa cấu trúc danh sách
B
À
B
À liên kết đôi trước khi thực hiện cài đặt
các giải thuật
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (24)
Đại Học Sư Phạm Tp. Hồ Chí Minh
Khoa Toán – Tin Học
CẤU TRÚC DỮ LIỆU
• Cấu trúc dữ liệu mảng
• Danh sách liên kết
• Cấu trúc dữ liệu cây
Cây nhị phân
• Cấu trúc cây
H
I
Ệ
P
H
I
Ệ
P
U U
– Thành phần dữ liệu: data
– Thành phần con trỏ: Left, Right
Cá l i â hị hâ
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U • c oạ c y n p n
– Cây nhị phân
– Cây nhị phân cân bằng
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D – Cây nhị phân tìm kiếm
– Cây nhị phân tìm kiếm cân bằng
• Các thao tác trên cây nhị phân tìm kiếm
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T
– Tạo cây
– Duyệt cây theo thứ tự: NLR, LNR, LRN 
Thêm phần tử vào cây
B
À
B
À
– 
– Xóa phần tử: nút lá, nút có 1 cây con, nút có 2 cây con.
– Tìm phần tử trong cây
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (26)
Demo
HI
Ệ
P
H
I
Ệ
P
U U
T
Ố
T
N
G
T
Ố
T
N
G
D
Ữ
L
I
Ệ
U
D
Ữ
L
I
Ệ
U
Ô
N
T
H
I
Ô
N
T
H
I
T
R
Ú
C
D
T
R
Ú
C
D
I
G
I
Ả
N
G
I
G
I
Ả
N
G
C
Ấ
U
T
C
Ấ
U
T
B
À
B
À
TRẦN NGỌC BẢO ” KHOA TOÁN -TIN HỌC ” ĐẠI HỌC SƯ PHẠM TP.HCM ” (27)27