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)

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.
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 4.2 - Trần Minh Thái (2016) Chương 4. Danh sách liên kết – Phần 2TrầnMinhTháiEmail:minhthai@huflit.edu.vnWebsite:www.minhthai.edu.vn Cập nhật: ngày 30 tháng 10 năm 2016Nội dungSinh viên sẽ được trình bày, hiểu và vận dụng vàolập trình một số kỹ thuật sau để xử lý trên DSLKđơn:1. Chèn thêm một node2. Xoá một node3. 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 pNewlist 3 pHead pTail Chèn node vào sau node p p pNewlist 4 pHead pTailChè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 pNewlist 7 pHead pTailTì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 ppublic Node PrevNodeP (Node p){} 9Chè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 1public bool InsertBeforeP1 (Node p, NodepNew){} 11 Chèn node vào trước node p – Cách 2 Bước1.ChènpNewvàosaup Bước2.HoánvịgiátrịpNewvàp p pNewlist 12 pHead pTail?Cài đặt phương thức thêm pNew vào trước node p – Cách 2public bool InsertBeforeP2 (Node p, NodepNew){} 13Xó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óalist 30 25 41 78 pHead pTail pDel 15Xoá 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 DSLKpublic 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 pDellist 30 25 41 78 pHead pTail 18Xoá 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 DSLKpublic void DeleteTail (){} 20 ...