7-1设A={1,2,3}-Read.doc

8-1 设有序顺序表中的元素依次为017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的二叉搜索树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 【解答】 8-2 若对有n个元素的有序顺序表和无序顺序表进行顺序搜索, 试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同? (1) 搜索失败; (2) 搜索成功, 且表中只有一个关键码等于给定值k的对象; (3) 搜索成功, 且表中有若干个关键码等于给定值k的对象, 要求一次搜索找出所有对象。 【解答】 (1) 不同。因为有序顺序表搜索到其关键码比要查找值大的对象时就停止搜索，报告失败信息，不必搜索到表尾；而无序顺序表必须搜索到表尾才能断定搜索失败。 (2) 相同。搜索到表中对象的关键码等于给定值时就停止搜索，报告成功信息。 (3) 不同。有序顺序表中关键码相等的对象相继排列在一起，只要搜索到第一个就可以连续搜索到其它关键码相同的对象。而无序顺序表必须搜索全部表中对象才能确定相同关键码的对象都找了出来，所需时间就不相同了。 前两问可做定量分析。第三问推导出的公式比较复杂，不再进一步讨论。 8-3 假定用一个循环链表来实现一个有序表，并让指针head指向具有最小关键码的结点。指针current初始时等于head，每次搜索后指向当前检索的结点，但如果搜索不成功则current重置为head。试编写一个函数search(head, current, key)实现这种搜索。当搜索成功时函数返回被检索的结点地址，若搜索不成功则函数返回空指针0。请说明如何保持指针current以减少搜索时的平均搜索长度。 【解答】 相应的搜索函数可以定义为链表及链表结点类的友元函数，直接使用链表及链表结点类的私有数据成员。 templateclass Type ListNode Type * Search ( ListNodeType * head, ListNodeType * 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 DblListNodeType * Search ( DblListNodeType * head, DblListNodeType * p, Type key ) { //在以head为表头的双向有序链表中搜索具有值key的结点。算法可视为双向链表类和双向链表结点类的友元 //函数。若给定值key大于结点p中的数据, 从p向右正向搜索, 否则, 从p向左反向搜索。 DblListNodeType * 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-