tailieunhanh - Cấu trúc dữ liệu : BẢNG BĂM (HASH TABLE) part 3

NODE hashtable[M]; //Khai bao bang bam Cài đặt bảng băm dùng phương pháp kết nối hợp nhất: . Bảng băm với phương pháp dò tuần tự Mô tả: - Cấu trúc dữ liệu: 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 khoá của phần tử. Khi khởi động bảng băm thì tất cả trường key được gán | NODE hashtable M Khai bao bang bam Cài đặt bảng băm dùng phương pháp kết nối hợp nhất . Bảng băm với phương pháp dò tuần tự Mô tả - Cấu trúc dữ liệu 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 khoá của phần tử. Khi khởi động bảng băm thì tất cả trường key được gán NullKey - Khi thêm phần tử có khoá key vào bảng băm hàm băm h key 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ỉ này. Nếu bị xung đột thì hàm băm lại lần 1 hàm h1 sẽ xét địa chỉ kế tiếp nếu lại bị xung đột thì hàm băm thì hàm băm lại lần 2 hàm h2 sẽ xét địa chỉ kế tiếp nữa . và quá trình cứ thế cho đến khi nào tìm được địa chỉ trống và thêm phần tử mới vào địa chỉ này. - Khi tìm một phần tử có khoá key trong bảng băm hàm băm h key sẽ xác định địa chỉ i trong khoảng từ 0 đến M-1 tìm phần tử khoá key trong bảng băm xuất phát từ địa chỉ i. Hàm băm lại lần i được biểu diễn bằng công thức sau f key f key i M với f key là hàm băm chính của bảng băm. Lưu ý địa chỉ dò tìm kế tiếp là địa chỉ 0 nếu đã dò đến cuối bảng. Giả sử khảo sát bảng băm 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 h key key 10. 11 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 56 1 NULL 1 NULL 1 NULL 1 NULL 1 NULL 2 32 2 32 2 32 2 32 2 32 3 53 3 53 3 53 3 53 3 53 4 NULL 4 22 4 22 4 22 4 22 5 NULL 5 92 5 92 5 92 5 92 6 NULL 6 NULL 6 34 6 34 6 34 7 NULL 7 NULL 7 17 7 17 7 17 8 NULL 8 NULL 8 NULL 8 24 8 24 9 NULL 9 NULL 9 NULL 9 37 9 37 Khai báo cấu trúc bảng băm define NULLKEY -1 define M 100 struct node int key khoa cua nut tren bang bam struct node hashtable M Khai bao bang bam co M nut Cài đặt bảng băm dùng phương pháp dò tuyến tính 12 . Bảng băm với phương pháp dò bậc hai Mô tả - 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