Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - Th.S Thiều Quang Trung

CHƯƠNG 4<br /> KIỂU DANH SÁCH LIÊN KẾT<br /> GV Th.S. Thiều Quang Trung<br /> Bộ môn Khoa học cơ bản<br /> Trường Cao đẳng Kinh tế Đối ngoại<br /> <br /> Nội dung<br /> <br /> 1<br /> <br /> • Khái niệm danh sách liên kết<br /> <br /> 2<br /> <br /> • Các phép tính trên danh sách liên kết đơn<br /> <br /> 3<br /> <br /> • Các phép tính trên danh sách liên kết kép<br /> <br /> 4<br /> <br /> • Ứng dụng của danh sách liên kết<br /> <br /> GV. Thiều Quang Trung<br /> <br /> 2<br /> <br /> Danh sách liên kết<br /> • Định nghĩa: Danh sách liên kết (DSLK) là một danh<br /> sách mà các phần tử được kết nối với nhau nhờ vào<br /> vùng liên kết của chúng.<br /> • Một phần tử của DSLK bao gồm 2 vùng chính:<br /> – Vùng chứa thông tin<br /> – Vùng chứa địa chỉ, còn gọi là vùng liên kết<br /> <br /> • DSLK là cấu trúc dữ liệu động nên có thể thực hiện<br /> các phép thêm vào, loại bỏ phần tử trong khi chạy<br /> chương trình.<br /> • Việc lưu trữ DSLK tốn bộ nhớ hơn danh sách đặc vì<br /> phải chứa thêm vùng liên kết.<br /> GV. Thiều Quang Trung<br /> <br /> 3<br /> <br /> Danh sách liên kết<br /> • Các kiểu tổ chức DSLK:<br /> <br /> – Danh sách liên kết đơn: mỗi phần tử liên kết với<br /> phần tử đứng sau nó trong danh sách:<br /> A<br /> <br /> B<br /> <br /> X<br /> <br /> Z<br /> <br /> Y<br /> <br /> – Danh sách liên kết kép: mỗi phần tử liên kết với<br /> các phần tử đứng trước và sau nó trong danh<br /> sách:<br /> A<br /> <br /> B<br /> <br /> C<br /> <br /> D<br /> <br /> – Danh sách liên kết vòng: phần tử cuối danh sách<br /> liên kết với phần tử đầu danh sách:<br /> GV. Thiều Quang Trung<br /> <br /> 4<br /> <br /> Danh sách liên kết<br /> – Danh sách liên kết đơn vòng<br /> A<br /> <br /> B<br /> <br /> A<br /> <br /> X<br /> <br /> B<br /> <br /> Z<br /> <br /> C<br /> <br /> Y<br /> <br /> D<br /> <br /> – Danh sách liến kết kép vòng<br /> GV. Thiều Quang Trung<br /> <br /> 5<br /> <br />