第七章集合与搜索 集合及其表示 等价类与并查集 静态搜索表 二又搜索树 最优二叉搜索树 ∠树 小结
◼ 集合及其表示 ◼ 等价类与并查集 ◼ 静态搜索表 ◼ 二叉搜索树 ◼ 最优二叉搜索树 ◼ AVL树 ◼ 小结
集合及其表示 集合基本概念 集合是成员对象或元素)的一个群集。集合中 的成员可以是原子(单元素),也可以是集合 集合的成员必须互不相同。 在算法与数据结构中所遇到的集合,其单元 素通常是整数、字符、字符串或指针,且同 一集合中所有成员具有相同的数据类型。 colour=( red, orange, yellow, green, black, blue, purple, white name={“An”,“Cao”, “Liu”,“Ma”,“Peng”,“wang”,“ zhang”}
集合基本概念 集合及其表示 ◼ 集合是成员(对象或元素)的一个群集。集合中 的成员可以是原子(单元素)，也可以是集合。 ◼ 集合的成员必须互不相同。 ◼ 在算法与数据结构中所遇到的集合，其单元 素通常是整数、字符、字符串或指针，且同 一集合中所有成员具有相同的数据类型。 ◼ colour = { red, orange, yellow, green, black, blue, purple, white } name = { “An”, “Cao”, “Liu”, “Ma”, “Peng”, “Wang”, “zhang” }
集合中的成员一般是无序的,没有先后次序关 系。但在表示它时,常常写在一个序列里。 我们常设定集合中的单元素具有线性有序关系 此关系可记作“b三者必居其 a若a,b,c是集合中的三个单元素,且a>b, b>c,则a>c。(传递性) 整数、字符和字符串都有一个自然的线性顺序。 而指针也可以依据其在序列中安排的位置给予 一个线性顺序。 集合操作有求集合的并、交、差、判存在等
◼ 集合中的成员一般是无序的，没有先后次序关 系。但在表示它时，常常写在一个序列里。 ◼ 我们常设定集合中的单元素具有线性有序关系， 此关系可记作“b三者必居其一； ◼ 若a, b, c是集合中的三个单元素，且a>b, b>c，则a>c。(传递性) ◼ 整数、字符和字符串都有一个自然的线性顺序。 而指针也可以依据其在序列中安排的位置给予 一个线性顺序。 集合操作有求集合的并、交、差、判存在等
B (a)A∪B(或A+B) (b)A∩B(或AB) (c)A-B 集合运算的文氏(venn)图 集合(Se)的抽象数据类型 Template class Set t Set( int MaxSetsize ): MaxSize( maxsetsize ) void MakeEmpty( set &s ) int AddMember( set &s, const Type x int DelMember set &s, const Type & x);
集合运算的文氏(Venn)图 集合(Set)的抽象数据类型 Template class Set { Set ( int MaxSetSize ) : MaxSize ( MaxSetSize ); void MakeEmpty ( Set &s ); int AddMember ( Set &s, const Type x ); int DelMember ( Set &s, const Type & x );
void Assign( Set& sl, Set& s2 ) void Union( set& sl, set& s2 void Intersection( Set& sl, Set& s2 ) void Difference( set& sl, set& s2 ); int Contains( Set &s, const Type &x ); int Equal( set &sl, set &s2) int SubSet( set &sl, set &s2 )
void Assign ( Set& s1, Set& s2 ); void Union ( Set& s1, Set& s2 ); void Intersection ( Set& s1, Set& s2 ); void Difference ( Set& s1, Set& s2 ); int Contains ( Set &s, const Type & x ); int Equal ( Set &s1, Set &s2 ); int SubSet ( Set &s1, Set &s2 ); }
用位向量实现集合抽象数据类型 当集合是全集合{0,1,2,…,n}的一个子集 且n是不大的整数时,可用位(0,1)向量来实现 集合。 a当全集合是由有限的可枚举的成员组成的集 合时,可建立全集合成员与整数0,1,2,.一 对应关系,用位向量来表示该集合的子集。 集合的位向量 bit vector)类的定义 include const int Defaultsize= 100 class set i
用位向量实现集合抽象数据类型 集合的位向量(bit Vector)类的定义 #include const int DefaultSize = 100; class Set { ◼ 当集合是全集合{ 0, 1, 2, …, n }的一个子集， 且 n是不大的整数时，可用位(0, 1)向量来实现 集合。 ◼ 当全集合是由有限的可枚举的成员组成的集 合时，可建立全集合成员与整数0, 1, 2, …的一 一对应关系，用位向量来表示该集合的子集
private int bitvector int Max size public Set( int Max Setsize= Defaultsize ) set oi delete l bitvector;) void Makeempty ot for (int i=0; i< MaxSize; i++) bivector=0 int AddMember( const int x); int DelMember( const int x ) Set& operator =( Set right )
private: int * bitVector; int MaxSize; public: Set ( int MaxSetSize = DefaultSize ); ~Set ( ) { delete [ ] bitVector; } void MakeEmpty ( ) { for ( int i = 0; i < MaxSize; i++ ) bitVector[i] = 0; } int AddMember ( const int x ); int DelMember ( const int x ); Set& operator = ( Set & right );
Set& operator + Set right ) Set& operator*( Set right ) Set& operator -( Set right ) int Contains( const int x ) int SubSet( set right ) int operator -- Set right ) 使用示例 Sets1,s2,s3,s4,s5; int index, equal;/构造集合 for( int k=0; k< 10; k++) 集合赋值 &sl. AddMember(k); s2. AddMember(k+7); ∥ls1:{0,1,2,…,9},s2:{7,8,9,,,16}
Set& operator + ( Set & right ); Set& operator * ( Set & right ); Set& operator - ( Set & right ); int Contains ( const int x ); int SubSet ( Set & right ); int operator == ( Set & right ); }; 使用示例 Set s1, s2, s3, s4, s5; int index, equal; //构造集合 for ( int k = 0; k < 10; k++ ) //集合赋值 { s1.AddMember( k ); s2.AddMember( k +7 ); } // s1 : { 0, 1, 2, …, 9 }, s2 : { 7, 8, 9, …, 16 }
s3=s1+s2;/求s1与s2的并{0,1,…,16} s4=s1*s2;/求s1与s2的交{7,8,9} s5=s1-s2;/求1与s2的差{0,1,2,3,4,5,6} ndex=s1. Subset(s4);/求s4在s1中首次匹配 cout0) bitvector= new int [MaxSizeli assert( bit Vector!=0);
s3 = s1 + s2; //求s1与s2的并{ 0, 1, …, 16 } s4 = s1 * s2; //求s1与s2的交{ 7, 8, 9 } s5 = s1 - s2; //求s1与s2的差 { 0, 1, 2, 3, 4, 5, 6 } index = s1.SubSet ( s4 ); //求s4在s1中首次匹配 cout 0 ); bitVector = new int [MaxSize]; assert ( bitVector != 0 );
for( int i=0; i=0 & x=0&&x< MaxSize ) if bitvectorlx)( bitvectorkx=0; return 1;) return o
for ( int i = 0; i = 0 && x = 0 && x < MaxSize ); if ( bitVector[x] ) { bitVector[x] = 0; return 1; } return 0; }