Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 2: Mảng và danh sách - Ngô Công Thắng

 CHƯƠNG 2
 MẢNG VÀ DANH SÁCH
1. Mảng
2. Danh sách
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật -Chương 02 3.1
 1. Mảng
 l Mảng làmộttậphợpcóthứ tự gồmmộtsốcố
 địnhcácphầntửcùngkiểu.
 l Mộtphầntửmảng đượcchỉ rabởichỉ số, thể
 hiệnthứ tự củaphầntửtrongmảng.
 l Các phần tử của mảng có thể được tổ chức 
 thành mảng 1 chiều, 2 chiều, 3 chiều
 Ví dụ: Véc tơ làmảng1 chiềucó1 chỉ số (i). 
 Ma trậnlàmảng2 chiềucó2 chỉ số (i, j). Không
 gian3 chiềulàmảng3 chiềucó3 chỉ số. Không
 giann chiềulàmảngn chiềucón chỉ số.
 1. Mảng
l Mảng chỉ dùng được cấu trúc lưu trữ kế tiếp, 
 để cho phép truy nhập trực tiếp các phần tử.
l Dùng vec tơ lưu trữ V có n ô nhớ liên tiếp với 
 chỉ số từ 1 đến n để lưu trữ các phần tử dữ 
 liệu của mảng.
l Với mảng 1 chiều, phần tử ai được lưu trữ ở 
 ô nhớ V[i]
l Với mảng 2 chiều, các phần tử được lưu trữ 
 lần lượt, hết hàng 1 đến hàng 2 Phần tử aij
 được lưu trữ ở ô nhớ V[k], k = (i-1)*n + j
 1. Mảng
l Mảng 2 chiều có m = 2 hàng, n = 3 cột. Tính 
 chỉ số k truy nhập vào ô nhớ chứa phần tử aij.
4 5 9
7 10 1
4 5 9 7 10 1 => k = (i-1)*n + j
l Có các phép tạo lập mảng, tìm kiếm 1 phần 
 tử từ mảng, truy nhập một phần tử mảng.
l Không có phép bổ sung hoặc loại bỏ một 
 phần tử mảng.
 2. Danh sách
2.1. Khái niệm
 l Danh sách là một tập hợp có thứ tự gồm một 
 số biến động các phần tử cùng kiểu. 
 l Phép loại bỏ, bổ sung 1 phần tử là phép 
 thường xuyên tác động lên danh sách.
 l Ví dụ: Tập hợp người đến khám bệnh cho ta 
 một danh sách. Người đến xếp hàng khám bổ 
 sung ở phía sau, người được khám sẽ ra khỏi 
 hàng ( loại bỏ ) ở phía trước.
 2.1. Khái niệm
l Danh sách tuyến tính: Một danh sách mà quan hệ lận 
 cận giữa các phần tử được xác định rõ ràng thì được gọi 
 là danh sách tuyến tính. Véc tơ là một danh sách tuyến 
 tính. 
l Danh sách tuyến tính hoặc rỗng (không có phần tử nào) 
 hoặc có dạng (a1, a2, ..., an) với ai , 1 £ i £ n là các 
 phần tử.
l Trong danh sách tuyến tính tồn tại phần tử đầu là a1, 
 phần tử cuối là an, phần tử thứ i là ai . Với ai bất kỳ 1 £ i 
 £ n thì ai+1 gọi là phần tử sau ai ; 2 £ i £ n thì phần tử 
 ai-1 là phần tử trước của ai .
 2.1. Khái niệm
l n là độ dài (kích thước) của danh sách, n có thể 
 thay đổi.
l Một phần tử trong danh sách thường là một bản 
 ghi (gồm một hoặc nhiều trường).
l Ví dụ 1: Danh mục điện thoại là một danh sách 
 tuyến tính, mỗi phần tử của nó là một thuê bao 
 gồm 3 trường: Họ tên chủ hộ, địa chỉ, số điện 
 thoại.
l Ví dụ 2: Tệp(File) là một danh sách có kích 
 thước lớn được lưu trữ ở bộ nhớ ngoài.
 2.2. Các phép toán trên danh sách
l Phép bổ sung: Có thể bổ sung phần tử vào 
 danh sách.
l Phép loại bỏ: có thể loại bỏ một phàn tử ra khỏi 
 danh sách.
l Phép ghép: có thể ghép hai hay nhiều danh 
 sách thành một danh sách.
l Phép tách: có thể tách một danh sách thành 
 nhiều danh sách.
l Phép cập nhật: cập nhật giá trị cho các phần tử 
 của danh sách.
 2.2. Các phép toán trên danh sách
l Phép sao chép: có thể sao chép một danh sách.
l Phép sắp xếp: Có thể sắp xếp các phần tử của 
 danh sách theo một thứ tự nhất định.
l Phép tìm kiếm: Tìm kiếm trong danh sách một 
 phần tử mà một trường nào đó có giá trị ấn định.
Ví dụ 1: Minh hoạ cho các phép toán trên danh 
sách được cài đặt trên mảng. Cho danh sách các 
số nguyên, thêm vào 1 số nguyên và loại bỏ một 
số nguyên.
 2.3. Lưu trữ kế tiếp cho danh sách 
 tuyến tính
l Dùng mảng một chiều làm cấu trúc lưu trữ danh 
 sách tuyến tính. Tức là dùng vector lưu trữ (Vi) 
 với 1£ i £ m để lưu trữ một danh sách tuyến tính 
 (a1,a2,...,an). Phần tử ai được chứa ở Vi .
 a1 a2... ai... an
 V1 V2 ... Vi ... Vn ... Vm
 2.3. Lưu trữ kế tiếp cho danh sách 
 tuyến tính
l Do số phần tử của danh sách tuyến tính luôn 
 biến động, tức là kích thước n luôn thay đổi, do 
 vậy m = max(n).
l Mặt khác, n không thể xác định chính xác mà chỉ 
 dự đoán. Bởi vậy, nếu max(n) lớn sẽ lãng phí bộ 
 nhớ cũng như lãng phí thời gian để thực hiện 
 các thao tác để dồn các phần tử xuống khi ta 
 thêm một phần tử vào danh sách tuyến tính.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật -Chương 03 3.11
 3. Cấu trúc ngăn xếp (Stack)
3.1. Định nghĩa
l Ngăn xếp là một kiểu danh sách tuyến tính đặc 
 biệt mà phép bổ sung và phép loại bỏ luôn luôn 
 thực hiện ở một đầu gọi là đỉnh (Top).
l Phép bổ sung và loại bỏ phần tử của ngăn xếp 
 được thực hiện theo nguyên tắc "Vào sau ra 
 trước" (Last in -First out, viết tắt là LIFO).
l Ngăn xếp có thể rỗng.
 3.2. Lưu trữ kế tiếp
l Dùng vector lưu trữ S có n ô nhớ kế tiếp nhau 
 với chỉ số từ 1 đến n để lưu trữ các phần tử dữ 
 liệu.
l Dùng biến T để lưu trữ chỉ số phần tử đỉnh của 
 ngăn xếp, T sẽ thay đổi khi ngăn xếp hoạt động. 
 Khi bổ sung 1 phần tử T sẽ tăng lên 1. Khi 1 
 phần tử bị loại khỏi ngăn xếp thì T giảm đi 1.
l Khi ngăn xếp rỗng T=0.
 3.3. Các phép toán trên ngăn xếp
l Bổ sung một phần tử vào stack
-Vào: phần tử x, ngăn xếp (S,T)
-Ra: không có
{Thủ tục này bổ sung phần tử x vào ngăn 
xếp được lưu trữ bởi véc tơ S có kích thước 
là n, có chỉ số đinh là T.}
Thủ tục bổ sung một phần tử vào stack
 Procedure push(Var S, T;x)
 1) {Kiểm tra ngăn xếp đã đầy chưa?}
 If T= n then Begin Write(‘Stack đã đầy‘)
 Return
 End;
 2) {Thay đổi chỉ số}
 T := T+1
 3){Bổ sung phần tử mới x}
 S[T] := x
Return
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật -Chương 03 3.15
 3.3. Các phép toán trên ngăn xếp
l Loại bỏ một phần tử ra khỏi stack
-Vào: Ngăn xếp (S, T)
-Ra: giá trị phần tử loại bỏ (đỉnh)
{Hàm này thực hiện việc loại bỏ phần tử ở 
đỉnh ngăn xếp (S,T) và trả về phần tử này.}
Hàm loại bỏ phần tử khỏi ngăn xếp
Function pop(Var S, T)
 1){Kiểm tra xem stack có rỗng?}
 If T= 0 then Begin 
 Write(‘Stack rỗng‘)
 Return;
 End
 2) Tg := S[T]; {Giữ lại phần tử đỉnh}
 3){Thay đổi chỉ số đỉnh}
 T := T-1
 4){Trả về phần tử bị loại}
 Pop := Tg;
Return
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật -Chương 02 2.17
 Hàm kiểm tra ngăn xếp rỗng
Function isEmpty(S,T)
 If T= 0 then Empty := TRUE
 ElseEmpty := FALSE;
Return
Function isFull(S,T)
 If T= nthen Full := TRUE
 ElseFull := FALSE;
Return
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật -Chương 02 2.18
 Hàm trả về phần tử đỉnh ngăn xếp
Function top(S,T)
 1){Kiểm tra xem stack có rỗng?}
 If T= 0 then Begin 
 Write(‘Stack rỗng‘)
 Return;
 End
 2){Trả về phần tử đỉnh}
 Top := S[T];
Return
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật -Chương 02 2.19
 Ví dụ về ứng dụng của ngăn xếp
l Viết giả mã có sử dụng ngăn xếp để đổi số 
 nguyên hệ 10 sang hệ 2.
l Giải thuật: Lấy số hệ 10 chianguyênliên tiếp 
 cho 2, kết quả là phần dư của phép chia lấy 
 theo thứ tự ngược lại. Ápdụng cơ chế vào sau 
 ra trước,mỗi lần chia ta lấy số dư của phép chia 
 đẩy vào stack (thủ tuc Push). Khi đã kết thúc 
 phép chia,kết quả lấy các số dư từ stack ra 
 (hàm loại bỏ phần tử khỏi stack,Pop).
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật -Chương 02 3.20
 Ví dụ về ứng dụng của ngăn xếp
-Vào: n
-Ra: số nhị phân
Procedure chuyen_doi(n);
 While n 0 do Begin
 R:=n mod 2
 Call Push(S,T,R);
 n= n div 2
 End;
 While SNULL do Begin
 R:=POP(S,T); {lay R tu dinh T cua Stack S }
 Write(R)
 End;
Return;
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật -Chương 02 3.21
 Bài tập
l Ứng dụng ngăn xếp chuyển biểu thức 
 trung tố hành hậu tố. Biết rằng biếu thức 
 trung tố có dấu ngoặc đầy đủ.
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật -Chương 02 3.22
 4. Cấu trúc hàng đợi (Queue)
4.1. Định nghĩa
l Hàng đợi (queue) là kiểu danh sách tuyến tính 
 mà phép bổ sung được thực hiện ở một đầu, gọi 
 là lối sau (rear) và phép loại bỏ thực hiện ở một 
 đầu khác, gọi là lối trước (front).
l Phép bổ sung và loại bỏ phần tử của hàng đợi 
 được thực hiện theo nguyên tắc vào trước ra 
 trước (First in -First out, viết tắt là FIFO).
l Hàng đợi có thể rỗng.
 4.2. Lưu trữ kế tiếp
l Dùng vector lưu trữ Q có n ô nhớ với chỉ 
 số từ 1 đến n để lưu trữ các phần tử dữ 
 liệu của hàng đợi.
l Dùng biến R chứa chỉ số của phần tử lối 
 sau và F cho lối trước. 
l Khi bổ sung 1 phần tử vào hàng đợi thì R 
 tăng lên 1, còn khi loại bỏ một phần tử 
 khỏi hàng đợi thì F tăng lên 1.
l Khi hàng đợi rỗng thì R=F=0.
 4.2. Lưu trữ hàng đợi bằng mảng
l Để sử dụng lại các ô nhớ chứa phần tử dữ liệu 
 đã loại bỏ, người ta sử dụng các ô nhớ của vec 
 tơ lưu trữ Q theo kiểu quay vòng, tức là tiếp 
 theo ô nhớ n là ô nhớ 1.
 4.3. Các phép toán trên Queue
a) Bổ sung một phần tử vào queue
l Vào: x, (Q, F, R)
l Ra: Không có
{Thủ tục này bổ sung phần tử x vào hàng 
đợi lưu trữ bởi vector Q có n ô nhớ theo 
kiểu vòng tròn, có biến chỉ số F, R}
 Procedure CQInsert(Var Q,F,R; x)
 1){Kiểm tra đầy}
 If (F=1)and(R=n) or (R+1=F)then Begin 
 Write( ‘Hàng đợi đã đầy‘);
 Return;
 End;
 2){Thay đổi chỉ số R}
 If F=R=0 Then F:=R:=1
 Else If R=n Then R:=1
 Else R:= R+1;
 3. {Bổ sung x vào}
 Q[R]:=x;
 Return { kết thúc}
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật -Chương 02 3.27
 4.3. Các phép toán trên Queue
b) Loại bỏ phần tử ra khỏi queue
- Vào: Hàng đợi (Q,F,R)
- Ra: Trả về phần tử loại bỏ
{Hàm này loại bỏ phần tử ở lối trước của 
hàng đợi (Q,F,R)vàtrả về phần tử loại bỏ}
 Thủ tục loại bỏ phần tử khỏi hàng đợi
 Function CQDelete(Var Q,F,R)
 1){Kiểm tra rỗng}
 If F=R=0 then Begin
 Write(‘Hàng đợi đã rỗng’);
 Return;
 End;
 2){Lưu lại phần tử loại bỏ}
 Tg:=Q[F]
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật -Chương 02 3.29
 Thủ tục loại bỏ phần tử khỏi hàng đợi
 Function CQDelete(Var Q,F,R)
 3){Thay đổi chỉ số F}
 If F=R thenF:=R:=0
 Else If F=n then F:=1
 Else F:=F+1;
 4) CQDelete := Tg;
Return
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật -Chương 02 3.30
 Kiểm tra hang đợi rỗng
Function CQIsEmpty(Q,F,R)
 If F=R=0 then
 CQIsEmpty:= TRUE
 Else
 CQIsEmpty:=FALSE;
Return
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật -Chương 02 3.31