Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 4: KDLTT danh sách cài đặt bằng mảng tính - Hoàng Thị Điệp

Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – Đại học Công Nghệ Bài 4: KDLTT danh sách cài đặt bằng mảng tĩnh Cấu trúc dữ liệu và giải thuật HKI, 2013-2014 Nội dung chính diepht@vnu2  KDLTT danh sách: đặc tả  Cài đặt bằng mảng tĩnh Danh sách  Danh sách là cấu trúc dữ liệu tuyến tính, trong đó các phần tử dữ liệu được sắp xếp theo một thứ tự xác định  Danh sách thuần nhất: các phần tử cùng một kiểu  Ví dụ  Danh sách sinh viên  Danh sách điện thoại  Danh sách môn học  Danh sách bài hát  Danh sách công việc diepht@vnu3 Trừu tượng hóa danh sách diepht@vnu4 1. Đặc tả dữ liệu  Là một dãy hữu hạn các phần tử L = (a0, a1, , an-1) 2. Đặc tả các phép toán  Kiểm tra danh sách có rỗng hay không  Đếm số phần tử của danh sách  Trả về phần tử ở vị trí thứ i của danh sách  Thêm phần tử x vào vị trí i trong danh sách  Thêm phần tử x vào đuôi danh sách  Loại phần tử ở vị trí thứ i trong danh sách  Ta muốn thiết kế lớp danh sách để người lập trình dùng lớp này có thể biểu diễn danh sách các phần tử có kiểu tùy ý  Generic programming  Template trong C++ Trừu tượng hóa danh sách diepht@vnu5 1. Đặc tả dữ liệu L = (a0, a1, , an-1) trong đó ai là phần tử thứ i+1 của danh sách L Ví dụ: L = (1, 2, 3, 3, 4, 5) L = (‘Vinh’, ‘Tuấn’, ‘Ánh’) 2. Đặc tả các phép toán  Kiểm tra danh sách có rỗng hay không: empty(L)  Đếm số phần tử của danh sách: length(L)  Trả về phần tử ở vị trí thứ i của danh sách: element(L, i)  Thêm phần tử x vào vị trí i trong danh sách: insert(L, i, x)  Thêm phần tử x vào đuôi danh sách: append(L, x)  Loại phần tử ở vị trí thứ i trong danh sách: erase(L, i) Ví dụ diepht@vnu6  L = (1, 2, 3, 3, 4, 5)  empty(L) → false  length(L) → 6  element(L, 0) → 1  element(L, 2) → 3  insert(L, 2, 10) → L = (1, 2, 10, 3, 3, 4, 5)  append(L, -5) → L = (1, 2, 10, 3, 3, 4, 5, -5)  erase(L, 3) → L = (1, 2, 10, 3, 4, 5, -5)  erase(L, 1) → L = (1, 10, 3, 4, 5, -5) Cài đặt danh sách bằng mảng diepht@vnu7  Mảng (array)  Tập hợp các phần tử (các biến) có cùng một kiểu  Một phần tử cụ thể trong mảng sẽ được xác định và truy cập bởi một chỉ số  Trong C/C++, các phần tử của mảng được đặt cạnh nhau tạo thành một khối liên tục. Địa chỉ thấp nhất tương ứng với phần tử đầu tiên, địa chỉ cao nhất tương ứng với phần tử cuối cùng  Mảng thì có thể là một chiều hoặc nhiều chiều Cài đặt danh sách bằng mảng  Mảng một chiều tĩnh int dayso[100]; Phanso dayphanso[15];  Mảng một chiều động  Cấp phát bộ nhớ bằng phép new int *daysod = new int[100]; Phanso *dayphansod = new Phanso[15];  Khi không dùng nữa, phải giải phóng bộ nhớ bằng phép delete delete [] daysod; delete [] dayphansod;  L = (a0, a1, , an-1) a0 a1 an-1 ? ? 0 1 n-1 n MAX-1 diepht@vnu8 insert(L, i, x) diepht@vnu9  Dồn tất cả các phần tử từ vị trí i tới vị trí n-1 về sau một vị trí  Sau đó đặt giá trị x vào vị trí i  Tăng số phần tử của danh sách lên 1 a0 ai-1 ai an-1 ? ? ? 0 i-1 i n-1 n n+1 MAX-1 a0 ai-1 x ai an-1 ? ? 0 i-1 i i+1 n n+1 MAX-1 erase(L, i) diepht@vnu10  Dồn tất cả các phần tử từ vị trí i+1 tới vị trí n-1 lên trước một vị trí  Giảm số phần tử của danh sách đi 1 a0 ai-1 ai ai+1 an-1 ? ? 0 i-1 i i+1 n-1 n MAX-1 a0 ai-1 ai+1 an-1 ? ? ? 0 i-1 i n-2 n-1 n MAX-1 Chuẩn bị tuần tới diepht@vnu11  Thực hành: Cài đặt KDLTT danh sách bằng mảng tĩnh  Lý thuyết: Đọc chương 4 (4.3 đến hết) và chương 5 giáo trình