Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 6 - ThS. Nguyễn Hà Giang

Chia sẻ: Tại Tâm | Ngày: | Loại File: PDF | Số trang:23

Thêm vào BST

Báo xấu

78
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung của bài giảng Cấu trúc dữ liệu và giải thuật - Chương 6 trình bày về Hash table. Trong chương này người học có thể hiểu được một số kiến thức sau: Mô tả, hàm băm, bảng băm kết nối trực tiếp, bảng băm kết nối hợp nhất, bảng băm dò tìm tuyến tính. Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 6 - ThS. Nguyễn Hà Giang

Hash Table Nguyễn Hà Giang 1 Nội dung (giới thiệu 1-2 tiết) • • • • • • Giới thiệu Mô tả Hàm băm Bảng băm kết nối trực tiếp Bảng băm kết nối hợp nhất Bảng băm dò tìm tuyến tính 2 Giới thiệu Tất cả các thao tác phải so sánh khoá!!! Khắc phục? 3 Vấn đề cơ bản • Bài toán: cần lưu trữ các mẫu tin và thực hiện các thao tác – Thêm mẫu tin – Xoá mẫu tin – Tìm mẫu tin theo khóa • Tìm cách thức thực hiện một cách hiệu quả? 4 Vấn đề cơ bản • Unsorted array – Sử dụng mảng để lưu mẫu tin, không có thứ tự – Thêm: thêm cuối nhanh O(1) – Xoá: chậm do tìm rồi xoá O(n) – Tìm kiếm: tuần tự chậm O(n) 5