Bài giảng Cấu trúc Dữ liệu và giải thuật - Chương 6: Tập hợp (Set) - Nguyễn Thị Xuân Hương

Nội dung text: Bài giảng Cấu trúc Dữ liệu và giải thuật - Chương 6: Tập hợp (Set) - Nguyễn Thị Xuân Hương

1. TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG KHOA CÔNG NGHỆ THÔNG TIN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Ths. Nguyễn Thị Xuân Hương 1
2. Chương 6: TẬP HỢP (SET) 6.1. Định nghĩa tập hợp và các phép toán cơ bản trên tập hợp - Định nghĩa: là tập hữu hạn các phần tử phân biệt có cùng kiểu dữ liệu. Ví dụ: A = {1,4,5,7,8} B = {xanh, đỏ, vàng, trắng, đen} -Một số phép toán cơ bản trên tập hợp: Phép kiểm tra xem một phần tử có thuộc tập hợp không, phép chèn thêm một phần tử, Phép loại bỏ một phần tử. Phép giao phép hợp, phép lấy hiệu hai tập hợp 2
3. Chương 6: TẬP HỢP 6.2. Biểu diễn dữ liệu tập hợp •Biểu diễn dữ liệu bằng vector bít: Giả sử: ta coi có một tập vũ trụ V (gồm các phần tử 0,1,2, )bao gồm tất cả các phần tử có thể có của tập hợp Một tập hợp gồm n phần tử được biểu diễn bằng một mảng Ele có n phần tử. Khi đó nếu phần tử thứ i thuộc tập hợp Ele[i] =1 và ngược lại nếu phần tử thứ i không thuộc tập hợp sẽ có Ele[i] =0 define MAXS 100; typedef struct SET { int n; //số phần tử của tập hợp int Ele[ MAXS]; }; SET A; 3
4. Chương 6: TẬP HỢP 6.2. Biểu diễn dữ liệu tập hợp •Biểu diễn dữ liệu bằng vector bít: Giả sử: ta coi có một tập vũ trụ V (gồm các phần tử 0,1,2, )bao gồm tất cả các phần tử có thể có của tập hợp Một tập hợp gồm n phần tử được biểu diễn bằng một mảng ele có n phần tử. Khi đó nếu phần tử thứ i thuộc tập hợp ele[i] =1 và ngược lại nếu phần tử thứ i không thuộc tập hợp sẽ có ele[i] =0 4
5. Chương 6: TẬP HỢP 6.2. Biểu diễn dữ liệu tập hợp •Biểu diễn dữ liệu bằng vector bít: define MAXS 100; typedef struct SET { int n; //số phần tử của tập hợp int ele[ MAXS]; }; SET A; VD: Tập A = {1,4,5,7,8} -> vector bit được lưu trữ như sau: 0 1 2 3 4 5 6 7 8 99 0 1 0 0 1 1 0 1 0 0 0 5
6. Chương 6: TẬP HỢP 6.2. Biểu diễn dữ liệu tập hợp 6.2.2. Biểu diễn bằng mảng các phần tử: mỗi phần tử của tập hợp chính là một phần tử của mảng. typedef KeyType ElementType; define MAXS 100; typedef struct SET { int n; ElementType item[MAXS]; } SET A; VD: Tập A = {1,4,5,7,8} Mảng các phần tử: 0 1 2 3 4 1 4 5 7 8 6
7. Chương 6: TẬP HỢP 6.2. Biểu diễn dữ liệu tập hợp 6.2.3. Biểu diễn bằng cấu trúc tự trỏ (Lưu trữ móc nối) Sử dụng danh sách liên kết trong đó mỗi phần tử của tập hợp là một nút của danh sách typedef KeyType ElementType; typedef struct NODE { ElementType item; NODE *next; } NODE *first, *last; VD: Tập A = {1,4,5,7,8} => Danh sách chứa các phần tử của tập hợp: 1 next 4 next 5 next 7 next 8 next NULL First Last 7
8. Chương 6: TẬP HỢP 6.2. Biểu diễn dữ liệu tập hợp ; Thảo luận: Tại sao lại cần sử dụng CTDL tập hợp? Các phép toán cơ bản trên tập hợp sẽ được thực hiện như thế nào với các cách biểu diễn trên? Ưu, nhược điểm của từng phương pháp? 8
9. Chương 6: TẬP HỢP 6.3. Các phép toán trên tập hợp biểu diễn bằng vector bít: define MAXS 100; typedef struct SET { int n; int Ele[ MAXS]; }; SET A; 9
10. Chương 6: TẬP HỢP 6.3. Một số phép toán cơ bản trên tập hợp biểu diễn bằng vector bít: - Khởi tạo - Kiểm tra một phần tử có thuộc tập hợp k? - Thêm một phần tử vào tập hợp - Loại bỏ một phần tử - Hợp - Giao - Hiệu hai tập hợp 10
11. Chương 6: TẬP HỢP 6.3. Một số phép toán cơ bản trên tập hợp biểu diễn bằng vector bít 1. Phép Khởi tạo: Khởi tập tập hợp rỗng void init ( SET &A) { A.n = 0; } 11
12. Chương 6: TẬP HỢP 6.3. Một số phép toán cơ bản trên tập hợp biểu diễn bằng vector bít 2. Phép kiểm tra thuộc: int in ( SET A, int x ) { return ( A.Ele[x] = 1 ) } 12
13. Chương 6: TẬP HỢP 6.3. Một số phép toán cơ bản trên tập hợp biểu diễn bằng vector bít 3. Phép thêm một phần tử vào tập hợp: thêm một phần tử vào tập (sao cho nó là duy nhất) Giải thuật: Thêm phần tử x vào tập hợp nếu nó chưa có mặt trong đó void insert (SET &A, int x ) { if (!in(A,x)) { A.n++; A.Ele[x] =1; } } Độ phức tạp thủ tục: O(3) 13
14. Chương 6: TẬP HỢP 6.3. Một số phép toán cơ bản trên tập hợp biểu diễn bằng vector bít 4. Phép loại bỏ phần tử x khỏi tập hợp Giải thuật: Nếu x thuộc tập hợp -> Xóa x void remove (SET &A, int x) { if (in(A,x) ) { A.Ele[x] = 0; A.n ; } } Độ phức tạp thủ tục: O(3) 14
15. Chương 6: TẬP HỢP 6.3. Một số phép toán cơ bản trên tập hợp biểu diễn bằng vector bít 5. Phép hợp hai tập hợp Input : cho hai tập hợp A và B Output: Tập C gồm các phần tử có mặt ở A hoặc B Giải thuật: Sử dụng phép OR với hai vector bit 15
16. Chương 6: TẬP HỢP 6.3. Một số phép toán cơ bản trên tập hợp biểu diễn bằng vector bít 5. Phép hợp của hai tập hợp SET union (SET A, SET B) { C.n=0; for (i =0; i< MAXS; i++) { C.Ele[i] = A.Ele[i] || B.Ele[i] ; if (C.Ele[i] !=0 ) C.n ++; } return C; } Độ phức tạp thủ tục: O(n) với n là số phần tử tối đa có thể có của tập hợp ( = MAXS) 16
17. Chương 6: TẬP HỢP 6.3. Một số phép toán cơ bản trên tập hợp biểu diễn bằng vector bít 6. Phép giao của hai tập hợp Input : cho hai tập hợp A và B Output: Tập C gồm các phần tử có mặt trong cả A và B Giải thuật: Sử dụng phép AND với hai vector bit 17
18. Chương 6: TẬP HỢP 6.3. Một số phép toán cơ bản trên tập hợp biểu diễn bằng vector bít 6. Phép giao của hai tập hợp SET intersection (SET A, SET B) { C.n=0; for (i =0; i< MAXS; i++) { C.Ele[i] = A.Ele[i] && B.Ele[i] ; if (C.Ele[i] !=0 ) C.n ++; } return C; } Độ phức tạp thủ tục: O(n) với n là số phần tử tối đa có thể có của tập hợp ( = MAXS) 18
19. Chương 6: TẬP HỢP 6.3. Một số phép toán cơ bản trên tập hợp biểu diễn bằng vector bít 7. Phép hiệu của hai tập hợp Input : cho hai tập hợp A và B Output: Tập C gồm các phần tử chỉ có trong A và không có trong B Giải thuật: Sử dụng phép AND của vector bit thứ nhất với phần bù của vector bit thứ 2. 19