Giải thuật và lập trình - C: III. Cài đặt tập hợp
Giải phóng thời gian, khai phóng năng lực
III. CÀI ĐẶT TẬP HỢP
1. Cài đặt tập hợp bằng vector Bit
Hiệu quả của một cách cài đặt tập hợp cụ thể phụ thuộc vào các phép toán và kích thước tập hợp. Hiệu quả này cũng sẽ phụ thuộc vào tần suất sử dụng các phép toán trên tập hợp. Chẳng hạn nếu chúng ta thường xuyên sử dụng phép thêm vào và loại bỏ các phần tử trong tập hợp thì chúng ta sẽ tìm cách cài đặt hiệu quả cho các phép toán này. Còn nếu phép tìm kiếm một phần tử xảy ra thường xuyên thì ta có thể phải tìm cách cài đặt phù hợp để có hiệu quả tốt nhất.
Ở đây ta xét một trường hợp đơn giản là khi toàn thể tập hợp của chúng ta là tập hợp con của một tập hợp các số nguyên nằm trong phạm vi nhỏ từ 1.. n chẳng hạn thì chúng ta có thể dùng một mảng kiểu Boolean có n phần tử để cài đặt tập hợp (ta gọi là vectơ bít), bằng cách cho phần tử thứ i của mảng này giá trị TRUE nếu i thuộc tập hợp hoặc cho mảng lưu kiểu 0-1. Nếu nội dung phần tử trong mảng tại vị trí i là 1 nghĩa là i tồn tại trong tập hợp và ngược lại, nội dung là 0 nghĩa là phần tử i đó không tồn tại trong tập hợp.
Ví dụ: Giả sử các phần tử của tập hợp được lấy trong các số nguyên từ 1 đến 10 thì mỗi tập hợp được biểu diễn bởi một mảng một chiều có 10 phần tử với các giá trị phần tử thuộc kiểu logic. Chẳng hạn tập hợp A={1,3,5,8} được biểu diễn trong mảng có 10 phần tử như sau:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
Cách biểu diễn này chỉ thích hợp trong điều kiện là mọi thành viên của tất cả các tập hợp đang xét phải có giá trị nguyên hoặc có thể đặt tương ứng duy nhất với số nguyên nằm trong một phạm vi nhỏ. Có thể dễ dàng nhận thấy khai báo cài đặt như sau
const maxlength = 100;
// giá trị phần tử lớn nhất trong tập hợp số nguyên không âm
typedef int SET [maxlength];
Tạo một tập hợp rỗng
Để tạo một tập hợp rỗng ta cần đặt tất cả các nội dung trong tập hợp từ vị trí 0 đến vị trí maxlength đều bằng 0. Câu lệnh được viết như sau :
void makenull(SET a)
{
int i;
for(i=0;i<maxlength;i++)
a[i]=0;
}
Biểu diễn tập hợp bằng vectơ bít tạo điều kiện thuận lợi cho các phép toán trên tập hợp. Các phép toán này có thể cài đặt dễ dàng bằng các phép toán Logic trong ngôn ngữ lập trình. Chẳng hạn thủ tục UNION(A,B,C) và thủ tục INTERSECTION được viết như sau :
void SET_union (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;
}
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;
}
Các phép toán giao, hiệu,... được viết một cách tương tự. Việc kiểm tra một phần tử có thuộc tập hợp hay không, thủ tục thêm một phần tử vào tập hợp, xóa một phần tử ra khỏi tập hợp cũng rất đơn giản và xem như bài tập.
2. Cài đặt bằng danh sách liên kết
Tập hợp cũng có thể cài đặt bằng danh sách liên kết, trong đó mỗi phần tử của danh sách là một thành viên của tập hợp. Không như biểu diễn bằng vectơ bít, sự biểu diễn này dùng kích thước bộ nhớ tỉ lệ với số phần tử của tập hợp chứ không phải là kích thước đủ lớn cho toàn thể các tập hợp đang xét. Hơn nữa, ta có thể biểu diễn một tập hợp bất kỳ. Mặc dù thứ tự của các phần tử trong tập hợp là không quan trọng nhưng nếu một danh sách liên kết có thứ tự nó có thể trợ giúp tốt cho các phép duyệt danh sách. Chẳng hạn nếu tập hợp A được biểu diễn bằng một danh sách có thứ tự tăng thì hàm MEMBER(x,A) có thể thực hiện việc so sánh x một cách tuần tự từ đầu danh sách cho đến khi gặp một phần tử y ≥ x chứ không cần so sánh với tất cả các phần tử trong tập hợp.
Một ví dụ khác, chẳng hạn ta muốn tìm giao của hai tập hợp A và B có n phần tử. Nếu A,B biểu diễn bằng các danh sách liên kết chưa có thứ tự thì để tìm giao của A và B ta phải tiến hành như sau:
for (mỗi x thuộc A )
{ Duyệt danh sách B xem x có thuộc B không. Nếu có thì x thuộc giao của hai tập hợp A và B; }
Rõ ràng quá trình này có thể phải cần đến n x m phép kiểm tra (với n,m là độ dài của A và B).
Nếu A,B được biểu diễn bằng danh sách có thứ tự tăng thì đối với một phần tử eÎA ta chỉ tìm kiếm trong B cho đến khi gặp phần tử x ≥ e. Quan trọng hơn nếu f đứng ngay sau e trong A thì để tìm kiếm f trong B ta chỉ cần tìm từ phần tử x trở đi chứ không phải từ đầu danh sách lưu trữ tập hợp B.
Khai báo
typedef int ElementType;
typedef struct Node
{
ElementType Data;
Node * Next;
};
typedef Node * Position;
typedef Position SET;
Thủ tục UNION
//C= hop cua hai tap hop A,B
void UnionSET(SET A, SET B, SET *C)
{
Position p;
MakeNullSET(C);
p=First(A);
while (p!=EndSET(A))
{
InsertSET (Retrieve(p,A),*C);
p=Next(p,A);
}
p=First(B);
while (p!=EndSET (B))
{
if (Member(Retrieve(p,B),*C)==0) InsertSET (Retrieve(p,B),*C);
p=Next(p,B);
}
}
Thủ tục INTERSECTION
// C=giao cua hai tap hop A,B
void IntersectionSET(SET A, SET B, SET *C)
{
Position p;
MakeNullSET(C);
p=First(A);
while (p!=EndSET(A)){
if (Member(Retrieve(p,A),B)==1) InsertSET (Retrieve(p,A),*C);
p=Next(p,A);
}
}
Phép toán hiệu có thể viết tương tự (xem như bài tập). Phép ASSIGN(A,B) chép các các phần tử của tập A sang tập B, chú ý rằng ta không được làm bằng lệnh gán đơn giản B:=A vì nếu làm như vậy hai danh sách biểu diễn cho hai tập hợp A,B chỉ là một nên sự thay đổi trên tập này kéo theo sự thay đổi ngoài ý muốn trên tập hợp kia. Toán tử MIN(A) chỉ cần trả ra phần tử đầu danh sách (tức là A->Next->Data). Toán tử DELETESET là hoàn toàn giống như DELETE_LIST. Phép INSERTSET(x,A) cũng tương tự INSERT_LIST tuy nhiên ta phải chú ý rằng khi xen x vào A phải đảm bảo thứ tự của danh sách.
Thêm phần tử vào tập hợp
// Them phan tu vao tap hop co thu tu 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;
}
Xoá phần tử ra khỏi tập hợ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)
if(P->Next->Data==X){
T=P->Next;
P->Next=T->Next;
free(T);
}
}
Kiểm tra sự hiện diện của phần tử trong tập hợp:
Hàm kiểm tra xem phần tử X có thuộc tập hợp hay không. Hàm trả về giá trị 1 nếu phần tử X đó thuộc tập hợp và ngược lại, hàm trả về giá trị 0.
int Member(ElementType X, SET L)
{
Position P;
int Found = 0;
P = First(L);
while ((P != EndSET(L)) && (Found == 0))
if (Retrieve(P,L) == X) Found = 1;
else P = Next(P, L);
return Found;
}
Giải phóng thời gian, khai phóng năng lực