Tập hợp là một danh sách mà không có phần tử nào trùng nhau, không phân biệt thứ tự các phần tử. Vì thế, ta có thể cài đặc cấu trúc dữ liệu tập hợp bằng cách sử dụng lại cấu trúc danh sách liên kết.
Trong bài viết này, giả sử kiểu dữ liệu của Danh sách và Tập hợp là kiểu số nguyên
Xét lại cấu trúc danh sách liên kết:
Khai báo cấu trúc dữ liệu danh sách liên kết:
#include <stdio.h>
#include <malloc.h>
typedef int ElementType;
typedef struct Node{
ElementType Element;
Node* Next;
};
typedef Node* Position;
typedef Position List;
Khởi tạo danh sách rỗng & kiểm tra danh sách rỗng:
void MakeNullList(List &L){
L =(Node*)malloc(sizeof(Node));
L->Next = NULL;
}
int EmptyList(List L){
return (L->Next==NULL);
}
Thêm, xóa phần tử trong danh sách:
void InsertList(ElementType X, int p, List &L){
Node* T = (Node*)malloc(sizeof(Node));
Position P = i2p(p,L);
T->Element = X;
T->Next = P->Next;
P->Next = T;
}
void DeleteList(Position P, List &L){
if (L->Next!=NULL){
Position T=P->Next;
P->Next = T->Next;
free (T);
}
}
In danh sách:
void PrintList(List L){
Position P = L;
while(P->Next!=NULL){
printf("%d ",P->Next->Element);
P=P->Next;
}
}
Để sử dụng lại cấu trúc danh sách liên kết, ta cần lưu các thủ tục và hàm ở trên ra 1 file và đặt tên là thuvien_list.cpp
Tiếp theo, tạo 1 tập tin tên là tap_hop.cpp để cài đặt cấu trúc dữ liệu TapHop. Chú ý tập tin tap_hop.cpp phải cùng thư mục với tập tin thuvien_list.cpp
Viết code cho cấu trúc dữ liệu tập hợp:
Include thư viện danh sách liên kết
#include "thuvien_list.cpp"
Khai báo cấu trúc dữ liệu tập hợp: cũng là cấu trúc dữ liệu danh sách
typedef List Set;
Khởi tạo tập hợp rỗng & kiểm tra tập hợp rỗng: thực chất tập hợp rỗng và danh sách rỗng là như nhau nên ta sử dụng lại hàm MakeNullList và EmptyList để cài
void MakeNullSet(Set &S){
MakeNullList(S);
}
int EmptySet(Set S){
return EmptyList(S);
}
Hàm Member kiểm tra xem X có phải là thành viên thuộc tập hợp hay không?
int Member(ElementType X, Set S){
Position P = S;
while (P->Next!=NULL){
if (P->Next->Element == X)
return 1;
P=P->Next;
}
return 0;
}
Thêm phần tử X vào tập hợp S: tương tự như thêm 1 phần tử vào danh sách nhưng trước khi thêm phải kiểm tra xem X có thuộc S hay không? Nếu không thuộc (!Member) thì mới thêm. Phần tử mới sẽ được thêm vào đầu tập hợp
void InsertSet(ElementType X, Set &S){
if (!Member(X,S))
InsertList(X,1,S);
}
Xóa phần tử X vào tập hợp S: trước tiên phải xác định vị trí của phần tử X trong tập hợp S, gọi là P. Nếu P->Next!=NULL (tức là X có tồn tại trong tập S) thì ta thực hiện gọi hàm xóa phần tử tại vị trí P trong danh sách S
void DeleteSet(ElementType X, Set &S){
Position P = S;
while (P->Next!=NULL )
if (P->Next->Element == X)
break;
else
P=P->Next;
if (P->Next!=NULL)
DeleteList(P,S);
}
Phép giao 2 tập hợp A và B: kết quả trả về là tập hợp C. Ý tưởng cho phép giao là: lần lượt với từng phần tử Xi thuộc tập hợp A, thực hiện kiểm tra xem Xi thuộc tập hợp B không? Nếu thuộc thì Xi là phần tử giao của tập A và B và đưa Xi vào tập kết quả C.
Set Intersect(Set A,Set B){
Set C;
MakeNullSet(C);
while(A->Next!=NULL){
if (Member(A->Next->Element,B))
InsertSet(A->Next->Element,C);
A=A->Next;
}
return C;
}
Phép hợp 2 tập hợp A và B: kết quả trả về là tập hợp C. Ý tưởng cho phép hợp là: thêm tất cả phần tử thuộc tập A vào tập C, thêm tất cả phần tử thuộc tập B vào tập C.
Set Union(Set A, Set B){
Set C;
MakeNullSet(C);
while(A->Next!=NULL){
InsertSet(A->Next->Element,C);
A=A->Next;
}
while(B->Next!=NULL){
InsertSet(B->Next->Element,C);
B=B->Next;
}
return C;
}
Phép hiệu 2 tập hợp A và B: kết quả trả về là tập hợp C. Ý tưởng cho phép hiệu là: với từng phần tử Xi thuộc A, kiểm tra xem Xi có thuộc B hay không? Nếu không thuộc thì thêm Xi vào tập kết quả C
Set Except(Set A, Set B){
Set C;
MakeNullSet(C);
while(A->Next!=NULL){
if (!Member(A->Next->Element,B))
InsertSet(A->Next->Element,C);
A=A->Next;
}
return C;
}
In tập hợp: tương tự như in danh sách
void PrintSet(Set S){
PrintList(S);
}
Hàm main để kiểm tra các phép toán đã cài đặt:
int main(){
Set A;
MakeNullSet(A);
InsertSet(2,A);
InsertSet(7,A);
InsertSet(3,A);
DeleteSet(2,A);
Set B;
MakeNullSet(B);
InsertSet(3,B);
InsertSet(2,B);
InsertSet(1,B);
Set C = Intersect(A,B);
Set D = Union(A,B);
Set E = Except(A,B);
Set F = Except(B,A);
printf("\nTap A : ");
PrintSet(A);
printf("\nTap B : ");
PrintSet(B);
printf("\nTap C : ");
PrintSet(C);
printf("\nTap D : ");
PrintSet(D);
printf("\nTap E : ");
PrintSet(E);
printf("\nTap F : ");
PrintSet(F);
return 0;
}
Trong bài viết này, giả sử kiểu dữ liệu của Danh sách và Tập hợp là kiểu số nguyên
Xét lại cấu trúc danh sách liên kết:
Khai báo cấu trúc dữ liệu danh sách liên kết:
#include <stdio.h>
#include <malloc.h>
typedef int ElementType;
typedef struct Node{
ElementType Element;
Node* Next;
};
typedef Node* Position;
typedef Position List;
Khởi tạo danh sách rỗng & kiểm tra danh sách rỗng:
void MakeNullList(List &L){
L =(Node*)malloc(sizeof(Node));
L->Next = NULL;
}
int EmptyList(List L){
return (L->Next==NULL);
}
Thêm, xóa phần tử trong danh sách:
void InsertList(ElementType X, int p, List &L){
Node* T = (Node*)malloc(sizeof(Node));
Position P = i2p(p,L);
T->Element = X;
T->Next = P->Next;
P->Next = T;
}
void DeleteList(Position P, List &L){
if (L->Next!=NULL){
Position T=P->Next;
P->Next = T->Next;
free (T);
}
}
In danh sách:
void PrintList(List L){
Position P = L;
while(P->Next!=NULL){
printf("%d ",P->Next->Element);
P=P->Next;
}
}
Để sử dụng lại cấu trúc danh sách liên kết, ta cần lưu các thủ tục và hàm ở trên ra 1 file và đặt tên là thuvien_list.cpp
Tiếp theo, tạo 1 tập tin tên là tap_hop.cpp để cài đặt cấu trúc dữ liệu TapHop. Chú ý tập tin tap_hop.cpp phải cùng thư mục với tập tin thuvien_list.cpp
Viết code cho cấu trúc dữ liệu tập hợp:
Include thư viện danh sách liên kết
#include "thuvien_list.cpp"
Khai báo cấu trúc dữ liệu tập hợp: cũng là cấu trúc dữ liệu danh sách
typedef List Set;
Khởi tạo tập hợp rỗng & kiểm tra tập hợp rỗng: thực chất tập hợp rỗng và danh sách rỗng là như nhau nên ta sử dụng lại hàm MakeNullList và EmptyList để cài
void MakeNullSet(Set &S){
MakeNullList(S);
}
int EmptySet(Set S){
return EmptyList(S);
}
Hàm Member kiểm tra xem X có phải là thành viên thuộc tập hợp hay không?
int Member(ElementType X, Set S){
Position P = S;
while (P->Next!=NULL){
if (P->Next->Element == X)
return 1;
P=P->Next;
}
return 0;
}
Thêm phần tử X vào tập hợp S: tương tự như thêm 1 phần tử vào danh sách nhưng trước khi thêm phải kiểm tra xem X có thuộc S hay không? Nếu không thuộc (!Member) thì mới thêm. Phần tử mới sẽ được thêm vào đầu tập hợp
void InsertSet(ElementType X, Set &S){
if (!Member(X,S))
InsertList(X,1,S);
}
Xóa phần tử X vào tập hợp S: trước tiên phải xác định vị trí của phần tử X trong tập hợp S, gọi là P. Nếu P->Next!=NULL (tức là X có tồn tại trong tập S) thì ta thực hiện gọi hàm xóa phần tử tại vị trí P trong danh sách S
void DeleteSet(ElementType X, Set &S){
Position P = S;
while (P->Next!=NULL )
if (P->Next->Element == X)
break;
else
P=P->Next;
if (P->Next!=NULL)
DeleteList(P,S);
}
Phép giao 2 tập hợp A và B: kết quả trả về là tập hợp C. Ý tưởng cho phép giao là: lần lượt với từng phần tử Xi thuộc tập hợp A, thực hiện kiểm tra xem Xi thuộc tập hợp B không? Nếu thuộc thì Xi là phần tử giao của tập A và B và đưa Xi vào tập kết quả C.
Set Intersect(Set A,Set B){
Set C;
MakeNullSet(C);
while(A->Next!=NULL){
if (Member(A->Next->Element,B))
InsertSet(A->Next->Element,C);
A=A->Next;
}
return C;
}
Phép hợp 2 tập hợp A và B: kết quả trả về là tập hợp C. Ý tưởng cho phép hợp là: thêm tất cả phần tử thuộc tập A vào tập C, thêm tất cả phần tử thuộc tập B vào tập C.
Set Union(Set A, Set B){
Set C;
MakeNullSet(C);
while(A->Next!=NULL){
InsertSet(A->Next->Element,C);
A=A->Next;
}
while(B->Next!=NULL){
InsertSet(B->Next->Element,C);
B=B->Next;
}
return C;
}
Phép hiệu 2 tập hợp A và B: kết quả trả về là tập hợp C. Ý tưởng cho phép hiệu là: với từng phần tử Xi thuộc A, kiểm tra xem Xi có thuộc B hay không? Nếu không thuộc thì thêm Xi vào tập kết quả C
Set Except(Set A, Set B){
Set C;
MakeNullSet(C);
while(A->Next!=NULL){
if (!Member(A->Next->Element,B))
InsertSet(A->Next->Element,C);
A=A->Next;
}
return C;
}
In tập hợp: tương tự như in danh sách
void PrintSet(Set S){
PrintList(S);
}
Hàm main để kiểm tra các phép toán đã cài đặt:
int main(){
Set A;
MakeNullSet(A);
InsertSet(2,A);
InsertSet(7,A);
InsertSet(3,A);
DeleteSet(2,A);
Set B;
MakeNullSet(B);
InsertSet(3,B);
InsertSet(2,B);
InsertSet(1,B);
Set C = Intersect(A,B);
Set D = Union(A,B);
Set E = Except(A,B);
Set F = Except(B,A);
printf("\nTap A : ");
PrintSet(A);
printf("\nTap B : ");
PrintSet(B);
printf("\nTap C : ");
PrintSet(C);
printf("\nTap D : ");
PrintSet(D);
printf("\nTap E : ");
PrintSet(E);
printf("\nTap F : ");
PrintSet(F);
return 0;
}