第7章集合与搜索 【解答】 head =10-20{--50-o 相应的搜索函数可以定义为链表及链表结点类的友元函数,直接使用链表及链表结点类的私有数据 成员。 Template<class Type> ListNode <Type>* Search( lisiNode<type>* head, ListNode<Type>*& current, Type key )t if( key current)ip= head; q= current; ∥确定检测范围,用p,q指示 while(p I=g &&p-data <key )p=p->ink ∥循链搜索其值等于key的结点 if(p->data== key )i current=p; return p;) ∥找到,返回结点地址 else (current= head; return NULL: 1 ∥未找到,返回空指针 I1考虑用双向链表来实现一个有序表,使得能在这个表中进行正向和反向搜索。若指针p总是指向最 后成功搜索到的结点,搜索可以从P指示的结点出发沿任一方向进行。试根据这种情况编写一个函数 search(head,p,key),检索具有关键码key的结点,并相应地修改p。最后请给出搜索成功和搜索不成功 时的平均搜索长度。 【解答】 d-囚20-刘一[一口s一卡日刘A Template <class type 在以head为表头的双向有序链表中搜索具有值key的结点。算法可视为双向链表类和双向链表结点类的友元 函数。若给定值key大于结点p中的数据,从p向右正向搜索,否则,从p向左反向搜索。 if(key<p>da){whle(q=MULL&&q->da>key)q=q->k;}"反向搜索 else( while (q l=NUll &&->data key )q=g->rLink; j ∥正向搜索 if (q l= NULL & g->data = key)p=g: return p:1 ∥搜索成功 else return null: 如果指针p处于第i个结点(=1,2,…,n),它左边有r-1个结点,右边有n个结点。找到左边第 i-1号结点比较2次,找到第2号结点比较3次,…,找到第1号结点比较i次,一般地,找到左边第 k个结点比较ik+1次(k=1,2,…,}-1)找到右边第计1号结点比较2次,找到第汁2号结点比较3次, 找到第n号结点比较n计+1次,一般地,找到右边第k个结点比较k计+1次(k=计+1,计2,…,n)。因此, 当指针处于第i个结点时的搜索成功的平均数据比较次数为 1+∑(-k+1)+∑(k-1+1)/n 般地,搜索成功的平均数据比较次数为 3i2第 7 章 集合与搜索 60 【解答】 相应的搜索函数可以定义为链表及链表结点类的友元函数，直接使用链表及链表结点类的私有数据 成员。 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。最后请给出搜索成功和搜索不成功 时的平均搜索长度。 【解答】 Template <class Type> DblListNode<Type> * Search ( DblListNode<Type> * head, DblListNode<Type> *& p, Type key ) { //在以 head 为表头的双向有序链表中搜索具有值 key 的结点。算法可视为双向链表类和双向链表结点类的友元 //函数。若给定值 key 大于结点 p 中的数据, 从 p 向右正向搜索, 否则, 从 p 向左反向搜索。 DblListNode<Type> * q = p; if ( key < p->data ){ while ( q != NULL && q->data > key ) q = q-> lLink; } //反向搜索 else { while ( q != NULL && q->data < key ) q = q-> 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 个结点时的搜索成功的平均数据比较次数为 一般地，搜索成功的平均数据比较次数为 head 10 20 30 40 50 60 head p ∧ 10 20 30 40 50 60 70 ∧ n n i i i n i i i n n n n i k k i n n k i i k * 2 3 * 2 * ( 3) 1 ( 1) ( 1) 2 2 1 1 1 − − + +  =      + − − +  =      +  − + +  − + = + − = n n n n n i i i n n ASL n i succ 3 * 3 1 2 1 3 2 1 2 + − =        − − + + = =