Cài đặt từ điển bằng bảng băm
mở: Định nghĩa bảng băm mở : Băm mở là một mảng một chiều có B phần tử có chỉ số từ 0 đến B-1. Mỗi phần tử là một con trỏ, trỏ tới một danh sách liên kết mà dữ liệu sẽ của từ điển sẽ được lưu ...
mở:
Định nghĩa bảng băm mở :
Băm mở là một mảng một chiều có B phần tử có chỉ số từ 0 đến B-1. Mỗi phần tử là một con trỏ, trỏ tới một danh sách liên kết mà dữ liệu sẽ của từ điển sẽ được lưu trong các danh sách liên kết này. Mỗi danh sách được gọi là một Bucket (một danh sách có chứa các phần tử có cùng giá trị hàm băm).
Hàm băm:
Hàm băm là một ánh xạ từ tập dữ liệu A đến các số nguyên 0..B-1 (h : A → 0..B-1); Theo đó giả sử x ∈ A thì h(x) là một số nguyên 0≤h(x) ≤B-1. Có nhiều cách để xây dựng hàm băm, cách đơn giản nhất là ‘nguyên hóa x ‘ và sau đó lấy h(x) = x % B.
Ví dụ : Cho tập hợp A = {1,5,7,2,4,15}
Bảng băm là mảng gồm 5 phần tử và hàm băm h(x) = x % 5; Ta có bảng băm lưu trữ A như sau :
Hình IV.1: Bảng băm mở
Hàm băm có thể được thiết kế như sau
//Ham bam H(X)=X Mod B
int H(ElementType X)
{
return X%B;
}
Sử dụng bảng băm mở để cài đặt từ điển
Dưới đây là các thủ tục cài đặt từ điển bằng bảng băm mở với giả thiết rằng các phần tử trong từ điển có kiểu ElementType và hàm băm là H.
Khai báo
#define B ...
typedef ... ElementType;
typedef struct Node
{
ElementType Data;
Node* Next;
};
typedef Node* Position;
typedef Position Dictionary[B];
Khởi tạo bảng băm mở rỗng
Lúc này tất cả các bucket là rỗng nên ta gán tất cả các con trỏ trỏ đến đầu các danh sách trong mỗi bucket là NULL.
void MakeNullSet(Dictionary *D)
{
for(int i=0;i<B;i++)
(*D)[i]=NULL;
}
Kiểm tra một thành viên trong từ điển được cài bằng bảng băm mở
Để kiểm tra xem một khoá x nào đó có trong từ điển hay không, ta tính địa chỉ của nó trong bảng băm. Theo cấu trúc của bảng băm thì khoá x sẽ nằm trong bucket được trỏ bởi D[h(x)], với h(x) là hàm băm. Như vậy để tìm khoá x trước hết ta phải tính h(x) sau đó duyệt danh sách của bucket được trỏ bởi D[h(x)]. Giải thuật như sau:
int Member(ElementType X, Dictionary D)
{
Position P;
int Found=0;
//Tim o muc H(X)
P=D[H(X)];
//Duyet tren ds thu H(X)
while((P!=NULL) && (!Found))
if (P->Data==X) Found=1;
else P=P->Next;
return Found;
}
Thêm một phần tử vào từ điển được cài bằng bảng băm mở
Để thêm một phần tử có khoá x vào từ điển ta phải tính bucket chứa nó, tức là phải tính h(x). Phần tử có khoá x sẽ được thêm vào bucket được trỏ bởi D[h(x)]. Vì ta không quan tâm đến thứ tự các phần tử trong mỗi bucket nên ta có thể thêm phần tử mới ngay đầu bucket này. Giải thuật như sau:
void InsertSet(ElementType X, Dictionary *D)
{
int Bucket;
Position P;
if (!Member(X,*D))
{
Bucket=H(X);
P=(*D)[Bucket];
//Cap phat o nho moi cho *D[Bucket]
(*D)[Bucket] = (Node*)malloc(sizeof(Node));
(*D)[Bucket]->Data=X;
(*D)[Bucket]->Next=P;
}
}
Xoá một phần tử trong từ điển được cài bằng bảng băm mở
Xoá một phần tử có khoá x trong từ điển bao gồm việc tìm ô chứa khoá và xoá ô này. Phần tử x, nếu có trong từ điển, sẽ nằm ở bucket D[h(x)]. Có hai trường hợp cần phân biệt. Nếu x nằm ngay đầu bucket, sau khi xoá x thì phần tử kế tiếp sau x trong bucket sẽ trở thành đầu bucket. Nếu x không nằm ở đầu bucket thì ta duyệt bucket này để tìm và xoá x. Trong trường hợp này ta phải định vị con trỏ duyệt tại "ô trước" ô chứa x để cập nhật lại con trỏ Next của ô này. Giải thuật như sau:
void DeleteSet(ElementType X, Dictionary *D)
{
int Bucket, Done;
Position P,Q;
Bucket=H(X);
// Neu danh sach ton tai
if ((*D)[Bucket]!=NULL)
{
// X o dau danh sach
if ((*D)[Bucket]->Data==X)
{
Q=(*D)[Bucket];
(*D)[Bucket]=(*D)[Bucket]->Next;
free(Q);
}
else // Tim X
{
Done=0;
P=(*D)[Bucket];
while ((P->Next!=NULL) && (!Done))
if (P->Next->Data==X) Done=1;
else P=P->Next;
// Neu tim thay
if (Done)
{
//Xoa P->Next
Q=P->Next;
P->Next=Q->Next;
free(Q);
}
}
}
}
