清华考研真题第八章查找

第九intSearch_Sq(SSTableST,intkey)//在有序表上顺序查找的算法,监视哨设在高下标{ em[i].key<key)returnERROR;returni;分析:本算法查找成功情况下的平均查找长度为ST.length/2,不成功情况下为intSearch_Bin_Recursive(SSTableST,intkey,intlow,inthigh)//折半查找的递归{if(low>highreturn0;查找不到时返回0 em[mid].key==key)returnmid;elseif(S returnSearch_Bin_Recursive(ST,key,low,mid-1);}intLocate_Bin(SSTableST,intkey)//折半查找,返回小于或等于待查元素的最后一个{int*r;if(key<r.key)returnelseif(key>=r[ST.length].key)returnST.length;{if(key>=r[mid].key&&key<r[mid+1].key)查找结束的条件returnelseif(key<r[mid].key)high=mid;elselow=mid;本算法不存在查找失败的情况,returntypedefstructtypedefstruct

intmaxkey;intfirstloc;}int*elem;intIndexidx[MAXBLOCK每块起始位置和最大元素,]不利用,其内容初始化为{0,0}以利于折半查intblknum;IdxSqListintSearch_IdxSeq(IdxSqListL,intkey)//分块查找,用折半查找法确定记录所在块{if(key>L.idx[L.blknum].maxkey)returnERROR超过最大元素while(low<=high&&!found){elseif(key>L.idx[mid].maxkey)elsehigh=mid-}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<i)returnERROR未找到returnk;typedefstructLNode*h;//hLNode*t;//t}LNode*Search_CSList(CSList&L,intkey)//在有序单循环链表结构上的查找算SList&L,intkey)//在有序单循环链表结构上的查找算,{if(L.t->data==key)returnL.t;elseif(L.t->data>key)for(p=L.t,i=L.tpos;p->data!=key;p=p-L.t=p;treturn积分可得,在等概率情况下,n/3.typedefstructtypedefstruct

DLNode*pre;intdata;DLNode*next;}DLNode*sp;intlength;DSList;檎业 蜓妨幢砝嘈DLNode*Search_DSList(DSList&L,intkey)//在有序双向循环链表结构上的查找{if(p-{while(p->data>key)p=p->pre;}elseif(p-{while(p->data<key)p=p->next;}returnintintIs_BSTree(BitreeT)//判断二叉树T是否二叉排序树,是则返回1,否则{if(T->lchild&&flag)Is_BSTree(T-if(T->data<last)flag=0;//与其中序前驱相比last=T-returnflag;intvoidMaxLT_MinGT(BiTreeT,intx)//T中小于xx的最{if(last<x&&T->data>=x)//x的最大元素if(last<=x&&T->data>x)找到了大于xif(T->rchild)MaxLT_MinGT(T-voidPrint_NLT(BiTreeT,intx)//Tx{if(T->rchild)Print_NLT(T-if(T->data<x)exit();//当遇到小于x的元素时立即结束运printf("%d\n",T-)//voidDelete_NLT(BiTree&T,intx)//Tx元素结点,并释放{if(T->rchild)Delete_NLT(T-if(T->data<x)exit();//当遇到小于x的元素时立即结束运free(q);//如果树根不小于x,则删除树根,并以左的根作为新的树voidPrint_Between(BiThrTreeT,inta,intb)//T中所ab的元素{while(!p->ltag)p=p->lchild;找到最小元素while(p&&p-{if(p->data>a)printf("%d\n",p->data);输出符合条件的元素if(p->rtag)p=p->rtag;{while(!p->ltag)p=p-voidBSTree_Insert_Key(BiThrTree&T,intx)//在后继线索二叉排序树T中元素{if(T->data<x)//到右{if(T->rtag)//T没有右时,作为右孩{q->rtag=1;q->rchild=p;}elseBSTree_Insert_Key(T->rchild,x);//T有右时,右elseif(T->data>x)//到左{if(!T->lchild)//T没有左时,作为左孩{;//}elseBSTree_Insert_Key(T->lchild,x);//T有左时,左StatusBSTree_Delete_key(BiThrTree&T,intx)//Tx{BTNode*pre,*ptr,*suc;//ptr为x所在结点,presuc分别指向ptrp=T;last=NULL;lastp的前一个(前驱)while(!p->ltag)p=p->lchild;{if(p->data==x)//找到了元素x结{}elseif(last&&last->data==x)suc=p;找到了xif(p->rtag)p=p->rtag;{while(!p->ltag)p=p-转到中序后继}//whilex及其前驱和后继结点if(!ptr)returnERROR;//未找到待删结点Delete_BSTree(ptr);//x结点if(pre&&pre-pre->rchild=suc;修改线索returnOK;returnvoidDelete_BSTree(BiThrTree&T)//上给出的删除二叉排序树的T的算法,按{elseif(T->ltag&&!T->rtag)//结点无左,此时只需重接其右{{r=r->rchild;//找到结点的前驱rr的双亲}T->data=r->data;rTs->rchild=r-elses->lchild=r->lchild;//重接r的左到其双亲结点free(q);//删除结分析:x结点的前驱和后继,x结点的办法,这样修改线索时会比较简单,直接让前驱的线索指向后继就行了.x结点的同时修改线索,则问voidBSTree_Merge(BiTree&T,BiTree&S)//ST{if(S->lchild)BSTree_Merge(T,S-if(S->rchild)BSTree_Merge(T,S->rchild);合并Insert_Key(T,S);//元素voidInsert_Node(Bitree&T,BTNode*S)//把树结点S到T的合适位置{if(S->data>T-{if(!T->rchild)T->rchild=S;}{{if(!T->lchild)T->lchild=S;}S->lchild=NULL;//的新结点必须和原来的左右断绝关//分析:这是一个与上不同的算法.在合并过程中,并不释放或新建任何结点,而是到另一棵树上,否则将会导致树的结构的.voidBSTree_Split(BiTree&T,BiTree&A,BiTree&B,intx)//把二叉排序树T为两AB,Ax,Bx{if(T->lchild)BSTree_Split(T-if(T->data<=x)elseInsert_Node(B,T);//将元素结点合适的树voidInsert_Node(Bitree&T,BTNode*S)//把树结点S到T的合适位置{if(!T)T=S;//考虑到刚开始时树A和树B为空的情//{if(!T->rchild)T->rchild=S;}{if(!T->lchild)T->lchild=S;}S-typedefstruct

intdata;intbf;intlsize;//lsize域表示该结点的左的结点总数加1ode*lchild,*rchild; ode,*BlcTree;lsizeBTNode*Locate_BlcTree(BlcTreeT,intk)//在含lsizeTk{{if(!T)returnNULL;//k1elseif(T->lsize>k)returnLocate_BlcTree(T->lchild,k);//在左中寻elsereturnLocate_BlcTree(T->rchild,k-T->lsize);//在右中寻找,注意要修改k的值typedefstructenum{LEAF,BRANCH}tag;结点类型标识intkeynum;BPLinkparent;双亲指intkey[MAXCHILD关键字union{BPLinkchild[MAXCHILD];//非叶结点的孩子指针struct{rectype*info[MAXCHILD];//叶子结点的信息针BPNode*next;}}}机查找的算法,ptrpo{//{for(i=0;i<p->keynum&&key>p->key[i];i++);确定关键字所在if(i==p->keynum)returnERROR;//关键字太大}for(i=0;i<p->keynum&&key!=p->key[i];i++);在叶子结点中查找if(i==p->keynum)returnERROR;//找不到关键字returnOK;voidTrieTree_Insert_Key(TrieTree&T,StringTypekey)//在Trie树T中字符串key,StringType的结构见第四章{q->lf.k=key;建叶子结点while(p&&i<=klen&&p-{if(p->kind==BRANCH)//如果最后落到分支结点(无同义词{p->bh.ptr[ord(key[i])]=q;直接连上叶子}else如果最后落到叶子结点(有同义词{r=(TrieNode*)malloc(sizeof(TrieNode));//建立新的分支结last->bh.ptr[ord(key[i-1])]=r;//用新分支结点取代老叶子结点和上一层的联r->bh.ptr[ord(p->lf.k[i])]=p;//新分支结点与新老两个叶子结点相}StatusTrieTree_Delete_Key(TrieTree&T,StringTypekey)//在Trie树T{while(p&&p->kind==BRANCH&&i<=key[0])//查找待删除元{}if(p&&p->kind==LEAF&&p->lf.k=key)//找到了待删除元{returnOK;return}elsereturnERROR;voidPrint_Hash(HashTableH)//Hash表中的所有关键字,其中处理采用线性探测开放定址法{for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeindex线性探测if(H(H.elem[j].key)==i)intH(char*s)//Hash{if(s)returns[0]-96;//求关键一个字母的字母序号(小写)elsereturn0;typedef*LNode[MAXSIZE]CHashTableHashStatusBuild_Hash(CHashTable&T,intm)//输入一组关键字,建立Hash表,m,用链地址法处理.{if(m<1)returnERROR;T=malloc(m*sizeof(WORD建立表头指针向量for(i=0;i<m;i++)while((key=Inputkey())!=NULL)Inputkey{if(!T[n])T[n]=q;作为链表的第一个结点{for(p=T[n];p->next;p=p-p->next=q;//链表尾部.本算法不考虑排序问题}returnOK;StatusL