C U TRÚC D LI UẤ Ữ Ệ
C U TRÚC D LI UẤ Ữ Ệ
(B C CAO Đ NG)Ậ Ẳ
Nguy n Thanh C mễ ẩ
Nguy n Thanh C mễ ẩ
BÀI GI NGẢ
BÀI GI NGẢ
KHOA KHOA H C MÁY TÍNH – B MÔN L P TRÌNHỌ Ộ Ậ
Ch ng2:ươ
Ch ng2:ươ
C U TRÚC D LI U DANH SÁCHẤ Ữ Ệ
C U TRÚC D LI U DANH SÁCHẤ Ữ Ệ
1. Danh sách
2. Danh sách đ cặ
3. Danh sách liên k tế
4. Ngăn x pế
5. Hàng đ iợ
N I DUNG TRÌNH BÀYỘ
1
1
1. Danh sách
a. Đ nh nghĩaị
b. Các phép toán trên danh sách
1. Danh sách
Danh sách là t p h p h u h n các ph n tậ ợ ữ ạ ầ ử
cùng ki u (Elementtype)ể : a1, a2, …, an (n>=1)
v i tính ch t: n u bi t đ c aớ ấ ế ế ượ i s bi t aẽ ế i+1
(0<= i <= n-1 )
Danh sách đ c s p x p tuy n tính theo v trí c a ượ ắ ế ế ị ủ
chúng (position)
S các ph n t (n) c a danh sách g i là đ dài ố ầ ử ủ ọ ộ
c a danh sách. N u n=0 thì ta có danh sách r ng.ủ ế ỗ
Ví d :ụ
a. Đ nh nghĩaị
1. Danh sách
Phép duy t danh sách: ệlà phép thăm t t c các ấ ả
ph n t c a danh sách th a mãn ầ ử ủ ỏ <đi u ki n>ề ệ
nào đó đ th c hi n công vi cể ự ệ ệ <x lý>ử
Ví d :ụ
Phép tìm ki m: ếlà thao tác tìm ph n t trong ầ ử
danh sách th a mãn đi u ki n nào đóỏ ề ệ
Ví d :ụ
b. Các phép toán trên danh sách