Bài giảng Chương 2: Các kiểu dữ liệu trừu tượng cơ bản môn Cấu trúc dữ liệu | Trường Đại học Xây Dựng Hà Nội

06/01/2026 CHƯƠNG 2
CÁC KIỂU DỮ LIỆU TRỪU TƯỢNG CƠ BẢN
1. Các kiểu dữ liệu trừu tượng cơ bản
Khái niệm: Kiểu dữ liệu trừu tượng (ADT) là
một mô hình dữ liệu trừu tượng kèm theo một tập
các phép toán được định nghĩa trên mô hình đó. Các ADT cơ bản:  Mảng (Array)  Danh sách (List)
 Danh sách liên kết (Linked List)  Ngăn xếp (Stack)  Hàng đợi (Queue) 2. ADT mảng (Array)
Mảng là một tập hợp hữu hạn các phần tử cùng
kiểu, được sắp xếp theo một thứ tự tuyến tính có độ dài nhất định. 1 06/01/2026
Các phép toán cơ bản: Rất ít. Gần nhưng phải
viết tay các hàm hoặc sử dụng các thư viện hỗ trợ.
Mảng phù hợp cho dữ liệu có thứ tự, đơn giản,
nhanh chóng, xác định số lượng phần tử. 3. ADT Danh sách (List)
Danh sách là một tập hợp hữu hạn các phần tử
cùng kiểu, được sắp xếp theo một thứ tự tuyến
tính (còn có thể goi là Dynamic Array). Có thể
không giới hạn số phần tử trong List. 2 06/01/2026 Các phép toán cơ bản:
 Create(): tạo danh sách rỗng
 IsEmpty(): kiểm tra rỗng
 Insert(x, p): chèn phần tử x tại vị trí p
 Delete(p): xóa phần tử tại vị trí p
 Search(x): tìm phần tử x
 Traverse(): duyệt danh sách
Danh sách phù hợp cho dữ liệu có thứ tự.
Mã giả các hàm của ADT LIST: Create(L) L.size ← 0 IsEmpty(L) if L.size = 0 then return TRUE else return FALSE 3 06/01/2026 Insert(L, x, p) if L.size = MAX then return "Danh sách đầy"
if p < 0 or p > L.size then
return "Vị trí không hợp lệ" for i ← L.size downto p+1 do L.A[i] ← L.A[i-1] L.A[p] ← x L.size ← L.size + 1 Delete(L, p) if IsEmpty(L) then return "Danh sách rỗng"
if p < 0 or p ≥ L.size then
return "Vị trí không hợp lệ" for i ← p to L.size-2 do L.A[i] ← L.A[i+1] L.size ← L.size - 1 4 06/01/2026 Search(L, x) for i ← 0 to L.size-1 do if L.A[i] = x then
return i // vị trí tìm thấy return -1 Traverse(L) if IsEmpty(L) then print "Danh sách rỗng" else for i ← 0 to L.size-1 do print L.A[i] 5 06/01/2026 Create(L) Insert(L, 2, 0) Insert(L, 4, 1) Insert(L, 6, 2) Traverse(L) Insert(L, 5, 2) Traverse(L) Delete(L, 1) Traverse(L) pos ← Search(L, 5) print pos
4. ADT Danh sách liên kết (Linked List)
Danh sách liên kết là một danh sách gồm các nút
(node), mỗi nút chứa: dữ liệu và liên kết đến nút khác.
Danh sách liên kết đơn có cấu trúc: Data và Next.
Danh sách liên kết kép có cấu trúc: Data, Next và Prev. 6 06/01/2026 Các phép toán cơ bản:
 IsEmpty(): kiểm tra rỗng
 Insert(x, p): chèn phần tử x tại vị trí p
 Delete(p): xóa phần tử tại vị trí p
 Search(x): tìm phần tử x
 Traverse(): duyệt danh sách
Mã giả các hàm của ADT LINKED LIST đơn: Create(L) L.Head ← NULL IsEmpty(L) if L.Head = NULL then return TRUE else return FALSE 7 06/01/2026 Insert(L, x, 0) new ← new Node new.data ← x new.next ← L.Head L.Head ← new Insert(L, x, p) if p < 0 then
return "Vị trí không hợp lệ" cur ← L.Head i ← 0
while cur ≠ NULL and i < p-1 do cur ← cur.next i ← i + 1 if cur = NULL then
return "Vị trí không hợp lệ" new ← new Node new.data ← x new.next ← cur.next cur.next ← new 8 06/01/2026 Delete(L, 0) if IsEmpty(L) then return "Danh sách rỗng" temp ← L.Head L.Head ← L.Head.next delete temp Delete(L, p) if IsEmpty(L) then return "Danh sách rỗng" cur ← L.Head i ← 0
while cur.next ≠ NULL and i < p-1 do cur ← cur.next i ← i + 1 if cur.next = NULL then
return "Vị trí không hợp lệ" temp ← cur.next cur.next ← temp.next delete temp 9 06/01/2026 Search(L, x) cur ← L.Head pos ← 0 while cur ≠ NULL do if cur.data = x then return pos cur ← cur.next pos ← pos + 1
return -1 // không tìm thấy Traverse(L) if IsEmpty(L) then print "Danh sách rỗng" else cur ← L.Head while cur ≠ NULL do print cur.data cur ← cur.next 10 06/01/2026 L.Head ← NULL Insert(L, 2, 0) Insert(L, 4, 1) Insert(L, 6, 2) Traverse(L) Insert(L, 5, 2) Traverse(L) Delete(L, 1) Traverse(L) pos ← Search(L, 5) print pos 5. ADT Ngăn xếp (Stack)
Ngăn xếp là một ADT trong đó các thao tác chỉ
thực hiện tại một đầu (top).
Nguyên tắc: LIFO – Last In, First Out. 11 06/01/2026 Các phép toán cơ bản:
 Push(x): đưa phần tử x vào stack
 Pop(): lấy phần tử trên cùng ra
 Peek(): xem phần tử trên cùng  IsEmpty()  IsFull()
Phù hợp cho dữ liệu có thứ tự ngược.
Mã giả các hàm của ADT STACK: Create(S) S.top ← -1 IsEmpty(S) if S.top = -1 then return TRUE else return FALSE 12 06/01/2026 IsFull(S) if S.top = MAX - 1 then return TRUE else return FALSE Push(S, x) if IsFull(S) then return "Stack đầy" S.top ← S.top + 1 S.A[S.top] ← x Pop(S) if IsEmpty(S) then return "Stack rỗng" x ← S.A[S.top] S.top ← S.top - 1 return x Peek(S) if IsEmpty(S) then return "Stack rỗng" return S.A[S.top] 13 06/01/2026 Create(S) Push(S, 5) Push(S, 8) Push(S, 3) Peek(S) Pop(S) Peek(S) IsEmpty(S) IsFull(S) 6. ADT Hàng đợi (Queue)
Hàng đợi là một ADT trong đó phần tử vào trước sẽ ra trước.
Nguyên tắc: FIFO – First In, First Out. 14 06/01/2026 Các phép toán cơ bản:
 Enqueue(x): thêm phần tử x vào cuối
 Dequeue(): lấy phần tử ở đầu ra  Front()  IsEmpty()  IsFull()
Phù hợp cho dữ liệu có thứ tự nối tiếp.
Mã giả các hàm của ADT QUEUE: Create(Q) Q.front ← -1 Q.rear ← -1 IsEmpty(Q) if Q.front = -1 then return TRUE else return FALSE 15 06/01/2026 IsFull(Q)
if (Q.rear + 1) mod MAX = Q.front then return TRUE else return FALSE Front(Q) if IsEmpty(Q) then return "Queue rỗng" return Q.A[Q.front] Enqueue(Q, x) if IsFull(Q) then return "Queue đầy" if IsEmpty(Q) then Q.front ← 0 Q.rear ← 0 else
Q.rear ← (Q.rear + 1) mod MAX Q.A[Q.rear] ← x 16 06/01/2026 Dequeue(Q) if IsEmpty(Q) then return "Queue rỗng" x ← Q.A[Q.front] if Q.front = Q.rear then Q.front ← -1 Q.rear ← -1 else
Q.front ← (Q.front + 1) mod MAX return x Create(Q) Enqueue(Q, 5) Enqueue(Q, 8) Enqueue(Q, 3) Front(Q) Dequeue(Q) Front(Q) IsEmpty(Q) IsFull(Q) 17 06/01/2026
SO SÁNH CÁC KIỂU DỮ LIỆU TRỪU TƯỢNG CƠ BẢN Thực tế:
Một bài toán không chỉ có một ADT duy nhất.
Có nhiều ADT đều dùng được, nhưng:
 Mức độ phù hợp khác nhau.  Hiệu quả khác nhau.
 Độ phức tạp chương trình khác nhau.
Ví dụ 1: Xây dựng thành phần phần mềm Quản lý danh sách sinh viên.
ADT phù hợp: List, Linked List. 18 06/01/2026
Ví dụ 2: Xây dựng thành phần phần mềm Quản
lý lịch sử thao tác (Undo). ADT phù hợp: Stack.
Ví dụ 3: Xây dựng thành phần phần mềm Quản
lý Hàng chờ xử lý công việc. ADT phù hợp: Queue. 19 06/01/2026 BÀI TẬP
Bài tập 1: Quản lý lịch học trong ngày
Mô tả: Một ứng dụng cần lưu danh sách các tiết
học trong một ngày theo thứ tự thời gian. Danh sách:
 Được tạo một lần vào đầu ngày.
 Chỉ dùng để duyệt và hiển thị.
 Không có thao tác thêm hoặc xóa trong ngày.
Câu hỏi: Chọn ADT nào là phù hợp và Giải thích lý do.
Đáp án Bài tập 1: Quản lý lịch học trong ngày ADT phù hợp: List.
Giải thích: Danh sách tiết học được tạo một lần
và không thay đổi trong ngày. Chương trình chủ
yếu duyệt và hiển thị dữ liệu theo thứ tự. Do đó,
ADT danh sách là phù hợp và đơn giản nhất. 20