第7章集合与搜索 7-2试编写一个算法,打印一个有穷集合中的所有成员。要求使用集合抽象数据类型中的基本操作。如 果集合中包含有子集合,各个子集合之间没有重复的元素,采用什么结构比较合适 【解答】 集合抽象数据类型的部分内容 ∥对象:零个或多个成员的聚集。其中所有成员的类型是一致的,但没有一个成员是相同的。 /判元素x是否集合this的成员 int SubSet( Set <Type>& right ) 判集合this是否集合 right的子集 Set <Type>& right ) ∥判集合thi与集合rgh是否相等 tempe (i 返回集合元素的类型 回集合原子元素的值 (); ∥返回集合ths的集合名 Set <Type>* GerSubSet ( ∥返回集合this的子集合地址 Set <Type>" GetNext ( ∥返回集合this的直接后继集合元素 int ls Empry ( ∥判断集合ths是否空。空则返回1,否则返回0 ostream& operator << ostream& out, Set <Type>I)i ∥友元函数,将集合t输出到输出流对象ou Traverse( out, 1); return oul; ∥友元函数,集合的遍历算法 if(s Elemtype (==0)out <<s GetName (<<'; ∥输出集合名及花括号 合原子元素 o<<s. Getdata(片; ∥输出原子元素的值 if(s GetNext(I=NULL)on ∥子集合 ∥输出子集合 if(s GetNext (I=NULL)out < } traverse(s. GerNext (); ∥向同一集合下一元素搜索 如果集合中包含有子集合,各个子集合之间没有重复的元素,采用广义表结构比较合适。也可以使 用并查集结构 7-4设+、*、-是集合的或、与、差运算,试举一个例子,验证第 7 章 集合与搜索 55 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 ( ); //输出原子元素的值 if ( s.GetNext ( ) != NULL ) out << ‘,’; } else { //子集合 traverse ( s. GetSubSet ( ) ); //输出子集合 if ( s.GetNext ( ) != NULL ) out << ‘,’; } traverse ( s.GetNext ( ) ); //向同一集合下一元素搜索 } else out << ‘}’; } 如果集合中包含有子集合，各个子集合之间没有重复的元素，采用广义表结构比较合适。也可以使 用并查集结构。 7-4 设+、*、-是集合的或、与、差运算，试举一个例子，验证