第7章集合与搜索 第7章集合与搜索 7-1设A={1,2,3},B={3,4,5},求下列结果 (2)A*B (3)A-B (4)AContains(1)(5)A.AddMember(1) (6)A. DelMember(1) (7)A Min o 【解答】 (1)集合的并A+B={1,2,3,4,5} (2)集合的交A*B={3} (3)集合的差A-B={1,2} (4)包含 A Contains(1)=1,表示运算结果为"True (5)增加 A. AddMember(1),集合中仍为{1,2,3},因为增加的是重复元素,所以不加入 (6)删除 A. DelMember(1),集合中为{2,3} (7)求最小元素AMn(),结果为1 2试编写一个算法,打印一个有穷集合中的所有成员。要求使用集合抽象数据类型中的基本操作。如 果集合中包含有子集合,各个子集合之间没有重复的元素,采用什么结构比较合适 【解答】 集合抽象数据类型的部分内容 template <class Type> class Set i ∥对象:零个或多个成员的聚集。其中所有成员的类型是一致的,但没有一个成员是相同的。 int Contains( const Type x ∥判元素x是否集合this的成员 int SubSet( Set<Type>& right )i 判集合this是否集合rght的子集 int operator==( Set <Type>& right ) ∥判集合this与集合rght是否相等 int Elemtype (; ∥返回集合元素的类型 Type GetData ( 返回集合原子元素的值 char GetName ( 返回集合this的集合名 Set <Type>*GetSubSet(; 回集合this的子集合地址 Set <t GetNext ( ∥返回集合this的直接后继集合元素 int IsEmpty ( ∥判断集合thi是否空。空则返回1,否则返回 ostream& operator <<( ostream& out, Set <Type>t)i ∥友元函数,将集合t输出到输出流对象out . traverse( out, t ) return out; void traverse( ostream& out, Set <Type>s)i ∥友元函数,集合的遄历算法 if(s Is Empty (=0)1 ∥集合元素不空 if(s Elemtype (==0)out <<s GetName ()<<'i 输出集合名及花括号 else if(s Elemtype (=1)( ∥集合原子元素 out<<sGetData ( ∥输出原子元素的值
第 7 章 集合与搜索 80 第 7 章 集合与搜索 7-1 设 A = { 1, 2, 3 }, B = { 3, 4, 5 }，求下列结果： (1) A + B (2) A * B (3) A - B (4) A.Contains (1) (5) A.AddMember (1) (6) A.DelMember (1) (7) A.Min ( ) 【解答】 (1) 集合的并 A + B = { 1, 2, 3, 4, 5 } (2) 集合的交 A * B = { 3 } (3) 集合的差 A - B = { 1, 2 } (4) 包含 A.Contains (1) = 1，表示运算结果为"True" (5) 增加 A.AddMember (1)，集合中仍为{ 1, 2, 3 }，因为增加的是重复元素，所以不加入 (6) 删除 A.DelMember (1)，集合中为{ 2, 3 } (7) 求最小元素 A.Min ( )，结果为 1 7-2 试编写一个算法，打印一个有穷集合中的所有成员。要求使用集合抽象数据类型中的基本操作。如 果集合中包含有子集合，各个子集合之间没有重复的元素，采用什么结构比较合适。 【解答】 集合抽象数据类型的部分内容 template <class Type> class Set { //对象: 零个或多个成员的聚集。其中所有成员的类型是一致的, 但没有一个成员是相同的。 int Contains ( const Type x ); //判元素 x 是否集合 this 的成员 int SubSet ( Set <Type>& right ); //判集合 this 是否集合 right 的子集 int operator == ( Set <Type>& right ); //判集合 this 与集合 right 是否相等 int Elemtype ( ); //返回集合元素的类型 Type GetData ( ); //返回集合原子元素的值 char GetName ( ); //返回集合 this 的集合名 Set <Type>* GetSubSet ( ); //返回集合 this 的子集合地址 Set <Type>* GetNext ( ); //返回集合 this 的直接后继集合元素 int IsEmpty ( ); //判断集合 this 是否空。空则返回 1, 否则返回 0 }; ostream& operator << ( ostream& out, Set <Type> t ) { //友元函数, 将集合 t 输出到输出流对象 out。 t.traverse ( out, t ); return out; } void traverse ( ostream& out, Set <Type> s ) { //友元函数, 集合的遍历算法 if ( s.IsEmpty ( ) == 0 ) { //集合元素不空 if ( s.Elemtype ( ) == 0 ) out << s.GetName ( ) << ‘{’; //输出集合名及花括号 else if ( s.Elemtype ( ) == 1 ) { //集合原子元素 out << s.GetData ( ); //输出原子元素的值
第7章集合与搜索 if(s GetNext (I=NULL )out <<',i ∥子集合 输出子集合 if(s GetNext ()I= NULL )out<<',; } traverse(s GetNext (); ∥向同一集合下一元素搜索 else out<<"}’; 如果集合中包含有子集合,各个子集合之间没有重复的元素,采用广义表结构比较合适。也可以使 用并查集结构 7-3当全集合可以映射成1到N之间的整数时,可以用位数组来表示它的任一子集合。当全集合是下列 集合时,应当建立什么样的映射?用映射对照表表示。 (1)整数0,1,…,99 (2)从n到m的所有整数,n≤m (3)整数n,n+2,n+4,…,n+2k (4)字母‘a,b;,c (5)两个字母组成的字符串,其中,每个字母取自‘a',b',ec',…,z。 【解答】 (1)i→i的映射关系,i=0,1,2,…,99 (2)i→ni的映射关系,i=n,n+1,n+2,…,m nn+1|n+2 (3)i→(i-n)/2的映射关系,i=n,n+2,n+4,…,n+2k (4)ord(c)→ord(c)-ord(a)的映射关系,c=a,b,e,…,z 心… (5)(ord(cl)-ord(a))*26+ord(c2)-ord(a)的映射关系,cl=c2=a,"b,'c,…,z 7-4试证明:集合A是集合B的子集的充分必要条件是集合A和集合B的交集是A。 【证明】 必要条件:因为集合A是集合B的子集,有A≌B,此时,对于任一x∈A,必有ⅹ∈B,因此可以 推得x∈A∩B,就是说,如果A是B的子集,一定有A∩B=A 充分条件:如果集合A和集合B的交集A∩B是A,则对于任一x∈A,一定有x∈A∩B,因此可
第 7 章 集合与搜索 81 if ( s.GetNext ( ) != NULL ) out << ‘,’; } else { //子集合 traverse ( s. GetSubSet ( ) ); //输出子集合 if ( s.GetNext ( ) != NULL ) out << ‘,’; } traverse ( s.GetNext ( ) ); //向同一集合下一元素搜索 } else out << ‘}’; } 如果集合中包含有子集合，各个子集合之间没有重复的元素，采用广义表结构比较合适。也可以使 用并查集结构。 7-3 当全集合可以映射成 1 到 N 之间的整数时，可以用位数组来表示它的任一子集合。当全集合是下列 集合时，应当建立什么样的映射？用映射对照表表示。 (1) 整数 0, 1, …, 99 (2) 从 n 到 m 的所有整数，n m (3) 整数 n, n+2, n+4, …, n+2k (4) 字母 ‘a’, ‘b’, ‘c’, …, ‘z’ (5) 两个字母组成的字符串, 其中， 每个字母取自 ‘a’, ‘b’, ‘c’, …, ‘z’。 【解答】 (1) i → i 的映射关系，i = 0, 1, 2, …, 99 (2) i → n-i 的映射关系，i = n, n+1, n+2, …, m 0 1 2 m-n n n+1 n+2 … m (3) i → (i-n)/2 的映射关系，i = n, n+2, n+4, …, n+2k 0 1 2 k n n+2 n+4 … n+2k (4) ord (c) → ord (c) - ord ('a') 的映射关系，c = 'a', 'b', 'c', …, 'z' 0 1 2 25 'a' 'b' 'c' … 'z' (5) (ord (c1) - ord ('a') )*26 + ord (c2) - ord ('a')的映射关系，c1 = c2 = 'a', 'b', 'c', …, 'z' 0 1 2 675 'aa' 'ab' 'ba' … 'zz' 7-4 试证明：集合 A 是集合 B 的子集的充分必要条件是集合 A 和集合 B 的交集是 A。 【证明】 必要条件：因为集合 A 是集合 B 的子集，有 A B，此时，对于任一 x A，必有 x B，因此可以 推得 x A∩B，就是说，如果 A 是 B 的子集，一定有 A∩B = A。 充分条件：如果集合 A 和集合 B 的交集 A∩B 是 A，则对于任一 x A，一定有 x A∩B，因此可
第7章集合与搜索 以推得x∈B,由此可得AcB,即集合A是集合B的子集。 7-5试证明:集合A是集合B的子集的充分必要条件是集合A和集合B的并集是B 【证明】 必要条件:因为集合A是集合B的子集,有AcB,此时,对于任一x∈A,必有x∈B,它一定 在AUB中。另一方面,对于那些xgA但x∈B的元素,它也必在AUB中,因此可以得出结论:凡 是属于集合B的元素一定在A∪B中,AUB=B 充分条件:如果存在元素x∈A且xgB,有x∈AUB,但这不符合集合A和集合B的并集AUB 是B的要求。集合的并AUB是集合B的要求表明,对于任一x∈AUB,同时应有x∈B。对于那些满 足x∈A的x,既然x∈AUB,也应当x∈B,因此,在此种情况下集合A应是集合B的子集 7-6设+、*、-是集合的或、与、差运算,试举一个例子,验证 A+B=(A- B)+(B-A)+A*B 【解答】 若设集合A={1,3,4,7,9,15},集合B={2,3,5,6,7,12,15,17}。则 A+B={1,2,3,4,5,6,7,9,12,15,17 又A*B={3,7,15},A-B={1,4,9},B-A={2,5,6,12,17} 则 (A-B)+(B-A)+A*B={1,2,3,4,5,6,7,9,12,15,17} H A+B=(A-B)+(B-A)+A*B 7给定一个用无序链表表示的集合,需要在其上执行 operator+(, operator+(, operator-( Contains(x Add Member(x, DelMember(x),Mn(),试写出它的类声明,并给出所有这些成员函数的实现。 【解答】 下面给出用无序链表表示集合时的类的声明 template <class Type 用以表示集合的无序链表的类的前视定义 template <class Type> class SetNode i ∥集合的结点类定义 friend class SetList<Type> Type data; ∥每个成员的数据 SetNode <Type>"link ∥链接指针 Node( const Type&item):data(item),link(NUL;∥构造函数 template <class Type> class Set ∥集合的类定义 private SetNode <Type>*first,"last; ∥无序链表的表头指针,表尾指针 Setlist (i first=last=new SetNode <Type>(0):) ∥构造函数 -Setlist()( MakeEmpty ( delete first;) ∥析构函数 void Make Empty ( 置空集合
第 7 章 集合与搜索 82 以推得 x B，由此可得 A B，即集合 A 是集合 B 的子集。 7-5 试证明：集合 A 是集合 B 的子集的充分必要条件是集合 A 和集合 B 的并集是 B。 【证明】 必要条件：因为集合 A 是集合 B 的子集，有 A B，此时，对于任一 x A，必有 x B， 它一定 在 A∪B 中。另一方面，对于那些 x' A, 但 x' B 的元素，它也必在 A∪B 中，因此可以得出结论：凡 是属于集合 B 的元素一定在 A∪B 中，A∪B = B。 充分条件：如果存在元素 x A 且 x B，有 x A∪B，但这不符合集合 A 和集合 B 的并集 A∪B 是 B 的要求。集合的并 A∪B 是集合 B 的要求表明，对于任一 x A∪B，同时应有 x B。对于那些满 足 x' A 的 x'，既然 x' A∪B，也应当 x' B，因此，在此种情况下集合 A 应是集合 B 的子集。 7-6 设+、*、-是集合的或、与、差运算，试举一个例子，验证 A + B = (A - B) + (B - A) + A * B 【解答】 若设集合 A= { 1, 3, 4, 7, 9, 15 }，集合 B = { 2, 3, 5, 6, 7, 12, 15, 17 }。则 A + B = { 1, 2, 3, 4, 5, 6, 7, 9, 12, 15, 17 } 又 A * B = { 3, 7, 15 }, A – B = { 1, 4, 9 }, B –A = { 2, 5, 6, 12, 17 } 则 (A – B) + (B – A) + A * B = { 1, 2, 3, 4, 5, 6, 7, 9, 12, 15, 17 } 有 A + B = (A – B) + ( B – A ) + A * B。 7-7 给定一个用无序链表表示的集合，需要在其上执行 operator+( ), operator*( ), operator- ( ), Contains(x), AddMember (x), DelMember(x), Min( )，试写出它的类声明，并给出所有这些成员函数的实现。 【解答】 下面给出用无序链表表示集合时的类的声明。 template <class Type> class Set; //用以表示集合的无序链表的类的前视定义 template <class Type> class SetNode { //集合的结点类定义 friend class SetList<Type>; private: Type data; //每个成员的数据 SetNode <Type> *link; //链接指针 public: SetNode (const Type& item ) : data (item), link (NULL); //构造函数 }; template <class Type> class Set { //集合的类定义 private: SetNode <Type> *first, *last; //无序链表的表头指针, 表尾指针 public: SetList ( ) { first = last = new SetNode <Type>(0); } //构造函数 ~SetList ( ) { MakeEmpty ( ); delete first; } //析构函数 void MakeEmpty ( ); //置空集合
第7章集合与搜索 int AddMember( const Type&x ) ∥把新元素x加入到集合之中 int DelMember const Type& x ) 把集合中成员x删去 Set <Type>& operator=( Set <Type>& right ) ∥复制集合 right到this Set <Type>& operator + Set <Type>& right ) 集合this与集合 right的并 Set <Type>& operator * Set <Type>& right ) ∥集合this与集合 right的交 Set<Iype>& operator-(Set<Iype>& right);∥求集合this与集合 right的差 t Contains( const Type&x ) /判ⅹ是否集合的成员 nt operator == Set <Type>& right ) ∥判集合this与集合 right相等 Type& Min ( ∥返回集合中的最小元素的值 (I)operator+( template <class Type> Set <Type>& Set <Ty perator+( Set <Type>& right)t ∥求集合this与集合 right的并,计算结果通过临时集合temp返回,this集合与rght集合不变。 SetNode <Type> pb=right. first->link right集合的链扫描指针 SetNode <Type>"pa, *pc; ∥this集合的链扫描指针和结果链的存放指针 Set <Type> temp: firs while( pa I= NULL)t ∥首先把集合this的所有元素复制到结果链 pc->link new SetNode<Type>( pa->data ); pa->ink: pc=pc->link while( pb I= NULL ) ∥将集合rght中元素一个个拿出到this中查重 while( pa I=NULL & pa->data I=pb->data )pa=pa->link if pa== NULL) ∥在集合this中未出现,链入到结果链 i pc->link= new SetNode<Type>( pa->data ) pc= pc->link; 1 b= pb->link return temp: template <class Type> Set <Type>& Set <Type>: operator*( Set <Type>& right )i ∥求集合this与集合 right的交,计算结果通过临时集合temp返回,this集合与rght集合不变。 SetNode<Type> *pb= rightfirst->link ght集合的链扫描指针 Set <Type> temp SetNode <Type>"pc=temp. first; ∥结果链的存放指针 while( pb I= NULL)t ∥将集合rght中元素一个个拿出到this中查重 SetNode<type>"pa=first-> ∥this集合的链扫描指针 while( pa I=NULL ) if( pa->data=pb->data ∥两集合公有的元素,插入到结果链
第 7 章 集合与搜索 83 int AddMember ( const Type& x ); //把新元素 x 加入到集合之中 int DelMember ( const Type& x ); //把集合中成员 x 删去 Set <Type>& operator = ( Set <Type>& right ); //复制集合 right 到 this。 Set <Type>& operator + ( Set <Type>& right ); //求集合 this 与集合 right 的并 Set <Type>& operator * ( Set <Type>& right ); //求集合 this 与集合 right 的交 Set <Type>& operator - ( Set <Type>& right ); //求集合 this 与集合 right 的差 int Contains ( const Type& x ); //判 x 是否集合的成员 int operator == ( Set <Type>& right ); //判集合 this 与集合 right 相等 Type& Min ( ); //返回集合中的最小元素的值 } (1) operator + ( ) template <class Type> Set <Type>& Set <Type> :: operator + ( Set <Type>& right ) { //求集合 this 与集合 right 的并, 计算结果通过临时集合 temp 返回，this 集合与 right 集合不变。 SetNode <Type> *pb = right.first->link; //right 集合的链扫描指针 SetNode <Type> *pa, *pc; //this 集合的链扫描指针和结果链的存放指针 Set <Type> temp; pa = first->link; pc = temp.first; while ( pa != NULL ) { //首先把集合 this 的所有元素复制到结果链 pc->link = new SetNode<Type> ( pa->data ) ; pa = pa->link; pc = pc->link; } while ( pb != NULL ) { //将集合 right 中元素一个个拿出到 this 中查重 pa = first->link; while ( pa != NULL && pa->data != pb->data ) pa = pa->link; if ( pa == NULL ) //在集合 this 中未出现, 链入到结果链 { pc->link = new SetNode<Type> ( pa->data ); pc = pc->link; } pb = pb->link; } pc->link = NULL; last = pc; //链表收尾 return temp; } (2) operator * ( ) template <class Type> Set <Type>& Set <Type> :: operator * ( Set <Type>& right ) { //求集合 this 与集合 right 的交, 计算结果通过临时集合 temp 返回，this 集合与 right 集合不变。 SetNode<Type> *pb = right.first->link; //right 集合的链扫描指针 Set <Type> temp; SetNode <Type> *pc = temp.first; //结果链的存放指针 while ( pb != NULL ) { //将集合 right 中元素一个个拿出到 this 中查重 SetNode<Type> *pa = first->link; //this 集合的链扫描指针 while ( pa != NULL ) { if ( pa->data == pb->data ) //两集合公有的元素, 插入到结果链
第7章集合与搜索 i pc-link= new SetNode<Type>( pa->data ) pc->link= NULL; last=pc; ∥置链尾指针 return temp: ()operator-(), template <class Type> Set <Type>& Set <Type>: operator-( Set <Type>& right )i ∥求集合this与集合 right的差,计算结果通过临时集合temp返回,this集合与 right集合不变 SetNode<Type> *pa= first-> link; /this集合的链扫描指针 Set <Type> temp: SetNode<Type> *pc= temp->first ∥结果链的存放指针 while( pa I= NULL )t ∥将集合this中元素一个个拿出到 right中查重 SetNode <Type> *pb=right. first->link; rght集合的链扫描指针 while( pb I= nulL & pa->data I=pb->data pb= pb-> link if pb== NULL) 此this中的元素在 right中未找到,插入 i pc->link= new SetNode <Type>( pa->data ) pc=pc->link; 3 ∥链表收尾 x ∥测试函数:如果x是集合的成员,则函数返回1,否则返回0。 SetNode<Type>*temp= first->link; ∥链的扫描指针 while( temp I= NULL & temp->data I=x )temp =temp-> link ∥循链搜索 ∥找到,返回 else return 0: ∥未找到,返回0 (5)AddMember(x) template <class Type> int Set <Type>: AddMember( const Type&x)( ∥把新元素x加入到集合之中。若集合中已有此元素,则函数返回0,否则函数返回1 ∥temp是扫描指针 while( temp I= NULL & temp->data I=x)temp=temp->link /循链扫描 if( temp I=NULL )return 0; ∥集合中已有此元素,不加
第 7 章 集合与搜索 84 { pc->link = new SetNode<Type> ( pa->data ); pc = pc->link; } pa = pa->link; } pb = pb->link; } pc->link = NULL; last = pc; //置链尾指针 return temp; } (3) operator - ( ), template <class Type> Set <Type>& Set <Type> :: operator - ( Set <Type>& right ) { //求集合 this 与集合 right 的差, 计算结果通过临时集合 temp 返回，this 集合与 right 集合不变。 SetNode<Type> *pa = first->link; //this 集合的链扫描指针 Set <Type> temp; SetNode<Type> *pc = temp->first; //结果链的存放指针 while ( pa != NULL ) { //将集合 this 中元素一个个拿出到 right 中查重 SetNode <Type> *pb = right.first->link; //right 集合的链扫描指针 while ( pb != NULL && pa->data != pb->data ) pb = pb->link; if ( pb == NULL ) //此 this 中的元素在 right 中未找到, 插入 { pc->link = new SetNode <Type> ( pa->data ); pc = pc->link; } pa = pa->link; } pc->link = NULL; last = pc; //链表收尾 return temp; } (4) Contains(x) template <class Type> int Set <Type> :: Contains ( const Type& x ) { //测试函数: 如果 x 是集合的成员, 则函数返回 1, 否则返回 0。 SetNode<Type> * temp = first->link; //链的扫描指针 while ( temp != NULL && temp->data != x ) temp = temp->link; //循链搜索 if ( temp != NULL ) return 1; //找到, 返回 1 else return 0; //未找到, 返回 0 } (5) AddMember (x) template <class Type> int Set <Type> :: AddMember ( const Type& x ) { //把新元素 x 加入到集合之中。若集合中已有此元素, 则函数返回 0, 否则函数返回 1。 SetNode<Type> * temp = first->link; // temp 是扫描指针 while ( temp != NULL && temp->data != x ) temp = temp->link; /循链扫描 if ( temp != NULL ) return 0; //集合中已有此元素, 不加