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 (Phần 1)

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.
Nội dung trích xuất từ tài liệu:
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 (Phần 1)Bài 4: C u trúc d li ubi u di n danh sáchGi ng viên: Hoàng Th i pKhoa Công ngh Thông tin –i h c Công NghDanh 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 ư cs 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ênDanh sách i n tho iDanh sách môn h cDanh sách bài hátDanh sách công vi cdiepht@vnu2Tr u tư ng hóa danh sách•c t d li u–•c t các phép toán1.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ôngm s ph n t c a danh sáchTr v ph n tv trí th i c a danh sáchThêm ph n t x vào v trí i trong danh sáchThêm ph n t x vào uôi danh sáchLo i ph n tv trí th i trong danh sáchCác phép toán trên c u trúc danh sách không ph thu c vàoki u d li u c a các ph n t trong danh sách–diepht@vnuGeneric programming• Template trong C++3Tr u tư ng hóa danh sách•c t d li uA = (a0, a1, …, an)trong ó ai là ph n t th i c a danh sách AVí d :A = (1, 2, 3, 3, 4, 5)A = (‘Vinh’, ‘Tu n’, ‘Ánh’)•c t các phép toán1.2.3.4.5.6.diepht@vnuKi 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 tv 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 tv trí th i trong danh sách: del (A, i)4Ví d•••••••••A = (1, 2, 3, 3, 4, 5)empty(A) → falselength(A) → 6element(A, 0) → 1element(A, 2) → 3insert(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, -5)diepht@vnu5