Giải Thuật Và Lập Trình - C: IV. Từ điển (DICTIONARY) | V1Study

• Đào tạo Độ tuổi từ 5 - 11 Độ tuổi từ 12 - 17 Từ 18 tuổi
• Lập trình Python Lập trình C C++ Java C# - C Sharp Android Scratch Pascal Robot mBot
• Web ReactJS HTML5 CSS3 JavaScript Node.js JSP ASP.NET Core jQuery PHP
• FW-CMS Laravel AngularJS Flutter Magento Bootstrap VueJS CodeIgnitor WordPress Sass Drupal
• Video Video Python Video Lập trình C Video C# Video Java Video HTML5-CSS3-JavaScript Video SQL Server Video PHP Video jQuery Video Android Video C++ Video Scratch
• Video1 Video XML-JSON Video MySQL Video Excel Video Giải thuật và Lập trình Video Sức khỏe Video Drupal Video mBot Video Giáo dục - Khoa học
• Other Unity Giải thuật và lập trình Giải thuật và lập trình - C CCNA Mạng máy tính Design Patterns English Facebook SEO Git Tin học đại cương Japanese App-Uti Download
• Data SQL Server XML JSON MySQL
• News

≡ ≡ Giải thuật và lập trình - C Chương I. Mở đầu I. Từ bài toán đến chương trình II. Kiểu dữ liệu trừu tượng (ABSTRACT DATA TYPE - ADT) III. Kiểu dữ liệu, Cấu trúc dữ liệu, Kiểu dữ liệu trừu tượng (DATA TYPES, DATA STRUCTURES, ABSTRACT DATA TYPES) Chương II. Các kiểu dữ liệu trừu tượng cơ bản I. Kiểu dữ liệu danh sách (LIST) II. Ngăn xếp (Stack) III. Hàng đợi (QUEUE) IV. Danh sách liên kết kép (DOUBLE - LISTS) BÀI TẬP Chương III. Cấu trúc cây (TREES) I. Các thuật ngữ cơ bản trên cây II. Kiểu dữ liệu trừu tượng cây III. Cài đặt cây IV. Cây nhị phân (BINARY TREES) V. Cây tìm kiếm nhị phân (BINARY SEARCH TREES) BÀI TẬP Chương IV. Tập hợp I, II. Khái niệm, Kiểu dữ liệu trừu tượng tập hợp III. Cài đặt tập hợp IV. Từ điển (DICTIONARY) V. HÀNG ƯU TIÊN (PRIORITY QUEUE) BÀI TẬP Chương V. Đồ thị (Graph) I. Các định nghĩa II. Kiểu dữ liệu trừu tượng đồ thị III. Biều diễn đồ thị IV. Các phép duyệt đồ thị (Traversals of graph) V. Một số bài toán trên đồ thị BÀI TẬP Solutions Solution CÀI ĐẶT CÂY (TREE) bằng mảng Giải thuật và lập trình - C: IV. Từ điển (DICTIONARY) Khóa học qua video: Lập trình Python All Lập trình C# All SQL Server All Lập trình C Java PHP HTML5-CSS3-JavaScript Đăng ký Hội viên Tất cả các video dành cho hội viên

IV. 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 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.

1. 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");

elseif (Member(X,*L)==0)

{

(*L).Last++; (*L).Data[(*L).Last]=X;

}

else

printf ("\nPhan 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.

2. Cài đặt từ điển bằng bảng băm

2.1 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ì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);

}

}

}

}

2.2. Cài đặt từ điển bằng bảng băm đóng

Định nghĩa bảng băm đóng :

Bảng băm đóng lưu giữ các phần tử của từ điển ngay trong mảng chứ không dùng mảng làm các chỉ điểm đầu của các danh sách liên kết. Bucket thứ i chứa phần tử có giá trị băm là i, nhưng vì có thể có nhiều phần tử có cùng giá trị băm nên ta sẽ gặp trường hợp sau: ta muốn đưa vào bucket i một phần tử x nhưng bucket này đã bị chiếm bởi một phần tử y nào đó (đụng độ). Như vậy khi thiết kế một bảng băm đóng ta phải có cách để giải quyết sự đụng độ này.

Giải quyết đụng độ :

Cách giải quyết đụng độ đó gọi là chiến lược băm lại (rehash strategy). Chiến lược băm lại là chọn tuần tự các vị trí h1,..., hk theo một cách nào đó cho tới khi gặp một vị trí trống để đặt x vào. Dãy h1,..., hk gọi là dãy các phép thử. Một chiến lược đơn giản là băm lại tuyến tính, trong đó dãy các phép thử có dạng :

Ví dụ B=8 và các phần tử của từ điển là a,b,c,d có giá trị băm lần lượt là: h(a)=3, h(b)=0, h(c)=4, h(d)=3. Ta muốn đưa các phần tử này lần lượt vào bảng băm.

Khởi đầu bảng băm là rỗng, có thể coi mỗi bucket chứa một giá trị đặc biệt Empty, Empty không bằng với bất kỳ một phần tử nào mà ta có thể xét trong tập hợp các phần tử muốn đưa vào bảng băm.

Ta đặt a vào bucket 3, b vào bucket 0, c vào bucket 4. Xét phần tử d, d có h(d)=3 nhưng bucket 3 đã bị a chiếm ta tìm vị trí h1(x)= (h (x)+1) mod B = 4, vị trí này cũng đã bị c chiếm, tiếp tục tìm sang vị trí h2 (x)= (h(x)+2) mod B= 5 đây là một bucket rỗng ta đặt d vào (xem hình IV.2)

Hình IV.2: Giải quyết đụng độ trong bảng băm đóng bằng chiến lược băm lại tuyến tính

Trong bảng băm đóng, phép kiểm tra một thành viên(thủ tục MEMBER (x,A)) phải xét dãy các bucket h(x),h1(x),h2(x),... cho đến khi tìm thấy x hoặc tìm thấy một vị trí trống. Bởi vì nếu hk(x) là vị trí trống được gặp đầu tiên thì x không thể được tìm gặp ở một vị trí nào xa hơn nữa. Tuy nhiên, nói chung điều đó chỉ đúng với trường hợp ta không hề xoá đi một phần tử nào trong bảng băm. Nếu chúng ta chấp nhận phép xoá thì chúng ta qui ước rằng phần tử bị xóa sẽ được thay bởi một giá trị đặc biệt, gọi là Deleted, giá trị Deleted không bằng với bất kỳ một phần tử nào trong tập hợp đang xét vào nó cũng phải khác giá trị Empty. Empty cũng là một giá trị đặc biệt cho ta biết ô trống.

Ví dụ

- Tìm phần tử e trong bảng băm trên, giả sử h(e)=4. Chúng ta tìm kiếm e tại các vị trí 4,5,6. Bucket 6 là chứa Empty, vậy không có e trong bảng băm.

- Tìm d, vì h(d)=3 ta khởi đầu tại vị trí này và duyệt qua các bucket 4,5. Phần tử d được tìm thấy tại bucket 5.

Sử dụng bảng băm đóng để cài đặt từ điển

Dưới đây là khai báo và thủ tục cần thiết để cài đặt từ điển bằng bảng băm đóng. Để dễ dàng minh hoạ các giá trị Deleted và Empty, giả sử rằng ta cần cài đặt từ điển gồm các chuỗi 10 kí tự. Ta có thể qui ước:

Empty là chuỗi 10 dấu + và Deleted là chuỗi 10 dấu *.

Khai báo

#define B 100

#define Deleted -1000//Gia dinh gia tri cho o da bi xoa

#define Empty 1000 //Gia dinh gia tri cho o chua su dung

typedef int ElementType;

typedef int Dictionary [B];

Tạo hàm băm

int H (ElementType X)]

{

return X%B;

}

Tạo tự điển rỗng

// Tao tu dien rong

void MakeNullDic(Dictionary D){

for (int i=0;i<B; i++)

D[i]=Empty;

}

Kiểm tra sự tồn tại của phần tử trong tự điển

Hàm trả về giá tri 0 nếu phần tử X không tồn tại trong tự điển; Ngược lại, hàm trả về giá trị 1;

int Member(ElementType X, Dictionary D)

{

Position init=H(X), i=0;

while ((i<B) && (D[i]!=Empty) && (D[i]!=X)) i++;

return (D[i]==X);

}

Thêm phần tử vào tự điển

void InsertDic(ElementType X, Dictionary D)

{

int i=0,init;

if (FullDic(D))

printf("Bang bam day");

else if (Member(X,D)==0)

{

init=H(X);

while((i<B)&&(D[(i+init)%B]!=Empty)&&(D[(i+init)%B]!=Deleted))i++;

D[(i+init)%B]=X;

printf("\n Vi tri de xen phan tu %d la %d\n",X,(i+init)%B);

}

else

printf ("\nPhan tu da ton tai trong bang bam");

}

Xóa từ ra khỏi tự điển

void DeleteDic(ElementType X, Dictionary D)

{

if (EmptyDic(D)) printf("\nBang bam rong!");

else

{

int i=0,init =H(X);

while((i<B)&&(D[(i+init)%B]!=X)&&(D[(i+init)%B]!=Deleted)) i++;

if ( D[(i+init)%B]==X) D[(i+init)%B]=Deleted;

}

}

3. Các phương pháp xác định hàm băm

Phương pháp chia

"Lấy phần dư của giá trị khoá khi chia cho số bucket" . Tức là hàm băm có dạng:

H(x)= x mod B

Phương pháp này rõ ràng là rất đơn giản nhưng nó có thể không cho kết quả ngẫu nhiên lắm. Chẳng hạn B=1000 thì H(x) chỉ phụ thuộc vào ba số cuối cùng của khoá mà không phụ thuộc vào các số đứng trước. Kết quả có thể ngẫu nhiên hơn nếu B là một số nguyên tố.

Phương pháp nhân

"Lấy khoá nhân với chính nó rồi chọn một số chữ số ở giữa làm kết quả của hàm băm".

Ví dụ:

Vì các chữ số ở giữa phụ thuộc vào tất cả các chữ số có mặt trong khoá do vậy các khoá có khác nhau đôi chút thì hàm băm cho kết quả khác nhau.

Phương pháp tách

Đối với các khoá dài và kích thước thay đổi người ta thường dùng phương pháp phân đoạn, tức là phân khoá ra thành nhiều đoạn có kích thước bằng nhau từ một đầu (trừ đoạn tại đầu cuối), nói chung mỗi đoạn có độ dài bằng độ dài của kết quả hàm băm. Phân đoạn có thể là tách hoặc gấp:

a. Tách:

Tách khóa ra từng đoạn rồi xếp các đoạn thành hàng được canh thẳng một đầu rồi có thể cộng chúng lại rồi áp dụng phương pháp chia để có kết quả băm.

Ví dụ: khoá 17046329 tách thành

329

046

017

cộng lại ta được 392. 392 mod 1000 = 392 là kết quả băm khoá đã cho.

b. Gấp:

Gấp khoá lại theo một cách nào đó, có thể tương tự như gấp giấy, các chữ số cùng nằm tại một vị trí sau khi gấp được xếp lại thẳng hàng với nhau rồi có thể cộng lại rồi áp dụng phương pháp chia (mod) để cho kết quả băm.

Ví dụ: khoá 17046329 gấp hai biên vào ta có

932

046

710

Cộng lại ta có 1679, lấy 1679 mod 1000 = 679 là kết quả băm khoá đã cho.

» Tiếp: V. HÀNG ƯU TIÊN (PRIORITY QUEUE) « Trước: III. Cài đặt tập hợp Khóa học qua video: Lập trình Python All Lập trình C# All SQL Server All Lập trình C Java PHP HTML5-CSS3-JavaScript Đăng ký Hội viên Tất cả các video dành cho hội viên Khóa học qua video: Lập trình Python All Lập trình C# All SQL Server All Lập trình C Java PHP HTML5-CSS3-JavaScript Đăng ký Hội viên Tất cả các video dành cho hội viên Copied !!! Copy linkCopied link!

Bạn muốn tìm kiếm điều gì?

×