第8章搜索 template<class Type> ListNode <Type>* Search( ListNode<Type>*head, ListNode<Type>*& current, Type key )4 ListNode <Type>*p, 'q: if( key <current )(p= head; q=current; j ∥确定检测范围,用p,q指示 else(p=current; q= head; 3 while( p I=q&& p->data key )p=p->ink; ∥循链搜索其值等于key的结点 if p->data = key)i current=p: return p: ∥找到,返回结点地址 lse current= head; return NULL; ∥未找到,返回空指针 8-4考虑用双向链表来实现一个有序表,使得能在这个表中进行正向和反向搜索。若指针p总是指向最 后成功搜索到的结点,搜索可以从p指示的结点出发沿任一方向进行。试根据这种情况编写一个函数 search(head,p,kesy),检索具有关键码key的结点,并相应地修改p。最后请给出搜索成功和搜索不成功 时的平均搜索长度 【解答】 hd囚卡20-列上4日5上卡日刘 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 l= nUll & q->data >key )q=q-> ILink: 1 反向搜索 else while(q= NULL&& q->data key )q=q->rLink; j ∥正向搜索 if (ql= null & q->data =key )(p=g: return p; j 搜索成功 else return NULL 如果指针p处于第i个结点(i=1,2,…,n),它左边有i-1个结点,右边有ni个结点。找到左边第 i-1号结点比较2次,找到第i-2号结点比较3次,…,找到第1号结点比较i次,一般地,找到左边第 k个结点比较i-k+1次(k=1,2,…,i-1)。找到右边第计1号结点比较2次,找到第计2号结点比较3次,…, 找到第n号结点比较ni计+1次,一般地,找到右边第k个结点比较k-计+1次(k=计+1,i+2,…;n)。因此, 1+∑(-k+1)+∑(k-i+1) 3) 3 当指针处于第i个结点时的搜索成功的平均数据比较次数为 般地,搜索成功的平均数据比较次数为 ASL n+3 i*n)n2+3n-1 succ 如果指针p处于第i个结点(i=1,2,…,n),它左边有i个不成功的位置,右边有ni+1个不成功的位置 ∑-k)+∑(k-i+1)/(mn+1) *(n+y+2-i-i*n+1/(mn+1) k=0第 8 章 搜索 81 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; } //未找到, 返回空指针 } 8-4 考虑用双向链表来实现一个有序表，使得能在这个表中进行正向和反向搜索。若指针 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 个结点时的搜索成功的平均数据比较次数为 一般地，搜索成功的平均数据比较次数为 如果指针 p 处于第 i 个结点(i = 1, 2, …, n)，它左边有 i 个不成功的位置，右边有 n-i+1 个不成功的位置。 head p ∧ 10 20 30 40 50 60 70 ∧ 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  +      + − − + +  + =       − + − + = − =