intTypePromotion=1

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

0
49
lượt xem
1
download

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

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

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2