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.
#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))
{
}
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);
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))
{
else
}
if (result)
{
q=s.data;
if (q==p)
{
delete (p);
}
else
{
delete (p);
}
}
}
return result;
}
//** phep xoa mot tap hop **//
void deleteset(SET &s)
{
node *p,*tg;
p=s.data;
while (p != NULL )
{
tg=p;
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)
{
}
}
//** toan tu hop cua hai tap hop **//
{
SET tem; node *p;
init(tem,s1.size);
assign(s2,tem);
p=s1.data;
while (p !=NULL)
{
}
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)
{
}
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 )
{
}
return tem;
}
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++)
if (in(nguyento,&i))
{
printf(“%4d “,i); remove(nguyento,&i);
}
}
Bùi Văn Tân
School@net (Theo THNT)