7-10 假定用一个循环链表来实现一个有序表，并让指针head指向具有最小关键码的结点。指针current初始时等于head，每次搜索后指向当前检索的结点，但如果搜索不成功则current重置为head。试编写一个函数search(head,current,key)实现这种搜索。当搜索成功时函数返回被检索的结点地址，若搜索不成功则函数返回空指针0.请说明如何保持指针current以减少搜索时的平均搜索长度。
思路：定义搜索函数为类的公共函数。并且这个有序循环列表按key值从小到大排列。
7-11 考虑用双向链表来实现一个有序表，使得能在这个表中进行正向和反向的搜索。若指针p总是指向最后成功搜索到的结点，搜索可以从p指示的结点出发沿任一方向进行。试根据这种情况编写一个函数search(head,p,key),检索具有关键码key的结点，并相应的修改p。最后请给出搜索成功和搜索不成功时的平均搜索长度。
思路：类似上题
7-14 试说明如何利用并查集来计算无向连通图中连通子图的个数。
1.以每个顶点为一个集合，初始化
2.边作为等价对，建立并查集
3.最后得到的集合个数就是连通子图的个数。
7-16 有n个结点的二叉搜索树具有多少种不同形态？
这个题和 问 在给定中序序列下的树，可以有多少种前序遍历。
答案是一样的1/(n+1)Cn/2n
7-18 在二叉搜索树上删除一个有两个子女的结点时，可以采用以下三种方法：
(1)用左子树Tl上具有最大关键码的结点X顶替，再递归地删除X。
(2)交替地用左子树Tl上具有最大关键码的结点和右子树Tr上具有最小关键码的结点顶替，再递归地删除适当的结点。
(3)用左子树Tl上具有最大关键码的结点或者用右子树Tr上具有最小关键码的结点顶替，再递归地删除适当的结点。可随机选择其中一个方案。
声明：均作为类函数加入，为减少篇幅，省略模板结构。并且假设所删除的结点一定是含有两个子女的。
(1)利用左子树上最大关键码结点代替。
(2)
设置一个参数来判断什么 顶替方案
思路：定义搜索函数为类的公共函数。并且这个有序循环列表按key值从小到大排列。
ListNode< Type >* Search(ListNode< Type >*head,ListNode< Type > *current,Type key){
if(key < current->data ) //key小，在前半段,递归调用.
return current=Search(current,head,key);
while(key > current->data && current!=head)
current=current->link;
if(current->data != key)
return NULL;
else return current;
}7-11 考虑用双向链表来实现一个有序表，使得能在这个表中进行正向和反向的搜索。若指针p总是指向最后成功搜索到的结点，搜索可以从p指示的结点出发沿任一方向进行。试根据这种情况编写一个函数search(head,p,key),检索具有关键码key的结点，并相应的修改p。最后请给出搜索成功和搜索不成功时的平均搜索长度。
思路：类似上题
ListNode< Type >* Search(ListNode< Type > *head,ListNode< Type > *p,Type key){
if(p->data > key)
while(p->data > key&&p !=NULL)p=p->llink;
if(p->data < key)
while(p->data < key&&p !=NULL)p=p->rlink;
if(p->data == key)
return p;
else{ p=head;reutrn NULL;}
}7-14 试说明如何利用并查集来计算无向连通图中连通子图的个数。
1.以每个顶点为一个集合，初始化
2.边作为等价对，建立并查集
3.最后得到的集合个数就是连通子图的个数。
7-16 有n个结点的二叉搜索树具有多少种不同形态？
这个题和 问 在给定中序序列下的树，可以有多少种前序遍历。
答案是一样的1/(n+1)Cn/2n
7-18 在二叉搜索树上删除一个有两个子女的结点时，可以采用以下三种方法：
(1)用左子树Tl上具有最大关键码的结点X顶替，再递归地删除X。
(2)交替地用左子树Tl上具有最大关键码的结点和右子树Tr上具有最小关键码的结点顶替，再递归地删除适当的结点。
(3)用左子树Tl上具有最大关键码的结点或者用右子树Tr上具有最小关键码的结点顶替，再递归地删除适当的结点。可随机选择其中一个方案。
声明：均作为类函数加入，为减少篇幅，省略模板结构。并且假设所删除的结点一定是含有两个子女的。
(1)利用左子树上最大关键码结点代替。
remove(BstNode< Type > *ptr){
if(no child)
直接删除
BstNode< Type > *temp;
temp=Max(ptr->leftChild);
ptr->data=temp->data;
remove(temp);
}(2)
设置一个参数来判断什么 顶替方案
Comments (0)