Bảng Băm Với Phương Pháp Dò Bậc Hai Mơ Tả: - Tài Liệu Text - 123doc

1. Trang chủ >
2. Công Nghệ Thông Tin >
3. Kỹ thuật lập trình >

Bảng băm với phương pháp dò bậc hai Mơ tả:

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (178.95 KB, 16 trang )

Hình thể hiện thêm các nut 32, 53, 22, 92, 17, 34, 24, 37, 56 vào bảng băm. 0 NULL 0 NULL 0 NULL 0 NULL 0 561 NULL 1 NULL 1 NULL 1 NULL 1 NULL 2 322 32 2 322 32 2 323 53 3 533 53 3 533 53 4 NULL 4 224 22 4 224 22 5 NULL 5 925 92 5 925 92 6 NULL 6 NULL 6 346 34 6 347 NULL 7 NULL 7 17 7 177 17 8 NULL 8 NULL 8 NULL 8 248 24 9 NULL 9 NULL 9 NULL 9 379 37Khai báo cấu trúc bảng băm: define NULLKEY –1define M 100 struct node{ int key; khoa cua nut tren bang bam}; struct node hashtable[M]; Khai bao bang bam co M nutCài đặt bảng băm dùng phương pháp dò tuyến tính:

2.4.4. Bảng băm với phương pháp dò bậc hai Mô tả:

12- Bảng băm trong trường hợp này được cài đặt bằng danh sách kề có M phần tử, mỗi phần tử của bảng băm là một mẫu tin có một trường key để chứa khóa cácphần tử.- Khi khởi động bảng băm thì tất cả trường key bị gán NULLKEY.Khi thêm phần tử có khóa key vào bảng băm, hàm băm hkey sẽ xác định địa chỉ i trong khoảng từ 0 đến M-1.· Nếu chưa bị xung đột thì thêm phần tử mới vào địa chỉ i này. · Nếu bị xung đột thì hàm băm lại lần 1 h1 sẽ xét địa chỉ cách i là 12, nếu lại bị xung đột thì hàm băm lại lần 2 h2 sẽ xét địa chỉ cách i 22,… , quá trình cứ thế cho đến khi nào tìm được trống và thêm phần tử vào địa chỉ này.- Khi tìm kiếm một phần tử có khóa key trong bảng băm thì xét phần tử tại địa chỉ i=fkey, nếu chưa tìm thấy thì xét phần tử cách i 12, 22, …, quá trình cứ thế cho đến khi tìm được khóa trường hợp tìm thấy hoặc rơi vào địa chỉ trống trườnghợp khơng tìm thấy.- Hàm băm lại lần thứ i được biểu diễn bằng công thức sau: fikey= fkey + i2M với fkey là hàm băm chính của bảng băm.Nếu đã dò đến cuối bảng thì trở về dò lại từ đầu bảng. Bảng băm minh họa có cấu trúc như sau:- Tập khóa K: tập số tự nhiên - Tập địa chỉ M: gồm 10 địa chỉ M={0, 1, …, 9}- Hàm băm fkey = key 10.Khai báo cấu trúc bảng băm: define NULLKEY –1define M 101M la so nut co tren bang bam,du de chua cac nut nhap vao bang bam,chon M la so nguyen to13Khai bao nut cua bang bam struct node{ int key; Khoa cua nut tren bang bam}; Khai bao bang bam co M nutstruct node hashtable[M]; int N;Cài đặt bảng băm dùng phương pháp dò bậc hai: Hàm băm: Giả sử chúng ta chọn hàm băm dạng: fkey=key 10.int hashfuncint key {returnkey 10; }Phép toán initializevoid initialize {int i; fori=0; iM;i++ hashtable[i].key = NULLKEY;N=0; so nut hien co khoi dong bang 0 }Phép toán empty:int empty {returnN ==0 ?TRUE :FALSE; }Phép toán full: int full{14returnN = = M-1 ?TRUE :FALSE; }Phép tốn search:Tìm phần tử có khóa k trên bảng băm,nếu khơng tìm thấy hàm này trả về trị M, nếu tìm thấy hàm này trả về địa chỉ tìm thấy.int searchint k {int i, d; i = hashfunsk;d = 1; whilehashtable[i].key=khashtable[i].key =NULLKEY{ Bam lai theo phuong phap bac haii = i+d M; d = d+2;} hashtable[i].key =k; N = N+1;returni; }

2.4.5. Bảng băm với phương pháp băm kép Mô tả:

Xem Thêm

Tài liệu liên quan

• BẢNG BĂM (HASH TABLE)
  • 16
  • 3,341
  • 21

Tải bản đầy đủ (.doc) (16 trang)

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(123 KB) - BẢNG BĂM (HASH TABLE)-16 (trang) Tải bản đầy đủ ngay ×