Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4.2 - Trần Minh Thái (2016)

Chia sẻ: Bình Yên | Ngày: | Loại File: PPTX | Số trang:27

Thêm vào BST

Báo xấu

57
lượt xem 2
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 4: Danh sách liên kết" sẽ giúp sinh viên trình bày, hiểu và vận dụng vào lập trình một số kỹ thuật sau để xử lý trên DSLK đơn gồm: Chèn thêm một node, xoá một node, sắp xếp. 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 4.2 - Trần Minh Thái (2016)

Chương 4. Danh sách liên kết – Phần 2 Trần Minh Thái Email: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn Cập nhật: ngày 30 tháng 10 năm 2016
Nội dung Sinh viên sẽ được trình bày, hiểu và vận dụng vào lập trình một số kỹ thuật sau để xử lý trên DSLK đơn: 1. Chèn thêm một node 2. Xoá một node 3. Sắp xếp 2
Chèn node vào DSLK đơn • Chèn vào sau node p • Chèn vào trước node p 25 p pNew list 3 pHead pTail
Chèn node vào sau node p p pNew list 4 pHead pTail
Chèn node vào sau node p • Input: DSLK list, node p và node cần thêm pNew • Output: list sau khi thêm pNew vào sau p • Algorithm: • B1: Nếu p là pTail của list thì Thêm pNew vào cuối list: Kết thúc • B2: pSau = p.pNext Nối pNew vào pSau Nối p vào pNew 5
?Cài đặt phương thức thêm pNew vào sau p public void InsertAfterP(Node p, Node pNew) { } 6
Chèn node vào trước node p – Cách 1 pPrev p pNew list 7 pHead pTail
Tìm node trước node p • Input: DSLK list, node p • Output: node phía trước node p: pTruoc (nếu không có node trước p thì trả về null) • Algorithm: • B1: Nếu p là pHead của list thì Trả về null: Kết thúc • B2: pTruoc = pHead của list • B3: Trong khi node sau của pTruoc khác p thực hiện pTruoc = node sau của pTruoc 8
? Cài đặt phương thức tìm node trước node p public Node PrevNodeP (Node p) { } 9
Chèn node pNew vào trước node p • Input: DSLK list, node p, node cần thêm pNew • Output: list sau khi thêm pNew vào trước node p (trả về true nếu chèn thành công, ngược lại trả về false) • Algorithm: • B1: Nếu p là pHead của list thì Thêm pNew vào đầu list trả về true: Kết thúc • B2: pTruoc = Tìm node trước p • B3: Nếu pTruoc = null trả về false: Kết thúc 10 • B4: pTruoc nối với pNew
? Cài đặt phương thức thêm pNew vào trước node p – Cách 1 public bool InsertBeforeP1 (Node p, Node pNew) { } 11
Chèn node vào trước node p – Cách 2 Bước 1. Chèn pNew vào sau p Bước 2. Hoán vị giá trị pNew và p p pNew list 12 pHead pTail
?Cài đặt phương thức thêm pNew vào trước node p – Cách 2 public bool InsertBeforeP2 (Node p, Node pNew) { } 13
Xóa một node trong danh sách • TH1: Xóa node đầu của danh sách  Ảnh hưởng pHead • TH2: Xóa node cuối của danh sách  Ảnh hưởng pTail • TH còn lại: Xoá node bên trong danh sách 14
Xóa một nút trong danh sách • TH1: Xóa nút đầu của danh sách Cần xóa list 30 25 41 78 pHead pTail pDel 15
Xoá node đầu của DSLK • Input: DSLK list • Output: list sau khi xoá node đầu • Algorithm: • B1: Nếu list có pHead = pTail thì pHead = pTail = null: Kết thúc • B2: Cập nhật pHead là node sau của pHead 16
?Cài đặt phương thức xoá node đầu DSLK public void DeleteHead () { } 17
Xóa một node trong danh sách • TH 2: Xóa node cuối của danh sách Cần xóa pPrev pDel list 30 25 41 78 pHead pTail 18
Xoá node cuối trong danh sách • Input: DSLK list • Output: list sau khi xoá node cuối • Algorithm: • B1: Nếu list có pHead = pTail thì pHead = pTail = null: Kết thúc • B2: pTruoc = node trước pTail của list pTail = null pTail = pTruoc 19
?Cài đặt phương thức xoá node cuối DSLK public void DeleteTail () { } 20