Xem mẫu

Ngôn ngữ lập trình
Bài 10:
Các Kiểu Dữ Liệu Trừu Tượng:
Danh sách liên kết,
Ngăn xếp, Hàng đợi
Giảng viên: Lê Nguyễn Tuấn Thành
Email:thanhlnt@tlu.edu.vn
Bộ Môn Công Nghệ Phần Mềm – Khoa CNTT
Trường Đại Học Thủy Lợi

Nội dung
1.

Các nút (Nodes) và Danh sách liên kết
1.

2.

Ứng dụng danh sách liên kết
1.
2.

3.

Ngăn xếp (Stack),
Hàng đợi (Queue)

Iterators
1.

4.

Tạo, tìm kiếm

Con trỏ như iterators

Cây (Trees)

Bài giảng có sử dụng hình vẽ trong cuốn sách “Absolute C++. W. Savitch, Addison Wesley, 2002”
2

Giới thiệu


Danh sách liên kết






Cây cũng sử dụng con trỏ
Con trỏ là xương sống của những cấu trúc này




Được xây dựng sử dụng con trỏ
Tăng giảm kích thước trong thời gian chạy

Sử dụng biến động

Thư viện mẫu chuẩn (STL)


Có những phiên bản định nghĩa sẵn của một vài cấu trúc

3

Cách tiếp cận


Có 3 cách để xử lý những cấu trúc dữ liệu này
1.
2.
3.





Cách tiếp cận C-style: sử dụng hàm và cấu trúc toàn cục
với mọi thứ đều public
Sử dụng lớp với các biến thành viên private và các hàm
accessor – mutator
Sử dụng lớp bạn

Danh sách liên kết sử dụng phương thức 1 (hoặc 2)
Ngăn xếp, Hàng đợi sử dụng phương thức 2
Cây sử dụng phương thức 3

4

Nút và danh sách liên kết


Danh sách liên kết





Một ví dụ đơn giản của “cấu trúc dữ liệu động”
Bao gồm nhiều nút

Mỗi nút là một biến kiểu cấu trúc hoặc đối tượng của
lớp (có thể tạo tự động với lệnh new)



Nút cũng bao gồm con trỏ trỏ tới những nút khác
Cung cấp “sự liên kết”

5

nguon tai.lieu . vn