tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Bài 4 - Hoàng Thị Điệp
Bài giảng "Cấu trúc dữ liệu và giải thuật - Bài 4: Cấu trúc dữ liệu biểu diễn danh sách" cung cấp cho người học các kiến thức: Danh sách, trừu tượng hóa danh sách, cài đặt danh sách bằng mảng,. nội dung chi tiết. | HK I, 2012-2013 Bài 4: Cấu trúc dữ liệu biểu diễn danh sách Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – ĐH Công Nghệ Danh sách • Danh sách là gì? – 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 – Là một tập sắp thứ 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@vnu INT2203/w03 2 Trừu tượng hóa danh sách • Đặc tả dữ liệu – • Tất cả các phần tử của danh sách sắp theo thứ tự nào đó Đặc tả các phép toán 1. 2. 3. 4. 5. 6. 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 • Các phép toán trên cấu trúc danh sách không phụ thuộc vào kiểu dữ liệu của các phần tử trong danh sách – Generic programming • Template trong C++ diepht@vnu INT2203/w03 3 Trừu tượng hóa danh sách • Đặc tả dữ liệu A = (a0, a1, , an) trong đó ai là phần tử thứ i của danh sách A Ví dụ: A = (1, 2, 3, 3, 4, 5) A = (‘Vinh’, ‘Tu ấn’, ‘Ánh’) • Đặc tả các phép toán 1. 2. 3. 4. 5. 6. diepht@vnu Kiểm tra danh sách có rỗng hay không: empty(A) Đếm số phần tử của danh sách: length(A) Trả về phần tử ở vị trí thứ i của danh sách: element(A, i) Thêm phần tử x vào vị trí i trong danh sách: insert(A, i, x) Thêm phần tử x vào đuôi danh sách: append(A, x) Loại phần tử ở vị trí thứ i trong danh sách: del (A, i) INT2203/w03 4 Ví dụ • • • • • • • • • A = (1, 2, 3, 3, 4, 5) empty(A) → false length(A) → 6 element(A, 0) → 1 element(A, 2) → 3 insert(A, 2, 10) → A = (1, 2, 10, 3, 3, 4, 5) append(A, -5) → A = (1, 2, 10, 3, 3, 4, 5, -5) del(A, 3) → A = (1, 2, 10, 3, 4, 5, -5) del(A, 1) → A = (1, 10, 3, 4, 5, .
đang nạp các trang xem trước
