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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:69

Thêm vào BST

Báo xấu

15
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 5 P.pNext = q.pNext f P 21 KHOA CÔNG NGHỆ THÔNG TIN