Nội dung

CHƯƠNG 4 KIỂU DANH SÁCH LIÊN KẾT GV Th.S. Thiều Quang Trung Bộ môn Khoa học cơ bản Trường Cao đẳng Kinh tế Đối ngoại Nội dung 1 • Khái niệm danh sách liên kết 2 • Các phép tính trên danh sách liên kết đơn 3 • Các phép tính trên danh sách liên kết kép 4 • Ứng dụng của danh sách liên kết GV. Thiều Quang Trung 2 Danh sách liên kết • Định nghĩa: Danh sách liên kết (DSLK) là một danh sách mà các phần tử được kết nối với nhau nhờ vào vùng liên kết của chúng. • Một phần tử của DSLK bao gồm 2 vùng chính: – Vùng chứa thông tin – Vùng chứa địa chỉ, còn gọi là vùng liên kết • DSLK là cấu trúc dữ liệu động nên có thể thực hiện các phép thêm vào, loại bỏ phần tử trong khi chạy chương trình. • Việc lưu trữ DSLK tốn bộ nhớ hơn danh sách đặc vì phải chứa thêm vùng liên kết. GV. Thiều Quang Trung 3 Danh sách liên kết • Các kiểu tổ chức DSLK: – Danh sách liên kết đơn: mỗi phần tử liên kết với phần tử đứng sau nó trong danh sách: A B X Z Y – Danh sách liên kết kép: mỗi phần tử liên kết với các phần tử đứng trước và sau nó trong danh sách: A B C D – Danh sách liên kết vòng: phần tử cuối danh sách liên kết với phần tử đầu danh sách: GV. Thiều Quang Trung 4 Danh sách liên kết – Danh sách liên kết đơn vòng A B A X B Z C Y D – Danh sách liến kết kép vòng GV. Thiều Quang Trung 5 Danh sách liên kết • Các phép toán cơ bản trên danh sách liên kết: 1. 2. 3. 4. 5. 6. 7. Khởi tạo danh sách Kiểm tra danh sách rỗng Tìm kiếm 1 phần tử trong danh sách Thêm 1 phần tử vào danh sách Hủy 1 phần tử khỏi danh sách Duyệt danh sách Hủy toàn bộ danh sách GV. Thiều Quang Trung 6 Danh sách liên kết đơn • Định nghĩa: DSLK đơn là loại DSLK mà vùng địa chỉ của mỗi phần tử chỉ chứa duy nhất một địa chỉ của phần tử tiếp theo. • Phần tử cuối cùng của DSLK đơn sẽ trỏ đến NULL NULL head A B X GV. Thiều Quang Trung Z Y 7 Danh sách liên kết đơn • Ví dụ: Ta có danh sách theo dạng bảng sau Ta có danh sách liên kết là : Joe – Marta – Bill – Koch - Sahra Address Name Age Link 100 Joe 20 140 110 Bill 42 500 140 Marta 27 110 230 Sahra 25 NULL … … … 500 Koch 31 GV. Thiều Quang Trung 230 8 Cài đặt danh sách liên kết đơn • Khai báo kiểu của 1 phần tử và kiểu danh sách liên kết đơn. • Để đơn giản ta xét mỗi node gồm vùng chứa dữ liệu là kiểu số nguyên: typedef { int NODE }; typedef { NODE }; struct NODE // kiểu của một phần tử trong danh sách info; *pNext; struct LIST // kiểu danh sách liên kết *phead; • Trong thực tế biến info là một kiểu struct GV. Thiều Quang Trung 9 Ví dụ danh sách liên kết đơn GV. Thiều Quang Trung 10