Bài giảng Cấu trúc dữ liệu và giải thuật: Bài 10 - Hoàng Thị Điệp (2014)

Bài giảng "Cấu trúc dữ liệu và giải thuật - Bài 10: Bảng băm" cung cấp cho người học các kiến thức: Giới thiệu phương pháp băm, các hàm băm, các hàm băm, các chiến lược giải quyết va chạm. Mời các bạn cùng tham khảo nội dung chi tiết.
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: Bài 10 - Hoàng Thị Điệp (2014)Bài 10: Bảng bămGiảng viên: Hoàng Thị ĐiệpKhoa Công nghệ Thông tin – Đại học Công NghệCấu trúc dữ liệu và giải thuậtHKI, 2013-2014Kiểm tra viết, 15 phút(Sinh viên có thể sử dụng tài liệu.)1. Nêu 2 hàm băm2. Nêu 2 phương pháp giải quyết va chạm trong bảngbămnói tới trong Chương 9 Giáo trình.2diepht@vnuNội dung chính Giới thiệu phương pháp băm Hashing Các hàm băm Hash function Các chiến lược giải quyết va chạm Collision resolution3diepht@vnuKDLTT từ điển Trường hợp riêng của tậpđộng khi ta chỉ quan tâm tớitìm kiếm, xen, loại Là tập hợp trong đó mỗi phầntử là một cặp (khóa, dữ liệu) Có thể tìm kiếm theo khóa Được sắp hoặc không đượcsắp Các phần tử có thể có cùngkhóa* Dictionary vs. Map Ứng dụng Từ vựng – nghĩa Tên miền – địa chỉ IP Mã sinh viên – hồ sơ SV4 Các phép toán find(k) trả về 1 phần tử cókhóa k. Nếu không thấy trảvề NULL.findAll(k)insert(k, v) thêm phần tử (k,v) và trả về con trỏ tới nóerase(k) loại bỏ phần tử bấtkì có khóa bằng kerase(p) loại bỏ phần tử trỏbởi psize() trả về số lượng phần tửempty() kiểm tra xem từ điểnrỗng hay khôngdiepht@vnuPhương án cài KDLTT từ điển Mảng được sắp / không được sắp DSLK đơn/kép được sắp / không được sắp Cây tìm kiếm nhị phân5diepht@vnu