第7章集合与搜索 last=last->link new SetNode(x); ∥则,创建数据值为x的新结点,链入 template <class Type> int Set <Type>: DelMember( const Type&x)t ∥把集合中成员x删去。若集合不空且元素x在集合中,则函数返回1,否则返回0。 while( p I= NULL) ∥重新链接 if (p==last )last=q ∥删去链尾结点时改链尾指针 ∥删除含x结点 ∥循链扫描 ∥集合中无此元素 emplate <class Type> SetNode<Type>. Set <Type>: Min()i ∥在集合中寻找值最小的成员并返回它的位置 SetNode<Type>*p=first->link, *q= first-> link 是检测指针,q是记忆最小指针 while(pI= NULL)t <g->data)q=p: ∥找到更小的,让q记忆它 ∥继续检测 7-8设有序顺序表中的元素依次为017,094,154,170,275,503,509,512553,612,677,765,897,908。试 画出对其进行折半搜索时的二叉搜索树,并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长 度 【解答】 路 C 45 1+2
第 7 章 集合与搜索 85 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 ( ) { //在集合中寻找值最小的成员并返回它的位置。 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。试 画出对其进行折半搜索时的二叉搜索树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长 度。 【解答】 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 C 14 1 ASL 1 4 i 1 succ = i = + + + = =
第7章集合与搜索 7-9若对有n个元素的有序顺序表和无序顺序表进行顺序搜索,试就下列三种情况分别讨论两者在等搜 索概率时的平均搜索长度是否相同? AS15之C1=1(3*1+4+14)-15 (1)搜索失败 (2)搜索成功,且表中只有一个关键码等于给定值k的对象; (3)搜索成功,且表中有若干个关键码等于给定值k的对象,要求一次搜索找出所有对象。 【解答】 (1)不同。因为有序顺序表搜索到其关键码比要查找值大的对象时就停止搜索,报告失败信息,不 必搜索到表尾;而无序顺序表必须搜索到表尾才能断定搜索失败。 (2)相同。搜索到表中对象的关键码等于给定值时就停止搜索,报告成功信息。 (3)不同。有序顺序表中关键码相等的对象相继排列在一起,只要搜索到第一个就可以连续搜索到 其它关键码相同的对象。而无序顺序表必须搜索全部表中对象才能确定相同关键码的对象都找了出来 所需时间就不相同了 前两问可做定量分析。第三问推导出的公式比较复杂,不再进一步讨论 7-10假定用一个循环链表来实现一个有序表,并让指针head指向具有最小关键码的结点。指针 current 初始时等于head,每次搜索后指向当前检索的结点,但如果搜索不成功则 current重置为head。试编写 个函数 search(head, current key)实现这种搜索。当搜索成功时函数返回被检索的结点地址,若搜索不 成功则函数返回空指针0。请说明如何保持指针 current以减少搜索时的平均搜索长度。 【解答】 current M-=1020[3045o6o 相应的搜索函数可以定义为链表及链表结点类的友元函数,直接使用链表及链表结点类的私有数据 成员 template<class Type> ListNode <Type>* Search( ListNode<Type>* head, ListNode<Type>*& current, Type key )t ListNode <Type>*p, *9: if( key <current)(p=head: q=current; ∥确定检测范围,用p,q指示 else p=current; q=head; j ∥循链搜索其值等于key的结点 if ( p->data==key )i =p: return p; 3 ∥找到,返回结点地址 Ise (current=head; return NULL; 3 ∥未找到,返回空指针 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<class Type> ListNode <Type> * Search ( ListNode<Type> * head, ListNode<Type> *& current, Type key ) { ListNode <Type> * p, * q; if ( key < current ) { p = head; q = current; } //确定检测范围, 用 p, q 指示 else { p = current; q = head; } while ( p != q && p->data < key ) p = p->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