Danh sách đặc là danh sách có đặc tính gì?

1Môn: CẤU TRÚC DỮ LIỆUChương 4: DANH SÁCH (LIST) 2NỘI DUNG CHƯƠNG 41. Khái niệm danh sách2. Các phép toán trên danh sách3. 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ụng1. 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ết1. 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 31. 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 = < VX , OX >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.}. 42. Các phép toán trên danh sáchTù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. 52. 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 đầu2.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 định2.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 63. 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 1000int RealLength;T CD_List[MaxLength]Hay: T * CD_List = new T[MaxLength] 73. Danh sách đặc (tt)3.3. Các thao tác trên danh sách đặcMộ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áchKhở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;} 83. 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áchTạ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; i< Len;I++)M[I] = InputOneElement();return (Len);}T InputOneElement(){ …} 93. Danh sách đặc (tt)3.3. Các thao tác trên danh sách đặc (tt)3.3.3. Thêm 1 phần tử vào danh sáchThêm 1 phần tử có giá trị NewValue vào trong danh sách có chiều dài Length tại vị trí InsPosB1: IF (Length = MaxLen)Thực hiện BKTB2: Pos = Length+1B3: IF(Pos = InsPos)Thực hiện B7B4: M[Pos] = M[Pos -1]B5: Pos--B6: Lặp lại B3B7:M[InsPos] = NewValueB8: Length++BKT: Kết thúc 103. Danh sách đặc (tt)3.3. Các thao tác trên danh sách đặc (tt)3.3.3. Thêm 1 phần tử vào danh sách (tt)int CD_InsertElement(T M[], int &Len, T NewValue, int InsPos){if (Len == MaxLen)return (-1);for (int I = Len; I >InsPos; I++)M[I] = M[I-1];M[InsPos] = NewValue;Len++;return (Len);} 113. 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áchDù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 123. 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 BKTB2: Pos = DelPosB3: IF(Pos = Length)Thực hiện B7B4: M[Pos] = M[Pos+1]B5: Pos++B6: Lặp lại B3B7: Length--BKT: Kết thúc 133. 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; i++)M[i] = M[i+1];Len --;return (Len);} 143. Danh sách đặc (tt)3.3. Các thao tác trên danh sách đặc (tt)3.3.6. Sửa đổi giá trị cho 1 phần tử trong danh sáchGiả sử phần tử trong danh sách được thay đổi ở tại vị trí Position trong danh sách M có chiều dài Length. Thao tác sửa đổi là thao tác tìm kiếm phần tử cần có vị trí (hay giá trị) và gán giá trị mớiM[Pos] = NewValue; 153. Danh sách đặc (tt)3.3. Các thao tác trên danh sách đặc (tt)3.3.7. Sắp xếp thứ tự phần tử trong danh sáchDùng các thuật toán sắp xếp nội Giải thuật sắp xếp nổi bọt (Bubble Sort)Giải thuật sắp xếp dựa trên phân hoạch (Quick Sort)Giải thuật sắp xếp chọn trực tiếp (Straight Selection Sort)Giải thuật sắp xếp chèn trực tiếp (Straight Insertion Sort)Giải thuật sắp xếp trộn trực tiếp (Straight Merge Sort)Giải thuật sắp xếp trộn tự nhiên (Natural Merge Sort) 163. 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áchCó nhiều thao tác tách 1 danh sách thành nhiều danh sách:Phân phối luân phiên theo đường chạy (distribute)Phân phối từng phần của danh sách thành các danh sách conTách các phần tử thỏa mãn điều kiện cho trước thành các danh sách con.Giả sử cần tách danh sách M có chiều dài Length thành các danh sách con SM1, SM2 có chiều dài tương ứng là Slen1 và SLen2 173. 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)B1: IF(SLen1 >= Len)SLen1 = LenSLen2 = 0B2:IF(SLen2 >= Len)SLen2 = LenSLen1 = 0B3: IF(SLen1 + SLen2 <> Len) SLen2 = Len – SLen1B4: IF (SLen1 < 0) SLen1 = 0B5: IF (SLen2 < 0) SLen2 = 0B6: I =1, SI = 1B7: IF (I > SLen1) Thực hiện B11B8: SM[SI] = M[I]B9: I++, SI++B10: Lặp lại B7B11: SI = 1B12: IF(I > Len) Thực hiện BKTB13: SM2[SI] = M[I]B14: I++, SI++B15: Lặp lại B12BKT: Kết thúc 183. 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 < 0) SLen1 = 0; if (SLen2 < 0) SLen2 = 0; if (SLen1 + SLen2 != Len) SLen2 = Len - SLen1;for (int i=0; i<SLen1; i++) SM1[i] = M[i];for (int j=0; j<SLen1; i++, j++) SM1[j] = M[i]; return;} 193. 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áchCác cách nhập danh sách:Ghép nối đuôi các danh sách thành danh sách mới có chiều dài là tổng chiều dài các danh sách.Trộn xen kẽ các phần tử trong danh sách con theo 1 quy luật nào đó thành 1 danh sách mới (dùng thuật toán merge trong merge sort)Giả sử cần ghép danh sách SM1, SM2 có chiều dài SLen1, SLen2 thành danh sách M có chiều dài Len = SLen1+SLen2 theo thứ tự từ SM1 đến hết SM2 203. 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)Thuật toán:B1: IF (Slen1+SLen2 > MaxLen) // M không đủ khả năng chứaThực hiện BKTB2: I = 1 // Chép từ SM1[] vào M[]B3: IF (I > SLen1) Thực hiện B7B4: M[I] = SM[I]B5: I++B6: Lặp lại B3B7: SI = 1 // Chép từ SM2[] vào M[]B8: IF (SI > SLen2) Thực hiện BKTB9: M[I] = SM[SI]B10: I++; SI++B11: Lặp lại B8BKT: Kết thúc 213. 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 < SLen1; I++)M[I] = SM1[I];for (int J = 0; J < SLen2; I++, J++)M[I] = SM1[J];Len = SLen1+ SLen2;return (Len);} 223. Danh sách đặc (tt)3.3. Các thao tác trên danh sách đặc (tt)3.3.10. Sao chép 1 danh sách: Sao chép nội dung danh sách thành 1 danh sách khác có cùng chiều dàiThuật toánB1: I = 1B2: IF (I > Length) // Length là chiều dài của dãyB3: CM[I] = M[I]B4: I++B5: Lặp lại B2BKT: Kết thúcint CD_Copy(T M[], int Len, T CM[]) // Hàm trả về chiều dài của DS{ for (int i=0; i< Len; i++)CM[i] = M[i];return (Len)} 233. Danh sách đặc (tt)3.3. Các thao tác trên danh sách đặc (tt)3.3.11. Hủy danh sáchNếu danh sách được cấp phát động  dùng toán tử delete để hủy.Nếu danh sách được cấp phát tĩnh, việc hủy bỏ chỉ có tác dụng đưa chiều dài danh sách về 0, việc thu hồi bộ nhớ sẽ do ngôn ngữ lập trình thực hiện 243. Danh sách đặc (tt)3.4. Ưu nhược điểm và ứng dụngDo phần tử được lưu trữ kề cập với nhau trong bộ nhớ, danh sách đặc có các ưu điểm:Mật độ sử dụng danh sách là tối ưu tuyệt đối.Truy cập, tìm kiếm các phần tử là dễ dàng vì vị trí các phần tử liền kề với nhau trong bộ nhớ.Nhược điểm của danh sách là khi thêm hay hủy 1 phần tử trong danh sách cần dịch chuyển các phần tử còn lại qua vị trí khác.Được ứng dụng nhiều trong cấu trúc dữ liệu mảng (mảng 1 chiều, mảng nhiều chiều, mảng cấp phát tĩnh, mảng cấp phát động). 254. Danh sách liên kết (Linked List)4.1. Định nghĩa4.2. Danh sách liên kết đơn (Simply Linked List)4.3. Danh sách liên kết kép (Doubly Linked List)4.4. Ưu nhược điểm của danh sách liên kết