Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 7 Danh sách liên kết, cung cấp cho người học những kiến thức như: các loại danh sách liên kết; danh sách liên kết đơn; cấu trúc dữ liệu của danh sách liên kết đơn; khởi tạo danh sách liên kết đơn. Mời các bạn cùng tham khảo! | A B C D A B C D 2 KHOA CÔNG NGHỆ THÔNG TIN A B C D A B C D 3 KHOA CÔNG NGHỆ THÔNG TIN DANH SÁCH LIÊN KẾT ĐƠN LIST 5 KHOA CÔNG NGHỆ THÔNG TIN x2 x0 x3 x1 6 KHOA CÔNG NGHỆ THÔNG TIN pNext Info 7 KHOA CÔNG NGHỆ THÔNG TIN pHead pTail 3f 4f 5f 4 4f 7 5f 6 NULL Trong ví dụ trên thành phần dữ liệu là 1 số nguyên 8 KHOA CÔNG NGHỆ THÔNG TIN Tạo 1 danh sách liên kết đơn rỗng Tạo 1 nút có trường Info bằng x Tìm một phần tử có Info bằng x Thêm một phần tử có khóa x vào danh sách Hủy một phần tử trong danh sách Duyệt danh sách Sắp xếp danh sách liên kết đơn 9 KHOA CÔNG NGHỆ THÔNG TIN Đầu tiên thiết lập Node class Node public int iData public Node pNext public Node int value value null 10 KHOA CÔNG NGHỆ THÔNG TIN Khai báo thông tin danh sách class MyLinkedList Node pHead pTail public MyLinkedList pHead null pTail null 11 KHOA CÔNG NGHỆ THÔNG TIN Nguyên tắc thêm Khi thêm 1 phần tử vào List thì có làm cho pHead pTail thay đổi Các vị trí cần thêm 1 phần tử vào List Thêm vào đầu List Thêm vào cuối List Thêm vào sau 1 phần tử q trong list 13 KHOA CÔNG NGHỆ THÔNG TIN Thêm nút p vào đầu danh sách liên kết đơn Bắt đầu Nếu List rỗng thì pHead p pTail pHead Ngược lại pHead pHead p 14 KHOA CÔNG NGHỆ THÔNG TIN pHead 2 3 4 f3 3f f 4 4f f8 9f 10 2f N pHead P pHead P 15 KHOA CÔNG NGHỆ THÔNG TIN public void AddHead Node p if pHead null kiểm tra nếu danh sách đang rỗng pHead null pHead pTail p Node p vừa là đầu vừa là cuối else nếu danh sách không rỗng pHead Nếu xem Node p đứng ở đầu danh sách pHead p Node p giờ đây được cập nhật là Node đầu danh sách 16 KHOA CÔNG NGHỆ THÔNG TIN Ta cần thêm nút p vào cuối list đơn Bắt đầu Nếu List rỗng thì pHead p pTail pHead Ngược lại p pTail p 17 KHOA CÔNG NGHỆ THÔNG TIN pTail 3 4f 5f f 4 4f 8 5f 5N 9f pTail P 9f 6N P 18 KHOA CÔNG NGHỆ THÔNG TIN public void AddTail Node p if pHead null kiểm tra nếu danh sách đang rỗng pHead pTail p Node p vừa là đầu vừa là cuối else nếu danh sách không rỗng
