Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu cơ bản - ĐH KHTN TPHCM

Giảng viên:<br /> <br /> Văn Chí Nam – Nguyễn Thị Hồng Nhung – Đặng Nguyễn Đức Tiến<br /> <br /> 2<br /> <br /> Danh sách liên kết<br /> Ngăn xếp<br /> Hàng đợi<br /> <br /> Cấu trúc dữ liệu và giải thuật – HCMUS 2011<br /> <br /> ©FIT-HCMUS<br /> <br /> 1<br /> <br /> 3<br /> <br /> Cấu trúc dữ liệu và giải thuật – HCMUS 2011<br /> <br /> 4<br /> <br /> <br /> <br /> Giới thiệu<br /> <br /> <br /> <br /> Các loại danh sách liên kết<br /> <br /> <br /> <br /> Các thao tác trên danh sách liên kết<br /> <br /> <br /> <br /> So sánh danh sách liên kết và mảng<br /> <br /> <br /> <br /> Ứng dụng<br /> Cấu trúc dữ liệu và giải thuật – HCMUS 2011<br /> <br /> ©FIT-HCMUS<br /> <br /> 2<br /> <br /> 5<br /> <br /> <br /> <br /> Mảng: cấu trúc dữ liệu quen thuộc<br />  Tập<br /> <br />  Số<br /> <br /> có thứ tự<br /> <br /> lượng phần tử cố định (tĩnh)<br /> <br />  Cấp<br /> <br /> phát vùng nhớ liên tục<br /> xuất phần tử thông qua chỉ số<br /> <br />  Truy<br /> <br /> Cấu trúc dữ liệu và giải thuật – HCMUS 2011<br /> <br /> 6<br /> <br /> <br /> <br /> Đánh giá thao tác trên mảng:<br /> xuất phần tử?<br /> <br />  Truy<br /> <br />  Cập<br /> <br /> nhật?<br /> <br />  Chèn<br /> <br />  Xoá<br /> <br /> phần tử?<br /> <br /> phần tử?<br /> <br /> Cấu trúc dữ liệu và giải thuật – HCMUS 2011<br /> <br /> ©FIT-HCMUS<br /> <br /> 3<br /> <br /> 7<br /> <br /> <br /> <br /> Thực tế:<br />  Không<br /> <br /> xác định được chính xác số lượng phần tử<br /> <br /> sách bệnh nhân: tăng/giảm.<br />  Danh sách sinh viên: tăng/giảm.<br />  Danh<br /> <br />  Vùng<br /> <br /> nhớ thay đổi trong quá trình sử dụng<br /> <br /> => Không đủ vùng nhớ cấp phát liên tục.<br /> <br /> => Cấu trúc dữ liệu động đáp ứng nhu cầu<br /> Cấu trúc dữ liệu và giải thuật – HCMUS 2011<br /> <br /> 8<br /> <br /> <br /> <br /> Danh sách liên kết đơn<br /> <br /> <br /> <br /> <br /> <br /> Danh sách liên kết kép<br /> <br /> <br /> <br /> <br /> <br /> singly linked list<br /> uni-directional linked list<br /> <br /> doubly linked list<br /> bi-directional linked list<br /> <br /> Danh sách liên kết vòng<br /> <br /> <br /> <br /> circularly linked list<br /> ring list<br /> Cấu trúc dữ liệu và giải thuật – HCMUS 2011<br /> <br /> ©FIT-HCMUS<br /> <br /> 4<br /> <br /> 9<br /> <br /> <br /> <br /> Mỗi phần tử có MỘT liên kết đến phần tử phía<br /> sau nó.<br /> 12<br /> <br /> 37<br /> <br /> 99<br /> <br /> Cấu trúc dữ liệu và giải thuật – HCMUS 2011<br /> <br /> 10<br /> <br /> <br /> <br /> Mỗi phần tử có HAI liên kết đến phần tử đứng<br /> sau và trước nó.<br /> 12<br /> <br /> 99<br /> <br /> 37<br /> <br /> Cấu trúc dữ liệu và giải thuật – HCMUS 2011<br /> <br /> ©FIT-HCMUS<br /> <br /> 5<br /> <br />