Mảng là một cấu trúc dữ liệu cơ bản, thường dùng và được các ngôn ngữ lập trình bậc cao hỗ trợ. Mảng là một dãy cố định các ô nhớ chứa các phần tử cùng kiểu. Mỗi ô nhớ của mảng được xác định bởi chỉ số. Mô hình danh sách có những tmh chất gần giống với cấu trúc dữ liệu kiểu mảng nên ta có thể dùng mảng để biểu diễn mô hình danh sách, trong đó các phần tử của danh sách được lưu vào các ô nhớ liên tục của mảng.
Điểm khác biệt giữa cấu trúc mảng và mô hình danh sách là số phần tử của mảngxố định trong khi số phần tử của danh sách thay đổi theo các thao tác thêm và xoá.
1.2.1. Tổ chức dữ liệu
Giả sử có danh sách L = (a,, a„) trong đó mỗi phần tử có kiểu Elemenữype.
Khi đó tổ chức dữ liệu kiểu mảng để lưu danh sách L gồm hai thành phần:
+ Thành phần element là một mảng lưu các phần tử của danh sách.
+ Thành phần count là vị trí của ô nhớ lưu phần tử cuối cùng của danh sách và cũng là số phần tử hiện tại của danh sách.
Để đơn giản ta quy định các phần tử của mảng có chỉ số từ 1 đến maxlength, các phần tử của danh sách lưu vào mảng từ vị trí đầu tiên đến vị trí count. Khi đó các vị trí của mảng từ vị trí count + 1 đến maxlength chưa sử dụng, những phần tử này sẽ được sử dụng khi thưc hiên các thao tác thêm vào danh sách.
count niaxlength
Các phần tử của danh sách các ô nhớ trống
Hình 2.1. T ổ chức danh sách bằng màng
Khai báo một danh sách trong Pascal có dạng:
C o n s t M a x L e n g t h = . . . ; { S ố p h ầ n t ử t ố i đ a c ủ a d a n h s á c h } T y p e
E l e m e n t T y p e = . . . ; { Đ ị n h n g h ĩ a k ị ể u p h ầ n t ử c ủ a d a n h s á c h } L i s t A r r = R e c o r d
e l e m e n t : A r r a y [ 1 . . M a x L e n g t h ] O f E l e m e n t T y p e ; c o u n t : 0 . . M a x L e n g t h ;
E n d ;
V a r L : L i s t A r r ; { K h a i b á o b i ế n d a n h s á c h }
Ví dụ. Khai báo danh bạ điện thoại gồm họ tên, địa chỉ, số điện thoại.
C o n s t M a x L e n g t h = 1 0 0 ; T y p e
DIENTHOAI = R e c o r d
H o T e n : s t r i n g [ 3 0 ] ; D ỉ a C h ỉ : s t r i n g [ 3 0 ] ;
S o D i e n T h o a i : s t r i n g [ 1 0 ] ; E n d ;
DANHBA = R e c o r d
e l e m e n t : A r r a y [ 1 . . M a x L e n g t h ] O f DIENTHOAI;
C o u n t : 0 . . M a x L e n g t h ; E n d ;
________V a r d b : DANHBA;____________________________________________________________________
1.2.2. Các thao tác trên danh sách Khỏi tạo danh sách
Vì số phần tử của danh sách được lưu vào thành phần count nên để khởi tạo danh sích rỗng ta chỉ cần thực hiện phép gán count := 0.
P r o c e d u r e I n i t ( v a r L : L i s t A r r ) ; B e g i n
L . c o u n t : = 0 ; E n d ;
Kiểm tra danh sách rỗng
P a n c t i o n E m p t y (L : L i s t A r r ) : B o o l e a n ; B e g i n
E m p t y : = ( L . c o u n t = 0 ) ; E n d ;
22
Kiểm tra danh sách đầy
Khi biểu diễn danh sách bằng mảng sẽ phải khống chế số lượng tối đa các phần tử của danh sách. Do đó, có thể đến một lúc nào đó không đủ ô nhớ để thêm các phần tử vào danh sách. Trường hợp này gọi là danh sách đầy. Như vậy, danh sách đầy khi số phần tử của danh sách bằng kích thước của mảng.
F u n c t i o n F u l l (L B e g i n
F u l l E n d ;
L i s t A r r ) ¡ B o o l e a n ;
( L . c o u n t = M a x L e n g t h ) ;
Thêm một phần tử vào danh sách
Cho danh sách L, cần thêm vào trước phần tử thứ k trong danh sách một phần tử X.
1 k count maxlength
*
*
Ấr+l count
Hình 2.2. Thêm m ột phẩn tử vào danh sách
Thuật toán
+ Di chuyển các phần tử từ vị trí thứ k đến cuối danh sách ra sau một vị trí.
+ Đưa phần tử cần thêm X vào vị trí k.
+ Tăng thành phần count lên 1.
Thủ tục thêm phần tử X vào danh sách L tại vị trí k:
P r o c e d u r e I n s e r t ( v a r L : L i s t A r r ; X : E l e m e n t T y p e ; k : 1 . . m a x l e n g t h ) ; v a r i : 1 . . m a x l e n g t h ;
B e g i n
I f ( k < = L . c o u n t + 1 ) a n d ( k > 0 ) a n d n o t F u l l (L) t h e n B e g i n
F o r i : = L . c o u n t DownTo k Do
L . e l e m e n t [ i + 1 ] : = L . e l e m e n t [ 1 ] ; L . e l e m e n t [ k ] : = x ;
L . c o u n t : = L . c o u n t + 1 ; E n d ;
E n d ;
Loại bỏ một phần tử khỏi danh sách
Giả sử cần xoá phần tử thứ k trong danh sách L.
Thuật toán
+ Dồn các phần tửtừ yị trí k+1 đến cuối danh sách về trước một vị trí.
+ Giảm số phần tử của danh sách đi 1.
1 k k+ l count maxlength
count-1 maxlength
Hình 2.3. }ủ)á phần tử thứ k trong danh sách
Thủ tục xoá phần tử tại vị trí k trong danh sách L:
P r o c e d u r e D e l e t e ( v a r L : L i s t A r r ; k : 1 . . m a x l e n g t h ) ; v a r i : 1 . . m a x l e n g t h ;
B e g i n
I f (k < = L . c o u n t ) a n d ( k > 0 ) a n d n o t E m p t y (L) t h e n B e g i n
F o r i : = k To L . c o u n t - 1 Do
L . e l e m e n t [ i ] : = L . e l e m e n t [ i + 1 ] ; L . c o u n t : = L . c o u n t - 1 ;
E n d ; E n d ;
Với danh sách có n phần tử, dễ thấy độ phức tạp thuật toán thêm một phần tử và thuật toỏn xoỏ một phần tử cú độ phức tạp là 0(ô).
Ghép hai danh sách
Cho hai danh sách L| và L2. Ghép hai danh sách này thành danh sách L.
Thủ tục ghép hai danh sách Lj, Lj theo thứ tự vào danh sách L:
P r o c e d u r e C o n c a t ( L l , L2 : L i s t A r r ; V a r L : L i s t A r r a y ) ; v a r i : 1 . . m a x l e n g t h ;
B e g i n
F o r i : = 1 To L l . c o u n t Do
L . e l e m e n t [ i ] : = L l . e l e m e n t [ i ] ; F o r ị : = l To L 2 . c o u n t Do
24
L . e l e m e n t [ i + L l . c o u n t ] : = L 2 . e l e m e n t [ i ] ; L . c o u n t : = L l . c o u n t + L 2 . c o u n t ;
End;
Sắp xếp danh sách
Cho danh sách L, sắp xếp danh sách theo thứ tự tăng của trường khoá Key (Key là một trường trong kiểu dữ liệu phần tử của danh sách).
Có nhiều thuật toán sắp xếp danh sách tổ chức bằng mảng. Trong phần này trình bày thuật toán sắp xếp bằng chọn trực tiếp.
Thuật toán
Duyệt lần lượt từng phần tử của danh sách, với phần tử thứ i thực hiện:
+ Tìm phần tử ở vị trí k có khoá nhỏ nhất trong danh sách con L[i..count]
+ Đổi giá trị phẩn tử thứ k với phần tử thứ i.
P r o c e d u r e S o r t ( V a r L : L i s t A r r ) ;
v a r i , j , k : 1 . . m a x l e n g t h ; t g : E l e m e n t T y p e ; B e g i n
F o r i ; = l To L . c o u n t - 1 Do B e g i n
k : = i ;
F o r j : = i + 1 To L . c o u n t Do
I f L . e l e m e n t [ k ] . K e y > L . e l e m e n t [ j ] . K e y t h e n k : = j ;
t g : = L . e l e m e n t [ i ] ;
L . e l e m e n t [ i ] : = L . e l e m e n t [ k ] ; L . e l e m e n t [ k ] : = t g ;
E n d ; E n d ;
Tim kiếm trong danh sách
Cho danh sách L, tìm trong danh sách phần tử có khoậ của trường Key là j:. Nếu tìm thấy thì cho biết vị trí của phần tử đầu tiên tìm được.
Thuật toán tỉm kiếm tuần tự
Duyệt lần lượt từng phần tử của danh sách, với mỗi phần tử thực hiện;
+ Nếu phần tử thứ i có khoá trùng với X thì phần tử thứ i là phần tử cần tìm, dừng thuật toán và kết quả tìm thấy.
+ Nếu đã duyệt hết danh sách thì kết luận không tìm thẩy.
Thủ tục Locate tìm trong danh sách L một phần tử có khoá là X. Nếu tìm thấy, kết quả được trả về qua tham biến found kiểu boolean và vị trí của phần tử tìm được đầu tiên qua tham biến id.
P r o c e d u r e L o c a t e ( L : L i s t A r r ; x : K e y T y p e ;
v a r f o u n d : B o o l e a n ; v a r i d : 0 . . M a x L e n g t h ) ; B e g i n
i d : = l ; F o u n d : = F a l s e ;
W h i l e ( i d < = L . c o u n t ) a n d n o t f o u n d Do b e g i n
I f L . p l e m e n t [ i d ] . K e y = x t h e n F o u n d : = T r u e
e l s e
i d : = i d + l ; e n d ;
E nd ;
Đụ phức tạp thuật toỏn tỡm kiếm tuần tự là 0(ô) với n là số phần tử của danh sỏch.
Để giảm độ phức tạp thuật toán tìm kiếm ta có thể dùng thuật toán tìm kiếm nhị phân. Yêu cầu để thực hiện được thuật toán tìm kiếm nhị phân là danh sách phải được sắp trên trường khoá cần tìm.
Giả sử danh sách L đã sắp theo thứ tự tăng của trường Key.
Thuật toán tìm kiếm nhị phân
Lặp lại trong khi danh sách còn ít nhất một phần tử, mỗi lần lặp thực hiện:
- So sánh khoá cần tìm với khoá của phần tử ỏ vị trí giữa của danh sách:
+ Nếu khoá của phần tử giữa lớn hơn khoá cẩn tìm thì tìm trong nửa đầu của danh sách.
+ Nếu khoá của phần tử giữa nhỏ hơn khoá cần tìm thì tìm trong nửa sau của danh sách.
+ Nếu khoá của phần tử giữa bằng khoá cẩn tìm thì thuật toán kết thúc và kết quả là tìm thấy.
Nếu danh sách không có phần tử nào thì kết quả là không tìm thấy.
P r o c e d u r e S e e k ( L : L i s t A r r ; x : K e y T y p e ; v a r f o u n d : B o o l e a n ; v a r i d : I n t e g e r ) ;
v a r l e f t , r i g h t : 1 . . M a x L e n g t h ; B e g i n
l e f t : = 1 ;
r i g h t : = L . c o u n t ;
26 4.C TD L...PTPM ÉM B
f o u n d : = f a l s e , •
W h i l e ( l e f t < = r i g h t ) a n d ( n o t f o u n d ) d o B e g i n
i d : = ( l e f t + r i g h t ) d i v 2 ;
i f L . e l e m e n t [ i d ] . K e y > X t h e n r i g h t : = i d - l ; i f L . e l e m e n t [ i d ] . K e y < X t h e n l e f t : = i d + l ; i f L . e l e m e n t [ i d ] . K e y = X t h e n f o u n d : = t r u e ; E nd;
E n d ;
Vì sau mỗi lần so sánh, số phần tử trong danh sách cắn tìm giảm đi một nửa nên độ phức tạp thuật toán tìm kiếm nhị phân được đánh giá trong trường hợp xấu nhất là 0 (log2/ỉ).
Nhận xét về cách biểu diễn danh sách bằng mảng
Với cách tổ chức dữ liệu cho mô hình danh sách bằng mảng như trên ta có một số nhận xét về ưu, nhược điểm của cách tổ chức dữ liệu này như sau;
Tổ chức danh sách bằng mảng thuận lợi khi truy xuất trực tiếp các phần tử của danh sách theo vị trí. Điều này thuận lợi cho một số thuật toán như tìm kiếm nhị phân.
Khi dùng mảng phải cố định kích thước, trong khi đó các thao tác trên danh sách luôn làm cho số phần tử của danh sách thay đổi. Điều này dẫn đến hai xu hướng, nếu khai báo mảng với kích thước lớn thì gây lãng phí vì nhiều ô nhớ không sử dụng hoặc khai báo kích thước nhỏ để ít lãng phí thì danh sách sẽ nhanh chóng đầy khi thêm.
Các thao tác thêm, xoá, cài đặt trên danh sách tổ chức bằng mảng có độ phức tạp là 0(ô) nờn khụng phự hợp với cỏc danh sỏch thường xuyờn sử đụng cỏc thao tác này.