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

Chương 4. Danh sách liên kết(Phần 1 – 3 tiết)Trần Minh TháiEmail: minhthai@huflit.edu.vnWebsite: www.minhthai.edu.vn Cập nhật: ngày 10 tháng 10 năm 2016Mục tiêuNắm vững khái niệm về kiểu dữ liệu tĩnh và độngNắm vững cách tổ chức dữ liệu động bằng danh sách liên kết và minh họa được các thao tác xử lý trên danh sách liên kết đơnCài đặt minh họa được các thao tác của danh sách đơn bằng ngôn ngữ C#2Vấn đề kiểu dữ liệu tĩnh3123456781057392151? Làm sao để chèn thêm số 6 vào vị trí 5 của mảng6Vấn đề kiểu dữ liệu tĩnh412345678910573921516Bổ sung thêm Giả sử cần thêm tiếp 1 phần tử?Bài tậpHãy cài phương thức (bằng ngôn ngữ C#) chèn một phần tử có giá trị x vào vị trí vt trong mảng số nguyên arr, theo mẫu như sau:class CMyIntArray{ int []arr; public void InsertX(int x, int vt){}}5Vấn đề kiểu dữ liệu tĩnh? Làm sao để xóa phần tử 96123456781057392151Vấn đề kiểu dữ liệu tĩnh7123456781057392151Bài tậpHãy cài đặt hàm (bằng ngôn ngữ C#) xóa phần tử có giá trị x (nếu có) trong mảng số nguyên arr, theo mẫu sau:class CMyIntArray{ int []arr; public void DeleteX(int x){}}8Vấn đề kiểu dữ liệu tĩnh9Độ phức tạp của chèn/ xóa trên mảng 1 chiều là O(n)iVấn đề kiểu dữ liệu tĩnhGiải quyết vấn đề phức tạp khi chèn/ xóa?Giải quyết vấn đề giới hạn kích thước vùng nhớ tối đa?Giải quyết vấn đề vùng nhớ không liên tục?Giải quyết vấn đề giải phóng vùng nhớ khi không cần dùng đến?10DÙNG CẤU TRÚC DỮ LIỆU ĐỘNGDanh sách liên kết (DSLK)1117263108594Các phần tử kết dính với nhau bằng “sợi dây liên kết”1217263108594Để đơn giản hơn trong việc minh họaĐặc điểm DSLKMột dãy tuần tự các nút (Node)Giữa hai nút có con trỏ liên kếtCác nút không cần phải lưu trữ liên tiếp nhau trong bộ nhớCó thể mở rộng tuỳ ý (chỉ giới hạn bởi dung lượng bộ nhớ)13Đặc điểm DSLKThao tác Chèn/Xóa không cần phải dịch chuyển phần tử mà chỉ cần thay đổi mối liên kếtQuản lý phần tử đầu tiên bằng con trỏ pHeadCó thể truy xuất đến các phần tử khác thông qua con trỏ liên kết14NodeCấu tạo của DSLK15pHeadpTailListCấu tạo của nútTạo lập bằng cách cấp phát bộ nhớ độngMỗi nút có 2 thông tin:Dữ liệu (data)Con trỏ liên kết đến phần tử kế tiếp trong danh sách (Next pointer link)Nếu không trỏ đến phần tử nào thì con trỏ Next = null16Thao tác chèn thêm node vào DSLK“Kết nối” lại sợi dây liên kết theo trình tự17pHeadpTailListThao tác xóa node khỏi DSLK18Cần xóapHeadpTailListCác loại hình DSLKDSLK đơn: Các phần tử kết nối với nhau theo hướng “chiều đi tới”19Các loại hình DSLKDSLK đôi: Các phần tử kết nối với nhau theo hướng “chiều đi tới và và đi lui”20Các loại hình DSLKDanh sách liên kết vòng: Các phần tử kết nối với nhau theo hướng “chiều đi tới” và phần tử cuối cùng có “đường đi vòng trở lại tới” phần tử đầu danh sách21So sánh Mảng và DSLKMảngDanh sách liên kếtKích thước cố địnhSố phần tử thay đổi tùy ýCác phần tử lưu trữ tuần tự (địa chỉ tăng dần) trong bộ nhớCác phần tử liên kết với nhau bằng con trỏPhải dịch chuyển các phần tử khi Thêm/XóaChỉ cần thay đổi con trỏ liên kết khi Thêm/XóaTruy xuất ngẫu nhiênTruy xuất tuần tự22DSLK đơn23Cấu trúc 1 nodeDatapNextData : Dữ liệu của nodepNext : Con trỏ đến node kế tiếppHead: Con trỏ đến node đầupTail: Con trỏ đến node cuốipHeadpTailListCấu tạo của DSLKQuản lý toàn bộ danh sách liên kết thông qua con trỏ đầu pHeadpHead không phải là 1 nút, nó chỉ là “con trỏ chỉ đến nút”Ta cũng có thể quản lý danh sách bằng cách sử dụng thêm con trỏ cuối (pTail)pTail không phải là 1 nút, nó chỉ là “con trỏ chỉ đến nút”24Cấu tạo của nútTạo lập bằng cách cấp phát bộ nhớ độngMỗi nút có 2 thông tin:Dữ liệu (data)Con trỏ liên kết đến phần tử kế tiếp trong danh sách (Next pointer link)Nếu không trỏ đến phần tử nào thì con trỏ Next = null25Khai báo node26datapNext public class Node { private T data; private Node pNext = null; public T Data { get { return data; } set { data = value; } } public Node PNext { get { return pNext; } set { pNext = value; } } }Khai báo node lưu số nguyên2720pNextpublic class IntNode{ private int data; private IntNode pNext = null; public int Data { get { return data; } set { data = value; } } public IntNode PNext { get { return pNext; } set { pNext = value; } }}Tạo lập danh sách rỗng28Sau khi tạo lập?pHead?pTailListTrước khi tạo lậppHeadpTailListpHead và pTail chưa xác địnhpHead và pTail trỏ vào null (rỗng)Khai báo DSLK đơn29pHeadpTailListclass CMyLinkedList{ private Node pHead = null; private Node pTail = null; //Các phương thức}Khai báo DSLK đơn số nguyên303291720pHeadpTailListpublic class CMyIntLinkedList{ private IntNode pHead = null; private IntNode pTail = null; //Các phương thức}Các thao tác trên DSLK đơnKiểm tra danh sách rỗngThêm 1 nút vào danh sáchDuyệt danh sáchXóa 1 nútTìm 1 phần tửSắp xếp danh sách31Kiểm tra danh sách rỗng32Danh sách rỗngpHeadpTailListpublic bool IsEmpty(){ return pHead == null;}Thêm một nút vào danh sáchTH danh sách rỗng33pHeadpTaillist30pNewpHead = pTail = pNew;Thêm một nút vào danh sáchTH danh sách đã có phần tử34pHeadpTaillist3025pNewCó 2 trường hợp để thêm pNewThêm pNew vào đầu (AddHead)Thêm pNew vào cuối (AddTail)TH Thêm một nút vào đầu danh sách35pHeadpTaillist3025pNew12TH Thêm một nút vào đầu danh sách36pHeadpTaillist3025pHeadpTaillist2530Vẽ lạiTH Thêm một nút vào đầu danh sách37pHeadpTaillist253042pNew Hãy vẽ lại “đường kết nối” theo thứ tự thích hợp khi thêm pNew vào đầu danh sách?TH Thêm một nút vào đầu danh sách381. pNew.PNext = pHead;2. pHead = pNew;TH Thêm một nút vào đầu danh sách39 Hãy viết phương thức thêm phần tử vào đầu danh sách (C#), theo mẫu sau:public void AddHead(Node pNew)?TH Thêm một nút vào cuối danh sách40pHeadpTaillist3025pNewpTail.PNext = pNewpTail = pNew1122TH Thêm một nút vào cuối danh sách41pHeadpTaillist3025 Hãy vẽ lại “đường kết nối” theo thứ tự thích hợp khi thêm pNew vào cuối danh sách?42pNewTH Thêm một nút vào cuối danh sách42 Hãy viết phương thức thêm phần tử pNew vào cuối danh sách (C#), theo mẫu: public void AddTail(Node pNew)?Nhập dữ liệu vào DSLK43Nhập dữ liệu cho nodeTạo con trỏ nodeThêm node vào danh sáchNhập dữ liệu vào danh sáchĐể tạo node mới từ dữ liệu x có sẵnĐưa dữ liệu có giá trị x vào phần dataCon trỏ pNext trỏ đến null44DatapNewxpNew.data = xpNew.pNext = nullVD nhập dữ liệu vào DSLK số nguyênTạo và trả về Node có chứa giá trị x45public class IntNode{ private int data; private IntNode pNext = null; public IntNode(int x) { data = x; pNext = null; }}Nhập dữ liệu vào DSLKVD nhập dữ liệu cho DSLK số nguyên dương và đưa vào đầu danh sách46public void Input(){ int x; do { Console.Write("Nhap vao so nguyen duong (nhap -1 ket thuc): "); int.TryParse(Console.ReadLine(), out x); if (x "); p = p.PNext; }}Bài tậpĐịnh nghĩa các phương thức cho lớp CMyIntLinkedList:Đếm số lượng node int DemSL();2. Tìm node có giá trị lớn nhất Node TimMax(); 3. Tìm node có giá trị x Node TimX(int x);4. In những node có giá trị chẵn void InChan();5. Tính giá trị trung bình cộng các node có giá trị lẻ double TBLe();49Chương trình mẫuMinh hoạ thao tác nhập vào đầu và xuất DSLK số nguyên. Chương trình gồm 3 lớp:1. Lớp IntNode: cấu trúc dữ liệu Node2. Lớp CMyIntLinkedList: cấu trúc DSLK đơn3. Lớp Program: gọi thử nghiệm50Lớp IntNode51 public class IntNode { private int data; private IntNode pNext = null; public int Data { get { return data; } set { data = value; } } public IntNode PNext { get { return pNext; } set { pNext = value; } } public IntNode(int x) { data = x; pNext=null; } }Lớp CMyIntLinkedList52 public class CMyIntLinkedList { private IntNode pHead = null; private IntNode pTail = null; public bool IsEmpty() { return pHead == null; } public void AddHead(IntNode pNew) { if (IsEmpty()) { pHead = pTail = pNew; } else { pNew.PNext = pHead; pHead = pNew; } }Lớp CMyIntLinkedList (tt)53public void Input(){ int x; do { Console.Write("Nhap vao so nguyen duong (nhap -1 ket thuc): "); int.TryParse(Console.ReadLine(), out x); if (x "); p = p.PNext; } Console.WriteLine("."); } }Lớp Program55class Program{ static void Main(string[] args) { CMyIntLinkedList intList = new CMyIntLinkedList(); intList.Input(); Console.WriteLine("Gia tri trong danh sach vua nhap:"); intList.Output(); }}Bài tập thực hànhCài đặt lớp CMyLinkedList có kiểu dữ liệu chung gồm các chức năng:Tạo nodeThêm node vào đầu DSLKThêm node vào cuối DSLKTìm node có giá trị xSử dụng lớp này cho trường hợp kiểu dữ liệu là số nguyên và thử nghiệm các chức năng: nhập, xuất, tìm kiếm56