tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Danh sách liên kết - Nguyễn Mạnh Hiển (HKI năm 2020-2021)

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. | Danh sách liên kết Linked Lists Nguyễn Mạnh Hiển hiennm@ 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 có trước có sau . Mỗi nút chứa một phần tử một hoặc hai liên kết tới 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 Mỗi nút chỉ có một liên kết trỏ tới nút kế tiếp. Riêng nút cuối cùng không có nút kế tiếp vì vậy con trỏ của nó bằng NULL. 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. e phần tử n địa chỉ của nút kế tiếp Node T e Node n elem e next n Hàm tạo và hàm hủy SingleList head NULL Ban đầu danh sách rỗng Hàm hủy dùng hàm empty để kiểm tra danh sách rỗng dùng hàm popFront để xóa phần tử đầu danh sách hai hàm đó ta sẽ lập trình sau . SingleList while empty Cứ xóa phần tử đầu tiên popFront cho đến khi danh sách rỗng thì thôi. 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 có kiểu là T . T front return head- gt elem head trỏ tới nút đầu còn elem là tên trường chứa phần tử. 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 Tạo nút mới v - chứa phần tử cần chèn e - trỏ tới nút đầu danh sách head Node v new Node e head Vì nút mới sẽ thành nút đầu danh sách phải cập nhật head cho trỏ tới nút mới. head v