第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 设+、*、-是集合的或、与、差运算，试举一个例子，验证
第7章集合与搜索 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), EndMember(x), Delmemben(x),Mn(),试写出它的类声明,并给出所有这些成员函数的实现 【解答】 下面给出用无序链表表示集合时的类的声明。 template <class Type> class Set 用以表示集合的无序链表的类的前视定义 template <class Type> class SetNode i ∥集合的结点类定义 friend class Setlist<type> private ∥每个成员的数据 MetHode<Iype>·lnk; 指针 Methode( const Type&iem):da(ilem),lnk(NULL;∥构造函数 template <class Type> class Set ∥集合的类定义 SetNode <Type> * first, "last: 无序链表的表头指针,表尾指针 Setlist()first=last= new SetNode <Type>(0);) 构造函数 -Setlist (i MakeEmpry ( delete first;1 ∥析构函数 oid Make Empty ( 置空集合 int AddMember( const Type& x )i 把新元素x加入到集合之中 int DelMember( const Type& x ) 把集合中成员x删去 Set <Type>& operator = Set <Type>& right ) ∥复制集合rght到 Set <Type>& operator + Set <Type>& right ) ∥集合this与集合rght的并 Set <Type>& operator ' Set <Type>& right ) 集合this与集合 right I的交 Set <Type>& operator-( Set <Type>& right ) ∥集合this与集合rght的差 int Contains( const Type& x ) 判x是否集合的成员 int operator == Set <Type>& right ) 判集合this与集合 right相等 Type& Min (; 返回集合中的最小元素的值 (I)operator+o template <class Type> Set <Type>& Set <Type>: operator + Set <Type>& right )t ∥求集合this与集合 right的并,计算结果通过临时集合lemp返回,this集合与rght集合不变
第 7 章 集合与搜索 56 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 ( ); //置空集合 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 集合不变
第7章集合与搜索 SenNode <Type> 'pb=right first->link; ∥rgh集合的链扫描指针 SetNode <Type> "pa, pc; this集合的链扫描指针和结果链的存放指针 while( pa I=NULL)( ∥首先把集合this的所有元素复制到结果链 pc->link= new SetNode<Type>(pa->data ) pa= pa-> ink; pc=pc->link; while( pb I= NULL)& ∥将集合righ中元素一个个拿出到this中查重 while(pa I= NULL & pa->data I= pb->data )pa=pa->link ∥在集合this中未出现,链入到结果链 c->ink= new SetNode<Type>( pa->data ) pc=pc-> pb=pb-> link pe->link=NULL; last=pc; ∥链表收尾 return temp; (2)operator *O template <class Type> Set <Type>& Set <Type>: operator'( Set <Type>& right)t ∥求集合this与集合rght的交,计算结果通过临时集合temp返回,this集合与rght集合不变 ∥rght集合的链扫描指针 Set <Type> temp; SetNode <Type> "pc= temp first; ∥结果链的存放指针 while(pb l= NULL)& ∥将集合rght中元素一个个拿出到this中查重 SetNode<Type> "pa=firsf->link; ∥this集合的链扫描指针 while( pa I= NULL)( /两集合公有的元素,插入到结果链 dpc->link= new SetNode<Type>( pa->data )i pc=pc->link; 3 } pb= pb-> ink; pe>ink=NULL; last=pc; ∥置链尾指针 eturn lemp, ()operator-( template <class Type> Set <Type>& Set <Type>:: operator-( Set <Type>& right)& ∥集合this与集合rght的差,计算结果通过临时集合lemp返回,this集合与 right集合不变。 SetNode<Type> "pa=firsf->link; /this集合的链扫描指针 SetNode<Type> 'pc=temp->first; ∥结果链的存放指针
第 7 章 集合与搜索 57 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 ) //两集合公有的元素, 插入到结果链 { 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; //结果链的存放指针
第7章集合与搜索 while(Pa I= NULL) ∥将集合this中元素一个个拿出到 right中查重 /right集合的链扫描指针 while( pb l= NULL & pa->data I= pb->data if(pb==NULL) 批此this中的元素在 right中未找到,插入 ipc->link new SetNode <Type>( pa->data ) pc= pc->link; pa=pa->ink pe>link=NULL; last=pc ∥链表收尾 return lemp (4)Contains(x) template <class Type> int Set <Type>:: Contains( const Type& x) 测试函数:如果x是集合的成员,则函数返回1,否则返回0。 SetNode<Type>*temp=first-> ink ∥链的扫描指针 while( temp=NULL&&lemp->daal=x)lemp=lemp->lmk;∥循链搜索 if( temp I=NULL)return 1; ∥找到,返回1 Ise return 0; ∥未找到,返回 (5)AddMember(x) template <class Type> int Set <Type>: AddMeml st Type& x)i ∥把新元素x加入到集合之中。若集合中已有此元素,则函数返回0,否则函数返回1 SetNode<Type>*temp =first-> ink; ∥temp是扫描指针 while( temp I=NULL & temp->data I=x )temp= temp-> ink; /循链扫描 if( temp I= NULL)return 0; ∥集合中己有此元素,不加 last= last->link new SetNode(x); ∥否则,创建数据值为x的新结点,链入 return 1: (6) DelMember(x) template <class Type> int Set <Type>: DelMember( const Type&x)i ∥把集合中成员x删去。若集合不空且元素x在集合中,则函数返回1,否则返回0。 ode<Type>*p=first-> ink, *q while(P= NULL)i ∥找到 ∥重新链接 if (p==last)last=q ∥删去链尾结点时改链尾指针 delete p: return ∥删除含x结点 else( g=p; p=p->link;) ∥循链扫描 return 0; ∥集合中无此元素 template <class Type> SetNode<Type>" Set <Type>: Min (t
第 7 章 集合与搜索 58 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; //集合中已有此元素, 不加 last = last->link = new SetNode (x); //否则, 创建数据值为 x 的新结点, 链入 return 1; } (6) DelMember (x) template <class Type> int Set <Type> :: DelMember ( const Type& x ) { //把集合中成员 x 删去。若集合不空且元素 x 在集合中, 则函数返回 1, 否则返回 0。 SetNode<Type> * p = first->link, *q = first; while ( p != NULL ) { if ( p->data == x ) { //找到 q->link = p->link; //重新链接 if ( p == last ) last = q; //删去链尾结点时改链尾指针 delete p; return 1; //删除含 x 结点 } else { q = p; p = p->link; } //循链扫描 return 0; //集合中无此元素 } (7) Min ( ) template <class Type> SetNode<Type> * Set <Type> :: Min ( ) {
第7章集合与搜索 ∥在集合中寻找值最小的成员并返回它的位置。 SetNode<Type>*p=first->ink, q=firsI->ink 仰是检测指针,q是记忆最小指针 while(p I=NULL)( if(p-data <q->data )q=p ∥找到更小的,让q记忆它 ∥继续检测 7-8设有序顺序表中的元素依次为017,094,154,170,275,503,509,512553,612,677765,897,908。试 画出对其进行折半搜索时的二叉搜索树,并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长 度 【解答】 m=14c=14+2*2+3*4+4+)=1 ASL (3*1+4*14) 7-9若对有n个元素的有序顺序表和无序顺序表进行顺序搜索,试就下列三种情况分别讨论两者在等搜 索概率时的平均搜索长度是否相同? (1)搜索失败 (2)搜索成功,且表中只有一个关键码等于给定值k的对象 (3)搜索成功,且表中有若干个关键码等于给定值k的对象,要求一次搜索找出所有对象 【解答】 (1)不同。因为有序顺序表搜索到其关键码比要査找值大的对象时就停止搜索,报告失败信息,不 必搜索到表尾;而无序顺序表必须搜索到表尾才能断定搜索失败 (2)相同。搜索到表中对象的关键码等于给定值时就停止搜索,报告成功信息 (3)不同。有序顺序表中关键码相等的对象相继排列在一起,只要搜索到第一个就可以连续搜索到 其它关键码相同的对象。而无序顺序表必须搜索全部表中对象才能确定相同关键码的对象都找了出来 所需时间就不相同了 前两问可做定量分析。第三问推导出的公式比较复杂,不再进一步讨论。 7-10假定用一个循环链表来实现一个有序表,并让指针head指向具有最小关键码的结点。指针 current 初始时等于head,每次搜索后指向当前检索的结点,但如果搜索不成功则crεn重置为heud。试编写 个函数 search(head, currenr,key)实现这种搜索。当搜索成功时函数返回被检索的结点地址,若搜索不 成功则函数返回空指针0。请说明如何保持指针 curent以减少搜索时的平均搜索长度
第 7 章 集合与搜索 59 //在集合中寻找值最小的成员并返回它的位置。 SetNode<Type> * p = first->link, *q = first->link; //p 是检测指针, q 是记忆最小指针 while ( p != NULL ) { if ( p->data < q->data ) q = p; //找到更小的, 让 q 记忆它 p = p->link; //继续检测 } return q; } 7-8 设有序顺序表中的元素依次为 017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。试 画出对其进行折半搜索时的二叉搜索树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长 度。 【解答】 7-9 若对有 n 个元素的有序顺序表和无序顺序表进行顺序搜索, 试就下列三种情况分别讨论两者在等搜 索概率时的平均搜索长度是否相同? (1) 搜索失败; (2) 搜索成功, 且表中只有一个关键码等于给定值 k 的对象; (3) 搜索成功, 且表中有若干个关键码等于给定值 k 的对象, 要求一次搜索找出所有对象。 【解答】 (1) 不同。因为有序顺序表搜索到其关键码比要查找值大的对象时就停止搜索，报告失败信息，不 必搜索到表尾；而无序顺序表必须搜索到表尾才能断定搜索失败。 (2) 相同。搜索到表中对象的关键码等于给定值时就停止搜索，报告成功信息。 (3) 不同。有序顺序表中关键码相等的对象相继排列在一起，只要搜索到第一个就可以连续搜索到 其它关键码相同的对象。而无序顺序表必须搜索全部表中对象才能确定相同关键码的对象都找了出来， 所需时间就不相同了。 前两问可做定量分析。第三问推导出的公式比较复杂，不再进一步讨论。 7-10 假定用一个循环链表来实现一个有序表，并让指针 head 指向具有最小关键码的结点。指针 current 初始时等于 head，每次搜索后指向当前检索的结点，但如果搜索不成功则 current 重置为 head。试编写 一个函数 search(head, current, key)实现这种搜索。当搜索成功时函数返回被检索的结点地址，若搜索不 成功则函数返回空指针 0。请说明如何保持指针 current 以减少搜索时的平均搜索长度。 509 154 677 017 275 553 897 094 170 503 512 612 765 908 14 45 (1 2 * 2 3* 4 4 * 7) 14 1 14 1 14 1 = = + + + = i= ASLsucc Ci 15 59 (3*1 4 *14) 15 1 15 1 15 0 ' = = + = i= ASLunsucc Ci current