Từ điển (dictionary)
Từ điển là một kiểu dữ liệu trừu tượng tập hợp đặc biệt, trong đó chúng ta chỉ quan tâm đến các phép toán InsertSet, DeleteSet, Member và MakeNullSet. Sở dĩ chúng ta nghiên cứu từ điển là do trong nhiều ứng dụng không sử dụng đến các phép ...
Từ điển là một kiểu dữ liệu trừu tượng tập hợp đặc biệt, trong đó chúng ta chỉ quan tâm đến các phép toán InsertSet, DeleteSet, Member và MakeNullSet. Sở dĩ chúng ta nghiên cứu từ điển là do trong nhiều ứng dụng không sử dụng đến các phép toán hợp, giao, hiệu của hai tập hợp. Ngược lại ta cần một cấu trúc làm sao cho việc tìm kiếm, thêm và bớt phần tử có phần hiệu quả nhất gọi là từ điển. Chúng ta cũng chấp nhận MakeNullSet như là phép khởi tạo cấu trúc.
Cài đặt từ điển bằng mảng
Thực chất việc cài đặt từ điển bằng mảng hoàn toàn giống với việc cài đặt danh sách đặc không có thứ tự.
Khai báo
#define MaxLength ... // So phan tu toi da
typedef ... ElementType; // Kieu du lieu trong tu dien
typedef int Position;
typedef struct
{
ElementType Data[MaxLength];
Position Last;
} SET;
Khởi tạo cấu trúc rỗng
void MakeNullSET(SET *L)
{
(*L).Last=0;
}
Hàm kiểm tra thành viên của tập hợp
int Member(ElementType X, SET L)
{
Position P=1, Found=0;
while ((P <= (L.Last)) && (Found == 0))
if ((L.Data[P]) == X) Found = 1;
else P++;
return Found;
}
Thêm một phần tử vào tập hợp
Vì danh sách không có thứ tự nên ta có thể thêm phần tử mới vào cuối danh sách.
void InsertSET(ElementType X, SET *L)
{
if (FullSET(*L))
printf("Tap hop day");
else
if (Member(X,*L)==0)
{
(*L).Last++;
(*L).Data[(*L).Last]=X;
}
else
printf (" Phan tu da ton tai trong tu dien");
}
Xóa một phần tử trong tập hợp
Để xoá một phần tử nào đó ta phải tiến hành tìm kiếm nó trong danh sách. Vì danh sách không có thứ tự nên ta có thay thế phần tử bị xoá bằng phần tử cuối cùng trong danh sách để khỏi phải dời các phần tử nằm sau phần tử bị xoá lên một vị trí.
void DeleteSET(ElementType X, SET *L)
{
if (EmptySET(*L))
printf("Tap hop rong!");
else
{
Position Q=1;
while ((Q<=(*L).Last)&& ((*L).Data[Q]!=X)) Q++;
if ( (*L).Data[Q]==X)
{ for (int i=Q;i<(*L).Last;i++)
(*L).Data[i]=(*L).Data[i+1];
(*L).Last--;
}
}
}
Cài đặt tự điển bằng mảng đòi hỏi tốn n phép so sánh để xác định xem một phần tử có thuộc từ điển n phần tử hay không thông qua hàm Member. Trên từ điển, việc tìm kiếm một phần tử được xác định bằng hàm Member sẽ thường xuyên được sử dụng. Do đó, nếu hàm Member thực hiện không hiệu quả sẽ làm giảm đi ý nghĩa của từ điển (vì nói đến từ điển là phải tìm kiếm nhanh chóng). Mặt khác hàm Member còn được gọi từ trong thủ tục InsertSet và nó cũng dẫn đến là thủ tục này cũng không hiệu quả. Kỹ thuật băm cho phép chúng ta khắc phục nhược điểm trên.
