Chương 4
CÁC PHÉP TOÁN CƠ BẢN
TRÊN TẬP HỢP
N.C.Danh
NỘI DUNG SẼ HỌC
• 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
KHÁI NIỆM TẬP HỢP
•Làtập hợp các thành viên (members) hoặc phần tử
(elements)
•Các phần tử của tập hợp phải khác nhau
•Các phần tử của tập hợp có quan hệ tuyến tính, 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
BIỂU DIỄN TẬP HỢP
•Liệt kê các phần tử trong cặp dấu ngoặc {}
•x
∈
S : x là một thành viên của tập hợp S
•x
∉
S : x không là một thành viên 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}
• Cho hai tập hợp A và B:

DELETESET(
x, A
)
Xóa x khỏi tập A
ASSIGN(
A, B
)
Gán B=A
MIN(
A
)
Trả về phần tử nhỏ nhất trong tập hợp
EQUAL(
A,B
)
Trả về TRUE nếu A=B
UNION(
A,B,C
)
C=A∪B
INTERSECTION(
A,B,C
)
C=A∩B
DIFFERENCE(
A,B,C
)
C=A\B
MERGE(
A,B,C

else c[i]=0;
}
CÀI ĐẶT TẬP HỢP BẰNG VECTƠ BIT (3)
• Tìm giao
void SET_intersection(SET a,SET b,SET c){
int i;
for (i=0;i<maxlength;i++)
if((a[i]==1)&&(b[i]==1)) c[i]=1;
else c[i]=0;
}
• Tìm hiệu
void SET_difference(SET a,SET b,SET c){
int i;
for (i=0;i<maxlength;i++)
if((a[i]==1)&& !(b[i]==1)) c[i]=1;
else c[i]=0;
}
CÀI ĐẶT TẬP HỢP BẰNG DSLK(1)
• Khai báo
typedef int ElementType;
typedef struct Node
{
ElementType Data;
Node * Next;
};
typedef Node * Position;
typedef Position SET;//LIST
//typedef List SET;
CÀI ĐẶT TẬP HỢP BẰNG DSLK(2)
Tìm hợp

void InsertSET(ElementType X, SET L)
{ Position T,P;
int finish=0;
P=L;
while ((P->Next!=NULL)&&(finish==0))
if (P->Next->Data<=X)
P=P->Next;
else finish=1;
// P dang luu tru vi tri de xen phan tu X vao
T=(Node*)malloc(sizeof(Node));
T->Data=X;
T->Next=P->Next;
P->Next=T;
}
CÀI ĐẶT TẬP HỢP BẰNG DSLK(5)
•Xóa một phần tử khỏi tập
void DeleteSET(ElementType X, SET L)
{
Position T,P=L;
int finish=0;
while ((P->Next!=NULL)&& (finish==0))
if (P->Next->Data<=X) P=P->Next;
else finish=1;
if ((finish==1) && (P->Next->Data==X)){
T=P->Next;
P->Next=T->Next;
free(T);
}
}
CÀI ĐẶT TẬP HỢP BẰNG DSLK (6)

#define MaxLength //So phan tu toi da
typedef ElementType; //Kieu du lieu
typedef int Position;
typedef struct
{
ElementType Data[MaxLength];
Position Last;
} SET;
CÀI ĐẶT TỪ ĐIỂN BẰNG MẢNG (2)
•Khởi tạo rỗng
void MakeNullSET(SET *L){
(*L).Last=0;
}
•Hàm kiểm tra 1 phần tử có trong từ điển
không:
int Member(ElementType X, SET L){
Position P=1, Found=0;
while ((P <= (L.Last)) && (Found == 0))
if ((L.Data[P-1]) == X) Found = 1;
else P++;
return Found;
}
CÀI ĐẶT TỪ ĐIỂN BẰNG MẢNG (2)
• Thêm 1 phần tử vào từ điển:
void InsertSET(ElementType X, SET *L)
{ if (FullSET(*L))
printf("Tap hop day");
else if (Member(X,*L)==0)
{
(*L).Last++;

200
Chỉ
số
H(x)=x%B
BĂM ĐÓNG (1)
• 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];
BĂM ĐÓNG (2)
• 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;
}
BĂM ĐÓNG (1)
Thêm vào giá trị 29
19B-1
E
E…
266
E5
344
E3
E2