Tổng quan,khái niệm,kiểu dữ liệu và cài đặt tập hợp
Mục tiêu Sau khi học xong chương này, sinh viên phải: - Nắm vững khái niệm về kiểu dữ liệu trừu tượng tập hợp và một số loại tập hợp đặc biệt như từ điển, bảng băm, hàng ưu tiên. - Cài đặt tập hợp và ...
Mục tiêu
Sau khi học xong chương này, sinh viên phải:
- Nắm vững khái niệm về kiểu dữ liệu trừu tượng tập hợp và một số loại tập hợp đặc biệt như từ điển, bảng băm, hàng ưu tiên.
- Cài đặt tập hợp và các loại tập hợp đặc biệt bằng ngôn ngữ lập trình cụ thể.
Kiến thức cơ bản cần thiết
Để học tốt chương này, sinh viên cần biết lập trình căn bản như:
- Kiểu mẩu tin (record) , kiểu mảng (array) và kiểu con trỏ (pointer).
- Các cấu trúc điều khiển, lệnh vòng lặp.
- Lập trình theo từng modul (chương trình con) và cách gọi chương trình con đó.
- Lập trình đệ qui và gọi đệ qui.
- Kiểu dữ liệu trừu tượng danh sách .
Tài liệu tham khảo
[1] Aho, A. V. , J. E. Hopcroft, J. D. Ullman. "Data Structure and Algorihtms", Addison–Wesley; 1983
[2] Đỗ Xuân Lôi . "Cấu trúc dữ liệu và giải thuật". Nhà xuất bản khoa học và kỹ thuật. Hà nội, 1995. (chương 10- Trang 300)
[3] Nguyễn Trung Trực, "Cấu trúc dữ liệu". BK tp HCM, 1990. (Chương 6 –trang 397)
[4] Lê Minh Trung ; “Lập trình nâng cao bằng pascal với các cấu trúc dữ liệu “; 1997 (chương 9)
Nội dung cốt lõi
Trong chương này chúng ta sẽ nghiên cứu các vấn đề sau:
- Khái niệm tập hợp
- Kiểu dữ liệu trừu tượng tập hợp.
- Cài đặt tập hợp
- Từ điển
- Cấu trúc bảng băm
- Hàng ưu tiên.
Tập hợp là một khái niệm cơ bản trong toán học. Tập hợp được dùng để mô hình hoá hay biểu diễn một nhóm bất kỳ các đối tượng trong thế giới thực cho nên nó đóng vai trò rất quan trọng trong mô hình hoá cũng như trong thiết kế các giải thuật.
Khái niệm tập hợp cũng như trong toán học, đó là sự tập hợp các thành viên (members) hoặc phần tử (elements). Tất cả các phần tử của tập hợp là khác nhau. Tập hợp có thể có thứ tự hoặc không có thứ tự, tức là, có thể có quan hệ thứ tự xác định trên các phần tử của tập hợp hoặc không. Tuy nhiên, trong chương này, chúng ta giả sử rằng các phần tử của tập hợp có thứ tự tuyến tính, tức là, trên tập hợp S có quan hệ < và = thoả mản hai tính chất:
Với mọi a,b ∈ S thì a<b hoặc b<a hoặc a=b
Với mọi a,b,c ∈ S, a<b và b<c thì a<c
Cũng như các kiểu dữ liệu trừu tượng khác, các phép toán kết hợp với mô hình tập hợp sẽ tạo thành một kiểu dữ liệu trừu tượng là rất đa dạng. Tùy theo nhu cầu của các ứng dụng mà các phép toán khác nhau sẽ được định nghĩa trên tập hợp. Ở đây ta đề cập đến một số phép toán thường gặp nhất như sau
- Thủ tục UNION(A,B,C) nhận vào 3 tham số là A,B,C; Thực hiện phép toán lấy hợp của hai tập A và B và trả ra kết quả là tập hợp C = A B.
- Thủ tục INTERSECTION(A,B,C) nhận vào 3 tham số là A,B,C; Thực hiện phép toán lấy giao của hai tập A và B và trả ra kết quả là tập hợp C = A B.
- Thủ tục DIFFERENCE(A,B,C) nhận vào 3 tham số là A,B,C; Thực hiện phép toán lấy hợp của hai tập A và B và trả ra kết quả là tập hợp C = AB
- Hàm MEMBER(x,A) cho kết quả kiểu logic (đúng/sai) tùy theo x có thuộc A hay không. Nếu x ∈ A thì hàm cho kết quả là 1 (đúng), ngược lại cho kết quả 0 (sai).
- Thủ tục MAKENULLSET(A) tạo tập hợp A tập rỗng
- Thủ tục INSERTSET(x,A) thêm x vào tập hợp A
- Thủ tục DELETESET(x,A) xoá x khỏi tập hợp A
- Thủ tục ASSIGN(A,B) gán A cho B ( tức là B:=A )
- Hàm MIN(A) cho phần tử bé nhất trong tập A
- Hàm EQUAL(A,B) cho kết quả TRUE nếu A=B ngược lại cho kết quả FALSE
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:
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.
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;
}
