Bài giảng Cấu trúc dữ liệu và giải thuật: Bài 4 - Hoàng Thị Điệp (2014)

Bài 4: KDLTT danh sách<br /> cài đặt bằng mảng tĩnh<br /> Giảng viên: Hoàng Thị Điệp<br /> Khoa Công nghệ Thông tin – Đại học Công Nghệ<br /> <br /> Cấu trúc dữ liệu và giải thuật<br /> <br /> HKI, 2013-2014<br /> <br /> Nội dung chính<br />  KDLTT danh sách: đặc tả<br />  Cài đặt bằng mảng tĩnh<br /> <br /> 2<br /> <br /> diepht@vnu<br /> <br /> Danh sách<br />  Danh sách là cấu trúc dữ liệu tuyến tính, trong đó<br /> <br /> các phần tử dữ liệu được sắp xếp theo một thứ tự<br /> xác định<br />  Danh sách thuần nhất: các phần tử cùng một kiểu<br />  Ví dụ<br />  Danh sách sinh viên<br />  Danh sách điện thoại<br />  Danh sách môn học<br />  Danh sách bài hát<br />  Danh sách công việc<br /> 3<br /> <br /> diepht@vnu<br /> <br /> Trừu tượng hóa danh sách<br /> 1.<br /> <br /> Đặc tả dữ liệu<br /> <br /> Là một dãy hữu hạn các phần tử L = (a0, a1, … , an-1)<br /> <br /> 2.<br /> <br /> Đặc tả các phép toán<br /> <br /> Kiểm tra danh sách có rỗng hay không<br /> <br /> Đếm số phần tử của danh sách<br /> <br /> Trả về phần tử ở vị trí thứ i của danh sách<br /> <br /> Thêm phần tử x vào vị trí i trong danh sách<br /> <br /> Thêm phần tử x vào đuôi danh sách<br /> <br /> Loại phần tử ở vị trí thứ i trong danh sách<br /> <br />  Ta muốn thiết kế lớp danh sách để người lập trình dùng lớp này có<br /> <br /> thể biểu diễn danh sách các phần tử có kiểu tùy ý<br />  Generic programming<br />  Template trong C++<br /> <br /> 4<br /> <br /> diepht@vnu<br /> <br /> Trừu tượng hóa danh sách<br /> <br /> 5<br /> <br /> 1.<br /> <br /> Đặc tả dữ liệu<br /> L = (a0, a1, …, an-1)<br /> trong đó ai là phần tử thứ i+1 của danh sách L<br /> Ví dụ:<br /> L = (1, 2, 3, 3, 4, 5)<br /> L = (‘Vinh’, ‘Tuấn’, ‘Ánh’)<br /> <br /> 2.<br /> <br /> Đặc tả các phép toán<br /> <br /> Kiểm tra danh sách có rỗng hay không: empty(L)<br /> <br /> Đếm số phần tử của danh sách: length(L)<br /> <br /> Trả về phần tử ở vị trí thứ i của danh sách: element(L, i)<br /> <br /> Thêm phần tử x vào vị trí i trong danh sách: insert(L, i, x)<br /> <br /> Thêm phần tử x vào đuôi danh sách: append(L, x)<br /> <br /> Loại phần tử ở vị trí thứ i trong danh sách: erase(L, i)<br /> diepht@vnu<br /> <br />