Bài giảng Cơ sở dữ liệu giải thuật: Bài 4 - Cấu trúc dữ liệu biểu diễn danh sách giới thiệu tới các bạn về danh sách, trừu tượng hóa danh sách, cài đặt danh sách bằng mảng. Bài viết hữu ích với các bạn chuyên ngành Công nghệ thông tin. | 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 – i h c 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 2 Tr u tư ng hóa danh sách • c t d li u – • c t các phép toán 1. 2. 3. 4. 5. 6. • T t c các ph n t c a danh sách s p theo th t nào ó 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 – diepht@vnu Generic programming • Template trong C++ 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) 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, .
