CH NG 4:ƯƠ
T P H PẬ Ợ
Nguy n Văn Linhễ
Khoa Công ngh Thông tin - Truy n thôngệ ề
Đ i h c C n Thạ ọ ầ ơ
Nguy n Văn Linhễ

Nguy n Văn Linhễ
N I DUNGỘ
•
Khái ni m t p h pệ ậ ợ
•
Các phép toán trên t p h pậ ợ
•
Cài đ t t p h pặ ậ ợ
•
T đi nừ ể
•
B ng bămả

Nguy n Văn Linhễ
KHÁI NI M T P H PỆ Ậ Ợ
•
T p h p các thành viên (members) ho c ph n t ậ ợ ặ ầ ử
(elements) nh khái ni m toán h c.ư ệ ọ
•
Các ph n t c a t p h p ph i khác nhauầ ử ủ ậ ợ ả
•
T p h p có th t ho c không có th t .ậ ợ ứ ự ặ ứ ự
•
đây ta s xét t p h p có th t , t c là trên t p Ở ẽ ậ ợ ứ ự ứ ậ

h p S có các quan h < th a mãn:ợ ệ ỏ
•
V i m i a, b trong S thì a<b ho c b<aớ ọ ặ
•
V i m i a, b, c trong S, n u a<b và b<c thì a<cớ ọ ế

Nguy n Văn Linhễ
BI U DI N T P H P (1)Ể Ễ Ậ Ợ
•
Li t kê các ph n t trong c p d u ngo c {}ệ ầ ử ặ ấ ặ
–
x∈ S : x là m t ph n t c a t p h p Sộ ầ ử ủ ậ ợ
–
x∉ S : x không là m t ph n t c a t p h p Sộ ầ ử ủ ậ ợ

∅ : t p h p r ng, không có thành viênậ ợ ỗ
–
VD: A={1,2} B= {1,2,3}

Nguy n Văn Linhễ
BI U DI N T P H P (2)Ể Ễ Ậ Ợ
•
Cho hai t p h p A và B:ậ ợ
–
A là 1 b ph n c a B, kí hi u A ộ ậ ủ ệ ⊆ B: n u m i ph n ế ọ ầ
t c a A đ u là ph n t c a Bử ủ ề ầ ử ủ
•
VD: A ⊆ B
–
T p h p A và B b ng nhau, kí hi u A = B:n u Aậ ợ ằ ệ ế ⊆ B

và B⊆ A
–
H p c a hai t p h p: Aợ ủ ậ ợ ∪B={x| x⊆A ho c xặ ∈B}
–
Giao c a hai t p h p: Aủ ậ ợ ∩B={x| x∈A và x∈B}
–
Hi u c a hai t p h p: A\B={x| xệ ủ ậ ợ ∈A và x∉B}

Nguy n Văn Linhễ
CÁC PHÉP TOÁN TRÊN T P H PẬ Ợ
Phép toán Di n gi iễ ả
Make_Null_Set(S) T o t p h p S r ngạ ậ ợ ỗ
Empty_Set(S) Ki m tra xem t p h p S có r ng?ể ậ ợ ỗ
Member(X,S) Ki m tra xem X có thu c S?ể ộ
Insert_Set(X,S) Thêm ph n t X vào t p h p Sầ ử ậ ợ
Delete_Set(X,S) Xoá ph n t X trong t p h p Sầ ử ậ ợ
Union(A, B,C) C=A∪B
Intersection(A, B, C) C=A∩B
Difference(A,B,C) C=A\B

Nguy n Văn Linhễ
CÀI Đ T T P H PẶ Ậ Ợ
•
CÀI Đ T B NG VECT BITẶ Ằ Ơ
•
CÀI Đ T B NG DANH SÁCH LIÊN K TẶ Ằ Ế

Nguy n Văn Linhễ
CÀI Đ T T P H P B NG VECT BIT (1)Ặ Ậ Ợ Ằ Ơ
•

Th ng đ c dùng khi t p h p c a ta là 1 t p con c a t p ườ ượ ậ ợ ủ ậ ủ ậ
s nguyên, có giá tr t 0 n-1. Khi đó ta s dùng 1 m ng các ố ị ừ ẽ ả
bit có kích th c n đ l u tr t p h p ướ ể ư ữ ậ ợ
•
N u i thu c t p h p thì ph n t th i c a m ng có giá tr 1 ế ộ ậ ợ ầ ử ứ ủ ả ị
•
VD: mu n l u tr các t p có giá tr ph n t t 0 9. Ta dùng ố ư ữ ậ ị ầ ử ừ
m ng có t i đa 10 ph n t .ả ố ầ ử
•
T p h p A={2,5,7,9} s đ c bi u di n b i:ậ ợ ẽ ượ ể ễ ở
0 1 2 3 4 5 6 7 8 9
0 0 1 0 0 1 0 1 0 1

Nguy n Văn Linhễ
CÀI T P H P Đ T B NG VECT BIT (2)Ậ Ợ Ặ Ằ Ơ
•
Khai báo
const Max_Length = 100; // giá tr ph n t l n nh t ị ầ ử ớ ấ
typedef int Set [Max_Length];
•
T o t p h p r ng:ạ ậ ợ ỗ
void Make_Null_Set (Set &a){
int i;
for(i=0;i<Max_Length;i++) a[i]=0;
}
•
T o h p c a 2 t p h pạ ợ ủ ậ ợ
void Set_Union (Set a,Set b,Set &c){
for (int i=0; i<Max_Length; i++)
if((a[i]==1)||(b[i]==1)) c[i]=1;

else c[i]=0;
}

Nguy n Văn Linhễ
CÀI Đ T T P H P B NG VECT BIT (3)Ặ Ậ Ợ Ằ Ơ
•
T o giao c a 2 t p h pạ ủ ậ ợ
void Set_Intersection(Set a,Set b,Set &c){
for (int i=0; i<Max_Length; i++)
if ((a[i]==1)&&(b[i]==1)) c[i]=1;
else c[i]=0;
}
•
T o hi u c a hai t p h pạ ệ ủ ậ ợ
void Set_Difference(Set a,Set b,Set &c){
for (int i=0; i< Max_Length; i++)
if ((a[i]==1)&& (b[i]==0)) c[i]=1;
else c[i]=0;
}

Nguy n Văn Linhễ
CÀI Đ T T P H P B NG VECT BIT (3)Ặ Ậ Ợ Ằ Ơ
•
Xét xem m t ph n t có thu c m t t p h p ộ ầ ử ộ ộ ậ ợ
hay không?
int Member (int i, Set a) {
if (i<0) || (i>Max_Length-1) return 0;
return a[i]==1;
}


Nguy n Văn Linhễ
CÀI Đ T T P H P B NG VECT BIT (3)Ặ Ậ Ợ Ằ Ơ
•
Cài đ t H p c a 2 t p h p b ng cách dùng ặ ợ ủ ậ ợ ằ
hàm member
void Set_Union (Set a,Set b,Set &c){
int i;
for (i=0;i<Max_Length;i++)
if (Member(i,a) || Member(i,b)) c[i]=1;
else c[i]=0;
}

Nguy n Văn Linhễ
CÀI Đ T T P H P B NG VECT BIT (3)Ặ Ậ Ợ Ằ Ơ
•
Xen m t ph n t i vào trong t p h p aộ ầ ử ậ ợ
void Insert_Set (int i, Set &a){
if ((i<0) || (i>Max_Length-1))
printf(“Gia tri khong hop le\n”);
else a[i]=1;
}

Nguy n Văn Linhễ
CÀI Đ T T P H P B NG VECT BIT (3)Ặ Ậ Ợ Ằ Ơ
•
Xoá m t ph n t i trong t p h p aộ ầ ử ậ ợ
void Delete_Set (int i, Set &a){
if ((i<0) || (i>Max_Length-1))
printf(“Gia tri khong hop le\n”);
else a[i]=0;

}

Nguy n Văn Linhễ
ĐÁNH GIÁ PH NG PHÁP CÀI Đ T ƯƠ Ặ
T P H P B NG VECT BITẬ Ợ Ằ Ơ
•
u đi m:Ư ể
–
D cài đ t.ễ ặ
–
Th c hi n nhanhự ệ
•
Nh c đi m:ượ ể
–
Không th bi u di n cho các t p h p có s ể ể ễ ậ ợ ố
l ng ph n t l n b t kỳ.ượ ầ ử ớ ấ

Nguy n Văn Linhễ
CÀI Đ T T P H P B NG DSLK(1)Ặ Ậ Ợ Ằ
•
Khai báo
typedef int Element_Type;
typedef struct Node
{
Element_Type Data;
Node * Next;
};
typedef Node * Position;
typedef Position Set;


Nguy n Văn Linhễ
CÀI Đ T T P H P B NG DSLK (2)Ặ Ậ Ợ Ằ
•
Ki m tra m t ph n t có thu c t p không?ể ộ ẩ ử ộ ậ
int Member(Element_Type X, Set S){
Position P;
int Found = 0;
P = S;
while ((P->Next != NULL) && (!Found))
if (P->Next->Data == X) Found = 1;
else P = P->Next;
return Found;
}

Nguy n Văn Linhễ
CÀI Đ T T P H P B NG DSLK(3)Ặ Ậ Ợ Ằ
•
Thêm m t ph n t vào t pộ ầ ử ậ
void Insert_Set(Element_Type X, Set &S){
Position T,P;
int Finish=0;
int Found=0;
P=S;
while ((P->Next!=NULL)&&(!Finish) &&(!Found))
if (P->Next->Data = X) Found = 1;
else if (P->Next->Data<X) P=P->Next;
else Finish=1;
// Neu X khong ton tai trong S thi xen X vao vi tri P
if(!Found) {
T=(Node*)malloc(sizeof(Node));

T->Data=X;
T->Next=P->Next;
P->Next=T;
}
}

Nguy n Văn Linhễ
CÀI Đ T T P H P B NG DSLK(4)Ặ Ậ Ợ Ằ
•
Xóa m t ph n t kh i t pộ ầ ử ỏ ậ
void Delete_Set(Element_Type X, Set &S)
{
Position T,P=S;
int Found=0;
while ((P->Next!=NULL)&& (!Found))
if (P->Next->Data==X) Found =1;
else P=P->Next;
if (Found){
T=P->Next;
P->Next=T->Next;
free(T);
}
}

Nguy n Văn Linhễ
CÀI Đ T T P H P B NG DSLK(5)Ặ Ậ Ợ Ằ
•
H p c a hai t p h pợ ủ ậ ợ
void Set_Union(Set A, Set B, Set &C)
{ Position P;

Make_Null_Set(C);
P= A;
while (P->Next!=NULL) {
Insert_Set (P->Next->Data,C);
P=P->Next;
}
P=B;
while (P->Next != NULL){
if (!Member(P->Next->Data,A))
Insert_Set (P->Next->Data,C);
P=P->Next;
}
}

Nguy n Văn Linhễ
CÀI Đ T T P H P B NG DSLK(6)Ặ Ậ Ợ Ằ
•
Tìm giao
void Set_Intersection(Set A, Set B, Set &C)
{
Position P;
Make_Null_Set(C);
P=A;
while (P->Next!=NULL){
if (Member(P->Next->Data,B))
Insert_Set (P->Next->Data,C);
P=P->Next;
}
}


Nguy n Văn Linhễ
CÀI Đ T T P H P B NG DSLK(7)Ặ Ậ Ợ Ằ
•
Tìm Hi uệ
void Set_Difference(Set A, Set B, Set &C)
{
Position P;
Make_Null_Set(C);
P= A;
while (P->Next!=NULL){
if (!Member(P->Next->Data,B))
Insert_Set (P->Next->Data,C);
P=P->Next;
}
}

Nguy n Văn Linhễ
ĐÁNH GIÁ PH NG PHÁP CÀI Đ T ƯƠ Ặ
T P H P B NG DSLKẬ Ợ Ằ
•
u đi m: Có th bi u di n cho m t t p Ư ể ể ể ễ ộ ậ
h p b t kỳ, s l ng ph n t không h n ợ ấ ố ượ ầ ử ạ
ch .ế
•
Nh c đi m: T c đ th c hi n ch mượ ể ố ộ ự ệ ậ

Nguy n Văn Linhễ
BÀI T PẬ
•
Vi t các khai báo c u trúc d li u và các ế ấ ữ ệ

th t c/hàm cho các phép toán trên t p h p ủ ụ ậ ợ
đ cài đ t t p h p kí t (256 kí t ASCII) ể ặ ậ ợ ự ự
b ng vect bit.ằ ơ

Nguy n Văn Linhễ
T ĐI NỪ Ể
•
Khái ni m: là m t t p h p mà ta không quan tâm đ n các ệ ộ ậ ợ ế
phép toán h p, giao và hi u c a 2 t p h pợ ệ ủ ậ ợ
•
Do trong m t s ng d ng, ch s d ng các phép toán ộ ố ứ ụ ỉ ử ụ
Insert_Set, Delete_Set và Member
•
Có th cài đ t t đi n b ng:ể ặ ừ ể ằ
–
Véct-bít
–
Danh sách liên k t có th t ho c không th tế ứ ự ặ ứ ự
–
M ng có kích th c c đ nh v i con nháy ch đ n v trí cu i ả ướ ố ị ớ ỉ ế ị ố
cùng (T ng t cài đ t danh sách b ng m ng)ươ ự ặ ằ ả
–
B ng bămả