Cài đặt Hash Table – Bảng Băm | Chuong Le Hoang

1. Mô tả:

– Bảng băm được sử dụng phổ biến và có rất nhiều tác dụng.

– Bạn có thể cài đặt bảng băm để làm một chương trình từ điển, mục đích của việc dùng bảng băm vào cài đặt từ điển là để cải thiện tốc độ tìm kiếm với số lượng từ vựng khổng lồ.

– Hình 1 mô tả 1 bảng băm đơn giản.

Hình 1

– Cho các số k: 8, 19, 5, 9, 10 , thực hiện chèn vào 1 bảng băm có m = 10 slot. Với công thức: slot = k % m. Ta được kết quả như Hình 2

Hình 2

2. Cài đặt:

– Hình 3 định nghĩa kiểu dữ liệu Cell, 1 cell tương đương với 1 phần tử trong bảng băm.

Hình 3

– Hình 4 định nghĩa hàm khởi tạo, khai báo mảng 2 chiều để thể hiện bảng băm, với kiểu dữ liệu là Cell.

Hình 4

– Hình 5 định nghĩa hàm GetSlot trả về slot của k.

Hình 5

– Hình 6 định nghĩa hàm khởi tạo của bảng băm.

Hình 6

– Hình 7 định nghĩa hàm hủy của bảng băm.

Hình 7

– Hình 8 định nghĩa phương thức chèn một phần tử vào bảng băm, để thưc hiện chèn phần tử vào bảng băm, ta thực hiện 2 bước sau:

 + Tìm slot thích hợp.

 + Chèn vào slot: có 2 trường hợp có thể xảy ra, đó là trường hợp là phần tử đầu tiên và không phải là phần tử đầu tiên.

Hình 8

– Hình 9 định nghĩa phương thức tìm kiếm phần tử có tồn tại trong bảng băm hay không.

Hình 9

– Hình 10 định nghĩa phương thức in tất cả phần tử của bảng băm theo từng slot.

Hình 10

Tôi vừa trình bày xong mô tả khái niệm và cách cài đặt bảng băm, sau khi cài đặt thành công bẳng băm, các bạn có thể cài đặt 1 bảng băm nâng cao hơn nữa bằng cách viết 1 chương trình từ điển đơn giản. Chúc các bạn thành công! 

Chia sẻ:

• X
• Facebook

Thích Đang tải...

Có liên quan