I.Giới thiệu :
Trong bài này mình xin chia sẻ cách cài đặt môt tập hợp gồm có 32 phần từ ([0,31]) theo tư duy hướng đối tượng.
Thoạt nhìn chúng ta dễ dàng nhận thấy số phần tử trong khoảng 0 – 31 trùng với chỉ số chứa phần tử(32 phần tử) trong mảng, do đó nếu dùng mảng kiểu số nguyên thì phí tổn khá cao, hơn nữa sẽ tốn Phí tổn đến n^2 độ phức tạp khi chúng ta làm các thao tác trên Tập hợp, do vậy có một cách tốt hơn, là chúng ta sử dụng dãy Bit 32 phần tử, và khi có 1 phần tử nào đc thêm vào thi bit này sẽ bật lên 1.
II. Coding :
Các Mở Visual Studio 6.0 lên và tạo Windows Console Application
Tạo 2 File : BitSet32.h và BitSet32. Cpp và Main.CPP để thực thi.
Tiếp theo chúng ta cài đặt lớp BitSet32 trong file BitSet32.h như sau :
1: /*Phat Trien bai tap hop thanh BitSet256 dùng day bit*/
2: #ifndef _BitSet32_H
3: #define _BitSet32_H
4: class BitSet32
5: {
6: //tap hop cac so nguyen thuoc [0,31]
7: private:
8: unsigned int Data;
9: private:
10: BitSet32(unsigned int x);
11: public:
12: static const int MIN,MAX ;
13: public :
14: BitSet32();
15: // PTTL gom mot mang va so phan tu
16: BitSet32(const int * pData, int num);
17: friend istream& operator>>(istream& is, BitSet32& p);
18: friend ostream& operator<<(ostream& os, BitSet32 p);
19: BitSet32 operator|(BitSet32 p)const ;
20: BitSet32 operator&(BitSet32 b) const ; //Giao
21: BitSet32 operator-(BitSet32 b) const ;
22: void RemoveAll();
23: bool IsSubSetOf(BitSet32 b) const ; // kiem tra tap hop la con cua tap hop #
24: bool Add(int x);
25: bool Contain(int x) const ;
26: bool InRange(int x) const;
27: };
28: #endif
vậy là xong phần cài đặt, tiếp theo chúng ta định nghĩa các thao tác trên BitSet32 trong file BitSet32.cpp
1: #include <iostream.h>
2: #include "BitSet32.h"
3: const int BitSet32::MAX = 32 ;
4: const int BitSet32::MIN = 0;
5: istream& operator>>(istream&is , BitSet32& p)
6: {
7: int x ;
8: p.Data = 0;
9: cout << "Nhap cac phan tu(nhap -1 de thoat): " ;
10: do{
11: is >> x ;
12: }while(p.Add(x));
13: return is;
14: }
15: ostream& operator<< (ostream& os, BitSet32 p)
16: {
17: os << "{ " ;
18: for(int i = BitSet32::MIN ; i <= BitSet32::MAX; i ++ )
19: if(p.Contain(i)) os << i << "," ;
20: os << "\b }" ;
21: return os ;
22: }
23: BitSet32::BitSet32()
24: {
25: // Khoi tao tat ca cac bit = 0-> Tap hop rong
26: Data = 0;
27: }
28: BitSet32::BitSet32(unsigned int x)
29: {
30: Data = x ;
31: }
32: BitSet32::BitSet32(const int* pData, int num)
33: {
34: // Tao tap hop tu day so lieu cho trc
35: Data = 0;// Tao tap hop Rong
36: for(int i = 0; i < num; i ++) Add(pData[i]);
37: }
38: bool BitSet32::InRange(int x) const
39: {
40: // x nam trong khoang Min - Max
41: return x >= BitSet32::MIN && x <= BitSet32::MAX ;
42: }
43: bool BitSet32::Add(int x)
44: {
45: if(BitSet32::InRange(x))
46: {
47: Data = Data|(1 << x) ;
48: return true ;
49: }
50: return false ;
51: }
52: bool BitSet32::Contain(int x) const
53: {
54: if(BitSet32::InRange(x))
55: {
56: return ((Data&(1 << x)) != 0);
57: }
58: return false ;
59: }
60: void BitSet32::RemoveAll()
61: {
62: Data = 0;
63: }
64: BitSet32 BitSet32::operator &(BitSet32 b) const
65: {
66: return BitSet32(Data &b.Data);
67: }
68: BitSet32 BitSet32::operator -(BitSet32 b) const
69: {
70: return BitSet32(Data &~b.Data);
71: }
72: BitSet32 BitSet32::operator |(BitSet32 b) const
73: {
74: return BitSet32(Data|b.Data);
75: }
76: bool BitSet32::IsSubSetOf(BitSet32 b) const
77: {
78: return (Data& b.Data) == Data ;
79: // Neu A la con cua B thi A giao B = A
80: }
Sau khi Định nghĩa xong các thao tác, bây giờ chúng ta đã có thể sử dụng lớp BitSet32 với các thao tác như Hội, Giao, Hiệu, Nhập Xuất tập hợp :
1: #include <iostream.h>
2: #include "BitSet32.h"
3: //#define dim(x) (sizeof(x)/sizeof(x[0]))
4: void main ()
5: {
6: BitSet32 p , c , e;
7: cin >> p >> c ;
8:
9: e = p&c ;
10: cout << e ;
11: }
Chạy ứng dụng và xem kết quả p giao với c :
Pham Nguyen 