Cài đặt từ điển bằng bảng băm
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 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à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);
}
}
}
}
- Cấu Trúc Dữ Liệu
- Lời nói đầu
- Tổng quan,tóm tắt,mô hình,giải thuật (algorithms),ngôn ngữ giả và tinh chế từng bước
- Kiểu dữ liệu trừu tượng (ABSTRACT DATA TYPE -ADT)
- Kiểu dữ liệu trừu tượng danh sách (LIST)
- Ngăn xếp (STACK)
- Hàng đợi (QUEUE)
- Danh sách liên kết kép (Double - lists)
- Bài tập về kiểu dữ liệu trừu tượng,ngăn xếp,hàng đợi và danh sách liên kết kép
- Tổng quan về các thuật ngữ và kiểu dữ liệu trừu tượng cây
- Cài đặt cây
- Cây nhị phân (BRNARY TREES)
- Cây tìm kiếm nhị phân (BINARY SEARCH TREES)
- Bài tập cấu trúc cây
- Tổng quan,khái niệm,kiểu dữ liệu và cài đặt tập hợp
- Từ điển (DICTIONARY)
- Hàng ưu tiên (priority queue)
- Bài tập về tập hợp
- Các định nghĩa,kiểu dữ liệu,biểu diễn và bài tập về đồ thị
- Các phép duyệt đồ thị (Traversals of graph)
- Một số bài toán trên đồ thị