查找.docx
《查找.docx》由会员分享,可在线阅读,更多相关《查找.docx(14页珍藏版)》请在冰点文库上搜索。
查找
第九章查找
9.25
intSearch_Sq(SSTableST,intkey)//在有序表上顺序查找的算法,监视哨设在高下标端
{
ST.elem[ST.length+1].key=key;
for(i=1;ST.elem[i].key>key;i++);
if(i>ST.length||ST.elem[i].key returni;}//Search_Sq分析:本算法查找成功情况下的平均查找长度为ST.length/2,不成功情况下为ST.length.9.26intSearch_Bin_Recursive(SSTableST,intkey,intlow,inthigh)//折半查找的递归算法{ if(low>high)return0;//查找不到时返回0 mid=(low+high)/2; if(ST.elem[mid].key==key)returnmid; elseif(ST.elem[mid].key>key) returnSearch_Bin_Recursive(ST,key,low,mid-1); elsereturnSearch_Bin_Recursive(ST,key,mid+1,high); }}//Search_Bin_Recursive9.27intLocate_Bin(SSTableST,intkey)//折半查找,返回小于或等于待查元素的最后一个结点号{ int*r; r=ST.elem; if(key elseif(key>=r[ST.length].key)returnST.length; low=1;high=ST.length; while(low<=high) { mid=(low+high)/2; if(key>=r[mid].key&&key returnmid; elseif(key elselow=mid; }//本算法不存在查找失败的情况,不需要return0;}//Locate_Bin9.28typedefstruct{ intmaxkey; intfirstloc; }Index;typedefstruct{ int*elem; intlength; Indexidx[MAXBLOCK];//每块起始位置和最大元素,其中idx[0]不利用,其内容初始化为{0,0}以利于折半查找 intblknum;//块的数目 }IdxSqList;//索引顺序表类型intSearch_IdxSeq(IdxSqListL,intkey)//分块查找,用折半查找法确定记录所在块,块内采用顺序查找法{ if(key>L.idx[L.blknum].maxkey)returnERROR;//超过最大元素 low=1;high=L.blknum; found=0; while(low<=high&&!found)//折半查找记录所在块号mid { mid=(low+high)/2; if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey) found=1; elseif(key>L.idx[mid].maxkey) low=mid+1; elsehigh=mid-1; } i=L.idx[mid].firstloc;//块的下界 j=i+blksize-1;//块的上界 temp=L.elem[i-1];//保存相邻元素 L.elem[i-1]=key;//设置监视哨 for(k=j;L.elem[k]!=key;k--);//顺序查找 L.elem[i-1]=temp;//恢复元素 if(k returnk;}//Search_IdxSeq分析:在块内进行顺序查找时,如果需要设置监视哨,则必须先保存相邻块的相邻元素,以免数据丢失.9.29typedefstruct{ LNode*h;//h指向最小元素 LNode*t;//t指向上次查找的结点 }CSList;LNode*Search_CSList(CSList&L,intkey)//在有序单循环链表存储结构上的查找算法,假定每次查找都成功{ if(L.t->data==key)returnL.t; elseif(L.t->data>key) for(p=L.h,i=1;p->data!=key;p=p->next,i++); else for(p=L.t,i=L.tpos;p->data!=key;p=p->next,i++); L.t=p;//更新t指针 returnp;}//Search_CSList分析:由于题目中假定每次查找都是成功的,所以本算法中没有关于查找失败的处理.由微积分可得,在等概率情况下,平均查找长度约为n/3.9.30typedefstruct{ DLNode*pre; intdata; DLNode*next; }DLNode;typedefstruct{ DLNode*sp; intlength; }DSList;//供查找的双向循环链表类型DLNode*Search_DSList(DSList&L,intkey)//在有序双向循环链表存储结构上的查找算法,假定每次查找都成功{ p=L.sp; if(p->data>key) { while(p->data>key)p=p->pre; L.sp=p; } elseif(p->data { while(p->datanext; L.sp=p; } returnp;}//Search_DSList分析:本题的平均查找长度与上一题相同,也是n/3.9.31intlast=0,flag=1;intIs_BSTree(BitreeT)//判断二叉树T是否二叉排序树,是则返回1,否则返回0{ if(T->lchild&&flag)Is_BSTree(T->lchild); if(T->data last=T->data; if(T->rchild&&flag)Is_BSTree(T->rchild); returnflag;}//Is_BSTree9.32intlast=0;voidMaxLT_MinGT(BiTreeT,intx)//找到二叉排序树T中小于x的最大元素和大于x的最小元素{ if(T->lchild)MaxLT_MinGT(T->lchild,x);//本算法仍是借助中序遍历来实现 if(lastdata>=x)//找到了小于x的最大元素 printf("a=%d\n",last); if(last<=x&&T->data>x)//找到了大于x的最小元素 printf("b=%d\n",T->data); last=T->data; if(T->rchild)MaxLT_MinGT(T->rchild,x);}//MaxLT_MinGT9.33voidPrint_NLT(BiTreeT,intx)//从大到小输出二叉排序树T中所有不小于x的元素{ if(T->rchild)Print_NLT(T->rchild,x); if(T->data printf("%d\n",T->data); if(T->lchild)Print_NLT(T->lchild,x);//先右后左的中序遍历}//Print_NLT9.34voidDelete_NLT(BiTree&T,intx)//删除二叉排序树T中所有不小于x元素结点,并释放空间{ if(T->rchild)Delete_NLT(T->rchild,x); if(T->data q=T; T=T->lchild; free(q);//如果树根不小于x,则删除树根,并以左子树的根作为新的树根 if(T)Delete_NLT(T,x);//继续在左子树中执行算法}//Delete_NLT9.35voidPrint_Between(BiThrTreeT,inta,intb)//打印输出后继线索二叉排序树T中所有大于a且小于b的元素{ p=T; while(!p->ltag)p=p->lchild;//找到最小元素 while(p&&p->data { if(p->data>a)printf("%d\n",p->data);//输出符合条件的元素 if(p->rtag)p=p->rtag; else { p=p->rchild; while(!p->ltag)p=p->lchild; }//转到中序后继 }//while}//Print_Between9.36voidBSTree_Insert_Key(BiThrTree&T,intx)//在后继线索二叉排序树T中插入元素x{ if(T->data { if(T->rtag)//T没有右子树时,作为右孩子插入 { p=T->rchild; q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->rchild=q;T->rtag=0; q->rtag=1;q->rchild=p;//修改原线索 } elseBSTree_Insert_Key(T->rchild,x);//T有右子树时,插入右子树中 }//if elseif(T->data>x)//插入到左子树中 { if(!T->lchild)//T没有左子树时,作为左孩子插入 { q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->lchild=q; q->rtag=1;q->rchild=T;//修改自身的线索 } elseBSTree_Insert_Key(T->lchild,x);//T有左子树时,插入左子树中 }//if}//BSTree_Insert_Key9.37StatusBSTree_Delete_key(BiThrTree&T,intx)//在后继线索二叉排序树T中删除元素x{ BTNode*pre,*ptr,*suc;//ptr为x所在结点,pre和suc分别指向ptr的前驱和后继 p=T;last=NULL;//last始终指向当前结点p的前一个(前驱) while(!p->ltag)p=p->lchild;//找到中序起始元素 while(p) { if(p->data==x)//找到了元素x结点 { pre=last; ptr=p; } elseif(last&&last->data==x)suc=p;//找到了x的后继 if(p->rtag)p=p->rtag; else { p=p->rchild; while(!p->ltag)p=p->lchild; }//转到中序后继 last=p; }//while//借助中序遍历找到元素x及其前驱和后继结点 if(!ptr)returnERROR;//未找到待删结点 Delete_BSTree(ptr);//删除x结点 if(pre&&pre->rtag) pre->rchild=suc;//修改线索 returnOK;}//BSTree_Delete_keyvoidDelete_BSTree(BiThrTree&T)//课本上给出的删除二叉排序树的子树T的算法,按照线索二叉树的结构作了一些改动{ q=T; if(!T->ltag&&T->rtag)//结点无右子树,此时只需重接其左子树 T=T->lchild; elseif(T->ltag&&!T->rtag)//结点无左子树,此时只需重接其右子树 T=T->rchild; elseif(!T->ltag&&!T->rtag)//结点既有左子树又有右子树 { p=T;r=T->lchild; while(!r->rtag) { s=r; r=r->rchild;//找到结点的前驱r和r的双亲s } T->data=r->data;//用r代替T结点 if(s!=T) s->rchild=r->lchild; elses->lchild=r->lchild;//重接r的左子树到其双亲结点上 q=r; }//else free(q);//删除结点}//Delete_BSTree分析:本算法采用了先求出x结点的前驱和后继,再删除x结点的办法,这样修改线索时会比较简单,直接让前驱的线索指向后继就行了.如果试图在删除x结点的同时修改线索,则问题反而复杂化了.9.38voidBSTree_Merge(BiTree&T,BiTree&S)//把二叉排序树S合并到T中{ if(S->lchild)BSTree_Merge(T,S->lchild); if(S->rchild)BSTree_Merge(T,S->rchild);//合并子树 Insert_Key(T,S);//插入元素}//BSTree_MergevoidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置上{ if(S->data>T->data) { if(!T->rchild)T->rchild=S; elseInsert_Node(T->rchild,S); } elseif(S->datadata) { if(!T->lchild)T->lchild=S; elseInsert_Node(T->lchild,S); } S->lchild=NULL;//插入的新结点必须和原来的左右子树断绝关系 S->rchild=NULL;//否则会导致树结构的混乱}//Insert_Node分析:这是一个与课本上不同的插入算法.在合并过程中,并不释放或新建任何结点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把一棵树中的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱.9.39voidBSTree_Split(BiTree&T,BiTree&A,BiTree&B,intx)//把二叉排序树T分裂为两棵二叉排序树A和B,其中A的元素全部小于等于x,B的元素全部大于x{ if(T->lchild)BSTree_Split(T->lchild,A,B,x); if(T->rchild)BSTree_Split(T->rchild,A,B,x);//分裂左右子树 if(T->data<=x)Insert_Node(A,T); elseInsert_Node(B,T);//将元素结点插入合适的树中}//BSTree_SplitvoidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置上{ if(!T)T=S;//考虑到刚开始分裂时树A和树B为空的情况 elseif(S->data>T->data)//其余部分与上一题同 { if(!T->rchild)T->rchild=S; elseInsert_Node(T->rchild,S); } elseif(S->datadata) { if(!T->lchild)T->lchild=S; elseInsert_Node(T->lchild,S); } S->lchild=NULL; S->rchild=NULL; }//Insert_Key9.40typedefstruct{ intdata; intbf; intlsize;//lsize域表示该结点的左子树的结点总数加1 BlcNode*lchild,*rchild; }BlcNode,*BlcTree;//含lsize域的平衡二叉排序树类型BTNode*Locate_BlcTree(BlcTreeT,intk)//在含lsize域的平衡二叉排序树T中确定第k小的结点指针{ if(!T)returnNULL;//k小于1或大于树结点总数 if(T->lsize==k)returnT;//就是这个结点 elseif(T->lsize>k) returnLocate_BlcTree(T->lchild,k);//在左子树中寻找 elsereturnLocate_BlcTree(T->rchild,k-T->lsize);//在右子树中寻找,注意要修改k的值}//Locate_BlcTree9.41typedefstruct{ enum{LEAF,BRANCH}tag;//结点类型标识 intkeynum; BPLinkparent;//双亲指针 intkey[MAXCHILD];//关键字 union{ BPLinkchild[MAXCHILD];//非叶结点的孩子指针 struct{ rectype*info[MAXCHILD];//叶子结点的信息指针 BPNode*next;//指向下一个叶子结点的链接 }leaf; } }BPNode,*BPLink,*BPTree;//B+树及其结点类型StatusBPTree_Search(BPTreeT,intkey,BPNode*ptr,intpos)//B+树中按关键字随机查找的算法,返回包含关键字的叶子结点的指针ptr以及关键字在叶子结点中的位置pos{ p=T; while(p.tag==BRANCH)//沿分支向下查找 { for(i=0;ikeynum&&key>p->key[i];i++);//确定关键字所在子树 if(i==p->keynum)returnERROR;//关键字太大 p=p->child[i]; } for(i=0;ikeynum&&key!=p->key[i];i++);//在叶子结点中查找 if(i==p->keynum)returnERROR;//找不到关键字 ptr=p;pos=i; returnOK;}//BPTree_Search 9.42voidTrieTree_Insert_Key(TrieTree&T,StringTypekey)//在Trie树T中插入字符串key,StringType的结构见第四章{ q=(TrieNode*)malloc(sizeof(TrieNode)); q->kind=LEAF; q->lf.k=key;//建叶子结点 klen=key[0]; p=T;i=1; while(p&&i<=klen&&p->bh.ptr[ord(key[i])]) { last=p; p=p->bh.ptr[ord(key[i])]; i++; }//自上而下查找 if(p->kind==BRANCH)//如果最后落到分支结点(无同义词): { p->bh.ptr[ord(k
returni;
}//Search_Sq
分析:
本算法查找成功情况下的平均查找长度为ST.length/2,不成功情况下为ST.length.
9.26
intSearch_Bin_Recursive(SSTableST,intkey,intlow,inthigh)//折半查找的递归算法
if(low>high)return0;//查找不到时返回0
mid=(low+high)/2;
if(ST.elem[mid].key==key)returnmid;
elseif(ST.elem[mid].key>key)
returnSearch_Bin_Recursive(ST,key,low,mid-1);
elsereturnSearch_Bin_Recursive(ST,key,mid+1,high);
}
}//Search_Bin_Recursive
9.27
intLocate_Bin(SSTableST,intkey)//折半查找,返回小于或等于待查元素的最后一个结点号
int*r;
r=ST.elem;
if(key elseif(key>=r[ST.length].key)returnST.length; low=1;high=ST.length; while(low<=high) { mid=(low+high)/2; if(key>=r[mid].key&&key returnmid; elseif(key elselow=mid; }//本算法不存在查找失败的情况,不需要return0;}//Locate_Bin9.28typedefstruct{ intmaxkey; intfirstloc; }Index;typedefstruct{ int*elem; intlength; Indexidx[MAXBLOCK];//每块起始位置和最大元素,其中idx[0]不利用,其内容初始化为{0,0}以利于折半查找 intblknum;//块的数目 }IdxSqList;//索引顺序表类型intSearch_IdxSeq(IdxSqListL,intkey)//分块查找,用折半查找法确定记录所在块,块内采用顺序查找法{ if(key>L.idx[L.blknum].maxkey)returnERROR;//超过最大元素 low=1;high=L.blknum; found=0; while(low<=high&&!found)//折半查找记录所在块号mid { mid=(low+high)/2; if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey) found=1; elseif(key>L.idx[mid].maxkey) low=mid+1; elsehigh=mid-1; } i=L.idx[mid].firstloc;//块的下界 j=i+blksize-1;//块的上界 temp=L.elem[i-1];//保存相邻元素 L.elem[i-1]=key;//设置监视哨 for(k=j;L.elem[k]!=key;k--);//顺序查找 L.elem[i-1]=temp;//恢复元素 if(k returnk;}//Search_IdxSeq分析:在块内进行顺序查找时,如果需要设置监视哨,则必须先保存相邻块的相邻元素,以免数据丢失.9.29typedefstruct{ LNode*h;//h指向最小元素 LNode*t;//t指向上次查找的结点 }CSList;LNode*Search_CSList(CSList&L,intkey)//在有序单循环链表存储结构上的查找算法,假定每次查找都成功{ if(L.t->data==key)returnL.t; elseif(L.t->data>key) for(p=L.h,i=1;p->data!=key;p=p->next,i++); else for(p=L.t,i=L.tpos;p->data!=key;p=p->next,i++); L.t=p;//更新t指针 returnp;}//Search_CSList分析:由于题目中假定每次查找都是成功的,所以本算法中没有关于查找失败的处理.由微积分可得,在等概率情况下,平均查找长度约为n/3.9.30typedefstruct{ DLNode*pre; intdata; DLNode*next; }DLNode;typedefstruct{ DLNode*sp; intlength; }DSList;//供查找的双向循环链表类型DLNode*Search_DSList(DSList&L,intkey)//在有序双向循环链表存储结构上的查找算法,假定每次查找都成功{ p=L.sp; if(p->data>key) { while(p->data>key)p=p->pre; L.sp=p; } elseif(p->data { while(p->datanext; L.sp=p; } returnp;}//Search_DSList分析:本题的平均查找长度与上一题相同,也是n/3.9.31intlast=0,flag=1;intIs_BSTree(BitreeT)//判断二叉树T是否二叉排序树,是则返回1,否则返回0{ if(T->lchild&&flag)Is_BSTree(T->lchild); if(T->data last=T->data; if(T->rchild&&flag)Is_BSTree(T->rchild); returnflag;}//Is_BSTree9.32intlast=0;voidMaxLT_MinGT(BiTreeT,intx)//找到二叉排序树T中小于x的最大元素和大于x的最小元素{ if(T->lchild)MaxLT_MinGT(T->lchild,x);//本算法仍是借助中序遍历来实现 if(lastdata>=x)//找到了小于x的最大元素 printf("a=%d\n",last); if(last<=x&&T->data>x)//找到了大于x的最小元素 printf("b=%d\n",T->data); last=T->data; if(T->rchild)MaxLT_MinGT(T->rchild,x);}//MaxLT_MinGT9.33voidPrint_NLT(BiTreeT,intx)//从大到小输出二叉排序树T中所有不小于x的元素{ if(T->rchild)Print_NLT(T->rchild,x); if(T->data printf("%d\n",T->data); if(T->lchild)Print_NLT(T->lchild,x);//先右后左的中序遍历}//Print_NLT9.34voidDelete_NLT(BiTree&T,intx)//删除二叉排序树T中所有不小于x元素结点,并释放空间{ if(T->rchild)Delete_NLT(T->rchild,x); if(T->data q=T; T=T->lchild; free(q);//如果树根不小于x,则删除树根,并以左子树的根作为新的树根 if(T)Delete_NLT(T,x);//继续在左子树中执行算法}//Delete_NLT9.35voidPrint_Between(BiThrTreeT,inta,intb)//打印输出后继线索二叉排序树T中所有大于a且小于b的元素{ p=T; while(!p->ltag)p=p->lchild;//找到最小元素 while(p&&p->data { if(p->data>a)printf("%d\n",p->data);//输出符合条件的元素 if(p->rtag)p=p->rtag; else { p=p->rchild; while(!p->ltag)p=p->lchild; }//转到中序后继 }//while}//Print_Between9.36voidBSTree_Insert_Key(BiThrTree&T,intx)//在后继线索二叉排序树T中插入元素x{ if(T->data { if(T->rtag)//T没有右子树时,作为右孩子插入 { p=T->rchild; q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->rchild=q;T->rtag=0; q->rtag=1;q->rchild=p;//修改原线索 } elseBSTree_Insert_Key(T->rchild,x);//T有右子树时,插入右子树中 }//if elseif(T->data>x)//插入到左子树中 { if(!T->lchild)//T没有左子树时,作为左孩子插入 { q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->lchild=q; q->rtag=1;q->rchild=T;//修改自身的线索 } elseBSTree_Insert_Key(T->lchild,x);//T有左子树时,插入左子树中 }//if}//BSTree_Insert_Key9.37StatusBSTree_Delete_key(BiThrTree&T,intx)//在后继线索二叉排序树T中删除元素x{ BTNode*pre,*ptr,*suc;//ptr为x所在结点,pre和suc分别指向ptr的前驱和后继 p=T;last=NULL;//last始终指向当前结点p的前一个(前驱) while(!p->ltag)p=p->lchild;//找到中序起始元素 while(p) { if(p->data==x)//找到了元素x结点 { pre=last; ptr=p; } elseif(last&&last->data==x)suc=p;//找到了x的后继 if(p->rtag)p=p->rtag; else { p=p->rchild; while(!p->ltag)p=p->lchild; }//转到中序后继 last=p; }//while//借助中序遍历找到元素x及其前驱和后继结点 if(!ptr)returnERROR;//未找到待删结点 Delete_BSTree(ptr);//删除x结点 if(pre&&pre->rtag) pre->rchild=suc;//修改线索 returnOK;}//BSTree_Delete_keyvoidDelete_BSTree(BiThrTree&T)//课本上给出的删除二叉排序树的子树T的算法,按照线索二叉树的结构作了一些改动{ q=T; if(!T->ltag&&T->rtag)//结点无右子树,此时只需重接其左子树 T=T->lchild; elseif(T->ltag&&!T->rtag)//结点无左子树,此时只需重接其右子树 T=T->rchild; elseif(!T->ltag&&!T->rtag)//结点既有左子树又有右子树 { p=T;r=T->lchild; while(!r->rtag) { s=r; r=r->rchild;//找到结点的前驱r和r的双亲s } T->data=r->data;//用r代替T结点 if(s!=T) s->rchild=r->lchild; elses->lchild=r->lchild;//重接r的左子树到其双亲结点上 q=r; }//else free(q);//删除结点}//Delete_BSTree分析:本算法采用了先求出x结点的前驱和后继,再删除x结点的办法,这样修改线索时会比较简单,直接让前驱的线索指向后继就行了.如果试图在删除x结点的同时修改线索,则问题反而复杂化了.9.38voidBSTree_Merge(BiTree&T,BiTree&S)//把二叉排序树S合并到T中{ if(S->lchild)BSTree_Merge(T,S->lchild); if(S->rchild)BSTree_Merge(T,S->rchild);//合并子树 Insert_Key(T,S);//插入元素}//BSTree_MergevoidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置上{ if(S->data>T->data) { if(!T->rchild)T->rchild=S; elseInsert_Node(T->rchild,S); } elseif(S->datadata) { if(!T->lchild)T->lchild=S; elseInsert_Node(T->lchild,S); } S->lchild=NULL;//插入的新结点必须和原来的左右子树断绝关系 S->rchild=NULL;//否则会导致树结构的混乱}//Insert_Node分析:这是一个与课本上不同的插入算法.在合并过程中,并不释放或新建任何结点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把一棵树中的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱.9.39voidBSTree_Split(BiTree&T,BiTree&A,BiTree&B,intx)//把二叉排序树T分裂为两棵二叉排序树A和B,其中A的元素全部小于等于x,B的元素全部大于x{ if(T->lchild)BSTree_Split(T->lchild,A,B,x); if(T->rchild)BSTree_Split(T->rchild,A,B,x);//分裂左右子树 if(T->data<=x)Insert_Node(A,T); elseInsert_Node(B,T);//将元素结点插入合适的树中}//BSTree_SplitvoidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置上{ if(!T)T=S;//考虑到刚开始分裂时树A和树B为空的情况 elseif(S->data>T->data)//其余部分与上一题同 { if(!T->rchild)T->rchild=S; elseInsert_Node(T->rchild,S); } elseif(S->datadata) { if(!T->lchild)T->lchild=S; elseInsert_Node(T->lchild,S); } S->lchild=NULL; S->rchild=NULL; }//Insert_Key9.40typedefstruct{ intdata; intbf; intlsize;//lsize域表示该结点的左子树的结点总数加1 BlcNode*lchild,*rchild; }BlcNode,*BlcTree;//含lsize域的平衡二叉排序树类型BTNode*Locate_BlcTree(BlcTreeT,intk)//在含lsize域的平衡二叉排序树T中确定第k小的结点指针{ if(!T)returnNULL;//k小于1或大于树结点总数 if(T->lsize==k)returnT;//就是这个结点 elseif(T->lsize>k) returnLocate_BlcTree(T->lchild,k);//在左子树中寻找 elsereturnLocate_BlcTree(T->rchild,k-T->lsize);//在右子树中寻找,注意要修改k的值}//Locate_BlcTree9.41typedefstruct{ enum{LEAF,BRANCH}tag;//结点类型标识 intkeynum; BPLinkparent;//双亲指针 intkey[MAXCHILD];//关键字 union{ BPLinkchild[MAXCHILD];//非叶结点的孩子指针 struct{ rectype*info[MAXCHILD];//叶子结点的信息指针 BPNode*next;//指向下一个叶子结点的链接 }leaf; } }BPNode,*BPLink,*BPTree;//B+树及其结点类型StatusBPTree_Search(BPTreeT,intkey,BPNode*ptr,intpos)//B+树中按关键字随机查找的算法,返回包含关键字的叶子结点的指针ptr以及关键字在叶子结点中的位置pos{ p=T; while(p.tag==BRANCH)//沿分支向下查找 { for(i=0;ikeynum&&key>p->key[i];i++);//确定关键字所在子树 if(i==p->keynum)returnERROR;//关键字太大 p=p->child[i]; } for(i=0;ikeynum&&key!=p->key[i];i++);//在叶子结点中查找 if(i==p->keynum)returnERROR;//找不到关键字 ptr=p;pos=i; returnOK;}//BPTree_Search 9.42voidTrieTree_Insert_Key(TrieTree&T,StringTypekey)//在Trie树T中插入字符串key,StringType的结构见第四章{ q=(TrieNode*)malloc(sizeof(TrieNode)); q->kind=LEAF; q->lf.k=key;//建叶子结点 klen=key[0]; p=T;i=1; while(p&&i<=klen&&p->bh.ptr[ord(key[i])]) { last=p; p=p->bh.ptr[ord(key[i])]; i++; }//自上而下查找 if(p->kind==BRANCH)//如果最后落到分支结点(无同义词): { p->bh.ptr[ord(k
elseif(key>=r[ST.length].key)returnST.length;
low=1;high=ST.length;
while(low<=high)
if(key>=r[mid].key&&key returnmid; elseif(key elselow=mid; }//本算法不存在查找失败的情况,不需要return0;}//Locate_Bin9.28typedefstruct{ intmaxkey; intfirstloc; }Index;typedefstruct{ int*elem; intlength; Indexidx[MAXBLOCK];//每块起始位置和最大元素,其中idx[0]不利用,其内容初始化为{0,0}以利于折半查找 intblknum;//块的数目 }IdxSqList;//索引顺序表类型intSearch_IdxSeq(IdxSqListL,intkey)//分块查找,用折半查找法确定记录所在块,块内采用顺序查找法{ if(key>L.idx[L.blknum].maxkey)returnERROR;//超过最大元素 low=1;high=L.blknum; found=0; while(low<=high&&!found)//折半查找记录所在块号mid { mid=(low+high)/2; if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey) found=1; elseif(key>L.idx[mid].maxkey) low=mid+1; elsehigh=mid-1; } i=L.idx[mid].firstloc;//块的下界 j=i+blksize-1;//块的上界 temp=L.elem[i-1];//保存相邻元素 L.elem[i-1]=key;//设置监视哨 for(k=j;L.elem[k]!=key;k--);//顺序查找 L.elem[i-1]=temp;//恢复元素 if(k returnk;}//Search_IdxSeq分析:在块内进行顺序查找时,如果需要设置监视哨,则必须先保存相邻块的相邻元素,以免数据丢失.9.29typedefstruct{ LNode*h;//h指向最小元素 LNode*t;//t指向上次查找的结点 }CSList;LNode*Search_CSList(CSList&L,intkey)//在有序单循环链表存储结构上的查找算法,假定每次查找都成功{ if(L.t->data==key)returnL.t; elseif(L.t->data>key) for(p=L.h,i=1;p->data!=key;p=p->next,i++); else for(p=L.t,i=L.tpos;p->data!=key;p=p->next,i++); L.t=p;//更新t指针 returnp;}//Search_CSList分析:由于题目中假定每次查找都是成功的,所以本算法中没有关于查找失败的处理.由微积分可得,在等概率情况下,平均查找长度约为n/3.9.30typedefstruct{ DLNode*pre; intdata; DLNode*next; }DLNode;typedefstruct{ DLNode*sp; intlength; }DSList;//供查找的双向循环链表类型DLNode*Search_DSList(DSList&L,intkey)//在有序双向循环链表存储结构上的查找算法,假定每次查找都成功{ p=L.sp; if(p->data>key) { while(p->data>key)p=p->pre; L.sp=p; } elseif(p->data { while(p->datanext; L.sp=p; } returnp;}//Search_DSList分析:本题的平均查找长度与上一题相同,也是n/3.9.31intlast=0,flag=1;intIs_BSTree(BitreeT)//判断二叉树T是否二叉排序树,是则返回1,否则返回0{ if(T->lchild&&flag)Is_BSTree(T->lchild); if(T->data last=T->data; if(T->rchild&&flag)Is_BSTree(T->rchild); returnflag;}//Is_BSTree9.32intlast=0;voidMaxLT_MinGT(BiTreeT,intx)//找到二叉排序树T中小于x的最大元素和大于x的最小元素{ if(T->lchild)MaxLT_MinGT(T->lchild,x);//本算法仍是借助中序遍历来实现 if(lastdata>=x)//找到了小于x的最大元素 printf("a=%d\n",last); if(last<=x&&T->data>x)//找到了大于x的最小元素 printf("b=%d\n",T->data); last=T->data; if(T->rchild)MaxLT_MinGT(T->rchild,x);}//MaxLT_MinGT9.33voidPrint_NLT(BiTreeT,intx)//从大到小输出二叉排序树T中所有不小于x的元素{ if(T->rchild)Print_NLT(T->rchild,x); if(T->data printf("%d\n",T->data); if(T->lchild)Print_NLT(T->lchild,x);//先右后左的中序遍历}//Print_NLT9.34voidDelete_NLT(BiTree&T,intx)//删除二叉排序树T中所有不小于x元素结点,并释放空间{ if(T->rchild)Delete_NLT(T->rchild,x); if(T->data q=T; T=T->lchild; free(q);//如果树根不小于x,则删除树根,并以左子树的根作为新的树根 if(T)Delete_NLT(T,x);//继续在左子树中执行算法}//Delete_NLT9.35voidPrint_Between(BiThrTreeT,inta,intb)//打印输出后继线索二叉排序树T中所有大于a且小于b的元素{ p=T; while(!p->ltag)p=p->lchild;//找到最小元素 while(p&&p->data { if(p->data>a)printf("%d\n",p->data);//输出符合条件的元素 if(p->rtag)p=p->rtag; else { p=p->rchild; while(!p->ltag)p=p->lchild; }//转到中序后继 }//while}//Print_Between9.36voidBSTree_Insert_Key(BiThrTree&T,intx)//在后继线索二叉排序树T中插入元素x{ if(T->data { if(T->rtag)//T没有右子树时,作为右孩子插入 { p=T->rchild; q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->rchild=q;T->rtag=0; q->rtag=1;q->rchild=p;//修改原线索 } elseBSTree_Insert_Key(T->rchild,x);//T有右子树时,插入右子树中 }//if elseif(T->data>x)//插入到左子树中 { if(!T->lchild)//T没有左子树时,作为左孩子插入 { q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->lchild=q; q->rtag=1;q->rchild=T;//修改自身的线索 } elseBSTree_Insert_Key(T->lchild,x);//T有左子树时,插入左子树中 }//if}//BSTree_Insert_Key9.37StatusBSTree_Delete_key(BiThrTree&T,intx)//在后继线索二叉排序树T中删除元素x{ BTNode*pre,*ptr,*suc;//ptr为x所在结点,pre和suc分别指向ptr的前驱和后继 p=T;last=NULL;//last始终指向当前结点p的前一个(前驱) while(!p->ltag)p=p->lchild;//找到中序起始元素 while(p) { if(p->data==x)//找到了元素x结点 { pre=last; ptr=p; } elseif(last&&last->data==x)suc=p;//找到了x的后继 if(p->rtag)p=p->rtag; else { p=p->rchild; while(!p->ltag)p=p->lchild; }//转到中序后继 last=p; }//while//借助中序遍历找到元素x及其前驱和后继结点 if(!ptr)returnERROR;//未找到待删结点 Delete_BSTree(ptr);//删除x结点 if(pre&&pre->rtag) pre->rchild=suc;//修改线索 returnOK;}//BSTree_Delete_keyvoidDelete_BSTree(BiThrTree&T)//课本上给出的删除二叉排序树的子树T的算法,按照线索二叉树的结构作了一些改动{ q=T; if(!T->ltag&&T->rtag)//结点无右子树,此时只需重接其左子树 T=T->lchild; elseif(T->ltag&&!T->rtag)//结点无左子树,此时只需重接其右子树 T=T->rchild; elseif(!T->ltag&&!T->rtag)//结点既有左子树又有右子树 { p=T;r=T->lchild; while(!r->rtag) { s=r; r=r->rchild;//找到结点的前驱r和r的双亲s } T->data=r->data;//用r代替T结点 if(s!=T) s->rchild=r->lchild; elses->lchild=r->lchild;//重接r的左子树到其双亲结点上 q=r; }//else free(q);//删除结点}//Delete_BSTree分析:本算法采用了先求出x结点的前驱和后继,再删除x结点的办法,这样修改线索时会比较简单,直接让前驱的线索指向后继就行了.如果试图在删除x结点的同时修改线索,则问题反而复杂化了.9.38voidBSTree_Merge(BiTree&T,BiTree&S)//把二叉排序树S合并到T中{ if(S->lchild)BSTree_Merge(T,S->lchild); if(S->rchild)BSTree_Merge(T,S->rchild);//合并子树 Insert_Key(T,S);//插入元素}//BSTree_MergevoidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置上{ if(S->data>T->data) { if(!T->rchild)T->rchild=S; elseInsert_Node(T->rchild,S); } elseif(S->datadata) { if(!T->lchild)T->lchild=S; elseInsert_Node(T->lchild,S); } S->lchild=NULL;//插入的新结点必须和原来的左右子树断绝关系 S->rchild=NULL;//否则会导致树结构的混乱}//Insert_Node分析:这是一个与课本上不同的插入算法.在合并过程中,并不释放或新建任何结点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把一棵树中的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱.9.39voidBSTree_Split(BiTree&T,BiTree&A,BiTree&B,intx)//把二叉排序树T分裂为两棵二叉排序树A和B,其中A的元素全部小于等于x,B的元素全部大于x{ if(T->lchild)BSTree_Split(T->lchild,A,B,x); if(T->rchild)BSTree_Split(T->rchild,A,B,x);//分裂左右子树 if(T->data<=x)Insert_Node(A,T); elseInsert_Node(B,T);//将元素结点插入合适的树中}//BSTree_SplitvoidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置上{ if(!T)T=S;//考虑到刚开始分裂时树A和树B为空的情况 elseif(S->data>T->data)//其余部分与上一题同 { if(!T->rchild)T->rchild=S; elseInsert_Node(T->rchild,S); } elseif(S->datadata) { if(!T->lchild)T->lchild=S; elseInsert_Node(T->lchild,S); } S->lchild=NULL; S->rchild=NULL; }//Insert_Key9.40typedefstruct{ intdata; intbf; intlsize;//lsize域表示该结点的左子树的结点总数加1 BlcNode*lchild,*rchild; }BlcNode,*BlcTree;//含lsize域的平衡二叉排序树类型BTNode*Locate_BlcTree(BlcTreeT,intk)//在含lsize域的平衡二叉排序树T中确定第k小的结点指针{ if(!T)returnNULL;//k小于1或大于树结点总数 if(T->lsize==k)returnT;//就是这个结点 elseif(T->lsize>k) returnLocate_BlcTree(T->lchild,k);//在左子树中寻找 elsereturnLocate_BlcTree(T->rchild,k-T->lsize);//在右子树中寻找,注意要修改k的值}//Locate_BlcTree9.41typedefstruct{ enum{LEAF,BRANCH}tag;//结点类型标识 intkeynum; BPLinkparent;//双亲指针 intkey[MAXCHILD];//关键字 union{ BPLinkchild[MAXCHILD];//非叶结点的孩子指针 struct{ rectype*info[MAXCHILD];//叶子结点的信息指针 BPNode*next;//指向下一个叶子结点的链接 }leaf; } }BPNode,*BPLink,*BPTree;//B+树及其结点类型StatusBPTree_Search(BPTreeT,intkey,BPNode*ptr,intpos)//B+树中按关键字随机查找的算法,返回包含关键字的叶子结点的指针ptr以及关键字在叶子结点中的位置pos{ p=T; while(p.tag==BRANCH)//沿分支向下查找 { for(i=0;ikeynum&&key>p->key[i];i++);//确定关键字所在子树 if(i==p->keynum)returnERROR;//关键字太大 p=p->child[i]; } for(i=0;ikeynum&&key!=p->key[i];i++);//在叶子结点中查找 if(i==p->keynum)returnERROR;//找不到关键字 ptr=p;pos=i; returnOK;}//BPTree_Search 9.42voidTrieTree_Insert_Key(TrieTree&T,StringTypekey)//在Trie树T中插入字符串key,StringType的结构见第四章{ q=(TrieNode*)malloc(sizeof(TrieNode)); q->kind=LEAF; q->lf.k=key;//建叶子结点 klen=key[0]; p=T;i=1; while(p&&i<=klen&&p->bh.ptr[ord(key[i])]) { last=p; p=p->bh.ptr[ord(key[i])]; i++; }//自上而下查找 if(p->kind==BRANCH)//如果最后落到分支结点(无同义词): { p->bh.ptr[ord(k
returnmid;
elseif(key elselow=mid; }//本算法不存在查找失败的情况,不需要return0;}//Locate_Bin9.28typedefstruct{ intmaxkey; intfirstloc; }Index;typedefstruct{ int*elem; intlength; Indexidx[MAXBLOCK];//每块起始位置和最大元素,其中idx[0]不利用,其内容初始化为{0,0}以利于折半查找 intblknum;//块的数目 }IdxSqList;//索引顺序表类型intSearch_IdxSeq(IdxSqListL,intkey)//分块查找,用折半查找法确定记录所在块,块内采用顺序查找法{ if(key>L.idx[L.blknum].maxkey)returnERROR;//超过最大元素 low=1;high=L.blknum; found=0; while(low<=high&&!found)//折半查找记录所在块号mid { mid=(low+high)/2; if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey) found=1; elseif(key>L.idx[mid].maxkey) low=mid+1; elsehigh=mid-1; } i=L.idx[mid].firstloc;//块的下界 j=i+blksize-1;//块的上界 temp=L.elem[i-1];//保存相邻元素 L.elem[i-1]=key;//设置监视哨 for(k=j;L.elem[k]!=key;k--);//顺序查找 L.elem[i-1]=temp;//恢复元素 if(k returnk;}//Search_IdxSeq分析:在块内进行顺序查找时,如果需要设置监视哨,则必须先保存相邻块的相邻元素,以免数据丢失.9.29typedefstruct{ LNode*h;//h指向最小元素 LNode*t;//t指向上次查找的结点 }CSList;LNode*Search_CSList(CSList&L,intkey)//在有序单循环链表存储结构上的查找算法,假定每次查找都成功{ if(L.t->data==key)returnL.t; elseif(L.t->data>key) for(p=L.h,i=1;p->data!=key;p=p->next,i++); else for(p=L.t,i=L.tpos;p->data!=key;p=p->next,i++); L.t=p;//更新t指针 returnp;}//Search_CSList分析:由于题目中假定每次查找都是成功的,所以本算法中没有关于查找失败的处理.由微积分可得,在等概率情况下,平均查找长度约为n/3.9.30typedefstruct{ DLNode*pre; intdata; DLNode*next; }DLNode;typedefstruct{ DLNode*sp; intlength; }DSList;//供查找的双向循环链表类型DLNode*Search_DSList(DSList&L,intkey)//在有序双向循环链表存储结构上的查找算法,假定每次查找都成功{ p=L.sp; if(p->data>key) { while(p->data>key)p=p->pre; L.sp=p; } elseif(p->data { while(p->datanext; L.sp=p; } returnp;}//Search_DSList分析:本题的平均查找长度与上一题相同,也是n/3.9.31intlast=0,flag=1;intIs_BSTree(BitreeT)//判断二叉树T是否二叉排序树,是则返回1,否则返回0{ if(T->lchild&&flag)Is_BSTree(T->lchild); if(T->data last=T->data; if(T->rchild&&flag)Is_BSTree(T->rchild); returnflag;}//Is_BSTree9.32intlast=0;voidMaxLT_MinGT(BiTreeT,intx)//找到二叉排序树T中小于x的最大元素和大于x的最小元素{ if(T->lchild)MaxLT_MinGT(T->lchild,x);//本算法仍是借助中序遍历来实现 if(lastdata>=x)//找到了小于x的最大元素 printf("a=%d\n",last); if(last<=x&&T->data>x)//找到了大于x的最小元素 printf("b=%d\n",T->data); last=T->data; if(T->rchild)MaxLT_MinGT(T->rchild,x);}//MaxLT_MinGT9.33voidPrint_NLT(BiTreeT,intx)//从大到小输出二叉排序树T中所有不小于x的元素{ if(T->rchild)Print_NLT(T->rchild,x); if(T->data printf("%d\n",T->data); if(T->lchild)Print_NLT(T->lchild,x);//先右后左的中序遍历}//Print_NLT9.34voidDelete_NLT(BiTree&T,intx)//删除二叉排序树T中所有不小于x元素结点,并释放空间{ if(T->rchild)Delete_NLT(T->rchild,x); if(T->data q=T; T=T->lchild; free(q);//如果树根不小于x,则删除树根,并以左子树的根作为新的树根 if(T)Delete_NLT(T,x);//继续在左子树中执行算法}//Delete_NLT9.35voidPrint_Between(BiThrTreeT,inta,intb)//打印输出后继线索二叉排序树T中所有大于a且小于b的元素{ p=T; while(!p->ltag)p=p->lchild;//找到最小元素 while(p&&p->data { if(p->data>a)printf("%d\n",p->data);//输出符合条件的元素 if(p->rtag)p=p->rtag; else { p=p->rchild; while(!p->ltag)p=p->lchild; }//转到中序后继 }//while}//Print_Between9.36voidBSTree_Insert_Key(BiThrTree&T,intx)//在后继线索二叉排序树T中插入元素x{ if(T->data { if(T->rtag)//T没有右子树时,作为右孩子插入 { p=T->rchild; q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->rchild=q;T->rtag=0; q->rtag=1;q->rchild=p;//修改原线索 } elseBSTree_Insert_Key(T->rchild,x);//T有右子树时,插入右子树中 }//if elseif(T->data>x)//插入到左子树中 { if(!T->lchild)//T没有左子树时,作为左孩子插入 { q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->lchild=q; q->rtag=1;q->rchild=T;//修改自身的线索 } elseBSTree_Insert_Key(T->lchild,x);//T有左子树时,插入左子树中 }//if}//BSTree_Insert_Key9.37StatusBSTree_Delete_key(BiThrTree&T,intx)//在后继线索二叉排序树T中删除元素x{ BTNode*pre,*ptr,*suc;//ptr为x所在结点,pre和suc分别指向ptr的前驱和后继 p=T;last=NULL;//last始终指向当前结点p的前一个(前驱) while(!p->ltag)p=p->lchild;//找到中序起始元素 while(p) { if(p->data==x)//找到了元素x结点 { pre=last; ptr=p; } elseif(last&&last->data==x)suc=p;//找到了x的后继 if(p->rtag)p=p->rtag; else { p=p->rchild; while(!p->ltag)p=p->lchild; }//转到中序后继 last=p; }//while//借助中序遍历找到元素x及其前驱和后继结点 if(!ptr)returnERROR;//未找到待删结点 Delete_BSTree(ptr);//删除x结点 if(pre&&pre->rtag) pre->rchild=suc;//修改线索 returnOK;}//BSTree_Delete_keyvoidDelete_BSTree(BiThrTree&T)//课本上给出的删除二叉排序树的子树T的算法,按照线索二叉树的结构作了一些改动{ q=T; if(!T->ltag&&T->rtag)//结点无右子树,此时只需重接其左子树 T=T->lchild; elseif(T->ltag&&!T->rtag)//结点无左子树,此时只需重接其右子树 T=T->rchild; elseif(!T->ltag&&!T->rtag)//结点既有左子树又有右子树 { p=T;r=T->lchild; while(!r->rtag) { s=r; r=r->rchild;//找到结点的前驱r和r的双亲s } T->data=r->data;//用r代替T结点 if(s!=T) s->rchild=r->lchild; elses->lchild=r->lchild;//重接r的左子树到其双亲结点上 q=r; }//else free(q);//删除结点}//Delete_BSTree分析:本算法采用了先求出x结点的前驱和后继,再删除x结点的办法,这样修改线索时会比较简单,直接让前驱的线索指向后继就行了.如果试图在删除x结点的同时修改线索,则问题反而复杂化了.9.38voidBSTree_Merge(BiTree&T,BiTree&S)//把二叉排序树S合并到T中{ if(S->lchild)BSTree_Merge(T,S->lchild); if(S->rchild)BSTree_Merge(T,S->rchild);//合并子树 Insert_Key(T,S);//插入元素}//BSTree_MergevoidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置上{ if(S->data>T->data) { if(!T->rchild)T->rchild=S; elseInsert_Node(T->rchild,S); } elseif(S->datadata) { if(!T->lchild)T->lchild=S; elseInsert_Node(T->lchild,S); } S->lchild=NULL;//插入的新结点必须和原来的左右子树断绝关系 S->rchild=NULL;//否则会导致树结构的混乱}//Insert_Node分析:这是一个与课本上不同的插入算法.在合并过程中,并不释放或新建任何结点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把一棵树中的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱.9.39voidBSTree_Split(BiTree&T,BiTree&A,BiTree&B,intx)//把二叉排序树T分裂为两棵二叉排序树A和B,其中A的元素全部小于等于x,B的元素全部大于x{ if(T->lchild)BSTree_Split(T->lchild,A,B,x); if(T->rchild)BSTree_Split(T->rchild,A,B,x);//分裂左右子树 if(T->data<=x)Insert_Node(A,T); elseInsert_Node(B,T);//将元素结点插入合适的树中}//BSTree_SplitvoidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置上{ if(!T)T=S;//考虑到刚开始分裂时树A和树B为空的情况 elseif(S->data>T->data)//其余部分与上一题同 { if(!T->rchild)T->rchild=S; elseInsert_Node(T->rchild,S); } elseif(S->datadata) { if(!T->lchild)T->lchild=S; elseInsert_Node(T->lchild,S); } S->lchild=NULL; S->rchild=NULL; }//Insert_Key9.40typedefstruct{ intdata; intbf; intlsize;//lsize域表示该结点的左子树的结点总数加1 BlcNode*lchild,*rchild; }BlcNode,*BlcTree;//含lsize域的平衡二叉排序树类型BTNode*Locate_BlcTree(BlcTreeT,intk)//在含lsize域的平衡二叉排序树T中确定第k小的结点指针{ if(!T)returnNULL;//k小于1或大于树结点总数 if(T->lsize==k)returnT;//就是这个结点 elseif(T->lsize>k) returnLocate_BlcTree(T->lchild,k);//在左子树中寻找 elsereturnLocate_BlcTree(T->rchild,k-T->lsize);//在右子树中寻找,注意要修改k的值}//Locate_BlcTree9.41typedefstruct{ enum{LEAF,BRANCH}tag;//结点类型标识 intkeynum; BPLinkparent;//双亲指针 intkey[MAXCHILD];//关键字 union{ BPLinkchild[MAXCHILD];//非叶结点的孩子指针 struct{ rectype*info[MAXCHILD];//叶子结点的信息指针 BPNode*next;//指向下一个叶子结点的链接 }leaf; } }BPNode,*BPLink,*BPTree;//B+树及其结点类型StatusBPTree_Search(BPTreeT,intkey,BPNode*ptr,intpos)//B+树中按关键字随机查找的算法,返回包含关键字的叶子结点的指针ptr以及关键字在叶子结点中的位置pos{ p=T; while(p.tag==BRANCH)//沿分支向下查找 { for(i=0;ikeynum&&key>p->key[i];i++);//确定关键字所在子树 if(i==p->keynum)returnERROR;//关键字太大 p=p->child[i]; } for(i=0;ikeynum&&key!=p->key[i];i++);//在叶子结点中查找 if(i==p->keynum)returnERROR;//找不到关键字 ptr=p;pos=i; returnOK;}//BPTree_Search 9.42voidTrieTree_Insert_Key(TrieTree&T,StringTypekey)//在Trie树T中插入字符串key,StringType的结构见第四章{ q=(TrieNode*)malloc(sizeof(TrieNode)); q->kind=LEAF; q->lf.k=key;//建叶子结点 klen=key[0]; p=T;i=1; while(p&&i<=klen&&p->bh.ptr[ord(key[i])]) { last=p; p=p->bh.ptr[ord(key[i])]; i++; }//自上而下查找 if(p->kind==BRANCH)//如果最后落到分支结点(无同义词): { p->bh.ptr[ord(k
elselow=mid;
}//本算法不存在查找失败的情况,不需要return0;
}//Locate_Bin
9.28
typedefstruct{
intmaxkey;
intfirstloc;
}Index;
int*elem;
intlength;
Indexidx[MAXBLOCK];//每块起始位置和最大元素,其中idx[0]不利用,其内容初始化为{0,0}以利于折半查找
intblknum;//块的数目
}IdxSqList;//索引顺序表类型
intSearch_IdxSeq(IdxSqListL,intkey)//分块查找,用折半查找法确定记录所在块,块内采用顺序查找法
if(key>L.idx[L.blknum].maxkey)returnERROR;//超过最大元素
low=1;high=L.blknum;
found=0;
while(low<=high&&!
found)//折半查找记录所在块号mid
if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey)
found=1;
elseif(key>L.idx[mid].maxkey)
low=mid+1;
elsehigh=mid-1;
i=L.idx[mid].firstloc;//块的下界
j=i+blksize-1;//块的上界
temp=L.elem[i-1];//保存相邻元素
L.elem[i-1]=key;//设置监视哨
for(k=j;L.elem[k]!
=key;k--);//顺序查找
L.elem[i-1]=temp;//恢复元素
if(k
returnk;
}//Search_IdxSeq
在块内进行顺序查找时,如果需要设置监视哨,则必须先保存相邻块的相邻元素,以免数据丢失.
9.29
LNode*h;//h指向最小元素
LNode*t;//t指向上次查找的结点
}CSList;
LNode*Search_CSList(CSList&L,intkey)//在有序单循环链表存储结构上的查找算法,假定每次查找都成功
if(L.t->data==key)returnL.t;
elseif(L.t->data>key)
for(p=L.h,i=1;p->data!
=key;p=p->next,i++);
else
for(p=L.t,i=L.tpos;p->data!
L.t=p;//更新t指针
returnp;
}//Search_CSList
由于题目中假定每次查找都是成功的,所以本算法中没有关于查找失败的处理.由微积分可得,在等概率情况下,平均查找长度约为n/3.
9.30
DLNode*pre;
intdata;
DLNode*next;
}DLNode;
DLNode*sp;
}DSList;//供查找的双向循环链表类型
DLNode*Search_DSList(DSList&L,intkey)//在有序双向循环链表存储结构上的查找算法,假定每次查找都成功
p=L.sp;
if(p->data>key)
while(p->data>key)p=p->pre;
L.sp=p;
elseif(p->data { while(p->datanext; L.sp=p; } returnp;}//Search_DSList分析:本题的平均查找长度与上一题相同,也是n/3.9.31intlast=0,flag=1;intIs_BSTree(BitreeT)//判断二叉树T是否二叉排序树,是则返回1,否则返回0{ if(T->lchild&&flag)Is_BSTree(T->lchild); if(T->data last=T->data; if(T->rchild&&flag)Is_BSTree(T->rchild); returnflag;}//Is_BSTree9.32intlast=0;voidMaxLT_MinGT(BiTreeT,intx)//找到二叉排序树T中小于x的最大元素和大于x的最小元素{ if(T->lchild)MaxLT_MinGT(T->lchild,x);//本算法仍是借助中序遍历来实现 if(lastdata>=x)//找到了小于x的最大元素 printf("a=%d\n",last); if(last<=x&&T->data>x)//找到了大于x的最小元素 printf("b=%d\n",T->data); last=T->data; if(T->rchild)MaxLT_MinGT(T->rchild,x);}//MaxLT_MinGT9.33voidPrint_NLT(BiTreeT,intx)//从大到小输出二叉排序树T中所有不小于x的元素{ if(T->rchild)Print_NLT(T->rchild,x); if(T->data printf("%d\n",T->data); if(T->lchild)Print_NLT(T->lchild,x);//先右后左的中序遍历}//Print_NLT9.34voidDelete_NLT(BiTree&T,intx)//删除二叉排序树T中所有不小于x元素结点,并释放空间{ if(T->rchild)Delete_NLT(T->rchild,x); if(T->data q=T; T=T->lchild; free(q);//如果树根不小于x,则删除树根,并以左子树的根作为新的树根 if(T)Delete_NLT(T,x);//继续在左子树中执行算法}//Delete_NLT9.35voidPrint_Between(BiThrTreeT,inta,intb)//打印输出后继线索二叉排序树T中所有大于a且小于b的元素{ p=T; while(!p->ltag)p=p->lchild;//找到最小元素 while(p&&p->data { if(p->data>a)printf("%d\n",p->data);//输出符合条件的元素 if(p->rtag)p=p->rtag; else { p=p->rchild; while(!p->ltag)p=p->lchild; }//转到中序后继 }//while}//Print_Between9.36voidBSTree_Insert_Key(BiThrTree&T,intx)//在后继线索二叉排序树T中插入元素x{ if(T->data { if(T->rtag)//T没有右子树时,作为右孩子插入 { p=T->rchild; q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->rchild=q;T->rtag=0; q->rtag=1;q->rchild=p;//修改原线索 } elseBSTree_Insert_Key(T->rchild,x);//T有右子树时,插入右子树中 }//if elseif(T->data>x)//插入到左子树中 { if(!T->lchild)//T没有左子树时,作为左孩子插入 { q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->lchild=q; q->rtag=1;q->rchild=T;//修改自身的线索 } elseBSTree_Insert_Key(T->lchild,x);//T有左子树时,插入左子树中 }//if}//BSTree_Insert_Key9.37StatusBSTree_Delete_key(BiThrTree&T,intx)//在后继线索二叉排序树T中删除元素x{ BTNode*pre,*ptr,*suc;//ptr为x所在结点,pre和suc分别指向ptr的前驱和后继 p=T;last=NULL;//last始终指向当前结点p的前一个(前驱) while(!p->ltag)p=p->lchild;//找到中序起始元素 while(p) { if(p->data==x)//找到了元素x结点 { pre=last; ptr=p; } elseif(last&&last->data==x)suc=p;//找到了x的后继 if(p->rtag)p=p->rtag; else { p=p->rchild; while(!p->ltag)p=p->lchild; }//转到中序后继 last=p; }//while//借助中序遍历找到元素x及其前驱和后继结点 if(!ptr)returnERROR;//未找到待删结点 Delete_BSTree(ptr);//删除x结点 if(pre&&pre->rtag) pre->rchild=suc;//修改线索 returnOK;}//BSTree_Delete_keyvoidDelete_BSTree(BiThrTree&T)//课本上给出的删除二叉排序树的子树T的算法,按照线索二叉树的结构作了一些改动{ q=T; if(!T->ltag&&T->rtag)//结点无右子树,此时只需重接其左子树 T=T->lchild; elseif(T->ltag&&!T->rtag)//结点无左子树,此时只需重接其右子树 T=T->rchild; elseif(!T->ltag&&!T->rtag)//结点既有左子树又有右子树 { p=T;r=T->lchild; while(!r->rtag) { s=r; r=r->rchild;//找到结点的前驱r和r的双亲s } T->data=r->data;//用r代替T结点 if(s!=T) s->rchild=r->lchild; elses->lchild=r->lchild;//重接r的左子树到其双亲结点上 q=r; }//else free(q);//删除结点}//Delete_BSTree分析:本算法采用了先求出x结点的前驱和后继,再删除x结点的办法,这样修改线索时会比较简单,直接让前驱的线索指向后继就行了.如果试图在删除x结点的同时修改线索,则问题反而复杂化了.9.38voidBSTree_Merge(BiTree&T,BiTree&S)//把二叉排序树S合并到T中{ if(S->lchild)BSTree_Merge(T,S->lchild); if(S->rchild)BSTree_Merge(T,S->rchild);//合并子树 Insert_Key(T,S);//插入元素}//BSTree_MergevoidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置上{ if(S->data>T->data) { if(!T->rchild)T->rchild=S; elseInsert_Node(T->rchild,S); } elseif(S->datadata) { if(!T->lchild)T->lchild=S; elseInsert_Node(T->lchild,S); } S->lchild=NULL;//插入的新结点必须和原来的左右子树断绝关系 S->rchild=NULL;//否则会导致树结构的混乱}//Insert_Node分析:这是一个与课本上不同的插入算法.在合并过程中,并不释放或新建任何结点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把一棵树中的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱.9.39voidBSTree_Split(BiTree&T,BiTree&A,BiTree&B,intx)//把二叉排序树T分裂为两棵二叉排序树A和B,其中A的元素全部小于等于x,B的元素全部大于x{ if(T->lchild)BSTree_Split(T->lchild,A,B,x); if(T->rchild)BSTree_Split(T->rchild,A,B,x);//分裂左右子树 if(T->data<=x)Insert_Node(A,T); elseInsert_Node(B,T);//将元素结点插入合适的树中}//BSTree_SplitvoidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置上{ if(!T)T=S;//考虑到刚开始分裂时树A和树B为空的情况 elseif(S->data>T->data)//其余部分与上一题同 { if(!T->rchild)T->rchild=S; elseInsert_Node(T->rchild,S); } elseif(S->datadata) { if(!T->lchild)T->lchild=S; elseInsert_Node(T->lchild,S); } S->lchild=NULL; S->rchild=NULL; }//Insert_Key9.40typedefstruct{ intdata; intbf; intlsize;//lsize域表示该结点的左子树的结点总数加1 BlcNode*lchild,*rchild; }BlcNode,*BlcTree;//含lsize域的平衡二叉排序树类型BTNode*Locate_BlcTree(BlcTreeT,intk)//在含lsize域的平衡二叉排序树T中确定第k小的结点指针{ if(!T)returnNULL;//k小于1或大于树结点总数 if(T->lsize==k)returnT;//就是这个结点 elseif(T->lsize>k) returnLocate_BlcTree(T->lchild,k);//在左子树中寻找 elsereturnLocate_BlcTree(T->rchild,k-T->lsize);//在右子树中寻找,注意要修改k的值}//Locate_BlcTree9.41typedefstruct{ enum{LEAF,BRANCH}tag;//结点类型标识 intkeynum; BPLinkparent;//双亲指针 intkey[MAXCHILD];//关键字 union{ BPLinkchild[MAXCHILD];//非叶结点的孩子指针 struct{ rectype*info[MAXCHILD];//叶子结点的信息指针 BPNode*next;//指向下一个叶子结点的链接 }leaf; } }BPNode,*BPLink,*BPTree;//B+树及其结点类型StatusBPTree_Search(BPTreeT,intkey,BPNode*ptr,intpos)//B+树中按关键字随机查找的算法,返回包含关键字的叶子结点的指针ptr以及关键字在叶子结点中的位置pos{ p=T; while(p.tag==BRANCH)//沿分支向下查找 { for(i=0;ikeynum&&key>p->key[i];i++);//确定关键字所在子树 if(i==p->keynum)returnERROR;//关键字太大 p=p->child[i]; } for(i=0;ikeynum&&key!=p->key[i];i++);//在叶子结点中查找 if(i==p->keynum)returnERROR;//找不到关键字 ptr=p;pos=i; returnOK;}//BPTree_Search 9.42voidTrieTree_Insert_Key(TrieTree&T,StringTypekey)//在Trie树T中插入字符串key,StringType的结构见第四章{ q=(TrieNode*)malloc(sizeof(TrieNode)); q->kind=LEAF; q->lf.k=key;//建叶子结点 klen=key[0]; p=T;i=1; while(p&&i<=klen&&p->bh.ptr[ord(key[i])]) { last=p; p=p->bh.ptr[ord(key[i])]; i++; }//自上而下查找 if(p->kind==BRANCH)//如果最后落到分支结点(无同义词): { p->bh.ptr[ord(k
while(p->datanext;
}//Search_DSList
本题的平均查找长度与上一题相同,也是n/3.
9.31
intlast=0,flag=1;
intIs_BSTree(BitreeT)//判断二叉树T是否二叉排序树,是则返回1,否则返回0
if(T->lchild&&flag)Is_BSTree(T->lchild);
if(T->data last=T->data; if(T->rchild&&flag)Is_BSTree(T->rchild); returnflag;}//Is_BSTree9.32intlast=0;voidMaxLT_MinGT(BiTreeT,intx)//找到二叉排序树T中小于x的最大元素和大于x的最小元素{ if(T->lchild)MaxLT_MinGT(T->lchild,x);//本算法仍是借助中序遍历来实现 if(lastdata>=x)//找到了小于x的最大元素 printf("a=%d\n",last); if(last<=x&&T->data>x)//找到了大于x的最小元素 printf("b=%d\n",T->data); last=T->data; if(T->rchild)MaxLT_MinGT(T->rchild,x);}//MaxLT_MinGT9.33voidPrint_NLT(BiTreeT,intx)//从大到小输出二叉排序树T中所有不小于x的元素{ if(T->rchild)Print_NLT(T->rchild,x); if(T->data printf("%d\n",T->data); if(T->lchild)Print_NLT(T->lchild,x);//先右后左的中序遍历}//Print_NLT9.34voidDelete_NLT(BiTree&T,intx)//删除二叉排序树T中所有不小于x元素结点,并释放空间{ if(T->rchild)Delete_NLT(T->rchild,x); if(T->data q=T; T=T->lchild; free(q);//如果树根不小于x,则删除树根,并以左子树的根作为新的树根 if(T)Delete_NLT(T,x);//继续在左子树中执行算法}//Delete_NLT9.35voidPrint_Between(BiThrTreeT,inta,intb)//打印输出后继线索二叉排序树T中所有大于a且小于b的元素{ p=T; while(!p->ltag)p=p->lchild;//找到最小元素 while(p&&p->data { if(p->data>a)printf("%d\n",p->data);//输出符合条件的元素 if(p->rtag)p=p->rtag; else { p=p->rchild; while(!p->ltag)p=p->lchild; }//转到中序后继 }//while}//Print_Between9.36voidBSTree_Insert_Key(BiThrTree&T,intx)//在后继线索二叉排序树T中插入元素x{ if(T->data { if(T->rtag)//T没有右子树时,作为右孩子插入 { p=T->rchild; q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->rchild=q;T->rtag=0; q->rtag=1;q->rchild=p;//修改原线索 } elseBSTree_Insert_Key(T->rchild,x);//T有右子树时,插入右子树中 }//if elseif(T->data>x)//插入到左子树中 { if(!T->lchild)//T没有左子树时,作为左孩子插入 { q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->lchild=q; q->rtag=1;q->rchild=T;//修改自身的线索 } elseBSTree_Insert_Key(T->lchild,x);//T有左子树时,插入左子树中 }//if}//BSTree_Insert_Key9.37StatusBSTree_Delete_key(BiThrTree&T,intx)//在后继线索二叉排序树T中删除元素x{ BTNode*pre,*ptr,*suc;//ptr为x所在结点,pre和suc分别指向ptr的前驱和后继 p=T;last=NULL;//last始终指向当前结点p的前一个(前驱) while(!p->ltag)p=p->lchild;//找到中序起始元素 while(p) { if(p->data==x)//找到了元素x结点 { pre=last; ptr=p; } elseif(last&&last->data==x)suc=p;//找到了x的后继 if(p->rtag)p=p->rtag; else { p=p->rchild; while(!p->ltag)p=p->lchild; }//转到中序后继 last=p; }//while//借助中序遍历找到元素x及其前驱和后继结点 if(!ptr)returnERROR;//未找到待删结点 Delete_BSTree(ptr);//删除x结点 if(pre&&pre->rtag) pre->rchild=suc;//修改线索 returnOK;}//BSTree_Delete_keyvoidDelete_BSTree(BiThrTree&T)//课本上给出的删除二叉排序树的子树T的算法,按照线索二叉树的结构作了一些改动{ q=T; if(!T->ltag&&T->rtag)//结点无右子树,此时只需重接其左子树 T=T->lchild; elseif(T->ltag&&!T->rtag)//结点无左子树,此时只需重接其右子树 T=T->rchild; elseif(!T->ltag&&!T->rtag)//结点既有左子树又有右子树 { p=T;r=T->lchild; while(!r->rtag) { s=r; r=r->rchild;//找到结点的前驱r和r的双亲s } T->data=r->data;//用r代替T结点 if(s!=T) s->rchild=r->lchild; elses->lchild=r->lchild;//重接r的左子树到其双亲结点上 q=r; }//else free(q);//删除结点}//Delete_BSTree分析:本算法采用了先求出x结点的前驱和后继,再删除x结点的办法,这样修改线索时会比较简单,直接让前驱的线索指向后继就行了.如果试图在删除x结点的同时修改线索,则问题反而复杂化了.9.38voidBSTree_Merge(BiTree&T,BiTree&S)//把二叉排序树S合并到T中{ if(S->lchild)BSTree_Merge(T,S->lchild); if(S->rchild)BSTree_Merge(T,S->rchild);//合并子树 Insert_Key(T,S);//插入元素}//BSTree_MergevoidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置上{ if(S->data>T->data) { if(!T->rchild)T->rchild=S; elseInsert_Node(T->rchild,S); } elseif(S->datadata) { if(!T->lchild)T->lchild=S; elseInsert_Node(T->lchild,S); } S->lchild=NULL;//插入的新结点必须和原来的左右子树断绝关系 S->rchild=NULL;//否则会导致树结构的混乱}//Insert_Node分析:这是一个与课本上不同的插入算法.在合并过程中,并不释放或新建任何结点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把一棵树中的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱.9.39voidBSTree_Split(BiTree&T,BiTree&A,BiTree&B,intx)//把二叉排序树T分裂为两棵二叉排序树A和B,其中A的元素全部小于等于x,B的元素全部大于x{ if(T->lchild)BSTree_Split(T->lchild,A,B,x); if(T->rchild)BSTree_Split(T->rchild,A,B,x);//分裂左右子树 if(T->data<=x)Insert_Node(A,T); elseInsert_Node(B,T);//将元素结点插入合适的树中}//BSTree_SplitvoidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置上{ if(!T)T=S;//考虑到刚开始分裂时树A和树B为空的情况 elseif(S->data>T->data)//其余部分与上一题同 { if(!T->rchild)T->rchild=S; elseInsert_Node(T->rchild,S); } elseif(S->datadata) { if(!T->lchild)T->lchild=S; elseInsert_Node(T->lchild,S); } S->lchild=NULL; S->rchild=NULL; }//Insert_Key9.40typedefstruct{ intdata; intbf; intlsize;//lsize域表示该结点的左子树的结点总数加1 BlcNode*lchild,*rchild; }BlcNode,*BlcTree;//含lsize域的平衡二叉排序树类型BTNode*Locate_BlcTree(BlcTreeT,intk)//在含lsize域的平衡二叉排序树T中确定第k小的结点指针{ if(!T)returnNULL;//k小于1或大于树结点总数 if(T->lsize==k)returnT;//就是这个结点 elseif(T->lsize>k) returnLocate_BlcTree(T->lchild,k);//在左子树中寻找 elsereturnLocate_BlcTree(T->rchild,k-T->lsize);//在右子树中寻找,注意要修改k的值}//Locate_BlcTree9.41typedefstruct{ enum{LEAF,BRANCH}tag;//结点类型标识 intkeynum; BPLinkparent;//双亲指针 intkey[MAXCHILD];//关键字 union{ BPLinkchild[MAXCHILD];//非叶结点的孩子指针 struct{ rectype*info[MAXCHILD];//叶子结点的信息指针 BPNode*next;//指向下一个叶子结点的链接 }leaf; } }BPNode,*BPLink,*BPTree;//B+树及其结点类型StatusBPTree_Search(BPTreeT,intkey,BPNode*ptr,intpos)//B+树中按关键字随机查找的算法,返回包含关键字的叶子结点的指针ptr以及关键字在叶子结点中的位置pos{ p=T; while(p.tag==BRANCH)//沿分支向下查找 { for(i=0;ikeynum&&key>p->key[i];i++);//确定关键字所在子树 if(i==p->keynum)returnERROR;//关键字太大 p=p->child[i]; } for(i=0;ikeynum&&key!=p->key[i];i++);//在叶子结点中查找 if(i==p->keynum)returnERROR;//找不到关键字 ptr=p;pos=i; returnOK;}//BPTree_Search 9.42voidTrieTree_Insert_Key(TrieTree&T,StringTypekey)//在Trie树T中插入字符串key,StringType的结构见第四章{ q=(TrieNode*)malloc(sizeof(TrieNode)); q->kind=LEAF; q->lf.k=key;//建叶子结点 klen=key[0]; p=T;i=1; while(p&&i<=klen&&p->bh.ptr[ord(key[i])]) { last=p; p=p->bh.ptr[ord(key[i])]; i++; }//自上而下查找 if(p->kind==BRANCH)//如果最后落到分支结点(无同义词): { p->bh.ptr[ord(k
last=T->data;
if(T->rchild&&flag)Is_BSTree(T->rchild);
returnflag;
}//Is_BSTree
9.32
intlast=0;
voidMaxLT_MinGT(BiTreeT,intx)//找到二叉排序树T中小于x的最大元素和大于x的最小元素
if(T->lchild)MaxLT_MinGT(T->lchild,x);//本算法仍是借助中序遍历来实现
if(lastdata>=x)//找到了小于x的最大元素
printf("a=%d\n",last);
if(last<=x&&T->data>x)//找到了大于x的最小元素
printf("b=%d\n",T->data);
if(T->rchild)MaxLT_MinGT(T->rchild,x);
}//MaxLT_MinGT
9.33
voidPrint_NLT(BiTreeT,intx)//从大到小输出二叉排序树T中所有不小于x的元素
if(T->rchild)Print_NLT(T->rchild,x);
if(T->data printf("%d\n",T->data); if(T->lchild)Print_NLT(T->lchild,x);//先右后左的中序遍历}//Print_NLT9.34voidDelete_NLT(BiTree&T,intx)//删除二叉排序树T中所有不小于x元素结点,并释放空间{ if(T->rchild)Delete_NLT(T->rchild,x); if(T->data q=T; T=T->lchild; free(q);//如果树根不小于x,则删除树根,并以左子树的根作为新的树根 if(T)Delete_NLT(T,x);//继续在左子树中执行算法}//Delete_NLT9.35voidPrint_Between(BiThrTreeT,inta,intb)//打印输出后继线索二叉排序树T中所有大于a且小于b的元素{ p=T; while(!p->ltag)p=p->lchild;//找到最小元素 while(p&&p->data { if(p->data>a)printf("%d\n",p->data);//输出符合条件的元素 if(p->rtag)p=p->rtag; else { p=p->rchild; while(!p->ltag)p=p->lchild; }//转到中序后继 }//while}//Print_Between9.36voidBSTree_Insert_Key(BiThrTree&T,intx)//在后继线索二叉排序树T中插入元素x{ if(T->data { if(T->rtag)//T没有右子树时,作为右孩子插入 { p=T->rchild; q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->rchild=q;T->rtag=0; q->rtag=1;q->rchild=p;//修改原线索 } elseBSTree_Insert_Key(T->rchild,x);//T有右子树时,插入右子树中 }//if elseif(T->data>x)//插入到左子树中 { if(!T->lchild)//T没有左子树时,作为左孩子插入 { q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->lchild=q; q->rtag=1;q->rchild=T;//修改自身的线索 } elseBSTree_Insert_Key(T->lchild,x);//T有左子树时,插入左子树中 }//if}//BSTree_Insert_Key9.37StatusBSTree_Delete_key(BiThrTree&T,intx)//在后继线索二叉排序树T中删除元素x{ BTNode*pre,*ptr,*suc;//ptr为x所在结点,pre和suc分别指向ptr的前驱和后继 p=T;last=NULL;//last始终指向当前结点p的前一个(前驱) while(!p->ltag)p=p->lchild;//找到中序起始元素 while(p) { if(p->data==x)//找到了元素x结点 { pre=last; ptr=p; } elseif(last&&last->data==x)suc=p;//找到了x的后继 if(p->rtag)p=p->rtag; else { p=p->rchild; while(!p->ltag)p=p->lchild; }//转到中序后继 last=p; }//while//借助中序遍历找到元素x及其前驱和后继结点 if(!ptr)returnERROR;//未找到待删结点 Delete_BSTree(ptr);//删除x结点 if(pre&&pre->rtag) pre->rchild=suc;//修改线索 returnOK;}//BSTree_Delete_keyvoidDelete_BSTree(BiThrTree&T)//课本上给出的删除二叉排序树的子树T的算法,按照线索二叉树的结构作了一些改动{ q=T; if(!T->ltag&&T->rtag)//结点无右子树,此时只需重接其左子树 T=T->lchild; elseif(T->ltag&&!T->rtag)//结点无左子树,此时只需重接其右子树 T=T->rchild; elseif(!T->ltag&&!T->rtag)//结点既有左子树又有右子树 { p=T;r=T->lchild; while(!r->rtag) { s=r; r=r->rchild;//找到结点的前驱r和r的双亲s } T->data=r->data;//用r代替T结点 if(s!=T) s->rchild=r->lchild; elses->lchild=r->lchild;//重接r的左子树到其双亲结点上 q=r; }//else free(q);//删除结点}//Delete_BSTree分析:本算法采用了先求出x结点的前驱和后继,再删除x结点的办法,这样修改线索时会比较简单,直接让前驱的线索指向后继就行了.如果试图在删除x结点的同时修改线索,则问题反而复杂化了.9.38voidBSTree_Merge(BiTree&T,BiTree&S)//把二叉排序树S合并到T中{ if(S->lchild)BSTree_Merge(T,S->lchild); if(S->rchild)BSTree_Merge(T,S->rchild);//合并子树 Insert_Key(T,S);//插入元素}//BSTree_MergevoidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置上{ if(S->data>T->data) { if(!T->rchild)T->rchild=S; elseInsert_Node(T->rchild,S); } elseif(S->datadata) { if(!T->lchild)T->lchild=S; elseInsert_Node(T->lchild,S); } S->lchild=NULL;//插入的新结点必须和原来的左右子树断绝关系 S->rchild=NULL;//否则会导致树结构的混乱}//Insert_Node分析:这是一个与课本上不同的插入算法.在合并过程中,并不释放或新建任何结点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把一棵树中的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱.9.39voidBSTree_Split(BiTree&T,BiTree&A,BiTree&B,intx)//把二叉排序树T分裂为两棵二叉排序树A和B,其中A的元素全部小于等于x,B的元素全部大于x{ if(T->lchild)BSTree_Split(T->lchild,A,B,x); if(T->rchild)BSTree_Split(T->rchild,A,B,x);//分裂左右子树 if(T->data<=x)Insert_Node(A,T); elseInsert_Node(B,T);//将元素结点插入合适的树中}//BSTree_SplitvoidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置上{ if(!T)T=S;//考虑到刚开始分裂时树A和树B为空的情况 elseif(S->data>T->data)//其余部分与上一题同 { if(!T->rchild)T->rchild=S; elseInsert_Node(T->rchild,S); } elseif(S->datadata) { if(!T->lchild)T->lchild=S; elseInsert_Node(T->lchild,S); } S->lchild=NULL; S->rchild=NULL; }//Insert_Key9.40typedefstruct{ intdata; intbf; intlsize;//lsize域表示该结点的左子树的结点总数加1 BlcNode*lchild,*rchild; }BlcNode,*BlcTree;//含lsize域的平衡二叉排序树类型BTNode*Locate_BlcTree(BlcTreeT,intk)//在含lsize域的平衡二叉排序树T中确定第k小的结点指针{ if(!T)returnNULL;//k小于1或大于树结点总数 if(T->lsize==k)returnT;//就是这个结点 elseif(T->lsize>k) returnLocate_BlcTree(T->lchild,k);//在左子树中寻找 elsereturnLocate_BlcTree(T->rchild,k-T->lsize);//在右子树中寻找,注意要修改k的值}//Locate_BlcTree9.41typedefstruct{ enum{LEAF,BRANCH}tag;//结点类型标识 intkeynum; BPLinkparent;//双亲指针 intkey[MAXCHILD];//关键字 union{ BPLinkchild[MAXCHILD];//非叶结点的孩子指针 struct{ rectype*info[MAXCHILD];//叶子结点的信息指针 BPNode*next;//指向下一个叶子结点的链接 }leaf; } }BPNode,*BPLink,*BPTree;//B+树及其结点类型StatusBPTree_Search(BPTreeT,intkey,BPNode*ptr,intpos)//B+树中按关键字随机查找的算法,返回包含关键字的叶子结点的指针ptr以及关键字在叶子结点中的位置pos{ p=T; while(p.tag==BRANCH)//沿分支向下查找 { for(i=0;ikeynum&&key>p->key[i];i++);//确定关键字所在子树 if(i==p->keynum)returnERROR;//关键字太大 p=p->child[i]; } for(i=0;ikeynum&&key!=p->key[i];i++);//在叶子结点中查找 if(i==p->keynum)returnERROR;//找不到关键字 ptr=p;pos=i; returnOK;}//BPTree_Search 9.42voidTrieTree_Insert_Key(TrieTree&T,StringTypekey)//在Trie树T中插入字符串key,StringType的结构见第四章{ q=(TrieNode*)malloc(sizeof(TrieNode)); q->kind=LEAF; q->lf.k=key;//建叶子结点 klen=key[0]; p=T;i=1; while(p&&i<=klen&&p->bh.ptr[ord(key[i])]) { last=p; p=p->bh.ptr[ord(key[i])]; i++; }//自上而下查找 if(p->kind==BRANCH)//如果最后落到分支结点(无同义词): { p->bh.ptr[ord(k
printf("%d\n",T->data);
if(T->lchild)Print_NLT(T->lchild,x);//先右后左的中序遍历
}//Print_NLT
9.34
voidDelete_NLT(BiTree&T,intx)//删除二叉排序树T中所有不小于x元素结点,并释放空间
if(T->rchild)Delete_NLT(T->rchild,x);
if(T->data q=T; T=T->lchild; free(q);//如果树根不小于x,则删除树根,并以左子树的根作为新的树根 if(T)Delete_NLT(T,x);//继续在左子树中执行算法}//Delete_NLT9.35voidPrint_Between(BiThrTreeT,inta,intb)//打印输出后继线索二叉排序树T中所有大于a且小于b的元素{ p=T; while(!p->ltag)p=p->lchild;//找到最小元素 while(p&&p->data { if(p->data>a)printf("%d\n",p->data);//输出符合条件的元素 if(p->rtag)p=p->rtag; else { p=p->rchild; while(!p->ltag)p=p->lchild; }//转到中序后继 }//while}//Print_Between9.36voidBSTree_Insert_Key(BiThrTree&T,intx)//在后继线索二叉排序树T中插入元素x{ if(T->data { if(T->rtag)//T没有右子树时,作为右孩子插入 { p=T->rchild; q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->rchild=q;T->rtag=0; q->rtag=1;q->rchild=p;//修改原线索 } elseBSTree_Insert_Key(T->rchild,x);//T有右子树时,插入右子树中 }//if elseif(T->data>x)//插入到左子树中 { if(!T->lchild)//T没有左子树时,作为左孩子插入 { q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->lchild=q; q->rtag=1;q->rchild=T;//修改自身的线索 } elseBSTree_Insert_Key(T->lchild,x);//T有左子树时,插入左子树中 }//if}//BSTree_Insert_Key9.37StatusBSTree_Delete_key(BiThrTree&T,intx)//在后继线索二叉排序树T中删除元素x{ BTNode*pre,*ptr,*suc;//ptr为x所在结点,pre和suc分别指向ptr的前驱和后继 p=T;last=NULL;//last始终指向当前结点p的前一个(前驱) while(!p->ltag)p=p->lchild;//找到中序起始元素 while(p) { if(p->data==x)//找到了元素x结点 { pre=last; ptr=p; } elseif(last&&last->data==x)suc=p;//找到了x的后继 if(p->rtag)p=p->rtag; else { p=p->rchild; while(!p->ltag)p=p->lchild; }//转到中序后继 last=p; }//while//借助中序遍历找到元素x及其前驱和后继结点 if(!ptr)returnERROR;//未找到待删结点 Delete_BSTree(ptr);//删除x结点 if(pre&&pre->rtag) pre->rchild=suc;//修改线索 returnOK;}//BSTree_Delete_keyvoidDelete_BSTree(BiThrTree&T)//课本上给出的删除二叉排序树的子树T的算法,按照线索二叉树的结构作了一些改动{ q=T; if(!T->ltag&&T->rtag)//结点无右子树,此时只需重接其左子树 T=T->lchild; elseif(T->ltag&&!T->rtag)//结点无左子树,此时只需重接其右子树 T=T->rchild; elseif(!T->ltag&&!T->rtag)//结点既有左子树又有右子树 { p=T;r=T->lchild; while(!r->rtag) { s=r; r=r->rchild;//找到结点的前驱r和r的双亲s } T->data=r->data;//用r代替T结点 if(s!=T) s->rchild=r->lchild; elses->lchild=r->lchild;//重接r的左子树到其双亲结点上 q=r; }//else free(q);//删除结点}//Delete_BSTree分析:本算法采用了先求出x结点的前驱和后继,再删除x结点的办法,这样修改线索时会比较简单,直接让前驱的线索指向后继就行了.如果试图在删除x结点的同时修改线索,则问题反而复杂化了.9.38voidBSTree_Merge(BiTree&T,BiTree&S)//把二叉排序树S合并到T中{ if(S->lchild)BSTree_Merge(T,S->lchild); if(S->rchild)BSTree_Merge(T,S->rchild);//合并子树 Insert_Key(T,S);//插入元素}//BSTree_MergevoidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置上{ if(S->data>T->data) { if(!T->rchild)T->rchild=S; elseInsert_Node(T->rchild,S); } elseif(S->datadata) { if(!T->lchild)T->lchild=S; elseInsert_Node(T->lchild,S); } S->lchild=NULL;//插入的新结点必须和原来的左右子树断绝关系 S->rchild=NULL;//否则会导致树结构的混乱}//Insert_Node分析:这是一个与课本上不同的插入算法.在合并过程中,并不释放或新建任何结点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把一棵树中的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱.9.39voidBSTree_Split(BiTree&T,BiTree&A,BiTree&B,intx)//把二叉排序树T分裂为两棵二叉排序树A和B,其中A的元素全部小于等于x,B的元素全部大于x{ if(T->lchild)BSTree_Split(T->lchild,A,B,x); if(T->rchild)BSTree_Split(T->rchild,A,B,x);//分裂左右子树 if(T->data<=x)Insert_Node(A,T); elseInsert_Node(B,T);//将元素结点插入合适的树中}//BSTree_SplitvoidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置上{ if(!T)T=S;//考虑到刚开始分裂时树A和树B为空的情况 elseif(S->data>T->data)//其余部分与上一题同 { if(!T->rchild)T->rchild=S; elseInsert_Node(T->rchild,S); } elseif(S->datadata) { if(!T->lchild)T->lchild=S; elseInsert_Node(T->lchild,S); } S->lchild=NULL; S->rchild=NULL; }//Insert_Key9.40typedefstruct{ intdata; intbf; intlsize;//lsize域表示该结点的左子树的结点总数加1 BlcNode*lchild,*rchild; }BlcNode,*BlcTree;//含lsize域的平衡二叉排序树类型BTNode*Locate_BlcTree(BlcTreeT,intk)//在含lsize域的平衡二叉排序树T中确定第k小的结点指针{ if(!T)returnNULL;//k小于1或大于树结点总数 if(T->lsize==k)returnT;//就是这个结点 elseif(T->lsize>k) returnLocate_BlcTree(T->lchild,k);//在左子树中寻找 elsereturnLocate_BlcTree(T->rchild,k-T->lsize);//在右子树中寻找,注意要修改k的值}//Locate_BlcTree9.41typedefstruct{ enum{LEAF,BRANCH}tag;//结点类型标识 intkeynum; BPLinkparent;//双亲指针 intkey[MAXCHILD];//关键字 union{ BPLinkchild[MAXCHILD];//非叶结点的孩子指针 struct{ rectype*info[MAXCHILD];//叶子结点的信息指针 BPNode*next;//指向下一个叶子结点的链接 }leaf; } }BPNode,*BPLink,*BPTree;//B+树及其结点类型StatusBPTree_Search(BPTreeT,intkey,BPNode*ptr,intpos)//B+树中按关键字随机查找的算法,返回包含关键字的叶子结点的指针ptr以及关键字在叶子结点中的位置pos{ p=T; while(p.tag==BRANCH)//沿分支向下查找 { for(i=0;ikeynum&&key>p->key[i];i++);//确定关键字所在子树 if(i==p->keynum)returnERROR;//关键字太大 p=p->child[i]; } for(i=0;ikeynum&&key!=p->key[i];i++);//在叶子结点中查找 if(i==p->keynum)returnERROR;//找不到关键字 ptr=p;pos=i; returnOK;}//BPTree_Search 9.42voidTrieTree_Insert_Key(TrieTree&T,StringTypekey)//在Trie树T中插入字符串key,StringType的结构见第四章{ q=(TrieNode*)malloc(sizeof(TrieNode)); q->kind=LEAF; q->lf.k=key;//建叶子结点 klen=key[0]; p=T;i=1; while(p&&i<=klen&&p->bh.ptr[ord(key[i])]) { last=p; p=p->bh.ptr[ord(key[i])]; i++; }//自上而下查找 if(p->kind==BRANCH)//如果最后落到分支结点(无同义词): { p->bh.ptr[ord(k
q=T;
T=T->lchild;
free(q);//如果树根不小于x,则删除树根,并以左子树的根作为新的树根
if(T)Delete_NLT(T,x);//继续在左子树中执行算法
}//Delete_NLT
9.35
voidPrint_Between(BiThrTreeT,inta,intb)//打印输出后继线索二叉排序树T中所有大于a且小于b的元素
p=T;
while(!
p->ltag)p=p->lchild;//找到最小元素
while(p&&p->data
if(p->data>a)printf("%d\n",p->data);//输出符合条件的元素
if(p->rtag)p=p->rtag;
p=p->rchild;
p->ltag)p=p->lchild;
}//转到中序后继
}//while
}//Print_Between
9.36
voidBSTree_Insert_Key(BiThrTree&T,intx)//在后继线索二叉排序树T中插入元素x
if(T->data { if(T->rtag)//T没有右子树时,作为右孩子插入 { p=T->rchild; q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->rchild=q;T->rtag=0; q->rtag=1;q->rchild=p;//修改原线索 } elseBSTree_Insert_Key(T->rchild,x);//T有右子树时,插入右子树中 }//if elseif(T->data>x)//插入到左子树中 { if(!T->lchild)//T没有左子树时,作为左孩子插入 { q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->lchild=q; q->rtag=1;q->rchild=T;//修改自身的线索 } elseBSTree_Insert_Key(T->lchild,x);//T有左子树时,插入左子树中 }//if}//BSTree_Insert_Key9.37StatusBSTree_Delete_key(BiThrTree&T,intx)//在后继线索二叉排序树T中删除元素x{ BTNode*pre,*ptr,*suc;//ptr为x所在结点,pre和suc分别指向ptr的前驱和后继 p=T;last=NULL;//last始终指向当前结点p的前一个(前驱) while(!p->ltag)p=p->lchild;//找到中序起始元素 while(p) { if(p->data==x)//找到了元素x结点 { pre=last; ptr=p; } elseif(last&&last->data==x)suc=p;//找到了x的后继 if(p->rtag)p=p->rtag; else { p=p->rchild; while(!p->ltag)p=p->lchild; }//转到中序后继 last=p; }//while//借助中序遍历找到元素x及其前驱和后继结点 if(!ptr)returnERROR;//未找到待删结点 Delete_BSTree(ptr);//删除x结点 if(pre&&pre->rtag) pre->rchild=suc;//修改线索 returnOK;}//BSTree_Delete_keyvoidDelete_BSTree(BiThrTree&T)//课本上给出的删除二叉排序树的子树T的算法,按照线索二叉树的结构作了一些改动{ q=T; if(!T->ltag&&T->rtag)//结点无右子树,此时只需重接其左子树 T=T->lchild; elseif(T->ltag&&!T->rtag)//结点无左子树,此时只需重接其右子树 T=T->rchild; elseif(!T->ltag&&!T->rtag)//结点既有左子树又有右子树 { p=T;r=T->lchild; while(!r->rtag) { s=r; r=r->rchild;//找到结点的前驱r和r的双亲s } T->data=r->data;//用r代替T结点 if(s!=T) s->rchild=r->lchild; elses->lchild=r->lchild;//重接r的左子树到其双亲结点上 q=r; }//else free(q);//删除结点}//Delete_BSTree分析:本算法采用了先求出x结点的前驱和后继,再删除x结点的办法,这样修改线索时会比较简单,直接让前驱的线索指向后继就行了.如果试图在删除x结点的同时修改线索,则问题反而复杂化了.9.38voidBSTree_Merge(BiTree&T,BiTree&S)//把二叉排序树S合并到T中{ if(S->lchild)BSTree_Merge(T,S->lchild); if(S->rchild)BSTree_Merge(T,S->rchild);//合并子树 Insert_Key(T,S);//插入元素}//BSTree_MergevoidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置上{ if(S->data>T->data) { if(!T->rchild)T->rchild=S; elseInsert_Node(T->rchild,S); } elseif(S->datadata) { if(!T->lchild)T->lchild=S; elseInsert_Node(T->lchild,S); } S->lchild=NULL;//插入的新结点必须和原来的左右子树断绝关系 S->rchild=NULL;//否则会导致树结构的混乱}//Insert_Node分析:这是一个与课本上不同的插入算法.在合并过程中,并不释放或新建任何结点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把一棵树中的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱.9.39voidBSTree_Split(BiTree&T,BiTree&A,BiTree&B,intx)//把二叉排序树T分裂为两棵二叉排序树A和B,其中A的元素全部小于等于x,B的元素全部大于x{ if(T->lchild)BSTree_Split(T->lchild,A,B,x); if(T->rchild)BSTree_Split(T->rchild,A,B,x);//分裂左右子树 if(T->data<=x)Insert_Node(A,T); elseInsert_Node(B,T);//将元素结点插入合适的树中}//BSTree_SplitvoidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置上{ if(!T)T=S;//考虑到刚开始分裂时树A和树B为空的情况 elseif(S->data>T->data)//其余部分与上一题同 { if(!T->rchild)T->rchild=S; elseInsert_Node(T->rchild,S); } elseif(S->datadata) { if(!T->lchild)T->lchild=S; elseInsert_Node(T->lchild,S); } S->lchild=NULL; S->rchild=NULL; }//Insert_Key9.40typedefstruct{ intdata; intbf; intlsize;//lsize域表示该结点的左子树的结点总数加1 BlcNode*lchild,*rchild; }BlcNode,*BlcTree;//含lsize域的平衡二叉排序树类型BTNode*Locate_BlcTree(BlcTreeT,intk)//在含lsize域的平衡二叉排序树T中确定第k小的结点指针{ if(!T)returnNULL;//k小于1或大于树结点总数 if(T->lsize==k)returnT;//就是这个结点 elseif(T->lsize>k) returnLocate_BlcTree(T->lchild,k);//在左子树中寻找 elsereturnLocate_BlcTree(T->rchild,k-T->lsize);//在右子树中寻找,注意要修改k的值}//Locate_BlcTree9.41typedefstruct{ enum{LEAF,BRANCH}tag;//结点类型标识 intkeynum; BPLinkparent;//双亲指针 intkey[MAXCHILD];//关键字 union{ BPLinkchild[MAXCHILD];//非叶结点的孩子指针 struct{ rectype*info[MAXCHILD];//叶子结点的信息指针 BPNode*next;//指向下一个叶子结点的链接 }leaf; } }BPNode,*BPLink,*BPTree;//B+树及其结点类型StatusBPTree_Search(BPTreeT,intkey,BPNode*ptr,intpos)//B+树中按关键字随机查找的算法,返回包含关键字的叶子结点的指针ptr以及关键字在叶子结点中的位置pos{ p=T; while(p.tag==BRANCH)//沿分支向下查找 { for(i=0;ikeynum&&key>p->key[i];i++);//确定关键字所在子树 if(i==p->keynum)returnERROR;//关键字太大 p=p->child[i]; } for(i=0;ikeynum&&key!=p->key[i];i++);//在叶子结点中查找 if(i==p->keynum)returnERROR;//找不到关键字 ptr=p;pos=i; returnOK;}//BPTree_Search 9.42voidTrieTree_Insert_Key(TrieTree&T,StringTypekey)//在Trie树T中插入字符串key,StringType的结构见第四章{ q=(TrieNode*)malloc(sizeof(TrieNode)); q->kind=LEAF; q->lf.k=key;//建叶子结点 klen=key[0]; p=T;i=1; while(p&&i<=klen&&p->bh.ptr[ord(key[i])]) { last=p; p=p->bh.ptr[ord(key[i])]; i++; }//自上而下查找 if(p->kind==BRANCH)//如果最后落到分支结点(无同义词): { p->bh.ptr[ord(k
if(T->rtag)//T没有右子树时,作为右孩子插入
p=T->rchild;
q=(BiThrNode*)malloc(sizeof(BiThrNode));
q->data=x;
T->rchild=q;T->rtag=0;
q->rtag=1;q->rchild=p;//修改原线索
elseBSTree_Insert_Key(T->rchild,x);//T有右子树时,插入右子树中
}//if
elseif(T->data>x)//插入到左子树中
if(!
T->lchild)//T没有左子树时,作为左孩子插入
T->lchild=q;
q->rtag=1;q->rchild=T;//修改自身的线索
elseBSTree_Insert_Key(T->lchild,x);//T有左子树时,插入左子树中
}//BSTree_Insert_Key
9.37
StatusBSTree_Delete_key(BiThrTree&T,intx)//在后继线索二叉排序树T中删除元素x
BTNode*pre,*ptr,*suc;//ptr为x所在结点,pre和suc分别指向ptr的前驱和后继
p=T;last=NULL;//last始终指向当前结点p的前一个(前驱)
p->ltag)p=p->lchild;//找到中序起始元素
while(p)
if(p->data==x)//找到了元素x结点
pre=last;
ptr=p;
elseif(last&&last->data==x)suc=p;//找到了x的后继
last=p;
}//while//借助中序遍历找到元素x及其前驱和后继结点
ptr)returnERROR;//未找到待删结点
Delete_BSTree(ptr);//删除x结点
if(pre&&pre->rtag)
pre->rchild=suc;//修改线索
returnOK;
}//BSTree_Delete_key
voidDelete_BSTree(BiThrTree&T)//课本上给出的删除二叉排序树的子树T的算法,按照线索二叉树的结构作了一些改动
T->ltag&&T->rtag)//结点无右子树,此时只需重接其左子树
elseif(T->ltag&&!
T->rtag)//结点无左子树,此时只需重接其右子树
T=T->rchild;
elseif(!
T->ltag&&!
T->rtag)//结点既有左子树又有右子树
p=T;r=T->lchild;
r->rtag)
s=r;
r=r->rchild;//找到结点的前驱r和r的双亲s
T->data=r->data;//用r代替T结点
if(s!
=T)
s->rchild=r->lchild;
elses->lchild=r->lchild;//重接r的左子树到其双亲结点上
q=r;
}//else
free(q);//删除结点
}//Delete_BSTree
本算法采用了先求出x结点的前驱和后继,再删除x结点的办法,这样修改线索时会比较简单,直接让前驱的线索指向后继就行了.如果试图在删除x结点的同时修改线索,则问题反而复杂化了.
9.38
voidBSTree_Merge(BiTree&T,BiTree&S)//把二叉排序树S合并到T中
if(S->lchild)BSTree_Merge(T,S->lchild);
if(S->rchild)BSTree_Merge(T,S->rchild);//合并子树
Insert_Key(T,S);//插入元素
}//BSTree_Merge
voidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置上
if(S->data>T->data)
T->rchild)T->rchild=S;
elseInsert_Node(T->rchild,S);
elseif(S->datadata)
T->lchild)T->lchild=S;
elseInsert_Node(T->lchild,S);
S->lchild=NULL;//插入的新结点必须和原来的左右子树断绝关系
S->rchild=NULL;//否则会导致树结构的混乱
}//Insert_Node
这是一个与课本上不同的插入算法.在合并过程中,并不释放或新建任何结点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把一棵树中的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱.
9.39
voidBSTree_Split(BiTree&T,BiTree&A,BiTree&B,intx)//把二叉排序树T分裂为两棵二叉排序树A和B,其中A的元素全部小于等于x,B的元素全部大于x
if(T->lchild)BSTree_Split(T->lchild,A,B,x);
if(T->rchild)BSTree_Split(T->rchild,A,B,x);//分裂左右子树
if(T->data<=x)Insert_Node(A,T);
elseInsert_Node(B,T);//将元素结点插入合适的树中
}//BSTree_Split
T)T=S;//考虑到刚开始分裂时树A和树B为空的情况
elseif(S->data>T->data)//其余部分与上一题同
S->lchild=NULL;
S->rchild=NULL;
}//Insert_Key
9.40
intbf;
intlsize;//lsize域表示该结点的左子树的结点总数加1
BlcNode*lchild,*rchild;
}BlcNode,*BlcTree;//含lsize域的平衡二叉排序树类型
BTNode*Locate_BlcTree(BlcTreeT,intk)//在含lsize域的平衡二叉排序树T中确定第k小的结点指针
T)returnNULL;//k小于1或大于树结点总数
if(T->lsize==k)returnT;//就是这个结点
elseif(T->lsize>k)
returnLocate_BlcTree(T->lchild,k);//在左子树中寻找
elsereturnLocate_BlcTree(T->rchild,k-T->lsize);//在右子树中寻找,注意要修改k的值
}//Locate_BlcTree
9.41
enum{LEAF,BRANCH}tag;//结点类型标识
intkeynum;
BPLinkparent;//双亲指针
intkey[MAXCHILD];//关键字
union{
BPLinkchild[MAXCHILD];//非叶结点的孩子指针
struct{
rectype*info[MAXCHILD];//叶子结点的信息指针
BPNode*next;//指向下一个叶子结点的链接
}leaf;
}BPNode,*BPLink,*BPTree;//B+树及其结点类型
StatusBPTree_Search(BPTreeT,intkey,BPNode*ptr,intpos)//B+树中按关键字随机查找的算法,返回包含关键字的叶子结点的指针ptr以及关键字在叶子结点中的位置pos
while(p.tag==BRANCH)//沿分支向下查找
for(i=0;ikeynum&&key>p->key[i];i++);//确定关键字所在子树
if(i==p->keynum)returnERROR;//关键字太大
p=p->child[i];
for(i=0;ikeynum&&key!
=p->key[i];i++);//在叶子结点中查找
if(i==p->keynum)returnERROR;//找不到关键字
ptr=p;pos=i;
}//BPTree_Search
9.42
voidTrieTree_Insert_Key(TrieTree&T,StringTypekey)//在Trie树T中插入字符串key,StringType的结构见第四章
q=(TrieNode*)malloc(sizeof(TrieNode));
q->kind=LEAF;
q->lf.k=key;//建叶子结点
klen=key[0];
p=T;i=1;
while(p&&i<=klen&&p->bh.ptr[ord(key[i])])
p=p->bh.ptr[ord(key[i])];
i++;
}//自上而下查找
if(p->kind==BRANCH)//如果最后落到分支结点(无同义词):
p->bh.ptr[ord(k
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2