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 - ĐHKHTN

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" được biên soạn bởi các giảng viên Văn Chí Nam, Nguyễn Thị Hồng Nhung và Đặng Nguyễn Đức Tiến trình bày về các nội dung: danh sách liên kết, giải thuật ngăn xếp, giải thuật hàng đợi. Để biết rõ hơn về nội dung chi tiết, mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
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 - ĐHKHTNGiảng viên:Văn Chí Nam – Nguyễn Thị Hồng Nhung – Đặng Nguyễn Đức Tiến2Danh sách liên kếtNgăn xếpHàng đợiCấu trúc dữ liệu và giải thuật – HCMUS 2011©FIT-HCMUS13Cấu trúc dữ liệu và giải thuật – HCMUS 20114Giới thiệuCác loại danh sách liên kếtCác thao tác trên danh sách liên kếtSo sánh danh sách liên kết và mảngỨng dụngCấu trúc dữ liệu và giải thuật – HCMUS 2011©FIT-HCMUS25Mảng: cấu trúc dữ liệu quen thuộc Tập Sốcó thứ tựlượng phần tử cố định (tĩnh) Cấpphát vùng nhớ liên tụcxuất phần tử thông qua chỉ số TruyCấu trúc dữ liệu và giải thuật – HCMUS 20116Đánh giá thao tác trên mảng:xuất phần tử? Truy Cậpnhật? Chèn Xoáphần tử?phần tử?Cấu trúc dữ liệu và giải thuật – HCMUS 2011©FIT-HCMUS37Thực tế: Khôngxác định được chính xác số lượng phần tửsách bệnh nhân: tăng/giảm. Danh sách sinh viên: tăng/giảm. Danh Vùngnhớ thay đổi trong quá trình sử dụng=> Không đủ vùng nhớ cấp phát liên tục.=> Cấu trúc dữ liệu động đáp ứng nhu cầuCấu trúc dữ liệu và giải thuật – HCMUS 20118Danh sách liên kết đơnDanh sách liên kết képsingly linked listuni-directional linked listdoubly linked listbi-directional linked listDanh sách liên kết vòngcircularly linked listring listCấu trúc dữ liệu và giải thuật – HCMUS 2011©FIT-HCMUS49Mỗi phần tử có MỘT liên kết đến phần tử phíasau nó.123799Cấu trúc dữ liệu và giải thuật – HCMUS 201110Mỗi phần tử có HAI liên kết đến phần tử đứngsau và trước nó.129937Cấu trúc dữ liệu và giải thuật – HCMUS 2011©FIT-HCMUS5