Trên quan điểm của cấu trúc dữ liệu, một tập hợp là một nhóm không có thứ tự các phần tử, trên đó định nghĩa các phép toán cơ bản: phép giao hai tập hợp S1, S2, ký hiệu S1 S2, là một tập hợp có các phần tử thuộc hai tập hợp đó. Hợp của S1, S2, ký hiệu S1 S2, là tập hợp có các phần tử thuộc S1, thuộc S2, hay thuộc cả hai tập hợp đó. Hiệu của S1, S2, ký hiệu S1-S2, là tập hợp gồm các phần tử thuộc S1 nhưng không thuộc S2. Giản đồ Venn (hình 1) là sự minh họa trực quan cho những phép toán này.

Tập hợp là kiểu dữ liệu tiền định trong một số ngôn ngữ lập trình bậc cao, nhưng hầu hết chúng đều có những hạn chế về kiểu và số lượng các phần tử. Đơn cử như trong ngôn ngữ lập trình Pascal, kiểu phần tử của một tập hợp chỉ có thể là kiểu có thứ tự (Ordinal type), và có số lượng không quá 256. Dễ nhận thấy rằng tập hợp được sử dụng rất nhiều trong các thuật toán quan trọng, việc sử dụng chúng làm cho thuật toán trở nên “gọn gàng” và “sáng sủa”, mà các thuật toán trên đồ thị là một ví dụ. Chính vì lẽ đó ta sẽ cài đặt tập hợp trở thành một cấu trúc dữ liệu mềm dẻo hơn, chấp nhận các phần tử có kiểu bất kỳ phù hợp với yêu cầu của nhiều bài toán. Có nhiều phương pháp cài đặt tập hợp với đặc trưng về hiệu xuất của các phép toán khác nhau, như phương pháp vector bit, bảng băm” Chúng ta sẽ xem sét một cài đặt tập hợp bằng danh sách móc nối. Bằng cách này cấu trúc của một tập hợp được mô tả nhưhình 2.

Dưới đây trình bày cài đặt tập hợp bằng C++, trong Borland Turbo C++ 4.5 for windows hoặc trong TC++3.0 bạn xây dựng tệp TAPHOP.H có nội dung như sau:

#include "stdio.h"

#include "conio.h"

#include "dos.h"

#include "memory.h"

#include "malloc.h"

typedef struct node

{

void*element;

node*link;

};

typedef struct SET

{

unsigned int size;

node*data;

};

//** thu tuc khoi tao tap hop rong **//

voidinit( SET&s, unsigned int sizeset)

{

s.size=sizeset;

s.data=NULL;

}

//** kiem tra tap hop rong **//

intempty( SETs)

{

return (s.data==NULL);

}

//** ham kiem tra mot doi tuong co thuoc tap hop khong **//

int in (SET s, void *item)

{

node *p; int result=0;

p=s.data;

while ((p != NULL)&&(!result))

{

if (!memcmp(p->element,item,s.size)) result=1;

p=p->link;

}

return result;

}

//** ham them mot phan tu vao tap hop **//

int add(SET &s, void *item)

{

node *p, *tg;

int result=0;

if (in(s,item))

result=0;

else

{

tg= new(node);

tg->element= malloc(s.size);

movedata(FP_SEG(item),FP_OFF(item),FP_SEG(tg->element),FP_OFF(tg->element),s.size);tg->link = s.data;

s.data= tg;

result= 1;

}

return result;

}

//** phep loai bo mot phan tu khoi tap hop **//

int remove(SET &s,void*item)

{

node *p,*q;

int result =1, found=0 ;

if(!in(s,item) )

result=0;

else

{

p=s.data;

while ((p!=NULL)&&(!found))

{

if (!memcmp(p->element,item,s.size)) found=1;

else

p=p->link;

}

if (result)

{

q=s.data;

if (q==p) // xoa nut dau

{

s.data=p->link;

free (p->element);

delete (p);

}

else // xoa nut giua

{

while (q->link!=p)

q=q->link;

q->link=p->link;

free (p->element);

delete (p);

}

}

}

return result;

}

//** phep xoa mot tap hop **//

void deleteset(SET &s)

{

node *p,*tg;

p=s.data;

while (p != NULL )

{

tg=p;

p=p->link;

free (tg->element);

delete (tg);

}

s.data=NULL;

}

// ** phep gan tap s1 cho tap s2 **//

void assign(SET s1, SET &s2)

{

node *p;

deleteset(s2);

p=s1.data;

while (p !=NULL)

{

add(s2,p->element);

p=p->link;

}

}

//** toan tu hop cua hai tap hop **//

SET operator || (SET s1, SET s2)

{

SET tem; node *p;

init(tem,s1.size);

assign(s2,tem);

p=s1.data;

while (p !=NULL)

{

add(tem,p->element);

p=p->link;

}

return tem;

}

// ** toan tu giao cua hai tap hop**//

SET operator && (SET s1, SET s2)

{

SET tem; node *p;

init(tem,s1.size);

p=s1.data;

while (p != NULL)

{

if ( in(s2,p->element) )add(tem,p->element);

p=p->link;

}

return tem;

}

//** toan tu tru tap hop s1 cho tap hop s2 **//

SET operator - (SET s1, SET s2)

{

SET tem; node *p;

init(tem,s1.size);

p=s1.data;

while (p !=NULL )

{

if ( !in(s2,p->element)) add(tem,p->element);

p=p->link;

}

return tem;

}

Cấu trúc dữ liệu SET cài đặt ở trên chấp nhận các phần tử có kiểu bất kỳ, có nghĩa là ta có thể khai báo một tập hợp của các số phức, vector, ma trận hay thậm chí là tập hợp. Các bạn có thể thực hiện cài đặt này trong các môi trường lập trình khác nhau. Trong Visual C++, với một sự thay đổi nhỏ là ta dùng hàm memcpy(item,(tg->element),s.size), thay cho hàm movedata(FP_SEG(item),FP_OFF(item),FP_SEG(tg->element),FP_OFF(tg->element),s.size), còn trong Pascal hay Delphi ta sử dụng kỹ thuật “đối không kiểu”.

Ví dụ áp dụng:Ta cài đặt thuật toán sàng Eratosthens để tìm các số nguyên tố bằng tập hợp.

#include "stdio.h"

#include "conio.h"

#include "taphop.h"

const intnumber = 1000;

void main()

{

SET sang, nguyento; int i,j;

init(nguyento,sizeof(int)); init(sang,sizeof(int));

for (i=2;i<=number;i++) add(sang,&i);

i=2;

while (!empty(sang))

{

while ((i<=number)&&(!in(sang,&i))) i=i+1;

add(nguyento,&i);

j=i;

while (j<=number)

{

remove(sang,&j);

j=j+i;

}

}

for (i=1; i<=number;i++) // hienthi

if (in(nguyento,&i))

{

printf("%4d ",i); remove(nguyento,&i);

}

}

“Tôi thấy, nhưng tôi không tin” - George Cantor. Để có thể hiểu thấu đáo, thấy được ứng dụng của cấu trúc đữ liệu trên; không có cách nào tốt hơn là chúng ta hãy cài đặt và sử dụng nó. Chúc các bạn thành công!

Bùi Văn Tân

School@net (Theo THNT)