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 - Phần 2 - Trần Minh Thái

Chương 4. Danh sách liên kết – Phần 2Trần Minh Thá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ào lập trình một số kỹ thuật sau để xử lý trên DSLK đơn:Chèn thêm một nodeXoá một nodeSắp xếp2Chèn node vào DSLK đơnChèn vào sau node pChèn vào trước node p3pHeadpTaillist25pNewpChèn node vào sau node p4pHeadpTaillistpNewpChèn node vào sau node pInput: DSLK list, node p và node cần thêm pNewOutput: list sau khi thêm pNew vào sau pAlgorithm:B1: Nếu p là pTail của list thì Thêm pNew vào cuối list: Kết thúcB2: pSau = p.pNext Nối pNew vào pSau Nối p vào pNew 5Cài đặt phương thức thêm pNew vào sau p6public void InsertAfterP(Node p, Node pNew){}?Chèn node vào trước node p – Cách 17pHeadpTaillistpNewppPrevTìm node trước node pInput: DSLK list, node pOutput: 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úcB2: pTruoc = pHead của listB3: Trong khi node sau của pTruoc khác p thực hiện pTruoc = node sau của pTruocB4: Trả về pTruoc 8Cài đặt phương thức tìm node trước node p9public Node PrevNodeP (Node p){}?Chèn node pNew vào trước node pInput: DSLK list, node p, node cần thêm pNewOutput: 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úcB2: pTruoc = Tìm node trước pB3: Nếu pTruoc = null trả về false: Kết thúcB4: pTruoc nối với pNew pNew nối với node sau của p trả về true10Cài đặt phương thức thêm pNew vào trước node p – Cách 111public bool InsertBeforeP1 (Node p, Node pNew){}?Chèn node vào trước node p – Cách 212pHeadpTaillistpNewpBước 1. Chèn pNew vào sau pBước 2. Hoán vị giá trị pNew và pCài đặt phương thức thêm pNew vào trước node p – Cách 213public bool InsertBeforeP2 (Node p, Node pNew){}?Xóa một node trong danh sáchTH1: Xóa node đầu của danh sách  Ảnh hưởng pHeadTH2: Xóa node cuối của danh sách  Ảnh hưởng pTailTH còn lại: Xoá node bên trong danh sách14Xóa một nút trong danh sáchTH1: Xóa nút đầu của danh sách15pHeadpTaillist30254178Cần xóapDelXoá node đầu của DSLKInput: DSLK listOutput: list sau khi xoá node đầuAlgorithm:B1: Nếu list có pHead = pTail thì pHead = pTail = null: Kết thúcB2: Cập nhật pHead là node sau của pHead16Cài đặt phương thức xoá node đầu DSLK17public void DeleteHead (){}?Xóa một node trong danh sáchTH 2: Xóa node cuối của danh sách18pHeadpTaillist30254178Cần xóapDelpPrevXoá node cuối trong danh sáchInput: DSLK listOutput: list sau khi xoá node cuốiAlgorithm:B1: Nếu list có pHead = pTail thì pHead = pTail = null: Kết thúcB2: pTruoc = node trước pTail của list pTail = null pTail = pTruoc19Cài đặt phương thức xoá node cuối DSLK20public void DeleteTail (){}?Xóa một node trong danh sáchTH còn lại: Xóa node bên trong danh sách21pHeadpTaillist30254178Cần xóapDelpPrev96Xoá node pDel bên trong DSLKInput: DSLK list, node pDelOutput: list sau khi xoá node pDelAlgorithm:B1: pTruoc = node trước node pDelB2: pTruoc nối với node sau của pDelB3: pDel = null22Đoạn code bằng C#?Xoá 1 node pDel bất kỳ của DSLKInput: DSLK list, node pDelOutput: list sau khi xoá node pDelAlgorithm:B1: Nếu pDel là pHead của list thì gọi DeleteHead(), kết thúcB2: Ngược lại nếu pDel là pTail của list thì gọi DeleteTail(), kết thúcB3: Ngược lại tìm node pTruoc là node trước pDel pTruoc nối với node sau của pDel pDel = null23Cài đặt phương thức xoá 1 node pDel bất kỳ trong DSLK24public void DeleteNode (Node pDel){}?Bài tập tại lớpĐịnh nghĩa các phương thức theo yêu cầu sau:1. Chèn node có giá trị x vào phía sau node có giá trị lớn nhất (giả sử danh sách không có giá trị trùng nhau)2. Xóa node có giá trị x xuất hiện đầu tiên trong danh sách (nếu có xóa: trả về true, ngược lại trả về false)3. Sắp DSLK theo thứ tự tăng dần (dùng phương pháp chọn trực tiếp)25Bài tập thực hànhSử dụng lại lớp DSLK đơn (CMyLinkedList), bổ sung các phương thức:Khi nhập dữ liệu vào danh sách sẽ tìm tự động vị trí thích hợp để chèn vào nhằm đảm bảo có thứ thự tăng dần (áp dụng kỹ thuật chèn trực tiếp và khoá so sánh bất kỳ)Bổ sung các phương thức xoá nodePhương thức sắp xếp theo thứ tự tăng dần dựa vào khoá so sánh bất kỳ26