Cấu trúc dữ liệu: Từ điển

Từ điển là một tập hợp có các phần tử có thứ tự. Khi sắp xếp có thứ tự theo 1 quy tắc nào đó nhằm giúp cho việc thêm, xóa, tìm kiếm phần tử được nhanh hơn.

Ví du: từ điển ngôn ngữ (Anh Việt, Việt Anh,..) thì các từ được sắp xếp theo thứ tự bảng chữ cái.

Trong bài này, giả sử chúng ta cần thiết kế 1 từ điển để lưu các số nguyên. Các số có hàng đơn vị giống nhau sẽ được đưa vào một nhóm. Như vậy mỗi nhóm hay còn gọi là lô (bucket) là một tập hợp các số nguyên có hàng đơn vị giống nhau. Và với từ điển số nguyên này, ta có 10 lô tương ứng từ 0 đến 9.

Ta có thể dụng dụng lại cấu trúc dữ liệu Tập hợp để cài đặt cấu trúc từ điển (xem bài cấu trúc dữ liệu tập hợp: http://vhlong.blogspot.com/2015/10/cau-truc-du-lieu-tap-hop.html)

Save cấu trúc dữ liệu tập hợp bên dưới ra 1 tập tin tên là tudien_lib.cpp

#include "thuvien_list.cpp"

typedef List Set;
void MakeNullSet(Set &S){
    MakeNullList(S);
}
int EmptySet(Set S){
    return EmptyList(S);
}
int Member(ElementType X, Set S){
    Position P = S;
    while (P->Next!=NULL){
        if (P->Next->Element == X)
            return 1;
        P=P->Next;
    }
    return 0;
}
void InsertSet(ElementType X, Set &S){
    if (!Member(X,S))
        InsertList(X,1,S);
}
void DeleteSet(ElementType X, Set &S){
    Position P = S;
    while (P->Next!=NULL )
        if (P->Next->Element == X)
            break;
        else
            P=P->Next;
    if (P->Next!=NULL)
        DeleteList(P,S);
}
Set Intersect(Set A,Set B){
    Set C;
    MakeNullSet(C);
    while(A->Next!=NULL){
        if (Member(A->Next->Element,B))
            InsertSet(A->Next->Element,C);
        A=A->Next;
    }
    return C;
}

Set Union(Set A, Set B){
    Set C;
    MakeNullSet(C);
    while(A->Next!=NULL){
        InsertSet(A->Next->Element,C);
        A=A->Next;
    }
    while(B->Next!=NULL){
        InsertSet(B->Next->Element,C);
        B=B->Next;
    }
    return C;
}
Set Except(Set A, Set B){
    Set C;
    MakeNullSet(C);
    while(A->Next!=NULL){
        if (!Member(A->Next->Element,B))
            InsertSet(A->Next->Element,C);
        A=A->Next;
    }
    return C;

}
void PrintSet(Set S){
    PrintList(S);
}

Tạo 1 file mới cho cấu trúc dữ liệu từ điển với tên là tu_dien.cpp cùng thư mục với tudien_lib.cpp

#include "tudien_lib.cpp"

typedef Set Dictionary[10];

void MakeNullDict(Dictionary &d){
    for(int i=0;i<10;i++){
        MakeNullSet(d[i]);
    }
}
int Hash(ElementType X){
    return X%10;
}
void InsertDict(ElementType X, Dictionary &d){
    int bucket = Hash(X);
    InsertSet(X,d[bucket]);
}

void PrintDict(Dictionary d){
    for(int i=0;i<10;i++){
        printf("B[%d] : ",i);
        PrintSet(d[i]);
        printf("\n");

    }
}
int Search(ElementType X, Dictionary d){
    int bucket = Hash(X);
    return Member(X,d[bucket]);

}
int main(){
    Dictionary d;
    MakeNullDict(d);
    int a[]={17, 28 , 29, 23, 30, 11, 16, 15, 13, 12, 121, 90};
    for(int i=0;i<12;i++)
        InsertDict(a[i],d);

    PrintDict(d);
    printf("\nSearch(29,D) = %d ",Search(29,d));
    printf("\nSearch(4449,D) = %d ",Search(4449,d));

    return 0;
}