Bài giảng môn Cấu trúc dữ liệu chương 4: Danh sách

Môn: CẤU TRÚC DỮ LIỆU Chương 4: DANH SÁCH (LIST) NỘI DUNG CHƯƠNG 4 Khái niệm danh sách Các phép toán trên danh sách Danh sách đặc Định nghĩa Biểu diễn danh sách đặc Các thao tác trên danh sách đặc Ưu nhược điểm và ứng dụng Danh sách liên kết Định nghĩa Danh sách liên kết đơn Danh sách liên kết kép Ưu nhược điểm của danh sách liên kết Danh sách hạn chế Hàng đợi Ngăn xếp Ứng dụng của danh sách hạn chế BÀI TẬP 1. Khái niệm danh sách Danh sách a1, a2, ….aN là tập hợp các phần tử có kiểu dữ liệu xác định và giữa chúng có 1 mối quan hệ nào đó. Nếu biết phần tử ai  vị trí của phần tử ai+1 Số phần tử trong một danh sách là chiều dài của 1 danh sách. Danh sách rỗng là danh sách có chiều dài = 0 Cho T là một kiểu được định nghĩa trước, kiểu danh sách TX gồm các phần tử thuộc kiểu T được định nghĩa là: TX = Trong đó : VX = { tập hợp các thứ tự gồm một số biến động các phần tử kiểu T }. OX = { tạo danh sách; tìm 1 phần tử trong danh sách; chèn 1 phần tử vào danh sách; huỷ 1 phần tử khỏi danh sách; liệt kê danh sách, sắp xếp danh sách.}. 2. Các phép toán trên danh sách Tùy theo loại của từng danh sách sẽ có các phép toán khác nhau, các phép toán thông thường như sau: 2.1. Tạo mới 1 danh sách Đưa vào danh sách nội dung các phần tử. Chiều dài của danh sách là xác định. 2.2. Thêm 1 phần tử vào danh sách Khi thêm 1 phần tử chiều dài danh sách tăng lên. Có thao tác thêm vào đầu, cuối hay tại 1 vị trí xác định của danh sách. 2.3. Tìm kiếm 1 phần tử trong danh sách Tìm 1 phần tử trong danh sách thỏa mãn điều kiện nào đó Dùng các thuật toán tìm kiếm trong chương “Tìm kiếm” 2.4. Loại bớt 1 phần tử trong danh sách Chiều dài danh sách giảm xuống 1 phần tử Công việc loại bớt cũng bao gồm thao tác tìm kiếm ra phần tử cần hủy trong danh sách. 2. Các phép toán trên danh sách (tt) 2.5. Sửa đổi giá trị 1 phần tử trong danh sách Thay đổi thông tin của 1 phần tử trong danh sách Công việc cập nhật phần tử cũng bao gồm thao tác tìm kiếm ra phần tử cần hủy trong danh sách. 2.6. Sắp xếp danh sách Dùng các thuật toán trong chương sắp xếp. 2.7. Tách danh sách thành nhiều danh sách con Tách danh sách thành các DS con theo 1 quy luật chia nào đó Tổng chiều dài các danh sách được chia bằng chiều dài danh sách ban đầu 2.8. Nhập nhiều danh sách thành 1 danh sách Nhập các danh sách thành 1 danh sách Tổng chiều dài danh sách bằng tổng chiều dài các danh sách ban đầu Có thể ghép đuôi các danh sách hay trộn lẫn theo 1 phương pháp nhất định 2.9. Sao chép 1 danh sách: Sao chép toàn bộ nội dung của danh sách thành 1 danh sách khác. 2.10. Hủy danh sách: Huỷ nội dung hay cả vùng nhớ chứa DS 3. Danh sách đặc (Condensed List) 3.1. Định nghĩa Danh sách đặc là danh sách mà không gian bộ nhớ lưu trữ các phần tử nằm kề cận nhau trong bộ nhớ. 3.2. Biểu diễn danh sách đặc Biểu diễn danh sách đặc dùng 1mảng các phần tử có kiểu dử liệu là kiểu dữ liệu của các phần tử trong danh sách Cần biết chiều dài tối đa của một danh sách đặc thông qua 1 biến. Cần biết chiều dài thực của một danh sách đặc thông qua 1 biến. VD: #define MaxLength 1000 int RealLength; T CD_List[MaxLength] Hay: T * CD_List = new T[MaxLength] 3. Danh sách đặc (tt) 3.3. Các thao tác trên danh sách đặc Một số thao tác trên danh sách đặc được thống kê tóm tắt: 3.3.1. Khởi tạo danh sách Khởi tạo danh sách cho chiều dài danh sách trở về 0. void CD_Initialize(int &Len) { Len = 0; return; } 3. Danh sách đặc (tt) 3.3. Các thao tác trên danh sách đặc (tt) 3.3.2. Tạo danh sách mới & nhập danh sách Tạo danh sách mới có chiều dài tối đa MaxLen, hàm trả về giá trị thực của danh sách mới được tạo. int CD_Create_List(T M[], int &Len) { if (Len > MaxLen) Len = MaxLen; for (int I = 0; iInsPos; I++) M[I] = M[I-1]; M[InsPos] = NewValue; Len++; return (Len); } 3. Danh sách đặc (tt) 3.3. Các thao tác trên danh sách đặc (tt) 3.3.4. Tìm kiếm 1 phần tử trong danh sách Dùng các thuật toán tìm kiếm tìm phần tử thỏa mãn điều kiện trong danh sách Tìm kiếm tuyến tính Tìm nhị phân 3. Danh sách đặc (tt) 3.3. Các thao tác trên danh sách đặc (tt) 3.3.5. Hủy 1 phần tử trong danh sách Loại bỏ phần tử có vị trí DelPosition trong danh sách M có chiều dài Length (có thể có thao tác tìm kiếm xác định vị trí xóa phần tử) Thuật toán: B1: IF(Length =0 OR DelPos > Len) Thực hiện BKT B2: Pos = DelPos B3: IF(Pos = Length) Thực hiện B7 B4: M[Pos] = M[Pos+1] B5: Pos++ B6: Lặp lại B3 B7: Length-- BKT: Kết thúc 3. Danh sách đặc (tt) 3.3. Các thao tác trên danh sách đặc (tt) 3.3.5. Hủy 1 phần tử trong danh sách (tt) int CD_Delete_Element(T M[], int &Len, int DelPos) { int (Len ==0 || DelPos >=Len) return (-1); for (int I =DelPos; i= Len) SLen1 = Len SLen2 = 0 B2:IF(SLen2 >= Len) SLen2 = Len SLen1 = 0 B3: IF(SLen1 + SLen2 Len) SLen2 = Len – SLen1 B4: IF (SLen1 SLen1) Thực hiện B11 B8: SM[SI] = M[I] B9: I++, SI++ B10: Lặp lại B7 B11: SI = 1 B12: IF(I > Len) Thực hiện BKT B13: SM2[SI] = M[I] B14: I++, SI++ B15: Lặp lại B12 BKT: Kết thúc 3. Danh sách đặc (tt) 3.3. Các thao tác trên danh sách đặc (tt) 3.3.8. Tách 1 danh sách thành nhiều danh sách (tt) void CS_Split(T M[], int Len, T SM1[], int &SLen1, T SM2[], int &SLen2) { int (Slen1 >=Len) { SLen1 = Len; Slen2 = 0; } int (Slen2 >=Len) { SLen2 = Len; SLen1 = 0; } if (SLen1 MaxLen) // M không đủ khả năng chứa Thực hiện BKT B2: I = 1 // Chép từ SM1[] vào M[] B3: IF (I > SLen1) Thực hiện B7 B4: M[I] = SM[I] B5: I++ B6: Lặp lại B3 B7: SI = 1 // Chép từ SM2[] vào M[] B8: IF (SI > SLen2) Thực hiện BKT B9: M[I] = SM[SI] B10: I++; SI++ B11: Lặp lại B8 BKT: Kết thúc 3. Danh sách đặc (tt) 3.3. Các thao tác trên danh sách đặc (tt) 3.3.9. Nhập nhiều danh sách thành 1 danh sách(tt) int CD_Concat(T SM1[], int SLen1, T SM2[], int SLen2, T M [], int &Len) { if (SLen1+SLen2 > MaxLen) return (-1); for (int I = 0; I Length) // Length là chiều dài của dãy B3: CM[I] = M[I] B4: I++ B5: Lặp lại B2 BKT: Kết thúc int CD_Copy(T M[], int Len, T CM[]) // Hàm trả về chiều dài của DS { for (int i=0; iNextNode = NULL; B4: First ->Key = NewData BKT: Kết thúc 4.2. Danh sách liên kết đơn (tt) 4.2.2. b. Tạo mới 1 phần tử (nút) trong danh sách SLL (tt) Cài đặt Prototype: SLLType SLLCreateNode(T NewData) SLLType SLLCreateNode(T NewData) { SLLType Pnode = New SLLOneNode; if (Pnode != NULL) { Pnode ->NextNode = NULL; Pnode ->Key = NewData; } return Pnode; } 4.2. Danh sách liên kết đơn (tt) 4.2.2.c. Thêm 1 phần tử vào danh sách SLL (Thêm đầu DS) Thuật toán B1: NewNode = SLLCreateNode(NewData) B2: If (NewNode == NULL) Thực hiện BKT B3: NewNode->NextNode = SSList B4: SLList = NewNode BKT: Kết thúc 4.2. Danh sách liên kết đơn (tt) 4.2.2.c. Thêm 1 phần tử vào danh sách SLL (Thêm đầu DS) (tt) Cài đặt SLLType SLLAddFirst (SLLType &SList, T NewData) { SLLType NewNode = SLLCreateNode(NewData); if (NewNode == NULL) return (NULL); NewNode->NextNode = SList; SList = NewNode; return (SList); } 4.2. Danh sách liên kết đơn (tt) 4.2.2.c. Thêm 1 phần tử vào danh sách SLL (tt) (Thêm giữa DS) Thêm phần tử mới vào ngay sau nút có địa chỉ InsNode. Thuật toán B1: NewNode = SLLCreateOneNode(NewData) B2: IF (NewNode == NULL) Thực hiện BKT B3: IF(InsNode ->NextNode == NULL) B3.1: InsNode->NextNode = NewNode B3.2: Thực hiện BKT B4: NewNode->NextNode = InsNode->NextNode B5: InsNode->NextNode = NewNode BKT: Kết thúc 4.2. Danh sách liên kết đơn (tt) 4.2.2.c. Thêm 1 phần tử vào danh sách SLL (Thêm giữa DS) (tt) SLLType SLLAddLast (SLLType &SList, T NewData) { SLLType NewNode = SLLCreateNode(NewData); if (NewNode == NULL) return (NULL); if (SList == NULL) { SList = NewNode; return (SList); } SLLType CurrNode = SList; while (CurrNode->NextNode != NULL) CurrNode = CurrNode-> NextNode; CurrNode-> NextNode = NewNode; return (SList); } 4.2. Danh sách liên kết đơn (tt) 4.2.2.c. Thêm 1 phần tử vào danh sách SLL (Thêm cuối DS) B1: NewNode = SLLCreateNode(NewData) B2: IF(NewNode == NULL) Thực hiện BKT B3:IF (SLList == NULL) B3.1: SLList = NewNode B3.2: Thực hiện BKT B4: CurrNode = SLList B5: IF(CurrNode->NextNode == NULL) Thực hiện B8 B6: CurrNode = CurrNode -> NextNode B7: Lặp lại B5 B8: CurrNode->NextNode = NewNode BKT: Kết thúc 4.2. Danh sách liên kết đơn (tt) 4.2.2.c. Thêm 1 phần tử vào danh sách SLL (Thêm cuối DS) (tt) Cài đặt SLLType SLLAddMid (SLLType &SList, T NewData, SLLType &InsNode) { SLLType NewNode = SLLCreateNode(NewData); if (NewNode == NULL) return (NULL); if (InsNode->NextNode == NULL) { InsNode->NextNode = NewNode; return (SList); } NewNode-> NextNode = InsNode->NextNode; InsNode-> NextNode = NewNode; return (SList); } 4.2. Danh sách liên kết đơn (tt) 4.2.2.d. Duyệt qua các nút trong danh sách liên kết đơn Là thao tác thường dùng trong các loại danh sách. Tùy theo từng trường hợp cụ thể để xử lý trong khi duyệt DS. Thuật toán: B1: CurrNode = SLList B2: IF (CurrNode == NULL) Thực hiện BKT B3: OutputData(CurrNode->Key) B4: CurrNode = CurrNode->NextNode B5: Lặp lại B2 BKT: Kết thúc 4.2. Danh sách liên kết đơn (tt) 4.2.2.d. Duyệt qua các nút trong danh sách liên kết đơn (tt) Cài đặt: void SLLTravelling(SLLType SList) { SLLType CurrNode = SList; while (CurrNode != NULL) { OutputData(CurrNode->Key); CurrNode = CurrNode->NextNode; } return; } // Tùy theo từng trường hợp cụ thể, hàm OutputData được xử lý khác nhau 4.2. Danh sách liên kết đơn (tt) 4.2.2.e. Tìm kiếm phần tử trong danh sách Giả sử cần tìm kiếm trong danh sách liên kết đơn phần tử có phần dữ liệu SearchData. Dùng thuật toán tìm tuyến tính. Thuật toán B1: CurrNode = SLList B2: IF(CurrNode == NULL OR CurrNode->Key == SearchData) Thực hiện BKT B3: CurrNode = CurrNode->NextNode B4: Lặp lại B2 BKT: Kết thúc 4.2. Danh sách liên kết đơn (tt) 4.2.2.e. Tìm kiếm phần tử trong danh sách (tt) Cài đặt SLLType SLLSearching (SLLType &SList, T SearchData) { SLLType CurrNode = SList; while (CurrNode != NULL) { if (CurrNode->Key == SearchData) break; CurrNode = CurrNode-> NextNode; } return (CurrNode); } 4.2. Danh sách liên kết đơn (tt) 4.2.2.f. Hủy bỏ 1 phần tử trong danh sách Loại bỏ phần tử (nút) có thành phần dữ liệu là DelData trong danh sách liên kết đơn. Gồm 2 thao tác: tìm phần tử có thành phần dữ liệu là DelData và loại bỏ phần tử này. (Trong quá trình tìm kiếm cần lưu trữ thành phần trước đó PreDelData) B1: DelNode = SLList // Tìm kiếm phần tử có Key = DelData B2: PreDelNode = NULL B3: IF (DelNode == NULL) Thực hiện BKT B4: IF (DelNode->Key == DelData) Thực hiện B8 B5: PreDelNode = DelNode B6: DelNode = DelNode->NextNode B7: Lặp lại B3 B8: IF (PreDelNode == NULL) // Loại bỏ phần tử đầu tiên trong DS B8.1: SLList = SLList->NextNode B8.2: Thực hiện B10 B9: PreDelNode->NextNode = DelNode->NextNode // Liên kết các nút sau DelNode về PreDelNode B10: DelNode->NextNode = NULL // Cắt mối liên kết của DelNode với các nút còn lại B11: delete DelNode // Hủy DelNode BKT: Kết thúc 4.2. Danh sách liên kết đơn (tt) 4.2.2.f. Hủy bỏ 1 phần tử trong danh sách (tt) Cài đặt thuật toán trong C++ (Hàm trả về giá trị 1 nếu hủy thành công) int SLLDeleteNode(SLLType &SList, T DelData) { SLLType DelNode = SList; SLLType PreDelNode = NULL; while (DelNode != NULL) { if (DelNode->Key = DelData) break; PreDelNode = DelNode; DelNode = DelNode->NextNode; } if (DelNode == NULL) return (-1); if (PreDelNode == NULL) SList = SList->NextNode; else PreDelNode->NextNode = DelNode->NextNode; DelNode->NextNode = NULL; delete DelNode; return (1); } 4.2. Danh sách liên kết đơn (tt) 4.2.2.g. Hủy danh sách Việc hủy danh sách thực chất là thực hiện nhiều lần hủy 1 nút Thuật toán: B1: IF (SLList = NULL) Thực hiện BKT; B2: TempNode = SLList B3: SLList = SLList->NextNode B4: TempNode->NextNode = NULL; B5: delete TempNode B6: Lặp lại B1; BKT: Kết thúc 4.2. Danh sách liên kết đơn (tt) 4.2.2.g. Hủy danh sách (tt) Cài đặt thuật toán: void SLLDelete (SLLType &SList) { SLLType TempNode = SList; while (SList != NULL) { SList = SList ->NextNode; TempNode ->NextNode = NULL; delete TempNode; TempNode = Slist; } return; } 4.2. Danh sách liên kết đơn (tt) 4.2.2.h. Tạo mới danh sách/Nhập danh sách Tạo mới 1 danh sách thực chất là liên tục thêm 1 phần tử vào danh sách mà danh sách ban đầu là rỗng. Có thể dùng lại các hàm SLLAddFirst, SLLAddMid, SLLAddLast B1: SLLInitialize (SLList) B2: I = 1 B3: IF (I > N) Thực hiện BKT; B4: NewData = InputNewData(); B5: SLLAddFirst(SLList, NewData) B6: I++ B7: Lặp lại B3 BKT: Kết thúc 4.2. Danh sách liên kết đơn (tt) 4.2.2.h. Tạo mới danh sách/Nhập danh sách (tt) Cài đặt SLLType SLLCreate(SLLType &SList, int N) { SLLInitialize(SList); T NewData; for (int I = 0; IKey) B5: CurrNode = CurrNode->NextNode B6: Lặp lại B3 BKT: Kết thúc 4.2. Danh sách liên kết đơn (tt) 4.2.2.h. Sao chép 1 danh sách (tt) Cài đặt thuật toán: SLLType SLLCopy(SLLType SList, SLLType &NewList) { NewList = NULL; SLLType CurrNode = SList; while (CurrNode != NULL) { SLLType NewNode=SLLAddLast(NewList,CurrNode->Key); if (NewNode == NULL) { SLLDelete(NewList); break; } } return (NewList); } 4.3. Danh sách liên kết đôi (DLL) Các phần tử của danh sách liên kết đôi có 2 mối liên kết với các phần tử khác trong danh sách. Cấu trúc dữ liệu của danh sách liên kết đôi: typedef struct DLLNode { T Key; InfoType Info; DLLNode * NextNode; DLLNode * PreNode; } DLLOneNode; typedef struct DLLNode { T Key; DLLNode * NextNode; DLLNode * PreNode; } DLLOneNode; typedef DLLOneNode * DLLType; 4.3. Danh sách liên kết đôi (tt) 4.3.1. Quản lý danh sách liên kết liên kết đôi: Quản lý địa chỉ phần tử đầu của danh sách DLLType DLList1 Quản lý địa chỉ phần tử đầu và phần tử cuối của danh sách typedef struct DLLPairNode { DLLType DLLFirst; DLLType DLLLast; } DLLPType; DLLPType DLList2; Quản lý địa chỉ phần tử đầu, phần tử cuối và số phần tử của danh sách typedef struct DLLPairNode { DLLType DLLFirst; DLLType DLLLast; unsigned NumNode; } DLLPNType; DLLPNType DLList3; 4.3. Danh sách liên kết đôi (tt) 4.3.2. Thao tác trên danh sách liên kết đôi Khởi tạo danh sách liên kết đôi Tạo mới 1 phần tử Thêm 1 phần tử vào danh sách Duyệt qua các nút trong 1 danh sách Tìm kiếm 1 phần tử trong danh sách Loại bỏ 1 phần tử trong danh sách Hủy toàn bộ danh sách Tạo 1 danh sách mới/Nhập danh sách Tách 1 danh sách thành nhiều danh sách Nhập nhiều danh sách thành 1 danh sách Sắp xếp thứ tự thành phần dữ liệu trong danh sách Sao chép 1 danh sách thành 1 danh sách mới 4.3. Danh sách liên kết đôi (tt) 4.3.2.a. Khởi tạo danh sách liên kết đôi Cho giá trị các con trỏ quản lý địa chỉ 2 nút đầu và cuối danh sách liên kết đôi về NULL DLLPType DLLInitialize(DLLPType &DList) { DList.DLLFirst = NULL; DList.DLLast = NULL; return (DList); } 4.3. Danh sách liên kết đôi (tt) 4.3.2.b. Tạo mới 1 phần tử Tạo nút mới có thành phần dữ liệu là NewData Thuật toán B1: Dnode = New DLLOneNode B2: IF (Dnode == NULL) Thực hiện BKT B3: DNode ->NextNode = NULL B4: DNode ->Key = NewData B5: DNode ->PreNode = NULL BKT: Kết thúc DLLType DLLCreateNode(T NewData) { DLLType Pnode = new DLLOneNode; if (Pnode != NULL) { Pnode ->NextNode = NULL; Pnode ->Key = NewData Pnode ->PreNode = NULL; } return (Pnode); } 4.3. Danh sách liên kết đôi (tt) 4.3.2.c. Thêm 1 phần tử vào danh sách (Thêm đầu) B1: NewNode = DLLCreateNode(NewData) B2: IF (NewNode == NULL) Thực hiện BKT B3: IF(DLLList.DLLFirst == NULL) B3.1: DLLList.DLLFirst = NewNode B3.2: DLLList.DLLLast = NewNode B3.3: Thực hiện BKT B4: NewNode ->NextNode = DLLList.DLLFirst B5: DLLList.DLLFirst ->PreNode = NewNode // chuyển vai trò đứng đầu của NewNode cho DLLFirst B6: DLLList.DLLFirst = NewNode BKT: Kết thúc 4.3. Danh sách liên kết đôi (tt) 4.3.2.c. Thêm 1 phần tử vào danh sách (Thêm đầu) DLLType DLLAddFirst(DLLPType &DList, T NewData) { DLLType NewNode = DLLCreateNode(NewData); if (NewNode == NULL) return (NULL); if (DList.DLLFirst == NULL) DList.DLLFirst = DList.DLLLast = NewNode; else { NewNode ->NextNode = DList.DLLFirst; DList.DLLFirst ->PreNode = NewNode; DList.DLLFirst = NewNode; } return (NewNode); } 4.3. Danh sách liên kết đôi (tt) 4.3.2.c. Thêm 1 phần tử vào danh sách (Thêm cuối) B1: NewNode = DLLCreateNode(NewData) B2: IF (NewNode == NULL) Thực hiện BKT B3: IF(DLLList.DLLFirst == NULL) B3.1: DLLList.DLLFirst = NewNode B3.2: DLLList.DLLLast = NewNode B3.3: Thực hiện BKT B4: DLLList.DLLLast ->NextNode = NewNode B5: NewNode ->PreNode = DLLList.DLLLast // chuyển vai trò đứng đầu của NewNode cho DLLFirst B6: DLLList.DLLLast = NewNode BKT: Kết thúc 4.3. Danh sách liên kết đôi (tt) 4.3.2.c. Thêm 1 phần tử vào danh sách (Thêm cuối) DLLType DLLAddLast(DLLPType &DList, T NewData) { DLLType NewNode = DLLCreateNode(NewData); if (NewNode == NULL) return (NULL); if (DList.DLLLast == NULL) DList.DLLFirst = DList.DLLLast = NewNode; else { DList.DLLLast ->NextNode = NewNode; NewNode ->PreNode = DList.DLLLast; DList.DLLLast = NewNode; } return (NewNode); } 4.3. Danh sách liên kết đôi (tt) 4.3.2.c. Thêm 1 phần tử vào danh sách (Thêm giữa) B1: IF (InsNode ->NextNode == NULL) B1.1: DLLAddLast(DLLList, NewData) B1.2: Thực hiện BKT B2: NewNode = DLLCreateNode(NewData) B3: IF (NewNode == NULL) Thực hiện BKT B4: NewNode ->NextNode = InsNode ->NextNode B5: InsNode ->NextNode ->PreNode = NewNode B6: InsNode ->NextNode = NewNode B7: NewNode ->PreNode = InsNode BKT: Kết thúc 4.3. Danh sách liên kết đôi (tt) 4.3.2.c. Thêm 1 phần tử vào danh sách (Thêm giữa) DLLType DLLAddMid(DLLPType &DList, T NewData, DLLType &InsNode) { DLLType NewNode = DLLCreateNode(NewData); if (NewNode == NULL) return (NULL); if (InsNode ->NextNode == NULL) { InsNode ->NextNode = NewNode; NewNode ->PreNode = InsNode; DList.DLLLast = NewNode; } else { NewNode ->NextNode = InsNode ->NextNode; InsNode ->NextNode ->PreNode = NewNode; InsNode ->NextNode = NewNode; NewNode ->PreNode = InsNode; } return (NewNode); } 4.3. Danh sách liên kết đôi (tt) 4.3.2.d. Duyệt qua các nút trong 1 danh sách Thuật toán B1: CurrNode = DLLList.First B2: IF (CurrNode == NULL) Thực hiện BKT B3: OutputData(CurrNode->Key) B4: CurrNode = CurrNode ->NextNode B5: Lặp lại B2 BKT: Kết thúc Cài đặt thuật toán void DLLTravelling (DLLPType DList) { DLLType CurrNode = DList.DLLFirst; while (CurrNode != NULL) { OutputData(CurrNode->Key); CurrNode = CurrNode ->NextNode ; } return; } 4.3. Danh sách liên kết đôi (tt) 4.3.2.e. Tìm kiếm 1 phần tử trong danh sách Thuật toán B1: CurrNode = DLLList.First B2: IF (CurrNode == NULL OR CurrNode->Key = SearchData) Thực hiện BKT B3: CurrNode = CurrNode ->NextNode B4: Lặp lại B2 BKT: Kết thúc Cài đặt thuật toán DLLType DLLSearching(DLLPType Dlist, T SearchData) { DLLType CurrNode = DList.DLLFirst; while (CurrNode != NULL) { if (CurrNode->Key == SearchData) break; CurrNode = CurrNode ->NextNode } return (CurrNode); } 4.3. Danh sách liên kết đôi (tt) 4.3.2.f. Loại bỏ 1 phần tử trong danh sách Thuật toán B1: DelNode = DLLSearching(DLLList. DelData) // Tìm kiếm nút DelData B2: IF(DelNode == NULL) Thực hiện BKT B3: IF(DelNode->PreNode=NULL AND DelNode->NextNode=NULL) B3.1: DLLList.DLLFirst = DLLList.DLLLast = NULL B3.2: Thực hiện B8 B4: IF (DelNode ->PreNode = NULL) // Loại nút đầu tiên trong DS B4.1: DLLList.DLLFirst = DLLList.DLLFirst ->NextNode B4.2: DLLList.DLLFirst ->PreNode = NULL B4.3: Thực hiện B8 B5: IF (DelNode ->NextNode = NULL) // Loại nút cuối trong DS B4.1: DLLList.DLLLast = DLLList.DLLLast ->PreNode B4.2: DLLList.DLLLast ->NextNode = NULL B4.3: Thực hiện B8 // Liên kết giữa nút trước và sau nút bị xóa B6: DelNode ->PreNode ->NextNode = DelNode ->NextNode B7: DelNode ->NextNode ->PreNode = DelNode ->PreNode // Bỏ mối liên kết giữa DelNode giữa 2 nút trước & sau B8: DelNode ->NextNode = DelNode ->PreNode = NULL B9: delete DelNode BKT: Kết thúc 4.3. Danh sách liên kết đôi (tt) 4.3.2.f. Loại bỏ 1 phần t