Bài giảng Công nghệ phần mềm - Chương 2: Mảng và danh sách - Ngô Công Thắng

CHƯƠNG 2
MẢNG VÀ DANH SÁCH
Ngô Công Thắng
Bộ môn Công nghệ phần mềm
Khoa Công nghệ thông tin
Website: dse.vnua.edu.vn/ncthang
Email: ncthang@vnua.edu.vn
1. Mảng
l Mảng là một tập hợp có thứ tự gồm một số cố
định các phần tử cùng kiểu.
l Một phần tử mảng được chỉ ra bởi chỉ số, thể
hiện thứ tự của phần tử trong mảng. Véc tơ là
mảng 1 chiều có 1 chỉ số (i). Ma trận là mảng
2 chiều có 2 chỉ số (i, j). Không gian 3 chiều là
mảng 3 chiều có 3 chỉ số. Không gian n chiều
là mảng n chiều có n chỉ số.
1. Mảng
l Để truy nhập trực tiếp các phần tử, mảng chỉ 
dùng được cấu trúc lưu trữ kế tiếp.
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 cho phép bổ sung hoặc loại bỏ một 
phần tử 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
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.10
3. Cấu trúc ngăn xếp (Stack)
3.1. Định nghĩa
l Stack 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 Stack có thể rỗng hoặc bao gồm một số phần 
tử.
3.2. Lưu trữ Stack bằng mảng
l Có thể lưu trữ Stack bởi một vector S gồm n ô 
nhớ kế tiếp nhau có chỉ số từ 1 đến n. Nếu T là 
chỉ số phần tử đỉnh của stack thì T sẽ có giá trị 
biến đổi khi stack hoạt động.
l Khi bổ sung 1 phần tử T sẽ tăng lên 1. Khi 1 
phần tử bị loại khỏi stack thì T giảm đi 1.
l Ta quy ước khi stack 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(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.14
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(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];
3) Thay đổi chỉ số đỉnh
T := T-1
4) Đưa phần tử bị loại ra
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.16
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.17
Hàm kiểm tra ngăn xếp rỗng
Function Empty(S,T)
If T = 0 then Empty:=TRUE
Else Empty:=FALSE;
Return
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chươn