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

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 do Th.S Thiều Quang Trung biên soạn có nội dung chính được trình bày như: Khái niệm danh sách liên kết, các phép tính trên danh sách liên kết đơn, các phép tính trên danh sách liên kết kép, ứng dụng của danh sách liên kết.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - Th.S Thiều Quang TrungCHƯƠNG 4KIỂU DANH SÁCH LIÊN KẾTGV Th.S. Thiều Quang TrungBộ môn Khoa học cơ bảnTrường Cao đẳng Kinh tế Đối ngoạiNội dung1• Khái niệm danh sách liên kết2• Các phép tính trên danh sách liên kết đơn3• Các phép tính trên danh sách liên kết kép4• Ứng dụng của danh sách liên kếtGV. Thiều Quang Trung2Danh sách liên kết• Định nghĩa: Danh sách liên kết (DSLK) là một danhsách mà các phần tử được kết nối với nhau nhờ vàovù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ệncác phép thêm vào, loại bỏ phần tử trong khi chạychươ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 Trung3Danh 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ớiphần tử đứng sau nó trong danh sách:ABXZY– Danh sách liên kết kép: mỗi phần tử liên kết vớicác phần tử đứng trước và sau nó trong danhsách:ABCD– Danh sách liên kết vòng: phần tử cuối danh sáchliên kết với phần tử đầu danh sách:GV. Thiều Quang Trung4Danh sách liên kết– Danh sách liên kết đơn vòngABAXBZCYD– Danh sách liến kết kép vòngGV. Thiều Quang Trung5