NỘI DUNG
CÁC PHÉP TOÁN CƠ BẢN
TRÊN TẬP HỢP
•
•
•
•
•
Khái niệm tập hợp
Các kiểu dữ liệu trừu tượng trên tập hợp
Cài đặt tập hợp
Từ điển
Bảng băm
Bộ môn Công nghệ phần mềm,
Khoa CNTT&TT, Đại học Cần Thơ
BĂM ĐÓNG
CÀI ĐẶT TỪ ĐIỂN BẰNG BẢNG BĂM
Chỉ
số
• BĂM ĐÓNG
• BĂM MỞ
0
20
1
2
3
4
34
5
6
26
H(x)=x%B
…
B-1
19
1
BĂM ĐÓNG
BĂM ĐÓNG
• Tạo từ điển rỗng
• Khai báo
// Tao tu dien rong
void MakeNullDic(Dictionary D)
for (int i=0;i
D[i]=Empty;
}
#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 struct Dictionary[B];
BĂM ĐÓNG
BĂM ĐÓNG
Thêm vào giá trị 29
Chỉ
số
Thêm vào giá trị 30
H(x)=x%B
0
20
20
1
29
1
29
2
12
i=1 H(30) = 1
2
E
3
D30
3
E
4
34
i=2 H(30)=2
4
34
5
E
5
E
26
6
26
i=1 H(29) = 0
6
…
E
…
E
i=2 H(29)=1
0
E
B-1 (9)
i=0 H(29) = 9
i=0 H(30) = 0
i=3 H(30)=3
E
B-1
19
19
Hi(x) = (H(x)+i)%B
2
BĂM ĐÓNG
• Kiểm tra sự tồn tại của phần tử trong từ điển
int Member(ElementType X, Dictionary D) {
Position P = H(X); // ham bam
int i=0;
Found = 0;
while ((i < B) && (D[P]!=Empty) && (!Found))
if (D[P] == X) Found = 1;
else {
P=(P+1)%B;
i++;
}
return Found;
}
BĂM ĐÓNG
• Kiểm tra bảng băm có đầy?
int FullSet(Dictionary D) {
int i=0;
int Full=1;
while ((i
if ((D[i] == Deleted)||(D[i] == Empty))
Full = 0;
else
i++;
return Full;
}
BĂM ĐÓNG
BĂM ĐÓNG
Xóa giá trị 30
• Thêm phần tử vào từ điển
void InsertSet(ElementType X, Dictionary D) {
Position P;
if (FullSet(D))
printf("\nBang bam day\n");
else if (!Member(X,D)){
P = H(X);
int i = 0;
while((i
i++;
P=(P+1)%B;
}
D[P]=X;
}
else
printf("\nPhan tu da ton tai");
}
0
20
1
29
2
12
i=1 H(30) = 1
3
30
Deleted
4
34
i=2 H(30)=2
5
E
6
26
…
E
i=0 H(30) = 0
i=3 H(30)=3
E
B-1
19
3
BĂM ĐÓNG
• Xóa từ ra khỏi từ điển
void DeleteSet(ElementType X,Dictionary D){
int i=0;
Position P = H(X);
while ((i
i++;
P=(P+1)%B;
}
if (D[P]==X)
D[P]=Deleted;
}
BĂM MỞ
• Khởi tạo bảng băm mở rỗng
void MakeNullSet(Dictionary *D){
for(int i=0;i
(*D)[i]=NULL;
}
BĂM MỞ
• Khai báo
#define B ...
typedef ... ElementType;
typedef struct Node* NodeType;
struct Node {
ElementType Data;
NodeType
Next;
};
typedef Node*
Position;
typedef Position Dictionary[B];
BĂM MỞ
• Kiểm tra một thành viên trong từ điển
int Member(ElementType X, Dictionary D){
Position P;
int Found=0;
P=D[H(X)]; //Tim o muc H(X)
//Duyet tren ds thu H(X)
while((P!=NULL) && (!Found))
if (P->Data==X) Found=1;
else P=P->Next;
return Found;
}
4
BĂM MỞ
• Thêm một phần tử vào từ điển
void InsertSet(ElementType X,Dictionary *D){
if (!Member(X,*D)){
NodeType temp;
temp=(NodeType)malloc(sizeof(struct Node));
temp->Data = X;
temp-> Next = (*D)[H(X)];
(*D)[H(X)] = temp;
}
}
• Xoá một phần tử trong từ điển
void DeleteSet(ElementType X, Dictionary *D) {
Position P, Q;
if((*D)[H(X)]!=NULL) {
if ((*D)[H(X)]->Data==X) {
Q=(*D)[H(X)];
(*D)[H(X)]=(*D)[H(X)]->Next;
free(Q); }
else {
int Found = 0;
P=(*D)[H(X)];
while ((P->Next!=NULL) && (!Found))
if (P->Next->Data==X) Found=1;
else P=P->Next;
if (Found) {
Q=P->Next;
P->Next=Q->Next;
free(Q);
}
}
}
}
Hết chương
5