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