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 u<br /> bi u di n danh sách<br /> Gi ng viên: Hoàng Th i p<br /> Khoa Công ngh Thông tin –<br /> i h c Công Ngh<br /> <br /> Danh sách<br /> • Danh sách là gì?<br /> – Là c u trúc d li u tuy n tính, trong ó các ph n t d li u ư c<br /> s p x p theo m t th t xác nh<br /> – Là m t t p s p th t các ph n t cùng m t ki u<br /> <br /> • Ví d<br /> –<br /> –<br /> –<br /> –<br /> –<br /> <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 /> <br /> diepht@vnu<br /> <br /> 2<br /> <br /> Tr u tư ng hóa danh sách<br /> •<br /> <br /> c t d li u<br /> –<br /> <br /> •<br /> <br /> c t các phép toán<br /> 1.<br /> 2.<br /> 3.<br /> 4.<br /> 5.<br /> 6.<br /> <br /> •<br /> <br /> T t c các ph n t c a danh sách s p theo th t nào ó<br /> Ki m tra danh sách có r ng hay không<br /> m s ph n t c a danh sách<br /> Tr v ph n t<br /> v trí th i c a danh sách<br /> Thêm ph n t x vào v trí i trong danh sách<br /> Thêm ph n t x vào uôi danh sách<br /> Lo i ph n t<br /> v trí th i trong danh sách<br /> <br /> Các phép toán trên c u trúc danh sách không ph thu c vào<br /> ki u d li u c a các ph n t trong danh sách<br /> –<br /> <br /> diepht@vnu<br /> <br /> Generic programming<br /> • Template trong C++<br /> <br /> 3<br /> <br /> Tr u tư ng hóa danh sách<br /> •<br /> <br /> c t d li u<br /> A = (a0, a1, …, an)<br /> trong ó ai là ph n t th i c a danh sách A<br /> Ví d :<br /> A = (1, 2, 3, 3, 4, 5)<br /> A = (‘Vinh’, ‘Tu n’, ‘Ánh’)<br /> <br /> •<br /> <br /> c t các phép toán<br /> 1.<br /> 2.<br /> 3.<br /> 4.<br /> 5.<br /> 6.<br /> <br /> diepht@vnu<br /> <br /> Ki m tra danh sách có r ng hay không: empty(A)<br /> m s ph n t c a danh sách: length(A)<br /> Tr v ph n t<br /> v trí th i c a danh sách: element(A, i)<br /> Thêm ph n t x vào v trí i trong danh sách: insert(A, i, x)<br /> Thêm ph n t x vào uôi danh sách: append(A, x)<br /> Lo i ph n t<br /> v trí th i trong danh sách: del (A, i)<br /> 4<br /> <br /> Ví d<br /> •<br /> •<br /> •<br /> •<br /> •<br /> •<br /> •<br /> •<br /> •<br /> <br /> A = (1, 2, 3, 3, 4, 5)<br /> empty(A) → false<br /> length(A) → 6<br /> element(A, 0) → 1<br /> element(A, 2) → 3<br /> insert(A, 2, 10) → A = (1, 2, 10, 3, 3, 4, 5)<br /> append(A, -5) → A = (1, 2, 10, 3, 3, 4, 5, -5)<br /> del(A, 3) → A = (1, 2, 10, 3, 4, 5, -5)<br /> del(A, 1) → A = (1, 10, 3, 4, 5, -5)<br /> <br /> diepht@vnu<br /> <br /> 5<br /> <br />