Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Danh sách liên kết - Phan Mạnh Hiển (2020)

Bài giảng "Cấu trúc dữ liệu và giải thuật: Danh sách liên kết" cung cấp cho người học các kiến thức: Danh sách liên kết, danh sách liên kết đơn, danh sách liên kết đôi, danh sách liên kết vòng tròn. | Bài giảng Cấu trúc dữ liệu và giải thuật Danh sách liên kết - Phan Mạnh Hiển 2020 Danh sách liên kết Linked Lists Nguyễn Mạnh Hiển hiennm@tlu.edu.vn Nội dung 1. Danh sách liên kết 2. Danh sách liên kết đơn 3. Danh sách liên kết đôi 4. Danh sách liên kết vòng tròn 1. Danh sách liên kết Danh sách liên kết Là một tập nút liên kết với nhau theo trật tự tuyến tính Mỗi nút chứa một phần tử một hoặc nhiều liên kết tới các nút lân cận Các nút nằm rải rác trong bộ nhớ máy tính trong khi các phần tử của mảng và vector nằm liên tục Các kiểu danh sách liên kết Danh sách liên kết đơn Danh sách liên kết đôi Danh sách liên kết vòng tròn 2. Danh sách liên kết đơn Danh sách liên kết đơn Có một liên kết duy nhất giữa hai nút liên tiếp Các thao tác chính Chèn phần tử mới vào đầu danh sách Xóa phần tử đầu danh sách Lấy phần tử đầu danh sách Cài đặt danh sách liên kết đơn template class SingleList public hàm tạo hàm hủy chèn xóa ở đầu danh sách lấy phần tử đầu danh sách . private struct Node . kiểu dữ liệu của các nút Node head con trỏ tới nút đầu danh sách Kiểu dữ liệu của các nút struct Node T elem phần tử Node next liên kết tới nút kế tiếp Hàm tạo Node T e Node n elem e next n Hàm tạo và hàm hủy SingleList head NULL Hàm empty kiểm tra trạng thái rỗng Hàm popFront xóa phần tử đầu danh sách tham khảo các slide sau cho hai hàm đó SingleList while empty popFront Các hàm khác Kiểm tra danh sách có rỗng hay không bool empty return head NULL Lấy phần tử đầu danh sách T front return head- gt elem Chèn vào đầu danh sách Chèn vào đầu danh sách tiếp e element là phần tử cần chèn void pushFront T e v là nút mới trong đó v.next head có nghĩa là v trỏ tới nút đầu danh sách. Node v new Node e head Nút đầu danh sách bây giờ là v vì vậy phải cập nhật con trỏ head. head v Xóa phần tử đầu danh sách Xóa phần tử đầu danh sách tiếp void popFront Giữ lại nút đầu danh sách Node old head Nhảy sang nút kế tiếp head head- gt next Xóa nút đầu danh sách cũ delete old Phân tích thời gian chạy Hàm tạo O 1 Hàm .