Bài giảng "Cấu trúc dữ liệu và giải thuật" Chương Danh sách móc nối, cung cấp cho người học những kiến thức như Con trỏ và cấp phát bộ nhớ cho đối tượng động; Mô tả cấu trúc lưu trữ móc nối (danh sách móc nối); Các loại danh sách móc nối; Cài đặt LIFO, FIFO bằng cấu trúc lưu trữ móc nối; . Mời các bạn cùng tham khảo! | Chương 2 CẤU TRÚC TUYẾN TÍNH Phần 3 Danh sách móc nối Data structures and Algorithms 2 18 2021 Cấu trúc dữ liệu và giải thuật 1 Các nội dung chính Con trỏ và cấp phát bộ nhớ cho đối tượng động Mô tả cấu trúc lưu trữ móc nối danh sách móc nối Các loại danh sách móc nối Danh sách nối đơn Danh sách nối đơn thẳng Danh sách nối đơn vòng Danh sách nối kép Danh sách nối kép thẳng Danh sách nối kép vòng Cài đặt LIFO FIFO bằng cấu trúc lưu trữ móc nối LIFO FIFO 2 Con trỏ và cấp phát bộ nhớ cho đối tượng động Con trỏ pointer là một kiểu dữ liệu datatype mà giá trị của nó chỉ dùng để chỉ đến một giá trị khác chứa trong bộ nhớ. P A 1000 20 amp A 1000 Các thao tác cơ bản Khởi tạo khai báo int P Lấy địa chỉ 1 đối tượng int A 20 P amp A Truy nhập vào đối tượng được trỏ P 20 Cấp phát bộ nhớ động cho đối tượng DL động P new int Giải phóng đối tượng DL động delete P 3 Mô tả cấu trúc lưu trữ móc nối danh sách móc nối Là tập hợp các phần tử dữ liệu không liên tục được kết nối với nhau thông qua một liên kết thường là con trỏ Cho phép ta quản lý bộ nhớ linh động Các phần tử được chèn vào danh sách và xóa khỏi danh sách một cách dễ dàng Tại mỗi nút có hai thành phần Dữ liệu trong nút Con trỏ trỏ đến phần tử kế tiếp H con trỏ trỏ vào nút đầu của danh sách H Mô tả A B C D Trong bộ nhớ A 800 B 712 C 992 D 0 1000 800 712 992 4 Phân loại danh sách móc nối Phân loại theo hướng con trỏ hay số con trỏ trong 1 nút Danh sách nối đơn single linked list con trỏ luôn chỉ theo một hướng trong danh sách H A B C Danh sách nối kép double linked list 2 con trỏ chỉ theo hai hướng trong danh sách H A B C 5 Phân loại danh sách móc nối Phân loại theo cách móc nối vòng hoặc thẳng Danh sách nối thẳng truy cập vào danh sách thông qua điểm truy nhập H H A B C Danh sách nối vòng circularly linked list bất cứ nút nào trong danh sách cũng có thể coi là nút đầu hay nút cơ sở mọi nút có vai trò như nhau H A B C 6 Cài đặt danh sách nối đơn thẳng Dùng 1 con trỏ luôn chỉ theo một hướng trong danh sách Phần tử nút cuối
