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

Bài giảng môn "Cấu trúc dữ liệu - Chương 4: Danh sách (list)" có cấu trúc gồm 5 phần cung cấp cho người học các kiến thức: Khái niệm danh sách, các phép tính toán trên danh sách, danh sách đặc, danh sách liên kết, danh sách hạn chế. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng môn Cấu trúc dữ liệu - Chương 4: Danh sách (list) Chương 4: DANH SÁCH (LIST) 77 78 NỘI DUNG CHƯƠNG 4 1. Khái niệm danh sách 2. Các phép toán trên danh sách 3. 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 4. 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 5. Danh sách hạn chế • Hàng đợi • Ngăn xếp • Ứng dụng của danh sách hạn chế 79 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 = < 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.}. 80 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” 81 2. Các phép toán trên danh sách 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.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. 82 2. Các phép toán trên danh sách 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 83 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] 84 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; } 85 3. Danh sách đặc 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; i< Len;I++) M[I] = InputOneElement(); return (Len); } T InputOneElement() { …} 86 3. Danh sách đặc 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 Thê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í InsPos B1: IF (Length = MaxLen) Thực hiện BKT B2: Pos = Length+1 B3: IF(Pos = InsPos) Thực hiện B7 B4: M[Pos] = M[Pos -1] B5: Pos-- B6: Lặp lại B3 B7:M[InsPos] = NewValue B8: Length++ BKT: Kết thúc 87 3. Danh sách đặc 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); } 88 3. Danh sách đặc 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 89 ...