福州大学：《数据结构》课程教学资源（习题解答）第7章集合与搜索.doc_大学文库

第 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 Set { //对象: 零个或多个成员的聚集。其中所有成员的类型是一致的, 但没有一个成员是相同的。 int Contains ( const Type x ); //判元素 x 是否集合 this 的成员 int SubSet ( Set & right ); //判集合 this 是否集合 right 的子集 int operator == ( Set & right ); //判集合 this 与集合 right 是否相等 int Elemtype ( ); //返回集合元素的类型 Type GetData ( ); //返回集合原子元素的值 char GetName ( ); //返回集合 this 的集合名 Set * GetSubSet ( ); //返回集合 this 的子集合地址 Set * GetNext ( ); //返回集合 this 的直接后继集合元素 int IsEmpty ( ); //判断集合 this 是否空。空则返回 1, 否则返回 0 }; ostream& operator t ) { //友元函数, 将集合 t 输出到输出流对象 out。 t.traverse ( out, t ); return out; } void traverse ( ostream& out, Set s ) { //友元函数, 集合的遍历算法 if ( s.IsEmpty ( ) == 0 ) { //集合元素不空 if ( s.Elemtype ( ) == 0 ) out << s.GetName ( ) << ‘{’; //输出集合名及花括号 else if ( s.Elemtype ( ) == 1 ) { //集合原子元素 out << s.GetData ( ); //输出原子元素的值

第 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 Set; //用以表示集合的无序链表的类的前视定义 template class SetNode { //集合的结点类定义 friend class SetList; private: Type data; //每个成员的数据 SetNode *link; //链接指针 public: SetNode (const Type& item ) : data (item), link (NULL); //构造函数 }; template class Set { //集合的类定义 private: SetNode *first, *last; //无序链表的表头指针, 表尾指针 public: SetList ( ) { first = last = new SetNode (0); } //构造函数 ~SetList ( ) { MakeEmpty ( ); delete first; } //析构函数 void MakeEmpty ( ); //置空集合

第 7 章集合与搜索 83 int AddMember ( const Type& x ); //把新元素 x 加入到集合之中 int DelMember ( const Type& x ); //把集合中成员 x 删去 Set & operator = ( Set & right ); //复制集合 right 到 this。 Set & operator + ( Set & right ); //求集合 this 与集合 right 的并 Set & operator * ( Set & right ); //求集合 this 与集合 right 的交 Set & operator - ( Set & right ); //求集合 this 与集合 right 的差 int Contains ( const Type& x ); //判 x 是否集合的成员 int operator == ( Set & right ); //判集合 this 与集合 right 相等 Type& Min ( ); //返回集合中的最小元素的值 } (1) operator + ( ) template Set & Set :: operator + ( Set & right ) { //求集合 this 与集合 right 的并, 计算结果通过临时集合 temp 返回，this 集合与 right 集合不变。 SetNode *pb = right.first->link; //right 集合的链扫描指针 SetNode *pa, *pc; //this 集合的链扫描指针和结果链的存放指针 Set temp; pa = first->link; pc = temp.first; while ( pa != NULL ) { //首先把集合 this 的所有元素复制到结果链 pc->link = new SetNode ( 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 ( pa->data ); pc = pc->link; } pb = pb->link; } pc->link = NULL; last = pc; //链表收尾 return temp; } (2) operator * ( ) template Set & Set :: operator * ( Set & right ) { //求集合 this 与集合 right 的交, 计算结果通过临时集合 temp 返回，this 集合与 right 集合不变。 SetNode *pb = right.first->link; //right 集合的链扫描指针 Set temp; SetNode *pc = temp.first; //结果链的存放指针 while ( pb != NULL ) { //将集合 right 中元素一个个拿出到 this 中查重 SetNode *pa = first->link; //this 集合的链扫描指针 while ( pa != NULL ) { if ( pa->data == pb->data ) //两集合公有的元素, 插入到结果链

第7章集合与搜索 7-9若对有n个元素的有序顺序表和无序顺序表进行顺序搜索,试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同? 小(3*1+4*14)=S9 (1)搜索失败 (2)搜索成功,且表中只有一个关键码等于给定值k的对象; (3)搜索成功,且表中有若干个关键码等于给定值k的对象,要求一次搜索找出所有对象。【解答】 (1)不同。因为有序顺序表搜索到其关键码比要查找值大的对象时就停止搜索,报告失败信息,不必搜索到表尾;而无序顺序表必须搜索到表尾才能断定搜索失败。 (2)相同。搜索到表中对象的关键码等于给定值时就停止搜索,报告成功信息。 (3)不同。有序顺序表中关键码相等的对象相继排列在一起,只要搜索到第一个就可以连续搜索到其它关键码相同的对象。而无序顺序表必须搜索全部表中对象才能确定相同关键码的对象都找了出来所需时间就不相同了前两问可做定量分析。第三问推导出的公式比较复杂,不再进一步讨论 7-10假定用一个循环链表来实现一个有序表,并让指针head指向具有最小关键码的结点。指针 cument 初始时等于head,每次搜索后指向当前检索的结点,但如果搜索不成功则 current重置为head。试编写个函数 search(head, current key)实现这种搜索。当搜索成功时函数返回被检索的结点地址,若搜索不成功则函数返回空指针0。请说明如何保持指针 current以减少搜索时的平均搜索长度。【解答】 current M-=1020[3045o6o 相应的搜索函数可以定义为链表及链表结点类的友元函数,直接使用链表及链表结点类的私有数据成员 template ListNode * Search( ListNode* head, ListNode*& current, Type key)t ListNode *p, *9: if( key data==key )i =p: return p; 3 ∥找到,返回结点地址 lse i current= head; return NULL; 1 ∥未找到,返回空指针 7-11考虑用双向链表来实现一个有序表,使得能在这个表中进行正向和反向搜索。若指针p总是指向最后成功搜索到的结点,搜索可以从p指示的结点出发沿任一方向进行。试根据这种情况编写一个函数 search(head,p,key),检索具有关键码key的结点,并相应地修改p。最后请给出搜索成功和搜索不成功时的平均搜索长度。【解答】

第 7 章集合与搜索 86 7-9 若对有 n 个元素的有序顺序表和无序顺序表进行顺序搜索, 试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同? (1) 搜索失败; (2) 搜索成功, 且表中只有一个关键码等于给定值 k 的对象; (3) 搜索成功, 且表中有若干个关键码等于给定值 k 的对象, 要求一次搜索找出所有对象。【解答】 (1) 不同。因为有序顺序表搜索到其关键码比要查找值大的对象时就停止搜索，报告失败信息，不必搜索到表尾；而无序顺序表必须搜索到表尾才能断定搜索失败。 (2) 相同。搜索到表中对象的关键码等于给定值时就停止搜索，报告成功信息。 (3) 不同。有序顺序表中关键码相等的对象相继排列在一起，只要搜索到第一个就可以连续搜索到其它关键码相同的对象。而无序顺序表必须搜索全部表中对象才能确定相同关键码的对象都找了出来，所需时间就不相同了。前两问可做定量分析。第三问推导出的公式比较复杂，不再进一步讨论。 7-10 假定用一个循环链表来实现一个有序表，并让指针 head 指向具有最小关键码的结点。指针 current 初始时等于 head，每次搜索后指向当前检索的结点，但如果搜索不成功则 current 重置为 head。试编写一个函数 search(head, current, key)实现这种搜索。当搜索成功时函数返回被检索的结点地址，若搜索不成功则函数返回空指针 0。请说明如何保持指针 current 以减少搜索时的平均搜索长度。【解答】相应的搜索函数可以定义为链表及链表结点类的友元函数，直接使用链表及链表结点类的私有数据成员。 template ListNode * Search ( ListNode * head, ListNode *& current, Type key ) { ListNode * p, * q; if ( key data link; //循链搜索其值等于 key 的结点 if ( p->data == key ) { current = p; return p; } //找到, 返回结点地址 else { current = head; return NULL; } //未找到, 返回空指针 } 7-11 考虑用双向链表来实现一个有序表，使得能在这个表中进行正向和反向搜索。若指针 p 总是指向最后成功搜索到的结点，搜索可以从 p 指示的结点出发沿任一方向进行。试根据这种情况编写一个函数 search(head, p, key)，检索具有关键码 key 的结点，并相应地修改 p。最后请给出搜索成功和搜索不成功时的平均搜索长度。【解答】 15 59 (3*1 4*14) 15 1 C 15 1 ASL 15 i 0 ' unsucc =  i = + = = head current 10 20 30 40 50 60 p

第 7 章集合与搜索 87 40 template DblListNode * Search ( DblListNode * head, DblListNode *& p, Type key ) { //在以 head 为表头的双向有序链表中搜索具有值 key 的结点。算法可视为双向链表类和双向链表结点类的友元 //函数。若给定值 key 大于结点 p 中的数据, 从 p 向右正向搜索, 否则, 从 p 向左反向搜索。 DblListNode * q = p; if ( key data ){ while ( q != NULL && q->data > key ) q = q-> lLink; } //反向搜索 else { while ( q != NULL && q->data rLink; } //正向搜索 if ( q != NULL && q->data == key ) { p = q; return p; } //搜索成功 else return NULL; } 如果指针 p 处于第 i 个结点(i = 1, 2, …, n)，它左边有 i-1 个结点，右边有 n-i 个结点。找到左边第 i-1 号结点比较 2 次，找到第 i-2 号结点比较 3 次，…，找到第 1 号结点比较 i 次，一般地，找到左边第 k个结点比较i-k+1次(k = 1, 2, …, i-1)。找到右边第i+1号结点比较2次，找到第i+2号结点比较3次，…，找到第 n 号结点比较 n-i+1 次，一般地，找到右边第 k 个结点比较 k-i+1 次(k = i+1, i+2, …, n)。因此，当指针处于第 i 个结点时的搜索成功的平均数据比较次数为一般地，搜索成功的平均数据比较次数为如果指针 p 处于第 i 个结点(i = 1, 2, …, n)，它左边有 i 个不成功的位置，右边有 n-i+1 个不成功的位置。一般地，搜索不成功的平均数据比较次数为 7-12 在一棵表示有序集 S 的二叉搜索树中，任意一条从根到叶结点的路径将 S 分为 3 部分：在该路径左边结点中的元素组成的集合 S1；在该路径上的结点中的元素组成的集合 S2；在该路径右边结点中的元素组成的集合 S3。S = S1  S2  S3。若对于任意的 a  S1, b  S2, c  S3，是否总有 a  b  c？为什么？【解答】答案是否定的。举个反例：看下图粗线所示的路径 head ∧ 10 20 30 40 50 60 70 ∧ 45 30 15 25 70 65 35 50 n i i i*n 2 n 3 i i i*n n 2 n *(n 3) 1 (i k 1) (k i 1) n 2 2 n k i 1 i 1 k 1 − − + +  =      + − − +  =      + − + +  − + = + − = 3n n 3n 1 n i i i*n 2 n 3 n 1 ASL n 2 i 1 2 succ + − =        − − + + = = i i i*n 1 (n 1) 2 n *(n 3) (i k) (k i 1) (n 1) 2 n k i i 1 k 0  +      + − − + +  + =       − + − + = − = = + + +  =      + − − + + + = n i 0 2 2 unsucc 2 n 1 2n 7n 6 i i i*n 1 2 n*(n 3) (n 1) 1 ASL

福州大学：《数据结构》课程教学资源（习题解答）第7章 集合与搜索

福州大学：《数据结构》课程教学资源（习题解答）第7章集合与搜索