Giáo trình cấu trúc dữ liệu part 8

Tham khảo tài liệu giáo trình cấu trúc dữ liệu part 8, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Giáo trình cấu trúc dữ liệu part 8Cấu trúc dữ liệu Chương IV: 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áchkhô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 Cấu trúc dữ liệu Chương IV: Tập hợp 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 :Bảng băm chứa các Danh sách của mỗi bucketchỉ điểm đầu củadanh sách 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 114 TrangCấu trúc dữ liệu Chương IV: Tập hợpDưới đây là các thủ tục cài đặt từ điển bằng bảng băm mở vớigiả thiết rằng các phần tử trong từ điển có kiểu ElementTypevà 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áchtrong mỗi bucket là NULL. void MakeNullSet(Dictionary *D) { for(int i=0;iCấu trúc dữ liệu Chương IV: Tập hợp { 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ínhh(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 quantâ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 đầubucket 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; 116 TrangCấu trúc dữ liệu Chương IV: Tập hợp (*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. Trongtrườ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 { 117 ...