Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 7 - Trường ĐH Văn Lang

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!
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 7 - Trường ĐH Văn Lang 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) { this.iData = value; this.pNext = 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 + p.pNext = 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 P.pNext=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 { p.pNext = 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 + pTail.pNext=p; + pTail=p 17 KHOA CÔNG NGHỆ THÔNG TIN pTail 3 4f 5f f 4 4f 8 5f 5N 9f pTail=P pTail.pNext 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 { pTail.pNext = p; // Nếu xem Node p đứng ở cuối danh sách pTail = p; // Node p giờ đây được cập nhật là Node cuối danh sách } } 19 KHOA CÔNG NGHỆ THÔNG TIN Ta cần thêm nút p vào sau nút q trong list đơn Bắt đầu: Nếu (q!=null) thì B1: p.pNext = q.pNext B2: + q.pNext = p + nếu q = pTail thì pTail=p 20 KHOA CÔNG NGHỆ THÔNG TIN 3 4 q 5 f 4 4f f 8 59 f 5 .. f 9 q.pNext=P f7 N ...