77
Chương 4:
DANH SÁCH (LIST)
78
NỘI DUNG CHƯƠNG 4
1. Khái niệm danh sách
2. Các phép toán trên danh sách
3. Danh sách đặc
•Định nghĩa
•Biểu diễn danh sách đặc
•Các thao tác trên danh sách đặc
•Ưu nhược điểm và ứng dụng
4. Danh sách liên kết
•Định nghĩa
•Danh sách liên kết đơn
•Danh sách liên kết kép
•Ưu nhược điểm của danh sách liên kết
5. Danh sách hạn chế
•Hàng đợi
•Ngăn xếp
•Ứng dụng của danh sách hạn chế
79
1. Khái niệm danh sách
•Danh sách a1, a2, ….aNlà tập hợp các phần tử có kiểu
dữ liệu xác định và giữa chúng có 1 mối quan hệ nào đó.
Nếu biết phần tử aivị trí của phần tử ai+1
•Số phần tử trong một danh sách là chiều dài của 1 danh
sách. Danh sách rỗng là danh sách có chiều dài = 0
•Cho T là một kiểu được định nghĩa trước, kiểu danh
sách TXgồm các phần tử thuộc kiểu T được định nghĩa
là:
TX= < VX, OX>
Trong đó :
•VX= { tập hợp các thứ tự gồm một số biến động các phần tử kiểu
T }.
•OX= { tạo danh sách; tìm 1 phần tử trong danh sách; chèn 1
phần tử vào danh sách; huỷ 1 phần tử khỏi danh sách; liệt kê
danh sách, sắp xếp danh sách.}.
80
2. Các phép toán trên danh sách
Tùy theo loại của từng danh sách sẽ có các phép toán khác
nhau, các phép toán thông thường như sau:
2.1. Tạo mới 1 danh sách
•Đưa vào danh sách nội dung các phần tử.
•Chiều dài của danh sách là xác định.
2.2. Thêm 1 phần tử vào danh sách
•Khi thêm 1 phần tử chiều dài danh sách tăng lên.
•Có thao tác thêm vào đầu, cuối hay tại 1 vị trí xác định của
danh sách.
2.3. Tìm kiếm 1 phần tử trong danh sách
•Tìm 1 phần tử trong danh sách thỏa mãn điều kiện nào đó
•Dùng các thuật toán tìm kiếm trong chương “Tìm kiếm”
81
2. Các phép toán trên danh sách
2.4. Loại bớt 1 phần tử trong danh sách
•Chiều dài danh sách giảm xuống 1 phần tử
•Công việc loại bớt cũng bao gồm thao tác tìm kiếm ra
phần tử cần hủy trong danh sách.
2.5. Sửa đổi giá trị 1 phần tử trong danh sách
•Thay đổi thông tin của 1 phần tử trong danh sách
•Công việc cập nhật phần tử cũng bao gồm thao tác tìm
kiếm ra phần tử cần hủy trong danh sách.
2.6. Sắp xếp danh sách
•Dùng các thuật toán trong chương sắp xếp.